gcc/tree-predcom.c

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