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   /* Both REF and ROOT must be accessing the same object.  */
1030   if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1031     return false;
1032
1033   /* The initializer is defined outside of loop, hence its address must be
1034      invariant inside the loop.  */
1035   gcc_assert (integer_zerop (DR_STEP (ref)));
1036
1037   /* If the address of the reference is invariant, initializer must access
1038      exactly the same location.  */
1039   if (integer_zerop (DR_STEP (root)))
1040     return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1041             && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1042
1043   /* Verify that this index of REF is equal to the root's index at
1044      -DISTANCE-th iteration.  */
1045   aff_combination_dr_offset (root, &diff);
1046   aff_combination_dr_offset (ref, &base);
1047   aff_combination_scale (&base, double_int_minus_one);
1048   aff_combination_add (&diff, &base);
1049
1050   tree_to_aff_combination_expand (DR_STEP (root), sizetype, &step,
1051                                   &name_expansions);
1052   if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1053     return false;
1054
1055   if (!double_int_equal_p (off, uhwi_to_double_int (distance)))
1056     return false;
1057
1058   return true;
1059 }
1060
1061 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1062    initial value is correct (equal to initial value of REF shifted by one
1063    iteration), returns the phi node.  Otherwise, NULL_TREE is returned.  ROOT
1064    is the root of the current chain.  */
1065
1066 static gimple
1067 find_looparound_phi (struct loop *loop, dref ref, dref root)
1068 {
1069   tree name, init, init_ref;
1070   gimple phi = NULL, init_stmt;
1071   edge latch = loop_latch_edge (loop);
1072   struct data_reference init_dr;
1073   gimple_stmt_iterator psi;
1074
1075   if (is_gimple_assign (ref->stmt))
1076     {
1077       if (DR_IS_READ (ref->ref))
1078         name = gimple_assign_lhs (ref->stmt);
1079       else
1080         name = gimple_assign_rhs1 (ref->stmt);
1081     }
1082   else
1083     name = PHI_RESULT (ref->stmt);
1084   if (!name)
1085     return NULL;
1086
1087   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1088     {
1089       phi = gsi_stmt (psi);
1090       if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name)
1091         break;
1092     }
1093
1094   if (gsi_end_p (psi))
1095     return NULL;
1096
1097   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1098   if (TREE_CODE (init) != SSA_NAME)
1099     return NULL;
1100   init_stmt = SSA_NAME_DEF_STMT (init);
1101   if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
1102     return NULL;
1103   gcc_assert (gimple_assign_lhs (init_stmt) == init);
1104
1105   init_ref = gimple_assign_rhs1 (init_stmt);
1106   if (!REFERENCE_CLASS_P (init_ref)
1107       && !DECL_P (init_ref))
1108     return NULL;
1109
1110   /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1111      loop enclosing PHI).  */
1112   memset (&init_dr, 0, sizeof (struct data_reference));
1113   DR_REF (&init_dr) = init_ref;
1114   DR_STMT (&init_dr) = phi;
1115   if (!dr_analyze_innermost (&init_dr))
1116     return NULL;
1117
1118   if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1119     return NULL;
1120
1121   return phi;
1122 }
1123
1124 /* Adds a reference for the looparound copy of REF in PHI to CHAIN.  */
1125
1126 static void
1127 insert_looparound_copy (chain_p chain, dref ref, gimple phi)
1128 {
1129   dref nw = XCNEW (struct dref), aref;
1130   unsigned i;
1131
1132   nw->stmt = phi;
1133   nw->distance = ref->distance + 1;
1134   nw->always_accessed = 1;
1135
1136   for (i = 0; VEC_iterate (dref, chain->refs, i, aref); i++)
1137     if (aref->distance >= nw->distance)
1138       break;
1139   VEC_safe_insert (dref, heap, chain->refs, i, nw);
1140
1141   if (nw->distance > chain->length)
1142     {
1143       chain->length = nw->distance;
1144       chain->has_max_use_after = false;
1145     }
1146 }
1147
1148 /* For references in CHAIN that are copied around the LOOP (created previously
1149    by PRE, or by user), add the results of such copies to the chain.  This
1150    enables us to remove the copies by unrolling, and may need less registers
1151    (also, it may allow us to combine chains together).  */
1152
1153 static void
1154 add_looparound_copies (struct loop *loop, chain_p chain)
1155 {
1156   unsigned i;
1157   dref ref, root = get_chain_root (chain);
1158   gimple phi;
1159
1160   for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++)
1161     {
1162       phi = find_looparound_phi (loop, ref, root);
1163       if (!phi)
1164         continue;
1165
1166       bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1167       insert_looparound_copy (chain, ref, phi);
1168     }
1169 }
1170
1171 /* Find roots of the values and determine distances in the component COMP.
1172    The references are redistributed into CHAINS.  LOOP is the current
1173    loop.  */
1174
1175 static void
1176 determine_roots_comp (struct loop *loop,
1177                       struct component *comp,
1178                       VEC (chain_p, heap) **chains)
1179 {
1180   unsigned i;
1181   dref a;
1182   chain_p chain = NULL;
1183
1184   /* Invariants are handled specially.  */
1185   if (comp->comp_step == RS_INVARIANT)
1186     {
1187       chain = make_invariant_chain (comp);
1188       VEC_safe_push (chain_p, heap, *chains, chain);
1189       return;
1190     }
1191
1192   qsort (VEC_address (dref, comp->refs), VEC_length (dref, comp->refs),
1193          sizeof (dref), order_drefs);
1194
1195   for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
1196     {
1197       if (!chain || !DR_IS_READ (a->ref))
1198         {
1199           if (nontrivial_chain_p (chain))
1200             VEC_safe_push (chain_p, heap, *chains, chain);
1201           else
1202             release_chain (chain);
1203           chain = make_rooted_chain (a);
1204           continue;
1205         }
1206
1207       add_ref_to_chain (chain, a);
1208     }
1209
1210   if (nontrivial_chain_p (chain))
1211     {
1212       add_looparound_copies (loop, chain);
1213       VEC_safe_push (chain_p, heap, *chains, chain);
1214     }
1215   else
1216     release_chain (chain);
1217 }
1218
1219 /* Find roots of the values and determine distances in components COMPS, and
1220    separates the references to CHAINS.  LOOP is the current loop.  */
1221
1222 static void
1223 determine_roots (struct loop *loop,
1224                  struct component *comps, VEC (chain_p, heap) **chains)
1225 {
1226   struct component *comp;
1227
1228   for (comp = comps; comp; comp = comp->next)
1229     determine_roots_comp (loop, comp, chains);
1230 }
1231
1232 /* Replace the reference in statement STMT with temporary variable
1233    NEW_TREE.  If SET is true, NEW_TREE is instead initialized to the value of
1234    the reference in the statement.  IN_LHS is true if the reference
1235    is in the lhs of STMT, false if it is in rhs.  */
1236
1237 static void
1238 replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs)
1239 {
1240   tree val;
1241   gimple new_stmt;
1242   gimple_stmt_iterator bsi, psi;
1243
1244   if (gimple_code (stmt) == GIMPLE_PHI)
1245     {
1246       gcc_assert (!in_lhs && !set);
1247
1248       val = PHI_RESULT (stmt);
1249       bsi = gsi_after_labels (gimple_bb (stmt));
1250       psi = gsi_for_stmt (stmt);
1251       remove_phi_node (&psi, false);
1252
1253       /* Turn the phi node into GIMPLE_ASSIGN.  */
1254       new_stmt = gimple_build_assign (val, new_tree);
1255       gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
1256       return;
1257     }
1258
1259   /* Since the reference is of gimple_reg type, it should only
1260      appear as lhs or rhs of modify statement.  */
1261   gcc_assert (is_gimple_assign (stmt));
1262
1263   bsi = gsi_for_stmt (stmt);
1264
1265   /* If we do not need to initialize NEW_TREE, just replace the use of OLD.  */
1266   if (!set)
1267     {
1268       gcc_assert (!in_lhs);
1269       gimple_assign_set_rhs_from_tree (&bsi, new_tree);
1270       stmt = gsi_stmt (bsi);
1271       update_stmt (stmt);
1272       return;
1273     }
1274
1275   if (in_lhs)
1276     {
1277       /* We have statement
1278
1279          OLD = VAL
1280
1281          If OLD is a memory reference, then VAL is gimple_val, and we transform
1282          this to
1283
1284          OLD = VAL
1285          NEW = VAL
1286
1287          Otherwise, we are replacing a combination chain,
1288          VAL is the expression that performs the combination, and OLD is an
1289          SSA name.  In this case, we transform the assignment to
1290
1291          OLD = VAL
1292          NEW = OLD
1293
1294          */
1295
1296       val = gimple_assign_lhs (stmt);
1297       if (TREE_CODE (val) != SSA_NAME)
1298         {
1299           gcc_assert (gimple_assign_copy_p (stmt));
1300           val = gimple_assign_rhs1 (stmt);
1301         }
1302     }
1303   else
1304     {
1305       /* VAL = OLD
1306
1307          is transformed to
1308
1309          VAL = OLD
1310          NEW = VAL  */
1311
1312       val = gimple_assign_lhs (stmt);
1313     }
1314
1315   new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
1316   gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
1317 }
1318
1319 /* Returns the reference to the address of REF in the ITER-th iteration of
1320    LOOP, or NULL if we fail to determine it (ITER may be negative).  We
1321    try to preserve the original shape of the reference (not rewrite it
1322    as an indirect ref to the address), to make tree_could_trap_p in
1323    prepare_initializers_chain return false more often.  */
1324
1325 static tree
1326 ref_at_iteration (struct loop *loop, tree ref, int iter)
1327 {
1328   tree idx, *idx_p, type, val, op0 = NULL_TREE, ret;
1329   affine_iv iv;
1330   bool ok;
1331
1332   if (handled_component_p (ref))
1333     {
1334       op0 = ref_at_iteration (loop, TREE_OPERAND (ref, 0), iter);
1335       if (!op0)
1336         return NULL_TREE;
1337     }
1338   else if (!INDIRECT_REF_P (ref))
1339     return unshare_expr (ref);
1340
1341   if (TREE_CODE (ref) == INDIRECT_REF)
1342     {
1343       ret = build1 (INDIRECT_REF, TREE_TYPE (ref), NULL_TREE);
1344       idx = TREE_OPERAND (ref, 0);
1345       idx_p = &TREE_OPERAND (ret, 0);
1346     }
1347   else if (TREE_CODE (ref) == COMPONENT_REF)
1348     {
1349       /* Check that the offset is loop invariant.  */
1350       if (TREE_OPERAND (ref, 2)
1351           && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1352         return NULL_TREE;
1353
1354       return build3 (COMPONENT_REF, TREE_TYPE (ref), op0,
1355                      unshare_expr (TREE_OPERAND (ref, 1)),
1356                      unshare_expr (TREE_OPERAND (ref, 2)));
1357     }
1358   else if (TREE_CODE (ref) == ARRAY_REF)
1359     {
1360       /* Check that the lower bound and the step are loop invariant.  */
1361       if (TREE_OPERAND (ref, 2)
1362           && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1363         return NULL_TREE;
1364       if (TREE_OPERAND (ref, 3)
1365           && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 3)))
1366         return NULL_TREE;
1367
1368       ret = build4 (ARRAY_REF, TREE_TYPE (ref), op0, NULL_TREE,
1369                     unshare_expr (TREE_OPERAND (ref, 2)),
1370                     unshare_expr (TREE_OPERAND (ref, 3)));
1371       idx = TREE_OPERAND (ref, 1);
1372       idx_p = &TREE_OPERAND (ret, 1);
1373     }
1374   else
1375     return NULL_TREE;
1376
1377   ok = simple_iv (loop, first_stmt (loop->header), idx, &iv, true);
1378   if (!ok)
1379     return NULL_TREE;
1380   iv.base = expand_simple_operations (iv.base);
1381   if (integer_zerop (iv.step))
1382     *idx_p = unshare_expr (iv.base);
1383   else
1384     {
1385       type = TREE_TYPE (iv.base);
1386       if (POINTER_TYPE_P (type))
1387         {
1388           val = fold_build2 (MULT_EXPR, sizetype, iv.step,
1389                              size_int (iter));
1390           val = fold_build2 (POINTER_PLUS_EXPR, type, iv.base, val);
1391         }
1392       else
1393         {
1394           val = fold_build2 (MULT_EXPR, type, iv.step,
1395                              build_int_cst_type (type, iter));
1396           val = fold_build2 (PLUS_EXPR, type, iv.base, val);
1397         }
1398       *idx_p = unshare_expr (val);
1399     }
1400
1401   return ret;
1402 }
1403
1404 /* Get the initialization expression for the INDEX-th temporary variable
1405    of CHAIN.  */
1406
1407 static tree
1408 get_init_expr (chain_p chain, unsigned index)
1409 {
1410   if (chain->type == CT_COMBINATION)
1411     {
1412       tree e1 = get_init_expr (chain->ch1, index);
1413       tree e2 = get_init_expr (chain->ch2, index);
1414
1415       return fold_build2 (chain->op, chain->rslt_type, e1, e2);
1416     }
1417   else
1418     return VEC_index (tree, chain->inits, index);
1419 }
1420
1421 /* Marks all virtual operands of statement STMT for renaming.  */
1422
1423 void
1424 mark_virtual_ops_for_renaming (gimple stmt)
1425 {
1426   ssa_op_iter iter;
1427   tree var;
1428
1429   if (gimple_code (stmt) == GIMPLE_PHI)
1430     {
1431       var = PHI_RESULT (stmt);
1432       if (is_gimple_reg (var))
1433         return;
1434
1435       if (TREE_CODE (var) == SSA_NAME)
1436         var = SSA_NAME_VAR (var);
1437       mark_sym_for_renaming (var);
1438       return;
1439     }
1440
1441   update_stmt (stmt);
1442
1443   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS)
1444     {
1445       if (TREE_CODE (var) == SSA_NAME)
1446         var = SSA_NAME_VAR (var);
1447       mark_sym_for_renaming (var);
1448     }
1449 }
1450
1451 /* Calls mark_virtual_ops_for_renaming for all members of LIST.  */
1452
1453 static void
1454 mark_virtual_ops_for_renaming_list (gimple_seq list)
1455 {
1456   gimple_stmt_iterator gsi;
1457
1458   for (gsi = gsi_start (list); !gsi_end_p (gsi); gsi_next (&gsi))
1459     mark_virtual_ops_for_renaming (gsi_stmt (gsi));
1460 }
1461
1462 /* Returns a new temporary variable used for the I-th variable carrying
1463    value of REF.  The variable's uid is marked in TMP_VARS.  */
1464
1465 static tree
1466 predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1467 {
1468   tree type = TREE_TYPE (ref);
1469   tree var = create_tmp_var (type, get_lsm_tmp_name (ref, i));
1470
1471   /* We never access the components of the temporary variable in predictive
1472      commoning.  */
1473   if (TREE_CODE (type) == COMPLEX_TYPE
1474       || TREE_CODE (type) == VECTOR_TYPE)
1475     DECL_GIMPLE_REG_P (var) = 1;
1476
1477   add_referenced_var (var);
1478   bitmap_set_bit (tmp_vars, DECL_UID (var));
1479   return var;
1480 }
1481
1482 /* Creates the variables for CHAIN, as well as phi nodes for them and
1483    initialization on entry to LOOP.  Uids of the newly created
1484    temporary variables are marked in TMP_VARS.  */
1485
1486 static void
1487 initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars)
1488 {
1489   unsigned i;
1490   unsigned n = chain->length;
1491   dref root = get_chain_root (chain);
1492   bool reuse_first = !chain->has_max_use_after;
1493   tree ref, init, var, next;
1494   gimple phi;
1495   gimple_seq stmts;
1496   edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1497
1498   /* If N == 0, then all the references are within the single iteration.  And
1499      since this is an nonempty chain, reuse_first cannot be true.  */
1500   gcc_assert (n > 0 || !reuse_first);
1501
1502   chain->vars = VEC_alloc (tree, heap, n + 1);
1503
1504   if (chain->type == CT_COMBINATION)
1505     ref = gimple_assign_lhs (root->stmt);
1506   else
1507     ref = DR_REF (root->ref);
1508
1509   for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1510     {
1511       var = predcom_tmp_var (ref, i, tmp_vars);
1512       VEC_quick_push (tree, chain->vars, var);
1513     }
1514   if (reuse_first)
1515     VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0));
1516
1517   for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++)
1518     VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL));
1519
1520   for (i = 0; i < n; i++)
1521     {
1522       var = VEC_index (tree, chain->vars, i);
1523       next = VEC_index (tree, chain->vars, i + 1);
1524       init = get_init_expr (chain, i);
1525
1526       init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1527       if (stmts)
1528         {
1529           mark_virtual_ops_for_renaming_list (stmts);
1530           gsi_insert_seq_on_edge_immediate (entry, stmts);
1531         }
1532
1533       phi = create_phi_node (var, loop->header);
1534       SSA_NAME_DEF_STMT (var) = phi;
1535       add_phi_arg (phi, init, entry);
1536       add_phi_arg (phi, next, latch);
1537     }
1538 }
1539
1540 /* Create the variables and initialization statement for root of chain
1541    CHAIN.  Uids of the newly created temporary variables are marked
1542    in TMP_VARS.  */
1543
1544 static void
1545 initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars)
1546 {
1547   dref root = get_chain_root (chain);
1548   bool in_lhs = (chain->type == CT_STORE_LOAD
1549                  || chain->type == CT_COMBINATION);
1550
1551   initialize_root_vars (loop, chain, tmp_vars);
1552   replace_ref_with (root->stmt,
1553                     VEC_index (tree, chain->vars, chain->length),
1554                     true, in_lhs);
1555 }
1556
1557 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1558    initialization on entry to LOOP if necessary.  The ssa name for the variable
1559    is stored in VARS.  If WRITTEN is true, also a phi node to copy its value
1560    around the loop is created.  Uid of the newly created temporary variable
1561    is marked in TMP_VARS.  INITS is the list containing the (single)
1562    initializer.  */
1563
1564 static void
1565 initialize_root_vars_lm (struct loop *loop, dref root, bool written,
1566                          VEC(tree, heap) **vars, VEC(tree, heap) *inits,
1567                          bitmap tmp_vars)
1568 {
1569   unsigned i;
1570   tree ref = DR_REF (root->ref), init, var, next;
1571   gimple_seq stmts;
1572   gimple phi;
1573   edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1574
1575   /* Find the initializer for the variable, and check that it cannot
1576      trap.  */
1577   init = VEC_index (tree, inits, 0);
1578
1579   *vars = VEC_alloc (tree, heap, written ? 2 : 1);
1580   var = predcom_tmp_var (ref, 0, tmp_vars);
1581   VEC_quick_push (tree, *vars, var);
1582   if (written)
1583     VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0));
1584
1585   for (i = 0; VEC_iterate (tree, *vars, i, var); i++)
1586     VEC_replace (tree, *vars, i, make_ssa_name (var, NULL));
1587
1588   var = VEC_index (tree, *vars, 0);
1589
1590   init = force_gimple_operand (init, &stmts, written, NULL_TREE);
1591   if (stmts)
1592     {
1593       mark_virtual_ops_for_renaming_list (stmts);
1594       gsi_insert_seq_on_edge_immediate (entry, stmts);
1595     }
1596
1597   if (written)
1598     {
1599       next = VEC_index (tree, *vars, 1);
1600       phi = create_phi_node (var, loop->header);
1601       SSA_NAME_DEF_STMT (var) = phi;
1602       add_phi_arg (phi, init, entry);
1603       add_phi_arg (phi, next, latch);
1604     }
1605   else
1606     {
1607       gimple init_stmt = gimple_build_assign (var, init);
1608       mark_virtual_ops_for_renaming (init_stmt);
1609       gsi_insert_on_edge_immediate (entry, init_stmt);
1610     }
1611 }
1612
1613
1614 /* Execute load motion for references in chain CHAIN.  Uids of the newly
1615    created temporary variables are marked in TMP_VARS.  */
1616
1617 static void
1618 execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars)
1619 {
1620   VEC (tree, heap) *vars;
1621   dref a;
1622   unsigned n_writes = 0, ridx, i;
1623   tree var;
1624
1625   gcc_assert (chain->type == CT_INVARIANT);
1626   gcc_assert (!chain->combined);
1627   for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
1628     if (!DR_IS_READ (a->ref))
1629       n_writes++;
1630
1631   /* If there are no reads in the loop, there is nothing to do.  */
1632   if (n_writes == VEC_length (dref, chain->refs))
1633     return;
1634
1635   initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
1636                            &vars, chain->inits, tmp_vars);
1637
1638   ridx = 0;
1639   for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
1640     {
1641       bool is_read = DR_IS_READ (a->ref);
1642       mark_virtual_ops_for_renaming (a->stmt);
1643
1644       if (!DR_IS_READ (a->ref))
1645         {
1646           n_writes--;
1647           if (n_writes)
1648             {
1649               var = VEC_index (tree, vars, 0);
1650               var = make_ssa_name (SSA_NAME_VAR (var), NULL);
1651               VEC_replace (tree, vars, 0, var);
1652             }
1653           else
1654             ridx = 1;
1655         }
1656
1657       replace_ref_with (a->stmt, VEC_index (tree, vars, ridx),
1658                         !is_read, !is_read);
1659     }
1660
1661   VEC_free (tree, heap, vars);
1662 }
1663
1664 /* Returns the single statement in that NAME is used, excepting
1665    the looparound phi nodes contained in one of the chains.  If there is no
1666    such statement, or more statements, NULL is returned.  */
1667
1668 static gimple
1669 single_nonlooparound_use (tree name)
1670 {
1671   use_operand_p use;
1672   imm_use_iterator it;
1673   gimple stmt, ret = NULL;
1674
1675   FOR_EACH_IMM_USE_FAST (use, it, name)
1676     {
1677       stmt = USE_STMT (use);
1678
1679       if (gimple_code (stmt) == GIMPLE_PHI)
1680         {
1681           /* Ignore uses in looparound phi nodes.  Uses in other phi nodes
1682              could not be processed anyway, so just fail for them.  */
1683           if (bitmap_bit_p (looparound_phis,
1684                             SSA_NAME_VERSION (PHI_RESULT (stmt))))
1685             continue;
1686
1687           return NULL;
1688         }
1689       else if (ret != NULL)
1690         return NULL;
1691       else
1692         ret = stmt;
1693     }
1694
1695   return ret;
1696 }
1697
1698 /* Remove statement STMT, as well as the chain of assignments in that it is
1699    used.  */
1700
1701 static void
1702 remove_stmt (gimple stmt)
1703 {
1704   tree name;
1705   gimple next;
1706   gimple_stmt_iterator psi;
1707
1708   if (gimple_code (stmt) == GIMPLE_PHI)
1709     {
1710       name = PHI_RESULT (stmt);
1711       next = single_nonlooparound_use (name);
1712       psi = gsi_for_stmt (stmt);
1713       remove_phi_node (&psi, true);
1714
1715       if (!next
1716           || !gimple_assign_ssa_name_copy_p (next)
1717           || gimple_assign_rhs1 (next) != name)
1718         return;
1719
1720       stmt = next;
1721     }
1722
1723   while (1)
1724     {
1725       gimple_stmt_iterator bsi;
1726
1727       bsi = gsi_for_stmt (stmt);
1728
1729       name = gimple_assign_lhs (stmt);
1730       gcc_assert (TREE_CODE (name) == SSA_NAME);
1731
1732       next = single_nonlooparound_use (name);
1733
1734       mark_virtual_ops_for_renaming (stmt);
1735       gsi_remove (&bsi, true);
1736       release_defs (stmt);
1737
1738       if (!next
1739           || !gimple_assign_ssa_name_copy_p (next)
1740           || gimple_assign_rhs1 (next) != name)
1741         return;
1742
1743       stmt = next;
1744     }
1745 }
1746
1747 /* Perform the predictive commoning optimization for a chain CHAIN.
1748    Uids of the newly created temporary variables are marked in TMP_VARS.*/
1749
1750 static void
1751 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
1752                              bitmap tmp_vars)
1753 {
1754   unsigned i;
1755   dref a, root;
1756   tree var;
1757
1758   if (chain->combined)
1759     {
1760       /* For combined chains, just remove the statements that are used to
1761          compute the values of the expression (except for the root one).  */
1762       for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1763         remove_stmt (a->stmt);
1764     }
1765   else
1766     {
1767       /* For non-combined chains, set up the variables that hold its value,
1768          and replace the uses of the original references by these
1769          variables.  */
1770       root = get_chain_root (chain);
1771       mark_virtual_ops_for_renaming (root->stmt);
1772
1773       initialize_root (loop, chain, tmp_vars);
1774       for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1775         {
1776           mark_virtual_ops_for_renaming (a->stmt);
1777           var = VEC_index (tree, chain->vars, chain->length - a->distance);
1778           replace_ref_with (a->stmt, var, false, false);
1779         }
1780     }
1781 }
1782
1783 /* Determines the unroll factor necessary to remove as many temporary variable
1784    copies as possible.  CHAINS is the list of chains that will be
1785    optimized.  */
1786
1787 static unsigned
1788 determine_unroll_factor (VEC (chain_p, heap) *chains)
1789 {
1790   chain_p chain;
1791   unsigned factor = 1, af, nfactor, i;
1792   unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1793
1794   for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1795     {
1796       if (chain->type == CT_INVARIANT || chain->combined)
1797         continue;
1798
1799       /* The best unroll factor for this chain is equal to the number of
1800          temporary variables that we create for it.  */
1801       af = chain->length;
1802       if (chain->has_max_use_after)
1803         af++;
1804
1805       nfactor = factor * af / gcd (factor, af);
1806       if (nfactor <= max)
1807         factor = nfactor;
1808     }
1809
1810   return factor;
1811 }
1812
1813 /* Perform the predictive commoning optimization for CHAINS.
1814    Uids of the newly created temporary variables are marked in TMP_VARS.  */
1815
1816 static void
1817 execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains,
1818                         bitmap tmp_vars)
1819 {
1820   chain_p chain;
1821   unsigned i;
1822
1823   for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1824     {
1825       if (chain->type == CT_INVARIANT)
1826         execute_load_motion (loop, chain, tmp_vars);
1827       else
1828         execute_pred_commoning_chain (loop, chain, tmp_vars);
1829     }
1830
1831   update_ssa (TODO_update_ssa_only_virtuals);
1832 }
1833
1834 /* For each reference in CHAINS, if its defining statement is
1835    phi node, record the ssa name that is defined by it.  */
1836
1837 static void
1838 replace_phis_by_defined_names (VEC (chain_p, heap) *chains)
1839 {
1840   chain_p chain;
1841   dref a;
1842   unsigned i, j;
1843
1844   for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1845     for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1846       {
1847         if (gimple_code (a->stmt) == GIMPLE_PHI)
1848           {
1849             a->name_defined_by_phi = PHI_RESULT (a->stmt);
1850             a->stmt = NULL;
1851           }
1852       }
1853 }
1854
1855 /* For each reference in CHAINS, if name_defined_by_phi is not
1856    NULL, use it to set the stmt field.  */
1857
1858 static void
1859 replace_names_by_phis (VEC (chain_p, heap) *chains)
1860 {
1861   chain_p chain;
1862   dref a;
1863   unsigned i, j;
1864
1865   for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1866     for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1867       if (a->stmt == NULL)
1868         {
1869           a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
1870           gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
1871           a->name_defined_by_phi = NULL_TREE;
1872         }
1873 }
1874
1875 /* Wrapper over execute_pred_commoning, to pass it as a callback
1876    to tree_transform_and_unroll_loop.  */
1877
1878 struct epcc_data
1879 {
1880   VEC (chain_p, heap) *chains;
1881   bitmap tmp_vars;
1882 };
1883
1884 static void
1885 execute_pred_commoning_cbck (struct loop *loop, void *data)
1886 {
1887   struct epcc_data *const dta = (struct epcc_data *) data;
1888
1889   /* Restore phi nodes that were replaced by ssa names before
1890      tree_transform_and_unroll_loop (see detailed description in
1891      tree_predictive_commoning_loop).  */
1892   replace_names_by_phis (dta->chains);
1893   execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
1894 }
1895
1896 /* Returns true if we can and should unroll LOOP FACTOR times.  Number
1897    of iterations of the loop is returned in NITER.  */
1898
1899 static bool
1900 should_unroll_loop_p (struct loop *loop, unsigned factor,
1901                       struct tree_niter_desc *niter)
1902 {
1903   edge exit;
1904
1905   if (factor == 1)
1906     return false;
1907
1908   /* Check whether unrolling is possible.  We only want to unroll loops
1909      for that we are able to determine number of iterations.  We also
1910      want to split the extra iterations of the loop from its end,
1911      therefore we require that the loop has precisely one
1912      exit.  */
1913
1914   exit = single_dom_exit (loop);
1915   if (!exit)
1916     return false;
1917
1918   if (!number_of_iterations_exit (loop, exit, niter, false))
1919     return false;
1920
1921   /* And of course, we must be able to duplicate the loop.  */
1922   if (!can_duplicate_loop_p (loop))
1923     return false;
1924
1925   /* The final loop should be small enough.  */
1926   if (tree_num_loop_insns (loop, &eni_size_weights) * factor
1927       > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
1928     return false;
1929
1930   return true;
1931 }
1932
1933 /* Base NAME and all the names in the chain of phi nodes that use it
1934    on variable VAR.  The phi nodes are recognized by being in the copies of
1935    the header of the LOOP.  */
1936
1937 static void
1938 base_names_in_chain_on (struct loop *loop, tree name, tree var)
1939 {
1940   gimple stmt, phi;
1941   imm_use_iterator iter;
1942   edge e;
1943
1944   SSA_NAME_VAR (name) = var;
1945
1946   while (1)
1947     {
1948       phi = NULL;
1949       FOR_EACH_IMM_USE_STMT (stmt, iter, name)
1950         {
1951           if (gimple_code (stmt) == GIMPLE_PHI
1952               && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1953             {
1954               phi = stmt;
1955               BREAK_FROM_IMM_USE_STMT (iter);
1956             }
1957         }
1958       if (!phi)
1959         return;
1960
1961       if (gimple_bb (phi) == loop->header)
1962         e = loop_latch_edge (loop);
1963       else
1964         e = single_pred_edge (gimple_bb (stmt));
1965
1966       name = PHI_RESULT (phi);
1967       SSA_NAME_VAR (name) = var;
1968     }
1969 }
1970
1971 /* Given an unrolled LOOP after predictive commoning, remove the
1972    register copies arising from phi nodes by changing the base
1973    variables of SSA names.  TMP_VARS is the set of the temporary variables
1974    for those we want to perform this.  */
1975
1976 static void
1977 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars)
1978 {
1979   edge e;
1980   gimple phi, stmt;
1981   tree name, use, var;
1982   gimple_stmt_iterator psi;
1983
1984   e = loop_latch_edge (loop);
1985   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1986     {
1987       phi = gsi_stmt (psi);
1988       name = PHI_RESULT (phi);
1989       var = SSA_NAME_VAR (name);
1990       if (!bitmap_bit_p (tmp_vars, DECL_UID (var)))
1991         continue;
1992       use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1993       gcc_assert (TREE_CODE (use) == SSA_NAME);
1994
1995       /* Base all the ssa names in the ud and du chain of NAME on VAR.  */
1996       stmt = SSA_NAME_DEF_STMT (use);
1997       while (gimple_code (stmt) == GIMPLE_PHI
1998              /* In case we could not unroll the loop enough to eliminate
1999                 all copies, we may reach the loop header before the defining
2000                 statement (in that case, some register copies will be present
2001                 in loop latch in the final code, corresponding to the newly
2002                 created looparound phi nodes).  */
2003              && gimple_bb (stmt) != loop->header)
2004         {
2005           gcc_assert (single_pred_p (gimple_bb (stmt)));
2006           use = PHI_ARG_DEF (stmt, 0);
2007           stmt = SSA_NAME_DEF_STMT (use);
2008         }
2009
2010       base_names_in_chain_on (loop, use, var);
2011     }
2012 }
2013
2014 /* Returns true if CHAIN is suitable to be combined.  */
2015
2016 static bool
2017 chain_can_be_combined_p (chain_p chain)
2018 {
2019   return (!chain->combined
2020           && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
2021 }
2022
2023 /* Returns the modify statement that uses NAME.  Skips over assignment
2024    statements, NAME is replaced with the actual name used in the returned
2025    statement.  */
2026
2027 static gimple
2028 find_use_stmt (tree *name)
2029 {
2030   gimple stmt;
2031   tree rhs, lhs;
2032
2033   /* Skip over assignments.  */
2034   while (1)
2035     {
2036       stmt = single_nonlooparound_use (*name);
2037       if (!stmt)
2038         return NULL;
2039
2040       if (gimple_code (stmt) != GIMPLE_ASSIGN)
2041         return NULL;
2042
2043       lhs = gimple_assign_lhs (stmt);
2044       if (TREE_CODE (lhs) != SSA_NAME)
2045         return NULL;
2046
2047       if (gimple_assign_copy_p (stmt))
2048         {
2049           rhs = gimple_assign_rhs1 (stmt);
2050           if (rhs != *name)
2051             return NULL;
2052
2053           *name = lhs;
2054         }
2055       else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
2056                == GIMPLE_BINARY_RHS)
2057         return stmt;
2058       else
2059         return NULL;
2060     }
2061 }
2062
2063 /* Returns true if we may perform reassociation for operation CODE in TYPE.  */
2064
2065 static bool
2066 may_reassociate_p (tree type, enum tree_code code)
2067 {
2068   if (FLOAT_TYPE_P (type)
2069       && !flag_unsafe_math_optimizations)
2070     return false;
2071
2072   return (commutative_tree_code (code)
2073           && associative_tree_code (code));
2074 }
2075
2076 /* If the operation used in STMT is associative and commutative, go through the
2077    tree of the same operations and returns its root.  Distance to the root
2078    is stored in DISTANCE.  */
2079
2080 static gimple
2081 find_associative_operation_root (gimple stmt, unsigned *distance)
2082 {
2083   tree lhs;
2084   gimple next;
2085   enum tree_code code = gimple_assign_rhs_code (stmt);
2086   tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2087   unsigned dist = 0;
2088
2089   if (!may_reassociate_p (type, code))
2090     return NULL;
2091
2092   while (1)
2093     {
2094       lhs = gimple_assign_lhs (stmt);
2095       gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2096
2097       next = find_use_stmt (&lhs);
2098       if (!next
2099           || gimple_assign_rhs_code (next) != code)
2100         break;
2101
2102       stmt = next;
2103       dist++;
2104     }
2105
2106   if (distance)
2107     *distance = dist;
2108   return stmt;
2109 }
2110
2111 /* Returns the common statement in that NAME1 and NAME2 have a use.  If there
2112    is no such statement, returns NULL_TREE.  In case the operation used on
2113    NAME1 and NAME2 is associative and commutative, returns the root of the
2114    tree formed by this operation instead of the statement that uses NAME1 or
2115    NAME2.  */
2116
2117 static gimple
2118 find_common_use_stmt (tree *name1, tree *name2)
2119 {
2120   gimple stmt1, stmt2;
2121
2122   stmt1 = find_use_stmt (name1);
2123   if (!stmt1)
2124     return NULL;
2125
2126   stmt2 = find_use_stmt (name2);
2127   if (!stmt2)
2128     return NULL;
2129
2130   if (stmt1 == stmt2)
2131     return stmt1;
2132
2133   stmt1 = find_associative_operation_root (stmt1, NULL);
2134   if (!stmt1)
2135     return NULL;
2136   stmt2 = find_associative_operation_root (stmt2, NULL);
2137   if (!stmt2)
2138     return NULL;
2139
2140   return (stmt1 == stmt2 ? stmt1 : NULL);
2141 }
2142
2143 /* Checks whether R1 and R2 are combined together using CODE, with the result
2144    in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2145    if it is true.  If CODE is ERROR_MARK, set these values instead.  */
2146
2147 static bool
2148 combinable_refs_p (dref r1, dref r2,
2149                    enum tree_code *code, bool *swap, tree *rslt_type)
2150 {
2151   enum tree_code acode;
2152   bool aswap;
2153   tree atype;
2154   tree name1, name2;
2155   gimple stmt;
2156
2157   name1 = name_for_ref (r1);
2158   name2 = name_for_ref (r2);
2159   gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2160
2161   stmt = find_common_use_stmt (&name1, &name2);
2162
2163   if (!stmt)
2164     return false;
2165
2166   acode = gimple_assign_rhs_code (stmt);
2167   aswap = (!commutative_tree_code (acode)
2168            && gimple_assign_rhs1 (stmt) != name1);
2169   atype = TREE_TYPE (gimple_assign_lhs (stmt));
2170
2171   if (*code == ERROR_MARK)
2172     {
2173       *code = acode;
2174       *swap = aswap;
2175       *rslt_type = atype;
2176       return true;
2177     }
2178
2179   return (*code == acode
2180           && *swap == aswap
2181           && *rslt_type == atype);
2182 }
2183
2184 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2185    an assignment of the remaining operand.  */
2186
2187 static void
2188 remove_name_from_operation (gimple stmt, tree op)
2189 {
2190   tree other_op;
2191   gimple_stmt_iterator si;
2192
2193   gcc_assert (is_gimple_assign (stmt));
2194
2195   if (gimple_assign_rhs1 (stmt) == op)
2196     other_op = gimple_assign_rhs2 (stmt);
2197   else
2198     other_op = gimple_assign_rhs1 (stmt);
2199
2200   si = gsi_for_stmt (stmt);
2201   gimple_assign_set_rhs_from_tree (&si, other_op);
2202
2203   /* We should not have reallocated STMT.  */
2204   gcc_assert (gsi_stmt (si) == stmt);
2205
2206   update_stmt (stmt);
2207 }
2208
2209 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2210    are combined in a single statement, and returns this statement.  */
2211
2212 static gimple
2213 reassociate_to_the_same_stmt (tree name1, tree name2)
2214 {
2215   gimple stmt1, stmt2, root1, root2, s1, s2;
2216   gimple new_stmt, tmp_stmt;
2217   tree new_name, tmp_name, var, r1, r2;
2218   unsigned dist1, dist2;
2219   enum tree_code code;
2220   tree type = TREE_TYPE (name1);
2221   gimple_stmt_iterator bsi;
2222
2223   stmt1 = find_use_stmt (&name1);
2224   stmt2 = find_use_stmt (&name2);
2225   root1 = find_associative_operation_root (stmt1, &dist1);
2226   root2 = find_associative_operation_root (stmt2, &dist2);
2227   code = gimple_assign_rhs_code (stmt1);
2228
2229   gcc_assert (root1 && root2 && root1 == root2
2230               && code == gimple_assign_rhs_code (stmt2));
2231
2232   /* Find the root of the nearest expression in that both NAME1 and NAME2
2233      are used.  */
2234   r1 = name1;
2235   s1 = stmt1;
2236   r2 = name2;
2237   s2 = stmt2;
2238
2239   while (dist1 > dist2)
2240     {
2241       s1 = find_use_stmt (&r1);
2242       r1 = gimple_assign_lhs (s1);
2243       dist1--;
2244     }
2245   while (dist2 > dist1)
2246     {
2247       s2 = find_use_stmt (&r2);
2248       r2 = gimple_assign_lhs (s2);
2249       dist2--;
2250     }
2251
2252   while (s1 != s2)
2253     {
2254       s1 = find_use_stmt (&r1);
2255       r1 = gimple_assign_lhs (s1);
2256       s2 = find_use_stmt (&r2);
2257       r2 = gimple_assign_lhs (s2);
2258     }
2259
2260   /* Remove NAME1 and NAME2 from the statements in that they are used
2261      currently.  */
2262   remove_name_from_operation (stmt1, name1);
2263   remove_name_from_operation (stmt2, name2);
2264
2265   /* Insert the new statement combining NAME1 and NAME2 before S1, and
2266      combine it with the rhs of S1.  */
2267   var = create_tmp_var (type, "predreastmp");
2268   add_referenced_var (var);
2269   new_name = make_ssa_name (var, NULL);
2270   new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2);
2271
2272   var = create_tmp_var (type, "predreastmp");
2273   add_referenced_var (var);
2274   tmp_name = make_ssa_name (var, NULL);
2275
2276   /* Rhs of S1 may now be either a binary expression with operation
2277      CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2278      so that name1 or name2 was removed from it).  */
2279   tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1),
2280                                            tmp_name,
2281                                            gimple_assign_rhs1 (s1),
2282                                            gimple_assign_rhs2 (s1));
2283
2284   bsi = gsi_for_stmt (s1);
2285   gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2286   s1 = gsi_stmt (bsi);
2287   update_stmt (s1);
2288
2289   gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2290   gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2291
2292   return new_stmt;
2293 }
2294
2295 /* Returns the statement that combines references R1 and R2.  In case R1
2296    and R2 are not used in the same statement, but they are used with an
2297    associative and commutative operation in the same expression, reassociate
2298    the expression so that they are used in the same statement.  */
2299
2300 static gimple
2301 stmt_combining_refs (dref r1, dref r2)
2302 {
2303   gimple stmt1, stmt2;
2304   tree name1 = name_for_ref (r1);
2305   tree name2 = name_for_ref (r2);
2306
2307   stmt1 = find_use_stmt (&name1);
2308   stmt2 = find_use_stmt (&name2);
2309   if (stmt1 == stmt2)
2310     return stmt1;
2311
2312   return reassociate_to_the_same_stmt (name1, name2);
2313 }
2314
2315 /* Tries to combine chains CH1 and CH2 together.  If this succeeds, the
2316    description of the new chain is returned, otherwise we return NULL.  */
2317
2318 static chain_p
2319 combine_chains (chain_p ch1, chain_p ch2)
2320 {
2321   dref r1, r2, nw;
2322   enum tree_code op = ERROR_MARK;
2323   bool swap = false;
2324   chain_p new_chain;
2325   unsigned i;
2326   gimple root_stmt;
2327   tree rslt_type = NULL_TREE;
2328
2329   if (ch1 == ch2)
2330     return false;
2331   if (ch1->length != ch2->length)
2332     return NULL;
2333
2334   if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs))
2335     return NULL;
2336
2337   for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2338                && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2339     {
2340       if (r1->distance != r2->distance)
2341         return NULL;
2342
2343       if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2344         return NULL;
2345     }
2346
2347   if (swap)
2348     {
2349       chain_p tmp = ch1;
2350       ch1 = ch2;
2351       ch2 = tmp;
2352     }
2353
2354   new_chain = XCNEW (struct chain);
2355   new_chain->type = CT_COMBINATION;
2356   new_chain->op = op;
2357   new_chain->ch1 = ch1;
2358   new_chain->ch2 = ch2;
2359   new_chain->rslt_type = rslt_type;
2360   new_chain->length = ch1->length;
2361
2362   for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2363                && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2364     {
2365       nw = XCNEW (struct dref);
2366       nw->stmt = stmt_combining_refs (r1, r2);
2367       nw->distance = r1->distance;
2368
2369       VEC_safe_push (dref, heap, new_chain->refs, nw);
2370     }
2371
2372   new_chain->has_max_use_after = false;
2373   root_stmt = get_chain_root (new_chain)->stmt;
2374   for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++)
2375     {
2376       if (nw->distance == new_chain->length
2377           && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2378         {
2379           new_chain->has_max_use_after = true;
2380           break;
2381         }
2382     }
2383
2384   ch1->combined = true;
2385   ch2->combined = true;
2386   return new_chain;
2387 }
2388
2389 /* Try to combine the CHAINS.  */
2390
2391 static void
2392 try_combine_chains (VEC (chain_p, heap) **chains)
2393 {
2394   unsigned i, j;
2395   chain_p ch1, ch2, cch;
2396   VEC (chain_p, heap) *worklist = NULL;
2397
2398   for (i = 0; VEC_iterate (chain_p, *chains, i, ch1); i++)
2399     if (chain_can_be_combined_p (ch1))
2400       VEC_safe_push (chain_p, heap, worklist, ch1);
2401
2402   while (!VEC_empty (chain_p, worklist))
2403     {
2404       ch1 = VEC_pop (chain_p, worklist);
2405       if (!chain_can_be_combined_p (ch1))
2406         continue;
2407
2408       for (j = 0; VEC_iterate (chain_p, *chains, j, ch2); j++)
2409         {
2410           if (!chain_can_be_combined_p (ch2))
2411             continue;
2412
2413           cch = combine_chains (ch1, ch2);
2414           if (cch)
2415             {
2416               VEC_safe_push (chain_p, heap, worklist, cch);
2417               VEC_safe_push (chain_p, heap, *chains, cch);
2418               break;
2419             }
2420         }
2421     }
2422 }
2423
2424 /* Sets alias information based on data reference DR for REF,
2425    if necessary.  */
2426
2427 static void
2428 set_alias_info (tree ref, struct data_reference *dr)
2429 {
2430   tree var;
2431   tree tag = DR_SYMBOL_TAG (dr);
2432
2433   gcc_assert (tag != NULL_TREE);
2434
2435   ref = get_base_address (ref);
2436   if (!ref || !INDIRECT_REF_P (ref))
2437     return;
2438
2439   var = SSA_NAME_VAR (TREE_OPERAND (ref, 0));
2440   if (var_ann (var)->symbol_mem_tag)
2441     return;
2442
2443   if (!MTAG_P (tag))
2444     new_type_alias (var, tag, ref);
2445   else
2446     var_ann (var)->symbol_mem_tag = tag;
2447 }
2448
2449 /* Prepare initializers for CHAIN in LOOP.  Returns false if this is
2450    impossible because one of these initializers may trap, true otherwise.  */
2451
2452 static bool
2453 prepare_initializers_chain (struct loop *loop, chain_p chain)
2454 {
2455   unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2456   struct data_reference *dr = get_chain_root (chain)->ref;
2457   tree init;
2458   gimple_seq stmts;
2459   dref laref;
2460   edge entry = loop_preheader_edge (loop);
2461
2462   /* Find the initializers for the variables, and check that they cannot
2463      trap.  */
2464   chain->inits = VEC_alloc (tree, heap, n);
2465   for (i = 0; i < n; i++)
2466     VEC_quick_push (tree, chain->inits, NULL_TREE);
2467
2468   /* If we have replaced some looparound phi nodes, use their initializers
2469      instead of creating our own.  */
2470   for (i = 0; VEC_iterate (dref, chain->refs, i, laref); i++)
2471     {
2472       if (gimple_code (laref->stmt) != GIMPLE_PHI)
2473         continue;
2474
2475       gcc_assert (laref->distance > 0);
2476       VEC_replace (tree, chain->inits, n - laref->distance,
2477                    PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry));
2478     }
2479
2480   for (i = 0; i < n; i++)
2481     {
2482       if (VEC_index (tree, chain->inits, i) != NULL_TREE)
2483         continue;
2484
2485       init = ref_at_iteration (loop, DR_REF (dr), (int) i - n);
2486       if (!init)
2487         return false;
2488
2489       if (!chain->all_always_accessed && tree_could_trap_p (init))
2490         return false;
2491
2492       init = force_gimple_operand (init, &stmts, false, NULL_TREE);
2493       if (stmts)
2494         {
2495           mark_virtual_ops_for_renaming_list (stmts);
2496           gsi_insert_seq_on_edge_immediate (entry, stmts);
2497         }
2498       set_alias_info (init, dr);
2499
2500       VEC_replace (tree, chain->inits, i, init);
2501     }
2502
2503   return true;
2504 }
2505
2506 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2507    be used because the initializers might trap.  */
2508
2509 static void
2510 prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains)
2511 {
2512   chain_p chain;
2513   unsigned i;
2514
2515   for (i = 0; i < VEC_length (chain_p, chains); )
2516     {
2517       chain = VEC_index (chain_p, chains, i);
2518       if (prepare_initializers_chain (loop, chain))
2519         i++;
2520       else
2521         {
2522           release_chain (chain);
2523           VEC_unordered_remove (chain_p, chains, i);
2524         }
2525     }
2526 }
2527
2528 /* Performs predictive commoning for LOOP.  Returns true if LOOP was
2529    unrolled.  */
2530
2531 static bool
2532 tree_predictive_commoning_loop (struct loop *loop)
2533 {
2534   VEC (data_reference_p, heap) *datarefs;
2535   VEC (ddr_p, heap) *dependences;
2536   struct component *components;
2537   VEC (chain_p, heap) *chains = NULL;
2538   unsigned unroll_factor;
2539   struct tree_niter_desc desc;
2540   bool unroll = false;
2541   edge exit;
2542   bitmap tmp_vars;
2543
2544   if (dump_file && (dump_flags & TDF_DETAILS))
2545     fprintf (dump_file, "Processing loop %d\n",  loop->num);
2546
2547   /* Find the data references and split them into components according to their
2548      dependence relations.  */
2549   datarefs = VEC_alloc (data_reference_p, heap, 10);
2550   dependences = VEC_alloc (ddr_p, heap, 10);
2551   compute_data_dependences_for_loop (loop, true, &datarefs, &dependences);
2552   if (dump_file && (dump_flags & TDF_DETAILS))
2553     dump_data_dependence_relations (dump_file, dependences);
2554
2555   components = split_data_refs_to_components (loop, datarefs, dependences);
2556   free_dependence_relations (dependences);
2557   if (!components)
2558     {
2559       free_data_refs (datarefs);
2560       return false;
2561     }
2562
2563   if (dump_file && (dump_flags & TDF_DETAILS))
2564     {
2565       fprintf (dump_file, "Initial state:\n\n");
2566       dump_components (dump_file, components);
2567     }
2568
2569   /* Find the suitable components and split them into chains.  */
2570   components = filter_suitable_components (loop, components);
2571
2572   tmp_vars = BITMAP_ALLOC (NULL);
2573   looparound_phis = BITMAP_ALLOC (NULL);
2574   determine_roots (loop, components, &chains);
2575   release_components (components);
2576
2577   if (!chains)
2578     {
2579       if (dump_file && (dump_flags & TDF_DETAILS))
2580         fprintf (dump_file,
2581                  "Predictive commoning failed: no suitable chains\n");
2582       goto end;
2583     }
2584   prepare_initializers (loop, chains);
2585
2586   /* Try to combine the chains that are always worked with together.  */
2587   try_combine_chains (&chains);
2588
2589   if (dump_file && (dump_flags & TDF_DETAILS))
2590     {
2591       fprintf (dump_file, "Before commoning:\n\n");
2592       dump_chains (dump_file, chains);
2593     }
2594
2595   /* Determine the unroll factor, and if the loop should be unrolled, ensure
2596      that its number of iterations is divisible by the factor.  */
2597   unroll_factor = determine_unroll_factor (chains);
2598   scev_reset ();
2599   unroll = should_unroll_loop_p (loop, unroll_factor, &desc);
2600   exit = single_dom_exit (loop);
2601
2602   /* Execute the predictive commoning transformations, and possibly unroll the
2603      loop.  */
2604   if (unroll)
2605     {
2606       struct epcc_data dta;
2607
2608       if (dump_file && (dump_flags & TDF_DETAILS))
2609         fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2610
2611       dta.chains = chains;
2612       dta.tmp_vars = tmp_vars;
2613
2614       update_ssa (TODO_update_ssa_only_virtuals);
2615
2616       /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2617          execute_pred_commoning_cbck is called may cause phi nodes to be
2618          reallocated, which is a problem since CHAINS may point to these
2619          statements.  To fix this, we store the ssa names defined by the
2620          phi nodes here instead of the phi nodes themselves, and restore
2621          the phi nodes in execute_pred_commoning_cbck.  A bit hacky.  */
2622       replace_phis_by_defined_names (chains);
2623
2624       tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2625                                       execute_pred_commoning_cbck, &dta);
2626       eliminate_temp_copies (loop, tmp_vars);
2627     }
2628   else
2629     {
2630       if (dump_file && (dump_flags & TDF_DETAILS))
2631         fprintf (dump_file,
2632                  "Executing predictive commoning without unrolling.\n");
2633       execute_pred_commoning (loop, chains, tmp_vars);
2634     }
2635
2636 end: ;
2637   release_chains (chains);
2638   free_data_refs (datarefs);
2639   BITMAP_FREE (tmp_vars);
2640   BITMAP_FREE (looparound_phis);
2641
2642   free_affine_expand_cache (&name_expansions);
2643
2644   return unroll;
2645 }
2646
2647 /* Runs predictive commoning.  */
2648
2649 unsigned
2650 tree_predictive_commoning (void)
2651 {
2652   bool unrolled = false;
2653   struct loop *loop;
2654   loop_iterator li;
2655   unsigned ret = 0;
2656
2657   initialize_original_copy_tables ();
2658   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
2659     if (optimize_loop_for_speed_p (loop))
2660       {
2661         unrolled |= tree_predictive_commoning_loop (loop);
2662       }
2663
2664   if (unrolled)
2665     {
2666       scev_reset ();
2667       ret = TODO_cleanup_cfg;
2668     }
2669   free_original_copy_tables ();
2670
2671   return ret;
2672 }