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