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