gcc/tree-predcom.c

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