llvm::LoopTraversal

Declared in <llvm/CodeGen/LoopTraversal.h>

Provides the basic block traversal order used by passes like ReachingDefAnalysis and ExecutionDomainFix. It identifies basic blocks that are part of loops and should be visited twice and returns an 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.

Created with MrDocs