gcc/tree-loop-distribution.c

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