/* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
Otherwise, when we finish traversing each of the sub-graphs, we
won't know whether the variables were found in the sub-graphs or
- if they had been found in a block upstream from BB. */
+ if they had been found in a block upstream from BB.
+
+ This is actually a bad idea is some cases, particularly jump
+ threading. Consider a CFG like the following:
+
+ 0
+ /|
+ 1 |
+ \|
+ 2
+ / \
+ 3 4
+
+ Assume that one or more operands in the conditional at the
+ end of block 0 are used in a conditional in block 2, but not
+ anywhere in block 1. In this case we will not insert any
+ assert statements in block 1, which may cause us to miss
+ opportunities to optimize, particularly for jump threading. */
FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
}
}
+/* Stack of dest,src equivalency pairs that need to be restored after
+ each attempt to thread a block's incoming edge to an outgoing edge.
+
+ A NULL entry is used to mark the end of pairs which need to be
+ restored. */
+static VEC(tree,heap) *stack;
+
+/* A trivial wrapper so that we can present the generic jump
+ threading code with a simple API for simplifying statements. */
+static tree
+simplify_stmt_for_jump_threading (tree stmt)
+{
+ /* We only use VRP information to simplify conditionals. This is
+ overly conservative, but it's unclear if doing more would be
+ worth the compile time cost. */
+ if (TREE_CODE (stmt) != COND_EXPR)
+ return NULL;
+
+ return vrp_evaluate_conditional (COND_EXPR_COND (stmt), true);
+}
+
+/* Blocks which have more than one predecessor and more than
+ one successor present jump threading opportunities. ie,
+ when the block is reached from a specific predecessor, we
+ may be able to determine which of the outgoing edges will
+ be traversed. When this optimization applies, we are able
+ to avoid conditionals at runtime and we may expose secondary
+ optimization opportunities.
+
+ This routine is effectively a driver for the generic jump
+ threading code. It basically just presents the generic code
+ with edges that may be suitable for jump threading.
+
+ Unlike DOM, we do not iterate VRP if jump threading was successful.
+ While iterating may expose new opportunities for VRP, it is expected
+ those opportunities would be very limited and the compile time cost
+ to expose those opportunities would be significant.
+
+ As jump threading opportunities are discovered, they are registered
+ for later realization. */
+
+static void
+identify_jump_threads (void)
+{
+ basic_block bb;
+ tree dummy;
+
+ /* Ugh. When substituting values earlier in this pass we can
+ wipe the dominance information. So rebuild the dominator
+ information as we need it within the jump threading code. */
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ /* We do not allow VRP information to be used for jump threading
+ across a back edge in the CFG. Otherwise it becomes too
+ difficult to avoid eliminating loop exit tests. Of course
+ EDGE_DFS_BACK is not accurate at this time so we have to
+ recompute it. */
+ mark_dfs_back_edges ();
+
+ /* Allocate our unwinder stack to unwind any temporary equivalences
+ that might be recorded. */
+ stack = VEC_alloc (tree, heap, 20);
+
+ /* To avoid lots of silly node creation, we create a single
+ conditional and just modify it in-place when attempting to
+ thread jumps. */
+ dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL);
+ dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL);
+
+ /* Walk through all the blocks finding those which present a
+ potential jump threading opportunity. We could set this up
+ as a dominator walker and record data during the walk, but
+ I doubt it's worth the effort for the classes of jump
+ threading opportunities we are trying to identify at this
+ point in compilation. */
+ FOR_EACH_BB (bb)
+ {
+ tree last, cond;
+
+ /* If the generic jump threading code does not find this block
+ interesting, then there is nothing to do. */
+ if (! potentially_threadable_block (bb))
+ continue;
+
+ /* We only care about blocks ending in a COND_EXPR. While there
+ may be some value in handling SWITCH_EXPR here, I doubt it's
+ terribly important. */
+ last = bsi_stmt (bsi_last (bb));
+ if (TREE_CODE (last) != COND_EXPR)
+ continue;
+
+ /* We're basically looking for any kind of conditional with
+ integral type arguments. */
+ cond = COND_EXPR_COND (last);
+ if ((TREE_CODE (cond) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (cond)))
+ || (COMPARISON_CLASS_P (cond)
+ && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0)))
+ && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME
+ || is_gimple_min_invariant (TREE_OPERAND (cond, 1)))
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
+ {
+ edge_iterator ei;
+ edge e;
+
+ /* We've got a block with multiple predecessors and multiple
+ successors which also ends in a suitable conditional. For
+ each predecessor, see if we can thread it to a specific
+ successor. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ /* Do not thread across back edges or abnormal edges
+ in the CFG. */
+ if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
+ continue;
+
+ thread_across_edge (dummy, e, true,
+ &stack,
+ simplify_stmt_for_jump_threading);
+ }
+ }
+ }
+
+ /* We do not actually update the CFG or SSA graphs at this point as
+ ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
+ handle ASSERT_EXPRs gracefully. */
+}
+
+/* We identified all the jump threading opportunities earlier, but could
+ not transform the CFG at that time. This routine transforms the
+ CFG and arranges for the dominator tree to be rebuilt if necessary.
+
+ Note the SSA graph update will occur during the normal TODO
+ processing by the pass manager. */
+static void
+finalize_jump_threads (void)
+{
+ bool cfg_altered = false;
+ cfg_altered = thread_through_all_blocks ();
+
+ /* If we threaded jumps, then we need to recompute the dominance
+ information, to safely do that we must clean up the CFG first. */
+ if (cfg_altered)
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ cleanup_tree_cfg ();
+ calculate_dominance_info (CDI_DOMINATORS);
+ }
+ VEC_free (tree, heap, stack);
+}
/* Traverse all the blocks folding conditionals with known ranges. */
substitute_and_fold (single_val_range, true);
+ /* We must identify jump threading opportunities before we release
+ the datastructures built by VRP. */
+ identify_jump_threads ();
+
/* Free allocated memory. */
for (i = 0; i < num_ssa_names; i++)
if (vr_value[i])
current_loops = NULL;
}
+ /* ASSERT_EXPRs must be removed before finalizing jump threads
+ as finalizing jump threads calls the CFG cleanup code which
+ does not properly handle ASSERT_EXPRs. */
remove_range_assertions ();
+ finalize_jump_threads ();
+
}
static bool
OSDN Git Service
