| /* IRA allocation based on graph coloring. |
| Copyright (C) 2006-2022 Free Software Foundation, Inc. |
| Contributed by Vladimir Makarov <vmakarov@redhat.com>. |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify it under |
| the terms of the GNU General Public License as published by the Free |
| Software Foundation; either version 3, or (at your option) any later |
| version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "target.h" |
| #include "rtl.h" |
| #include "tree.h" |
| #include "predict.h" |
| #include "df.h" |
| #include "memmodel.h" |
| #include "tm_p.h" |
| #include "insn-config.h" |
| #include "regs.h" |
| #include "ira.h" |
| #include "ira-int.h" |
| #include "reload.h" |
| #include "cfgloop.h" |
| |
| /* To prevent soft conflict detection becoming quadratic in the |
| loop depth. Only for very pathological cases, so it hardly |
| seems worth a --param. */ |
| const int max_soft_conflict_loop_depth = 64; |
| |
| typedef struct allocno_hard_regs *allocno_hard_regs_t; |
| |
| /* The structure contains information about hard registers can be |
| assigned to allocnos. Usually it is allocno profitable hard |
| registers but in some cases this set can be a bit different. Major |
| reason of the difference is a requirement to use hard register sets |
| that form a tree or a forest (set of trees), i.e. hard register set |
| of a node should contain hard register sets of its subnodes. */ |
| struct allocno_hard_regs |
| { |
| /* Hard registers can be assigned to an allocno. */ |
| HARD_REG_SET set; |
| /* Overall (spilling) cost of all allocnos with given register |
| set. */ |
| int64_t cost; |
| }; |
| |
| typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t; |
| |
| /* A node representing allocno hard registers. Such nodes form a |
| forest (set of trees). Each subnode of given node in the forest |
| refers for hard register set (usually allocno profitable hard |
| register set) which is a subset of one referred from given |
| node. */ |
| struct allocno_hard_regs_node |
| { |
| /* Set up number of the node in preorder traversing of the forest. */ |
| int preorder_num; |
| /* Used for different calculation like finding conflict size of an |
| allocno. */ |
| int check; |
| /* Used for calculation of conflict size of an allocno. The |
| conflict size of the allocno is maximal number of given allocno |
| hard registers needed for allocation of the conflicting allocnos. |
| Given allocno is trivially colored if this number plus the number |
| of hard registers needed for given allocno is not greater than |
| the number of given allocno hard register set. */ |
| int conflict_size; |
| /* The number of hard registers given by member hard_regs. */ |
| int hard_regs_num; |
| /* The following member is used to form the final forest. */ |
| bool used_p; |
| /* Pointer to the corresponding profitable hard registers. */ |
| allocno_hard_regs_t hard_regs; |
| /* Parent, first subnode, previous and next node with the same |
| parent in the forest. */ |
| allocno_hard_regs_node_t parent, first, prev, next; |
| }; |
| |
| /* Info about changing hard reg costs of an allocno. */ |
| struct update_cost_record |
| { |
| /* Hard regno for which we changed the cost. */ |
| int hard_regno; |
| /* Divisor used when we changed the cost of HARD_REGNO. */ |
| int divisor; |
| /* Next record for given allocno. */ |
| struct update_cost_record *next; |
| }; |
| |
| /* To decrease footprint of ira_allocno structure we store all data |
| needed only for coloring in the following structure. */ |
| struct allocno_color_data |
| { |
| /* TRUE value means that the allocno was not removed yet from the |
| conflicting graph during coloring. */ |
| unsigned int in_graph_p : 1; |
| /* TRUE if it is put on the stack to make other allocnos |
| colorable. */ |
| unsigned int may_be_spilled_p : 1; |
| /* TRUE if the allocno is trivially colorable. */ |
| unsigned int colorable_p : 1; |
| /* Number of hard registers of the allocno class really |
| available for the allocno allocation. It is number of the |
| profitable hard regs. */ |
| int available_regs_num; |
| /* Sum of frequencies of hard register preferences of all |
| conflicting allocnos which are not the coloring stack yet. */ |
| int conflict_allocno_hard_prefs; |
| /* Allocnos in a bucket (used in coloring) chained by the following |
| two members. */ |
| ira_allocno_t next_bucket_allocno; |
| ira_allocno_t prev_bucket_allocno; |
| /* Used for temporary purposes. */ |
| int temp; |
| /* Used to exclude repeated processing. */ |
| int last_process; |
| /* Profitable hard regs available for this pseudo allocation. It |
| means that the set excludes unavailable hard regs and hard regs |
| conflicting with given pseudo. They should be of the allocno |
| class. */ |
| HARD_REG_SET profitable_hard_regs; |
| /* The allocno hard registers node. */ |
| allocno_hard_regs_node_t hard_regs_node; |
| /* Array of structures allocno_hard_regs_subnode representing |
| given allocno hard registers node (the 1st element in the array) |
| and all its subnodes in the tree (forest) of allocno hard |
| register nodes (see comments above). */ |
| int hard_regs_subnodes_start; |
| /* The length of the previous array. */ |
| int hard_regs_subnodes_num; |
| /* Records about updating allocno hard reg costs from copies. If |
| the allocno did not get expected hard register, these records are |
| used to restore original hard reg costs of allocnos connected to |
| this allocno by copies. */ |
| struct update_cost_record *update_cost_records; |
| /* Threads. We collect allocnos connected by copies into threads |
| and try to assign hard regs to allocnos by threads. */ |
| /* Allocno representing all thread. */ |
| ira_allocno_t first_thread_allocno; |
| /* Allocnos in thread forms a cycle list through the following |
| member. */ |
| ira_allocno_t next_thread_allocno; |
| /* All thread frequency. Defined only for first thread allocno. */ |
| int thread_freq; |
| /* Sum of frequencies of hard register preferences of the allocno. */ |
| int hard_reg_prefs; |
| }; |
| |
| /* See above. */ |
| typedef struct allocno_color_data *allocno_color_data_t; |
| |
| /* Container for storing allocno data concerning coloring. */ |
| static allocno_color_data_t allocno_color_data; |
| |
| /* Macro to access the data concerning coloring. */ |
| #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a)) |
| |
| /* Used for finding allocno colorability to exclude repeated allocno |
| processing and for updating preferencing to exclude repeated |
| allocno processing during assignment. */ |
| static int curr_allocno_process; |
| |
| /* This file contains code for regional graph coloring, spill/restore |
| code placement optimization, and code helping the reload pass to do |
| a better job. */ |
| |
| /* Bitmap of allocnos which should be colored. */ |
| static bitmap coloring_allocno_bitmap; |
| |
| /* Bitmap of allocnos which should be taken into account during |
| coloring. In general case it contains allocnos from |
| coloring_allocno_bitmap plus other already colored conflicting |
| allocnos. */ |
| static bitmap consideration_allocno_bitmap; |
| |
| /* All allocnos sorted according their priorities. */ |
| static ira_allocno_t *sorted_allocnos; |
| |
| /* Vec representing the stack of allocnos used during coloring. */ |
| static vec<ira_allocno_t> allocno_stack_vec; |
| |
| /* Helper for qsort comparison callbacks - return a positive integer if |
| X > Y, or a negative value otherwise. Use a conditional expression |
| instead of a difference computation to insulate from possible overflow |
| issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */ |
| #define SORTGT(x,y) (((x) > (y)) ? 1 : -1) |
| |
| |
| |
| /* Definition of vector of allocno hard registers. */ |
| |
| /* Vector of unique allocno hard registers. */ |
| static vec<allocno_hard_regs_t> allocno_hard_regs_vec; |
| |
| struct allocno_hard_regs_hasher : nofree_ptr_hash <allocno_hard_regs> |
| { |
| static inline hashval_t hash (const allocno_hard_regs *); |
| static inline bool equal (const allocno_hard_regs *, |
| const allocno_hard_regs *); |
| }; |
| |
| /* Returns hash value for allocno hard registers V. */ |
| inline hashval_t |
| allocno_hard_regs_hasher::hash (const allocno_hard_regs *hv) |
| { |
| return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0); |
| } |
| |
| /* Compares allocno hard registers V1 and V2. */ |
| inline bool |
| allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1, |
| const allocno_hard_regs *hv2) |
| { |
| return hv1->set == hv2->set; |
| } |
| |
| /* Hash table of unique allocno hard registers. */ |
| static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab; |
| |
| /* Return allocno hard registers in the hash table equal to HV. */ |
| static allocno_hard_regs_t |
| find_hard_regs (allocno_hard_regs_t hv) |
| { |
| return allocno_hard_regs_htab->find (hv); |
| } |
| |
| /* Insert allocno hard registers HV in the hash table (if it is not |
| there yet) and return the value which in the table. */ |
| static allocno_hard_regs_t |
| insert_hard_regs (allocno_hard_regs_t hv) |
| { |
| allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT); |
| |
| if (*slot == NULL) |
| *slot = hv; |
| return *slot; |
| } |
| |
| /* Initialize data concerning allocno hard registers. */ |
| static void |
| init_allocno_hard_regs (void) |
| { |
| allocno_hard_regs_vec.create (200); |
| allocno_hard_regs_htab |
| = new hash_table<allocno_hard_regs_hasher> (200); |
| } |
| |
| /* Add (or update info about) allocno hard registers with SET and |
| COST. */ |
| static allocno_hard_regs_t |
| add_allocno_hard_regs (HARD_REG_SET set, int64_t cost) |
| { |
| struct allocno_hard_regs temp; |
| allocno_hard_regs_t hv; |
| |
| gcc_assert (! hard_reg_set_empty_p (set)); |
| temp.set = set; |
| if ((hv = find_hard_regs (&temp)) != NULL) |
| hv->cost += cost; |
| else |
| { |
| hv = ((struct allocno_hard_regs *) |
| ira_allocate (sizeof (struct allocno_hard_regs))); |
| hv->set = set; |
| hv->cost = cost; |
| allocno_hard_regs_vec.safe_push (hv); |
| insert_hard_regs (hv); |
| } |
| return hv; |
| } |
| |
| /* Finalize data concerning allocno hard registers. */ |
| static void |
| finish_allocno_hard_regs (void) |
| { |
| int i; |
| allocno_hard_regs_t hv; |
| |
| for (i = 0; |
| allocno_hard_regs_vec.iterate (i, &hv); |
| i++) |
| ira_free (hv); |
| delete allocno_hard_regs_htab; |
| allocno_hard_regs_htab = NULL; |
| allocno_hard_regs_vec.release (); |
| } |
| |
| /* Sort hard regs according to their frequency of usage. */ |
| static int |
| allocno_hard_regs_compare (const void *v1p, const void *v2p) |
| { |
| allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p; |
| allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p; |
| |
| if (hv2->cost > hv1->cost) |
| return 1; |
| else if (hv2->cost < hv1->cost) |
| return -1; |
| return SORTGT (allocno_hard_regs_hasher::hash(hv2), allocno_hard_regs_hasher::hash(hv1)); |
| } |
| |
| |
| |
| /* Used for finding a common ancestor of two allocno hard registers |
| nodes in the forest. We use the current value of |
| 'node_check_tick' to mark all nodes from one node to the top and |
| then walking up from another node until we find a marked node. |
| |
| It is also used to figure out allocno colorability as a mark that |
| we already reset value of member 'conflict_size' for the forest |
| node corresponding to the processed allocno. */ |
| static int node_check_tick; |
| |
| /* Roots of the forest containing hard register sets can be assigned |
| to allocnos. */ |
| static allocno_hard_regs_node_t hard_regs_roots; |
| |
| /* Definition of vector of allocno hard register nodes. */ |
| |
| /* Vector used to create the forest. */ |
| static vec<allocno_hard_regs_node_t> hard_regs_node_vec; |
| |
| /* Create and return allocno hard registers node containing allocno |
| hard registers HV. */ |
| static allocno_hard_regs_node_t |
| create_new_allocno_hard_regs_node (allocno_hard_regs_t hv) |
| { |
| allocno_hard_regs_node_t new_node; |
| |
| new_node = ((struct allocno_hard_regs_node *) |
| ira_allocate (sizeof (struct allocno_hard_regs_node))); |
| new_node->check = 0; |
| new_node->hard_regs = hv; |
| new_node->hard_regs_num = hard_reg_set_size (hv->set); |
| new_node->first = NULL; |
| new_node->used_p = false; |
| return new_node; |
| } |
| |
| /* Add allocno hard registers node NEW_NODE to the forest on its level |
| given by ROOTS. */ |
| static void |
| add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots, |
| allocno_hard_regs_node_t new_node) |
| { |
| new_node->next = *roots; |
| if (new_node->next != NULL) |
| new_node->next->prev = new_node; |
| new_node->prev = NULL; |
| *roots = new_node; |
| } |
| |
| /* Add allocno hard registers HV (or its best approximation if it is |
| not possible) to the forest on its level given by ROOTS. */ |
| static void |
| add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots, |
| allocno_hard_regs_t hv) |
| { |
| unsigned int i, start; |
| allocno_hard_regs_node_t node, prev, new_node; |
| HARD_REG_SET temp_set; |
| allocno_hard_regs_t hv2; |
| |
| start = hard_regs_node_vec.length (); |
| for (node = *roots; node != NULL; node = node->next) |
| { |
| if (hv->set == node->hard_regs->set) |
| return; |
| if (hard_reg_set_subset_p (hv->set, node->hard_regs->set)) |
| { |
| add_allocno_hard_regs_to_forest (&node->first, hv); |
| return; |
| } |
| if (hard_reg_set_subset_p (node->hard_regs->set, hv->set)) |
| hard_regs_node_vec.safe_push (node); |
| else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set)) |
| { |
| temp_set = hv->set & node->hard_regs->set; |
| hv2 = add_allocno_hard_regs (temp_set, hv->cost); |
| add_allocno_hard_regs_to_forest (&node->first, hv2); |
| } |
| } |
| if (hard_regs_node_vec.length () |
| > start + 1) |
| { |
| /* Create a new node which contains nodes in hard_regs_node_vec. */ |
| CLEAR_HARD_REG_SET (temp_set); |
| for (i = start; |
| i < hard_regs_node_vec.length (); |
| i++) |
| { |
| node = hard_regs_node_vec[i]; |
| temp_set |= node->hard_regs->set; |
| } |
| hv = add_allocno_hard_regs (temp_set, hv->cost); |
| new_node = create_new_allocno_hard_regs_node (hv); |
| prev = NULL; |
| for (i = start; |
| i < hard_regs_node_vec.length (); |
| i++) |
| { |
| node = hard_regs_node_vec[i]; |
| if (node->prev == NULL) |
| *roots = node->next; |
| else |
| node->prev->next = node->next; |
| if (node->next != NULL) |
| node->next->prev = node->prev; |
| if (prev == NULL) |
| new_node->first = node; |
| else |
| prev->next = node; |
| node->prev = prev; |
| node->next = NULL; |
| prev = node; |
| } |
| add_new_allocno_hard_regs_node_to_forest (roots, new_node); |
| } |
| hard_regs_node_vec.truncate (start); |
| } |
| |
| /* Add allocno hard registers nodes starting with the forest level |
| given by FIRST which contains biggest set inside SET. */ |
| static void |
| collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first, |
| HARD_REG_SET set) |
| { |
| allocno_hard_regs_node_t node; |
| |
| ira_assert (first != NULL); |
| for (node = first; node != NULL; node = node->next) |
| if (hard_reg_set_subset_p (node->hard_regs->set, set)) |
| hard_regs_node_vec.safe_push (node); |
| else if (hard_reg_set_intersect_p (set, node->hard_regs->set)) |
| collect_allocno_hard_regs_cover (node->first, set); |
| } |
| |
| /* Set up field parent as PARENT in all allocno hard registers nodes |
| in forest given by FIRST. */ |
| static void |
| setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first, |
| allocno_hard_regs_node_t parent) |
| { |
| allocno_hard_regs_node_t node; |
| |
| for (node = first; node != NULL; node = node->next) |
| { |
| node->parent = parent; |
| setup_allocno_hard_regs_nodes_parent (node->first, node); |
| } |
| } |
| |
| /* Return allocno hard registers node which is a first common ancestor |
| node of FIRST and SECOND in the forest. */ |
| static allocno_hard_regs_node_t |
| first_common_ancestor_node (allocno_hard_regs_node_t first, |
| allocno_hard_regs_node_t second) |
| { |
| allocno_hard_regs_node_t node; |
| |
| node_check_tick++; |
| for (node = first; node != NULL; node = node->parent) |
| node->check = node_check_tick; |
| for (node = second; node != NULL; node = node->parent) |
| if (node->check == node_check_tick) |
| return node; |
| return first_common_ancestor_node (second, first); |
| } |
| |
| /* Print hard reg set SET to F. */ |
| static void |
| print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p) |
| { |
| int i, start, end; |
| |
| for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++) |
| { |
| bool reg_included = TEST_HARD_REG_BIT (set, i); |
| |
| if (reg_included) |
| { |
| if (start == -1) |
| start = i; |
| end = i; |
| } |
| if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1)) |
| { |
| if (start == end) |
| fprintf (f, " %d", start); |
| else if (start == end + 1) |
| fprintf (f, " %d %d", start, end); |
| else |
| fprintf (f, " %d-%d", start, end); |
| start = -1; |
| } |
| } |
| if (new_line_p) |
| fprintf (f, "\n"); |
| } |
| |
| /* Print allocno hard register subforest given by ROOTS and its LEVEL |
| to F. */ |
| static void |
| print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots, |
| int level) |
| { |
| int i; |
| allocno_hard_regs_node_t node; |
| |
| for (node = roots; node != NULL; node = node->next) |
| { |
| fprintf (f, " "); |
| for (i = 0; i < level * 2; i++) |
| fprintf (f, " "); |
| fprintf (f, "%d:(", node->preorder_num); |
| print_hard_reg_set (f, node->hard_regs->set, false); |
| fprintf (f, ")@%" PRId64"\n", node->hard_regs->cost); |
| print_hard_regs_subforest (f, node->first, level + 1); |
| } |
| } |
| |
| /* Print the allocno hard register forest to F. */ |
| static void |
| print_hard_regs_forest (FILE *f) |
| { |
| fprintf (f, " Hard reg set forest:\n"); |
| print_hard_regs_subforest (f, hard_regs_roots, 1); |
| } |
| |
| /* Print the allocno hard register forest to stderr. */ |
| void |
| ira_debug_hard_regs_forest (void) |
| { |
| print_hard_regs_forest (stderr); |
| } |
| |
| /* Remove unused allocno hard registers nodes from forest given by its |
| *ROOTS. */ |
| static void |
| remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots) |
| { |
| allocno_hard_regs_node_t node, prev, next, last; |
| |
| for (prev = NULL, node = *roots; node != NULL; node = next) |
| { |
| next = node->next; |
| if (node->used_p) |
| { |
| remove_unused_allocno_hard_regs_nodes (&node->first); |
| prev = node; |
| } |
| else |
| { |
| for (last = node->first; |
| last != NULL && last->next != NULL; |
| last = last->next) |
| ; |
| if (last != NULL) |
| { |
| if (prev == NULL) |
| *roots = node->first; |
| else |
| prev->next = node->first; |
| if (next != NULL) |
| next->prev = last; |
| last->next = next; |
| next = node->first; |
| } |
| else |
| { |
| if (prev == NULL) |
| *roots = next; |
| else |
| prev->next = next; |
| if (next != NULL) |
| next->prev = prev; |
| } |
| ira_free (node); |
| } |
| } |
| } |
| |
| /* Set up fields preorder_num starting with START_NUM in all allocno |
| hard registers nodes in forest given by FIRST. Return biggest set |
| PREORDER_NUM increased by 1. */ |
| static int |
| enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first, |
| allocno_hard_regs_node_t parent, |
| int start_num) |
| { |
| allocno_hard_regs_node_t node; |
| |
| for (node = first; node != NULL; node = node->next) |
| { |
| node->preorder_num = start_num++; |
| node->parent = parent; |
| start_num = enumerate_allocno_hard_regs_nodes (node->first, node, |
| start_num); |
| } |
| return start_num; |
| } |
| |
| /* Number of allocno hard registers nodes in the forest. */ |
| static int allocno_hard_regs_nodes_num; |
| |
| /* Table preorder number of allocno hard registers node in the forest |
| -> the allocno hard registers node. */ |
| static allocno_hard_regs_node_t *allocno_hard_regs_nodes; |
| |
| /* See below. */ |
| typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t; |
| |
| /* The structure is used to describes all subnodes (not only immediate |
| ones) in the mentioned above tree for given allocno hard register |
| node. The usage of such data accelerates calculation of |
| colorability of given allocno. */ |
| struct allocno_hard_regs_subnode |
| { |
| /* The conflict size of conflicting allocnos whose hard register |
| sets are equal sets (plus supersets if given node is given |
| allocno hard registers node) of one in the given node. */ |
| int left_conflict_size; |
| /* The summary conflict size of conflicting allocnos whose hard |
| register sets are strict subsets of one in the given node. |
| Overall conflict size is |
| left_conflict_subnodes_size |
| + MIN (max_node_impact - left_conflict_subnodes_size, |
| left_conflict_size) |
| */ |
| short left_conflict_subnodes_size; |
| short max_node_impact; |
| }; |
| |
| /* Container for hard regs subnodes of all allocnos. */ |
| static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes; |
| |
| /* Table (preorder number of allocno hard registers node in the |
| forest, preorder number of allocno hard registers subnode) -> index |
| of the subnode relative to the node. -1 if it is not a |
| subnode. */ |
| static int *allocno_hard_regs_subnode_index; |
| |
| /* Setup arrays ALLOCNO_HARD_REGS_NODES and |
| ALLOCNO_HARD_REGS_SUBNODE_INDEX. */ |
| static void |
| setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first) |
| { |
| allocno_hard_regs_node_t node, parent; |
| int index; |
| |
| for (node = first; node != NULL; node = node->next) |
| { |
| allocno_hard_regs_nodes[node->preorder_num] = node; |
| for (parent = node; parent != NULL; parent = parent->parent) |
| { |
| index = parent->preorder_num * allocno_hard_regs_nodes_num; |
| allocno_hard_regs_subnode_index[index + node->preorder_num] |
| = node->preorder_num - parent->preorder_num; |
| } |
| setup_allocno_hard_regs_subnode_index (node->first); |
| } |
| } |
| |
| /* Count all allocno hard registers nodes in tree ROOT. */ |
| static int |
| get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root) |
| { |
| int len = 1; |
| |
| for (root = root->first; root != NULL; root = root->next) |
| len += get_allocno_hard_regs_subnodes_num (root); |
| return len; |
| } |
| |
| /* Build the forest of allocno hard registers nodes and assign each |
| allocno a node from the forest. */ |
| static void |
| form_allocno_hard_regs_nodes_forest (void) |
| { |
| unsigned int i, j, size, len; |
| int start; |
| ira_allocno_t a; |
| allocno_hard_regs_t hv; |
| bitmap_iterator bi; |
| HARD_REG_SET temp; |
| allocno_hard_regs_node_t node, allocno_hard_regs_node; |
| allocno_color_data_t allocno_data; |
| |
| node_check_tick = 0; |
| init_allocno_hard_regs (); |
| hard_regs_roots = NULL; |
| hard_regs_node_vec.create (100); |
| for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) |
| if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i)) |
| { |
| CLEAR_HARD_REG_SET (temp); |
| SET_HARD_REG_BIT (temp, i); |
| hv = add_allocno_hard_regs (temp, 0); |
| node = create_new_allocno_hard_regs_node (hv); |
| add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node); |
| } |
| start = allocno_hard_regs_vec.length (); |
| EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) |
| { |
| a = ira_allocnos[i]; |
| allocno_data = ALLOCNO_COLOR_DATA (a); |
| |
| if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs)) |
| continue; |
| hv = (add_allocno_hard_regs |
| (allocno_data->profitable_hard_regs, |
| ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))); |
| } |
| temp = ~ira_no_alloc_regs; |
| add_allocno_hard_regs (temp, 0); |
| qsort (allocno_hard_regs_vec.address () + start, |
| allocno_hard_regs_vec.length () - start, |
| sizeof (allocno_hard_regs_t), allocno_hard_regs_compare); |
| for (i = start; |
| allocno_hard_regs_vec.iterate (i, &hv); |
| i++) |
| { |
| add_allocno_hard_regs_to_forest (&hard_regs_roots, hv); |
| ira_assert (hard_regs_node_vec.length () == 0); |
| } |
| /* We need to set up parent fields for right work of |
| first_common_ancestor_node. */ |
| setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL); |
| EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) |
| { |
| a = ira_allocnos[i]; |
| allocno_data = ALLOCNO_COLOR_DATA (a); |
| if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs)) |
| continue; |
| hard_regs_node_vec.truncate (0); |
| collect_allocno_hard_regs_cover (hard_regs_roots, |
| allocno_data->profitable_hard_regs); |
| allocno_hard_regs_node = NULL; |
| for (j = 0; hard_regs_node_vec.iterate (j, &node); j++) |
| allocno_hard_regs_node |
| = (j == 0 |
| ? node |
| : first_common_ancestor_node (node, allocno_hard_regs_node)); |
| /* That is a temporary storage. */ |
| allocno_hard_regs_node->used_p = true; |
| allocno_data->hard_regs_node = allocno_hard_regs_node; |
| } |
| ira_assert (hard_regs_roots->next == NULL); |
| hard_regs_roots->used_p = true; |
| remove_unused_allocno_hard_regs_nodes (&hard_regs_roots); |
| allocno_hard_regs_nodes_num |
| = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0); |
| allocno_hard_regs_nodes |
| = ((allocno_hard_regs_node_t *) |
| ira_allocate (allocno_hard_regs_nodes_num |
| * sizeof (allocno_hard_regs_node_t))); |
| size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num; |
| allocno_hard_regs_subnode_index |
| = (int *) ira_allocate (size * sizeof (int)); |
| for (i = 0; i < size; i++) |
| allocno_hard_regs_subnode_index[i] = -1; |
| setup_allocno_hard_regs_subnode_index (hard_regs_roots); |
| start = 0; |
| EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) |
| { |
| a = ira_allocnos[i]; |
| allocno_data = ALLOCNO_COLOR_DATA (a); |
| if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs)) |
| continue; |
| len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node); |
| allocno_data->hard_regs_subnodes_start = start; |
| allocno_data->hard_regs_subnodes_num = len; |
| start += len; |
| } |
| allocno_hard_regs_subnodes |
| = ((allocno_hard_regs_subnode_t) |
| ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start)); |
| hard_regs_node_vec.release (); |
| } |
| |
| /* Free tree of allocno hard registers nodes given by its ROOT. */ |
| static void |
| finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root) |
| { |
| allocno_hard_regs_node_t child, next; |
| |
| for (child = root->first; child != NULL; child = next) |
| { |
| next = child->next; |
| finish_allocno_hard_regs_nodes_tree (child); |
| } |
| ira_free (root); |
| } |
| |
| /* Finish work with the forest of allocno hard registers nodes. */ |
| static void |
| finish_allocno_hard_regs_nodes_forest (void) |
| { |
| allocno_hard_regs_node_t node, next; |
| |
| ira_free (allocno_hard_regs_subnodes); |
| for (node = hard_regs_roots; node != NULL; node = next) |
| { |
| next = node->next; |
| finish_allocno_hard_regs_nodes_tree (node); |
| } |
| ira_free (allocno_hard_regs_nodes); |
| ira_free (allocno_hard_regs_subnode_index); |
| finish_allocno_hard_regs (); |
| } |
| |
| /* Set up left conflict sizes and left conflict subnodes sizes of hard |
| registers subnodes of allocno A. Return TRUE if allocno A is |
| trivially colorable. */ |
| static bool |
| setup_left_conflict_sizes_p (ira_allocno_t a) |
| { |
| int i, k, nobj, start; |
| int conflict_size, left_conflict_subnodes_size, node_preorder_num; |
| allocno_color_data_t data; |
| HARD_REG_SET profitable_hard_regs; |
| allocno_hard_regs_subnode_t subnodes; |
| allocno_hard_regs_node_t node; |
| HARD_REG_SET node_set; |
| |
| nobj = ALLOCNO_NUM_OBJECTS (a); |
| data = ALLOCNO_COLOR_DATA (a); |
| subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start; |
| profitable_hard_regs = data->profitable_hard_regs; |
| node = data->hard_regs_node; |
| node_preorder_num = node->preorder_num; |
| node_set = node->hard_regs->set; |
| node_check_tick++; |
| for (k = 0; k < nobj; k++) |
| { |
| ira_object_t obj = ALLOCNO_OBJECT (a, k); |
| ira_object_t conflict_obj; |
| ira_object_conflict_iterator oci; |
| |
| FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) |
| { |
| int size; |
| ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); |
| allocno_hard_regs_node_t conflict_node, temp_node; |
| HARD_REG_SET conflict_node_set; |
| allocno_color_data_t conflict_data; |
| |
| conflict_data = ALLOCNO_COLOR_DATA (conflict_a); |
| if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p |
| || ! hard_reg_set_intersect_p (profitable_hard_regs, |
| conflict_data |
| ->profitable_hard_regs)) |
| continue; |
| conflict_node = conflict_data->hard_regs_node; |
| conflict_node_set = conflict_node->hard_regs->set; |
| if (hard_reg_set_subset_p (node_set, conflict_node_set)) |
| temp_node = node; |
| else |
| { |
| ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set)); |
| temp_node = conflict_node; |
| } |
| if (temp_node->check != node_check_tick) |
| { |
| temp_node->check = node_check_tick; |
| temp_node->conflict_size = 0; |
| } |
| size = (ira_reg_class_max_nregs |
| [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]); |
| if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1) |
| /* We will deal with the subwords individually. */ |
| size = 1; |
| temp_node->conflict_size += size; |
| } |
| } |
| for (i = 0; i < data->hard_regs_subnodes_num; i++) |
| { |
| allocno_hard_regs_node_t temp_node; |
| |
| temp_node = allocno_hard_regs_nodes[i + node_preorder_num]; |
| ira_assert (temp_node->preorder_num == i + node_preorder_num); |
| subnodes[i].left_conflict_size = (temp_node->check != node_check_tick |
| ? 0 : temp_node->conflict_size); |
| if (hard_reg_set_subset_p (temp_node->hard_regs->set, |
| profitable_hard_regs)) |
| subnodes[i].max_node_impact = temp_node->hard_regs_num; |
| else |
| { |
| HARD_REG_SET temp_set; |
| int j, n, hard_regno; |
| enum reg_class aclass; |
| |
| temp_set = temp_node->hard_regs->set & profitable_hard_regs; |
| aclass = ALLOCNO_CLASS (a); |
| for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--) |
| { |
| hard_regno = ira_class_hard_regs[aclass][j]; |
| if (TEST_HARD_REG_BIT (temp_set, hard_regno)) |
| n++; |
| } |
| subnodes[i].max_node_impact = n; |
| } |
| subnodes[i].left_conflict_subnodes_size = 0; |
| } |
| start = node_preorder_num * allocno_hard_regs_nodes_num; |
| for (i = data->hard_regs_subnodes_num - 1; i > 0; i--) |
| { |
| int size, parent_i; |
| allocno_hard_regs_node_t parent; |
| |
| size = (subnodes[i].left_conflict_subnodes_size |
| + MIN (subnodes[i].max_node_impact |
| - subnodes[i].left_conflict_subnodes_size, |
| subnodes[i].left_conflict_size)); |
| parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent; |
| gcc_checking_assert(parent); |
| parent_i |
| = allocno_hard_regs_subnode_index[start + parent->preorder_num]; |
| gcc_checking_assert(parent_i >= 0); |
| subnodes[parent_i].left_conflict_subnodes_size += size; |
| } |
| left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size; |
| conflict_size |
| = (left_conflict_subnodes_size |
| + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size, |
| subnodes[0].left_conflict_size)); |
| conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]; |
| data->colorable_p = conflict_size <= data->available_regs_num; |
| return data->colorable_p; |
| } |
| |
| /* Update left conflict sizes of hard registers subnodes of allocno A |
| after removing allocno REMOVED_A with SIZE from the conflict graph. |
| Return TRUE if A is trivially colorable. */ |
| static bool |
| update_left_conflict_sizes_p (ira_allocno_t a, |
| ira_allocno_t removed_a, int size) |
| { |
| int i, conflict_size, before_conflict_size, diff, start; |
| int node_preorder_num, parent_i; |
| allocno_hard_regs_node_t node, removed_node, parent; |
| allocno_hard_regs_subnode_t subnodes; |
| allocno_color_data_t data = ALLOCNO_COLOR_DATA (a); |
| |
| ira_assert (! data->colorable_p); |
| node = data->hard_regs_node; |
| node_preorder_num = node->preorder_num; |
| removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node; |
| ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set, |
| node->hard_regs->set) |
| || hard_reg_set_subset_p (node->hard_regs->set, |
| removed_node->hard_regs->set)); |
| start = node_preorder_num * allocno_hard_regs_nodes_num; |
| i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num]; |
| if (i < 0) |
| i = 0; |
| subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start; |
| before_conflict_size |
| = (subnodes[i].left_conflict_subnodes_size |
| + MIN (subnodes[i].max_node_impact |
| - subnodes[i].left_conflict_subnodes_size, |
| subnodes[i].left_conflict_size)); |
| subnodes[i].left_conflict_size -= size; |
| for (;;) |
| { |
| conflict_size |
| = (subnodes[i].left_conflict_subnodes_size |
| + MIN (subnodes[i].max_node_impact |
| - subnodes[i].left_conflict_subnodes_size, |
| subnodes[i].left_conflict_size)); |
| if ((diff = before_conflict_size - conflict_size) == 0) |
| break; |
| ira_assert (conflict_size < before_conflict_size); |
| parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent; |
| if (parent == NULL) |
| break; |
| parent_i |
| = allocno_hard_regs_subnode_index[start + parent->preorder_num]; |
| if (parent_i < 0) |
| break; |
| i = parent_i; |
| before_conflict_size |
| = (subnodes[i].left_conflict_subnodes_size |
| + MIN (subnodes[i].max_node_impact |
| - subnodes[i].left_conflict_subnodes_size, |
| subnodes[i].left_conflict_size)); |
| subnodes[i].left_conflict_subnodes_size -= diff; |
| } |
| if (i != 0 |
| || (conflict_size |
| + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)] |
| > data->available_regs_num)) |
| return false; |
| data->colorable_p = true; |
| return true; |
| } |
| |
| /* Return true if allocno A has empty profitable hard regs. */ |
| static bool |
| empty_profitable_hard_regs (ira_allocno_t a) |
| { |
| allocno_color_data_t data = ALLOCNO_COLOR_DATA (a); |
| |
| return hard_reg_set_empty_p (data->profitable_hard_regs); |
| } |
| |
| /* Set up profitable hard registers for each allocno being |
| colored. */ |
| static void |
| setup_profitable_hard_regs (void) |
| { |
| unsigned int i; |
| int j, k, nobj, hard_regno, nregs, class_size; |
| ira_allocno_t a; |
| bitmap_iterator bi; |
| enum reg_class aclass; |
| machine_mode mode; |
| allocno_color_data_t data; |
| |
| /* Initial set up from allocno classes and explicitly conflicting |
| hard regs. */ |
| EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) |
| { |
| a = ira_allocnos[i]; |
| if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS) |
| continue; |
| data = ALLOCNO_COLOR_DATA (a); |
| if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL |
| && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a) |
| /* Do not empty profitable regs for static chain pointer |
| pseudo when non-local goto is used. */ |
| && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a))) |
| CLEAR_HARD_REG_SET (data->profitable_hard_regs); |
| else |
| { |
| mode = ALLOCNO_MODE (a); |
| data->profitable_hard_regs |
| = ira_useful_class_mode_regs[aclass][mode]; |
| nobj = ALLOCNO_NUM_OBJECTS (a); |
| for (k = 0; k < nobj; k++) |
| { |
| ira_object_t obj = ALLOCNO_OBJECT (a, k); |
| |
| data->profitable_hard_regs |
| &= ~OBJECT_TOTAL_CONFLICT_HARD_REGS (obj); |
| } |
| } |
| } |
| /* Exclude hard regs already assigned for conflicting objects. */ |
| EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi) |
| { |
| a = ira_allocnos[i]; |
| if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS |
| || ! ALLOCNO_ASSIGNED_P (a) |
| || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0) |
| continue; |
| mode = ALLOCNO_MODE (a); |
| nregs = hard_regno_nregs (hard_regno, mode); |
| nobj = ALLOCNO_NUM_OBJECTS (a); |
| for (k = 0; k < nobj; k++) |
| { |
| ira_object_t obj = ALLOCNO_OBJECT (a, k); |
| ira_object_t conflict_obj; |
| ira_object_conflict_iterator oci; |
| |
| FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) |
| { |
| ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); |
| |
| /* We can process the conflict allocno repeatedly with |
| the same result. */ |
| if (nregs == nobj && nregs > 1) |
| { |
| int num = OBJECT_SUBWORD (conflict_obj); |
| |
| if (REG_WORDS_BIG_ENDIAN) |
| CLEAR_HARD_REG_BIT |
| (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs, |
| hard_regno + nobj - num - 1); |
| else |
| CLEAR_HARD_REG_BIT |
| (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs, |
| hard_regno + num); |
| } |
| else |
| ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs |
| &= ~ira_reg_mode_hard_regset[hard_regno][mode]; |
| } |
| } |
| } |
| /* Exclude too costly hard regs. */ |
| EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) |
| { |
| int min_cost = INT_MAX; |
| int *costs; |
| |
| a = ira_allocnos[i]; |
| if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS |
| || empty_profitable_hard_regs (a)) |
| continue; |
| data = ALLOCNO_COLOR_DATA (a); |
| if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL |
| || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL) |
| { |
| class_size = ira_class_hard_regs_num[aclass]; |
| for (j = 0; j < class_size; j++) |
| { |
| hard_regno = ira_class_hard_regs[aclass][j]; |
| if (! TEST_HARD_REG_BIT (data->profitable_hard_regs, |
| hard_regno)) |
| continue; |
| if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j] |
| /* Do not remove HARD_REGNO for static chain pointer |
| pseudo when non-local goto is used. */ |
| && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a))) |
| CLEAR_HARD_REG_BIT (data->profitable_hard_regs, |
| hard_regno); |
| else if (min_cost > costs[j]) |
| min_cost = costs[j]; |
| } |
| } |
| else if (ALLOCNO_UPDATED_MEMORY_COST (a) |
| < ALLOCNO_UPDATED_CLASS_COST (a) |
| /* Do not empty profitable regs for static chain |
| pointer pseudo when non-local goto is used. */ |
| && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a))) |
| CLEAR_HARD_REG_SET (data->profitable_hard_regs); |
| if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost) |
| ALLOCNO_UPDATED_CLASS_COST (a) = min_cost; |
| } |
| } |
| |
| |
| |
| /* This page contains functions used to choose hard registers for |
| allocnos. */ |
| |
| /* Pool for update cost records. */ |
| static object_allocator<update_cost_record> update_cost_record_pool |
| ("update cost records"); |
| |
| /* Return new update cost record with given params. */ |
| static struct update_cost_record * |
| get_update_cost_record (int hard_regno, int divisor, |
| struct update_cost_record *next) |
| { |
| struct update_cost_record *record; |
| |
| record = update_cost_record_pool.allocate (); |
| record->hard_regno = hard_regno; |
| record->divisor = divisor; |
| record->next = next; |
| return record; |
| } |
| |
| /* Free memory for all records in LIST. */ |
| static void |
| free_update_cost_record_list (struct update_cost_record *list) |
| { |
| struct update_cost_record *next; |
| |
| while (list != NULL) |
| { |
| next = list->next; |
| update_cost_record_pool.remove (list); |
| list = next; |
| } |
| } |
| |
| /* Free memory allocated for all update cost records. */ |
| static void |
| finish_update_cost_records (void) |
| { |
| update_cost_record_pool.release (); |
| } |
| |
| /* Array whose element value is TRUE if the corresponding hard |
| register was already allocated for an allocno. */ |
| static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER]; |
| |
| /* Describes one element in a queue of allocnos whose costs need to be |
| updated. Each allocno in the queue is known to have an allocno |
| class. */ |
| struct update_cost_queue_elem |
| { |
| /* This element is in the queue iff CHECK == update_cost_check. */ |
| int check; |
| |
| /* COST_HOP_DIVISOR**N, where N is the length of the shortest path |
| connecting this allocno to the one being allocated. */ |
| int divisor; |
| |
| /* Allocno from which we started chaining costs of connected |
| allocnos. */ |
| ira_allocno_t start; |
| |
| /* Allocno from which we are chaining costs of connected allocnos. |
| It is used not go back in graph of allocnos connected by |
| copies. */ |
| ira_allocno_t from; |
| |
| /* The next allocno in the queue, or null if this is the last element. */ |
| ira_allocno_t next; |
| }; |
| |
| /* The first element in a queue of allocnos whose copy costs need to be |
| updated. Null if the queue is empty. */ |
| static ira_allocno_t update_cost_queue; |
| |
| /* The last element in the queue described by update_cost_queue. |
| Not valid if update_cost_queue is null. */ |
| static struct update_cost_queue_elem *update_cost_queue_tail; |
| |
| /* A pool of elements in the queue described by update_cost_queue. |
| Elements are indexed by ALLOCNO_NUM. */ |
| static struct update_cost_queue_elem *update_cost_queue_elems; |
| |
| /* The current value of update_costs_from_copies call count. */ |
| static int update_cost_check; |
| |
| /* Allocate and initialize data necessary for function |
| update_costs_from_copies. */ |
| static void |
| initiate_cost_update (void) |
| { |
| size_t size; |
| |
| size = ira_allocnos_num * sizeof (struct update_cost_queue_elem); |
| update_cost_queue_elems |
| = (struct update_cost_queue_elem *) ira_allocate (size); |
| memset (update_cost_queue_elems, 0, size); |
| update_cost_check = 0; |
| } |
| |
| /* Deallocate data used by function update_costs_from_copies. */ |
| static void |
| finish_cost_update (void) |
| { |
| ira_free (update_cost_queue_elems); |
| finish_update_cost_records (); |
| } |
| |
| /* When we traverse allocnos to update hard register costs, the cost |
| divisor will be multiplied by the following macro value for each |
| hop from given allocno to directly connected allocnos. */ |
| #define COST_HOP_DIVISOR 4 |
| |
| /* Start a new cost-updating pass. */ |
| static void |
| start_update_cost (void) |
| { |
| update_cost_check++; |
| update_cost_queue = NULL; |
| } |
| |
| /* Add (ALLOCNO, START, FROM, DIVISOR) to the end of update_cost_queue, unless |
| ALLOCNO is already in the queue, or has NO_REGS class. */ |
| static inline void |
| queue_update_cost (ira_allocno_t allocno, ira_allocno_t start, |
| ira_allocno_t from, int divisor) |
| { |
| struct update_cost_queue_elem *elem; |
| |
| elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)]; |
| if (elem->check != update_cost_check |
| && ALLOCNO_CLASS (allocno) != NO_REGS) |
| { |
| elem->check = update_cost_check; |
| elem->start = start; |
| elem->from = from; |
| elem->divisor = divisor; |
| elem->next = NULL; |
| if (update_cost_queue == NULL) |
| update_cost_queue = allocno; |
| else |
| update_cost_queue_tail->next = allocno; |
| update_cost_queue_tail = elem; |
| } |
| } |
| |
| /* Try to remove the first element from update_cost_queue. Return |
| false if the queue was empty, otherwise make (*ALLOCNO, *START, |
| *FROM, *DIVISOR) describe the removed element. */ |
| static inline bool |
| get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *start, |
| ira_allocno_t *from, int *divisor) |
| { |
| struct update_cost_queue_elem *elem; |
| |
| if (update_cost_queue == NULL) |
| return false; |
| |
| *allocno = update_cost_queue; |
| elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)]; |
| *start = elem->start; |
| *from = elem->from; |
| *divisor = elem->divisor; |
| update_cost_queue = elem->next; |
| return true; |
| } |
| |
| /* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by |
| UPDATE_CONFLICT_COST for ALLOCNO. Return true if we really |
| modified the cost. */ |
| static bool |
| update_allocno_cost (ira_allocno_t allocno, int hard_regno, |
| int update_cost, int update_conflict_cost) |
| { |
| int i; |
| enum reg_class aclass = ALLOCNO_CLASS (allocno); |
| |
| i = ira_class_hard_reg_index[aclass][hard_regno]; |
| if (i < 0) |
| return false; |
| ira_allocate_and_set_or_copy_costs |
| (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass, |
| ALLOCNO_UPDATED_CLASS_COST (allocno), |
| ALLOCNO_HARD_REG_COSTS (allocno)); |
| ira_allocate_and_set_or_copy_costs |
| (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno), |
| aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno)); |
| ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost; |
| ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_conflict_cost; |
| return true; |
| } |
| |
| /* Return TRUE if the object OBJ conflicts with the allocno A. */ |
| static bool |
| object_conflicts_with_allocno_p (ira_object_t obj, ira_allocno_t a) |
| { |
| if (!OBJECT_CONFLICT_VEC_P (obj)) |
| for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a); word++) |
| { |
| ira_object_t another_obj = ALLOCNO_OBJECT (a, word); |
| if (OBJECT_CONFLICT_ID (another_obj) >= OBJECT_MIN (obj) |
| && OBJECT_CONFLICT_ID (another_obj) <= OBJECT_MAX (obj) |
| && TEST_MINMAX_SET_BIT (OBJECT_CONFLICT_BITVEC (obj), |
| OBJECT_CONFLICT_ID (another_obj), |
| OBJECT_MIN (obj), OBJECT_MAX (obj))) |
| return true; |
| } |
| else |
| { |
| /* If this linear walk ever becomes a bottleneck we could add a |
| conflict_vec_sorted_p flag and if not set, sort the conflicts after |
| their ID so we can use a binary search. That would also require |
| tracking the actual number of conflicts in the vector to not rely |
| on the NULL termination. */ |
| ira_object_conflict_iterator oci; |
| ira_object_t conflict_obj; |
| FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) |
| if (OBJECT_ALLOCNO (conflict_obj) == a) |
| return true; |
| } |
| return false; |
| } |
| |
| /* Return TRUE if allocnos A1 and A2 conflicts. Here we are |
| interested only in conflicts of allocnos with intersecting allocno |
| classes. */ |
| static bool |
| allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t a2) |
| { |
| /* Compute the upper bound for the linear iteration when the object |
| conflicts are represented as a sparse vector. In particular this |
| will make sure we prefer O(1) bitvector testing. */ |
| int num_conflicts_in_vec1 = 0, num_conflicts_in_vec2 = 0; |
| for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a1); ++word) |
| if (OBJECT_CONFLICT_VEC_P (ALLOCNO_OBJECT (a1, word))) |
| num_conflicts_in_vec1 += OBJECT_NUM_CONFLICTS (ALLOCNO_OBJECT (a1, word)); |
| for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a2); ++word) |
| if (OBJECT_CONFLICT_VEC_P (ALLOCNO_OBJECT (a2, word))) |
| num_conflicts_in_vec2 += OBJECT_NUM_CONFLICTS (ALLOCNO_OBJECT (a2, word)); |
| if (num_conflicts_in_vec2 < num_conflicts_in_vec1) |
| std::swap (a1, a2); |
| |
| for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a1); word++) |
| { |
| ira_object_t obj = ALLOCNO_OBJECT (a1, word); |
| /* Take preferences of conflicting allocnos into account. */ |
| if (object_conflicts_with_allocno_p (obj, a2)) |
| return true; |
| } |
| return false; |
| } |
| |
| /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected |
| by copies to ALLOCNO to increase chances to remove some copies as |
| the result of subsequent assignment. Update conflict costs. |
| Record cost updates if RECORD_P is true. */ |
| static void |
| update_costs_from_allocno (ira_allocno_t allocno, int hard_regno, |
| int divisor, bool decr_p, bool record_p) |
| { |
| int cost, update_cost, update_conflict_cost; |
| machine_mode mode; |
| enum reg_class rclass, aclass; |
| ira_allocno_t another_allocno, start = allocno, from = NULL; |
| ira_copy_t cp, next_cp; |
| |
| rclass = REGNO_REG_CLASS (hard_regno); |
| do |
| { |
| mode = ALLOCNO_MODE (allocno); |
| ira_init_register_move_cost_if_necessary (mode); |
| for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) |
| { |
| if (cp->first == allocno) |
| { |
| next_cp = cp->next_first_allocno_copy; |
| another_allocno = cp->second; |
| } |
| else if (cp->second == allocno) |
| { |
| next_cp = cp->next_second_allocno_copy; |
| another_allocno = cp->first; |
| } |
| else |
| gcc_unreachable (); |
| |
| if (another_allocno == from |
| || (ALLOCNO_COLOR_DATA (another_allocno) != NULL |
| && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno |
| != ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno))) |
| continue; |
| |
| aclass = ALLOCNO_CLASS (another_allocno); |
| if (! TEST_HARD_REG_BIT (reg_class_contents[aclass], |
| hard_regno) |
| || ALLOCNO_ASSIGNED_P (another_allocno)) |
| continue; |
| |
| /* If we have different modes use the smallest one. It is |
| a sub-register move. It is hard to predict what LRA |
| will reload (the pseudo or its sub-register) but LRA |
| will try to minimize the data movement. Also for some |
| register classes bigger modes might be invalid, |
| e.g. DImode for AREG on x86. For such cases the |
| register move cost will be maximal. */ |
| mode = narrower_subreg_mode (ALLOCNO_MODE (cp->first), |
| ALLOCNO_MODE (cp->second)); |
| |
| ira_init_register_move_cost_if_necessary (mode); |
| |
| cost = (cp->second == allocno |
| ? ira_register_move_cost[mode][rclass][aclass] |
| : ira_register_move_cost[mode][aclass][rclass]); |
| if (decr_p) |
| cost = -cost; |
| |
| update_cost = cp->freq * cost / divisor; |
| update_conflict_cost = update_cost; |
| |
| if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, |
| " a%dr%d (hr%d): update cost by %d, conflict cost by %d\n", |
| ALLOCNO_NUM (another_allocno), ALLOCNO_REGNO (another_allocno), |
| hard_regno, update_cost, update_conflict_cost); |
| if (update_cost == 0) |
| continue; |
| |
| if (! update_allocno_cost (another_allocno, hard_regno, |
| update_cost, update_conflict_cost)) |
| continue; |
| queue_update_cost (another_allocno, start, allocno, |
| divisor * COST_HOP_DIVISOR); |
| if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL) |
| ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records |
| = get_update_cost_record (hard_regno, divisor, |
| ALLOCNO_COLOR_DATA (another_allocno) |
| ->update_cost_records); |
| } |
| } |
| while (get_next_update_cost (&allocno, &start, &from, &divisor)); |
| } |
| |
| /* Decrease preferred ALLOCNO hard register costs and costs of |
| allocnos connected to ALLOCNO through copy. */ |
| static void |
| update_costs_from_prefs (ira_allocno_t allocno) |
| { |
| ira_pref_t pref; |
| |
| start_update_cost (); |
| for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref) |
| { |
| if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, " Start updating from pref of hr%d for a%dr%d:\n", |
| pref->hard_regno, ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno)); |
| update_costs_from_allocno (allocno, pref->hard_regno, |
| COST_HOP_DIVISOR, true, true); |
| } |
| } |
| |
| /* Update (decrease if DECR_P) the cost of allocnos connected to |
| ALLOCNO through copies to increase chances to remove some copies as |
| the result of subsequent assignment. ALLOCNO was just assigned to |
| a hard register. Record cost updates if RECORD_P is true. */ |
| static void |
| update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p) |
| { |
| int hard_regno; |
| |
| hard_regno = ALLOCNO_HARD_REGNO (allocno); |
| ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS); |
| start_update_cost (); |
| if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, " Start updating from a%dr%d by copies:\n", |
| ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno)); |
| update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p); |
| } |
| |
| /* Update conflict_allocno_hard_prefs of allocnos conflicting with |
| ALLOCNO. */ |
| static void |
| update_conflict_allocno_hard_prefs (ira_allocno_t allocno) |
| { |
| int l, nr = ALLOCNO_NUM_OBJECTS (allocno); |
| |
| for (l = 0; l < nr; l++) |
| { |
| ira_object_t conflict_obj, obj = ALLOCNO_OBJECT (allocno, l); |
| ira_object_conflict_iterator oci; |
| |
| FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) |
| { |
| ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); |
| allocno_color_data_t conflict_data = ALLOCNO_COLOR_DATA (conflict_a); |
| ira_pref_t pref; |
| |
| if (!(hard_reg_set_intersect_p |
| (ALLOCNO_COLOR_DATA (allocno)->profitable_hard_regs, |
| conflict_data->profitable_hard_regs))) |
| continue; |
| for (pref = ALLOCNO_PREFS (allocno); |
| pref != NULL; |
| pref = pref->next_pref) |
| conflict_data->conflict_allocno_hard_prefs += pref->freq; |
| } |
| } |
| } |
| |
| /* Restore costs of allocnos connected to ALLOCNO by copies as it was |
| before updating costs of these allocnos from given allocno. This |
| is a wise thing to do as if given allocno did not get an expected |
| hard reg, using smaller cost of the hard reg for allocnos connected |
| by copies to given allocno becomes actually misleading. Free all |
| update cost records for ALLOCNO as we don't need them anymore. */ |
| static void |
| restore_costs_from_copies (ira_allocno_t allocno) |
| { |
| struct update_cost_record *records, *curr; |
| |
| if (ALLOCNO_COLOR_DATA (allocno) == NULL) |
| return; |
| records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records; |
| start_update_cost (); |
| if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, " Start restoring from a%dr%d:\n", |
| ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno)); |
| for (curr = records; curr != NULL; curr = curr->next) |
| update_costs_from_allocno (allocno, curr->hard_regno, |
| curr->divisor, true, false); |
| free_update_cost_record_list (records); |
| ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL; |
| } |
| |
| /* This function updates COSTS (decrease if DECR_P) for hard_registers |
| of ACLASS by conflict costs of the unassigned allocnos |
| connected by copies with allocnos in update_cost_queue. This |
| update increases chances to remove some copies. */ |
| static void |
| update_conflict_hard_regno_costs (int *costs, enum reg_class aclass, |
| bool decr_p) |
| { |
| int i, cost, class_size, freq, mult, div, divisor; |
| int index, hard_regno; |
| int *conflict_costs; |
| bool cont_p; |
| enum reg_class another_aclass; |
| ira_allocno_t allocno, another_allocno, start, from; |
| ira_copy_t cp, next_cp; |
| |
| while (get_next_update_cost (&allocno, &start, &from, &divisor)) |
| for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) |
| { |
| if (cp->first == allocno) |
| { |
| next_cp = cp->next_first_allocno_copy; |
| another_allocno = cp->second; |
| } |
| else if (cp->second == allocno) |
| { |
| next_cp = cp->next_second_allocno_copy; |
| another_allocno = cp->first; |
| } |
| else |
| gcc_unreachable (); |
| |
| another_aclass = ALLOCNO_CLASS (another_allocno); |
| if (another_allocno == from |
| || ALLOCNO_ASSIGNED_P (another_allocno) |
| || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p |
| || ! ira_reg_classes_intersect_p[aclass][another_aclass]) |
| continue; |
| if (allocnos_conflict_p (another_allocno, start)) |
| continue; |
| |
| class_size = ira_class_hard_regs_num[another_aclass]; |
| ira_allocate_and_copy_costs |
| (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), |
| another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); |
| conflict_costs |
| = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno); |
| if (conflict_costs == NULL) |
| cont_p = true; |
| else |
| { |
| mult = cp->freq; |
| freq = ALLOCNO_FREQ (another_allocno); |
| if (freq == 0) |
| freq = 1; |
| div = freq * divisor; |
| cont_p = false; |
| for (i = class_size - 1; i >= 0; i--) |
| { |
| hard_regno = ira_class_hard_regs[another_aclass][i]; |
| ira_assert (hard_regno >= 0); |
| index = ira_class_hard_reg_index[aclass][hard_regno]; |
| if (index < 0) |
| continue; |
| cost = (int) (((int64_t) conflict_costs [i] * mult) / div); |
| if (cost == 0) |
| continue; |
| cont_p = true; |
| if (decr_p) |
| cost = -cost; |
| costs[index] += cost; |
| } |
| } |
| /* Probably 5 hops will be enough. */ |
| if (cont_p |
| && divisor <= (COST_HOP_DIVISOR |
| * COST_HOP_DIVISOR |
| * COST_HOP_DIVISOR |
| * COST_HOP_DIVISOR)) |
| queue_update_cost (another_allocno, start, from, divisor * COST_HOP_DIVISOR); |
| } |
| } |
| |
| /* Set up conflicting (through CONFLICT_REGS) for each object of |
| allocno A and the start allocno profitable regs (through |
| START_PROFITABLE_REGS). Remember that the start profitable regs |
| exclude hard regs which cannot hold value of mode of allocno A. |
| This covers mostly cases when multi-register value should be |
| aligned. */ |
| static inline void |
| get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p, |
| HARD_REG_SET *conflict_regs, |
| HARD_REG_SET *start_profitable_regs) |
| { |
| int i, nwords; |
| ira_object_t obj; |
| |
| nwords = ALLOCNO_NUM_OBJECTS (a); |
| for (i = 0; i < nwords; i++) |
| { |
| obj = ALLOCNO_OBJECT (a, i); |
| conflict_regs[i] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj); |
| } |
| if (retry_p) |
| *start_profitable_regs |
| = (reg_class_contents[ALLOCNO_CLASS (a)] |
| &~ (ira_prohibited_class_mode_regs |
| [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)])); |
| else |
| *start_profitable_regs = ALLOCNO_COLOR_DATA (a)->profitable_hard_regs; |
| } |
| |
| /* Return true if HARD_REGNO is ok for assigning to allocno A with |
| PROFITABLE_REGS and whose objects have CONFLICT_REGS. */ |
| static inline bool |
| check_hard_reg_p (ira_allocno_t a, int hard_regno, |
| HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs) |
| { |
| int j, nwords, nregs; |
| enum reg_class aclass; |
| machine_mode mode; |
| |
| aclass = ALLOCNO_CLASS (a); |
| mode = ALLOCNO_MODE (a); |
| if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode], |
| hard_regno)) |
| return false; |
| /* Checking only profitable hard regs. */ |
| if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno)) |
| return false; |
| nregs = hard_regno_nregs (hard_regno, mode); |
| nwords = ALLOCNO_NUM_OBJECTS (a); |
| for (j = 0; j < nregs; j++) |
| { |
| int k; |
| int set_to_test_start = 0, set_to_test_end = nwords; |
| |
| if (nregs == nwords) |
| { |
| if (REG_WORDS_BIG_ENDIAN) |
| set_to_test_start = nwords - j - 1; |
| else |
| set_to_test_start = j; |
| set_to_test_end = set_to_test_start + 1; |
| } |
| for (k = set_to_test_start; k < set_to_test_end; k++) |
| if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j)) |
| break; |
| if (k != set_to_test_end) |
| break; |
| } |
| return j == nregs; |
| } |
| |
| /* Return number of registers needed to be saved and restored at |
| function prologue/epilogue if we allocate HARD_REGNO to hold value |
| of MODE. */ |
| static int |
| calculate_saved_nregs (int hard_regno, machine_mode mode) |
| { |
| int i; |
| int nregs = 0; |
| |
| ira_assert (hard_regno >= 0); |
| for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--) |
| if (!allocated_hardreg_p[hard_regno + i] |
| && !crtl->abi->clobbers_full_reg_p (hard_regno + i) |
| && !LOCAL_REGNO (hard_regno + i)) |
| nregs++; |
| return nregs; |
| } |
| |
| /* Allocnos A1 and A2 are known to conflict. Check whether, in some loop L |
| that is either the current loop or a nested subloop, the conflict is of |
| the following form: |
| |
| - One allocno (X) is a cap allocno for some non-cap allocno X2. |
| |
| - X2 belongs to some loop L2. |
| |
| - The other allocno (Y) is a non-cap allocno. |
| |
| - Y is an ancestor of some allocno Y2 in L2. (Note that such a Y2 |
| must exist, given that X and Y conflict.) |
| |
| - Y2 is not referenced in L2 (that is, ALLOCNO_NREFS (Y2) == 0). |
| |
| - Y can use a different allocation from Y2. |
| |
| In this case, Y's register is live across L2 but is not used within it, |
| whereas X's register is used only within L2. The conflict is therefore |
| only "soft", in that it can easily be avoided by spilling Y2 inside L2 |
| without affecting any insn references. |
| |
| If the conflict does have this form, return the Y2 that would need to be |
| spilled in order to allow X and Y (and thus A1 and A2) to use the same |
| register. Return null otherwise. Returning null is conservatively correct; |
| any nonnnull return value is an optimization. */ |
| ira_allocno_t |
| ira_soft_conflict (ira_allocno_t a1, ira_allocno_t a2) |
| { |
| /* Search for the loop L and its associated allocnos X and Y. */ |
| int search_depth = 0; |
| while (ALLOCNO_CAP_MEMBER (a1) && ALLOCNO_CAP_MEMBER (a2)) |
| { |
| a1 = ALLOCNO_CAP_MEMBER (a1); |
| a2 = ALLOCNO_CAP_MEMBER (a2); |
| if (search_depth++ > max_soft_conflict_loop_depth) |
| return nullptr; |
| } |
| /* This must be true if A1 and A2 conflict. */ |
| ira_assert (ALLOCNO_LOOP_TREE_NODE (a1) == ALLOCNO_LOOP_TREE_NODE (a2)); |
| |
| /* Make A1 the cap allocno (X in the comment above) and A2 the |
| non-cap allocno (Y in the comment above). */ |
| if (ALLOCNO_CAP_MEMBER (a2)) |
| std::swap (a1, a2); |
| if (!ALLOCNO_CAP_MEMBER (a1)) |
| return nullptr; |
| |
| /* Search for the real allocno that A1 caps (X2 in the comment above). */ |
| do |
| { |
| a1 = ALLOCNO_CAP_MEMBER (a1); |
| if (search_depth++ > max_soft_conflict_loop_depth) |
| return nullptr; |
| } |
| while (ALLOCNO_CAP_MEMBER (a1)); |
| |
| /* Find the associated allocno for A2 (Y2 in the comment above). */ |
| auto node = ALLOCNO_LOOP_TREE_NODE (a1); |
| auto local_a2 = node->regno_allocno_map[ALLOCNO_REGNO (a2)]; |
| |
| /* Find the parent of LOCAL_A2/Y2. LOCAL_A2 must be a descendant of A2 |
| for the conflict query to make sense, so this parent lookup must succeed. |
| |
| If the parent allocno has no references, it is usually cheaper to |
| spill at that loop level instead. Keep searching until we find |
| a parent allocno that does have references (but don't look past |
| the starting allocno). */ |
| ira_allocno_t local_parent_a2; |
| for (;;) |
| { |
| local_parent_a2 = ira_parent_allocno (local_a2); |
| if (local_parent_a2 == a2 || ALLOCNO_NREFS (local_parent_a2) != 0) |
| break; |
| local_a2 = local_parent_a2; |
| } |
| if (CHECKING_P) |
| { |
| /* Sanity check to make sure that the conflict we've been given |
| makes sense. */ |
| auto test_a2 = local_parent_a2; |
| while (test_a2 != a2) |
| { |
| test_a2 = ira_parent_allocno (test_a2); |
| ira_assert (test_a2); |
| } |
| } |
| if (local_a2 |
| && ALLOCNO_NREFS (local_a2) == 0 |
| && ira_subloop_allocnos_can_differ_p (local_parent_a2)) |
| return local_a2; |
| return nullptr; |
| } |
| |
| /* The caller has decided to allocate HREGNO to A and has proved that |
| this is safe. However, the allocation might require the kind of |
| spilling described in the comment above ira_soft_conflict. |
| The caller has recorded that: |
| |
| - The allocnos in ALLOCNOS_TO_SPILL are the ones that would need |
| to be spilled to satisfy soft conflicts for at least one allocation |
| (not necessarily HREGNO). |
| |
| - The soft conflicts apply only to A allocations that overlap |
| SOFT_CONFLICT_REGS. |
| |
| If allocating HREGNO is subject to any soft conflicts, record the |
| subloop allocnos that need to be spilled. */ |
| static void |
| spill_soft_conflicts (ira_allocno_t a, bitmap allocnos_to_spill, |
| HARD_REG_SET soft_conflict_regs, int hregno) |
| { |
| auto nregs = hard_regno_nregs (hregno, ALLOCNO_MODE (a)); |
| bitmap_iterator bi; |
| unsigned int i; |
| EXECUTE_IF_SET_IN_BITMAP (allocnos_to_spill, 0, i, bi) |
| { |
| /* SPILL_A needs to be spilled for at least one allocation |
| (not necessarily this one). */ |
| auto spill_a = ira_allocnos[i]; |
| |
| /* Find the corresponding allocno for this loop. */ |
| auto conflict_a = spill_a; |
| do |
| { |
| conflict_a = ira_parent_or_cap_allocno (conflict_a); |
| ira_assert (conflict_a); |
| } |
| while (ALLOCNO_LOOP_TREE_NODE (conflict_a)->level |
| > ALLOCNO_LOOP_TREE_NODE (a)->level); |
| |
| ira_assert (ALLOCNO_LOOP_TREE_NODE (conflict_a) |
| == ALLOCNO_LOOP_TREE_NODE (a)); |
| |
| if (conflict_a == a) |
| { |
| /* SPILL_A is a descendant of A. We don't know (and don't need |
| to know) which cap allocnos have a soft conflict with A. |
| All we need to do is test whether the soft conflict applies |
| to the chosen allocation. */ |
| if (ira_hard_reg_set_intersection_p (hregno, ALLOCNO_MODE (a), |
| soft_conflict_regs)) |
| ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (spill_a) = true; |
| } |
| else |
| { |
| /* SPILL_A is a descendant of CONFLICT_A, which has a soft conflict |
| with A. Test whether the soft conflict applies to the current |
| allocation. */ |
| ira_assert (ira_soft_conflict (a, conflict_a) == spill_a); |
| auto conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a); |
| ira_assert (conflict_hregno >= 0); |
| auto conflict_nregs = hard_regno_nregs (conflict_hregno, |
| ALLOCNO_MODE (conflict_a)); |
| if (hregno + nregs > conflict_hregno |
| && conflict_hregno + conflict_nregs > hregno) |
| ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (spill_a) = true; |
| } |
| } |
| } |
| |
| /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means |
| that the function called from function |
| `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In |
| this case some allocno data are not defined or updated and we |
| should not touch these data. The function returns true if we |
| managed to assign a hard register to the allocno. |
| |
| To assign a hard register, first of all we calculate all conflict |
| hard registers which can come from conflicting allocnos with |
| already assigned hard registers. After that we find first free |
| hard register with the minimal cost. During hard register cost |
| calculation we take conflict hard register costs into account to |
| give a chance for conflicting allocnos to get a better hard |
| register in the future. |
| |
| If the best hard register cost is bigger than cost of memory usage |
| for the allocno, we don't assign a hard register to given allocno |
| at all. |
| |
| If we assign a hard register to the allocno, we update costs of the |
| hard register for allocnos connected by copies to improve a chance |
| to coalesce insns represented by the copies when we assign hard |
| registers to the allocnos connected by the copies. */ |
| static bool |
| assign_hard_reg (ira_allocno_t a, bool retry_p) |
| { |
| HARD_REG_SET conflicting_regs[2], profitable_hard_regs; |
| int i, j, hard_regno, best_hard_regno, class_size; |
| int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word; |
| int *a_costs; |
| enum reg_class aclass; |
| machine_mode mode; |
| static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER]; |
| int saved_nregs; |
| enum reg_class rclass; |
| int add_cost; |
| #ifdef STACK_REGS |
| bool no_stack_reg_p; |
| #endif |
| auto_bitmap allocnos_to_spill; |
| HARD_REG_SET soft_conflict_regs = {}; |
| |
| ira_assert (! ALLOCNO_ASSIGNED_P (a)); |
| get_conflict_and_start_profitable_regs (a, retry_p, |
| conflicting_regs, |
| &profitable_hard_regs); |
| aclass = ALLOCNO_CLASS (a); |
| class_size = ira_class_hard_regs_num[aclass]; |
| best_hard_regno = -1; |
| memset (full_costs, 0, sizeof (int) * class_size); |
| mem_cost = 0; |
| memset (costs, 0, sizeof (int) * class_size); |
| memset (full_costs, 0, sizeof (int) * class_size); |
| #ifdef STACK_REGS |
| no_stack_reg_p = false; |
| #endif |
| if (! retry_p) |
| start_update_cost (); |
| mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a); |
| |
| ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), |
| aclass, ALLOCNO_HARD_REG_COSTS (a)); |
| a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a); |
| #ifdef STACK_REGS |
| no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a); |
| #endif |
| cost = ALLOCNO_UPDATED_CLASS_COST (a); |
| for (i = 0; i < class_size; i++) |
| if (a_costs != NULL) |
| { |
| costs[i] += a_costs[i]; |
| full_costs[i] += a_costs[i]; |
| } |
| else |
| { |
| costs[i] += cost; |
| full_costs[i] += cost; |
| } |
| nwords = ALLOCNO_NUM_OBJECTS (a); |
| curr_allocno_process++; |
| for (word = 0; word < nwords; word++) |
| { |
| ira_object_t conflict_obj; |
| ira_object_t obj = ALLOCNO_OBJECT (a, word); |
| ira_object_conflict_iterator oci; |
| |
| /* Take preferences of conflicting allocnos into account. */ |
| FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) |
| { |
| ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); |
| enum reg_class conflict_aclass; |
| allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a); |
| |
| /* Reload can give another class so we need to check all |
| allocnos. */ |
| if (!retry_p |
| && ((!ALLOCNO_ASSIGNED_P (conflict_a) |
| || ALLOCNO_HARD_REGNO (conflict_a) < 0) |
| && !(hard_reg_set_intersect_p |
| (profitable_hard_regs, |
| ALLOCNO_COLOR_DATA |
| (conflict_a)->profitable_hard_regs)))) |
| { |
| /* All conflict allocnos are in consideration bitmap |
| when retry_p is false. It might change in future and |
| if it happens the assert will be broken. It means |
| the code should be modified for the new |
| assumptions. */ |
| ira_assert (bitmap_bit_p (consideration_allocno_bitmap, |
| ALLOCNO_NUM (conflict_a))); |
| continue; |
| } |
| conflict_aclass = ALLOCNO_CLASS (conflict_a); |
| ira_assert (ira_reg_classes_intersect_p |
| [aclass][conflict_aclass]); |
| if (ALLOCNO_ASSIGNED_P (conflict_a)) |
| { |
| hard_regno = ALLOCNO_HARD_REGNO (conflict_a); |
| if (hard_regno >= 0 |
| && (ira_hard_reg_set_intersection_p |
| (hard_regno, ALLOCNO_MODE (conflict_a), |
| reg_class_contents[aclass]))) |
| { |
| int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a); |
| int conflict_nregs; |
| |
| mode = ALLOCNO_MODE (conflict_a); |
| conflict_nregs = hard_regno_nregs (hard_regno, mode); |
| auto spill_a = (retry_p |
| ? nullptr |
| : ira_soft_conflict (a, conflict_a)); |
| if (spill_a) |
| { |
| if (bitmap_set_bit (allocnos_to_spill, |
| ALLOCNO_NUM (spill_a))) |
| { |
| ira_loop_border_costs border_costs (spill_a); |
| auto cost = border_costs.spill_inside_loop_cost (); |
| auto note_conflict = [&](int r) |
| { |
| SET_HARD_REG_BIT (soft_conflict_regs, r); |
| auto hri = ira_class_hard_reg_index[aclass][r]; |
| if (hri >= 0) |
| { |
| costs[hri] += cost; |
| full_costs[hri] += cost; |
| } |
| }; |
| for (int r = hard_regno; |
| r >= 0 && (int) end_hard_regno (mode, r) > hard_regno; |
| r--) |
| note_conflict (r); |
| for (int r = hard_regno + 1; |
| r < hard_regno + conflict_nregs; |
| r++) |
| note_conflict (r); |
| } |
| } |
| else |
| { |
| if (conflict_nregs == n_objects && conflict_nregs > 1) |
| { |
| int num = OBJECT_SUBWORD (conflict_obj); |
| |
| if (REG_WORDS_BIG_ENDIAN) |
| SET_HARD_REG_BIT (conflicting_regs[word], |
| hard_regno + n_objects - num - 1); |
| else |
| SET_HARD_REG_BIT (conflicting_regs[word], |
| hard_regno + num); |
| } |
| else |
| conflicting_regs[word] |
| |= ira_reg_mode_hard_regset[hard_regno][mode]; |
| if (hard_reg_set_subset_p (profitable_hard_regs, |
| conflicting_regs[word])) |
| goto fail; |
| } |
| } |
| } |
| else if (! retry_p |
| && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p |
| /* Don't process the conflict allocno twice. */ |
| && (ALLOCNO_COLOR_DATA (conflict_a)->last_process |
| != curr_allocno_process)) |
| { |
| int k, *conflict_costs; |
| |
| ALLOCNO_COLOR_DATA (conflict_a)->last_process |
| = curr_allocno_process; |
| ira_allocate_and_copy_costs |
| (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a), |
| conflict_aclass, |
| ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a)); |
| conflict_costs |
| = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a); |
| if (conflict_costs != NULL) |
| for (j = class_size - 1; j >= 0; j--) |
| { |
| hard_regno = ira_class_hard_regs[aclass][j]; |
| ira_assert (hard_regno >= 0); |
| k = ira_class_hard_reg_index[conflict_aclass][hard_regno]; |
| if (k < 0 |
| /* If HARD_REGNO is not available for CONFLICT_A, |
| the conflict would be ignored, since HARD_REGNO |
| will never be assigned to CONFLICT_A. */ |
| || !TEST_HARD_REG_BIT (data->profitable_hard_regs, |
| hard_regno)) |
| continue; |
| full_costs[j] -= conflict_costs[k]; |
| } |
| queue_update_cost (conflict_a, conflict_a, NULL, COST_HOP_DIVISOR); |
| } |
| } |
| } |
| if (! retry_p) |
| /* Take into account preferences of allocnos connected by copies to |
| the conflict allocnos. */ |
| update_conflict_hard_regno_costs (full_costs, aclass, true); |
| |
| /* Take preferences of allocnos connected by copies into |
| account. */ |
| if (! retry_p) |
| { |
| start_update_cost (); |
| queue_update_cost (a, a, NULL, COST_HOP_DIVISOR); |
| update_conflict_hard_regno_costs (full_costs, aclass, false); |
| } |
| min_cost = min_full_cost = INT_MAX; |
| /* We don't care about giving callee saved registers to allocnos no |
| living through calls because call clobbered registers are |
| allocated first (it is usual practice to put them first in |
| REG_ALLOC_ORDER). */ |
| mode = ALLOCNO_MODE (a); |
| for (i = 0; i < class_size; i++) |
| { |
| hard_regno = ira_class_hard_regs[aclass][i]; |
| #ifdef STACK_REGS |
| if (no_stack_reg_p |
| && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG) |
| continue; |
| #endif |
| if (! check_hard_reg_p (a, hard_regno, |
| conflicting_regs, profitable_hard_regs)) |
| continue; |
| cost = costs[i]; |
| full_cost = full_costs[i]; |
| if (!HONOR_REG_ALLOC_ORDER) |
| { |
| if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0) |
| /* We need to save/restore the hard register in |
| epilogue/prologue. Therefore we increase the cost. */ |
| { |
| rclass = REGNO_REG_CLASS (hard_regno); |
| add_cost = ((ira_memory_move_cost[mode][rclass][0] |
| + ira_memory_move_cost[mode][rclass][1]) |
| * saved_nregs / hard_regno_nregs (hard_regno, |
| mode) - 1); |
| cost += add_cost; |
| full_cost += add_cost; |
| } |
| } |
| if (min_cost > cost) |
| min_cost = cost; |
| if (min_full_cost > full_cost) |
| { |
| min_full_cost = full_cost; |
| best_hard_regno = hard_regno; |
| ira_assert (hard_regno >= 0); |
| } |
| if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, "(%d=%d,%d) ", hard_regno, cost, full_cost); |
| } |
| if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, "\n"); |
| if (min_full_cost > mem_cost |
| /* Do not spill static chain pointer pseudo when non-local goto |
| is used. */ |
| && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a))) |
| { |
| if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ", |
| mem_cost, min_full_cost); |
| best_hard_regno = -1; |
| } |
| fail: |
| if (best_hard_regno >= 0) |
| { |
| for (i = hard_regno_nregs (best_hard_regno, mode) - 1; i >= 0; i--) |
| allocated_hardreg_p[best_hard_regno + i] = true; |
| spill_soft_conflicts (a, allocnos_to_spill, soft_conflict_regs, |
| best_hard_regno); |
| } |
| if (! retry_p) |
| restore_costs_from_copies (a); |
| ALLOCNO_HARD_REGNO (a) = best_hard_regno; |
| ALLOCNO_ASSIGNED_P (a) = true; |
| if (best_hard_regno >= 0) |
| update_costs_from_copies (a, true, ! retry_p); |
| ira_assert (ALLOCNO_CLASS (a) == aclass); |
| /* We don't need updated costs anymore. */ |
| ira_free_allocno_updated_costs (a); |
| return best_hard_regno >= 0; |
| } |
| |
| |
| |
| /* An array used to sort copies. */ |
| static ira_copy_t *sorted_copies; |
| |
| /* If allocno A is a cap, return non-cap allocno from which A is |
| created. Otherwise, return A. */ |
| static ira_allocno_t |
| get_cap_member (ira_allocno_t a) |
| { |
| ira_allocno_t member; |
| |
| while ((member = ALLOCNO_CAP_MEMBER (a)) != NULL) |
| a = member; |
| return a; |
| } |
| |
| /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is |
| used to find a conflict for new allocnos or allocnos with the |
| different allocno classes. */ |
| static bool |
| allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2) |
| { |
| rtx reg1, reg2; |
| int i, j; |
| int n1 = ALLOCNO_NUM_OBJECTS (a1); |
| int n2 = ALLOCNO_NUM_OBJECTS (a2); |
| |
| if (a1 == a2) |
| return false; |
| reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)]; |
| reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)]; |
| if (reg1 != NULL && reg2 != NULL |
| && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2)) |
| return false; |
| |
| /* We don't keep live ranges for caps because they can be quite big. |
| Use ranges of non-cap allocno from which caps are created. */ |
| a1 = get_cap_member (a1); |
| a2 = get_cap_member (a2); |
| for (i = 0; i < n1; i++) |
| { |
| ira_object_t c1 = ALLOCNO_OBJECT (a1, i); |
| |
| for (j = 0; j < n2; j++) |
| { |
| ira_object_t c2 = ALLOCNO_OBJECT (a2, j); |
| |
| if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1), |
| OBJECT_LIVE_RANGES (c2))) |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /* The function is used to sort copies according to their execution |
| frequencies. */ |
| static int |
| copy_freq_compare_func (const void *v1p, const void *v2p) |
| { |
| ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p; |
| int pri1, pri2; |
| |
| pri1 = cp1->freq; |
| pri2 = cp2->freq; |
| if (pri2 - pri1) |
| return pri2 - pri1; |
| |
| /* If frequencies are equal, sort by copies, so that the results of |
| qsort leave nothing to chance. */ |
| return cp1->num - cp2->num; |
| } |
| |
| |
| |
| /* Return true if any allocno from thread of A1 conflicts with any |
| allocno from thread A2. */ |
| static bool |
| allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2) |
| { |
| ira_allocno_t a, conflict_a; |
| |
| for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;; |
| a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno) |
| { |
| for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;; |
| conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno) |
| { |
| if (allocnos_conflict_by_live_ranges_p (a, conflict_a)) |
| return true; |
| if (conflict_a == a1) |
| break; |
| } |
| if (a == a2) |
| break; |
| } |
| return false; |
| } |
| |
| /* Merge two threads given correspondingly by their first allocnos T1 |
| and T2 (more accurately merging T2 into T1). */ |
| static void |
| merge_threads (ira_allocno_t t1, ira_allocno_t t2) |
| { |
| ira_allocno_t a, next, last; |
| |
| gcc_assert (t1 != t2 |
| && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1 |
| && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2); |
| for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;; |
| a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno) |
| { |
| ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1; |
| if (a == t2) |
| break; |
| last = a; |
| } |
| next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno; |
| ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2; |
| ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next; |
| ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq; |
| } |
| |
| /* Create threads by processing CP_NUM copies from sorted copies. We |
| process the most expensive copies first. */ |
| static void |
| form_threads_from_copies (int cp_num) |
| { |
| ira_allocno_t a, thread1, thread2; |
| ira_copy_t cp; |
| |
| qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func); |
| /* Form threads processing copies, most frequently executed |
| first. */ |
| for (int i = 0; i < cp_num; i++) |
| { |
| cp = sorted_copies[i]; |
| thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno; |
| thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno; |
| if (thread1 == thread2) |
| continue; |
| if (! allocno_thread_conflict_p (thread1, thread2)) |
| { |
| if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| fprintf |
| (ira_dump_file, |
| " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n", |
| cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first), |
| ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), |
| cp->freq); |
| merge_threads (thread1, thread2); |
| if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| { |
| thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno; |
| fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)", |
| ALLOCNO_COLOR_DATA (thread1)->thread_freq, |
| ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1), |
| ALLOCNO_FREQ (thread1)); |
| for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno; |
| a != thread1; |
| a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno) |
| fprintf (ira_dump_file, " a%dr%d(%d)", |
| ALLOCNO_NUM (a), ALLOCNO_REGNO (a), |
| ALLOCNO_FREQ (a)); |
| fprintf (ira_dump_file, "\n"); |
| } |
| } |
| } |
| } |
| |
| /* Create threads by processing copies of all alocnos from BUCKET. We |
| process the most expensive copies first. */ |
| static void |
| form_threads_from_bucket (ira_allocno_t bucket) |
| { |
| ira_allocno_t a; |
| ira_copy_t cp, next_cp; |
| int cp_num = 0; |
| |
| for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno) |
| { |
| for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) |
| { |
| if (cp->first == a) |
| { |
| next_cp = cp->next_first_allocno_copy; |
| sorted_copies[cp_num++] = cp; |
| } |
| else if (cp->second == a) |
| next_cp = cp->next_second_allocno_copy; |
| else |
| gcc_unreachable (); |
| } |
| } |
| form_threads_from_copies (cp_num); |
| } |
| |
| /* Create threads by processing copies of colorable allocno A. We |
| process most expensive copies first. */ |
| static void |
| form_threads_from_colorable_allocno (ira_allocno_t a) |
| { |
| ira_allocno_t another_a; |
| ira_copy_t cp, next_cp; |
| int cp_num = 0; |
| |
| if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, " Forming thread from allocno a%dr%d:\n", |
| ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); |
| for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) |
| { |
| if (cp->first == a) |
| { |
| next_cp = cp->next_first_allocno_copy; |
| another_a = cp->second; |
| } |
| else if (cp->second == a) |
| { |
| next_cp = cp->next_second_allocno_copy; |
| another_a = cp->first; |
| } |
| else |
| gcc_unreachable (); |
| if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p |
| && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p) |
| || ALLOCNO_COLOR_DATA (another_a)->colorable_p) |
| sorted_copies[cp_num++] = cp; |
| } |
| form_threads_from_copies (cp_num); |
| } |
| |
| /* Form initial threads which contain only one allocno. */ |
| static void |
| init_allocno_threads (void) |
| { |
| ira_allocno_t a; |
| unsigned int j; |
| bitmap_iterator bi; |
| ira_pref_t pref; |
| |
| EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) |
| { |
| a = ira_allocnos[j]; |
| /* Set up initial thread data: */ |
| ALLOCNO_COLOR_DATA (a)->first_thread_allocno |
| = ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a; |
| ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a); |
| ALLOCNO_COLOR_DATA (a)->hard_reg_prefs = 0; |
| for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref) |
| ALLOCNO_COLOR_DATA (a)->hard_reg_prefs += pref->freq; |
| } |
| } |
| |
| |
| |
| /* This page contains the allocator based on the Chaitin-Briggs algorithm. */ |
| |
| /* Bucket of allocnos that can colored currently without spilling. */ |
| static ira_allocno_t colorable_allocno_bucket; |
| |
| /* Bucket of allocnos that might be not colored currently without |
| spilling. */ |
| static ira_allocno_t uncolorable_allocno_bucket; |
| |
| /* The current number of allocnos in the uncolorable_bucket. */ |
| static int uncolorable_allocnos_num; |
| |
| /* Return the current spill priority of allocno A. The less the |
| number, the more preferable the allocno for spilling. */ |
| static inline int |
| allocno_spill_priority (ira_allocno_t a) |
| { |
| allocno_color_data_t data = ALLOCNO_COLOR_DATA (a); |
| |
| return (data->temp |
| / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) |
| * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)] |
| + 1)); |
| } |
| |
| /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket |
| before the call. */ |
| static void |
| add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr) |
| { |
| ira_allocno_t first_a; |
| allocno_color_data_t data; |
| |
| if (bucket_ptr == &uncolorable_allocno_bucket |
| && ALLOCNO_CLASS (a) != NO_REGS) |
| { |
| uncolorable_allocnos_num++; |
| ira_assert (uncolorable_allocnos_num > 0); |
| } |
| first_a = *bucket_ptr; |
| data = ALLOCNO_COLOR_DATA (a); |
| data->next_bucket_allocno = first_a; |
| data->prev_bucket_allocno = NULL; |
| if (first_a != NULL) |
| ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a; |
| *bucket_ptr = a; |
| } |
| |
| /* Compare two allocnos to define which allocno should be pushed first |
| into the coloring stack. If the return is a negative number, the |
| allocno given by the first parameter will be pushed first. In this |
| case such allocno has less priority than the second one and the |
| hard register will be assigned to it after assignment to the second |
| one. As the result of such assignment order, the second allocno |
| has a better chance to get the best hard register. */ |
| static int |
| bucket_allocno_compare_func (const void *v1p, const void *v2p) |
| { |
| ira_allocno_t a1 = *(const ira_allocno_t *) v1p; |
| ira_allocno_t a2 = *(const ira_allocno_t *) v2p; |
| int diff, freq1, freq2, a1_num, a2_num, pref1, pref2; |
| ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno; |
| ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno; |
| int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2); |
| |
| freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq; |
| freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq; |
| if ((diff = freq1 - freq2) != 0) |
| return diff; |
| |
| if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0) |
| return diff; |
| |
| /* Push pseudos requiring less hard registers first. It means that |
| we will assign pseudos requiring more hard registers first |
| avoiding creation small holes in free hard register file into |
| which the pseudos requiring more hard registers cannot fit. */ |
| if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)] |
| - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0) |
| return diff; |
| |
| freq1 = ALLOCNO_FREQ (a1); |
| freq2 = ALLOCNO_FREQ (a2); |
| if ((diff = freq1 - freq2) != 0) |
| return diff; |
| |
| a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num; |
| a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num; |
| if ((diff = a2_num - a1_num) != 0) |
| return diff; |
| /* Push allocnos with minimal conflict_allocno_hard_prefs first. */ |
| pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs; |
| pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs; |
| if ((diff = pref1 - pref2) != 0) |
| return diff; |
| return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1); |
| } |
| |
| /* Sort bucket *BUCKET_PTR and return the result through |
| BUCKET_PTR. */ |
| static void |
| sort_bucket (ira_allocno_t *bucket_ptr, |
| int (*compare_func) (const void *, const void *)) |
| { |
| ira_allocno_t a, head; |
| int n; |
| |
| for (n = 0, a = *bucket_ptr; |
| a != NULL; |
| a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno) |
| sorted_allocnos[n++] = a; |
| if (n <= 1) |
| return; |
| qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func); |
| head = NULL; |
| for (n--; n >= 0; n--) |
| { |
| a = sorted_allocnos[n]; |
| ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head; |
| ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL; |
| if (head != NULL) |
| ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a; |
| head = a; |
| } |
| *bucket_ptr = head; |
| } |
| |
| /* Add ALLOCNO to colorable bucket maintaining the order according |
| their priority. ALLOCNO should be not in a bucket before the |
| call. */ |
| static void |
| add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno) |
| { |
| ira_allocno_t before, after; |
| |
| form_threads_from_colorable_allocno (allocno); |
| for (before = colorable_allocno_bucket, after = NULL; |
| before != NULL; |
| after = before, |
| before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno) |
| if (bucket_allocno_compare_func (&allocno, &before) < 0) |
| break; |
| ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before; |
| ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after; |
| if (after == NULL) |
| colorable_allocno_bucket = allocno; |
| else |
| ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno; |
| if (before != NULL) |
| ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno; |
| } |
| |
| /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before |
| the call. */ |
| static void |
| delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr) |
| { |
| ira_allocno_t prev_allocno, next_allocno; |
| |
| if (bucket_ptr == &uncolorable_allocno_bucket |
| && ALLOCNO_CLASS (allocno) != NO_REGS) |
| { |
| uncolorable_allocnos_num--; |
| ira_assert (uncolorable_allocnos_num >= 0); |
| } |
| prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno; |
| next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno; |
| if (prev_allocno != NULL) |
| ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno; |
| else |
| { |
| ira_assert (*bucket_ptr == allocno); |
| *bucket_ptr = next_allocno; |
| } |
| if (next_allocno != NULL) |
| ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno; |
| } |
| |
| /* Put allocno A onto the coloring stack without removing it from its |
| bucket. Pushing allocno to the coloring stack can result in moving |
| conflicting allocnos from the uncolorable bucket to the colorable |
| one. Update conflict_allocno_hard_prefs of the conflicting |
| allocnos which are not on stack yet. */ |
| static void |
| push_allocno_to_stack (ira_allocno_t a) |
| { |
| enum reg_class aclass; |
| allocno_color_data_t data, conflict_data; |
| int size, i, n = ALLOCNO_NUM_OBJECTS (a); |
| |
| data = ALLOCNO_COLOR_DATA (a); |
| data->in_graph_p = false; |
| allocno_stack_vec.safe_push (a); |
| aclass = ALLOCNO_CLASS (a); |
| if (aclass == NO_REGS) |
| return; |
| size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)]; |
| if (n > 1) |
| { |
| /* We will deal with the subwords individually. */ |
| gcc_assert (size == ALLOCNO_NUM_OBJECTS (a)); |
| size = 1; |
| } |
| for (i = 0; i < n; i++) |
| { |
| ira_object_t obj = ALLOCNO_OBJECT (a, i); |
| ira_object_t conflict_obj; |
| ira_object_conflict_iterator oci; |
| |
| FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) |
| { |
| ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); |
| ira_pref_t pref; |
| |
| conflict_data = ALLOCNO_COLOR_DATA (conflict_a); |
| if (! conflict_data->in_graph_p |
| || ALLOCNO_ASSIGNED_P (conflict_a) |
| || !(hard_reg_set_intersect_p |
| (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs, |
| conflict_data->profitable_hard_regs))) |
| continue; |
| for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref) |
| conflict_data->conflict_allocno_hard_prefs -= pref->freq; |
| if (conflict_data->colorable_p) |
| continue; |
| ira_assert (bitmap_bit_p (coloring_allocno_bitmap, |
| ALLOCNO_NUM (conflict_a))); |
| if (update_left_conflict_sizes_p (conflict_a, a, size)) |
| { |
| delete_allocno_from_bucket |
| (conflict_a, &uncolorable_allocno_bucket); |
| add_allocno_to_ordered_colorable_bucket (conflict_a); |
| if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) |
| { |
| fprintf (ira_dump_file, " Making"); |
| ira_print_expanded_allocno (conflict_a); |
| fprintf (ira_dump_file, " colorable\n"); |
| } |
| } |
| |
| } |
| } |
| } |
| |
| /* Put ALLOCNO onto the coloring stack and remove it from its bucket. |
| The allocno is in the colorable bucket if COLORABLE_P is TRUE. */ |
| static void |
| remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p) |
| { |
| if (colorable_p) |
| delete_allocno_from_bucket (allocno, &colorable_allocno_bucket); |
| else |
| delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket); |
| if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| { |
| fprintf (ira_dump_file, " Pushing"); |
| ira_print_expanded_allocno (allocno); |
| if (colorable_p) |
| fprintf (ira_dump_file, "(cost %d)\n", |
| ALLOCNO_COLOR_DATA (allocno)->temp); |
| else |
| fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n", |
| ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "", |
| allocno_spill_priority (allocno), |
| ALLOCNO_COLOR_DATA (allocno)->temp); |
| } |
| if (! colorable_p) |
| ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true; |
| push_allocno_to_stack (allocno); |
| } |
| |
| /* Put all allocnos from colorable bucket onto the coloring stack. */ |
| static void |
| push_only_colorable (void) |
| { |
| if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, " Forming thread from colorable bucket:\n"); |
| form_threads_from_bucket (colorable_allocno_bucket); |
| for (ira_allocno_t a = colorable_allocno_bucket; |
| a != NULL; |
| a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno) |
| update_costs_from_prefs (a); |
| sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func); |
| for (;colorable_allocno_bucket != NULL;) |
| remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true); |
| } |
| |
| /* Return the frequency of exit edges (if EXIT_P) or entry from/to the |
| loop given by its LOOP_NODE. */ |
| int |
| ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p) |
| { |
| int freq, i; |
| edge_iterator ei; |
| edge e; |
| |
| ira_assert (current_loops != NULL && loop_node->loop != NULL |
| && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER)); |
| freq = 0; |
| if (! exit_p) |
| { |
| FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds) |
| if (e->src != loop_node->loop->latch |
| && (regno < 0 |
| || (bitmap_bit_p (df_get_live_out (e->src), regno) |
| && bitmap_bit_p (df_get_live_in (e->dest), regno)))) |
| freq += EDGE_FREQUENCY (e); |
| } |
| else |
| { |
| auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop); |
| FOR_EACH_VEC_ELT (edges, i, e) |
| if (regno < 0 |
| || (bitmap_bit_p (df_get_live_out (e->src), regno) |
| && bitmap_bit_p (df_get_live_in (e->dest), regno))) |
| freq += EDGE_FREQUENCY (e); |
| } |
| |
| return REG_FREQ_FROM_EDGE_FREQ (freq); |
| } |
| |
| /* Construct an object that describes the boundary between A and its |
| parent allocno. */ |
| ira_loop_border_costs::ira_loop_border_costs (ira_allocno_t a) |
| : m_mode (ALLOCNO_MODE (a)), |
| m_class (ALLOCNO_CLASS (a)), |
| m_entry_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a), |
| ALLOCNO_REGNO (a), false)), |
| m_exit_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a), |
| ALLOCNO_REGNO (a), true)) |
| { |
| } |
| |
| /* Calculate and return the cost of putting allocno A into memory. */ |
| static int |
| calculate_allocno_spill_cost (ira_allocno_t a) |
| { |
| int regno, cost; |
| ira_allocno_t parent_allocno; |
| ira_loop_tree_node_t parent_node, loop_node; |
| |
| regno = ALLOCNO_REGNO (a); |
| cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a); |
| if (ALLOCNO_CAP (a) != NULL) |
| return cost; |
| loop_node = ALLOCNO_LOOP_TREE_NODE (a); |
| if ((parent_node = loop_node->parent) == NULL) |
| return cost; |
| if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL) |
| return cost; |
| ira_loop_border_costs border_costs (a); |
| if (ALLOCNO_HARD_REGNO (parent_allocno) < 0) |
| cost -= border_costs.spill_outside_loop_cost (); |
| else |
| cost += (border_costs.spill_inside_loop_cost () |
| - border_costs.move_between_loops_cost ()); |
| return cost; |
| } |
| |
| /* Used for sorting allocnos for spilling. */ |
| static inline int |
| allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2) |
| { |
| int pri1, pri2, diff; |
| |
| /* Avoid spilling static chain pointer pseudo when non-local goto is |
| used. */ |
| if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1))) |
| return 1; |
| else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2))) |
| return -1; |
| if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2)) |
| return 1; |
| if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1)) |
| return -1; |
| pri1 = allocno_spill_priority (a1); |
| pri2 = allocno_spill_priority (a2); |
| if ((diff = pri1 - pri2) != 0) |
| return diff; |
| if ((diff |
| = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0) |
| return diff; |
| return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2); |
| } |
| |
| /* Used for sorting allocnos for spilling. */ |
| static int |
| allocno_spill_sort_compare (const void *v1p, const void *v2p) |
| { |
| ira_allocno_t p1 = *(const ira_allocno_t *) v1p; |
| ira_allocno_t p2 = *(const ira_allocno_t *) v2p; |
| |
| return allocno_spill_priority_compare (p1, p2); |
| } |
| |
| /* Push allocnos to the coloring stack. The order of allocnos in the |
| stack defines the order for the subsequent coloring. */ |
| static void |
| push_allocnos_to_stack (void) |
| { |
| ira_allocno_t a; |
| int cost; |
| |
| /* Calculate uncolorable allocno spill costs. */ |
| for (a = uncolorable_allocno_bucket; |
| a != NULL; |
| a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno) |
| if (ALLOCNO_CLASS (a) != NO_REGS) |
| { |
| cost = calculate_allocno_spill_cost (a); |
| /* ??? Remove cost of copies between the coalesced |
| allocnos. */ |
| ALLOCNO_COLOR_DATA (a)->temp = cost; |
| } |
| sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare); |
| for (;;) |
| { |
| push_only_colorable (); |
| a = uncolorable_allocno_bucket; |
| if (a == NULL) |
| break; |
| remove_allocno_from_bucket_and_push (a, false); |
| } |
| ira_assert (colorable_allocno_bucket == NULL |
| && uncolorable_allocno_bucket == NULL); |
| ira_assert (uncolorable_allocnos_num == 0); |
| } |
| |
| /* Pop the coloring stack and assign hard registers to the popped |
| allocnos. */ |
| static void |
| pop_allocnos_from_stack (void) |
| { |
| ira_allocno_t allocno; |
| enum reg_class aclass; |
| |
| for (;allocno_stack_vec.length () != 0;) |
| { |
| allocno = allocno_stack_vec.pop (); |
| aclass = ALLOCNO_CLASS (allocno); |
| if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| { |
| fprintf (ira_dump_file, " Popping"); |
| ira_print_expanded_allocno (allocno); |
| fprintf (ira_dump_file, " -- "); |
| } |
| if (aclass == NO_REGS) |
| { |
| ALLOCNO_HARD_REGNO (allocno) = -1; |
| ALLOCNO_ASSIGNED_P (allocno) = true; |
| ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL); |
| ira_assert |
| (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL); |
| if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, "assign memory\n"); |
| } |
| else if (assign_hard_reg (allocno, false)) |
| { |
| if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, " assign reg %d\n", |
| ALLOCNO_HARD_REGNO (allocno)); |
| } |
| else if (ALLOCNO_ASSIGNED_P (allocno)) |
| { |
| if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) |
| fprintf (ira_dump_file, "spill%s\n", |
| ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p |
| ? "" : "!"); |
| } |
| ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true; |
| } |
| } |
| |
| /* Set up number of available hard registers for allocno A. */ |
| static void |
| setup_allocno_available_regs_num (ira_allocno_t a) |
| { |
| int i, n, hard_regno, hard_regs_num, nwords; |
| enum reg_class aclass; |
| allocno_color_data_t data; |
| |
| aclass = ALLOCNO_CLASS (a); |
| data = ALLOCNO_COLOR_DATA (a); |
| data->available_regs_num = 0; |
| if (aclass == NO_REGS) |
| return; |
| hard_regs_num = ira_class_hard_regs_num[aclass]; |
| nwords = ALLOCNO_NUM_OBJECTS (a); |
| for (n = 0, i = hard_regs_num - 1; i >= 0; i--) |
| { |
| hard_regno = ira_class_hard_regs[aclass][i]; |
| /* Checking only profitable hard regs. */ |
| if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno)) |
| n++; |
| } |
| data->available_regs_num = n; |
| if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL) |
| return; |
| fprintf |
| (ira_dump_file, |
| " Allocno a%dr%d of %s(%d) has %d avail. regs ", |
| ALLOCNO_NUM (a), ALLOCNO_REGNO (a), |
| reg_class_names[aclass], ira_class_hard_regs_num[aclass], n); |
| print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false); |
| fprintf (ira_dump_file, ", %snode: ", |
| data->profitable_hard_regs == data->hard_regs_node->hard_regs->set |
| ? "" : "^"); |
| print_hard_reg_set (ira_dump_file, |
| data->hard_regs_node->hard_regs->set, false); |
| for (i = 0; i < nwords; i++) |
| { |
| ira_object_t obj = ALLOCNO_OBJECT (a, i); |
| |
| if (nwords != 1) |
| { |
| if (i != 0) |
| fprintf (ira_dump_file, ", "); |
| fprintf (ira_dump_file, " obj %d", i); |
| } |
| fprintf (ira_dump_file, " (confl regs = "); |
| print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), |
| false); |
| fprintf (ira_dump_file, ")"); |
| } |
| fprintf (ira_dump_file, "\n"); |
| } |
| |
| /* Put ALLOCNO in a bucket corresponding to its number and size of its |
| conflicting allocnos and hard registers. */ |
| static void |
| put_allocno_into_bucket (ira_allocno_t allocno) |
| { |
| ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true; |
| setup_allocno_available_regs_num (allocno); |
| if (setup_left_conflict_sizes_p (allocno)) |
| add_allocno_to_bucket (allocno, &colorable_allocno_bucket); |
| else |
| add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket); |
| } |
| |
| /* Map: allocno number -> allocno priority. */ |
| static int *allocno_priorities; |
| |
| /* Set up priorities for N allocnos in array |
| CONSIDERATION_ALLOCNOS. */ |
| static void |
| setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n) |
| { |
| int i, length, nrefs, priority, max_priority, mult, diff; |
| ira_allocno_t a; |
| |
| max_priority = 0; |
| for (i = 0; i < n; i++) |
| { |
| a = consideration_allocnos[i]; |
| nrefs = ALLOCNO_NREFS (a); |
| ira_assert (nrefs >= 0); |
| mult = floor_log2 (ALLOCNO_NREFS (a)) + 1; |
| ira_assert (mult >= 0); |
| mult *= ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]; |
| diff = ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a); |
| #ifdef __has_builtin |
| #if __has_builtin(__builtin_smul_overflow) |
| #define HAS_SMUL_OVERFLOW |
| #endif |
| #endif |
| /* Multiplication can overflow for very large functions. |
| Check the overflow and constrain the result if necessary: */ |
| #ifdef HAS_SMUL_OVERFLOW |
| if (__builtin_smul_overflow (mult, diff, &priority) |
| || priority < -INT_MAX) |
| priority = diff >= 0 ? INT_MAX : -INT_MAX; |
| #else |
| static_assert |
| (sizeof (long long) >= 2 * sizeof (int), |
| "overflow code does not work for such int and long long sizes"); |
| long long priorityll = (long long) mult * diff; |
| if (priorityll < -INT_MAX || priorityll > INT_MAX) |
| priority = diff >= 0 ? INT_MAX : -INT_MAX; |
| else |
| priority = priorityll; |
| #endif |
| allocno_priorities[ALLOCNO_NUM (a)] = priority; |
| if (priority < 0) |
| priority = -priority; |
| if (max_priority < priority) |
| max_priority = priority; |
| } |
| mult = max_priority == 0 ? 1 : INT_MAX / max_priority; |
| for (i = 0; i < n; i++) |
| { |
| a = consideration_allocnos[i]; |
| length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); |
| if (ALLOCNO_NUM_OBJECTS (a) > 1) |
| length /= ALLOCNO_NUM_OBJECTS (a); |
| if (length <= 0) |
| length = 1; |
| allocno_priorities[ALLOCNO_NUM (a)] |
| = allocno_priorities[ALLOCNO_NUM (a)] * mult / length; |
| } |
| } |
| |
| /* Sort allocnos according to the profit of usage of a hard register |
| instead of memory for them. */ |
| static int |
| allocno_cost_compare_func (const void *v1p, const void *v2p) |
| { |
| ira_allocno_t p1 = *(const ira_allocno_t *) v1p; |
| ira_allocno_t p2 = *(const ira_allocno_t *) v2p; |
| int c1, c2; |
| |
| c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1); |
| c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2); |
| if (c1 -
|