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