Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-predcom.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 24 May 2010 12:47:05 +0900 |
| parents | 77e2b8dfacca |
| children | f6334be47118 |
| rev | line source |
|---|---|
| 0 | 1 /* Predictive commoning. |
|
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) 2005, 2007, 2008, 2009, 2010 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3 Free Software Foundation, Inc. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
4 |
| 0 | 5 This file is part of GCC. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
6 |
| 0 | 7 GCC is free software; you can redistribute it and/or modify it |
| 8 under the terms of the GNU General Public License as published by the | |
| 9 Free Software Foundation; either version 3, or (at your option) any | |
| 10 later version. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
11 |
| 0 | 12 GCC is distributed in the hope that it will be useful, but WITHOUT |
| 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 15 for more details. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
16 |
| 0 | 17 You should have received a copy of the GNU General Public License |
| 18 along with GCC; see the file COPYING3. If not see | |
| 19 <http://www.gnu.org/licenses/>. */ | |
| 20 | |
| 21 /* This file implements the predictive commoning optimization. Predictive | |
| 22 commoning can be viewed as CSE around a loop, and with some improvements, | |
| 23 as generalized strength reduction-- i.e., reusing values computed in | |
| 24 earlier iterations of a loop in the later ones. So far, the pass only | |
| 25 handles the most useful case, that is, reusing values of memory references. | |
| 26 If you think this is all just a special case of PRE, you are sort of right; | |
| 27 however, concentrating on loops is simpler, and makes it possible to | |
| 28 incorporate data dependence analysis to detect the opportunities, perform | |
| 29 loop unrolling to avoid copies together with renaming immediately, | |
| 30 and if needed, we could also take register pressure into account. | |
| 31 | |
| 32 Let us demonstrate what is done on an example: | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
33 |
| 0 | 34 for (i = 0; i < 100; i++) |
| 35 { | |
| 36 a[i+2] = a[i] + a[i+1]; | |
| 37 b[10] = b[10] + i; | |
| 38 c[i] = c[99 - i]; | |
| 39 d[i] = d[i + 1]; | |
| 40 } | |
| 41 | |
| 42 1) We find data references in the loop, and split them to mutually | |
| 43 independent groups (i.e., we find components of a data dependence | |
| 44 graph). We ignore read-read dependences whose distance is not constant. | |
| 45 (TODO -- we could also ignore antidependences). In this example, we | |
| 46 find the following groups: | |
| 47 | |
| 48 a[i]{read}, a[i+1]{read}, a[i+2]{write} | |
| 49 b[10]{read}, b[10]{write} | |
| 50 c[99 - i]{read}, c[i]{write} | |
| 51 d[i + 1]{read}, d[i]{write} | |
| 52 | |
| 53 2) Inside each of the group, we verify several conditions: | |
| 54 a) all the references must differ in indices only, and the indices | |
| 55 must all have the same step | |
| 56 b) the references must dominate loop latch (and thus, they must be | |
| 57 ordered by dominance relation). | |
| 58 c) the distance of the indices must be a small multiple of the step | |
| 59 We are then able to compute the difference of the references (# of | |
| 60 iterations before they point to the same place as the first of them). | |
| 61 Also, in case there are writes in the loop, we split the groups into | |
| 62 chains whose head is the write whose values are used by the reads in | |
| 63 the same chain. The chains are then processed independently, | |
| 64 making the further transformations simpler. Also, the shorter chains | |
| 65 need the same number of registers, but may require lower unrolling | |
| 66 factor in order to get rid of the copies on the loop latch. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
67 |
| 0 | 68 In our example, we get the following chains (the chain for c is invalid). |
| 69 | |
| 70 a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2} | |
| 71 b[10]{read,+0}, b[10]{write,+0} | |
| 72 d[i + 1]{read,+0}, d[i]{write,+1} | |
| 73 | |
| 74 3) For each read, we determine the read or write whose value it reuses, | |
| 75 together with the distance of this reuse. I.e. we take the last | |
| 76 reference before it with distance 0, or the last of the references | |
| 77 with the smallest positive distance to the read. Then, we remove | |
| 78 the references that are not used in any of these chains, discard the | |
| 79 empty groups, and propagate all the links so that they point to the | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
80 single root reference of the chain (adjusting their distance |
| 0 | 81 appropriately). Some extra care needs to be taken for references with |
| 82 step 0. In our example (the numbers indicate the distance of the | |
| 83 reuse), | |
| 84 | |
| 85 a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*) | |
| 86 b[10] --> (*) 1, b[10] (*) | |
| 87 | |
| 88 4) The chains are combined together if possible. If the corresponding | |
| 89 elements of two chains are always combined together with the same | |
| 90 operator, we remember just the result of this combination, instead | |
| 91 of remembering the values separately. We may need to perform | |
| 92 reassociation to enable combining, for example | |
| 93 | |
| 94 e[i] + f[i+1] + e[i+1] + f[i] | |
| 95 | |
| 96 can be reassociated as | |
| 97 | |
| 98 (e[i] + f[i]) + (e[i+1] + f[i+1]) | |
| 99 | |
| 100 and we can combine the chains for e and f into one chain. | |
| 101 | |
| 102 5) For each root reference (end of the chain) R, let N be maximum distance | |
| 103 of a reference reusing its value. Variables R0 upto RN are created, | |
| 104 together with phi nodes that transfer values from R1 .. RN to | |
| 105 R0 .. R(N-1). | |
| 106 Initial values are loaded to R0..R(N-1) (in case not all references | |
| 107 must necessarily be accessed and they may trap, we may fail here; | |
| 108 TODO sometimes, the loads could be guarded by a check for the number | |
| 109 of iterations). Values loaded/stored in roots are also copied to | |
| 110 RN. Other reads are replaced with the appropriate variable Ri. | |
| 111 Everything is put to SSA form. | |
| 112 | |
| 113 As a small improvement, if R0 is dead after the root (i.e., all uses of | |
| 114 the value with the maximum distance dominate the root), we can avoid | |
| 115 creating RN and use R0 instead of it. | |
| 116 | |
| 117 In our example, we get (only the parts concerning a and b are shown): | |
| 118 for (i = 0; i < 100; i++) | |
| 119 { | |
| 120 f = phi (a[0], s); | |
| 121 s = phi (a[1], f); | |
| 122 x = phi (b[10], x); | |
| 123 | |
| 124 f = f + s; | |
| 125 a[i+2] = f; | |
| 126 x = x + i; | |
| 127 b[10] = x; | |
| 128 } | |
| 129 | |
| 130 6) Factor F for unrolling is determined as the smallest common multiple of | |
| 131 (N + 1) for each root reference (N for references for that we avoided | |
| 132 creating RN). If F and the loop is small enough, loop is unrolled F | |
| 133 times. The stores to RN (R0) in the copies of the loop body are | |
| 134 periodically replaced with R0, R1, ... (R1, R2, ...), so that they can | |
| 135 be coalesced and the copies can be eliminated. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
136 |
| 0 | 137 TODO -- copy propagation and other optimizations may change the live |
| 138 ranges of the temporary registers and prevent them from being coalesced; | |
| 139 this may increase the register pressure. | |
| 140 | |
| 141 In our case, F = 2 and the (main loop of the) result is | |
| 142 | |
| 143 for (i = 0; i < ...; i += 2) | |
| 144 { | |
| 145 f = phi (a[0], f); | |
| 146 s = phi (a[1], s); | |
| 147 x = phi (b[10], x); | |
| 148 | |
| 149 f = f + s; | |
| 150 a[i+2] = f; | |
| 151 x = x + i; | |
| 152 b[10] = x; | |
| 153 | |
| 154 s = s + f; | |
| 155 a[i+3] = s; | |
| 156 x = x + i; | |
| 157 b[10] = x; | |
| 158 } | |
| 159 | |
| 160 TODO -- stores killing other stores can be taken into account, e.g., | |
| 161 for (i = 0; i < n; i++) | |
| 162 { | |
| 163 a[i] = 1; | |
| 164 a[i+2] = 2; | |
| 165 } | |
| 166 | |
| 167 can be replaced with | |
| 168 | |
| 169 t0 = a[0]; | |
| 170 t1 = a[1]; | |
| 171 for (i = 0; i < n; i++) | |
| 172 { | |
| 173 a[i] = 1; | |
| 174 t2 = 2; | |
| 175 t0 = t1; | |
| 176 t1 = t2; | |
| 177 } | |
| 178 a[n] = t0; | |
| 179 a[n+1] = t1; | |
| 180 | |
| 181 The interesting part is that this would generalize store motion; still, since | |
| 182 sm is performed elsewhere, it does not seem that important. | |
| 183 | |
| 184 Predictive commoning can be generalized for arbitrary computations (not | |
| 185 just memory loads), and also nontrivial transfer functions (e.g., replacing | |
| 186 i * i with ii_last + 2 * i + 1), to generalize strength reduction. */ | |
| 187 | |
| 188 #include "config.h" | |
| 189 #include "system.h" | |
| 190 #include "coretypes.h" | |
| 191 #include "tm.h" | |
| 192 #include "tree.h" | |
| 193 #include "tm_p.h" | |
| 194 #include "cfgloop.h" | |
| 195 #include "tree-flow.h" | |
| 196 #include "ggc.h" | |
| 197 #include "tree-data-ref.h" | |
| 198 #include "tree-scalar-evolution.h" | |
| 199 #include "tree-chrec.h" | |
| 200 #include "params.h" | |
| 201 #include "diagnostic.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
|
202 #include "tree-pretty-print.h" |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
203 #include "gimple-pretty-print.h" |
| 0 | 204 #include "tree-pass.h" |
| 205 #include "tree-affine.h" | |
| 206 #include "tree-inline.h" | |
| 207 | |
| 208 /* The maximum number of iterations between the considered memory | |
| 209 references. */ | |
| 210 | |
| 211 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
212 |
| 0 | 213 /* Data references (or phi nodes that carry data reference values across |
| 214 loop iterations). */ | |
| 215 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
216 typedef struct dref_d |
| 0 | 217 { |
| 218 /* The reference itself. */ | |
| 219 struct data_reference *ref; | |
| 220 | |
| 221 /* The statement in that the reference appears. */ | |
| 222 gimple stmt; | |
| 223 | |
| 224 /* In case that STMT is a phi node, this field is set to the SSA name | |
| 225 defined by it in replace_phis_by_defined_names (in order to avoid | |
| 226 pointing to phi node that got reallocated in the meantime). */ | |
| 227 tree name_defined_by_phi; | |
| 228 | |
| 229 /* Distance of the reference from the root of the chain (in number of | |
| 230 iterations of the loop). */ | |
| 231 unsigned distance; | |
| 232 | |
| 233 /* Number of iterations offset from the first reference in the component. */ | |
| 234 double_int offset; | |
| 235 | |
| 236 /* Number of the reference in a component, in dominance ordering. */ | |
| 237 unsigned pos; | |
| 238 | |
| 239 /* True if the memory reference is always accessed when the loop is | |
| 240 entered. */ | |
| 241 unsigned always_accessed : 1; | |
| 242 } *dref; | |
| 243 | |
| 244 DEF_VEC_P (dref); | |
| 245 DEF_VEC_ALLOC_P (dref, heap); | |
| 246 | |
| 247 /* Type of the chain of the references. */ | |
| 248 | |
| 249 enum chain_type | |
| 250 { | |
| 251 /* The addresses of the references in the chain are constant. */ | |
| 252 CT_INVARIANT, | |
| 253 | |
| 254 /* There are only loads in the chain. */ | |
| 255 CT_LOAD, | |
| 256 | |
| 257 /* Root of the chain is store, the rest are loads. */ | |
| 258 CT_STORE_LOAD, | |
| 259 | |
| 260 /* A combination of two chains. */ | |
| 261 CT_COMBINATION | |
| 262 }; | |
| 263 | |
| 264 /* Chains of data references. */ | |
| 265 | |
| 266 typedef struct chain | |
| 267 { | |
| 268 /* Type of the chain. */ | |
| 269 enum chain_type type; | |
| 270 | |
| 271 /* For combination chains, the operator and the two chains that are | |
| 272 combined, and the type of the result. */ | |
| 273 enum tree_code op; | |
| 274 tree rslt_type; | |
| 275 struct chain *ch1, *ch2; | |
| 276 | |
| 277 /* The references in the chain. */ | |
| 278 VEC(dref,heap) *refs; | |
| 279 | |
| 280 /* The maximum distance of the reference in the chain from the root. */ | |
| 281 unsigned length; | |
| 282 | |
| 283 /* The variables used to copy the value throughout iterations. */ | |
| 284 VEC(tree,heap) *vars; | |
| 285 | |
| 286 /* Initializers for the variables. */ | |
| 287 VEC(tree,heap) *inits; | |
| 288 | |
| 289 /* True if there is a use of a variable with the maximal distance | |
| 290 that comes after the root in the loop. */ | |
| 291 unsigned has_max_use_after : 1; | |
| 292 | |
| 293 /* True if all the memory references in the chain are always accessed. */ | |
| 294 unsigned all_always_accessed : 1; | |
| 295 | |
| 296 /* True if this chain was combined together with some other chain. */ | |
| 297 unsigned combined : 1; | |
| 298 } *chain_p; | |
| 299 | |
| 300 DEF_VEC_P (chain_p); | |
| 301 DEF_VEC_ALLOC_P (chain_p, heap); | |
| 302 | |
| 303 /* Describes the knowledge about the step of the memory references in | |
| 304 the component. */ | |
| 305 | |
| 306 enum ref_step_type | |
| 307 { | |
| 308 /* The step is zero. */ | |
| 309 RS_INVARIANT, | |
| 310 | |
| 311 /* The step is nonzero. */ | |
| 312 RS_NONZERO, | |
| 313 | |
| 314 /* The step may or may not be nonzero. */ | |
| 315 RS_ANY | |
| 316 }; | |
| 317 | |
| 318 /* Components of the data dependence graph. */ | |
| 319 | |
| 320 struct component | |
| 321 { | |
| 322 /* The references in the component. */ | |
| 323 VEC(dref,heap) *refs; | |
| 324 | |
| 325 /* What we know about the step of the references in the component. */ | |
| 326 enum ref_step_type comp_step; | |
| 327 | |
| 328 /* Next component in the list. */ | |
| 329 struct component *next; | |
| 330 }; | |
| 331 | |
| 332 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */ | |
| 333 | |
| 334 static bitmap looparound_phis; | |
| 335 | |
| 336 /* Cache used by tree_to_aff_combination_expand. */ | |
| 337 | |
| 338 static struct pointer_map_t *name_expansions; | |
| 339 | |
| 340 /* Dumps data reference REF to FILE. */ | |
| 341 | |
| 342 extern void dump_dref (FILE *, dref); | |
| 343 void | |
| 344 dump_dref (FILE *file, dref ref) | |
| 345 { | |
| 346 if (ref->ref) | |
| 347 { | |
| 348 fprintf (file, " "); | |
| 349 print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM); | |
| 350 fprintf (file, " (id %u%s)\n", ref->pos, | |
| 351 DR_IS_READ (ref->ref) ? "" : ", write"); | |
| 352 | |
| 353 fprintf (file, " offset "); | |
| 354 dump_double_int (file, ref->offset, false); | |
| 355 fprintf (file, "\n"); | |
| 356 | |
| 357 fprintf (file, " distance %u\n", ref->distance); | |
| 358 } | |
| 359 else | |
| 360 { | |
| 361 if (gimple_code (ref->stmt) == GIMPLE_PHI) | |
| 362 fprintf (file, " looparound ref\n"); | |
| 363 else | |
| 364 fprintf (file, " combination ref\n"); | |
| 365 fprintf (file, " in statement "); | |
| 366 print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM); | |
| 367 fprintf (file, "\n"); | |
| 368 fprintf (file, " distance %u\n", ref->distance); | |
| 369 } | |
| 370 | |
| 371 } | |
| 372 | |
| 373 /* Dumps CHAIN to FILE. */ | |
| 374 | |
| 375 extern void dump_chain (FILE *, chain_p); | |
| 376 void | |
| 377 dump_chain (FILE *file, chain_p chain) | |
| 378 { | |
| 379 dref a; | |
| 380 const char *chain_type; | |
| 381 unsigned i; | |
| 382 tree var; | |
| 383 | |
| 384 switch (chain->type) | |
| 385 { | |
| 386 case CT_INVARIANT: | |
| 387 chain_type = "Load motion"; | |
| 388 break; | |
| 389 | |
| 390 case CT_LOAD: | |
| 391 chain_type = "Loads-only"; | |
| 392 break; | |
| 393 | |
| 394 case CT_STORE_LOAD: | |
| 395 chain_type = "Store-loads"; | |
| 396 break; | |
| 397 | |
| 398 case CT_COMBINATION: | |
| 399 chain_type = "Combination"; | |
| 400 break; | |
| 401 | |
| 402 default: | |
| 403 gcc_unreachable (); | |
| 404 } | |
| 405 | |
| 406 fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain, | |
| 407 chain->combined ? " (combined)" : ""); | |
| 408 if (chain->type != CT_INVARIANT) | |
| 409 fprintf (file, " max distance %u%s\n", chain->length, | |
| 410 chain->has_max_use_after ? "" : ", may reuse first"); | |
| 411 | |
| 412 if (chain->type == CT_COMBINATION) | |
| 413 { | |
| 414 fprintf (file, " equal to %p %s %p in type ", | |
| 415 (void *) chain->ch1, op_symbol_code (chain->op), | |
| 416 (void *) chain->ch2); | |
| 417 print_generic_expr (file, chain->rslt_type, TDF_SLIM); | |
| 418 fprintf (file, "\n"); | |
| 419 } | |
| 420 | |
| 421 if (chain->vars) | |
| 422 { | |
| 423 fprintf (file, " vars"); | |
| 424 for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++) | |
| 425 { | |
| 426 fprintf (file, " "); | |
| 427 print_generic_expr (file, var, TDF_SLIM); | |
| 428 } | |
| 429 fprintf (file, "\n"); | |
| 430 } | |
| 431 | |
| 432 if (chain->inits) | |
| 433 { | |
| 434 fprintf (file, " inits"); | |
| 435 for (i = 0; VEC_iterate (tree, chain->inits, i, var); i++) | |
| 436 { | |
| 437 fprintf (file, " "); | |
| 438 print_generic_expr (file, var, TDF_SLIM); | |
| 439 } | |
| 440 fprintf (file, "\n"); | |
| 441 } | |
| 442 | |
| 443 fprintf (file, " references:\n"); | |
| 444 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++) | |
| 445 dump_dref (file, a); | |
| 446 | |
| 447 fprintf (file, "\n"); | |
| 448 } | |
| 449 | |
| 450 /* Dumps CHAINS to FILE. */ | |
| 451 | |
| 452 extern void dump_chains (FILE *, VEC (chain_p, heap) *); | |
| 453 void | |
| 454 dump_chains (FILE *file, VEC (chain_p, heap) *chains) | |
| 455 { | |
| 456 chain_p chain; | |
| 457 unsigned i; | |
| 458 | |
| 459 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) | |
| 460 dump_chain (file, chain); | |
| 461 } | |
| 462 | |
| 463 /* Dumps COMP to FILE. */ | |
| 464 | |
| 465 extern void dump_component (FILE *, struct component *); | |
| 466 void | |
| 467 dump_component (FILE *file, struct component *comp) | |
| 468 { | |
| 469 dref a; | |
| 470 unsigned i; | |
| 471 | |
| 472 fprintf (file, "Component%s:\n", | |
| 473 comp->comp_step == RS_INVARIANT ? " (invariant)" : ""); | |
| 474 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++) | |
| 475 dump_dref (file, a); | |
| 476 fprintf (file, "\n"); | |
| 477 } | |
| 478 | |
| 479 /* Dumps COMPS to FILE. */ | |
| 480 | |
| 481 extern void dump_components (FILE *, struct component *); | |
| 482 void | |
| 483 dump_components (FILE *file, struct component *comps) | |
| 484 { | |
| 485 struct component *comp; | |
| 486 | |
| 487 for (comp = comps; comp; comp = comp->next) | |
| 488 dump_component (file, comp); | |
| 489 } | |
| 490 | |
| 491 /* Frees a chain CHAIN. */ | |
| 492 | |
| 493 static void | |
| 494 release_chain (chain_p chain) | |
| 495 { | |
| 496 dref ref; | |
| 497 unsigned i; | |
| 498 | |
| 499 if (chain == NULL) | |
| 500 return; | |
| 501 | |
| 502 for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++) | |
| 503 free (ref); | |
| 504 | |
| 505 VEC_free (dref, heap, chain->refs); | |
| 506 VEC_free (tree, heap, chain->vars); | |
| 507 VEC_free (tree, heap, chain->inits); | |
| 508 | |
| 509 free (chain); | |
| 510 } | |
| 511 | |
| 512 /* Frees CHAINS. */ | |
| 513 | |
| 514 static void | |
| 515 release_chains (VEC (chain_p, heap) *chains) | |
| 516 { | |
| 517 unsigned i; | |
| 518 chain_p chain; | |
| 519 | |
| 520 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) | |
| 521 release_chain (chain); | |
| 522 VEC_free (chain_p, heap, chains); | |
| 523 } | |
| 524 | |
| 525 /* Frees a component COMP. */ | |
| 526 | |
| 527 static void | |
| 528 release_component (struct component *comp) | |
| 529 { | |
| 530 VEC_free (dref, heap, comp->refs); | |
| 531 free (comp); | |
| 532 } | |
| 533 | |
| 534 /* Frees list of components COMPS. */ | |
| 535 | |
| 536 static void | |
| 537 release_components (struct component *comps) | |
| 538 { | |
| 539 struct component *act, *next; | |
| 540 | |
| 541 for (act = comps; act; act = next) | |
| 542 { | |
| 543 next = act->next; | |
| 544 release_component (act); | |
| 545 } | |
| 546 } | |
| 547 | |
| 548 /* Finds a root of tree given by FATHERS containing A, and performs path | |
| 549 shortening. */ | |
| 550 | |
| 551 static unsigned | |
| 552 component_of (unsigned fathers[], unsigned a) | |
| 553 { | |
| 554 unsigned root, n; | |
| 555 | |
| 556 for (root = a; root != fathers[root]; root = fathers[root]) | |
| 557 continue; | |
| 558 | |
| 559 for (; a != root; a = n) | |
| 560 { | |
| 561 n = fathers[a]; | |
| 562 fathers[a] = root; | |
| 563 } | |
| 564 | |
| 565 return root; | |
| 566 } | |
| 567 | |
| 568 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the | |
| 569 components, A and B are components to merge. */ | |
| 570 | |
| 571 static void | |
| 572 merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b) | |
| 573 { | |
| 574 unsigned ca = component_of (fathers, a); | |
| 575 unsigned cb = component_of (fathers, b); | |
| 576 | |
| 577 if (ca == cb) | |
| 578 return; | |
| 579 | |
| 580 if (sizes[ca] < sizes[cb]) | |
| 581 { | |
| 582 sizes[cb] += sizes[ca]; | |
| 583 fathers[ca] = cb; | |
| 584 } | |
| 585 else | |
| 586 { | |
| 587 sizes[ca] += sizes[cb]; | |
| 588 fathers[cb] = ca; | |
| 589 } | |
| 590 } | |
| 591 | |
| 592 /* Returns true if A is a reference that is suitable for predictive commoning | |
| 593 in the innermost loop that contains it. REF_STEP is set according to the | |
| 594 step of the reference A. */ | |
| 595 | |
| 596 static bool | |
| 597 suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step) | |
| 598 { | |
| 599 tree ref = DR_REF (a), step = DR_STEP (a); | |
| 600 | |
| 601 if (!step | |
| 602 || !is_gimple_reg_type (TREE_TYPE (ref)) | |
| 603 || tree_could_throw_p (ref)) | |
| 604 return false; | |
| 605 | |
| 606 if (integer_zerop (step)) | |
| 607 *ref_step = RS_INVARIANT; | |
| 608 else if (integer_nonzerop (step)) | |
| 609 *ref_step = RS_NONZERO; | |
| 610 else | |
| 611 *ref_step = RS_ANY; | |
| 612 | |
| 613 return true; | |
| 614 } | |
| 615 | |
| 616 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */ | |
| 617 | |
| 618 static void | |
| 619 aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset) | |
| 620 { | |
| 621 aff_tree delta; | |
| 622 | |
| 623 tree_to_aff_combination_expand (DR_OFFSET (dr), sizetype, offset, | |
| 624 &name_expansions); | |
| 625 aff_combination_const (&delta, sizetype, tree_to_double_int (DR_INIT (dr))); | |
| 626 aff_combination_add (offset, &delta); | |
| 627 } | |
| 628 | |
| 629 /* Determines number of iterations of the innermost enclosing loop before B | |
| 630 refers to exactly the same location as A and stores it to OFF. If A and | |
| 631 B do not have the same step, they never meet, or anything else fails, | |
| 632 returns false, otherwise returns true. Both A and B are assumed to | |
| 633 satisfy suitable_reference_p. */ | |
| 634 | |
| 635 static bool | |
| 636 determine_offset (struct data_reference *a, struct data_reference *b, | |
| 637 double_int *off) | |
| 638 { | |
| 639 aff_tree diff, baseb, step; | |
| 640 tree typea, typeb; | |
| 641 | |
| 642 /* Check that both the references access the location in the same type. */ | |
| 643 typea = TREE_TYPE (DR_REF (a)); | |
| 644 typeb = TREE_TYPE (DR_REF (b)); | |
| 645 if (!useless_type_conversion_p (typeb, typea)) | |
| 646 return false; | |
| 647 | |
| 648 /* Check whether the base address and the step of both references is the | |
| 649 same. */ | |
| 650 if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0) | |
| 651 || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0)) | |
| 652 return false; | |
| 653 | |
| 654 if (integer_zerop (DR_STEP (a))) | |
| 655 { | |
| 656 /* If the references have loop invariant address, check that they access | |
| 657 exactly the same location. */ | |
| 658 *off = double_int_zero; | |
| 659 return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0) | |
| 660 && operand_equal_p (DR_INIT (a), DR_INIT (b), 0)); | |
| 661 } | |
| 662 | |
| 663 /* Compare the offsets of the addresses, and check whether the difference | |
| 664 is a multiple of step. */ | |
| 665 aff_combination_dr_offset (a, &diff); | |
| 666 aff_combination_dr_offset (b, &baseb); | |
| 667 aff_combination_scale (&baseb, double_int_minus_one); | |
| 668 aff_combination_add (&diff, &baseb); | |
| 669 | |
| 670 tree_to_aff_combination_expand (DR_STEP (a), sizetype, | |
| 671 &step, &name_expansions); | |
| 672 return aff_combination_constant_multiple_p (&diff, &step, off); | |
| 673 } | |
| 674 | |
| 675 /* Returns the last basic block in LOOP for that we are sure that | |
| 676 it is executed whenever the loop is entered. */ | |
| 677 | |
| 678 static basic_block | |
| 679 last_always_executed_block (struct loop *loop) | |
| 680 { | |
| 681 unsigned i; | |
| 682 VEC (edge, heap) *exits = get_loop_exit_edges (loop); | |
| 683 edge ex; | |
| 684 basic_block last = loop->latch; | |
| 685 | |
| 686 for (i = 0; VEC_iterate (edge, exits, i, ex); i++) | |
| 687 last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src); | |
| 688 VEC_free (edge, heap, exits); | |
| 689 | |
| 690 return last; | |
| 691 } | |
| 692 | |
| 693 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */ | |
| 694 | |
| 695 static struct component * | |
| 696 split_data_refs_to_components (struct loop *loop, | |
| 697 VEC (data_reference_p, heap) *datarefs, | |
| 698 VEC (ddr_p, heap) *depends) | |
| 699 { | |
| 700 unsigned i, n = VEC_length (data_reference_p, datarefs); | |
| 701 unsigned ca, ia, ib, bad; | |
| 702 unsigned *comp_father = XNEWVEC (unsigned, n + 1); | |
| 703 unsigned *comp_size = XNEWVEC (unsigned, n + 1); | |
| 704 struct component **comps; | |
| 705 struct data_reference *dr, *dra, *drb; | |
| 706 struct data_dependence_relation *ddr; | |
| 707 struct component *comp_list = NULL, *comp; | |
| 708 dref dataref; | |
| 709 basic_block last_always_executed = last_always_executed_block (loop); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
710 |
| 0 | 711 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) |
| 712 { | |
| 713 if (!DR_REF (dr)) | |
| 714 { | |
| 715 /* A fake reference for call or asm_expr that may clobber memory; | |
| 716 just fail. */ | |
| 717 goto end; | |
| 718 } | |
| 719 dr->aux = (void *) (size_t) i; | |
| 720 comp_father[i] = i; | |
| 721 comp_size[i] = 1; | |
| 722 } | |
| 723 | |
| 724 /* A component reserved for the "bad" data references. */ | |
| 725 comp_father[n] = n; | |
| 726 comp_size[n] = 1; | |
| 727 | |
| 728 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) | |
| 729 { | |
| 730 enum ref_step_type dummy; | |
| 731 | |
| 732 if (!suitable_reference_p (dr, &dummy)) | |
| 733 { | |
| 734 ia = (unsigned) (size_t) dr->aux; | |
| 735 merge_comps (comp_father, comp_size, n, ia); | |
| 736 } | |
| 737 } | |
| 738 | |
| 739 for (i = 0; VEC_iterate (ddr_p, depends, i, ddr); i++) | |
| 740 { | |
| 741 double_int dummy_off; | |
| 742 | |
| 743 if (DDR_ARE_DEPENDENT (ddr) == chrec_known) | |
| 744 continue; | |
| 745 | |
| 746 dra = DDR_A (ddr); | |
| 747 drb = DDR_B (ddr); | |
| 748 ia = component_of (comp_father, (unsigned) (size_t) dra->aux); | |
| 749 ib = component_of (comp_father, (unsigned) (size_t) drb->aux); | |
| 750 if (ia == ib) | |
| 751 continue; | |
| 752 | |
| 753 bad = component_of (comp_father, n); | |
| 754 | |
| 755 /* If both A and B are reads, we may ignore unsuitable dependences. */ | |
| 756 if (DR_IS_READ (dra) && DR_IS_READ (drb) | |
| 757 && (ia == bad || ib == bad | |
| 758 || !determine_offset (dra, drb, &dummy_off))) | |
| 759 continue; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
760 |
| 0 | 761 merge_comps (comp_father, comp_size, ia, ib); |
| 762 } | |
| 763 | |
| 764 comps = XCNEWVEC (struct component *, n); | |
| 765 bad = component_of (comp_father, n); | |
| 766 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) | |
| 767 { | |
| 768 ia = (unsigned) (size_t) dr->aux; | |
| 769 ca = component_of (comp_father, ia); | |
| 770 if (ca == bad) | |
| 771 continue; | |
| 772 | |
| 773 comp = comps[ca]; | |
| 774 if (!comp) | |
| 775 { | |
| 776 comp = XCNEW (struct component); | |
| 777 comp->refs = VEC_alloc (dref, heap, comp_size[ca]); | |
| 778 comps[ca] = comp; | |
| 779 } | |
| 780 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
781 dataref = XCNEW (struct dref_d); |
| 0 | 782 dataref->ref = dr; |
| 783 dataref->stmt = DR_STMT (dr); | |
| 784 dataref->offset = double_int_zero; | |
| 785 dataref->distance = 0; | |
| 786 | |
| 787 dataref->always_accessed | |
| 788 = dominated_by_p (CDI_DOMINATORS, last_always_executed, | |
| 789 gimple_bb (dataref->stmt)); | |
| 790 dataref->pos = VEC_length (dref, comp->refs); | |
| 791 VEC_quick_push (dref, comp->refs, dataref); | |
| 792 } | |
| 793 | |
| 794 for (i = 0; i < n; i++) | |
| 795 { | |
| 796 comp = comps[i]; | |
| 797 if (comp) | |
| 798 { | |
| 799 comp->next = comp_list; | |
| 800 comp_list = comp; | |
| 801 } | |
| 802 } | |
| 803 free (comps); | |
| 804 | |
| 805 end: | |
| 806 free (comp_father); | |
| 807 free (comp_size); | |
| 808 return comp_list; | |
| 809 } | |
| 810 | |
| 811 /* Returns true if the component COMP satisfies the conditions | |
| 812 described in 2) at the beginning of this file. LOOP is the current | |
| 813 loop. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
814 |
| 0 | 815 static bool |
| 816 suitable_component_p (struct loop *loop, struct component *comp) | |
| 817 { | |
| 818 unsigned i; | |
| 819 dref a, first; | |
| 820 basic_block ba, bp = loop->header; | |
| 821 bool ok, has_write = false; | |
| 822 | |
| 823 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++) | |
| 824 { | |
| 825 ba = gimple_bb (a->stmt); | |
| 826 | |
| 827 if (!just_once_each_iteration_p (loop, ba)) | |
| 828 return false; | |
| 829 | |
| 830 gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp)); | |
| 831 bp = ba; | |
| 832 | |
| 833 if (!DR_IS_READ (a->ref)) | |
| 834 has_write = true; | |
| 835 } | |
| 836 | |
| 837 first = VEC_index (dref, comp->refs, 0); | |
| 838 ok = suitable_reference_p (first->ref, &comp->comp_step); | |
| 839 gcc_assert (ok); | |
| 840 first->offset = double_int_zero; | |
| 841 | |
| 842 for (i = 1; VEC_iterate (dref, comp->refs, i, a); i++) | |
| 843 { | |
| 844 if (!determine_offset (first->ref, a->ref, &a->offset)) | |
| 845 return false; | |
| 846 | |
| 847 #ifdef ENABLE_CHECKING | |
| 848 { | |
| 849 enum ref_step_type a_step; | |
| 850 ok = suitable_reference_p (a->ref, &a_step); | |
| 851 gcc_assert (ok && a_step == comp->comp_step); | |
| 852 } | |
| 853 #endif | |
| 854 } | |
| 855 | |
| 856 /* If there is a write inside the component, we must know whether the | |
| 857 step is nonzero or not -- we would not otherwise be able to recognize | |
| 858 whether the value accessed by reads comes from the OFFSET-th iteration | |
| 859 or the previous one. */ | |
| 860 if (has_write && comp->comp_step == RS_ANY) | |
| 861 return false; | |
| 862 | |
| 863 return true; | |
| 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 |
| 0 | 866 /* Check the conditions on references inside each of components COMPS, |
| 867 and remove the unsuitable components from the list. The new list | |
| 868 of components is returned. The conditions are described in 2) at | |
| 869 the beginning of this file. LOOP is the current loop. */ | |
| 870 | |
| 871 static struct component * | |
| 872 filter_suitable_components (struct loop *loop, struct component *comps) | |
| 873 { | |
| 874 struct component **comp, *act; | |
| 875 | |
| 876 for (comp = &comps; *comp; ) | |
| 877 { | |
| 878 act = *comp; | |
| 879 if (suitable_component_p (loop, act)) | |
| 880 comp = &act->next; | |
| 881 else | |
| 882 { | |
| 883 dref ref; | |
| 884 unsigned i; | |
| 885 | |
| 886 *comp = act->next; | |
| 887 for (i = 0; VEC_iterate (dref, act->refs, i, ref); i++) | |
| 888 free (ref); | |
| 889 release_component (act); | |
| 890 } | |
| 891 } | |
| 892 | |
| 893 return comps; | |
| 894 } | |
| 895 | |
| 896 /* Compares two drefs A and B by their offset and position. Callback for | |
| 897 qsort. */ | |
| 898 | |
| 899 static int | |
| 900 order_drefs (const void *a, const void *b) | |
| 901 { | |
| 902 const dref *const da = (const dref *) a; | |
| 903 const dref *const db = (const dref *) b; | |
| 904 int offcmp = double_int_scmp ((*da)->offset, (*db)->offset); | |
| 905 | |
| 906 if (offcmp != 0) | |
| 907 return offcmp; | |
| 908 | |
| 909 return (*da)->pos - (*db)->pos; | |
| 910 } | |
| 911 | |
| 912 /* Returns root of the CHAIN. */ | |
| 913 | |
| 914 static inline dref | |
| 915 get_chain_root (chain_p chain) | |
| 916 { | |
| 917 return VEC_index (dref, chain->refs, 0); | |
| 918 } | |
| 919 | |
| 920 /* Adds REF to the chain CHAIN. */ | |
| 921 | |
| 922 static void | |
| 923 add_ref_to_chain (chain_p chain, dref ref) | |
| 924 { | |
| 925 dref root = get_chain_root (chain); | |
| 926 double_int dist; | |
| 927 | |
| 928 gcc_assert (double_int_scmp (root->offset, ref->offset) <= 0); | |
| 929 dist = double_int_add (ref->offset, double_int_neg (root->offset)); | |
| 930 if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), dist) <= 0) | |
| 931 { | |
| 932 free (ref); | |
| 933 return; | |
| 934 } | |
| 935 gcc_assert (double_int_fits_in_uhwi_p (dist)); | |
| 936 | |
| 937 VEC_safe_push (dref, heap, chain->refs, ref); | |
| 938 | |
| 939 ref->distance = double_int_to_uhwi (dist); | |
| 940 | |
| 941 if (ref->distance >= chain->length) | |
| 942 { | |
| 943 chain->length = ref->distance; | |
| 944 chain->has_max_use_after = false; | |
| 945 } | |
| 946 | |
| 947 if (ref->distance == chain->length | |
| 948 && ref->pos > root->pos) | |
| 949 chain->has_max_use_after = true; | |
| 950 | |
| 951 chain->all_always_accessed &= ref->always_accessed; | |
| 952 } | |
| 953 | |
| 954 /* Returns the chain for invariant component COMP. */ | |
| 955 | |
| 956 static chain_p | |
| 957 make_invariant_chain (struct component *comp) | |
| 958 { | |
| 959 chain_p chain = XCNEW (struct chain); | |
| 960 unsigned i; | |
| 961 dref ref; | |
| 962 | |
| 963 chain->type = CT_INVARIANT; | |
| 964 | |
| 965 chain->all_always_accessed = true; | |
| 966 | |
| 967 for (i = 0; VEC_iterate (dref, comp->refs, i, ref); i++) | |
| 968 { | |
| 969 VEC_safe_push (dref, heap, chain->refs, ref); | |
| 970 chain->all_always_accessed &= ref->always_accessed; | |
| 971 } | |
| 972 | |
| 973 return chain; | |
| 974 } | |
| 975 | |
| 976 /* Make a new chain rooted at REF. */ | |
| 977 | |
| 978 static chain_p | |
| 979 make_rooted_chain (dref ref) | |
| 980 { | |
| 981 chain_p chain = XCNEW (struct chain); | |
| 982 | |
| 983 chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD; | |
| 984 | |
| 985 VEC_safe_push (dref, heap, chain->refs, ref); | |
| 986 chain->all_always_accessed = ref->always_accessed; | |
| 987 | |
| 988 ref->distance = 0; | |
| 989 | |
| 990 return chain; | |
| 991 } | |
| 992 | |
| 993 /* Returns true if CHAIN is not trivial. */ | |
| 994 | |
| 995 static bool | |
| 996 nontrivial_chain_p (chain_p chain) | |
| 997 { | |
| 998 return chain != NULL && VEC_length (dref, chain->refs) > 1; | |
| 999 } | |
| 1000 | |
| 1001 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there | |
| 1002 is no such name. */ | |
| 1003 | |
| 1004 static tree | |
| 1005 name_for_ref (dref ref) | |
| 1006 { | |
| 1007 tree name; | |
| 1008 | |
| 1009 if (is_gimple_assign (ref->stmt)) | |
| 1010 { | |
| 1011 if (!ref->ref || DR_IS_READ (ref->ref)) | |
| 1012 name = gimple_assign_lhs (ref->stmt); | |
| 1013 else | |
| 1014 name = gimple_assign_rhs1 (ref->stmt); | |
| 1015 } | |
| 1016 else | |
| 1017 name = PHI_RESULT (ref->stmt); | |
| 1018 | |
| 1019 return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE); | |
| 1020 } | |
| 1021 | |
| 1022 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in | |
| 1023 iterations of the innermost enclosing loop). */ | |
| 1024 | |
| 1025 static bool | |
| 1026 valid_initializer_p (struct data_reference *ref, | |
| 1027 unsigned distance, struct data_reference *root) | |
| 1028 { | |
| 1029 aff_tree diff, base, step; | |
| 1030 double_int off; | |
| 1031 | |
| 1032 /* Both REF and ROOT must be accessing the same object. */ | |
| 1033 if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0)) | |
| 1034 return false; | |
| 1035 | |
| 1036 /* The initializer is defined outside of loop, hence its address must be | |
| 1037 invariant inside the loop. */ | |
| 1038 gcc_assert (integer_zerop (DR_STEP (ref))); | |
| 1039 | |
| 1040 /* If the address of the reference is invariant, initializer must access | |
| 1041 exactly the same location. */ | |
| 1042 if (integer_zerop (DR_STEP (root))) | |
| 1043 return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0) | |
| 1044 && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0)); | |
| 1045 | |
| 1046 /* Verify that this index of REF is equal to the root's index at | |
| 1047 -DISTANCE-th iteration. */ | |
| 1048 aff_combination_dr_offset (root, &diff); | |
| 1049 aff_combination_dr_offset (ref, &base); | |
| 1050 aff_combination_scale (&base, double_int_minus_one); | |
| 1051 aff_combination_add (&diff, &base); | |
| 1052 | |
| 1053 tree_to_aff_combination_expand (DR_STEP (root), sizetype, &step, | |
| 1054 &name_expansions); | |
| 1055 if (!aff_combination_constant_multiple_p (&diff, &step, &off)) | |
| 1056 return false; | |
| 1057 | |
| 1058 if (!double_int_equal_p (off, uhwi_to_double_int (distance))) | |
| 1059 return false; | |
| 1060 | |
| 1061 return true; | |
| 1062 } | |
| 1063 | |
| 1064 /* Finds looparound phi node of LOOP that copies the value of REF, and if its | |
| 1065 initial value is correct (equal to initial value of REF shifted by one | |
| 1066 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT | |
| 1067 is the root of the current chain. */ | |
| 1068 | |
| 1069 static gimple | |
| 1070 find_looparound_phi (struct loop *loop, dref ref, dref root) | |
| 1071 { | |
| 1072 tree name, init, init_ref; | |
| 1073 gimple phi = NULL, init_stmt; | |
| 1074 edge latch = loop_latch_edge (loop); | |
| 1075 struct data_reference init_dr; | |
| 1076 gimple_stmt_iterator psi; | |
| 1077 | |
| 1078 if (is_gimple_assign (ref->stmt)) | |
| 1079 { | |
| 1080 if (DR_IS_READ (ref->ref)) | |
| 1081 name = gimple_assign_lhs (ref->stmt); | |
| 1082 else | |
| 1083 name = gimple_assign_rhs1 (ref->stmt); | |
| 1084 } | |
| 1085 else | |
| 1086 name = PHI_RESULT (ref->stmt); | |
| 1087 if (!name) | |
| 1088 return NULL; | |
| 1089 | |
| 1090 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) | |
| 1091 { | |
| 1092 phi = gsi_stmt (psi); | |
| 1093 if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name) | |
| 1094 break; | |
| 1095 } | |
| 1096 | |
| 1097 if (gsi_end_p (psi)) | |
| 1098 return NULL; | |
| 1099 | |
| 1100 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); | |
| 1101 if (TREE_CODE (init) != SSA_NAME) | |
| 1102 return NULL; | |
| 1103 init_stmt = SSA_NAME_DEF_STMT (init); | |
| 1104 if (gimple_code (init_stmt) != GIMPLE_ASSIGN) | |
| 1105 return NULL; | |
| 1106 gcc_assert (gimple_assign_lhs (init_stmt) == init); | |
| 1107 | |
| 1108 init_ref = gimple_assign_rhs1 (init_stmt); | |
| 1109 if (!REFERENCE_CLASS_P (init_ref) | |
| 1110 && !DECL_P (init_ref)) | |
| 1111 return NULL; | |
| 1112 | |
| 1113 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost | |
| 1114 loop enclosing PHI). */ | |
| 1115 memset (&init_dr, 0, sizeof (struct data_reference)); | |
| 1116 DR_REF (&init_dr) = init_ref; | |
| 1117 DR_STMT (&init_dr) = phi; | |
| 1118 if (!dr_analyze_innermost (&init_dr)) | |
| 1119 return NULL; | |
| 1120 | |
| 1121 if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref)) | |
| 1122 return NULL; | |
| 1123 | |
| 1124 return phi; | |
| 1125 } | |
| 1126 | |
| 1127 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */ | |
| 1128 | |
| 1129 static void | |
| 1130 insert_looparound_copy (chain_p chain, dref ref, gimple phi) | |
| 1131 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1132 dref nw = XCNEW (struct dref_d), aref; |
| 0 | 1133 unsigned i; |
| 1134 | |
| 1135 nw->stmt = phi; | |
| 1136 nw->distance = ref->distance + 1; | |
| 1137 nw->always_accessed = 1; | |
| 1138 | |
| 1139 for (i = 0; VEC_iterate (dref, chain->refs, i, aref); i++) | |
| 1140 if (aref->distance >= nw->distance) | |
| 1141 break; | |
| 1142 VEC_safe_insert (dref, heap, chain->refs, i, nw); | |
| 1143 | |
| 1144 if (nw->distance > chain->length) | |
| 1145 { | |
| 1146 chain->length = nw->distance; | |
| 1147 chain->has_max_use_after = false; | |
| 1148 } | |
| 1149 } | |
| 1150 | |
| 1151 /* For references in CHAIN that are copied around the LOOP (created previously | |
| 1152 by PRE, or by user), add the results of such copies to the chain. This | |
| 1153 enables us to remove the copies by unrolling, and may need less registers | |
| 1154 (also, it may allow us to combine chains together). */ | |
| 1155 | |
| 1156 static void | |
| 1157 add_looparound_copies (struct loop *loop, chain_p chain) | |
| 1158 { | |
| 1159 unsigned i; | |
| 1160 dref ref, root = get_chain_root (chain); | |
| 1161 gimple phi; | |
| 1162 | |
| 1163 for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++) | |
| 1164 { | |
| 1165 phi = find_looparound_phi (loop, ref, root); | |
| 1166 if (!phi) | |
| 1167 continue; | |
| 1168 | |
| 1169 bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi))); | |
| 1170 insert_looparound_copy (chain, ref, phi); | |
| 1171 } | |
| 1172 } | |
| 1173 | |
| 1174 /* Find roots of the values and determine distances in the component COMP. | |
| 1175 The references are redistributed into CHAINS. LOOP is the current | |
| 1176 loop. */ | |
| 1177 | |
| 1178 static void | |
| 1179 determine_roots_comp (struct loop *loop, | |
| 1180 struct component *comp, | |
| 1181 VEC (chain_p, heap) **chains) | |
| 1182 { | |
| 1183 unsigned i; | |
| 1184 dref a; | |
| 1185 chain_p chain = NULL; | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1186 double_int last_ofs = double_int_zero; |
| 0 | 1187 |
| 1188 /* Invariants are handled specially. */ | |
| 1189 if (comp->comp_step == RS_INVARIANT) | |
| 1190 { | |
| 1191 chain = make_invariant_chain (comp); | |
| 1192 VEC_safe_push (chain_p, heap, *chains, chain); | |
| 1193 return; | |
| 1194 } | |
| 1195 | |
| 1196 qsort (VEC_address (dref, comp->refs), VEC_length (dref, comp->refs), | |
| 1197 sizeof (dref), order_drefs); | |
| 1198 | |
| 1199 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++) | |
| 1200 { | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1201 if (!chain || !DR_IS_READ (a->ref) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1202 || double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1203 double_int_add (a->offset, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1204 double_int_neg (last_ofs))) <= 0) |
| 0 | 1205 { |
| 1206 if (nontrivial_chain_p (chain)) | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1207 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1208 add_looparound_copies (loop, chain); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1209 VEC_safe_push (chain_p, heap, *chains, chain); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1210 } |
| 0 | 1211 else |
| 1212 release_chain (chain); | |
| 1213 chain = make_rooted_chain (a); | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1214 last_ofs = a->offset; |
| 0 | 1215 continue; |
| 1216 } | |
| 1217 | |
| 1218 add_ref_to_chain (chain, a); | |
| 1219 } | |
| 1220 | |
| 1221 if (nontrivial_chain_p (chain)) | |
| 1222 { | |
| 1223 add_looparound_copies (loop, chain); | |
| 1224 VEC_safe_push (chain_p, heap, *chains, chain); | |
| 1225 } | |
| 1226 else | |
| 1227 release_chain (chain); | |
| 1228 } | |
| 1229 | |
| 1230 /* Find roots of the values and determine distances in components COMPS, and | |
| 1231 separates the references to CHAINS. LOOP is the current loop. */ | |
| 1232 | |
| 1233 static void | |
| 1234 determine_roots (struct loop *loop, | |
| 1235 struct component *comps, VEC (chain_p, heap) **chains) | |
| 1236 { | |
| 1237 struct component *comp; | |
| 1238 | |
| 1239 for (comp = comps; comp; comp = comp->next) | |
| 1240 determine_roots_comp (loop, comp, chains); | |
| 1241 } | |
| 1242 | |
| 1243 /* Replace the reference in statement STMT with temporary variable | |
| 1244 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of | |
| 1245 the reference in the statement. IN_LHS is true if the reference | |
| 1246 is in the lhs of STMT, false if it is in rhs. */ | |
| 1247 | |
| 1248 static void | |
| 1249 replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs) | |
| 1250 { | |
| 1251 tree val; | |
| 1252 gimple new_stmt; | |
| 1253 gimple_stmt_iterator bsi, psi; | |
| 1254 | |
| 1255 if (gimple_code (stmt) == GIMPLE_PHI) | |
| 1256 { | |
| 1257 gcc_assert (!in_lhs && !set); | |
| 1258 | |
| 1259 val = PHI_RESULT (stmt); | |
| 1260 bsi = gsi_after_labels (gimple_bb (stmt)); | |
| 1261 psi = gsi_for_stmt (stmt); | |
| 1262 remove_phi_node (&psi, false); | |
| 1263 | |
| 1264 /* Turn the phi node into GIMPLE_ASSIGN. */ | |
| 1265 new_stmt = gimple_build_assign (val, new_tree); | |
| 1266 gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT); | |
| 1267 return; | |
| 1268 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1269 |
| 0 | 1270 /* Since the reference is of gimple_reg type, it should only |
| 1271 appear as lhs or rhs of modify statement. */ | |
| 1272 gcc_assert (is_gimple_assign (stmt)); | |
| 1273 | |
| 1274 bsi = gsi_for_stmt (stmt); | |
| 1275 | |
| 1276 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */ | |
| 1277 if (!set) | |
| 1278 { | |
| 1279 gcc_assert (!in_lhs); | |
| 1280 gimple_assign_set_rhs_from_tree (&bsi, new_tree); | |
| 1281 stmt = gsi_stmt (bsi); | |
| 1282 update_stmt (stmt); | |
| 1283 return; | |
| 1284 } | |
| 1285 | |
| 1286 if (in_lhs) | |
| 1287 { | |
| 1288 /* We have statement | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1289 |
| 0 | 1290 OLD = VAL |
| 1291 | |
| 1292 If OLD is a memory reference, then VAL is gimple_val, and we transform | |
| 1293 this to | |
| 1294 | |
| 1295 OLD = VAL | |
| 1296 NEW = VAL | |
| 1297 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1298 Otherwise, we are replacing a combination chain, |
| 0 | 1299 VAL is the expression that performs the combination, and OLD is an |
| 1300 SSA name. In this case, we transform the assignment to | |
| 1301 | |
| 1302 OLD = VAL | |
| 1303 NEW = OLD | |
| 1304 | |
| 1305 */ | |
| 1306 | |
| 1307 val = gimple_assign_lhs (stmt); | |
| 1308 if (TREE_CODE (val) != SSA_NAME) | |
| 1309 { | |
| 1310 gcc_assert (gimple_assign_copy_p (stmt)); | |
| 1311 val = gimple_assign_rhs1 (stmt); | |
| 1312 } | |
| 1313 } | |
| 1314 else | |
| 1315 { | |
| 1316 /* VAL = OLD | |
| 1317 | |
| 1318 is transformed to | |
| 1319 | |
| 1320 VAL = OLD | |
| 1321 NEW = VAL */ | |
| 1322 | |
| 1323 val = gimple_assign_lhs (stmt); | |
| 1324 } | |
| 1325 | |
| 1326 new_stmt = gimple_build_assign (new_tree, unshare_expr (val)); | |
| 1327 gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT); | |
| 1328 } | |
| 1329 | |
| 1330 /* Returns the reference to the address of REF in the ITER-th iteration of | |
| 1331 LOOP, or NULL if we fail to determine it (ITER may be negative). We | |
| 1332 try to preserve the original shape of the reference (not rewrite it | |
| 1333 as an indirect ref to the address), to make tree_could_trap_p in | |
| 1334 prepare_initializers_chain return false more often. */ | |
| 1335 | |
| 1336 static tree | |
| 1337 ref_at_iteration (struct loop *loop, tree ref, int iter) | |
| 1338 { | |
| 1339 tree idx, *idx_p, type, val, op0 = NULL_TREE, ret; | |
| 1340 affine_iv iv; | |
| 1341 bool ok; | |
| 1342 | |
| 1343 if (handled_component_p (ref)) | |
| 1344 { | |
| 1345 op0 = ref_at_iteration (loop, TREE_OPERAND (ref, 0), iter); | |
| 1346 if (!op0) | |
| 1347 return NULL_TREE; | |
| 1348 } | |
| 1349 else if (!INDIRECT_REF_P (ref)) | |
| 1350 return unshare_expr (ref); | |
| 1351 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1352 if (INDIRECT_REF_P (ref)) |
| 0 | 1353 { |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1354 /* Take care for INDIRECT_REF and MISALIGNED_INDIRECT_REF at |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1355 the same time. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1356 ret = copy_node (ref); |
| 0 | 1357 idx = TREE_OPERAND (ref, 0); |
| 1358 idx_p = &TREE_OPERAND (ret, 0); | |
| 1359 } | |
| 1360 else if (TREE_CODE (ref) == COMPONENT_REF) | |
| 1361 { | |
| 1362 /* Check that the offset is loop invariant. */ | |
| 1363 if (TREE_OPERAND (ref, 2) | |
| 1364 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2))) | |
| 1365 return NULL_TREE; | |
| 1366 | |
| 1367 return build3 (COMPONENT_REF, TREE_TYPE (ref), op0, | |
| 1368 unshare_expr (TREE_OPERAND (ref, 1)), | |
| 1369 unshare_expr (TREE_OPERAND (ref, 2))); | |
| 1370 } | |
| 1371 else if (TREE_CODE (ref) == ARRAY_REF) | |
| 1372 { | |
| 1373 /* Check that the lower bound and the step are loop invariant. */ | |
| 1374 if (TREE_OPERAND (ref, 2) | |
| 1375 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2))) | |
| 1376 return NULL_TREE; | |
| 1377 if (TREE_OPERAND (ref, 3) | |
| 1378 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 3))) | |
| 1379 return NULL_TREE; | |
| 1380 | |
| 1381 ret = build4 (ARRAY_REF, TREE_TYPE (ref), op0, NULL_TREE, | |
| 1382 unshare_expr (TREE_OPERAND (ref, 2)), | |
| 1383 unshare_expr (TREE_OPERAND (ref, 3))); | |
| 1384 idx = TREE_OPERAND (ref, 1); | |
| 1385 idx_p = &TREE_OPERAND (ret, 1); | |
| 1386 } | |
| 1387 else | |
| 1388 return NULL_TREE; | |
| 1389 | |
| 1390 ok = simple_iv (loop, loop, idx, &iv, true); | |
| 1391 if (!ok) | |
| 1392 return NULL_TREE; | |
| 1393 iv.base = expand_simple_operations (iv.base); | |
| 1394 if (integer_zerop (iv.step)) | |
| 1395 *idx_p = unshare_expr (iv.base); | |
| 1396 else | |
| 1397 { | |
| 1398 type = TREE_TYPE (iv.base); | |
| 1399 if (POINTER_TYPE_P (type)) | |
| 1400 { | |
| 1401 val = fold_build2 (MULT_EXPR, sizetype, iv.step, | |
| 1402 size_int (iter)); | |
| 1403 val = fold_build2 (POINTER_PLUS_EXPR, type, iv.base, val); | |
| 1404 } | |
| 1405 else | |
| 1406 { | |
| 1407 val = fold_build2 (MULT_EXPR, type, iv.step, | |
| 1408 build_int_cst_type (type, iter)); | |
| 1409 val = fold_build2 (PLUS_EXPR, type, iv.base, val); | |
| 1410 } | |
| 1411 *idx_p = unshare_expr (val); | |
| 1412 } | |
| 1413 | |
| 1414 return ret; | |
| 1415 } | |
| 1416 | |
| 1417 /* Get the initialization expression for the INDEX-th temporary variable | |
| 1418 of CHAIN. */ | |
| 1419 | |
| 1420 static tree | |
| 1421 get_init_expr (chain_p chain, unsigned index) | |
| 1422 { | |
| 1423 if (chain->type == CT_COMBINATION) | |
| 1424 { | |
| 1425 tree e1 = get_init_expr (chain->ch1, index); | |
| 1426 tree e2 = get_init_expr (chain->ch2, index); | |
| 1427 | |
| 1428 return fold_build2 (chain->op, chain->rslt_type, e1, e2); | |
| 1429 } | |
| 1430 else | |
| 1431 return VEC_index (tree, chain->inits, index); | |
| 1432 } | |
| 1433 | |
| 1434 /* Marks all virtual operands of statement STMT for renaming. */ | |
| 1435 | |
| 1436 void | |
| 1437 mark_virtual_ops_for_renaming (gimple stmt) | |
| 1438 { | |
| 1439 tree var; | |
| 1440 | |
| 1441 if (gimple_code (stmt) == GIMPLE_PHI) | |
| 1442 { | |
| 1443 var = PHI_RESULT (stmt); | |
| 1444 if (is_gimple_reg (var)) | |
| 1445 return; | |
| 1446 | |
| 1447 if (TREE_CODE (var) == SSA_NAME) | |
| 1448 var = SSA_NAME_VAR (var); | |
| 1449 mark_sym_for_renaming (var); | |
| 1450 return; | |
| 1451 } | |
| 1452 | |
| 1453 update_stmt (stmt); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1454 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
|
1455 mark_sym_for_renaming (gimple_vop (cfun)); |
| 0 | 1456 } |
| 1457 | |
| 1458 /* Returns a new temporary variable used for the I-th variable carrying | |
| 1459 value of REF. The variable's uid is marked in TMP_VARS. */ | |
| 1460 | |
| 1461 static tree | |
| 1462 predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars) | |
| 1463 { | |
| 1464 tree type = TREE_TYPE (ref); | |
| 1465 /* We never access the components of the temporary variable in predictive | |
| 1466 commoning. */ | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1467 tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i)); |
| 0 | 1468 |
| 1469 add_referenced_var (var); | |
| 1470 bitmap_set_bit (tmp_vars, DECL_UID (var)); | |
| 1471 return var; | |
| 1472 } | |
| 1473 | |
| 1474 /* Creates the variables for CHAIN, as well as phi nodes for them and | |
| 1475 initialization on entry to LOOP. Uids of the newly created | |
| 1476 temporary variables are marked in TMP_VARS. */ | |
| 1477 | |
| 1478 static void | |
| 1479 initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars) | |
| 1480 { | |
| 1481 unsigned i; | |
| 1482 unsigned n = chain->length; | |
| 1483 dref root = get_chain_root (chain); | |
| 1484 bool reuse_first = !chain->has_max_use_after; | |
| 1485 tree ref, init, var, next; | |
| 1486 gimple phi; | |
| 1487 gimple_seq stmts; | |
| 1488 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop); | |
| 1489 | |
| 1490 /* If N == 0, then all the references are within the single iteration. And | |
| 1491 since this is an nonempty chain, reuse_first cannot be true. */ | |
| 1492 gcc_assert (n > 0 || !reuse_first); | |
| 1493 | |
| 1494 chain->vars = VEC_alloc (tree, heap, n + 1); | |
| 1495 | |
| 1496 if (chain->type == CT_COMBINATION) | |
| 1497 ref = gimple_assign_lhs (root->stmt); | |
| 1498 else | |
| 1499 ref = DR_REF (root->ref); | |
| 1500 | |
| 1501 for (i = 0; i < n + (reuse_first ? 0 : 1); i++) | |
| 1502 { | |
| 1503 var = predcom_tmp_var (ref, i, tmp_vars); | |
| 1504 VEC_quick_push (tree, chain->vars, var); | |
| 1505 } | |
| 1506 if (reuse_first) | |
| 1507 VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0)); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1508 |
| 0 | 1509 for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++) |
| 1510 VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL)); | |
| 1511 | |
| 1512 for (i = 0; i < n; i++) | |
| 1513 { | |
| 1514 var = VEC_index (tree, chain->vars, i); | |
| 1515 next = VEC_index (tree, chain->vars, i + 1); | |
| 1516 init = get_init_expr (chain, i); | |
| 1517 | |
| 1518 init = force_gimple_operand (init, &stmts, true, NULL_TREE); | |
| 1519 if (stmts) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1520 gsi_insert_seq_on_edge_immediate (entry, stmts); |
| 0 | 1521 |
| 1522 phi = create_phi_node (var, loop->header); | |
| 1523 SSA_NAME_DEF_STMT (var) = phi; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1524 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1525 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION); |
| 0 | 1526 } |
| 1527 } | |
| 1528 | |
| 1529 /* Create the variables and initialization statement for root of chain | |
| 1530 CHAIN. Uids of the newly created temporary variables are marked | |
| 1531 in TMP_VARS. */ | |
| 1532 | |
| 1533 static void | |
| 1534 initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars) | |
| 1535 { | |
| 1536 dref root = get_chain_root (chain); | |
| 1537 bool in_lhs = (chain->type == CT_STORE_LOAD | |
| 1538 || chain->type == CT_COMBINATION); | |
| 1539 | |
| 1540 initialize_root_vars (loop, chain, tmp_vars); | |
| 1541 replace_ref_with (root->stmt, | |
| 1542 VEC_index (tree, chain->vars, chain->length), | |
| 1543 true, in_lhs); | |
| 1544 } | |
| 1545 | |
| 1546 /* Initializes a variable for load motion for ROOT and prepares phi nodes and | |
| 1547 initialization on entry to LOOP if necessary. The ssa name for the variable | |
| 1548 is stored in VARS. If WRITTEN is true, also a phi node to copy its value | |
| 1549 around the loop is created. Uid of the newly created temporary variable | |
| 1550 is marked in TMP_VARS. INITS is the list containing the (single) | |
| 1551 initializer. */ | |
| 1552 | |
| 1553 static void | |
| 1554 initialize_root_vars_lm (struct loop *loop, dref root, bool written, | |
| 1555 VEC(tree, heap) **vars, VEC(tree, heap) *inits, | |
| 1556 bitmap tmp_vars) | |
| 1557 { | |
| 1558 unsigned i; | |
| 1559 tree ref = DR_REF (root->ref), init, var, next; | |
| 1560 gimple_seq stmts; | |
| 1561 gimple phi; | |
| 1562 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop); | |
| 1563 | |
| 1564 /* Find the initializer for the variable, and check that it cannot | |
| 1565 trap. */ | |
| 1566 init = VEC_index (tree, inits, 0); | |
| 1567 | |
| 1568 *vars = VEC_alloc (tree, heap, written ? 2 : 1); | |
| 1569 var = predcom_tmp_var (ref, 0, tmp_vars); | |
| 1570 VEC_quick_push (tree, *vars, var); | |
| 1571 if (written) | |
| 1572 VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0)); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1573 |
| 0 | 1574 for (i = 0; VEC_iterate (tree, *vars, i, var); i++) |
| 1575 VEC_replace (tree, *vars, i, make_ssa_name (var, NULL)); | |
| 1576 | |
| 1577 var = VEC_index (tree, *vars, 0); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1578 |
| 0 | 1579 init = force_gimple_operand (init, &stmts, written, NULL_TREE); |
| 1580 if (stmts) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1581 gsi_insert_seq_on_edge_immediate (entry, stmts); |
| 0 | 1582 |
| 1583 if (written) | |
| 1584 { | |
| 1585 next = VEC_index (tree, *vars, 1); | |
| 1586 phi = create_phi_node (var, loop->header); | |
| 1587 SSA_NAME_DEF_STMT (var) = phi; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1588 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1589 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION); |
| 0 | 1590 } |
| 1591 else | |
| 1592 { | |
| 1593 gimple init_stmt = gimple_build_assign (var, init); | |
| 1594 mark_virtual_ops_for_renaming (init_stmt); | |
| 1595 gsi_insert_on_edge_immediate (entry, init_stmt); | |
| 1596 } | |
| 1597 } | |
| 1598 | |
| 1599 | |
| 1600 /* Execute load motion for references in chain CHAIN. Uids of the newly | |
| 1601 created temporary variables are marked in TMP_VARS. */ | |
| 1602 | |
| 1603 static void | |
| 1604 execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars) | |
| 1605 { | |
| 1606 VEC (tree, heap) *vars; | |
| 1607 dref a; | |
| 1608 unsigned n_writes = 0, ridx, i; | |
| 1609 tree var; | |
| 1610 | |
| 1611 gcc_assert (chain->type == CT_INVARIANT); | |
| 1612 gcc_assert (!chain->combined); | |
| 1613 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++) | |
| 1614 if (!DR_IS_READ (a->ref)) | |
| 1615 n_writes++; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1616 |
| 0 | 1617 /* If there are no reads in the loop, there is nothing to do. */ |
| 1618 if (n_writes == VEC_length (dref, chain->refs)) | |
| 1619 return; | |
| 1620 | |
| 1621 initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0, | |
| 1622 &vars, chain->inits, tmp_vars); | |
| 1623 | |
| 1624 ridx = 0; | |
| 1625 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++) | |
| 1626 { | |
| 1627 bool is_read = DR_IS_READ (a->ref); | |
| 1628 mark_virtual_ops_for_renaming (a->stmt); | |
| 1629 | |
| 1630 if (!DR_IS_READ (a->ref)) | |
| 1631 { | |
| 1632 n_writes--; | |
| 1633 if (n_writes) | |
| 1634 { | |
| 1635 var = VEC_index (tree, vars, 0); | |
| 1636 var = make_ssa_name (SSA_NAME_VAR (var), NULL); | |
| 1637 VEC_replace (tree, vars, 0, var); | |
| 1638 } | |
| 1639 else | |
| 1640 ridx = 1; | |
| 1641 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1642 |
| 0 | 1643 replace_ref_with (a->stmt, VEC_index (tree, vars, ridx), |
| 1644 !is_read, !is_read); | |
| 1645 } | |
| 1646 | |
| 1647 VEC_free (tree, heap, vars); | |
| 1648 } | |
| 1649 | |
| 1650 /* Returns the single statement in that NAME is used, excepting | |
| 1651 the looparound phi nodes contained in one of the chains. If there is no | |
| 1652 such statement, or more statements, NULL is returned. */ | |
| 1653 | |
| 1654 static gimple | |
| 1655 single_nonlooparound_use (tree name) | |
| 1656 { | |
| 1657 use_operand_p use; | |
| 1658 imm_use_iterator it; | |
| 1659 gimple stmt, ret = NULL; | |
| 1660 | |
| 1661 FOR_EACH_IMM_USE_FAST (use, it, name) | |
| 1662 { | |
| 1663 stmt = USE_STMT (use); | |
| 1664 | |
| 1665 if (gimple_code (stmt) == GIMPLE_PHI) | |
| 1666 { | |
| 1667 /* Ignore uses in looparound phi nodes. Uses in other phi nodes | |
| 1668 could not be processed anyway, so just fail for them. */ | |
| 1669 if (bitmap_bit_p (looparound_phis, | |
| 1670 SSA_NAME_VERSION (PHI_RESULT (stmt)))) | |
| 1671 continue; | |
| 1672 | |
| 1673 return NULL; | |
| 1674 } | |
| 1675 else if (ret != NULL) | |
| 1676 return NULL; | |
| 1677 else | |
| 1678 ret = stmt; | |
| 1679 } | |
| 1680 | |
| 1681 return ret; | |
| 1682 } | |
| 1683 | |
| 1684 /* Remove statement STMT, as well as the chain of assignments in that it is | |
| 1685 used. */ | |
| 1686 | |
| 1687 static void | |
| 1688 remove_stmt (gimple stmt) | |
| 1689 { | |
| 1690 tree name; | |
| 1691 gimple next; | |
| 1692 gimple_stmt_iterator psi; | |
| 1693 | |
| 1694 if (gimple_code (stmt) == GIMPLE_PHI) | |
| 1695 { | |
| 1696 name = PHI_RESULT (stmt); | |
| 1697 next = single_nonlooparound_use (name); | |
| 1698 psi = gsi_for_stmt (stmt); | |
| 1699 remove_phi_node (&psi, true); | |
| 1700 | |
| 1701 if (!next | |
| 1702 || !gimple_assign_ssa_name_copy_p (next) | |
| 1703 || gimple_assign_rhs1 (next) != name) | |
| 1704 return; | |
| 1705 | |
| 1706 stmt = next; | |
| 1707 } | |
| 1708 | |
| 1709 while (1) | |
| 1710 { | |
| 1711 gimple_stmt_iterator bsi; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1712 |
| 0 | 1713 bsi = gsi_for_stmt (stmt); |
| 1714 | |
| 1715 name = gimple_assign_lhs (stmt); | |
| 1716 gcc_assert (TREE_CODE (name) == SSA_NAME); | |
| 1717 | |
| 1718 next = single_nonlooparound_use (name); | |
| 1719 | |
| 1720 mark_virtual_ops_for_renaming (stmt); | |
| 1721 gsi_remove (&bsi, true); | |
| 1722 release_defs (stmt); | |
| 1723 | |
| 1724 if (!next | |
| 1725 || !gimple_assign_ssa_name_copy_p (next) | |
| 1726 || gimple_assign_rhs1 (next) != name) | |
| 1727 return; | |
| 1728 | |
| 1729 stmt = next; | |
| 1730 } | |
| 1731 } | |
| 1732 | |
| 1733 /* Perform the predictive commoning optimization for a chain CHAIN. | |
| 1734 Uids of the newly created temporary variables are marked in TMP_VARS.*/ | |
| 1735 | |
| 1736 static void | |
| 1737 execute_pred_commoning_chain (struct loop *loop, chain_p chain, | |
| 1738 bitmap tmp_vars) | |
| 1739 { | |
| 1740 unsigned i; | |
| 1741 dref a, root; | |
| 1742 tree var; | |
| 1743 | |
| 1744 if (chain->combined) | |
| 1745 { | |
| 1746 /* For combined chains, just remove the statements that are used to | |
| 1747 compute the values of the expression (except for the root one). */ | |
| 1748 for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++) | |
| 1749 remove_stmt (a->stmt); | |
| 1750 } | |
| 1751 else | |
| 1752 { | |
| 1753 /* For non-combined chains, set up the variables that hold its value, | |
| 1754 and replace the uses of the original references by these | |
| 1755 variables. */ | |
| 1756 root = get_chain_root (chain); | |
| 1757 mark_virtual_ops_for_renaming (root->stmt); | |
| 1758 | |
| 1759 initialize_root (loop, chain, tmp_vars); | |
| 1760 for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++) | |
| 1761 { | |
| 1762 mark_virtual_ops_for_renaming (a->stmt); | |
| 1763 var = VEC_index (tree, chain->vars, chain->length - a->distance); | |
| 1764 replace_ref_with (a->stmt, var, false, false); | |
| 1765 } | |
| 1766 } | |
| 1767 } | |
| 1768 | |
| 1769 /* Determines the unroll factor necessary to remove as many temporary variable | |
| 1770 copies as possible. CHAINS is the list of chains that will be | |
| 1771 optimized. */ | |
| 1772 | |
| 1773 static unsigned | |
| 1774 determine_unroll_factor (VEC (chain_p, heap) *chains) | |
| 1775 { | |
| 1776 chain_p chain; | |
| 1777 unsigned factor = 1, af, nfactor, i; | |
| 1778 unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES); | |
| 1779 | |
| 1780 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) | |
| 1781 { | |
| 1782 if (chain->type == CT_INVARIANT || chain->combined) | |
| 1783 continue; | |
| 1784 | |
| 1785 /* The best unroll factor for this chain is equal to the number of | |
| 1786 temporary variables that we create for it. */ | |
| 1787 af = chain->length; | |
| 1788 if (chain->has_max_use_after) | |
| 1789 af++; | |
| 1790 | |
| 1791 nfactor = factor * af / gcd (factor, af); | |
| 1792 if (nfactor <= max) | |
| 1793 factor = nfactor; | |
| 1794 } | |
| 1795 | |
| 1796 return factor; | |
| 1797 } | |
| 1798 | |
| 1799 /* Perform the predictive commoning optimization for CHAINS. | |
| 1800 Uids of the newly created temporary variables are marked in TMP_VARS. */ | |
| 1801 | |
| 1802 static void | |
| 1803 execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains, | |
| 1804 bitmap tmp_vars) | |
| 1805 { | |
| 1806 chain_p chain; | |
| 1807 unsigned i; | |
| 1808 | |
| 1809 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) | |
| 1810 { | |
| 1811 if (chain->type == CT_INVARIANT) | |
| 1812 execute_load_motion (loop, chain, tmp_vars); | |
| 1813 else | |
| 1814 execute_pred_commoning_chain (loop, chain, tmp_vars); | |
| 1815 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1816 |
| 0 | 1817 update_ssa (TODO_update_ssa_only_virtuals); |
| 1818 } | |
| 1819 | |
| 1820 /* For each reference in CHAINS, if its defining statement is | |
| 1821 phi node, record the ssa name that is defined by it. */ | |
| 1822 | |
| 1823 static void | |
| 1824 replace_phis_by_defined_names (VEC (chain_p, heap) *chains) | |
| 1825 { | |
| 1826 chain_p chain; | |
| 1827 dref a; | |
| 1828 unsigned i, j; | |
| 1829 | |
| 1830 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) | |
| 1831 for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++) | |
| 1832 { | |
| 1833 if (gimple_code (a->stmt) == GIMPLE_PHI) | |
| 1834 { | |
| 1835 a->name_defined_by_phi = PHI_RESULT (a->stmt); | |
| 1836 a->stmt = NULL; | |
| 1837 } | |
| 1838 } | |
| 1839 } | |
| 1840 | |
| 1841 /* For each reference in CHAINS, if name_defined_by_phi is not | |
| 1842 NULL, use it to set the stmt field. */ | |
| 1843 | |
| 1844 static void | |
| 1845 replace_names_by_phis (VEC (chain_p, heap) *chains) | |
| 1846 { | |
| 1847 chain_p chain; | |
| 1848 dref a; | |
| 1849 unsigned i, j; | |
| 1850 | |
| 1851 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) | |
| 1852 for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++) | |
| 1853 if (a->stmt == NULL) | |
| 1854 { | |
| 1855 a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi); | |
| 1856 gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI); | |
| 1857 a->name_defined_by_phi = NULL_TREE; | |
| 1858 } | |
| 1859 } | |
| 1860 | |
| 1861 /* Wrapper over execute_pred_commoning, to pass it as a callback | |
| 1862 to tree_transform_and_unroll_loop. */ | |
| 1863 | |
| 1864 struct epcc_data | |
| 1865 { | |
| 1866 VEC (chain_p, heap) *chains; | |
| 1867 bitmap tmp_vars; | |
| 1868 }; | |
| 1869 | |
| 1870 static void | |
| 1871 execute_pred_commoning_cbck (struct loop *loop, void *data) | |
| 1872 { | |
| 1873 struct epcc_data *const dta = (struct epcc_data *) data; | |
| 1874 | |
| 1875 /* Restore phi nodes that were replaced by ssa names before | |
| 1876 tree_transform_and_unroll_loop (see detailed description in | |
| 1877 tree_predictive_commoning_loop). */ | |
| 1878 replace_names_by_phis (dta->chains); | |
| 1879 execute_pred_commoning (loop, dta->chains, dta->tmp_vars); | |
| 1880 } | |
| 1881 | |
| 1882 /* Base NAME and all the names in the chain of phi nodes that use it | |
| 1883 on variable VAR. The phi nodes are recognized by being in the copies of | |
| 1884 the header of the LOOP. */ | |
| 1885 | |
| 1886 static void | |
| 1887 base_names_in_chain_on (struct loop *loop, tree name, tree var) | |
| 1888 { | |
| 1889 gimple stmt, phi; | |
| 1890 imm_use_iterator iter; | |
| 1891 | |
| 1892 SSA_NAME_VAR (name) = var; | |
| 1893 | |
| 1894 while (1) | |
| 1895 { | |
| 1896 phi = NULL; | |
| 1897 FOR_EACH_IMM_USE_STMT (stmt, iter, name) | |
| 1898 { | |
| 1899 if (gimple_code (stmt) == GIMPLE_PHI | |
| 1900 && flow_bb_inside_loop_p (loop, gimple_bb (stmt))) | |
| 1901 { | |
| 1902 phi = stmt; | |
| 1903 BREAK_FROM_IMM_USE_STMT (iter); | |
| 1904 } | |
| 1905 } | |
| 1906 if (!phi) | |
| 1907 return; | |
| 1908 | |
| 1909 name = PHI_RESULT (phi); | |
| 1910 SSA_NAME_VAR (name) = var; | |
| 1911 } | |
| 1912 } | |
| 1913 | |
| 1914 /* Given an unrolled LOOP after predictive commoning, remove the | |
| 1915 register copies arising from phi nodes by changing the base | |
| 1916 variables of SSA names. TMP_VARS is the set of the temporary variables | |
| 1917 for those we want to perform this. */ | |
| 1918 | |
| 1919 static void | |
| 1920 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars) | |
| 1921 { | |
| 1922 edge e; | |
| 1923 gimple phi, stmt; | |
| 1924 tree name, use, var; | |
| 1925 gimple_stmt_iterator psi; | |
| 1926 | |
| 1927 e = loop_latch_edge (loop); | |
| 1928 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) | |
| 1929 { | |
| 1930 phi = gsi_stmt (psi); | |
| 1931 name = PHI_RESULT (phi); | |
| 1932 var = SSA_NAME_VAR (name); | |
| 1933 if (!bitmap_bit_p (tmp_vars, DECL_UID (var))) | |
| 1934 continue; | |
| 1935 use = PHI_ARG_DEF_FROM_EDGE (phi, e); | |
| 1936 gcc_assert (TREE_CODE (use) == SSA_NAME); | |
| 1937 | |
| 1938 /* Base all the ssa names in the ud and du chain of NAME on VAR. */ | |
| 1939 stmt = SSA_NAME_DEF_STMT (use); | |
| 1940 while (gimple_code (stmt) == GIMPLE_PHI | |
| 1941 /* In case we could not unroll the loop enough to eliminate | |
| 1942 all copies, we may reach the loop header before the defining | |
| 1943 statement (in that case, some register copies will be present | |
| 1944 in loop latch in the final code, corresponding to the newly | |
| 1945 created looparound phi nodes). */ | |
| 1946 && gimple_bb (stmt) != loop->header) | |
| 1947 { | |
| 1948 gcc_assert (single_pred_p (gimple_bb (stmt))); | |
| 1949 use = PHI_ARG_DEF (stmt, 0); | |
| 1950 stmt = SSA_NAME_DEF_STMT (use); | |
| 1951 } | |
| 1952 | |
| 1953 base_names_in_chain_on (loop, use, var); | |
| 1954 } | |
| 1955 } | |
| 1956 | |
| 1957 /* Returns true if CHAIN is suitable to be combined. */ | |
| 1958 | |
| 1959 static bool | |
| 1960 chain_can_be_combined_p (chain_p chain) | |
| 1961 { | |
| 1962 return (!chain->combined | |
| 1963 && (chain->type == CT_LOAD || chain->type == CT_COMBINATION)); | |
| 1964 } | |
| 1965 | |
| 1966 /* Returns the modify statement that uses NAME. Skips over assignment | |
| 1967 statements, NAME is replaced with the actual name used in the returned | |
| 1968 statement. */ | |
| 1969 | |
| 1970 static gimple | |
| 1971 find_use_stmt (tree *name) | |
| 1972 { | |
| 1973 gimple stmt; | |
| 1974 tree rhs, lhs; | |
| 1975 | |
| 1976 /* Skip over assignments. */ | |
| 1977 while (1) | |
| 1978 { | |
| 1979 stmt = single_nonlooparound_use (*name); | |
| 1980 if (!stmt) | |
| 1981 return NULL; | |
| 1982 | |
| 1983 if (gimple_code (stmt) != GIMPLE_ASSIGN) | |
| 1984 return NULL; | |
| 1985 | |
| 1986 lhs = gimple_assign_lhs (stmt); | |
| 1987 if (TREE_CODE (lhs) != SSA_NAME) | |
| 1988 return NULL; | |
| 1989 | |
| 1990 if (gimple_assign_copy_p (stmt)) | |
| 1991 { | |
| 1992 rhs = gimple_assign_rhs1 (stmt); | |
| 1993 if (rhs != *name) | |
| 1994 return NULL; | |
| 1995 | |
| 1996 *name = lhs; | |
| 1997 } | |
| 1998 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)) | |
| 1999 == GIMPLE_BINARY_RHS) | |
| 2000 return stmt; | |
| 2001 else | |
| 2002 return NULL; | |
| 2003 } | |
| 2004 } | |
| 2005 | |
| 2006 /* Returns true if we may perform reassociation for operation CODE in TYPE. */ | |
| 2007 | |
| 2008 static bool | |
| 2009 may_reassociate_p (tree type, enum tree_code code) | |
| 2010 { | |
| 2011 if (FLOAT_TYPE_P (type) | |
| 2012 && !flag_unsafe_math_optimizations) | |
| 2013 return false; | |
| 2014 | |
| 2015 return (commutative_tree_code (code) | |
| 2016 && associative_tree_code (code)); | |
| 2017 } | |
| 2018 | |
| 2019 /* If the operation used in STMT is associative and commutative, go through the | |
| 2020 tree of the same operations and returns its root. Distance to the root | |
| 2021 is stored in DISTANCE. */ | |
| 2022 | |
| 2023 static gimple | |
| 2024 find_associative_operation_root (gimple stmt, unsigned *distance) | |
| 2025 { | |
| 2026 tree lhs; | |
| 2027 gimple next; | |
| 2028 enum tree_code code = gimple_assign_rhs_code (stmt); | |
| 2029 tree type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
| 2030 unsigned dist = 0; | |
| 2031 | |
| 2032 if (!may_reassociate_p (type, code)) | |
| 2033 return NULL; | |
| 2034 | |
| 2035 while (1) | |
| 2036 { | |
| 2037 lhs = gimple_assign_lhs (stmt); | |
| 2038 gcc_assert (TREE_CODE (lhs) == SSA_NAME); | |
| 2039 | |
| 2040 next = find_use_stmt (&lhs); | |
| 2041 if (!next | |
| 2042 || gimple_assign_rhs_code (next) != code) | |
| 2043 break; | |
| 2044 | |
| 2045 stmt = next; | |
| 2046 dist++; | |
| 2047 } | |
| 2048 | |
| 2049 if (distance) | |
| 2050 *distance = dist; | |
| 2051 return stmt; | |
| 2052 } | |
| 2053 | |
| 2054 /* Returns the common statement in that NAME1 and NAME2 have a use. If there | |
| 2055 is no such statement, returns NULL_TREE. In case the operation used on | |
| 2056 NAME1 and NAME2 is associative and commutative, returns the root of the | |
| 2057 tree formed by this operation instead of the statement that uses NAME1 or | |
| 2058 NAME2. */ | |
| 2059 | |
| 2060 static gimple | |
| 2061 find_common_use_stmt (tree *name1, tree *name2) | |
| 2062 { | |
| 2063 gimple stmt1, stmt2; | |
| 2064 | |
| 2065 stmt1 = find_use_stmt (name1); | |
| 2066 if (!stmt1) | |
| 2067 return NULL; | |
| 2068 | |
| 2069 stmt2 = find_use_stmt (name2); | |
| 2070 if (!stmt2) | |
| 2071 return NULL; | |
| 2072 | |
| 2073 if (stmt1 == stmt2) | |
| 2074 return stmt1; | |
| 2075 | |
| 2076 stmt1 = find_associative_operation_root (stmt1, NULL); | |
| 2077 if (!stmt1) | |
| 2078 return NULL; | |
| 2079 stmt2 = find_associative_operation_root (stmt2, NULL); | |
| 2080 if (!stmt2) | |
| 2081 return NULL; | |
| 2082 | |
| 2083 return (stmt1 == stmt2 ? stmt1 : NULL); | |
| 2084 } | |
| 2085 | |
| 2086 /* Checks whether R1 and R2 are combined together using CODE, with the result | |
| 2087 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1 | |
| 2088 if it is true. If CODE is ERROR_MARK, set these values instead. */ | |
| 2089 | |
| 2090 static bool | |
| 2091 combinable_refs_p (dref r1, dref r2, | |
| 2092 enum tree_code *code, bool *swap, tree *rslt_type) | |
| 2093 { | |
| 2094 enum tree_code acode; | |
| 2095 bool aswap; | |
| 2096 tree atype; | |
| 2097 tree name1, name2; | |
| 2098 gimple stmt; | |
| 2099 | |
| 2100 name1 = name_for_ref (r1); | |
| 2101 name2 = name_for_ref (r2); | |
| 2102 gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE); | |
| 2103 | |
| 2104 stmt = find_common_use_stmt (&name1, &name2); | |
| 2105 | |
| 2106 if (!stmt) | |
| 2107 return false; | |
| 2108 | |
| 2109 acode = gimple_assign_rhs_code (stmt); | |
| 2110 aswap = (!commutative_tree_code (acode) | |
| 2111 && gimple_assign_rhs1 (stmt) != name1); | |
| 2112 atype = TREE_TYPE (gimple_assign_lhs (stmt)); | |
| 2113 | |
| 2114 if (*code == ERROR_MARK) | |
| 2115 { | |
| 2116 *code = acode; | |
| 2117 *swap = aswap; | |
| 2118 *rslt_type = atype; | |
| 2119 return true; | |
| 2120 } | |
| 2121 | |
| 2122 return (*code == acode | |
| 2123 && *swap == aswap | |
| 2124 && *rslt_type == atype); | |
| 2125 } | |
| 2126 | |
| 2127 /* Remove OP from the operation on rhs of STMT, and replace STMT with | |
| 2128 an assignment of the remaining operand. */ | |
| 2129 | |
| 2130 static void | |
| 2131 remove_name_from_operation (gimple stmt, tree op) | |
| 2132 { | |
| 2133 tree other_op; | |
| 2134 gimple_stmt_iterator si; | |
| 2135 | |
| 2136 gcc_assert (is_gimple_assign (stmt)); | |
| 2137 | |
| 2138 if (gimple_assign_rhs1 (stmt) == op) | |
| 2139 other_op = gimple_assign_rhs2 (stmt); | |
| 2140 else | |
| 2141 other_op = gimple_assign_rhs1 (stmt); | |
| 2142 | |
| 2143 si = gsi_for_stmt (stmt); | |
| 2144 gimple_assign_set_rhs_from_tree (&si, other_op); | |
| 2145 | |
| 2146 /* We should not have reallocated STMT. */ | |
| 2147 gcc_assert (gsi_stmt (si) == stmt); | |
| 2148 | |
| 2149 update_stmt (stmt); | |
| 2150 } | |
| 2151 | |
| 2152 /* Reassociates the expression in that NAME1 and NAME2 are used so that they | |
| 2153 are combined in a single statement, and returns this statement. */ | |
| 2154 | |
| 2155 static gimple | |
| 2156 reassociate_to_the_same_stmt (tree name1, tree name2) | |
| 2157 { | |
| 2158 gimple stmt1, stmt2, root1, root2, s1, s2; | |
| 2159 gimple new_stmt, tmp_stmt; | |
| 2160 tree new_name, tmp_name, var, r1, r2; | |
| 2161 unsigned dist1, dist2; | |
| 2162 enum tree_code code; | |
| 2163 tree type = TREE_TYPE (name1); | |
| 2164 gimple_stmt_iterator bsi; | |
| 2165 | |
| 2166 stmt1 = find_use_stmt (&name1); | |
| 2167 stmt2 = find_use_stmt (&name2); | |
| 2168 root1 = find_associative_operation_root (stmt1, &dist1); | |
| 2169 root2 = find_associative_operation_root (stmt2, &dist2); | |
| 2170 code = gimple_assign_rhs_code (stmt1); | |
| 2171 | |
| 2172 gcc_assert (root1 && root2 && root1 == root2 | |
| 2173 && code == gimple_assign_rhs_code (stmt2)); | |
| 2174 | |
| 2175 /* Find the root of the nearest expression in that both NAME1 and NAME2 | |
| 2176 are used. */ | |
| 2177 r1 = name1; | |
| 2178 s1 = stmt1; | |
| 2179 r2 = name2; | |
| 2180 s2 = stmt2; | |
| 2181 | |
| 2182 while (dist1 > dist2) | |
| 2183 { | |
| 2184 s1 = find_use_stmt (&r1); | |
| 2185 r1 = gimple_assign_lhs (s1); | |
| 2186 dist1--; | |
| 2187 } | |
| 2188 while (dist2 > dist1) | |
| 2189 { | |
| 2190 s2 = find_use_stmt (&r2); | |
| 2191 r2 = gimple_assign_lhs (s2); | |
| 2192 dist2--; | |
| 2193 } | |
| 2194 | |
| 2195 while (s1 != s2) | |
| 2196 { | |
| 2197 s1 = find_use_stmt (&r1); | |
| 2198 r1 = gimple_assign_lhs (s1); | |
| 2199 s2 = find_use_stmt (&r2); | |
| 2200 r2 = gimple_assign_lhs (s2); | |
| 2201 } | |
| 2202 | |
| 2203 /* Remove NAME1 and NAME2 from the statements in that they are used | |
| 2204 currently. */ | |
| 2205 remove_name_from_operation (stmt1, name1); | |
| 2206 remove_name_from_operation (stmt2, name2); | |
| 2207 | |
| 2208 /* Insert the new statement combining NAME1 and NAME2 before S1, and | |
| 2209 combine it with the rhs of S1. */ | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2210 var = create_tmp_reg (type, "predreastmp"); |
| 0 | 2211 add_referenced_var (var); |
| 2212 new_name = make_ssa_name (var, NULL); | |
| 2213 new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2); | |
| 2214 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2215 var = create_tmp_reg (type, "predreastmp"); |
| 0 | 2216 add_referenced_var (var); |
| 2217 tmp_name = make_ssa_name (var, NULL); | |
| 2218 | |
| 2219 /* Rhs of S1 may now be either a binary expression with operation | |
| 2220 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1, | |
| 2221 so that name1 or name2 was removed from it). */ | |
| 2222 tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1), | |
| 2223 tmp_name, | |
| 2224 gimple_assign_rhs1 (s1), | |
| 2225 gimple_assign_rhs2 (s1)); | |
| 2226 | |
| 2227 bsi = gsi_for_stmt (s1); | |
| 2228 gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name); | |
| 2229 s1 = gsi_stmt (bsi); | |
| 2230 update_stmt (s1); | |
| 2231 | |
| 2232 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT); | |
| 2233 gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT); | |
| 2234 | |
| 2235 return new_stmt; | |
| 2236 } | |
| 2237 | |
| 2238 /* Returns the statement that combines references R1 and R2. In case R1 | |
| 2239 and R2 are not used in the same statement, but they are used with an | |
| 2240 associative and commutative operation in the same expression, reassociate | |
| 2241 the expression so that they are used in the same statement. */ | |
| 2242 | |
| 2243 static gimple | |
| 2244 stmt_combining_refs (dref r1, dref r2) | |
| 2245 { | |
| 2246 gimple stmt1, stmt2; | |
| 2247 tree name1 = name_for_ref (r1); | |
| 2248 tree name2 = name_for_ref (r2); | |
| 2249 | |
| 2250 stmt1 = find_use_stmt (&name1); | |
| 2251 stmt2 = find_use_stmt (&name2); | |
| 2252 if (stmt1 == stmt2) | |
| 2253 return stmt1; | |
| 2254 | |
| 2255 return reassociate_to_the_same_stmt (name1, name2); | |
| 2256 } | |
| 2257 | |
| 2258 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the | |
| 2259 description of the new chain is returned, otherwise we return NULL. */ | |
| 2260 | |
| 2261 static chain_p | |
| 2262 combine_chains (chain_p ch1, chain_p ch2) | |
| 2263 { | |
| 2264 dref r1, r2, nw; | |
| 2265 enum tree_code op = ERROR_MARK; | |
| 2266 bool swap = false; | |
| 2267 chain_p new_chain; | |
| 2268 unsigned i; | |
| 2269 gimple root_stmt; | |
| 2270 tree rslt_type = NULL_TREE; | |
| 2271 | |
| 2272 if (ch1 == ch2) | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2273 return NULL; |
| 0 | 2274 if (ch1->length != ch2->length) |
| 2275 return NULL; | |
| 2276 | |
| 2277 if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs)) | |
| 2278 return NULL; | |
| 2279 | |
| 2280 for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1) | |
| 2281 && VEC_iterate (dref, ch2->refs, i, r2)); i++) | |
| 2282 { | |
| 2283 if (r1->distance != r2->distance) | |
| 2284 return NULL; | |
| 2285 | |
| 2286 if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type)) | |
| 2287 return NULL; | |
| 2288 } | |
| 2289 | |
| 2290 if (swap) | |
| 2291 { | |
| 2292 chain_p tmp = ch1; | |
| 2293 ch1 = ch2; | |
| 2294 ch2 = tmp; | |
| 2295 } | |
| 2296 | |
| 2297 new_chain = XCNEW (struct chain); | |
| 2298 new_chain->type = CT_COMBINATION; | |
| 2299 new_chain->op = op; | |
| 2300 new_chain->ch1 = ch1; | |
| 2301 new_chain->ch2 = ch2; | |
| 2302 new_chain->rslt_type = rslt_type; | |
| 2303 new_chain->length = ch1->length; | |
| 2304 | |
| 2305 for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1) | |
| 2306 && VEC_iterate (dref, ch2->refs, i, r2)); i++) | |
| 2307 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2308 nw = XCNEW (struct dref_d); |
| 0 | 2309 nw->stmt = stmt_combining_refs (r1, r2); |
| 2310 nw->distance = r1->distance; | |
| 2311 | |
| 2312 VEC_safe_push (dref, heap, new_chain->refs, nw); | |
| 2313 } | |
| 2314 | |
| 2315 new_chain->has_max_use_after = false; | |
| 2316 root_stmt = get_chain_root (new_chain)->stmt; | |
| 2317 for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++) | |
| 2318 { | |
| 2319 if (nw->distance == new_chain->length | |
| 2320 && !stmt_dominates_stmt_p (nw->stmt, root_stmt)) | |
| 2321 { | |
| 2322 new_chain->has_max_use_after = true; | |
| 2323 break; | |
| 2324 } | |
| 2325 } | |
| 2326 | |
| 2327 ch1->combined = true; | |
| 2328 ch2->combined = true; | |
| 2329 return new_chain; | |
| 2330 } | |
| 2331 | |
| 2332 /* Try to combine the CHAINS. */ | |
| 2333 | |
| 2334 static void | |
| 2335 try_combine_chains (VEC (chain_p, heap) **chains) | |
| 2336 { | |
| 2337 unsigned i, j; | |
| 2338 chain_p ch1, ch2, cch; | |
| 2339 VEC (chain_p, heap) *worklist = NULL; | |
| 2340 | |
| 2341 for (i = 0; VEC_iterate (chain_p, *chains, i, ch1); i++) | |
| 2342 if (chain_can_be_combined_p (ch1)) | |
| 2343 VEC_safe_push (chain_p, heap, worklist, ch1); | |
| 2344 | |
| 2345 while (!VEC_empty (chain_p, worklist)) | |
| 2346 { | |
| 2347 ch1 = VEC_pop (chain_p, worklist); | |
| 2348 if (!chain_can_be_combined_p (ch1)) | |
| 2349 continue; | |
| 2350 | |
| 2351 for (j = 0; VEC_iterate (chain_p, *chains, j, ch2); j++) | |
| 2352 { | |
| 2353 if (!chain_can_be_combined_p (ch2)) | |
| 2354 continue; | |
| 2355 | |
| 2356 cch = combine_chains (ch1, ch2); | |
| 2357 if (cch) | |
| 2358 { | |
| 2359 VEC_safe_push (chain_p, heap, worklist, cch); | |
| 2360 VEC_safe_push (chain_p, heap, *chains, cch); | |
| 2361 break; | |
| 2362 } | |
| 2363 } | |
| 2364 } | |
| 2365 } | |
| 2366 | |
| 2367 /* Prepare initializers for CHAIN in LOOP. Returns false if this is | |
| 2368 impossible because one of these initializers may trap, true otherwise. */ | |
| 2369 | |
| 2370 static bool | |
| 2371 prepare_initializers_chain (struct loop *loop, chain_p chain) | |
| 2372 { | |
| 2373 unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length; | |
| 2374 struct data_reference *dr = get_chain_root (chain)->ref; | |
| 2375 tree init; | |
| 2376 gimple_seq stmts; | |
| 2377 dref laref; | |
| 2378 edge entry = loop_preheader_edge (loop); | |
| 2379 | |
| 2380 /* Find the initializers for the variables, and check that they cannot | |
| 2381 trap. */ | |
| 2382 chain->inits = VEC_alloc (tree, heap, n); | |
| 2383 for (i = 0; i < n; i++) | |
| 2384 VEC_quick_push (tree, chain->inits, NULL_TREE); | |
| 2385 | |
| 2386 /* If we have replaced some looparound phi nodes, use their initializers | |
| 2387 instead of creating our own. */ | |
| 2388 for (i = 0; VEC_iterate (dref, chain->refs, i, laref); i++) | |
| 2389 { | |
| 2390 if (gimple_code (laref->stmt) != GIMPLE_PHI) | |
| 2391 continue; | |
| 2392 | |
| 2393 gcc_assert (laref->distance > 0); | |
| 2394 VEC_replace (tree, chain->inits, n - laref->distance, | |
| 2395 PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry)); | |
| 2396 } | |
| 2397 | |
| 2398 for (i = 0; i < n; i++) | |
| 2399 { | |
| 2400 if (VEC_index (tree, chain->inits, i) != NULL_TREE) | |
| 2401 continue; | |
| 2402 | |
| 2403 init = ref_at_iteration (loop, DR_REF (dr), (int) i - n); | |
| 2404 if (!init) | |
| 2405 return false; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2406 |
| 0 | 2407 if (!chain->all_always_accessed && tree_could_trap_p (init)) |
| 2408 return false; | |
| 2409 | |
| 2410 init = force_gimple_operand (init, &stmts, false, NULL_TREE); | |
| 2411 if (stmts) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2412 gsi_insert_seq_on_edge_immediate (entry, stmts); |
| 0 | 2413 |
| 2414 VEC_replace (tree, chain->inits, i, init); | |
| 2415 } | |
| 2416 | |
| 2417 return true; | |
| 2418 } | |
| 2419 | |
| 2420 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot | |
| 2421 be used because the initializers might trap. */ | |
| 2422 | |
| 2423 static void | |
| 2424 prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains) | |
| 2425 { | |
| 2426 chain_p chain; | |
| 2427 unsigned i; | |
| 2428 | |
| 2429 for (i = 0; i < VEC_length (chain_p, chains); ) | |
| 2430 { | |
| 2431 chain = VEC_index (chain_p, chains, i); | |
| 2432 if (prepare_initializers_chain (loop, chain)) | |
| 2433 i++; | |
| 2434 else | |
| 2435 { | |
| 2436 release_chain (chain); | |
| 2437 VEC_unordered_remove (chain_p, chains, i); | |
| 2438 } | |
| 2439 } | |
| 2440 } | |
| 2441 | |
| 2442 /* Performs predictive commoning for LOOP. Returns true if LOOP was | |
| 2443 unrolled. */ | |
| 2444 | |
| 2445 static bool | |
| 2446 tree_predictive_commoning_loop (struct loop *loop) | |
| 2447 { | |
| 2448 VEC (data_reference_p, heap) *datarefs; | |
| 2449 VEC (ddr_p, heap) *dependences; | |
| 2450 struct component *components; | |
| 2451 VEC (chain_p, heap) *chains = NULL; | |
| 2452 unsigned unroll_factor; | |
| 2453 struct tree_niter_desc desc; | |
| 2454 bool unroll = false; | |
| 2455 edge exit; | |
| 2456 bitmap tmp_vars; | |
| 2457 | |
| 2458 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2459 fprintf (dump_file, "Processing loop %d\n", loop->num); | |
| 2460 | |
| 2461 /* Find the data references and split them into components according to their | |
| 2462 dependence relations. */ | |
| 2463 datarefs = VEC_alloc (data_reference_p, heap, 10); | |
| 2464 dependences = VEC_alloc (ddr_p, heap, 10); | |
| 2465 compute_data_dependences_for_loop (loop, true, &datarefs, &dependences); | |
| 2466 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2467 dump_data_dependence_relations (dump_file, dependences); | |
| 2468 | |
| 2469 components = split_data_refs_to_components (loop, datarefs, dependences); | |
| 2470 free_dependence_relations (dependences); | |
| 2471 if (!components) | |
| 2472 { | |
| 2473 free_data_refs (datarefs); | |
| 2474 return false; | |
| 2475 } | |
| 2476 | |
| 2477 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2478 { | |
| 2479 fprintf (dump_file, "Initial state:\n\n"); | |
| 2480 dump_components (dump_file, components); | |
| 2481 } | |
| 2482 | |
| 2483 /* Find the suitable components and split them into chains. */ | |
| 2484 components = filter_suitable_components (loop, components); | |
| 2485 | |
| 2486 tmp_vars = BITMAP_ALLOC (NULL); | |
| 2487 looparound_phis = BITMAP_ALLOC (NULL); | |
| 2488 determine_roots (loop, components, &chains); | |
| 2489 release_components (components); | |
| 2490 | |
| 2491 if (!chains) | |
| 2492 { | |
| 2493 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2494 fprintf (dump_file, | |
| 2495 "Predictive commoning failed: no suitable chains\n"); | |
| 2496 goto end; | |
| 2497 } | |
| 2498 prepare_initializers (loop, chains); | |
| 2499 | |
| 2500 /* Try to combine the chains that are always worked with together. */ | |
| 2501 try_combine_chains (&chains); | |
| 2502 | |
| 2503 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2504 { | |
| 2505 fprintf (dump_file, "Before commoning:\n\n"); | |
| 2506 dump_chains (dump_file, chains); | |
| 2507 } | |
| 2508 | |
| 2509 /* Determine the unroll factor, and if the loop should be unrolled, ensure | |
| 2510 that its number of iterations is divisible by the factor. */ | |
| 2511 unroll_factor = determine_unroll_factor (chains); | |
| 2512 scev_reset (); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2513 unroll = (unroll_factor > 1 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2514 && can_unroll_loop_p (loop, unroll_factor, &desc)); |
| 0 | 2515 exit = single_dom_exit (loop); |
| 2516 | |
| 2517 /* Execute the predictive commoning transformations, and possibly unroll the | |
| 2518 loop. */ | |
| 2519 if (unroll) | |
| 2520 { | |
| 2521 struct epcc_data dta; | |
| 2522 | |
| 2523 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2524 fprintf (dump_file, "Unrolling %u times.\n", unroll_factor); | |
| 2525 | |
| 2526 dta.chains = chains; | |
| 2527 dta.tmp_vars = tmp_vars; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2528 |
| 0 | 2529 update_ssa (TODO_update_ssa_only_virtuals); |
| 2530 | |
| 2531 /* Cfg manipulations performed in tree_transform_and_unroll_loop before | |
| 2532 execute_pred_commoning_cbck is called may cause phi nodes to be | |
| 2533 reallocated, which is a problem since CHAINS may point to these | |
| 2534 statements. To fix this, we store the ssa names defined by the | |
| 2535 phi nodes here instead of the phi nodes themselves, and restore | |
| 2536 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */ | |
| 2537 replace_phis_by_defined_names (chains); | |
| 2538 | |
| 2539 tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc, | |
| 2540 execute_pred_commoning_cbck, &dta); | |
| 2541 eliminate_temp_copies (loop, tmp_vars); | |
| 2542 } | |
| 2543 else | |
| 2544 { | |
| 2545 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2546 fprintf (dump_file, | |
| 2547 "Executing predictive commoning without unrolling.\n"); | |
| 2548 execute_pred_commoning (loop, chains, tmp_vars); | |
| 2549 } | |
| 2550 | |
| 2551 end: ; | |
| 2552 release_chains (chains); | |
| 2553 free_data_refs (datarefs); | |
| 2554 BITMAP_FREE (tmp_vars); | |
| 2555 BITMAP_FREE (looparound_phis); | |
| 2556 | |
| 2557 free_affine_expand_cache (&name_expansions); | |
| 2558 | |
| 2559 return unroll; | |
| 2560 } | |
| 2561 | |
| 2562 /* Runs predictive commoning. */ | |
| 2563 | |
| 2564 unsigned | |
| 2565 tree_predictive_commoning (void) | |
| 2566 { | |
| 2567 bool unrolled = false; | |
| 2568 struct loop *loop; | |
| 2569 loop_iterator li; | |
| 2570 unsigned ret = 0; | |
| 2571 | |
| 2572 initialize_original_copy_tables (); | |
| 2573 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) | |
| 2574 if (optimize_loop_for_speed_p (loop)) | |
| 2575 { | |
| 2576 unrolled |= tree_predictive_commoning_loop (loop); | |
| 2577 } | |
| 2578 | |
| 2579 if (unrolled) | |
| 2580 { | |
| 2581 scev_reset (); | |
| 2582 ret = TODO_cleanup_cfg; | |
| 2583 } | |
| 2584 free_original_copy_tables (); | |
| 2585 | |
| 2586 return ret; | |
| 2587 } |