gcc/tree-loop-distribution.c

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