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