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