#include "config.h"#include "system.h"#include "coretypes.h"#include "tree.h"#include "flags.h"#include "basic-block.h"#include "function.h"#include "gimple.h"#include "gimple-ssa.h"#include "tree-phinodes.h"#include "tree-ssa.h"#include "tree-ssa-threadupdate.h"#include "dumpfile.h"#include "cfgloop.h"#include "hash-table.h"#include "dbgcnt.h"
Data Structures | |
| struct | el |
| struct | redirection_data |
| struct | ssa_local_info_t |
| struct | thread_stats_d |
Macros | |
| #define | THREAD_PATH(E) ((vec<jump_thread_edge *> *)(E)->aux) |
Enumerations | |
| enum | bb_dom_status { DOMST_NONDOMINATING, DOMST_LOOP_BROKEN, DOMST_DOMINATING } |
Variables | |
| static vec< vec < jump_thread_edge * > * > | paths |
| struct thread_stats_d | thread_stats |
| static hash_table < redirection_data > | redirection_data |
| static basic_block | dbds_ce_stop |
Macro Definition Documentation
| #define THREAD_PATH | ( | E | ) | ((vec<jump_thread_edge *> *)(E)->aux) |
When we start updating the CFG for threading, data necessary for jump threading is attached to the AUX field for the incoming edge. Use these macros to access the underlying structure attached to the AUX field.
Referenced by copy_phi_args(), create_block_for_threading(), def_split_header_continue_p(), redirection_block_p(), and thread_through_loop_header().
Enumeration Type Documentation
| enum bb_dom_status |
Function Documentation
|
static |
For each PHI in BB, copy the argument associated with SRC_E to TGT_E.
References edge_def::count, basic_block_def::count, make_edge(), redirection_data::path, edge_def::probability, REG_BR_PROB_BASE, rescan_loop_exit(), and THREAD_PATH.
|
static |
Create a duplicate of BB. Record the duplicate block in RD.
We can use the generic block duplication code and simply remove the stuff we do not need.
Zero out the profile, since the block is unreachable for now.
References redirection_data::dup_block, redirection_data::incoming_edges, NULL, redirection_data::path, path, and THREAD_PATH.
Referenced by ssa_fix_duplicate_block_edges().
|
static |
Given a duplicate block and its single destination (both stored in RD). Create an edge between the duplicate and its single destination.
Add an additional argument to any PHI nodes at the single destination.
We have to copy path – which means creating a new vector as well as all the jump_thread_edge entries.
Sadly, the elements of the vector are pointers and need to
be copied as well. If there are any PHI nodes at the destination of the outgoing edge from the duplicate block, then we will need to add a new argument to them. The argument should have the same value as the argument associated with the outgoing edge stored in RD.
|
static |
Referenced by thread_single_edge().
|
static |
Return true if BB is part of the new pre-header that is created when threading the latch to DATA.
References edge_def::dest, EDGE_COPY_SRC_JOINER_BLOCK, and THREAD_PATH.
|
static |
This function assumes BB is a successor of LOOP->header. If that is not the case return DOMST_NONDOMINATING which is always safe.
Check that BB dominates LOOP->latch, and that it is back-reachable from it.
|
static |
Dump a jump threading path, including annotations about each edge in the path.
We can get paths with a NULL edge when the final destination of a jump thread turns out to be a constant address. We dump those paths when debugging, so we have to be prepared for that possibility here.
|
staticread |
Given an outgoing edge E lookup and return its entry in our hash table.
If INSERT is true, then we insert the entry into the hash table if it is not already present. INCOMING_EDGE is added to the list of incoming edges associated with E in the hash table.
Build a hash table element so we can see if E is already in the table.
This will only happen if INSERT is false and the entry is not in the hash table.
This will only happen if E was not in the hash table and INSERT is true.
E was in the hash table.
Free ELT as we do not need it anymore, we will extract the
relevant entry from the hash table itself. Get the entry stored in the hash table.
If insertion was requested, then we need to add INCOMING_EDGE
to the list of incoming edges associated with E.
References el::e, redirection_data::incoming_edges, el::next, and NULL.
|
static |
Walk through the registered jump threads and convert them into a form convenient for this pass.
Any block which has incoming edges threaded to outgoing edges will have its entry in THREADED_BLOCK set.
Any threaded edge will have its new outgoing edge stored in the original edge's AUX field.
This form avoids the need to walk all the edges in the CFG to discover blocks which need processing and avoids unnecessary hash table lookups to map from threaded edge to new target.
Move the jump threading requests from PATHS to each edge which starts a jump thread path.
If we have a joiner block (J) which has two successors S1 and S2 and we are threading though S1 and the final destination of the thread is S2, then we must verify that any PHI nodes in S2 have the same PHI arguments for the edge J->S2 and J->S1->...->S2. We used to detect this prior to registering the jump thread, but that prohibits propagation of edge equivalences into non-dominated PHI nodes as the equivalency test might occur before propagation. This works for now, but will need improvement as part of the FSA optimization. Note since we've moved the thread request data to the edges, we have to iterate on those rather than the threaded_edges vector.
If optimizing for size, only thread through block if we don't have to duplicate it or it's an otherwise empty redirection block.
Look for jump threading paths which cross multiple loop headers. The code to thread through loop headers will change the CFG in ways that break assumptions made by the loop optimization code. We don't want to blindly cancel the requests. We can instead do better by trimming off the end of the jump thread path.
Basically we're looking for a situation where we can see
3 or more loop structures on a jump threading path. See if this is a loop father we have not seen before.
We've already seen two loop fathers, so we
need to trim this jump threading path. Trim from entry I onwards.
Now that we've truncated the path, make sure
what's left is still valid. We need at least
two edges on the path and the last edge can not
be a joiner. This should never happen, but let's
be safe.
References edge_def::aux, EDGE_COPY_SRC_JOINER_BLOCK, and NULL.
|
static |
E1 and E2 are edges into the same basic block. Return TRUE if the PHI arguments associated with those edges are equal or there are no PHI arguments, otherwise return FALSE.
|
static |
Return true if this block has no executable statements other than a simple ctrl flow instruction. When the number of outgoing edges is one, this is equivalent to a "forwarder" block.
Advance to the first executable statement.
Check if this is an empty block.
Test that we've reached the terminating control statement.
References EDGE_COPY_SRC_BLOCK, EDGE_COPY_SRC_JOINER_BLOCK, loop::header, loop::latch, loop_exit_edge_p(), loop_latch_edge(), LOOPS_NEED_FIXUP, loops_state_set(), NULL, and THREAD_PATH.
| void register_jump_thread | ( | ) |
Register a jump threading opportunity. We queue up all the jump threading opportunities discovered by a pass and update the CFG and SSA form all at once.
E is the edge we can thread, E2 is the new target edge, i.e., we are effectively recording that E->dest can be changed to E2->dest after fixing the SSA graph.
First make sure there are no NULL outgoing edges on the jump threading path. That can happen for jumping to a constant address.
|
static |
Remove the last statement in block BB if it is a control statement Also remove all outgoing edges except the edge which reaches DEST_BB. If DEST_BB is NULL, then remove all outgoing edges.
If the duplicate ends with a control statement, then remove it.
Note that if we are duplicating the template block rather than the original basic block, then the duplicate might not have any real statements in it.
References edge_def::dest, ei_next(), and remove_edge().
| int ssa_create_duplicates | ( | struct redirection_data ** | slot, |
| ssa_local_info_t * | local_info | ||
| ) |
Hash table traversal callback routine to create duplicate blocks.
Create a template block if we have not done so already. Otherwise use the template to create a new block.
We do not create any outgoing edges for the template. We will
take care of that in a later traversal. That way we do not
create edges that are going to just be deleted. Go ahead and wire up outgoing edges and update PHIs for the duplicate
block. Keep walking the hash table.
References ssa_fix_duplicate_block_edges().
| void ssa_fix_duplicate_block_edges | ( | struct redirection_data * | rd, |
| ssa_local_info_t * | local_info | ||
| ) |
Wire up the outgoing edges from the duplicate block and update any PHIs as needed.
If we were threading through an joiner block, then we want to keep its control statement and redirect an outgoing edge. Else we want to remove the control statement & edges, then create a new outgoing edge. In both cases we may need to update PHIs.
This updates the PHIs at the destination of the duplicate
block. Find the edge from the duplicate block to the block we're
threading through. That's the edge we want to redirect. If we redirected the edge, then we need to copy PHI arguments
at the target. If the edge already existed (e2 != victim case),
then the PHIs in the target already have the correct arguments.
References ssa_local_info_t::bb, create_block_for_threading(), redirection_data::dup_block, and ssa_local_info_t::template_block.
Referenced by ssa_create_duplicates().
|
inline |
We did not create any outgoing edges for the template block during block creation. This hash table traversal callback creates the outgoing edge for the template block.
If this is the template block halt the traversal after updating it appropriately.
If we were threading through an joiner block, then we want to keep its control statement and redirect an outgoing edge. Else we want to remove the control statement & edges, then create a new outgoing edge. In both cases we may need to update PHIs.
| int ssa_redirect_edges | ( | struct redirection_data ** | slot, |
| ssa_local_info_t * | local_info | ||
| ) |
Hash table traversal callback to redirect each incoming edge associated with this hash table element to its new destination.
Walk over all the incoming edges associated associated with this hash table entry.
Go ahead and free this element from the list. Doing this now
avoids the need for another list walk when we destroy the hash
table. Excessive jump threading may make frequencies large enough so
the computation overflows. In the case of threading through a joiner block, the outgoing
edges from the duplicate block were updated when they were
redirected during ssa_fix_duplicate_block_edges. Redirect the incoming edge (possibly to the joiner block) to the
appropriate duplicate block. Go ahead and clear E->aux. It's not needed anymore and failure
to clear it will cause all kinds of unpleasant problems later. Indicate that we actually threaded one or more jumps.
|
static |
Wrapper for thread_block_1 so that we can first handle jump thread paths which do not involve copying joiner blocks, then handle jump thread paths which have joiner blocks.
By doing things this way we can be as aggressive as possible and not worry that copying a joiner block will create a jump threading opportunity.
|
static |
BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB is reached via one or more specific incoming edges, we know which outgoing edge from BB will be traversed.
We want to redirect those incoming edges to the target of the appropriate outgoing edge. Doing so avoids a conditional branch and may expose new optimization opportunities. Note that we have to update dominator tree and SSA graph after such changes.
The key to keeping the SSA graph update manageable is to duplicate the side effects occurring in BB so that those side effects still occur on the paths which bypass BB after redirecting edges.
We accomplish this by creating duplicates of BB and arranging for the duplicates to unconditionally pass control to one specific successor of BB. We then revector the incoming edges into BB to the appropriate duplicate of BB.
If NOLOOP_ONLY is true, we only perform the threading as long as it does not affect the structure of the loops in a nontrivial way.
If JOINERS is true, then thread through joiner blocks as well.
E is an incoming edge into BB that we may or may not want to redirect to a duplicate of BB.
To avoid scanning a linear array for the element we need we instead use a hash table. For normal code there should be no noticeable difference. However, if we have a block with a large number of incoming and outgoing edges such linear searches can get expensive.
If we thread the latch of the loop to its exit, the loop ceases to exist. Make sure we do not restrict ourselves in order to preserve this loop.
Record each unique threaded destination into a hash table for efficient lookups.
If NOLOOP_ONLY is true, we only allow threading through the
header of a loop to exit edges.
There are two cases to consider. The first when BB is the
loop header. We will attempt to thread this elsewhere, so
we can just continue here. The second occurs when there was loop header buried in a jump
threading path. We do not try and thread this elsewhere, so
just cancel the jump threading request by clearing the AUX
field now. Since this case is not handled by our special code
to thread through a loop header, we must explicitly
cancel the threading request here. Insert the outgoing edge into the hash table if it is not
already in the hash table. We do not update dominance info.
We know we only thread through the loop header to loop exits. Let the basic block duplication hook know we are not creating a multiple entry loop.
Now create duplicates of BB. Note that for a block with a high outgoing degree we can waste a lot of time and memory creating and destroying useless edges. So we first duplicate BB and remove the control structure at the tail of the duplicate as well as all outgoing edges from the duplicate. We then use that duplicate block as a template for the rest of the duplicates.
The template does not have an outgoing edge. Create that outgoing edge and update PHI nodes as the edge's target as necessary. We do this after creating all the duplicates to avoid creating unnecessary edges.
The hash table traversals above created the duplicate blocks (and the statements within the duplicate blocks). This loop creates PHI nodes for the duplicated blocks and redirects the incoming edges into BB to reach the duplicates of BB.
Done with this block. Clear REDIRECTION_DATA.
Indicate to our caller whether or not any jumps were threaded.
References edge_def::aux, and NULL.
|
static |
Threads edge E through E->dest to the edge THREAD_TARGET (E). Returns the copy of E->dest created during threading, or E->dest if it was not necessary to copy it (E is its single predecessor).
If BB has just a single predecessor, we should only remove the
control statements at its end, and successors except for ETO.
And fixup the flags on the single remaining edge.
Otherwise, we need to create a copy.
References dbds_continue_enumeration_p(), dfs_enumerate_from(), DOMST_DOMINATING, DOMST_LOOP_BROKEN, DOMST_NONDOMINATING, FOR_EACH_EDGE, loop::header, loop::latch, loop::num_nodes, basic_block_def::preds, and edge_def::src.
| bool thread_through_all_blocks | ( | ) |
Walk through all blocks and thread incoming edges to the appropriate outgoing edge for each edge pair recorded in THREADED_EDGES.
It is the caller's responsibility to fix the dominance information and rewrite duplicated SSA_NAMEs back into SSA form.
If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through loop headers if it does not simplify the loop.
Returns true if one or more edges were threaded, false otherwise.
We must know about loops in order to preserve them.
First perform the threading requests that do not affect loop structure.
Then perform the threading through loop headers. We start with the innermost loop, so that the changes in cfg we perform won't affect further threading.
Assume we had a jump thread path which went from the latch to the exit and a path which goes from outside to inside the same loop. If the latch to exit was handled first, we will thread it and clear loop->header. The second path will be ignored by thread_block because we're going through a loop header. It will also be ignored by the loop above because loop->header is NULL. This results in the second path never being threaded. The failure mode is a dangling AUX field. This is inherently a bit of a pain to fix, so we just walk all the blocks and all the incoming edges to those blocks and clear their AUX fields.
|
static |
Thread jumps through the header of LOOP. Returns true if cfg changes. If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges to the inside of the loop.
We have already threaded through headers to exits, so all the threading
requests now are to the inside of the loop. We need to avoid creating
irreducible regions (i.e., loops with more than one entry block), and
also loop with several latch edges, or new subloops of the loop (although
there are cases where it might be appropriate, it is difficult to decide,
and doing it wrongly may confuse other optimizers).
We could handle more general cases here. However, the intention is to
preserve some information about the loop, which is impossible if its
structure changes significantly, in a way that is not well understood.
Thus we only handle few important special cases, in which also updating
of the loop-carried information should be feasible:
1) Propagation of latch edge to a block that dominates the latch block
of a loop. This aims to handle the following idiom:
first = 1;
while (1)
{
if (first)
initialize;
first = 0;
body;
}
After threading the latch edge, this becomes
first = 1;
if (first)
initialize;
while (1)
{
first = 0;
body;
}
The original header of the loop is moved out of it, and we may thread
the remaining edges through it without further constraints.
2) All entry edges are propagated to a single basic block that dominates
the latch block of the loop. This aims to handle the following idiom
(normally created for "for" loops):
i = 0;
while (1)
{
if (i >= 100)
break;
body;
i++;
}
This becomes
i = 0;
while (1)
{
body;
i++;
if (i >= 100)
break;
}
Threading through the header won't improve the code if the header has just one successor.
If latch is not threaded, and there is a header
edge that is not threaded, we would create loop
with multiple entries. Two targets of threading would make us create loop
with multiple entries. There are no threading requests.
Redirecting to empty loop latch is useless.
The target block must dominate the loop latch, otherwise we would be creating a subloop.
If the loop ceased to exist, mark it as such, and thread through its
original header. If the target of the threading is a header of a subloop, we need
to create a preheader for it, so that the headers of the two loops
do not merge. First handle the case latch edge is redirected. We are copying
the loop header but not creating a multiple entry loop. Make the
cfg manipulation code aware of that fact. Remove the new pre-header blocks from our loop.
If the new header has multiple latches mark it so.
Cancel remaining threading requests that would make the
loop a multiple entry loop. Thread the remaining edges through the former header.
Now consider the case entry edges are redirected to the new entry
block. Remember one entry edge, so that we can find the new
preheader (its destination after threading). The duplicate of the header is the new preheader of the loop. Ensure
that it is placed correctly in the loop hierarchy. Create the new latch block. This is always necessary, as the latch
must have only a single successor, but the original header had at
least two successors. We failed to thread anything. Cancel the requests.
References edge_def::aux, edge_def::dest, EDGE_COPY_SRC_JOINER_BLOCK, and THREAD_PATH.
|
static |
We have recently made a copy of ORIG_BB, including its outgoing edges. The copy is NEW_BB. Every PHI node in every direct successor of ORIG_BB has a new argument associated with edge from NEW_BB to the successor. Initialize the PHI argument so that it is equal to the PHI argument associated with the edge from ORIG_BB to the successor.
Variable Documentation
|
static |
Callback for dfs_enumerate_from. Returns true if BB is different from STOP and DBDS_CE_STOP.
|
static |
Passes which use the jump threading code register jump threading opportunities as they are discovered. We keep the registered jump threading opportunities in this vector as edge pairs (original_edge, target_edge).
Main data structure to hold information for duplicates of BB.
| struct thread_stats_d thread_stats |
