|
LLVM
8.0.1
|
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and ExecutionDomainFix. More...
#include "llvm/CodeGen/LoopTraversal.h"
Classes | |
| struct | TraversedMBBInfo |
Public Types | |
| typedef SmallVector< TraversedMBBInfo, 4 > | TraversalOrder |
| Identifies basic blocks that are part of loops and should to be visited twice and returns efficient traversal order for all the blocks. More... | |
Public Member Functions | |
| LoopTraversal () | |
| TraversalOrder | traverse (MachineFunction &MF) |
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and ExecutionDomainFix.
It identifies basic blocks that are part of loops and should to be visited twice and returns efficient traversal order for all the blocks.
We want to visit every instruction in every basic block in order to update it's execution domain or collect clearance information. However, for the clearance calculation, we need to know clearances from all predecessors (including any backedges), therfore we need to visit some blocks twice. As an example, consider the following loop.
PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT ^ | +-------------------------------—+
The iteration order this pass will return is as follows: Optimized: PH A B C A' B' C' D
The basic block order is constructed as follows: Once we finish processing some block, we update the counters in MBBInfos and re-process any successors that are now 'done'. We call a block that is ready for its final round of processing done (isBlockDone), e.g. when all predecessor information is known.
Note that a naive traversal order would be to do two complete passes over all basic blocks/instructions, the first for recording clearances, the second for updating clearance based on backedges. However, for functions without backedges, or functions with a lot of straight-line code, and a small loop, that would be a lot of unnecessary work (since only the BBs that are part of the loop require two passes).
E.g., the naive iteration order for the above exmple is as follows: Naive: PH A B C D A' B' C' D'
In the optimized approach we avoid processing D twice, because we can entirely process the predecessors before getting to D.
Definition at line 66 of file LoopTraversal.h.
Identifies basic blocks that are part of loops and should to be visited twice and returns efficient traversal order for all the blocks.
Definition at line 106 of file LoopTraversal.h.
|
inline |
Definition at line 102 of file LoopTraversal.h.
| LoopTraversal::TraversalOrder LoopTraversal::traverse | ( | MachineFunction & | MF | ) |
Definition at line 25 of file LoopTraversal.cpp.
References assert(), llvm::SmallVectorImpl< T >::assign(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::MachineFunction::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorBase::empty(), llvm::MachineBasicBlock::getNumber(), llvm::MachineFunction::getNumBlockIDs(), llvm::SmallVectorTemplateBase< T >::pop_back(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorBase::size(), and llvm::MachineBasicBlock::successors().
Referenced by llvm::ReachingDefAnalysis::runOnMachineFunction(), and llvm::ExecutionDomainFix::runOnMachineFunction().
1.8.13