Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-coalesce.c @ 56:3c8a44c06a95
Added tag gcc-4.4.5 for changeset 77e2b8dfacca
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:41:23 +0900 |
| parents | 77e2b8dfacca |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* Coalesce SSA_NAMES together for the out-of-ssa pass. |
| 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 | |
| 3 Free Software Foundation, Inc. | |
| 4 Contributed by Andrew MacLeod <amacleod@redhat.com> | |
| 5 | |
| 6 This file is part of GCC. | |
| 7 | |
| 8 GCC is free software; you can redistribute it and/or modify | |
| 9 it under the terms of the GNU General Public License as published by | |
| 10 the Free Software Foundation; either version 3, or (at your option) | |
| 11 any later version. | |
| 12 | |
| 13 GCC is distributed in the hope that it will be useful, | |
| 14 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 16 GNU General Public License for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
| 19 along with GCC; see the file COPYING3. If not see | |
| 20 <http://www.gnu.org/licenses/>. */ | |
| 21 | |
| 22 #include "config.h" | |
| 23 #include "system.h" | |
| 24 #include "coretypes.h" | |
| 25 #include "tm.h" | |
| 26 #include "tree.h" | |
| 27 #include "flags.h" | |
| 28 #include "diagnostic.h" | |
| 29 #include "bitmap.h" | |
| 30 #include "tree-flow.h" | |
| 31 #include "hashtab.h" | |
| 32 #include "tree-dump.h" | |
| 33 #include "tree-ssa-live.h" | |
| 34 #include "toplev.h" | |
| 35 | |
| 36 | |
| 37 /* This set of routines implements a coalesce_list. This is an object which | |
| 38 is used to track pairs of ssa_names which are desirable to coalesce | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
39 together to avoid copies. Costs are associated with each pair, and when |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
40 all desired information has been collected, the object can be used to |
| 0 | 41 order the pairs for processing. */ |
| 42 | |
| 43 /* This structure defines a pair entry. */ | |
| 44 | |
| 45 typedef struct coalesce_pair | |
| 46 { | |
| 47 int first_element; | |
| 48 int second_element; | |
| 49 int cost; | |
| 50 } * coalesce_pair_p; | |
| 51 typedef const struct coalesce_pair *const_coalesce_pair_p; | |
| 52 | |
| 53 typedef struct cost_one_pair_d | |
| 54 { | |
| 55 int first_element; | |
| 56 int second_element; | |
| 57 struct cost_one_pair_d *next; | |
| 58 } * cost_one_pair_p; | |
| 59 | |
| 60 /* This structure maintains the list of coalesce pairs. */ | |
| 61 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
62 typedef struct coalesce_list_d |
| 0 | 63 { |
| 64 htab_t list; /* Hash table. */ | |
| 65 coalesce_pair_p *sorted; /* List when sorted. */ | |
| 66 int num_sorted; /* Number in the sorted list. */ | |
| 67 cost_one_pair_p cost_one_list;/* Single use coalesces with cost 1. */ | |
| 68 } *coalesce_list_p; | |
| 69 | |
| 70 #define NO_BEST_COALESCE -1 | |
| 71 #define MUST_COALESCE_COST INT_MAX | |
| 72 | |
| 73 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
74 /* Return cost of execution of copy instruction with FREQUENCY. */ |
| 0 | 75 |
| 76 static inline int | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
77 coalesce_cost (int frequency, bool optimize_for_size) |
| 0 | 78 { |
| 79 /* Base costs on BB frequencies bounded by 1. */ | |
| 80 int cost = frequency; | |
| 81 | |
| 82 if (!cost) | |
| 83 cost = 1; | |
| 84 | |
| 85 if (optimize_for_size) | |
| 86 cost = 1; | |
| 87 | |
| 88 return cost; | |
| 89 } | |
| 90 | |
| 91 | |
| 92 /* Return the cost of executing a copy instruction in basic block BB. */ | |
| 93 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
94 static inline int |
| 0 | 95 coalesce_cost_bb (basic_block bb) |
| 96 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
97 return coalesce_cost (bb->frequency, optimize_bb_for_size_p (bb)); |
| 0 | 98 } |
| 99 | |
| 100 | |
| 101 /* Return the cost of executing a copy instruction on edge E. */ | |
| 102 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
103 static inline int |
| 0 | 104 coalesce_cost_edge (edge e) |
| 105 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
106 int mult = 1; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
107 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
108 /* Inserting copy on critical edge costs more than inserting it elsewhere. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
109 if (EDGE_CRITICAL_P (e)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
110 mult = 2; |
| 0 | 111 if (e->flags & EDGE_ABNORMAL) |
| 112 return MUST_COALESCE_COST; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
113 if (e->flags & EDGE_EH) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
114 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
115 edge e2; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
116 edge_iterator ei; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
117 FOR_EACH_EDGE (e2, ei, e->dest->preds) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
118 if (e2 != e) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
119 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
120 /* Putting code on EH edge that leads to BB |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
121 with multiple predecestors imply splitting of |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
122 edge too. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
123 if (mult < 2) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
124 mult = 2; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
125 /* If there are multiple EH predecestors, we |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
126 also copy EH regions and produce separate |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
127 landing pad. This is expensive. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
128 if (e2->flags & EDGE_EH) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
129 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
130 mult = 5; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
131 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
132 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
133 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
134 } |
| 0 | 135 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
136 return coalesce_cost (EDGE_FREQUENCY (e), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
137 optimize_edge_for_size_p (e)) * mult; |
| 0 | 138 } |
| 139 | |
| 140 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
141 /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the |
| 0 | 142 2 elements via P1 and P2. 1 is returned by the function if there is a pair, |
| 143 NO_BEST_COALESCE is returned if there aren't any. */ | |
| 144 | |
| 145 static inline int | |
| 146 pop_cost_one_pair (coalesce_list_p cl, int *p1, int *p2) | |
| 147 { | |
| 148 cost_one_pair_p ptr; | |
| 149 | |
| 150 ptr = cl->cost_one_list; | |
| 151 if (!ptr) | |
| 152 return NO_BEST_COALESCE; | |
| 153 | |
| 154 *p1 = ptr->first_element; | |
| 155 *p2 = ptr->second_element; | |
| 156 cl->cost_one_list = ptr->next; | |
| 157 | |
| 158 free (ptr); | |
| 159 | |
| 160 return 1; | |
| 161 } | |
| 162 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
163 /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the |
| 0 | 164 2 elements via P1 and P2. Their calculated cost is returned by the function. |
| 165 NO_BEST_COALESCE is returned if the coalesce list is empty. */ | |
| 166 | |
| 167 static inline int | |
| 168 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2) | |
| 169 { | |
| 170 coalesce_pair_p node; | |
| 171 int ret; | |
| 172 | |
| 173 if (cl->sorted == NULL) | |
| 174 return pop_cost_one_pair (cl, p1, p2); | |
| 175 | |
| 176 if (cl->num_sorted == 0) | |
| 177 return pop_cost_one_pair (cl, p1, p2); | |
| 178 | |
| 179 node = cl->sorted[--(cl->num_sorted)]; | |
| 180 *p1 = node->first_element; | |
| 181 *p2 = node->second_element; | |
| 182 ret = node->cost; | |
| 183 free (node); | |
| 184 | |
| 185 return ret; | |
| 186 } | |
| 187 | |
| 188 | |
| 189 #define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1)) | |
| 190 | |
| 191 /* Hash function for coalesce list. Calculate hash for PAIR. */ | |
| 192 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
193 static unsigned int |
| 0 | 194 coalesce_pair_map_hash (const void *pair) |
| 195 { | |
| 196 hashval_t a = (hashval_t)(((const_coalesce_pair_p)pair)->first_element); | |
| 197 hashval_t b = (hashval_t)(((const_coalesce_pair_p)pair)->second_element); | |
| 198 | |
| 199 return COALESCE_HASH_FN (a,b); | |
| 200 } | |
| 201 | |
| 202 | |
| 203 /* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2, | |
| 204 returning TRUE if the two pairs are equivalent. */ | |
| 205 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 static int |
| 0 | 207 coalesce_pair_map_eq (const void *pair1, const void *pair2) |
| 208 { | |
| 209 const_coalesce_pair_p const p1 = (const_coalesce_pair_p) pair1; | |
| 210 const_coalesce_pair_p const p2 = (const_coalesce_pair_p) pair2; | |
| 211 | |
| 212 return (p1->first_element == p2->first_element | |
| 213 && p1->second_element == p2->second_element); | |
| 214 } | |
| 215 | |
| 216 | |
| 217 /* Create a new empty coalesce list object and return it. */ | |
| 218 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
219 static inline coalesce_list_p |
| 0 | 220 create_coalesce_list (void) |
| 221 { | |
| 222 coalesce_list_p list; | |
| 223 unsigned size = num_ssa_names * 3; | |
| 224 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
225 if (size < 40) |
| 0 | 226 size = 40; |
| 227 | |
| 228 list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d)); | |
| 229 list->list = htab_create (size, coalesce_pair_map_hash, | |
| 230 coalesce_pair_map_eq, NULL); | |
| 231 list->sorted = NULL; | |
| 232 list->num_sorted = 0; | |
| 233 list->cost_one_list = NULL; | |
| 234 return list; | |
| 235 } | |
| 236 | |
| 237 | |
| 238 /* Delete coalesce list CL. */ | |
| 239 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
240 static inline void |
| 0 | 241 delete_coalesce_list (coalesce_list_p cl) |
| 242 { | |
| 243 gcc_assert (cl->cost_one_list == NULL); | |
| 244 htab_delete (cl->list); | |
| 245 if (cl->sorted) | |
| 246 free (cl->sorted); | |
| 247 gcc_assert (cl->num_sorted == 0); | |
| 248 free (cl); | |
| 249 } | |
| 250 | |
| 251 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
252 /* Find a matching coalesce pair object in CL for the pair P1 and P2. If |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
253 one isn't found, return NULL if CREATE is false, otherwise create a new |
| 0 | 254 coalesce pair object and return it. */ |
| 255 | |
| 256 static coalesce_pair_p | |
| 257 find_coalesce_pair (coalesce_list_p cl, int p1, int p2, bool create) | |
| 258 { | |
| 259 struct coalesce_pair p, *pair; | |
| 260 void **slot; | |
| 261 unsigned int hash; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
262 |
| 0 | 263 /* Normalize so that p1 is the smaller value. */ |
| 264 if (p2 < p1) | |
| 265 { | |
| 266 p.first_element = p2; | |
| 267 p.second_element = p1; | |
| 268 } | |
| 269 else | |
| 270 { | |
| 271 p.first_element = p1; | |
| 272 p.second_element = p2; | |
| 273 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
274 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
275 |
| 0 | 276 hash = coalesce_pair_map_hash (&p); |
| 277 pair = (struct coalesce_pair *) htab_find_with_hash (cl->list, &p, hash); | |
| 278 | |
| 279 if (create && !pair) | |
| 280 { | |
| 281 gcc_assert (cl->sorted == NULL); | |
| 282 pair = XNEW (struct coalesce_pair); | |
| 283 pair->first_element = p.first_element; | |
| 284 pair->second_element = p.second_element; | |
| 285 pair->cost = 0; | |
| 286 slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT); | |
| 287 *(struct coalesce_pair **)slot = pair; | |
| 288 } | |
| 289 | |
| 290 return pair; | |
| 291 } | |
| 292 | |
| 293 static inline void | |
| 294 add_cost_one_coalesce (coalesce_list_p cl, int p1, int p2) | |
| 295 { | |
| 296 cost_one_pair_p pair; | |
| 297 | |
| 298 pair = XNEW (struct cost_one_pair_d); | |
| 299 pair->first_element = p1; | |
| 300 pair->second_element = p2; | |
| 301 pair->next = cl->cost_one_list; | |
| 302 cl->cost_one_list = pair; | |
| 303 } | |
| 304 | |
| 305 | |
| 306 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */ | |
| 307 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
308 static inline void |
| 0 | 309 add_coalesce (coalesce_list_p cl, int p1, int p2, int value) |
| 310 { | |
| 311 coalesce_pair_p node; | |
| 312 | |
| 313 gcc_assert (cl->sorted == NULL); | |
| 314 if (p1 == p2) | |
| 315 return; | |
| 316 | |
| 317 node = find_coalesce_pair (cl, p1, p2, true); | |
| 318 | |
| 319 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */ | |
| 320 if (node->cost < MUST_COALESCE_COST - 1) | |
| 321 { | |
| 322 if (value < MUST_COALESCE_COST - 1) | |
| 323 node->cost += value; | |
| 324 else | |
| 325 node->cost = value; | |
| 326 } | |
| 327 } | |
| 328 | |
| 329 | |
| 330 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */ | |
| 331 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
332 static int |
| 0 | 333 compare_pairs (const void *p1, const void *p2) |
| 334 { | |
| 335 const_coalesce_pair_p const *const pp1 = (const_coalesce_pair_p const *) p1; | |
| 336 const_coalesce_pair_p const *const pp2 = (const_coalesce_pair_p const *) p2; | |
| 337 int result; | |
| 338 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
339 result = (* pp1)->cost - (* pp2)->cost; |
| 0 | 340 /* Since qsort does not guarantee stability we use the elements |
| 341 as a secondary key. This provides us with independence from | |
| 342 the host's implementation of the sorting algorithm. */ | |
| 343 if (result == 0) | |
| 344 { | |
| 345 result = (* pp2)->first_element - (* pp1)->first_element; | |
| 346 if (result == 0) | |
| 347 result = (* pp2)->second_element - (* pp1)->second_element; | |
| 348 } | |
| 349 | |
| 350 return result; | |
| 351 } | |
| 352 | |
| 353 | |
| 354 /* Return the number of unique coalesce pairs in CL. */ | |
| 355 | |
| 356 static inline int | |
| 357 num_coalesce_pairs (coalesce_list_p cl) | |
| 358 { | |
| 359 return htab_elements (cl->list); | |
| 360 } | |
| 361 | |
| 362 | |
| 363 /* Iterator over hash table pairs. */ | |
| 364 typedef struct | |
| 365 { | |
| 366 htab_iterator hti; | |
| 367 } coalesce_pair_iterator; | |
| 368 | |
| 369 | |
| 370 /* Return first partition pair from list CL, initializing iterator ITER. */ | |
| 371 | |
| 372 static inline coalesce_pair_p | |
| 373 first_coalesce_pair (coalesce_list_p cl, coalesce_pair_iterator *iter) | |
| 374 { | |
| 375 coalesce_pair_p pair; | |
| 376 | |
| 377 pair = (coalesce_pair_p) first_htab_element (&(iter->hti), cl->list); | |
| 378 return pair; | |
| 379 } | |
| 380 | |
| 381 | |
| 382 /* Return TRUE if there are no more partitions in for ITER to process. */ | |
| 383 | |
| 384 static inline bool | |
| 385 end_coalesce_pair_p (coalesce_pair_iterator *iter) | |
| 386 { | |
| 387 return end_htab_p (&(iter->hti)); | |
| 388 } | |
| 389 | |
| 390 | |
| 391 /* Return the next partition pair to be visited by ITER. */ | |
| 392 | |
| 393 static inline coalesce_pair_p | |
| 394 next_coalesce_pair (coalesce_pair_iterator *iter) | |
| 395 { | |
| 396 coalesce_pair_p pair; | |
| 397 | |
| 398 pair = (coalesce_pair_p) next_htab_element (&(iter->hti)); | |
| 399 return pair; | |
| 400 } | |
| 401 | |
| 402 | |
| 403 /* Iterate over CL using ITER, returning values in PAIR. */ | |
| 404 | |
| 405 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \ | |
| 406 for ((PAIR) = first_coalesce_pair ((CL), &(ITER)); \ | |
| 407 !end_coalesce_pair_p (&(ITER)); \ | |
| 408 (PAIR) = next_coalesce_pair (&(ITER))) | |
| 409 | |
| 410 | |
| 411 /* Prepare CL for removal of preferred pairs. When finished they are sorted | |
| 412 in order from most important coalesce to least important. */ | |
| 413 | |
| 414 static void | |
| 415 sort_coalesce_list (coalesce_list_p cl) | |
| 416 { | |
| 417 unsigned x, num; | |
| 418 coalesce_pair_p p; | |
| 419 coalesce_pair_iterator ppi; | |
| 420 | |
| 421 gcc_assert (cl->sorted == NULL); | |
| 422 | |
| 423 num = num_coalesce_pairs (cl); | |
| 424 cl->num_sorted = num; | |
| 425 if (num == 0) | |
| 426 return; | |
| 427 | |
| 428 /* Allocate a vector for the pair pointers. */ | |
| 429 cl->sorted = XNEWVEC (coalesce_pair_p, num); | |
| 430 | |
| 431 /* Populate the vector with pointers to the pairs. */ | |
| 432 x = 0; | |
| 433 FOR_EACH_PARTITION_PAIR (p, ppi, cl) | |
| 434 cl->sorted[x++] = p; | |
| 435 gcc_assert (x == num); | |
| 436 | |
| 437 /* Already sorted. */ | |
| 438 if (num == 1) | |
| 439 return; | |
| 440 | |
| 441 /* If there are only 2, just pick swap them if the order isn't correct. */ | |
| 442 if (num == 2) | |
| 443 { | |
| 444 if (cl->sorted[0]->cost > cl->sorted[1]->cost) | |
| 445 { | |
| 446 p = cl->sorted[0]; | |
| 447 cl->sorted[0] = cl->sorted[1]; | |
| 448 cl->sorted[1] = p; | |
| 449 } | |
| 450 return; | |
| 451 } | |
| 452 | |
| 453 /* Only call qsort if there are more than 2 items. */ | |
| 454 if (num > 2) | |
| 455 qsort (cl->sorted, num, sizeof (coalesce_pair_p), compare_pairs); | |
| 456 } | |
| 457 | |
| 458 | |
| 459 /* Send debug info for coalesce list CL to file F. */ | |
| 460 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
461 static void |
| 0 | 462 dump_coalesce_list (FILE *f, coalesce_list_p cl) |
| 463 { | |
| 464 coalesce_pair_p node; | |
| 465 coalesce_pair_iterator ppi; | |
| 466 int x; | |
| 467 tree var; | |
| 468 | |
| 469 if (cl->sorted == NULL) | |
| 470 { | |
| 471 fprintf (f, "Coalesce List:\n"); | |
| 472 FOR_EACH_PARTITION_PAIR (node, ppi, cl) | |
| 473 { | |
| 474 tree var1 = ssa_name (node->first_element); | |
| 475 tree var2 = ssa_name (node->second_element); | |
| 476 print_generic_expr (f, var1, TDF_SLIM); | |
| 477 fprintf (f, " <-> "); | |
| 478 print_generic_expr (f, var2, TDF_SLIM); | |
| 479 fprintf (f, " (%1d), ", node->cost); | |
| 480 fprintf (f, "\n"); | |
| 481 } | |
| 482 } | |
| 483 else | |
| 484 { | |
| 485 fprintf (f, "Sorted Coalesce list:\n"); | |
| 486 for (x = cl->num_sorted - 1 ; x >=0; x--) | |
| 487 { | |
| 488 node = cl->sorted[x]; | |
| 489 fprintf (f, "(%d) ", node->cost); | |
| 490 var = ssa_name (node->first_element); | |
| 491 print_generic_expr (f, var, TDF_SLIM); | |
| 492 fprintf (f, " <-> "); | |
| 493 var = ssa_name (node->second_element); | |
| 494 print_generic_expr (f, var, TDF_SLIM); | |
| 495 fprintf (f, "\n"); | |
| 496 } | |
| 497 } | |
| 498 } | |
| 499 | |
| 500 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
501 /* This represents a conflict graph. Implemented as an array of bitmaps. |
| 0 | 502 A full matrix is used for conflicts rather than just upper triangular form. |
| 503 this make sit much simpler and faster to perform conflict merges. */ | |
| 504 | |
| 505 typedef struct ssa_conflicts_d | |
| 506 { | |
| 507 unsigned size; | |
| 508 bitmap *conflicts; | |
| 509 } * ssa_conflicts_p; | |
| 510 | |
| 511 | |
| 512 /* Return an empty new conflict graph for SIZE elements. */ | |
| 513 | |
| 514 static inline ssa_conflicts_p | |
| 515 ssa_conflicts_new (unsigned size) | |
| 516 { | |
| 517 ssa_conflicts_p ptr; | |
| 518 | |
| 519 ptr = XNEW (struct ssa_conflicts_d); | |
| 520 ptr->conflicts = XCNEWVEC (bitmap, size); | |
| 521 ptr->size = size; | |
| 522 return ptr; | |
| 523 } | |
| 524 | |
| 525 | |
| 526 /* Free storage for conflict graph PTR. */ | |
| 527 | |
| 528 static inline void | |
| 529 ssa_conflicts_delete (ssa_conflicts_p ptr) | |
| 530 { | |
| 531 unsigned x; | |
| 532 for (x = 0; x < ptr->size; x++) | |
| 533 if (ptr->conflicts[x]) | |
| 534 BITMAP_FREE (ptr->conflicts[x]); | |
| 535 | |
| 536 free (ptr->conflicts); | |
| 537 free (ptr); | |
| 538 } | |
| 539 | |
| 540 | |
| 541 /* Test if elements X and Y conflict in graph PTR. */ | |
| 542 | |
| 543 static inline bool | |
| 544 ssa_conflicts_test_p (ssa_conflicts_p ptr, unsigned x, unsigned y) | |
| 545 { | |
| 546 bitmap b; | |
| 547 | |
| 548 #ifdef ENABLE_CHECKING | |
| 549 gcc_assert (x < ptr->size); | |
| 550 gcc_assert (y < ptr->size); | |
| 551 gcc_assert (x != y); | |
| 552 #endif | |
| 553 | |
| 554 b = ptr->conflicts[x]; | |
| 555 if (b) | |
| 556 /* Avoid the lookup if Y has no conflicts. */ | |
| 557 return ptr->conflicts[y] ? bitmap_bit_p (b, y) : false; | |
| 558 else | |
| 559 return false; | |
| 560 } | |
| 561 | |
| 562 | |
| 563 /* Add a conflict with Y to the bitmap for X in graph PTR. */ | |
| 564 | |
| 565 static inline void | |
| 566 ssa_conflicts_add_one (ssa_conflicts_p ptr, unsigned x, unsigned y) | |
| 567 { | |
| 568 /* If there are no conflicts yet, allocate the bitmap and set bit. */ | |
| 569 if (!ptr->conflicts[x]) | |
| 570 ptr->conflicts[x] = BITMAP_ALLOC (NULL); | |
| 571 bitmap_set_bit (ptr->conflicts[x], y); | |
| 572 } | |
| 573 | |
| 574 | |
| 575 /* Add conflicts between X and Y in graph PTR. */ | |
| 576 | |
| 577 static inline void | |
| 578 ssa_conflicts_add (ssa_conflicts_p ptr, unsigned x, unsigned y) | |
| 579 { | |
| 580 #ifdef ENABLE_CHECKING | |
| 581 gcc_assert (x < ptr->size); | |
| 582 gcc_assert (y < ptr->size); | |
| 583 gcc_assert (x != y); | |
| 584 #endif | |
| 585 ssa_conflicts_add_one (ptr, x, y); | |
| 586 ssa_conflicts_add_one (ptr, y, x); | |
| 587 } | |
| 588 | |
| 589 | |
| 590 /* Merge all Y's conflict into X in graph PTR. */ | |
| 591 | |
| 592 static inline void | |
| 593 ssa_conflicts_merge (ssa_conflicts_p ptr, unsigned x, unsigned y) | |
| 594 { | |
| 595 unsigned z; | |
| 596 bitmap_iterator bi; | |
| 597 | |
| 598 gcc_assert (x != y); | |
| 599 if (!(ptr->conflicts[y])) | |
| 600 return; | |
| 601 | |
| 602 /* Add a conflict between X and every one Y has. If the bitmap doesn't | |
| 603 exist, then it has already been coalesced, and we don't need to add a | |
| 604 conflict. */ | |
| 605 EXECUTE_IF_SET_IN_BITMAP (ptr->conflicts[y], 0, z, bi) | |
| 606 if (ptr->conflicts[z]) | |
| 607 bitmap_set_bit (ptr->conflicts[z], x); | |
| 608 | |
| 609 if (ptr->conflicts[x]) | |
| 610 { | |
| 611 /* If X has conflicts, add Y's to X. */ | |
| 612 bitmap_ior_into (ptr->conflicts[x], ptr->conflicts[y]); | |
| 613 BITMAP_FREE (ptr->conflicts[y]); | |
| 614 } | |
| 615 else | |
| 616 { | |
| 617 /* If X has no conflicts, simply use Y's. */ | |
| 618 ptr->conflicts[x] = ptr->conflicts[y]; | |
| 619 ptr->conflicts[y] = NULL; | |
| 620 } | |
| 621 } | |
| 622 | |
| 623 | |
| 624 /* Dump a conflicts graph. */ | |
| 625 | |
| 626 static void | |
| 627 ssa_conflicts_dump (FILE *file, ssa_conflicts_p ptr) | |
| 628 { | |
| 629 unsigned x; | |
| 630 | |
| 631 fprintf (file, "\nConflict graph:\n"); | |
| 632 | |
| 633 for (x = 0; x < ptr->size; x++) | |
| 634 if (ptr->conflicts[x]) | |
| 635 { | |
| 636 fprintf (dump_file, "%d: ", x); | |
| 637 dump_bitmap (file, ptr->conflicts[x]); | |
| 638 } | |
| 639 } | |
| 640 | |
| 641 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
642 /* This structure is used to efficiently record the current status of live |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
643 SSA_NAMES when building a conflict graph. |
| 0 | 644 LIVE_BASE_VAR has a bit set for each base variable which has at least one |
| 645 ssa version live. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
646 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
647 index, and is used to track what partitions of each base variable are |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
648 live. This makes it easy to add conflicts between just live partitions |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
649 with the same base variable. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
650 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is |
| 0 | 651 marked as being live. This delays clearing of these bitmaps until |
| 652 they are actually needed again. */ | |
| 653 | |
| 654 typedef struct live_track_d | |
| 655 { | |
| 656 bitmap live_base_var; /* Indicates if a basevar is live. */ | |
| 657 bitmap *live_base_partitions; /* Live partitions for each basevar. */ | |
| 658 var_map map; /* Var_map being used for partition mapping. */ | |
| 659 } * live_track_p; | |
| 660 | |
| 661 | |
| 662 /* This routine will create a new live track structure based on the partitions | |
| 663 in MAP. */ | |
| 664 | |
| 665 static live_track_p | |
| 666 new_live_track (var_map map) | |
| 667 { | |
| 668 live_track_p ptr; | |
| 669 int lim, x; | |
| 670 | |
| 671 /* Make sure there is a partition view in place. */ | |
| 672 gcc_assert (map->partition_to_base_index != NULL); | |
| 673 | |
| 674 ptr = (live_track_p) xmalloc (sizeof (struct live_track_d)); | |
| 675 ptr->map = map; | |
| 676 lim = num_basevars (map); | |
| 677 ptr->live_base_partitions = (bitmap *) xmalloc(sizeof (bitmap *) * lim); | |
| 678 ptr->live_base_var = BITMAP_ALLOC (NULL); | |
| 679 for (x = 0; x < lim; x++) | |
| 680 ptr->live_base_partitions[x] = BITMAP_ALLOC (NULL); | |
| 681 return ptr; | |
| 682 } | |
| 683 | |
| 684 | |
| 685 /* This routine will free the memory associated with PTR. */ | |
| 686 | |
| 687 static void | |
| 688 delete_live_track (live_track_p ptr) | |
| 689 { | |
| 690 int x, lim; | |
| 691 | |
| 692 lim = num_basevars (ptr->map); | |
| 693 for (x = 0; x < lim; x++) | |
| 694 BITMAP_FREE (ptr->live_base_partitions[x]); | |
| 695 BITMAP_FREE (ptr->live_base_var); | |
| 696 free (ptr->live_base_partitions); | |
| 697 free (ptr); | |
| 698 } | |
| 699 | |
| 700 | |
| 701 /* This function will remove PARTITION from the live list in PTR. */ | |
| 702 | |
| 703 static inline void | |
| 704 live_track_remove_partition (live_track_p ptr, int partition) | |
| 705 { | |
| 706 int root; | |
| 707 | |
| 708 root = basevar_index (ptr->map, partition); | |
| 709 bitmap_clear_bit (ptr->live_base_partitions[root], partition); | |
| 710 /* If the element list is empty, make the base variable not live either. */ | |
| 711 if (bitmap_empty_p (ptr->live_base_partitions[root])) | |
| 712 bitmap_clear_bit (ptr->live_base_var, root); | |
| 713 } | |
| 714 | |
| 715 | |
| 716 /* This function will adds PARTITION to the live list in PTR. */ | |
| 717 | |
| 718 static inline void | |
| 719 live_track_add_partition (live_track_p ptr, int partition) | |
| 720 { | |
| 721 int root; | |
| 722 | |
| 723 root = basevar_index (ptr->map, partition); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
724 /* If this base var wasn't live before, it is now. Clear the element list |
| 0 | 725 since it was delayed until needed. */ |
| 726 if (!bitmap_bit_p (ptr->live_base_var, root)) | |
| 727 { | |
| 728 bitmap_set_bit (ptr->live_base_var, root); | |
| 729 bitmap_clear (ptr->live_base_partitions[root]); | |
| 730 } | |
| 731 bitmap_set_bit (ptr->live_base_partitions[root], partition); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
732 |
| 0 | 733 } |
| 734 | |
| 735 | |
| 736 /* Clear the live bit for VAR in PTR. */ | |
| 737 | |
| 738 static inline void | |
| 739 live_track_clear_var (live_track_p ptr, tree var) | |
| 740 { | |
| 741 int p; | |
| 742 | |
| 743 p = var_to_partition (ptr->map, var); | |
| 744 if (p != NO_PARTITION) | |
| 745 live_track_remove_partition (ptr, p); | |
| 746 } | |
| 747 | |
| 748 | |
| 749 /* Return TRUE if VAR is live in PTR. */ | |
| 750 | |
| 751 static inline bool | |
| 752 live_track_live_p (live_track_p ptr, tree var) | |
| 753 { | |
| 754 int p, root; | |
| 755 | |
| 756 p = var_to_partition (ptr->map, var); | |
| 757 if (p != NO_PARTITION) | |
| 758 { | |
| 759 root = basevar_index (ptr->map, p); | |
| 760 if (bitmap_bit_p (ptr->live_base_var, root)) | |
| 761 return bitmap_bit_p (ptr->live_base_partitions[root], p); | |
| 762 } | |
| 763 return false; | |
| 764 } | |
| 765 | |
| 766 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
767 /* This routine will add USE to PTR. USE will be marked as live in both the |
| 0 | 768 ssa live map and the live bitmap for the root of USE. */ |
| 769 | |
| 770 static inline void | |
| 771 live_track_process_use (live_track_p ptr, tree use) | |
| 772 { | |
| 773 int p; | |
| 774 | |
| 775 p = var_to_partition (ptr->map, use); | |
| 776 if (p == NO_PARTITION) | |
| 777 return; | |
| 778 | |
| 779 /* Mark as live in the appropriate live list. */ | |
| 780 live_track_add_partition (ptr, p); | |
| 781 } | |
| 782 | |
| 783 | |
| 784 /* This routine will process a DEF in PTR. DEF will be removed from the live | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
785 lists, and if there are any other live partitions with the same base |
| 0 | 786 variable, conflicts will be added to GRAPH. */ |
| 787 | |
| 788 static inline void | |
| 789 live_track_process_def (live_track_p ptr, tree def, ssa_conflicts_p graph) | |
| 790 { | |
| 791 int p, root; | |
| 792 bitmap b; | |
| 793 unsigned x; | |
| 794 bitmap_iterator bi; | |
| 795 | |
| 796 p = var_to_partition (ptr->map, def); | |
| 797 if (p == NO_PARTITION) | |
| 798 return; | |
| 799 | |
| 800 /* Clear the liveness bit. */ | |
| 801 live_track_remove_partition (ptr, p); | |
| 802 | |
| 803 /* If the bitmap isn't empty now, conflicts need to be added. */ | |
| 804 root = basevar_index (ptr->map, p); | |
| 805 if (bitmap_bit_p (ptr->live_base_var, root)) | |
| 806 { | |
| 807 b = ptr->live_base_partitions[root]; | |
| 808 EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi) | |
| 809 ssa_conflicts_add (graph, p, x); | |
| 810 } | |
| 811 } | |
| 812 | |
| 813 | |
| 814 /* Initialize PTR with the partitions set in INIT. */ | |
| 815 | |
| 816 static inline void | |
| 817 live_track_init (live_track_p ptr, bitmap init) | |
| 818 { | |
| 819 unsigned p; | |
| 820 bitmap_iterator bi; | |
| 821 | |
| 822 /* Mark all live on exit partitions. */ | |
| 823 EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi) | |
| 824 live_track_add_partition (ptr, p); | |
| 825 } | |
| 826 | |
| 827 | |
| 828 /* This routine will clear all live partitions in PTR. */ | |
| 829 | |
| 830 static inline void | |
| 831 live_track_clear_base_vars (live_track_p ptr) | |
| 832 { | |
| 833 /* Simply clear the live base list. Anything marked as live in the element | |
| 834 lists will be cleared later if/when the base variable ever comes alive | |
| 835 again. */ | |
| 836 bitmap_clear (ptr->live_base_var); | |
| 837 } | |
| 838 | |
| 839 | |
| 840 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
841 partition view of the var_map liveinfo is based on get entries in the |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
842 conflict graph. Only conflicts between ssa_name partitions with the same |
| 0 | 843 base variable are added. */ |
| 844 | |
| 845 static ssa_conflicts_p | |
| 846 build_ssa_conflict_graph (tree_live_info_p liveinfo) | |
| 847 { | |
| 848 ssa_conflicts_p graph; | |
| 849 var_map map; | |
| 850 basic_block bb; | |
| 851 ssa_op_iter iter; | |
| 852 live_track_p live; | |
| 853 | |
| 854 map = live_var_map (liveinfo); | |
| 855 graph = ssa_conflicts_new (num_var_partitions (map)); | |
| 856 | |
| 857 live = new_live_track (map); | |
| 858 | |
| 859 FOR_EACH_BB (bb) | |
| 860 { | |
| 861 gimple_stmt_iterator gsi; | |
| 862 | |
| 863 /* Start with live on exit temporaries. */ | |
| 864 live_track_init (live, live_on_exit (liveinfo, bb)); | |
| 865 | |
| 866 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) | |
| 867 { | |
| 868 tree var; | |
| 869 gimple stmt = gsi_stmt (gsi); | |
| 870 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
871 /* A copy between 2 partitions does not introduce an interference |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
872 by itself. If they did, you would never be able to coalesce |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
873 two things which are copied. If the two variables really do |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
874 conflict, they will conflict elsewhere in the program. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
875 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
876 This is handled by simply removing the SRC of the copy from the |
| 0 | 877 live list, and processing the stmt normally. */ |
| 878 if (is_gimple_assign (stmt)) | |
| 879 { | |
| 880 tree lhs = gimple_assign_lhs (stmt); | |
| 881 tree rhs1 = gimple_assign_rhs1 (stmt); | |
| 882 if (gimple_assign_copy_p (stmt) | |
| 883 && TREE_CODE (lhs) == SSA_NAME | |
| 884 && TREE_CODE (rhs1) == SSA_NAME) | |
| 885 live_track_clear_var (live, rhs1); | |
| 886 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
887 else if (is_gimple_debug (stmt)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
888 continue; |
| 0 | 889 |
| 890 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF) | |
| 891 live_track_process_def (live, var, graph); | |
| 892 | |
| 893 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) | |
| 894 live_track_process_use (live, var); | |
| 895 } | |
| 896 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
897 /* If result of a PHI is unused, looping over the statements will not |
| 0 | 898 record any conflicts since the def was never live. Since the PHI node |
| 899 is going to be translated out of SSA form, it will insert a copy. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
900 There must be a conflict recorded between the result of the PHI and |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
901 any variables that are live. Otherwise the out-of-ssa translation |
| 0 | 902 may create incorrect code. */ |
| 903 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 904 { | |
| 905 gimple phi = gsi_stmt (gsi); | |
| 906 tree result = PHI_RESULT (phi); | |
| 907 if (live_track_live_p (live, result)) | |
| 908 live_track_process_def (live, result, graph); | |
| 909 } | |
| 910 | |
| 911 live_track_clear_base_vars (live); | |
| 912 } | |
| 913 | |
| 914 delete_live_track (live); | |
| 915 return graph; | |
| 916 } | |
| 917 | |
| 918 | |
| 919 /* Shortcut routine to print messages to file F of the form: | |
| 920 "STR1 EXPR1 STR2 EXPR2 STR3." */ | |
| 921 | |
| 922 static inline void | |
| 923 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2, | |
| 924 tree expr2, const char *str3) | |
| 925 { | |
| 926 fprintf (f, "%s", str1); | |
| 927 print_generic_expr (f, expr1, TDF_SLIM); | |
| 928 fprintf (f, "%s", str2); | |
| 929 print_generic_expr (f, expr2, TDF_SLIM); | |
| 930 fprintf (f, "%s", str3); | |
| 931 } | |
| 932 | |
| 933 | |
| 934 /* Called if a coalesce across and abnormal edge cannot be performed. PHI is | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
935 the phi node at fault, I is the argument index at fault. A message is |
| 0 | 936 printed and compilation is then terminated. */ |
| 937 | |
| 938 static inline void | |
| 939 abnormal_corrupt (gimple phi, int i) | |
| 940 { | |
| 941 edge e = gimple_phi_arg_edge (phi, i); | |
| 942 tree res = gimple_phi_result (phi); | |
| 943 tree arg = gimple_phi_arg_def (phi, i); | |
| 944 | |
| 945 fprintf (stderr, " Corrupt SSA across abnormal edge BB%d->BB%d\n", | |
| 946 e->src->index, e->dest->index); | |
| 947 fprintf (stderr, "Argument %d (", i); | |
| 948 print_generic_expr (stderr, arg, TDF_SLIM); | |
| 949 if (TREE_CODE (arg) != SSA_NAME) | |
| 950 fprintf (stderr, ") is not an SSA_NAME.\n"); | |
| 951 else | |
| 952 { | |
| 953 gcc_assert (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg)); | |
| 954 fprintf (stderr, ") does not have the same base variable as the result "); | |
| 955 print_generic_stmt (stderr, res, TDF_SLIM); | |
| 956 } | |
| 957 | |
| 958 internal_error ("SSA corruption"); | |
| 959 } | |
| 960 | |
| 961 | |
| 962 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */ | |
| 963 | |
| 964 static inline void | |
| 965 fail_abnormal_edge_coalesce (int x, int y) | |
| 966 { | |
| 967 fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y); | |
| 968 fprintf (stderr, " which are marked as MUST COALESCE.\n"); | |
| 969 print_generic_expr (stderr, ssa_name (x), TDF_SLIM); | |
| 970 fprintf (stderr, " and "); | |
| 971 print_generic_stmt (stderr, ssa_name (y), TDF_SLIM); | |
| 972 | |
| 973 internal_error ("SSA corruption"); | |
| 974 } | |
| 975 | |
| 976 | |
| 977 /* This function creates a var_map for the current function as well as creating | |
| 978 a coalesce list for use later in the out of ssa process. */ | |
| 979 | |
| 980 static var_map | |
| 981 create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy) | |
| 982 { | |
| 983 gimple_stmt_iterator gsi; | |
| 984 basic_block bb; | |
| 985 tree var; | |
| 986 gimple stmt; | |
| 987 tree first; | |
| 988 var_map map; | |
| 989 ssa_op_iter iter; | |
| 990 int v1, v2, cost; | |
| 991 unsigned i; | |
| 992 | |
| 993 #ifdef ENABLE_CHECKING | |
| 994 bitmap used_in_real_ops; | |
| 995 bitmap used_in_virtual_ops; | |
| 996 | |
| 997 used_in_real_ops = BITMAP_ALLOC (NULL); | |
| 998 used_in_virtual_ops = BITMAP_ALLOC (NULL); | |
| 999 #endif | |
| 1000 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1001 map = init_var_map (num_ssa_names); |
| 0 | 1002 |
| 1003 FOR_EACH_BB (bb) | |
| 1004 { | |
| 1005 tree arg; | |
| 1006 | |
| 1007 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 1008 { | |
| 1009 gimple phi = gsi_stmt (gsi); | |
| 1010 size_t i; | |
| 1011 int ver; | |
| 1012 tree res; | |
| 1013 bool saw_copy = false; | |
| 1014 | |
| 1015 res = gimple_phi_result (phi); | |
| 1016 ver = SSA_NAME_VERSION (res); | |
| 1017 register_ssa_partition (map, res); | |
| 1018 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1019 /* Register ssa_names and coalesces between the args and the result |
| 0 | 1020 of all PHI. */ |
| 1021 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
| 1022 { | |
| 1023 edge e = gimple_phi_arg_edge (phi, i); | |
| 1024 arg = PHI_ARG_DEF (phi, i); | |
| 1025 if (TREE_CODE (arg) == SSA_NAME) | |
| 1026 register_ssa_partition (map, arg); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1027 if (TREE_CODE (arg) == SSA_NAME |
| 0 | 1028 && SSA_NAME_VAR (arg) == SSA_NAME_VAR (res)) |
| 1029 { | |
| 1030 saw_copy = true; | |
| 1031 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg)); | |
| 1032 if ((e->flags & EDGE_ABNORMAL) == 0) | |
| 1033 { | |
| 1034 int cost = coalesce_cost_edge (e); | |
| 1035 if (cost == 1 && has_single_use (arg)) | |
| 1036 add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg)); | |
| 1037 else | |
| 1038 add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost); | |
| 1039 } | |
| 1040 } | |
| 1041 else | |
| 1042 if (e->flags & EDGE_ABNORMAL) | |
| 1043 abnormal_corrupt (phi, i); | |
| 1044 } | |
| 1045 if (saw_copy) | |
| 1046 bitmap_set_bit (used_in_copy, ver); | |
| 1047 } | |
| 1048 | |
| 1049 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 1050 { | |
| 1051 stmt = gsi_stmt (gsi); | |
| 1052 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1053 if (is_gimple_debug (stmt)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1054 continue; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1055 |
| 0 | 1056 /* Register USE and DEF operands in each statement. */ |
| 1057 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE)) | |
| 1058 register_ssa_partition (map, var); | |
| 1059 | |
| 1060 /* Check for copy coalesces. */ | |
| 1061 switch (gimple_code (stmt)) | |
| 1062 { | |
| 1063 case GIMPLE_ASSIGN: | |
| 1064 { | |
| 1065 tree lhs = gimple_assign_lhs (stmt); | |
| 1066 tree rhs1 = gimple_assign_rhs1 (stmt); | |
| 1067 | |
| 1068 if (gimple_assign_copy_p (stmt) | |
| 1069 && TREE_CODE (lhs) == SSA_NAME | |
| 1070 && TREE_CODE (rhs1) == SSA_NAME | |
| 1071 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs1)) | |
| 1072 { | |
| 1073 v1 = SSA_NAME_VERSION (lhs); | |
| 1074 v2 = SSA_NAME_VERSION (rhs1); | |
| 1075 cost = coalesce_cost_bb (bb); | |
| 1076 add_coalesce (cl, v1, v2, cost); | |
| 1077 bitmap_set_bit (used_in_copy, v1); | |
| 1078 bitmap_set_bit (used_in_copy, v2); | |
| 1079 } | |
| 1080 } | |
| 1081 break; | |
| 1082 | |
| 1083 case GIMPLE_ASM: | |
| 1084 { | |
| 1085 unsigned long noutputs, i; | |
| 1086 unsigned long ninputs; | |
| 1087 tree *outputs, link; | |
| 1088 noutputs = gimple_asm_noutputs (stmt); | |
| 1089 ninputs = gimple_asm_ninputs (stmt); | |
| 1090 outputs = (tree *) alloca (noutputs * sizeof (tree)); | |
| 1091 for (i = 0; i < noutputs; ++i) { | |
| 1092 link = gimple_asm_output_op (stmt, i); | |
| 1093 outputs[i] = TREE_VALUE (link); | |
| 1094 } | |
| 1095 | |
| 1096 for (i = 0; i < ninputs; ++i) | |
| 1097 { | |
| 1098 const char *constraint; | |
| 1099 tree input; | |
| 1100 char *end; | |
| 1101 unsigned long match; | |
| 1102 | |
| 1103 link = gimple_asm_input_op (stmt, i); | |
| 1104 constraint | |
| 1105 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); | |
| 1106 input = TREE_VALUE (link); | |
| 1107 | |
| 1108 if (TREE_CODE (input) != SSA_NAME) | |
| 1109 continue; | |
| 1110 | |
| 1111 match = strtoul (constraint, &end, 10); | |
| 1112 if (match >= noutputs || end == constraint) | |
| 1113 continue; | |
| 1114 | |
| 1115 if (TREE_CODE (outputs[match]) != SSA_NAME) | |
| 1116 continue; | |
| 1117 | |
| 1118 v1 = SSA_NAME_VERSION (outputs[match]); | |
| 1119 v2 = SSA_NAME_VERSION (input); | |
| 1120 | |
| 1121 if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input)) | |
| 1122 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1123 cost = coalesce_cost (REG_BR_PROB_BASE, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1124 optimize_bb_for_size_p (bb)); |
| 0 | 1125 add_coalesce (cl, v1, v2, cost); |
| 1126 bitmap_set_bit (used_in_copy, v1); | |
| 1127 bitmap_set_bit (used_in_copy, v2); | |
| 1128 } | |
| 1129 } | |
| 1130 break; | |
| 1131 } | |
| 1132 | |
| 1133 default: | |
| 1134 break; | |
| 1135 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1136 |
| 0 | 1137 #ifdef ENABLE_CHECKING |
| 1138 /* Mark real uses and defs. */ | |
| 1139 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE)) | |
| 1140 bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var))); | |
| 1141 | |
| 1142 /* Validate that virtual ops don't get used in funny ways. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1143 if (gimple_vuse (stmt)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1144 bitmap_set_bit (used_in_virtual_ops, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1145 DECL_UID (SSA_NAME_VAR (gimple_vuse (stmt)))); |
| 0 | 1146 #endif /* ENABLE_CHECKING */ |
| 1147 } | |
| 1148 } | |
| 1149 | |
| 1150 /* Now process result decls and live on entry variables for entry into | |
| 1151 the coalesce list. */ | |
| 1152 first = NULL_TREE; | |
| 1153 for (i = 1; i < num_ssa_names; i++) | |
| 1154 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1155 var = ssa_name (i); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1156 if (var != NULL_TREE && is_gimple_reg (var)) |
| 0 | 1157 { |
| 1158 /* Add coalesces between all the result decls. */ | |
| 1159 if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL) | |
| 1160 { | |
| 1161 if (first == NULL_TREE) | |
| 1162 first = var; | |
| 1163 else | |
| 1164 { | |
| 1165 gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first)); | |
| 1166 v1 = SSA_NAME_VERSION (first); | |
| 1167 v2 = SSA_NAME_VERSION (var); | |
| 1168 bitmap_set_bit (used_in_copy, v1); | |
| 1169 bitmap_set_bit (used_in_copy, v2); | |
| 1170 cost = coalesce_cost_bb (EXIT_BLOCK_PTR); | |
| 1171 add_coalesce (cl, v1, v2, cost); | |
| 1172 } | |
| 1173 } | |
| 1174 /* Mark any default_def variables as being in the coalesce list | |
| 1175 since they will have to be coalesced with the base variable. If | |
| 1176 not marked as present, they won't be in the coalesce view. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1177 if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1178 && !has_zero_uses (var)) |
| 0 | 1179 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var)); |
| 1180 } | |
| 1181 } | |
| 1182 | |
| 1183 #if defined ENABLE_CHECKING | |
| 1184 { | |
| 1185 unsigned i; | |
| 1186 bitmap both = BITMAP_ALLOC (NULL); | |
| 1187 bitmap_and (both, used_in_real_ops, used_in_virtual_ops); | |
| 1188 if (!bitmap_empty_p (both)) | |
| 1189 { | |
| 1190 bitmap_iterator bi; | |
| 1191 | |
| 1192 EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi) | |
| 1193 fprintf (stderr, "Variable %s used in real and virtual operands\n", | |
| 1194 get_name (referenced_var (i))); | |
| 1195 internal_error ("SSA corruption"); | |
| 1196 } | |
| 1197 | |
| 1198 BITMAP_FREE (used_in_real_ops); | |
| 1199 BITMAP_FREE (used_in_virtual_ops); | |
| 1200 BITMAP_FREE (both); | |
| 1201 } | |
| 1202 #endif | |
| 1203 | |
| 1204 return map; | |
| 1205 } | |
| 1206 | |
| 1207 | |
| 1208 /* Attempt to coalesce ssa versions X and Y together using the partition | |
| 1209 mapping in MAP and checking conflicts in GRAPH. Output any debug info to | |
| 1210 DEBUG, if it is nun-NULL. */ | |
| 1211 | |
| 1212 static inline bool | |
| 1213 attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y, | |
| 1214 FILE *debug) | |
| 1215 { | |
| 1216 int z; | |
| 1217 tree var1, var2; | |
| 1218 int p1, p2; | |
| 1219 | |
| 1220 p1 = var_to_partition (map, ssa_name (x)); | |
| 1221 p2 = var_to_partition (map, ssa_name (y)); | |
| 1222 | |
| 1223 if (debug) | |
| 1224 { | |
| 1225 fprintf (debug, "(%d)", x); | |
| 1226 print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM); | |
| 1227 fprintf (debug, " & (%d)", y); | |
| 1228 print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM); | |
| 1229 } | |
| 1230 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1231 if (p1 == p2) |
| 0 | 1232 { |
| 1233 if (debug) | |
| 1234 fprintf (debug, ": Already Coalesced.\n"); | |
| 1235 return true; | |
| 1236 } | |
| 1237 | |
| 1238 if (debug) | |
| 1239 fprintf (debug, " [map: %d, %d] ", p1, p2); | |
| 1240 | |
| 1241 | |
| 1242 if (!ssa_conflicts_test_p (graph, p1, p2)) | |
| 1243 { | |
| 1244 var1 = partition_to_var (map, p1); | |
| 1245 var2 = partition_to_var (map, p2); | |
| 1246 z = var_union (map, var1, var2); | |
| 1247 if (z == NO_PARTITION) | |
| 1248 { | |
| 1249 if (debug) | |
| 1250 fprintf (debug, ": Unable to perform partition union.\n"); | |
| 1251 return false; | |
| 1252 } | |
| 1253 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1254 /* z is the new combined partition. Remove the other partition from |
| 0 | 1255 the list, and merge the conflicts. */ |
| 1256 if (z == p1) | |
| 1257 ssa_conflicts_merge (graph, p1, p2); | |
| 1258 else | |
| 1259 ssa_conflicts_merge (graph, p2, p1); | |
| 1260 | |
| 1261 if (debug) | |
| 1262 fprintf (debug, ": Success -> %d\n", z); | |
| 1263 return true; | |
| 1264 } | |
| 1265 | |
| 1266 if (debug) | |
| 1267 fprintf (debug, ": Fail due to conflict\n"); | |
| 1268 | |
| 1269 return false; | |
| 1270 } | |
| 1271 | |
| 1272 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1273 /* Attempt to Coalesce partitions in MAP which occur in the list CL using |
| 0 | 1274 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */ |
| 1275 | |
| 1276 static void | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1277 coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl, |
| 0 | 1278 FILE *debug) |
| 1279 { | |
| 1280 int x = 0, y = 0; | |
| 1281 tree var1, var2; | |
| 1282 int cost; | |
| 1283 basic_block bb; | |
| 1284 edge e; | |
| 1285 edge_iterator ei; | |
| 1286 | |
| 1287 /* First, coalesce all the copies across abnormal edges. These are not placed | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1288 in the coalesce list because they do not need to be sorted, and simply |
| 0 | 1289 consume extra memory/compilation time in large programs. */ |
| 1290 | |
| 1291 FOR_EACH_BB (bb) | |
| 1292 { | |
| 1293 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 1294 if (e->flags & EDGE_ABNORMAL) | |
| 1295 { | |
| 1296 gimple_stmt_iterator gsi; | |
| 1297 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); | |
| 1298 gsi_next (&gsi)) | |
| 1299 { | |
| 1300 gimple phi = gsi_stmt (gsi); | |
| 1301 tree res = PHI_RESULT (phi); | |
| 1302 tree arg = PHI_ARG_DEF (phi, e->dest_idx); | |
| 1303 int v1 = SSA_NAME_VERSION (res); | |
| 1304 int v2 = SSA_NAME_VERSION (arg); | |
| 1305 | |
| 1306 if (SSA_NAME_VAR (arg) != SSA_NAME_VAR (res)) | |
| 1307 abnormal_corrupt (phi, e->dest_idx); | |
| 1308 | |
| 1309 if (debug) | |
| 1310 fprintf (debug, "Abnormal coalesce: "); | |
| 1311 | |
| 1312 if (!attempt_coalesce (map, graph, v1, v2, debug)) | |
| 1313 fail_abnormal_edge_coalesce (v1, v2); | |
| 1314 } | |
| 1315 } | |
| 1316 } | |
| 1317 | |
| 1318 /* Now process the items in the coalesce list. */ | |
| 1319 | |
| 1320 while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE) | |
| 1321 { | |
| 1322 var1 = ssa_name (x); | |
| 1323 var2 = ssa_name (y); | |
| 1324 | |
| 1325 /* Assert the coalesces have the same base variable. */ | |
| 1326 gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2)); | |
| 1327 | |
| 1328 if (debug) | |
| 1329 fprintf (debug, "Coalesce list: "); | |
| 1330 attempt_coalesce (map, graph, x, y, debug); | |
| 1331 } | |
| 1332 } | |
| 1333 | |
| 1334 /* Returns a hash code for P. */ | |
| 1335 | |
| 1336 static hashval_t | |
| 1337 hash_ssa_name_by_var (const void *p) | |
| 1338 { | |
| 1339 const_tree n = (const_tree) p; | |
| 1340 return (hashval_t) htab_hash_pointer (SSA_NAME_VAR (n)); | |
| 1341 } | |
| 1342 | |
| 1343 /* Returns nonzero if P1 and P2 are equal. */ | |
| 1344 | |
| 1345 static int | |
| 1346 eq_ssa_name_by_var (const void *p1, const void *p2) | |
| 1347 { | |
| 1348 const_tree n1 = (const_tree) p1; | |
| 1349 const_tree n2 = (const_tree) p2; | |
| 1350 return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2); | |
| 1351 } | |
| 1352 | |
| 1353 /* Reduce the number of copies by coalescing variables in the function. Return | |
| 1354 a partition map with the resulting coalesces. */ | |
| 1355 | |
| 1356 extern var_map | |
| 1357 coalesce_ssa_name (void) | |
| 1358 { | |
| 1359 tree_live_info_p liveinfo; | |
| 1360 ssa_conflicts_p graph; | |
| 1361 coalesce_list_p cl; | |
| 1362 bitmap used_in_copies = BITMAP_ALLOC (NULL); | |
| 1363 var_map map; | |
| 1364 unsigned int i; | |
| 1365 static htab_t ssa_name_hash; | |
| 1366 | |
| 1367 cl = create_coalesce_list (); | |
| 1368 map = create_outofssa_var_map (cl, used_in_copies); | |
| 1369 | |
| 1370 /* We need to coalesce all names originating same SSA_NAME_VAR | |
| 1371 so debug info remains undisturbed. */ | |
| 1372 if (!optimize) | |
| 1373 { | |
| 1374 ssa_name_hash = htab_create (10, hash_ssa_name_by_var, | |
| 1375 eq_ssa_name_by_var, NULL); | |
| 1376 for (i = 1; i < num_ssa_names; i++) | |
| 1377 { | |
| 1378 tree a = ssa_name (i); | |
| 1379 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1380 if (a |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1381 && SSA_NAME_VAR (a) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1382 && !DECL_ARTIFICIAL (SSA_NAME_VAR (a)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1383 && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a))) |
| 0 | 1384 { |
| 1385 tree *slot = (tree *) htab_find_slot (ssa_name_hash, a, INSERT); | |
| 1386 | |
| 1387 if (!*slot) | |
| 1388 *slot = a; | |
| 1389 else | |
| 1390 { | |
| 1391 add_coalesce (cl, SSA_NAME_VERSION (a), SSA_NAME_VERSION (*slot), | |
| 1392 MUST_COALESCE_COST - 1); | |
| 1393 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a)); | |
| 1394 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot)); | |
| 1395 } | |
| 1396 } | |
| 1397 } | |
| 1398 htab_delete (ssa_name_hash); | |
| 1399 } | |
| 1400 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1401 dump_var_map (dump_file, map); | |
| 1402 | |
| 1403 /* Don't calculate live ranges for variables not in the coalesce list. */ | |
| 1404 partition_view_bitmap (map, used_in_copies, true); | |
| 1405 BITMAP_FREE (used_in_copies); | |
| 1406 | |
| 1407 if (num_var_partitions (map) < 1) | |
| 1408 { | |
| 1409 delete_coalesce_list (cl); | |
| 1410 return map; | |
| 1411 } | |
| 1412 | |
| 1413 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1414 dump_var_map (dump_file, map); | |
| 1415 | |
| 1416 liveinfo = calculate_live_ranges (map); | |
| 1417 | |
| 1418 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1419 dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY); | |
| 1420 | |
| 1421 /* Build a conflict graph. */ | |
| 1422 graph = build_ssa_conflict_graph (liveinfo); | |
| 1423 delete_tree_live_info (liveinfo); | |
| 1424 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1425 ssa_conflicts_dump (dump_file, graph); | |
| 1426 | |
| 1427 sort_coalesce_list (cl); | |
| 1428 | |
| 1429 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1430 { | |
| 1431 fprintf (dump_file, "\nAfter sorting:\n"); | |
| 1432 dump_coalesce_list (dump_file, cl); | |
| 1433 } | |
| 1434 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1435 /* First, coalesce all live on entry variables to their base variable. |
| 0 | 1436 This will ensure the first use is coming from the correct location. */ |
| 1437 | |
| 1438 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1439 dump_var_map (dump_file, map); | |
| 1440 | |
| 1441 /* Now coalesce everything in the list. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1442 coalesce_partitions (map, graph, cl, |
| 0 | 1443 ((dump_flags & TDF_DETAILS) ? dump_file |
| 1444 : NULL)); | |
| 1445 | |
| 1446 delete_coalesce_list (cl); | |
| 1447 ssa_conflicts_delete (graph); | |
| 1448 | |
| 1449 return map; | |
| 1450 } |