gcc/tree-loop-distribution.c

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