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