gcc/tree-loop-distribution.c

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