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 operator;
 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->operator),
 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.  If SET is true, NEW 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, 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);
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, just replace the use of OLD.  */
1260   if (!set)
1261     {
1262       gcc_assert (!in_lhs);
1263       gimple_assign_set_rhs_from_tree (&bsi, new);
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, 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->operator, 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_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
1731       if (!next
1732           || !gimple_assign_copy_p (next)
1733           || gimple_assign_rhs1 (next) != name)
1734         return;
1735
1736       stmt = next;
1737     }
1738 }
1739
1740 /* Perform the predictive commoning optimization for a chain CHAIN.
1741    Uids of the newly created temporary variables are marked in TMP_VARS.*/
1742
1743 static void
1744 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
1745                              bitmap tmp_vars)
1746 {
1747   unsigned i;
1748   dref a, root;
1749   tree var;
1750
1751   if (chain->combined)
1752     {
1753       /* For combined chains, just remove the statements that are used to
1754          compute the values of the expression (except for the root one).  */
1755       for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1756         remove_stmt (a->stmt);
1757     }
1758   else
1759     {
1760       /* For non-combined chains, set up the variables that hold its value,
1761          and replace the uses of the original references by these
1762          variables.  */
1763       root = get_chain_root (chain);
1764       mark_virtual_ops_for_renaming (root->stmt);
1765
1766       initialize_root (loop, chain, tmp_vars);
1767       for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1768         {
1769           mark_virtual_ops_for_renaming (a->stmt);
1770           var = VEC_index (tree, chain->vars, chain->length - a->distance);
1771           replace_ref_with (a->stmt, var, false, false);
1772         }
1773     }
1774 }
1775
1776 /* Determines the unroll factor necessary to remove as many temporary variable
1777    copies as possible.  CHAINS is the list of chains that will be
1778    optimized.  */
1779
1780 static unsigned
1781 determine_unroll_factor (VEC (chain_p, heap) *chains)
1782 {
1783   chain_p chain;
1784   unsigned factor = 1, af, nfactor, i;
1785   unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1786
1787   for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1788     {
1789       if (chain->type == CT_INVARIANT || chain->combined)
1790         continue;
1791
1792       /* The best unroll factor for this chain is equal to the number of
1793          temporary variables that we create for it.  */
1794       af = chain->length;
1795       if (chain->has_max_use_after)
1796         af++;
1797
1798       nfactor = factor * af / gcd (factor, af);
1799       if (nfactor <= max)
1800         factor = nfactor;
1801     }
1802
1803   return factor;
1804 }
1805
1806 /* Perform the predictive commoning optimization for CHAINS.
1807    Uids of the newly created temporary variables are marked in TMP_VARS.  */
1808
1809 static void
1810 execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains,
1811                         bitmap tmp_vars)
1812 {
1813   chain_p chain;
1814   unsigned i;
1815
1816   for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1817     {
1818       if (chain->type == CT_INVARIANT)
1819         execute_load_motion (loop, chain, tmp_vars);
1820       else
1821         execute_pred_commoning_chain (loop, chain, tmp_vars);
1822     }
1823
1824   update_ssa (TODO_update_ssa_only_virtuals);
1825 }
1826
1827 /* For each reference in CHAINS, if its defining statement is
1828    phi node, record the ssa name that is defined by it.  */
1829
1830 static void
1831 replace_phis_by_defined_names (VEC (chain_p, heap) *chains)
1832 {
1833   chain_p chain;
1834   dref a;
1835   unsigned i, j;
1836
1837   for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1838     for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1839       {
1840         if (gimple_code (a->stmt) == GIMPLE_PHI)
1841           {
1842             a->name_defined_by_phi = PHI_RESULT (a->stmt);
1843             a->stmt = NULL;
1844           }
1845       }
1846 }
1847
1848 /* For each reference in CHAINS, if name_defined_by_phi is not
1849    NULL, use it to set the stmt field.  */
1850
1851 static void
1852 replace_names_by_phis (VEC (chain_p, heap) *chains)
1853 {
1854   chain_p chain;
1855   dref a;
1856   unsigned i, j;
1857
1858   for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1859     for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1860       if (a->stmt == NULL)
1861         {
1862           a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
1863           gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
1864           a->name_defined_by_phi = NULL_TREE;
1865         }
1866 }
1867
1868 /* Wrapper over execute_pred_commoning, to pass it as a callback
1869    to tree_transform_and_unroll_loop.  */
1870
1871 struct epcc_data
1872 {
1873   VEC (chain_p, heap) *chains;
1874   bitmap tmp_vars;
1875 };
1876
1877 static void
1878 execute_pred_commoning_cbck (struct loop *loop, void *data)
1879 {
1880   struct epcc_data *const dta = (struct epcc_data *) data;
1881
1882   /* Restore phi nodes that were replaced by ssa names before
1883      tree_transform_and_unroll_loop (see detailed description in
1884      tree_predictive_commoning_loop).  */
1885   replace_names_by_phis (dta->chains);
1886   execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
1887 }
1888
1889 /* Returns true if we can and should unroll LOOP FACTOR times.  Number
1890    of iterations of the loop is returned in NITER.  */
1891
1892 static bool
1893 should_unroll_loop_p (struct loop *loop, unsigned factor,
1894                       struct tree_niter_desc *niter)
1895 {
1896   edge exit;
1897
1898   if (factor == 1)
1899     return false;
1900
1901   /* Check whether unrolling is possible.  We only want to unroll loops
1902      for that we are able to determine number of iterations.  We also
1903      want to split the extra iterations of the loop from its end,
1904      therefore we require that the loop has precisely one
1905      exit.  */
1906
1907   exit = single_dom_exit (loop);
1908   if (!exit)
1909     return false;
1910
1911   if (!number_of_iterations_exit (loop, exit, niter, false))
1912     return false;
1913
1914   /* And of course, we must be able to duplicate the loop.  */
1915   if (!can_duplicate_loop_p (loop))
1916     return false;
1917
1918   /* The final loop should be small enough.  */
1919   if (tree_num_loop_insns (loop, &eni_size_weights) * factor
1920       > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
1921     return false;
1922
1923   return true;
1924 }
1925
1926 /* Base NAME and all the names in the chain of phi nodes that use it
1927    on variable VAR.  The phi nodes are recognized by being in the copies of
1928    the header of the LOOP.  */
1929
1930 static void
1931 base_names_in_chain_on (struct loop *loop, tree name, tree var)
1932 {
1933   gimple stmt, phi;
1934   imm_use_iterator iter;
1935   edge e;
1936
1937   SSA_NAME_VAR (name) = var;
1938
1939   while (1)
1940     {
1941       phi = NULL;
1942       FOR_EACH_IMM_USE_STMT (stmt, iter, name)
1943         {
1944           if (gimple_code (stmt) == GIMPLE_PHI
1945               && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1946             {
1947               phi = stmt;
1948               BREAK_FROM_IMM_USE_STMT (iter);
1949             }
1950         }
1951       if (!phi)
1952         return;
1953
1954       if (gimple_bb (phi) == loop->header)
1955         e = loop_latch_edge (loop);
1956       else
1957         e = single_pred_edge (gimple_bb (stmt));
1958
1959       name = PHI_RESULT (phi);
1960       SSA_NAME_VAR (name) = var;
1961     }
1962 }
1963
1964 /* Given an unrolled LOOP after predictive commoning, remove the
1965    register copies arising from phi nodes by changing the base
1966    variables of SSA names.  TMP_VARS is the set of the temporary variables
1967    for those we want to perform this.  */
1968
1969 static void
1970 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars)
1971 {
1972   edge e;
1973   gimple phi, stmt;
1974   tree name, use, var;
1975   gimple_stmt_iterator psi;
1976
1977   e = loop_latch_edge (loop);
1978   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1979     {
1980       phi = gsi_stmt (psi);
1981       name = PHI_RESULT (phi);
1982       var = SSA_NAME_VAR (name);
1983       if (!bitmap_bit_p (tmp_vars, DECL_UID (var)))
1984         continue;
1985       use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1986       gcc_assert (TREE_CODE (use) == SSA_NAME);
1987
1988       /* Base all the ssa names in the ud and du chain of NAME on VAR.  */
1989       stmt = SSA_NAME_DEF_STMT (use);
1990       while (gimple_code (stmt) == GIMPLE_PHI
1991              /* In case we could not unroll the loop enough to eliminate
1992                 all copies, we may reach the loop header before the defining
1993                 statement (in that case, some register copies will be present
1994                 in loop latch in the final code, corresponding to the newly
1995                 created looparound phi nodes).  */
1996              && gimple_bb (stmt) != loop->header)
1997         {
1998           gcc_assert (single_pred_p (gimple_bb (stmt)));
1999           use = PHI_ARG_DEF (stmt, 0);
2000           stmt = SSA_NAME_DEF_STMT (use);
2001         }
2002
2003       base_names_in_chain_on (loop, use, var);
2004     }
2005 }
2006
2007 /* Returns true if CHAIN is suitable to be combined.  */
2008
2009 static bool
2010 chain_can_be_combined_p (chain_p chain)
2011 {
2012   return (!chain->combined
2013           && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
2014 }
2015
2016 /* Returns the modify statement that uses NAME.  Skips over assignment
2017    statements, NAME is replaced with the actual name used in the returned
2018    statement.  */
2019
2020 static gimple
2021 find_use_stmt (tree *name)
2022 {
2023   gimple stmt;
2024   tree rhs, lhs;
2025
2026   /* Skip over assignments.  */
2027   while (1)
2028     {
2029       stmt = single_nonlooparound_use (*name);
2030       if (!stmt)
2031         return NULL;
2032
2033       if (gimple_code (stmt) != GIMPLE_ASSIGN)
2034         return NULL;
2035
2036       lhs = gimple_assign_lhs (stmt);
2037       if (TREE_CODE (lhs) != SSA_NAME)
2038         return NULL;
2039
2040       if (gimple_assign_copy_p (stmt))
2041         {
2042           rhs = gimple_assign_rhs1 (stmt);
2043           if (rhs != *name)
2044             return NULL;
2045
2046           *name = lhs;
2047         }
2048       else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
2049                == GIMPLE_BINARY_RHS)
2050         return stmt;
2051       else
2052         return NULL;
2053     }
2054 }
2055
2056 /* Returns true if we may perform reassociation for operation CODE in TYPE.  */
2057
2058 static bool
2059 may_reassociate_p (tree type, enum tree_code code)
2060 {
2061   if (FLOAT_TYPE_P (type)
2062       && !flag_unsafe_math_optimizations)
2063     return false;
2064
2065   return (commutative_tree_code (code)
2066           && associative_tree_code (code));
2067 }
2068
2069 /* If the operation used in STMT is associative and commutative, go through the
2070    tree of the same operations and returns its root.  Distance to the root
2071    is stored in DISTANCE.  */
2072
2073 static gimple
2074 find_associative_operation_root (gimple stmt, unsigned *distance)
2075 {
2076   tree lhs;
2077   gimple next;
2078   enum tree_code code = gimple_assign_rhs_code (stmt);
2079   tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2080   unsigned dist = 0;
2081
2082   if (!may_reassociate_p (type, code))
2083     return NULL;
2084
2085   while (1)
2086     {
2087       lhs = gimple_assign_lhs (stmt);
2088       gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2089
2090       next = find_use_stmt (&lhs);
2091       if (!next
2092           || gimple_assign_rhs_code (next) != code)
2093         break;
2094
2095       stmt = next;
2096       dist++;
2097     }
2098
2099   if (distance)
2100     *distance = dist;
2101   return stmt;
2102 }
2103
2104 /* Returns the common statement in that NAME1 and NAME2 have a use.  If there
2105    is no such statement, returns NULL_TREE.  In case the operation used on
2106    NAME1 and NAME2 is associative and commutative, returns the root of the
2107    tree formed by this operation instead of the statement that uses NAME1 or
2108    NAME2.  */
2109
2110 static gimple
2111 find_common_use_stmt (tree *name1, tree *name2)
2112 {
2113   gimple stmt1, stmt2;
2114
2115   stmt1 = find_use_stmt (name1);
2116   if (!stmt1)
2117     return NULL;
2118
2119   stmt2 = find_use_stmt (name2);
2120   if (!stmt2)
2121     return NULL;
2122
2123   if (stmt1 == stmt2)
2124     return stmt1;
2125
2126   stmt1 = find_associative_operation_root (stmt1, NULL);
2127   if (!stmt1)
2128     return NULL;
2129   stmt2 = find_associative_operation_root (stmt2, NULL);
2130   if (!stmt2)
2131     return NULL;
2132
2133   return (stmt1 == stmt2 ? stmt1 : NULL);
2134 }
2135
2136 /* Checks whether R1 and R2 are combined together using CODE, with the result
2137    in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2138    if it is true.  If CODE is ERROR_MARK, set these values instead.  */
2139
2140 static bool
2141 combinable_refs_p (dref r1, dref r2,
2142                    enum tree_code *code, bool *swap, tree *rslt_type)
2143 {
2144   enum tree_code acode;
2145   bool aswap;
2146   tree atype;
2147   tree name1, name2;
2148   gimple stmt;
2149
2150   name1 = name_for_ref (r1);
2151   name2 = name_for_ref (r2);
2152   gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2153
2154   stmt = find_common_use_stmt (&name1, &name2);
2155
2156   if (!stmt)
2157     return false;
2158
2159   acode = gimple_assign_rhs_code (stmt);
2160   aswap = (!commutative_tree_code (acode)
2161            && gimple_assign_rhs1 (stmt) != name1);
2162   atype = TREE_TYPE (gimple_assign_lhs (stmt));
2163
2164   if (*code == ERROR_MARK)
2165     {
2166       *code = acode;
2167       *swap = aswap;
2168       *rslt_type = atype;
2169       return true;
2170     }
2171
2172   return (*code == acode
2173           && *swap == aswap
2174           && *rslt_type == atype);
2175 }
2176
2177 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2178    an assignment of the remaining operand.  */
2179
2180 static void
2181 remove_name_from_operation (gimple stmt, tree op)
2182 {
2183   tree other_op;
2184   gimple_stmt_iterator si;
2185
2186   gcc_assert (is_gimple_assign (stmt));
2187
2188   if (gimple_assign_rhs1 (stmt) == op)
2189     other_op = gimple_assign_rhs2 (stmt);
2190   else
2191     other_op = gimple_assign_rhs1 (stmt);
2192
2193   si = gsi_for_stmt (stmt);
2194   gimple_assign_set_rhs_from_tree (&si, other_op);
2195
2196   /* We should not have reallocated STMT.  */
2197   gcc_assert (gsi_stmt (si) == stmt);
2198
2199   update_stmt (stmt);
2200 }
2201
2202 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2203    are combined in a single statement, and returns this statement.  */
2204
2205 static gimple
2206 reassociate_to_the_same_stmt (tree name1, tree name2)
2207 {
2208   gimple stmt1, stmt2, root1, root2, s1, s2;
2209   gimple new_stmt, tmp_stmt;
2210   tree new_name, tmp_name, var, r1, r2;
2211   unsigned dist1, dist2;
2212   enum tree_code code;
2213   tree type = TREE_TYPE (name1);
2214   gimple_stmt_iterator bsi;
2215
2216   stmt1 = find_use_stmt (&name1);
2217   stmt2 = find_use_stmt (&name2);
2218   root1 = find_associative_operation_root (stmt1, &dist1);
2219   root2 = find_associative_operation_root (stmt2, &dist2);
2220   code = gimple_assign_rhs_code (stmt1);
2221
2222   gcc_assert (root1 && root2 && root1 == root2
2223               && code == gimple_assign_rhs_code (stmt2));
2224
2225   /* Find the root of the nearest expression in that both NAME1 and NAME2
2226      are used.  */
2227   r1 = name1;
2228   s1 = stmt1;
2229   r2 = name2;
2230   s2 = stmt2;
2231
2232   while (dist1 > dist2)
2233     {
2234       s1 = find_use_stmt (&r1);
2235       r1 = gimple_assign_lhs (s1);
2236       dist1--;
2237     }
2238   while (dist2 > dist1)
2239     {
2240       s2 = find_use_stmt (&r2);
2241       r2 = gimple_assign_lhs (s2);
2242       dist2--;
2243     }
2244
2245   while (s1 != s2)
2246     {
2247       s1 = find_use_stmt (&r1);
2248       r1 = gimple_assign_lhs (s1);
2249       s2 = find_use_stmt (&r2);
2250       r2 = gimple_assign_lhs (s2);
2251     }
2252
2253   /* Remove NAME1 and NAME2 from the statements in that they are used
2254      currently.  */
2255   remove_name_from_operation (stmt1, name1);
2256   remove_name_from_operation (stmt2, name2);
2257
2258   /* Insert the new statement combining NAME1 and NAME2 before S1, and
2259      combine it with the rhs of S1.  */
2260   var = create_tmp_var (type, "predreastmp");
2261   add_referenced_var (var);
2262   new_name = make_ssa_name (var, NULL);
2263   new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2);
2264
2265   var = create_tmp_var (type, "predreastmp");
2266   add_referenced_var (var);
2267   tmp_name = make_ssa_name (var, NULL);
2268
2269   /* Rhs of S1 may now be either a binary expression with operation
2270      CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2271      so that name1 or name2 was removed from it).  */
2272   tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1),
2273                                            tmp_name,
2274                                            gimple_assign_rhs1 (s1),
2275                                            gimple_assign_rhs2 (s1));
2276
2277   bsi = gsi_for_stmt (s1);
2278   gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2279   s1 = gsi_stmt (bsi);
2280   update_stmt (s1);
2281
2282   gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2283   gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2284
2285   return new_stmt;
2286 }
2287
2288 /* Returns the statement that combines references R1 and R2.  In case R1
2289    and R2 are not used in the same statement, but they are used with an
2290    associative and commutative operation in the same expression, reassociate
2291    the expression so that they are used in the same statement.  */
2292
2293 static gimple
2294 stmt_combining_refs (dref r1, dref r2)
2295 {
2296   gimple stmt1, stmt2;
2297   tree name1 = name_for_ref (r1);
2298   tree name2 = name_for_ref (r2);
2299
2300   stmt1 = find_use_stmt (&name1);
2301   stmt2 = find_use_stmt (&name2);
2302   if (stmt1 == stmt2)
2303     return stmt1;
2304
2305   return reassociate_to_the_same_stmt (name1, name2);
2306 }
2307
2308 /* Tries to combine chains CH1 and CH2 together.  If this succeeds, the
2309    description of the new chain is returned, otherwise we return NULL.  */
2310
2311 static chain_p
2312 combine_chains (chain_p ch1, chain_p ch2)
2313 {
2314   dref r1, r2, nw;
2315   enum tree_code op = ERROR_MARK;
2316   bool swap = false;
2317   chain_p new_chain;
2318   unsigned i;
2319   gimple root_stmt;
2320   tree rslt_type = NULL_TREE;
2321
2322   if (ch1 == ch2)
2323     return false;
2324   if (ch1->length != ch2->length)
2325     return NULL;
2326
2327   if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs))
2328     return NULL;
2329
2330   for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2331                && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2332     {
2333       if (r1->distance != r2->distance)
2334         return NULL;
2335
2336       if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2337         return NULL;
2338     }
2339
2340   if (swap)
2341     {
2342       chain_p tmp = ch1;
2343       ch1 = ch2;
2344       ch2 = tmp;
2345     }
2346
2347   new_chain = XCNEW (struct chain);
2348   new_chain->type = CT_COMBINATION;
2349   new_chain->operator = op;
2350   new_chain->ch1 = ch1;
2351   new_chain->ch2 = ch2;
2352   new_chain->rslt_type = rslt_type;
2353   new_chain->length = ch1->length;
2354
2355   for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2356                && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2357     {
2358       nw = XCNEW (struct dref);
2359       nw->stmt = stmt_combining_refs (r1, r2);
2360       nw->distance = r1->distance;
2361
2362       VEC_safe_push (dref, heap, new_chain->refs, nw);
2363     }
2364
2365   new_chain->has_max_use_after = false;
2366   root_stmt = get_chain_root (new_chain)->stmt;
2367   for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++)
2368     {
2369       if (nw->distance == new_chain->length
2370           && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2371         {
2372           new_chain->has_max_use_after = true;
2373           break;
2374         }
2375     }
2376
2377   ch1->combined = true;
2378   ch2->combined = true;
2379   return new_chain;
2380 }
2381
2382 /* Try to combine the CHAINS.  */
2383
2384 static void
2385 try_combine_chains (VEC (chain_p, heap) **chains)
2386 {
2387   unsigned i, j;
2388   chain_p ch1, ch2, cch;
2389   VEC (chain_p, heap) *worklist = NULL;
2390
2391   for (i = 0; VEC_iterate (chain_p, *chains, i, ch1); i++)
2392     if (chain_can_be_combined_p (ch1))
2393       VEC_safe_push (chain_p, heap, worklist, ch1);
2394
2395   while (!VEC_empty (chain_p, worklist))
2396     {
2397       ch1 = VEC_pop (chain_p, worklist);
2398       if (!chain_can_be_combined_p (ch1))
2399         continue;
2400
2401       for (j = 0; VEC_iterate (chain_p, *chains, j, ch2); j++)
2402         {
2403           if (!chain_can_be_combined_p (ch2))
2404             continue;
2405
2406           cch = combine_chains (ch1, ch2);
2407           if (cch)
2408             {
2409               VEC_safe_push (chain_p, heap, worklist, cch);
2410               VEC_safe_push (chain_p, heap, *chains, cch);
2411               break;
2412             }
2413         }
2414     }
2415 }
2416
2417 /* Sets alias information based on data reference DR for REF,
2418    if necessary.  */
2419
2420 static void
2421 set_alias_info (tree ref, struct data_reference *dr)
2422 {
2423   tree var;
2424   tree tag = DR_SYMBOL_TAG (dr);
2425
2426   gcc_assert (tag != NULL_TREE);
2427
2428   ref = get_base_address (ref);
2429   if (!ref || !INDIRECT_REF_P (ref))
2430     return;
2431
2432   var = SSA_NAME_VAR (TREE_OPERAND (ref, 0));
2433   if (var_ann (var)->symbol_mem_tag)
2434     return;
2435
2436   if (!MTAG_P (tag))
2437     new_type_alias (var, tag, ref);
2438   else
2439     var_ann (var)->symbol_mem_tag = tag;
2440 }
2441
2442 /* Prepare initializers for CHAIN in LOOP.  Returns false if this is
2443    impossible because one of these initializers may trap, true otherwise.  */
2444
2445 static bool
2446 prepare_initializers_chain (struct loop *loop, chain_p chain)
2447 {
2448   unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2449   struct data_reference *dr = get_chain_root (chain)->ref;
2450   tree init;
2451   gimple_seq stmts;
2452   dref laref;
2453   edge entry = loop_preheader_edge (loop);
2454
2455   /* Find the initializers for the variables, and check that they cannot
2456      trap.  */
2457   chain->inits = VEC_alloc (tree, heap, n);
2458   for (i = 0; i < n; i++)
2459     VEC_quick_push (tree, chain->inits, NULL_TREE);
2460
2461   /* If we have replaced some looparound phi nodes, use their initializers
2462      instead of creating our own.  */
2463   for (i = 0; VEC_iterate (dref, chain->refs, i, laref); i++)
2464     {
2465       if (gimple_code (laref->stmt) != GIMPLE_PHI)
2466         continue;
2467
2468       gcc_assert (laref->distance > 0);
2469       VEC_replace (tree, chain->inits, n - laref->distance,
2470                    PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry));
2471     }
2472
2473   for (i = 0; i < n; i++)
2474     {
2475       if (VEC_index (tree, chain->inits, i) != NULL_TREE)
2476         continue;
2477
2478       init = ref_at_iteration (loop, DR_REF (dr), (int) i - n);
2479       if (!init)
2480         return false;
2481
2482       if (!chain->all_always_accessed && tree_could_trap_p (init))
2483         return false;
2484
2485       init = force_gimple_operand (init, &stmts, false, NULL_TREE);
2486       if (stmts)
2487         {
2488           mark_virtual_ops_for_renaming_list (stmts);
2489           gsi_insert_seq_on_edge_immediate (entry, stmts);
2490         }
2491       set_alias_info (init, dr);
2492
2493       VEC_replace (tree, chain->inits, i, init);
2494     }
2495
2496   return true;
2497 }
2498
2499 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2500    be used because the initializers might trap.  */
2501
2502 static void
2503 prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains)
2504 {
2505   chain_p chain;
2506   unsigned i;
2507
2508   for (i = 0; i < VEC_length (chain_p, chains); )
2509     {
2510       chain = VEC_index (chain_p, chains, i);
2511       if (prepare_initializers_chain (loop, chain))
2512         i++;
2513       else
2514         {
2515           release_chain (chain);
2516           VEC_unordered_remove (chain_p, chains, i);
2517         }
2518     }
2519 }
2520
2521 /* Performs predictive commoning for LOOP.  Returns true if LOOP was
2522    unrolled.  */
2523
2524 static bool
2525 tree_predictive_commoning_loop (struct loop *loop)
2526 {
2527   VEC (data_reference_p, heap) *datarefs;
2528   VEC (ddr_p, heap) *dependences;
2529   struct component *components;
2530   VEC (chain_p, heap) *chains = NULL;
2531   unsigned unroll_factor;
2532   struct tree_niter_desc desc;
2533   bool unroll = false;
2534   edge exit;
2535   bitmap tmp_vars;
2536
2537   if (dump_file && (dump_flags & TDF_DETAILS))
2538     fprintf (dump_file, "Processing loop %d\n",  loop->num);
2539
2540   /* Find the data references and split them into components according to their
2541      dependence relations.  */
2542   datarefs = VEC_alloc (data_reference_p, heap, 10);
2543   dependences = VEC_alloc (ddr_p, heap, 10);
2544   compute_data_dependences_for_loop (loop, true, &datarefs, &dependences);
2545   if (dump_file && (dump_flags & TDF_DETAILS))
2546     dump_data_dependence_relations (dump_file, dependences);
2547
2548   components = split_data_refs_to_components (loop, datarefs, dependences);
2549   free_dependence_relations (dependences);
2550   if (!components)
2551     {
2552       free_data_refs (datarefs);
2553       return false;
2554     }
2555
2556   if (dump_file && (dump_flags & TDF_DETAILS))
2557     {
2558       fprintf (dump_file, "Initial state:\n\n");
2559       dump_components (dump_file, components);
2560     }
2561
2562   /* Find the suitable components and split them into chains.  */
2563   components = filter_suitable_components (loop, components);
2564
2565   tmp_vars = BITMAP_ALLOC (NULL);
2566   looparound_phis = BITMAP_ALLOC (NULL);
2567   determine_roots (loop, components, &chains);
2568   release_components (components);
2569
2570   if (!chains)
2571     {
2572       if (dump_file && (dump_flags & TDF_DETAILS))
2573         fprintf (dump_file,
2574                  "Predictive commoning failed: no suitable chains\n");
2575       goto end;
2576     }
2577   prepare_initializers (loop, chains);
2578
2579   /* Try to combine the chains that are always worked with together.  */
2580   try_combine_chains (&chains);
2581
2582   if (dump_file && (dump_flags & TDF_DETAILS))
2583     {
2584       fprintf (dump_file, "Before commoning:\n\n");
2585       dump_chains (dump_file, chains);
2586     }
2587
2588   /* Determine the unroll factor, and if the loop should be unrolled, ensure
2589      that its number of iterations is divisible by the factor.  */
2590   unroll_factor = determine_unroll_factor (chains);
2591   scev_reset ();
2592   unroll = should_unroll_loop_p (loop, unroll_factor, &desc);
2593   exit = single_dom_exit (loop);
2594
2595   /* Execute the predictive commoning transformations, and possibly unroll the
2596      loop.  */
2597   if (unroll)
2598     {
2599       struct epcc_data dta;
2600
2601       if (dump_file && (dump_flags & TDF_DETAILS))
2602         fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2603
2604       dta.chains = chains;
2605       dta.tmp_vars = tmp_vars;
2606
2607       update_ssa (TODO_update_ssa_only_virtuals);
2608
2609       /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2610          execute_pred_commoning_cbck is called may cause phi nodes to be
2611          reallocated, which is a problem since CHAINS may point to these
2612          statements.  To fix this, we store the ssa names defined by the
2613          phi nodes here instead of the phi nodes themselves, and restore
2614          the phi nodes in execute_pred_commoning_cbck.  A bit hacky.  */
2615       replace_phis_by_defined_names (chains);
2616
2617       tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2618                                       execute_pred_commoning_cbck, &dta);
2619       eliminate_temp_copies (loop, tmp_vars);
2620     }
2621   else
2622     {
2623       if (dump_file && (dump_flags & TDF_DETAILS))
2624         fprintf (dump_file,
2625                  "Executing predictive commoning without unrolling.\n");
2626       execute_pred_commoning (loop, chains, tmp_vars);
2627     }
2628
2629 end: ;
2630   release_chains (chains);
2631   free_data_refs (datarefs);
2632   BITMAP_FREE (tmp_vars);
2633   BITMAP_FREE (looparound_phis);
2634
2635   free_affine_expand_cache (&name_expansions);
2636
2637   return unroll;
2638 }
2639
2640 /* Runs predictive commoning.  */
2641
2642 unsigned
2643 tree_predictive_commoning (void)
2644 {
2645   bool unrolled = false;
2646   struct loop *loop;
2647   loop_iterator li;
2648   unsigned ret = 0;
2649
2650   initialize_original_copy_tables ();
2651   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
2652     {
2653       unrolled |= tree_predictive_commoning_loop (loop);
2654     }
2655
2656   if (unrolled)
2657     {
2658       scev_reset ();
2659       ret = TODO_cleanup_cfg;
2660     }
2661   free_original_copy_tables ();
2662
2663   return ret;
2664 }