gcc/tree-loop-distribution.c

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