gcc/tree-loop-distribution.c

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