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