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