Go to the documentation of this file.
78 #define DEBUG_TYPE "fix-irreducible"
107 "Convert irreducible control-flow into natural loops",
121 auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()
122 : LI.getTopLevelLoopsVector();
127 CandidateLoops.begin(), CandidateLoops.end(), [&](
Loop *L) {
128 return L == NewLoop || !Blocks.contains(L->getHeader());
131 CandidateLoops.erase(FirstChild, CandidateLoops.end());
133 for (
Loop *Child : ChildLoops) {
134 LLVM_DEBUG(
dbgs() <<
"child loop: " << Child->getHeader()->getName()
139 if (Headers.count(Child->getHeader())) {
140 for (
auto BB : Child->blocks()) {
141 if (LI.getLoopFor(
BB) != Child)
143 LI.changeLoopFor(
BB, NewLoop);
147 std::vector<Loop *> GrandChildLoops;
148 std::swap(GrandChildLoops, Child->getSubLoopsVector());
149 for (
auto GrandChildLoop : GrandChildLoops) {
150 GrandChildLoop->setParentLoop(
nullptr);
151 NewLoop->addChildLoop(GrandChildLoop);
158 Child->setParentLoop(
nullptr);
159 NewLoop->addChildLoop(Child);
173 for (
auto H : Headers) {
179 for (
auto H : Headers) {
186 dbgs() <<
"Found predecessors:";
187 for (
auto P : Predecessors) {
188 dbgs() <<
" " <<
P->getName();
198 #if defined(EXPENSIVE_CHECKS)
217 for (
auto G : GuardBlocks) {
219 NewLoop->addBasicBlockToLoop(
G, LI);
223 for (
auto BB : Blocks) {
224 NewLoop->addBlockEntry(
BB);
234 << NewLoop->getHeader()->getName() <<
"\n");
238 NewLoop->verifyLoop();
242 #if defined(EXPENSIVE_CHECKS)
244 #endif // EXPENSIVE_CHECKS
269 template <
class Graph>
271 bool Changed =
false;
272 for (
auto Scc =
scc_begin(
G); !Scc.isAtEnd(); ++Scc) {
277 for (
auto N : *Scc) {
305 if (Headers.
size() == 1) {
307 LLVM_DEBUG(
dbgs() <<
"Natural loop with a single header: skipped\n");
317 LLVM_DEBUG(
dbgs() <<
"===== Fix irreducible control-flow in function: "
318 <<
F.getName() <<
"\n");
320 bool Changed =
false;
330 while (!WorkList.empty()) {
333 << L->getHeader()->getName() <<
"\n");
337 WorkList.
append(L->begin(), L->end());
344 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
345 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
A set of analyses that are preserved following a run of a transformation pass.
This is an optimization pass for GlobalISel generic memory operations.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represents a single loop in the control flow graph.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
size_type size() const
Determine the number of elements in the SetVector.
FunctionPass * createFixIrreduciblePass()
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
The legacy pass manager's analysis pass to compute loop information.
fix Convert irreducible control flow into natural static false void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop, SetVector< BasicBlock * > &Blocks, SetVector< BasicBlock * > &Headers)
INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible", "Convert irreducible control-flow into natural loops", false, false) INITIALIZE_PASS_END(FixIrreducible
LLVM_NODISCARD T pop_back_val()
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
std::pair< const Loop *, BasicBlock * > NodeRef
static BasicBlock * unwrapBlock(BasicBlock *B)
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Represent the analysis usage information of a pass.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void verifyLoop() const
Verify loop structure.
Legacy analysis pass which computes a DominatorTree.
void initializeFixIrreduciblePass(PassRegistry &)
auto predecessors(MachineBasicBlock *BB)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
LoopT * AllocateLoop(ArgsTy &&... Args)
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F, SetVector< BasicBlock * > &Blocks, SetVector< BasicBlock * > &Headers)
void preserve()
Mark an analysis as preserved.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool insert(const value_type &X)
Insert a new element into the SetVector.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
auto partition(R &&Range, UnaryPredicate P)
Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly.
static bool runOnFunction(Function &F, bool PostInlining)
bool isLoopHeader(const BlockT *BB) const
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
const T & front() const
Return the first element of the SetVector.
static bool FixIrreducibleImpl(Function &F, LoopInfo &LI, DominatorTree &DT)
Analysis pass which computes a DominatorTree.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT, Loop *ParentLoop, SetVector< BasicBlock * > &Blocks, SetVector< BasicBlock * > &Headers)
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
AnalysisUsage & addRequiredID(const void *ID)
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
fix Convert irreducible control flow into natural loops
A vector that has set insertion semantics.
Analysis pass that exposes the LoopInfo for a function.