gcc/tree-loop-distribution.c

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