LLVM  7.0.0svn
Classes | Public Types | Public Member Functions | List of all members
llvm::LoopTraversal Class Reference

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)
 

Detailed Description

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.

Member Typedef Documentation

◆ TraversalOrder

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.

Constructor & Destructor Documentation

◆ LoopTraversal()

llvm::LoopTraversal::LoopTraversal ( )
inline

Definition at line 102 of file LoopTraversal.h.

Member Function Documentation

◆ traverse()

LoopTraversal::TraversalOrder LoopTraversal::traverse ( MachineFunction MF)

The documentation for this class was generated from the following files: