diff options
Diffstat (limited to 'gcc/tree-ssa-loop-manip.c')
| -rw-r--r-- | gcc/tree-ssa-loop-manip.c | 340 |
1 files changed, 340 insertions, 0 deletions
diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index e6ff8a8..a06b352 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -506,3 +506,343 @@ standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, *insert_after = false; } } + +/* Copies phi node arguments for duplicated blocks. The index of the first + duplicated block is FIRST_NEW_BLOCK. */ + +static void +copy_phi_node_args (unsigned first_new_block) +{ + unsigned i; + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + BASIC_BLOCK (i)->rbi->duplicated = 1; + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + add_phi_args_after_copy_bb (BASIC_BLOCK (i)); + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + BASIC_BLOCK (i)->rbi->duplicated = 0; +} + +/* Renames variables in the area copied by tree_duplicate_loop_to_header_edge. + FIRST_NEW_BLOCK is the first block in the copied area. DEFINITIONS is + a bitmap of all ssa names defined inside the loop. */ + +static void +rename_variables (unsigned first_new_block, bitmap definitions) +{ + unsigned i, copy_number = 0; + basic_block bb; + htab_t ssa_name_map = NULL; + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + { + bb = BASIC_BLOCK (i); + + /* We assume that first come all blocks from the first copy, then all + blocks from the second copy, etc. */ + if (copy_number != (unsigned) bb->rbi->copy_number) + { + allocate_ssa_names (definitions, &ssa_name_map); + copy_number = bb->rbi->copy_number; + } + + rewrite_to_new_ssa_names_bb (bb, ssa_name_map); + } + + htab_delete (ssa_name_map); +} + +/* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB. */ + +static void +set_phi_def_stmts (basic_block bb) +{ + tree phi; + + for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi; +} + +/* The same ad cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates + ssa. In order to achieve this, only loops whose exits all lead to the same + location are handled. + + FIXME: we create some degenerate phi nodes that could be avoided by copy + propagating them instead. Unfortunately this is not completely + straightforward due to problems with constant folding. */ + +bool +tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, + struct loops *loops, + unsigned int ndupl, sbitmap wont_exit, + edge orig, edge *to_remove, + unsigned int *n_to_remove, int flags) +{ + unsigned first_new_block; + basic_block bb; + unsigned i; + tree phi, arg, map, def; + bitmap definitions; + + if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) + return false; + if (!(loops->state & LOOPS_HAVE_PREHEADERS)) + return false; + +#ifdef ENABLE_CHECKING + verify_loop_closed_ssa (); +#endif + + gcc_assert (!any_marked_for_rewrite_p ()); + + first_new_block = last_basic_block; + if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, + orig, to_remove, n_to_remove, flags)) + return false; + + /* Readd the removed phi args for e. */ + map = PENDING_STMT (e); + PENDING_STMT (e) = NULL; + + for (phi = phi_nodes (e->dest), arg = map; + phi; + phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg)) + { + def = TREE_VALUE (arg); + add_phi_arg (&phi, def, e); + } + gcc_assert (arg == NULL); + + /* Copy the phi node arguments. */ + copy_phi_node_args (first_new_block); + + /* Rename the variables. */ + definitions = marked_ssa_names (); + rename_variables (first_new_block, definitions); + unmark_all_for_rewrite (); + BITMAP_XFREE (definitions); + + /* For some time we have the identical ssa names as results in multiple phi + nodes. When phi node is resized, it sets SSA_NAME_DEF_STMT of its result + to the new copy. This means that we cannot easily ensure that the ssa + names defined in those phis are pointing to the right one -- so just + recompute SSA_NAME_DEF_STMT for them. */ + + for (i = first_new_block; i < (unsigned) last_basic_block; i++) + { + bb = BASIC_BLOCK (i); + set_phi_def_stmts (bb); + if (bb->rbi->copy_number == 1) + set_phi_def_stmts (bb->rbi->original); + } + + scev_reset (); +#ifdef ENABLE_CHECKING + verify_loop_closed_ssa (); +#endif + + return true; +} + +/*--------------------------------------------------------------------------- + Loop versioning + ---------------------------------------------------------------------------*/ + +/* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy + of 'first'. Both of them are dominated by 'new_head' basic block. When + 'new_head' was created by 'second's incoming edge it received phi arguments + on the edge by split_edge(). Later, additional edge 'e' was created to + connect 'new_head' and 'first'. Now this routine adds phi args on this + additional edge 'e' that new_head to second edge received as part of edge + splitting. +*/ + +static void +lv_adjust_loop_header_phi (basic_block first, basic_block second, + basic_block new_head, edge e) +{ + tree phi1, phi2; + + /* Browse all 'second' basic block phi nodes and add phi args to + edge 'e' for 'first' head. PHI args are always in correct order. */ + + for (phi2 = phi_nodes (second), phi1 = phi_nodes (first); + phi2 && phi1; + phi2 = TREE_CHAIN (phi2), phi1 = TREE_CHAIN (phi1)) + { + int i; + for (i = 0; i < PHI_NUM_ARGS (phi2); i++) + { + if (PHI_ARG_EDGE (phi2, i)->src == new_head) + { + tree def = PHI_ARG_DEF (phi2, i); + add_phi_arg (&phi1, def, e); + } + } + } +} + +/* Adjust entry edge for lv. + + e is a incoming edge. + + --- edge e ---- > [second_head] + + Split it and insert new conditional expression and adjust edges. + + --- edge e ---> [cond expr] ---> [first_head] + | + +---------> [second_head] + +*/ + +static basic_block +lv_adjust_loop_entry_edge (basic_block first_head, + basic_block second_head, + edge e, + tree cond_expr) +{ + block_stmt_iterator bsi; + basic_block new_head = NULL; + tree goto1 = NULL_TREE; + tree goto2 = NULL_TREE; + tree new_cond_expr = NULL_TREE; + edge e0, e1; + + gcc_assert (e->dest == second_head); + + /* Split edge 'e'. This will create a new basic block, where we can + insert conditional expr. */ + new_head = split_edge (e); + + /* Build new conditional expr */ + goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head)); + goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head)); + new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2); + + /* Add new cond. in new head. */ + bsi = bsi_start (new_head); + bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT); + + /* Adjust edges appropriately to connect new head with first head + as well as second head. */ + e0 = new_head->succ; + e0->flags &= ~EDGE_FALLTHRU; + e0->flags |= EDGE_FALSE_VALUE; + e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE); + set_immediate_dominator (CDI_DOMINATORS, first_head, new_head); + set_immediate_dominator (CDI_DOMINATORS, second_head, new_head); + + /* Adjust loop header phi nodes. */ + lv_adjust_loop_header_phi (first_head, second_head, new_head, e1); + + return new_head; +} + +/* Add phi args using PENDINT_STMT list. */ + +static void +lv_update_pending_stmts (edge e) +{ + basic_block dest; + tree phi, arg, def; + + if (!PENDING_STMT (e)) + return; + + dest = e->dest; + + for (phi = phi_nodes (dest), arg = PENDING_STMT (e); + phi; + phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg)) + { + def = TREE_VALUE (arg); + add_phi_arg (&phi, def, e); + } + + PENDING_STMT (e) = NULL; +} + + +/* Main entry point for Loop Versioning transformation. + +This transformation given a condition and a loop, creates +-if (condition) { loop_copy1 } else { loop_copy2 }, +where loop_copy1 is the loop transformed in one way, and loop_copy2 +is the loop transformed in another way (or unchanged). 'condition' +may be a run time test for things that were not resolved by static +analysis (overlapping ranges (anti-aliasing), alignment, etc.). */ + +struct loop * +tree_ssa_loop_version (struct loops *loops, struct loop * loop, + tree cond_expr, basic_block *condition_bb) +{ + edge entry, latch_edge, exit; + basic_block first_head, second_head; + int irred_flag; + struct loop *nloop; + + /* CHECKME: Loop versioning does not handle nested loop at this point. */ + if (loop->inner) + return NULL; + + /* Record entry and latch edges for the loop */ + entry = loop_preheader_edge (loop); + + /* Note down head of loop as first_head. */ + first_head = entry->dest; + + /* Duplicate loop. */ + irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; + entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; + if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1, + NULL, NULL, NULL, NULL, 0)) + { + entry->flags |= irred_flag; + return NULL; + } + + /* After duplication entry edge now points to new loop head block. + Note down new head as second_head. */ + second_head = entry->dest; + + /* Split loop entry edge and insert new block with cond expr. */ + *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry, + cond_expr); + + latch_edge = loop->latch->rbi->copy->succ; + nloop = loopify (loops, + latch_edge, + loop->header->rbi->copy->pred, + *condition_bb, + false /* Do not redirect all edges. */); + + exit = loop->single_exit; + if (exit) + nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest); + + /* loopify redirected latch_edge. Update its PENDING_STMTS. */ + lv_update_pending_stmts (latch_edge); + + /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */ + lv_update_pending_stmts (FALLTHRU_EDGE (*condition_bb)); + + /* Adjust irreducible flag. */ + if (irred_flag) + { + (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP; + loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP; + loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP; + (*condition_bb)->pred->flags |= EDGE_IRREDUCIBLE_LOOP; + } + + /* At this point condition_bb is loop predheader with two successors, + first_head and second_head. Make sure that loop predheader has only + one successor. */ + loop_split_edge_with (loop_preheader_edge (loop), NULL); + loop_split_edge_with (loop_preheader_edge (nloop), NULL); + + return nloop; +} |