gcc/tree-loop-distribution.c

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