gcc/tree-loop-distribution.c

   1 /* Loop distribution.
   2    Copyright (C) 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
   5    and Sebastian Pop <sebastian.pop@amd.com>.
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it
  10 under the terms of the GNU General Public License as published by the
  11 Free Software Foundation; either version 3, or (at your option) any
  12 later version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT
  15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  22
  23 /* This pass performs loop distribution: for example, the loop
  24
  25    |DO I = 2, N
  26    |    A(I) = B(I) + C
  27    |    D(I) = A(I-1)*E
  28    |ENDDO
  29
  30    is transformed to
  31
  32    |DOALL I = 2, N
  33    |   A(I) = B(I) + C
  34    |ENDDO
  35    |
  36    |DOALL I = 2, N
  37    |   D(I) = A(I-1)*E
  38    |ENDDO
  39
  40    This pass uses an RDG, Reduced Dependence Graph built on top of the
  41    data dependence relations.  The RDG is then topologically sorted to
  42    obtain a map of information producers/consumers based on which it
  43    generates the new loops.  */
  44
  45 #include "config.h"
  46 #include "system.h"
  47 #include "coretypes.h"
  48 #include "tm.h"
  49 #include "ggc.h"
  50 #include "tree.h"
  51 #include "target.h"
  52
  53 #include "rtl.h"
  54 #include "basic-block.h"
  55 #include "diagnostic.h"
  56 #include "tree-flow.h"
  57 #include "tree-dump.h"
  58 #include "timevar.h"
  59 #include "cfgloop.h"
  60 #include "expr.h"
  61 #include "optabs.h"
  62 #include "tree-chrec.h"
  63 #include "tree-data-ref.h"
  64 #include "tree-scalar-evolution.h"
  65 #include "tree-pass.h"
  66 #include "lambda.h"
  67 #include "langhooks.h"
  68 #include "tree-vectorizer.h"
  69
  70 /* If bit I is not set, it means that this node represents an
  71    operation that has already been performed, and that should not be
  72    performed again.  This is the subgraph of remaining important
  73    computations that is passed to the DFS algorithm for avoiding to
  74    include several times the same stores in different loops.  */
  75 static bitmap remaining_stmts;
  76
  77 /* A node of the RDG is marked in this bitmap when it has as a
  78    predecessor a node that writes to memory.  */
  79 static bitmap upstream_mem_writes;
  80
  81 /* Update the PHI nodes of NEW_LOOP.  NEW_LOOP is a duplicate of
  82    ORIG_LOOP.  */
  83
  84 static void
  85 update_phis_for_loop_copy (struct loop *orig_loop, struct loop *new_loop)
  86 {
  87   tree new_ssa_name;
  88   gimple_stmt_iterator si_new, si_orig;
  89   edge orig_loop_latch = loop_latch_edge (orig_loop);
  90   edge orig_entry_e = loop_preheader_edge (orig_loop);
  91   edge new_loop_entry_e = loop_preheader_edge (new_loop);
  92
  93   /* Scan the phis in the headers of the old and new loops
  94      (they are organized in exactly the same order).  */
  95   for (si_new = gsi_start_phis (new_loop->header),
  96        si_orig = gsi_start_phis (orig_loop->header);
  97        !gsi_end_p (si_new) && !gsi_end_p (si_orig);
  98        gsi_next (&si_new), gsi_next (&si_orig))
  99     {
 100       tree def;
 101       source_location locus;
 102       gimple phi_new = gsi_stmt (si_new);
 103       gimple phi_orig = gsi_stmt (si_orig);
 104
 105       /* Add the first phi argument for the phi in NEW_LOOP (the one
 106          associated with the entry of NEW_LOOP)  */
 107       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_entry_e);
 108       locus = gimple_phi_arg_location_from_edge (phi_orig, orig_entry_e);
 109       add_phi_arg (phi_new, def, new_loop_entry_e, locus);
 110
 111       /* Add the second phi argument for the phi in NEW_LOOP (the one
 112          associated with the latch of NEW_LOOP)  */
 113       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
 114       locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
 115
 116       if (TREE_CODE (def) == SSA_NAME)
 117         {
 118           new_ssa_name = get_current_def (def);
 119
 120           if (!new_ssa_name)
 121             /* This only happens if there are no definitions inside the
 122                loop.  Use the the invariant in the new loop as is.  */
 123             new_ssa_name = def;
 124         }
 125       else
 126         /* Could be an integer.  */
 127         new_ssa_name = def;
 128
 129       add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
 130     }
 131 }
 132
 133 /* Return a copy of LOOP placed before LOOP.  */
 134
 135 static struct loop *
 136 copy_loop_before (struct loop *loop)
 137 {
 138   struct loop *res;
 139   edge preheader = loop_preheader_edge (loop);
 140
 141   if (!single_exit (loop))
 142     return NULL;
 143
 144   initialize_original_copy_tables ();
 145   res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader);
 146   free_original_copy_tables ();
 147
 148   if (!res)
 149     return NULL;
 150
 151   update_phis_for_loop_copy (loop, res);
 152   rename_variables_in_loop (res);
 153
 154   return res;
 155 }
 156
 157 /* Creates an empty basic block after LOOP.  */
 158
 159 static void
 160 create_bb_after_loop (struct loop *loop)
 161 {
 162   edge exit = single_exit (loop);
 163
 164   if (!exit)
 165     return;
 166
 167   split_edge (exit);
 168 }
 169
 170 /* Generate code for PARTITION from the code in LOOP.  The loop is
 171    copied when COPY_P is true.  All the statements not flagged in the
 172    PARTITION bitmap are removed from the loop or from its copy.  The
 173    statements are indexed in sequence inside a basic block, and the
 174    basic blocks of a loop are taken in dom order.  Returns true when
 175    the code gen succeeded. */
 176
 177 static bool
 178 generate_loops_for_partition (struct loop *loop, bitmap partition, bool copy_p)
 179 {
 180   unsigned i, x;
 181   gimple_stmt_iterator bsi;
 182   basic_block *bbs;
 183
 184   if (copy_p)
 185     {
 186       loop = copy_loop_before (loop);
 187       create_preheader (loop, CP_SIMPLE_PREHEADERS);
 188       create_bb_after_loop (loop);
 189     }
 190
 191   if (loop == NULL)
 192     return false;
 193
 194   /* Remove stmts not in the PARTITION bitmap.  The order in which we
 195      visit the phi nodes and the statements is exactly as in
 196      stmts_from_loop.  */
 197   bbs = get_loop_body_in_dom_order (loop);
 198
 199   for (x = 0, i = 0; i < loop->num_nodes; i++)
 200     {
 201       basic_block bb = bbs[i];
 202
 203       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
 204         if (!bitmap_bit_p (partition, x++))
 205           remove_phi_node (&bsi, true);
 206         else
 207           gsi_next (&bsi);
 208
 209       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
 210         if (gimple_code (gsi_stmt (bsi)) != GIMPLE_LABEL
 211             && !bitmap_bit_p (partition, x++))
 212           gsi_remove (&bsi, false);
 213         else
 214           gsi_next (&bsi);
 215
 216         mark_virtual_ops_in_bb (bb);
 217     }
 218
 219   free (bbs);
 220   return true;
 221 }
 222
 223 /* Build the size argument for a memset call.  */
 224
 225 static inline tree
 226 build_size_arg_loc (location_t loc, tree nb_iter, tree op,
 227                     gimple_seq *stmt_list)
 228 {
 229   gimple_seq stmts;
 230   tree x = size_binop_loc (loc, MULT_EXPR,
 231                            fold_convert_loc (loc, sizetype, nb_iter),
 232                            TYPE_SIZE_UNIT (TREE_TYPE (op)));
 233   x = force_gimple_operand (x, &stmts, true, NULL);
 234   gimple_seq_add_seq (stmt_list, stmts);
 235
 236   return x;
 237 }
 238
 239 /* Generate a call to memset.  Return true when the operation succeeded.  */
 240
 241 static bool
 242 generate_memset_zero (gimple stmt, tree op0, tree nb_iter,
 243                       gimple_stmt_iterator bsi)
 244 {
 245   tree addr_base, nb_bytes;
 246   bool res = false;
 247   gimple_seq stmt_list = NULL, stmts;
 248   gimple fn_call;
 249   tree mem, fn;
 250   gimple_stmt_iterator i;
 251   struct data_reference *dr = XCNEW (struct data_reference);
 252   location_t loc = gimple_location (stmt);
 253
 254   DR_STMT (dr) = stmt;
 255   DR_REF (dr) = op0;
 256   if (!dr_analyze_innermost (dr))
 257     goto end;
 258
 259   /* Test for a positive stride, iterating over every element.  */
 260   if (integer_zerop (size_binop (MINUS_EXPR,
 261                                  fold_convert (sizetype, DR_STEP (dr)),
 262                                  TYPE_SIZE_UNIT (TREE_TYPE (op0)))))
 263     {
 264       addr_base = fold_convert_loc (loc, sizetype,
 265                                     size_binop_loc (loc, PLUS_EXPR,
 266                                                     DR_OFFSET (dr),
 267                                                     DR_INIT (dr)));
 268       addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR,
 269                                    TREE_TYPE (DR_BASE_ADDRESS (dr)),
 270                                    DR_BASE_ADDRESS (dr), addr_base);
 271
 272       nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
 273     }
 274
 275   /* Test for a negative stride, iterating over every element.  */
 276   else if (integer_zerop (size_binop (PLUS_EXPR,
 277                                       TYPE_SIZE_UNIT (TREE_TYPE (op0)),
 278                                       fold_convert (sizetype, DR_STEP (dr)))))
 279     {
 280       nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
 281
 282       addr_base = size_binop_loc (loc, PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr));
 283       addr_base = fold_convert_loc (loc, sizetype, addr_base);
 284       addr_base = size_binop_loc (loc, MINUS_EXPR, addr_base,
 285                                   fold_convert_loc (loc, sizetype, nb_bytes));
 286       addr_base = size_binop_loc (loc, PLUS_EXPR, addr_base,
 287                                   TYPE_SIZE_UNIT (TREE_TYPE (op0)));
 288       addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR,
 289                                    TREE_TYPE (DR_BASE_ADDRESS (dr)),
 290                                    DR_BASE_ADDRESS (dr), addr_base);
 291     }
 292   else
 293     goto end;
 294
 295   mem = force_gimple_operand (addr_base, &stmts, true, NULL);
 296   gimple_seq_add_seq (&stmt_list, stmts);
 297
 298   fn = build_fold_addr_expr (implicit_built_in_decls [BUILT_IN_MEMSET]);
 299   fn_call = gimple_build_call (fn, 3, mem, integer_zero_node, nb_bytes);
 300   gimple_seq_add_stmt (&stmt_list, fn_call);
 301
 302   for (i = gsi_start (stmt_list); !gsi_end_p (i); gsi_next (&i))
 303     {
 304       gimple s = gsi_stmt (i);
 305       update_stmt_if_modified (s);
 306     }
 307
 308   gsi_insert_seq_after (&bsi, stmt_list, GSI_CONTINUE_LINKING);
 309   res = true;
 310
 311   if (dump_file && (dump_flags & TDF_DETAILS))
 312     fprintf (dump_file, "generated memset zero\n");
 313
 314  end:
 315   free_data_ref (dr);
 316   return res;
 317 }
 318
 319 /* Propagate phis in BB b to their uses and remove them.  */
 320
 321 static void
 322 prop_phis (basic_block b)
 323 {
 324   gimple_stmt_iterator psi;
 325   gimple_seq phis = phi_nodes (b);
 326
 327   for (psi = gsi_start (phis); !gsi_end_p (psi); )
 328     {
 329       gimple phi = gsi_stmt (psi);
 330       tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
 331
 332       gcc_assert (gimple_phi_num_args (phi) == 1);
 333
 334       if (!is_gimple_reg (def))
 335         {
 336           imm_use_iterator iter;
 337           use_operand_p use_p;
 338           gimple stmt;
 339
 340           FOR_EACH_IMM_USE_STMT (stmt, iter, def)
 341             FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 342               SET_USE (use_p, use);
 343         }
 344       else
 345         replace_uses_by (def, use);
 346
 347       remove_phi_node (&psi, true);
 348     }
 349 }
 350
 351 /* Tries to generate a builtin function for the instructions of LOOP
 352    pointed to by the bits set in PARTITION.  Returns true when the
 353    operation succeeded.  */
 354
 355 static bool
 356 generate_builtin (struct loop *loop, bitmap partition, bool copy_p)
 357 {
 358   bool res = false;
 359   unsigned i, x = 0;
 360   basic_block *bbs;
 361   gimple write = NULL;
 362   tree op0, op1;
 363   gimple_stmt_iterator bsi;
 364   tree nb_iter = number_of_exit_cond_executions (loop);
 365
 366   if (!nb_iter || nb_iter == chrec_dont_know)
 367     return false;
 368
 369   bbs = get_loop_body_in_dom_order (loop);
 370
 371   for (i = 0; i < loop->num_nodes; i++)
 372     {
 373       basic_block bb = bbs[i];
 374
 375       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 376         x++;
 377
 378       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 379         {
 380           gimple stmt = gsi_stmt (bsi);
 381
 382           if (bitmap_bit_p (partition, x++)
 383               && is_gimple_assign (stmt)
 384               && !is_gimple_reg (gimple_assign_lhs (stmt)))
 385             {
 386               /* Don't generate the builtins when there are more than
 387                  one memory write.  */
 388               if (write != NULL)
 389                 goto end;
 390
 391               write = stmt;
 392               if (bb == loop->latch)
 393                 nb_iter = number_of_latch_executions (loop);
 394             }
 395         }
 396     }
 397
 398   if (!write)
 399     goto end;
 400
 401   op0 = gimple_assign_lhs (write);
 402   op1 = gimple_assign_rhs1 (write);
 403
 404   if (!(TREE_CODE (op0) == ARRAY_REF
 405         || TREE_CODE (op0) == INDIRECT_REF))
 406     goto end;
 407
 408   /* The new statements will be placed before LOOP.  */
 409   bsi = gsi_last_bb (loop_preheader_edge (loop)->src);
 410
 411   if (gimple_assign_rhs_code (write) == INTEGER_CST
 412       && (integer_zerop (op1) || real_zerop (op1)))
 413     res = generate_memset_zero (write, op0, nb_iter, bsi);
 414
 415   /* If this is the last partition for which we generate code, we have
 416      to destroy the loop.  */
 417   if (res && !copy_p)
 418     {
 419       unsigned nbbs = loop->num_nodes;
 420       basic_block src = loop_preheader_edge (loop)->src;
 421       basic_block dest = single_exit (loop)->dest;
 422       prop_phis (dest);
 423       make_edge (src, dest, EDGE_FALLTHRU);
 424       cancel_loop_tree (loop);
 425
 426       for (i = 0; i < nbbs; i++)
 427         delete_basic_block (bbs[i]);
 428
 429       set_immediate_dominator (CDI_DOMINATORS, dest,
 430                                recompute_dominator (CDI_DOMINATORS, dest));
 431     }
 432
 433  end:
 434   free (bbs);
 435   return res;
 436 }
 437
 438 /* Generates code for PARTITION.  For simple loops, this function can
 439    generate a built-in.  */
 440
 441 static bool
 442 generate_code_for_partition (struct loop *loop, bitmap partition, bool copy_p)
 443 {
 444   if (generate_builtin (loop, partition, copy_p))
 445     return true;
 446
 447   return generate_loops_for_partition (loop, partition, copy_p);
 448 }
 449
 450
 451 /* Returns true if the node V of RDG cannot be recomputed.  */
 452
 453 static bool
 454 rdg_cannot_recompute_vertex_p (struct graph *rdg, int v)
 455 {
 456   if (RDG_MEM_WRITE_STMT (rdg, v))
 457     return true;
 458
 459   return false;
 460 }
 461
 462 /* Returns true when the vertex V has already been generated in the
 463    current partition (V is in PROCESSED), or when V belongs to another
 464    partition and cannot be recomputed (V is not in REMAINING_STMTS).  */
 465
 466 static inline bool
 467 already_processed_vertex_p (bitmap processed, int v)
 468 {
 469   return (bitmap_bit_p (processed, v)
 470           || !bitmap_bit_p (remaining_stmts, v));
 471 }
 472
 473 /* Returns NULL when there is no anti-dependence among the successors
 474    of vertex V, otherwise returns the edge with the anti-dep.  */
 475
 476 static struct graph_edge *
 477 has_anti_dependence (struct vertex *v)
 478 {
 479   struct graph_edge *e;
 480
 481   if (v->succ)
 482     for (e = v->succ; e; e = e->succ_next)
 483       if (RDGE_TYPE (e) == anti_dd)
 484         return e;
 485
 486   return NULL;
 487 }
 488
 489 /* Returns true when V has an anti-dependence edge among its successors.  */
 490
 491 static bool
 492 predecessor_has_mem_write (struct graph *rdg, struct vertex *v)
 493 {
 494   struct graph_edge *e;
 495
 496   if (v->pred)
 497     for (e = v->pred; e; e = e->pred_next)
 498       if (bitmap_bit_p (upstream_mem_writes, e->src)
 499           /* Don't consider flow channels: a write to memory followed
 500              by a read from memory.  These channels allow the split of
 501              the RDG in different partitions.  */
 502           && !RDG_MEM_WRITE_STMT (rdg, e->src))
 503         return true;
 504
 505   return false;
 506 }
 507
 508 /* Initializes the upstream_mem_writes bitmap following the
 509    information from RDG.  */
 510
 511 static void
 512 mark_nodes_having_upstream_mem_writes (struct graph *rdg)
 513 {
 514   int v, x;
 515   bitmap seen = BITMAP_ALLOC (NULL);
 516
 517   for (v = rdg->n_vertices - 1; v >= 0; v--)
 518     if (!bitmap_bit_p (seen, v))
 519       {
 520         unsigned i;
 521         VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
 522
 523         graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
 524
 525         for (i = 0; VEC_iterate (int, nodes, i, x); i++)
 526           {
 527             if (bitmap_bit_p (seen, x))
 528               continue;
 529
 530             bitmap_set_bit (seen, x);
 531
 532             if (RDG_MEM_WRITE_STMT (rdg, x)
 533                 || predecessor_has_mem_write (rdg, &(rdg->vertices[x]))
 534                 /* In anti dependences the read should occur before
 535                    the write, this is why both the read and the write
 536                    should be placed in the same partition.  */
 537                 || has_anti_dependence (&(rdg->vertices[x])))
 538               {
 539                 bitmap_set_bit (upstream_mem_writes, x);
 540               }
 541           }
 542
 543         VEC_free (int, heap, nodes);
 544       }
 545 }
 546
 547 /* Returns true when vertex u has a memory write node as a predecessor
 548    in RDG.  */
 549
 550 static bool
 551 has_upstream_mem_writes (int u)
 552 {
 553   return bitmap_bit_p (upstream_mem_writes, u);
 554 }
 555
 556 static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap,
 557                                            bitmap, bool *);
 558
 559 /* Flag all the uses of U.  */
 560
 561 static void
 562 rdg_flag_all_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
 563                    bitmap processed, bool *part_has_writes)
 564 {
 565   struct graph_edge *e;
 566
 567   for (e = rdg->vertices[u].succ; e; e = e->succ_next)
 568     if (!bitmap_bit_p (processed, e->dest))
 569       {
 570         rdg_flag_vertex_and_dependent (rdg, e->dest, partition, loops,
 571                                        processed, part_has_writes);
 572         rdg_flag_all_uses (rdg, e->dest, partition, loops, processed,
 573                            part_has_writes);
 574       }
 575 }
 576
 577 /* Flag the uses of U stopping following the information from
 578    upstream_mem_writes.  */
 579
 580 static void
 581 rdg_flag_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
 582                bitmap processed, bool *part_has_writes)
 583 {
 584   use_operand_p use_p;
 585   struct vertex *x = &(rdg->vertices[u]);
 586   gimple stmt = RDGV_STMT (x);
 587   struct graph_edge *anti_dep = has_anti_dependence (x);
 588
 589   /* Keep in the same partition the destination of an antidependence,
 590      because this is a store to the exact same location.  Putting this
 591      in another partition is bad for cache locality.  */
 592   if (anti_dep)
 593     {
 594       int v = anti_dep->dest;
 595
 596       if (!already_processed_vertex_p (processed, v))
 597         rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
 598                                        processed, part_has_writes);
 599     }
 600
 601   if (gimple_code (stmt) != GIMPLE_PHI)
 602     {
 603       if ((use_p = gimple_vuse_op (stmt)) != NULL_USE_OPERAND_P)
 604         {
 605           tree use = USE_FROM_PTR (use_p);
 606
 607           if (TREE_CODE (use) == SSA_NAME)
 608             {
 609               gimple def_stmt = SSA_NAME_DEF_STMT (use);
 610               int v = rdg_vertex_for_stmt (rdg, def_stmt);
 611
 612               if (v >= 0
 613                   && !already_processed_vertex_p (processed, v))
 614                 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
 615                                                processed, part_has_writes);
 616             }
 617         }
 618     }
 619
 620   if (is_gimple_assign (stmt) && has_upstream_mem_writes (u))
 621     {
 622       tree op0 = gimple_assign_lhs (stmt);
 623
 624       /* Scalar channels don't have enough space for transmitting data
 625          between tasks, unless we add more storage by privatizing.  */
 626       if (is_gimple_reg (op0))
 627         {
 628           use_operand_p use_p;
 629           imm_use_iterator iter;
 630
 631           FOR_EACH_IMM_USE_FAST (use_p, iter, op0)
 632             {
 633               int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p));
 634
 635               if (!already_processed_vertex_p (processed, v))
 636                 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
 637                                                processed, part_has_writes);
 638             }
 639         }
 640     }
 641 }
 642
 643 /* Flag V from RDG as part of PARTITION, and also flag its loop number
 644    in LOOPS.  */
 645
 646 static void
 647 rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops,
 648                  bool *part_has_writes)
 649 {
 650   struct loop *loop;
 651
 652   if (bitmap_bit_p (partition, v))
 653     return;
 654
 655   loop = loop_containing_stmt (RDG_STMT (rdg, v));
 656   bitmap_set_bit (loops, loop->num);
 657   bitmap_set_bit (partition, v);
 658
 659   if (rdg_cannot_recompute_vertex_p (rdg, v))
 660     {
 661       *part_has_writes = true;
 662       bitmap_clear_bit (remaining_stmts, v);
 663     }
 664 }
 665
 666 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
 667    Also flag their loop number in LOOPS.  */
 668
 669 static void
 670 rdg_flag_vertex_and_dependent (struct graph *rdg, int v, bitmap partition,
 671                                bitmap loops, bitmap processed,
 672                                bool *part_has_writes)
 673 {
 674   unsigned i;
 675   VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
 676   int x;
 677
 678   bitmap_set_bit (processed, v);
 679   rdg_flag_uses (rdg, v, partition, loops, processed, part_has_writes);
 680   graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts);
 681   rdg_flag_vertex (rdg, v, partition, loops, part_has_writes);
 682
 683   for (i = 0; VEC_iterate (int, nodes, i, x); i++)
 684     if (!already_processed_vertex_p (processed, x))
 685       rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed,
 686                                      part_has_writes);
 687
 688   VEC_free (int, heap, nodes);
 689 }
 690
 691 /* Initialize CONDS with all the condition statements from the basic
 692    blocks of LOOP.  */
 693
 694 static void
 695 collect_condition_stmts (struct loop *loop, VEC (gimple, heap) **conds)
 696 {
 697   unsigned i;
 698   edge e;
 699   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
 700
 701   for (i = 0; VEC_iterate (edge, exits, i, e); i++)
 702     {
 703       gimple cond = last_stmt (e->src);
 704
 705       if (cond)
 706         VEC_safe_push (gimple, heap, *conds, cond);
 707     }
 708
 709   VEC_free (edge, heap, exits);
 710 }
 711
 712 /* Add to PARTITION all the exit condition statements for LOOPS
 713    together with all their dependent statements determined from
 714    RDG.  */
 715
 716 static void
 717 rdg_flag_loop_exits (struct graph *rdg, bitmap loops, bitmap partition,
 718                      bitmap processed, bool *part_has_writes)
 719 {
 720   unsigned i;
 721   bitmap_iterator bi;
 722   VEC (gimple, heap) *conds = VEC_alloc (gimple, heap, 3);
 723
 724   EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi)
 725     collect_condition_stmts (get_loop (i), &conds);
 726
 727   while (!VEC_empty (gimple, conds))
 728     {
 729       gimple cond = VEC_pop (gimple, conds);
 730       int v = rdg_vertex_for_stmt (rdg, cond);
 731       bitmap new_loops = BITMAP_ALLOC (NULL);
 732
 733       if (!already_processed_vertex_p (processed, v))
 734         rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed,
 735                                        part_has_writes);
 736
 737       EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi)
 738         if (!bitmap_bit_p (loops, i))
 739           {
 740             bitmap_set_bit (loops, i);
 741             collect_condition_stmts (get_loop (i), &conds);
 742           }
 743
 744       BITMAP_FREE (new_loops);
 745     }
 746 }
 747
 748 /* Flag all the nodes of RDG containing memory accesses that could
 749    potentially belong to arrays already accessed in the current
 750    PARTITION.  */
 751
 752 static void
 753 rdg_flag_similar_memory_accesses (struct graph *rdg, bitmap partition,
 754                                   bitmap loops, bitmap processed,
 755                                   VEC (int, heap) **other_stores)
 756 {
 757   bool foo;
 758   unsigned i, n;
 759   int j, k, kk;
 760   bitmap_iterator ii;
 761   struct graph_edge *e;
 762
 763   EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
 764     if (RDG_MEM_WRITE_STMT (rdg, i)
 765         || RDG_MEM_READS_STMT (rdg, i))
 766       {
 767         for (j = 0; j < rdg->n_vertices; j++)
 768           if (!bitmap_bit_p (processed, j)
 769               && (RDG_MEM_WRITE_STMT (rdg, j)
 770                   || RDG_MEM_READS_STMT (rdg, j))
 771               && rdg_has_similar_memory_accesses (rdg, i, j))
 772             {
 773               /* Flag first the node J itself, and all the nodes that
 774                  are needed to compute J.  */
 775               rdg_flag_vertex_and_dependent (rdg, j, partition, loops,
 776                                              processed, &foo);
 777
 778               /* When J is a read, we want to coalesce in the same
 779                  PARTITION all the nodes that are using J: this is
 780                  needed for better cache locality.  */
 781               rdg_flag_all_uses (rdg, j, partition, loops, processed, &foo);
 782
 783               /* Remove from OTHER_STORES the vertex that we flagged.  */
 784               if (RDG_MEM_WRITE_STMT (rdg, j))
 785                 for (k = 0; VEC_iterate (int, *other_stores, k, kk); k++)
 786                   if (kk == j)
 787                     {
 788                       VEC_unordered_remove (int, *other_stores, k);
 789                       break;
 790                     }
 791             }
 792
 793         /* If the node I has two uses, then keep these together in the
 794            same PARTITION.  */
 795         for (n = 0, e = rdg->vertices[i].succ; e; e = e->succ_next, n++);
 796
 797         if (n > 1)
 798           rdg_flag_all_uses (rdg, i, partition, loops, processed, &foo);
 799       }
 800 }
 801
 802 /* Returns a bitmap in which all the statements needed for computing
 803    the strongly connected component C of the RDG are flagged, also
 804    including the loop exit conditions.  */
 805
 806 static bitmap
 807 build_rdg_partition_for_component (struct graph *rdg, rdgc c,
 808                                    bool *part_has_writes,
 809                                    VEC (int, heap) **other_stores)
 810 {
 811   int i, v;
 812   bitmap partition = BITMAP_ALLOC (NULL);
 813   bitmap loops = BITMAP_ALLOC (NULL);
 814   bitmap processed = BITMAP_ALLOC (NULL);
 815
 816   for (i = 0; VEC_iterate (int, c->vertices, i, v); i++)
 817     if (!already_processed_vertex_p (processed, v))
 818       rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed,
 819                                      part_has_writes);
 820
 821   /* Also iterate on the array of stores not in the starting vertices,
 822      and determine those vertices that have some memory affinity with
 823      the current nodes in the component: these are stores to the same
 824      arrays, i.e. we're taking care of cache locality.  */
 825   rdg_flag_similar_memory_accesses (rdg, partition, loops, processed,
 826                                     other_stores);
 827
 828   rdg_flag_loop_exits (rdg, loops, partition, processed, part_has_writes);
 829
 830   BITMAP_FREE (processed);
 831   BITMAP_FREE (loops);
 832   return partition;
 833 }
 834
 835 /* Free memory for COMPONENTS.  */
 836
 837 static void
 838 free_rdg_components (VEC (rdgc, heap) *components)
 839 {
 840   int i;
 841   rdgc x;
 842
 843   for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
 844     {
 845       VEC_free (int, heap, x->vertices);
 846       free (x);
 847     }
 848 }
 849
 850 /* Build the COMPONENTS vector with the strongly connected components
 851    of RDG in which the STARTING_VERTICES occur.  */
 852
 853 static void
 854 rdg_build_components (struct graph *rdg, VEC (int, heap) *starting_vertices,
 855                       VEC (rdgc, heap) **components)
 856 {
 857   int i, v;
 858   bitmap saved_components = BITMAP_ALLOC (NULL);
 859   int n_components = graphds_scc (rdg, NULL);
 860   VEC (int, heap) **all_components = XNEWVEC (VEC (int, heap) *, n_components);
 861
 862   for (i = 0; i < n_components; i++)
 863     all_components[i] = VEC_alloc (int, heap, 3);
 864
 865   for (i = 0; i < rdg->n_vertices; i++)
 866     VEC_safe_push (int, heap, all_components[rdg->vertices[i].component], i);
 867
 868   for (i = 0; VEC_iterate (int, starting_vertices, i, v); i++)
 869     {
 870       int c = rdg->vertices[v].component;
 871
 872       if (!bitmap_bit_p (saved_components, c))
 873         {
 874           rdgc x = XCNEW (struct rdg_component);
 875           x->num = c;
 876           x->vertices = all_components[c];
 877
 878           VEC_safe_push (rdgc, heap, *components, x);
 879           bitmap_set_bit (saved_components, c);
 880         }
 881     }
 882
 883   for (i = 0; i < n_components; i++)
 884     if (!bitmap_bit_p (saved_components, i))
 885       VEC_free (int, heap, all_components[i]);
 886
 887   free (all_components);
 888   BITMAP_FREE (saved_components);
 889 }
 890
 891 /* Aggregate several components into a useful partition that is
 892    registered in the PARTITIONS vector.  Partitions will be
 893    distributed in different loops.  */
 894
 895 static void
 896 rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components,
 897                       VEC (int, heap) **other_stores,
 898                       VEC (bitmap, heap) **partitions, bitmap processed)
 899 {
 900   int i;
 901   rdgc x;
 902   bitmap partition = BITMAP_ALLOC (NULL);
 903
 904   for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
 905     {
 906       bitmap np;
 907       bool part_has_writes = false;
 908       int v = VEC_index (int, x->vertices, 0);
 909
 910       if (bitmap_bit_p (processed, v))
 911         continue;
 912
 913       np = build_rdg_partition_for_component (rdg, x, &part_has_writes,
 914                                               other_stores);
 915       bitmap_ior_into (partition, np);
 916       bitmap_ior_into (processed, np);
 917       BITMAP_FREE (np);
 918
 919       if (part_has_writes)
 920         {
 921           if (dump_file && (dump_flags & TDF_DETAILS))
 922             {
 923               fprintf (dump_file, "ldist useful partition:\n");
 924               dump_bitmap (dump_file, partition);
 925             }
 926
 927           VEC_safe_push (bitmap, heap, *partitions, partition);
 928           partition = BITMAP_ALLOC (NULL);
 929         }
 930     }
 931
 932   /* Add the nodes from the RDG that were not marked as processed, and
 933      that are used outside the current loop.  These are scalar
 934      computations that are not yet part of previous partitions.  */
 935   for (i = 0; i < rdg->n_vertices; i++)
 936     if (!bitmap_bit_p (processed, i)
 937         && rdg_defs_used_in_other_loops_p (rdg, i))
 938       VEC_safe_push (int, heap, *other_stores, i);
 939
 940   /* If there are still statements left in the OTHER_STORES array,
 941      create other components and partitions with these stores and
 942      their dependences.  */
 943   if (VEC_length (int, *other_stores) > 0)
 944     {
 945       VEC (rdgc, heap) *comps = VEC_alloc (rdgc, heap, 3);
 946       VEC (int, heap) *foo = VEC_alloc (int, heap, 3);
 947
 948       rdg_build_components (rdg, *other_stores, &comps);
 949       rdg_build_partitions (rdg, comps, &foo, partitions, processed);
 950
 951       VEC_free (int, heap, foo);
 952       free_rdg_components (comps);
 953     }
 954
 955   /* If there is something left in the last partition, save it.  */
 956   if (bitmap_count_bits (partition) > 0)
 957     VEC_safe_push (bitmap, heap, *partitions, partition);
 958   else
 959     BITMAP_FREE (partition);
 960 }
 961
 962 /* Dump to FILE the PARTITIONS.  */
 963
 964 static void
 965 dump_rdg_partitions (FILE *file, VEC (bitmap, heap) *partitions)
 966 {
 967   int i;
 968   bitmap partition;
 969
 970   for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
 971     debug_bitmap_file (file, partition);
 972 }
 973
 974 /* Debug PARTITIONS.  */
 975 extern void debug_rdg_partitions (VEC (bitmap, heap) *);
 976
 977 void
 978 debug_rdg_partitions (VEC (bitmap, heap) *partitions)
 979 {
 980   dump_rdg_partitions (stderr, partitions);
 981 }
 982
 983 /* Returns the number of read and write operations in the RDG.  */
 984
 985 static int
 986 number_of_rw_in_rdg (struct graph *rdg)
 987 {
 988   int i, res = 0;
 989
 990   for (i = 0; i < rdg->n_vertices; i++)
 991     {
 992       if (RDG_MEM_WRITE_STMT (rdg, i))
 993         ++res;
 994
 995       if (RDG_MEM_READS_STMT (rdg, i))
 996         ++res;
 997     }
 998
 999   return res;
1000 }
1001
1002 /* Returns the number of read and write operations in a PARTITION of
1003    the RDG.  */
1004
1005 static int
1006 number_of_rw_in_partition (struct graph *rdg, bitmap partition)
1007 {
1008   int res = 0;
1009   unsigned i;
1010   bitmap_iterator ii;
1011
1012   EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
1013     {
1014       if (RDG_MEM_WRITE_STMT (rdg, i))
1015         ++res;
1016
1017       if (RDG_MEM_READS_STMT (rdg, i))
1018         ++res;
1019     }
1020
1021   return res;
1022 }
1023
1024 /* Returns true when one of the PARTITIONS contains all the read or
1025    write operations of RDG.  */
1026
1027 static bool
1028 partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions)
1029 {
1030   int i;
1031   bitmap partition;
1032   int nrw = number_of_rw_in_rdg (rdg);
1033
1034   for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
1035     if (nrw == number_of_rw_in_partition (rdg, partition))
1036       return true;
1037
1038   return false;
1039 }
1040
1041 /* Generate code from STARTING_VERTICES in RDG.  Returns the number of
1042    distributed loops.  */
1043
1044 static int
1045 ldist_gen (struct loop *loop, struct graph *rdg,
1046            VEC (int, heap) *starting_vertices)
1047 {
1048   int i, nbp;
1049   VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3);
1050   VEC (bitmap, heap) *partitions = VEC_alloc (bitmap, heap, 3);
1051   VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3);
1052   bitmap partition, processed = BITMAP_ALLOC (NULL);
1053
1054   remaining_stmts = BITMAP_ALLOC (NULL);
1055   upstream_mem_writes = BITMAP_ALLOC (NULL);
1056
1057   for (i = 0; i < rdg->n_vertices; i++)
1058     {
1059       bitmap_set_bit (remaining_stmts, i);
1060
1061       /* Save in OTHER_STORES all the memory writes that are not in
1062          STARTING_VERTICES.  */
1063       if (RDG_MEM_WRITE_STMT (rdg, i))
1064         {
1065           int v;
1066           unsigned j;
1067           bool found = false;
1068
1069           for (j = 0; VEC_iterate (int, starting_vertices, j, v); j++)
1070             if (i == v)
1071               {
1072                 found = true;
1073                 break;
1074               }
1075
1076           if (!found)
1077             VEC_safe_push (int, heap, other_stores, i);
1078         }
1079     }
1080
1081   mark_nodes_having_upstream_mem_writes (rdg);
1082   rdg_build_components (rdg, starting_vertices, &components);
1083   rdg_build_partitions (rdg, components, &other_stores, &partitions,
1084                         processed);
1085   BITMAP_FREE (processed);
1086   nbp = VEC_length (bitmap, partitions);
1087
1088   if (nbp <= 1
1089       || partition_contains_all_rw (rdg, partitions))
1090     goto ldist_done;
1091
1092   if (dump_file && (dump_flags & TDF_DETAILS))
1093     dump_rdg_partitions (dump_file, partitions);
1094
1095   for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
1096     if (!generate_code_for_partition (loop, partition, i < nbp - 1))
1097       goto ldist_done;
1098
1099   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1100   update_ssa (TODO_update_ssa_only_virtuals | TODO_update_ssa);
1101
1102  ldist_done:
1103
1104   BITMAP_FREE (remaining_stmts);
1105   BITMAP_FREE (upstream_mem_writes);
1106
1107   for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
1108     BITMAP_FREE (partition);
1109
1110   VEC_free (int, heap, other_stores);
1111   VEC_free (bitmap, heap, partitions);
1112   free_rdg_components (components);
1113   return nbp;
1114 }
1115
1116 /* Distributes the code from LOOP in such a way that producer
1117    statements are placed before consumer statements.  When STMTS is
1118    NULL, performs the maximal distribution, if STMTS is not NULL,
1119    tries to separate only these statements from the LOOP's body.
1120    Returns the number of distributed loops.  */
1121
1122 static int
1123 distribute_loop (struct loop *loop, VEC (gimple, heap) *stmts)
1124 {
1125   int res = 0;
1126   struct graph *rdg;
1127   gimple s;
1128   unsigned i;
1129   VEC (int, heap) *vertices;
1130
1131   if (loop->num_nodes > 2)
1132     {
1133       if (dump_file && (dump_flags & TDF_DETAILS))
1134         fprintf (dump_file,
1135                  "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1136                  loop->num);
1137
1138       return res;
1139     }
1140
1141   rdg = build_rdg (loop);
1142
1143   if (!rdg)
1144     {
1145       if (dump_file && (dump_flags & TDF_DETAILS))
1146         fprintf (dump_file,
1147                  "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1148                  loop->num);
1149
1150       return res;
1151     }
1152
1153   vertices = VEC_alloc (int, heap, 3);
1154
1155   if (dump_file && (dump_flags & TDF_DETAILS))
1156     dump_rdg (dump_file, rdg);
1157
1158   for (i = 0; VEC_iterate (gimple, stmts, i, s); i++)
1159     {
1160       int v = rdg_vertex_for_stmt (rdg, s);
1161
1162       if (v >= 0)
1163         {
1164           VEC_safe_push (int, heap, vertices, v);
1165
1166           if (dump_file && (dump_flags & TDF_DETAILS))
1167             fprintf (dump_file,
1168                      "ldist asked to generate code for vertex %d\n", v);
1169         }
1170     }
1171
1172   res = ldist_gen (loop, rdg, vertices);
1173   VEC_free (int, heap, vertices);
1174   free_rdg (rdg);
1175
1176   return res;
1177 }
1178
1179 /* Distribute all loops in the current function.  */
1180
1181 static unsigned int
1182 tree_loop_distribution (void)
1183 {
1184   struct loop *loop;
1185   loop_iterator li;
1186   int nb_generated_loops = 0;
1187
1188   FOR_EACH_LOOP (li, loop, 0)
1189     {
1190       VEC (gimple, heap) *work_list = VEC_alloc (gimple, heap, 3);
1191
1192       /* With the following working list, we're asking distribute_loop
1193          to separate the stores of the loop: when dependences allow,
1194          it will end on having one store per loop.  */
1195       stores_from_loop (loop, &work_list);
1196
1197       /* A simple heuristic for cache locality is to not split stores
1198          to the same array.  Without this call, an unrolled loop would
1199          be split into as many loops as unroll factor, each loop
1200          storing in the same array.  */
1201       remove_similar_memory_refs (&work_list);
1202
1203       nb_generated_loops = distribute_loop (loop, work_list);
1204
1205       if (dump_file && (dump_flags & TDF_DETAILS))
1206         {
1207           if (nb_generated_loops > 1)
1208             fprintf (dump_file, "Loop %d distributed: split to %d loops.\n",
1209                      loop->num, nb_generated_loops);
1210           else
1211             fprintf (dump_file, "Loop %d is the same.\n", loop->num);
1212         }
1213
1214       verify_loop_structure ();
1215
1216       VEC_free (gimple, heap, work_list);
1217     }
1218
1219   return 0;
1220 }
1221
1222 static bool
1223 gate_tree_loop_distribution (void)
1224 {
1225   return flag_tree_loop_distribution != 0;
1226 }
1227
1228 struct gimple_opt_pass pass_loop_distribution =
1229 {
1230  {
1231   GIMPLE_PASS,
1232   "ldist",                      /* name */
1233   gate_tree_loop_distribution,  /* gate */
1234   tree_loop_distribution,       /* execute */
1235   NULL,                         /* sub */
1236   NULL,                         /* next */
1237   0,                            /* static_pass_number */
1238   TV_TREE_LOOP_DISTRIBUTION,    /* tv_id */
1239   PROP_cfg | PROP_ssa,          /* properties_required */
1240   0,                            /* properties_provided */
1241   0,                            /* properties_destroyed */
1242   0,                            /* todo_flags_start */
1243   TODO_dump_func                /* todo_flags_finish */
1244  }
1245 };