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