gcc/tree-predcom.c

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