aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp')
-rw-r--r--llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp518
1 files changed, 282 insertions, 236 deletions
diff --git a/llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp b/llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp
index 4371b821eae6..8a5c506eed69 100644
--- a/llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp
+++ b/llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp
@@ -76,7 +76,6 @@
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/SSAUpdaterBulk.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
-#include <algorithm>
#include <deque>
#ifdef EXPENSIVE_CHECKS
@@ -106,6 +105,12 @@ static cl::opt<unsigned> MaxPathLength(
cl::desc("Max number of blocks searched to find a threading path"),
cl::Hidden, cl::init(20));
+static cl::opt<unsigned> MaxNumVisitiedPaths(
+ "dfa-max-num-visited-paths",
+ cl::desc(
+ "Max number of blocks visited while enumerating paths around a switch"),
+ cl::Hidden, cl::init(2500));
+
static cl::opt<unsigned>
MaxNumPaths("dfa-max-num-paths",
cl::desc("Max number of paths enumerated around a switch"),
@@ -149,9 +154,7 @@ private:
unfoldSelectInstrs(DominatorTree *DT,
const SmallVector<SelectInstToUnfold, 4> &SelectInsts) {
DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
- SmallVector<SelectInstToUnfold, 4> Stack;
- for (SelectInstToUnfold SIToUnfold : SelectInsts)
- Stack.push_back(SIToUnfold);
+ SmallVector<SelectInstToUnfold, 4> Stack(SelectInsts);
while (!Stack.empty()) {
SelectInstToUnfold SIToUnfold = Stack.pop_back_val();
@@ -177,24 +180,6 @@ private:
namespace {
-/// Create a new basic block and sink \p SIToSink into it.
-void createBasicBlockAndSinkSelectInst(
- DomTreeUpdater *DTU, SelectInst *SI, PHINode *SIUse, SelectInst *SIToSink,
- BasicBlock *EndBlock, StringRef NewBBName, BasicBlock **NewBlock,
- BranchInst **NewBranch, std::vector<SelectInstToUnfold> *NewSIsToUnfold,
- std::vector<BasicBlock *> *NewBBs) {
- assert(SIToSink->hasOneUse());
- assert(NewBlock);
- assert(NewBranch);
- *NewBlock = BasicBlock::Create(SI->getContext(), NewBBName,
- EndBlock->getParent(), EndBlock);
- NewBBs->push_back(*NewBlock);
- *NewBranch = BranchInst::Create(EndBlock, *NewBlock);
- SIToSink->moveBefore(*NewBranch);
- NewSIsToUnfold->push_back(SelectInstToUnfold(SIToSink, SIUse));
- DTU->applyUpdates({{DominatorTree::Insert, *NewBlock, EndBlock}});
-}
-
/// Unfold the select instruction held in \p SIToUnfold by replacing it with
/// control flow.
///
@@ -208,105 +193,145 @@ void unfold(DomTreeUpdater *DTU, LoopInfo *LI, SelectInstToUnfold SIToUnfold,
SelectInst *SI = SIToUnfold.getInst();
PHINode *SIUse = SIToUnfold.getUse();
BasicBlock *StartBlock = SI->getParent();
- BasicBlock *EndBlock = SIUse->getParent();
BranchInst *StartBlockTerm =
dyn_cast<BranchInst>(StartBlock->getTerminator());
- assert(StartBlockTerm && StartBlockTerm->isUnconditional());
+ assert(StartBlockTerm);
assert(SI->hasOneUse());
- // These are the new basic blocks for the conditional branch.
- // At least one will become an actual new basic block.
- BasicBlock *TrueBlock = nullptr;
- BasicBlock *FalseBlock = nullptr;
- BranchInst *TrueBranch = nullptr;
- BranchInst *FalseBranch = nullptr;
-
- // Sink select instructions to be able to unfold them later.
- if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getTrueValue())) {
- createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
- "si.unfold.true", &TrueBlock, &TrueBranch,
- NewSIsToUnfold, NewBBs);
- }
- if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getFalseValue())) {
- createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
- "si.unfold.false", &FalseBlock,
- &FalseBranch, NewSIsToUnfold, NewBBs);
- }
-
- // If there was nothing to sink, then arbitrarily choose the 'false' side
- // for a new input value to the PHI.
- if (!TrueBlock && !FalseBlock) {
- FalseBlock = BasicBlock::Create(SI->getContext(), "si.unfold.false",
- EndBlock->getParent(), EndBlock);
- NewBBs->push_back(FalseBlock);
- BranchInst::Create(EndBlock, FalseBlock);
- DTU->applyUpdates({{DominatorTree::Insert, FalseBlock, EndBlock}});
- }
+ if (StartBlockTerm->isUnconditional()) {
+ BasicBlock *EndBlock = StartBlock->getUniqueSuccessor();
+ // Arbitrarily choose the 'false' side for a new input value to the PHI.
+ BasicBlock *NewBlock = BasicBlock::Create(
+ SI->getContext(), Twine(SI->getName(), ".si.unfold.false"),
+ EndBlock->getParent(), EndBlock);
+ NewBBs->push_back(NewBlock);
+ BranchInst::Create(EndBlock, NewBlock);
+ DTU->applyUpdates({{DominatorTree::Insert, NewBlock, EndBlock}});
+
+ // StartBlock
+ // | \
+ // | NewBlock
+ // | /
+ // EndBlock
+ Value *SIOp1 = SI->getTrueValue();
+ Value *SIOp2 = SI->getFalseValue();
- // Insert the real conditional branch based on the original condition.
- // If we did not create a new block for one of the 'true' or 'false' paths
- // of the condition, it means that side of the branch goes to the end block
- // directly and the path originates from the start block from the point of
- // view of the new PHI.
- BasicBlock *TT = EndBlock;
- BasicBlock *FT = EndBlock;
- if (TrueBlock && FalseBlock) {
- // A diamond.
- TT = TrueBlock;
- FT = FalseBlock;
-
- // Update the phi node of SI.
- SIUse->addIncoming(SI->getTrueValue(), TrueBlock);
- SIUse->addIncoming(SI->getFalseValue(), FalseBlock);
+ PHINode *NewPhi = PHINode::Create(SIUse->getType(), 1,
+ Twine(SIOp2->getName(), ".si.unfold.phi"),
+ NewBlock->getFirstInsertionPt());
+ NewPhi->addIncoming(SIOp2, StartBlock);
// Update any other PHI nodes in EndBlock.
for (PHINode &Phi : EndBlock->phis()) {
- if (&Phi != SIUse) {
- Value *OrigValue = Phi.getIncomingValueForBlock(StartBlock);
- Phi.addIncoming(OrigValue, TrueBlock);
- Phi.addIncoming(OrigValue, FalseBlock);
+ if (SIUse == &Phi)
+ continue;
+ Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlock);
+ }
+
+ // Update the phi node of SI, which is its only use.
+ if (EndBlock == SIUse->getParent()) {
+ SIUse->addIncoming(NewPhi, NewBlock);
+ SIUse->replaceUsesOfWith(SI, SIOp1);
+ } else {
+ PHINode *EndPhi = PHINode::Create(SIUse->getType(), pred_size(EndBlock),
+ Twine(SI->getName(), ".si.unfold.phi"),
+ EndBlock->getFirstInsertionPt());
+ for (BasicBlock *Pred : predecessors(EndBlock)) {
+ if (Pred != StartBlock && Pred != NewBlock)
+ EndPhi->addIncoming(EndPhi, Pred);
}
- // Remove incoming place of original StartBlock, which comes in a indirect
- // way (through TrueBlock and FalseBlock) now.
- Phi.removeIncomingValue(StartBlock, /* DeletePHIIfEmpty = */ false);
+ EndPhi->addIncoming(SIOp1, StartBlock);
+ EndPhi->addIncoming(NewPhi, NewBlock);
+ SIUse->replaceUsesOfWith(SI, EndPhi);
+ SIUse = EndPhi;
}
- } else {
- BasicBlock *NewBlock = nullptr;
- Value *SIOp1 = SI->getTrueValue();
- Value *SIOp2 = SI->getFalseValue();
- // A triangle pointing right.
- if (!TrueBlock) {
- NewBlock = FalseBlock;
- FT = FalseBlock;
- }
- // A triangle pointing left.
- else {
- NewBlock = TrueBlock;
- TT = TrueBlock;
- std::swap(SIOp1, SIOp2);
- }
+ if (auto *OpSi = dyn_cast<SelectInst>(SIOp1))
+ NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, SIUse));
+ if (auto *OpSi = dyn_cast<SelectInst>(SIOp2))
+ NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, NewPhi));
- // Update the phi node of SI.
- for (unsigned Idx = 0; Idx < SIUse->getNumIncomingValues(); ++Idx) {
- if (SIUse->getIncomingBlock(Idx) == StartBlock)
- SIUse->setIncomingValue(Idx, SIOp1);
- }
- SIUse->addIncoming(SIOp2, NewBlock);
+ // Insert the real conditional branch based on the original condition.
+ StartBlockTerm->eraseFromParent();
+ BranchInst::Create(EndBlock, NewBlock, SI->getCondition(), StartBlock);
+ DTU->applyUpdates({{DominatorTree::Insert, StartBlock, EndBlock},
+ {DominatorTree::Insert, StartBlock, NewBlock}});
+ } else {
+ BasicBlock *EndBlock = SIUse->getParent();
+ BasicBlock *NewBlockT = BasicBlock::Create(
+ SI->getContext(), Twine(SI->getName(), ".si.unfold.true"),
+ EndBlock->getParent(), EndBlock);
+ BasicBlock *NewBlockF = BasicBlock::Create(
+ SI->getContext(), Twine(SI->getName(), ".si.unfold.false"),
+ EndBlock->getParent(), EndBlock);
+
+ NewBBs->push_back(NewBlockT);
+ NewBBs->push_back(NewBlockF);
+
+ // Def only has one use in EndBlock.
+ // Before transformation:
+ // StartBlock(Def)
+ // | \
+ // EndBlock OtherBlock
+ // (Use)
+ //
+ // After transformation:
+ // StartBlock(Def)
+ // | \
+ // | OtherBlock
+ // NewBlockT
+ // | \
+ // | NewBlockF
+ // | /
+ // | /
+ // EndBlock
+ // (Use)
+ BranchInst::Create(EndBlock, NewBlockF);
+ // Insert the real conditional branch based on the original condition.
+ BranchInst::Create(EndBlock, NewBlockF, SI->getCondition(), NewBlockT);
+ DTU->applyUpdates({{DominatorTree::Insert, NewBlockT, NewBlockF},
+ {DominatorTree::Insert, NewBlockT, EndBlock},
+ {DominatorTree::Insert, NewBlockF, EndBlock}});
+
+ Value *TrueVal = SI->getTrueValue();
+ Value *FalseVal = SI->getFalseValue();
+
+ PHINode *NewPhiT = PHINode::Create(
+ SIUse->getType(), 1, Twine(TrueVal->getName(), ".si.unfold.phi"),
+ NewBlockT->getFirstInsertionPt());
+ PHINode *NewPhiF = PHINode::Create(
+ SIUse->getType(), 1, Twine(FalseVal->getName(), ".si.unfold.phi"),
+ NewBlockF->getFirstInsertionPt());
+ NewPhiT->addIncoming(TrueVal, StartBlock);
+ NewPhiF->addIncoming(FalseVal, NewBlockT);
+
+ if (auto *TrueSI = dyn_cast<SelectInst>(TrueVal))
+ NewSIsToUnfold->push_back(SelectInstToUnfold(TrueSI, NewPhiT));
+ if (auto *FalseSi = dyn_cast<SelectInst>(FalseVal))
+ NewSIsToUnfold->push_back(SelectInstToUnfold(FalseSi, NewPhiF));
+
+ SIUse->addIncoming(NewPhiT, NewBlockT);
+ SIUse->addIncoming(NewPhiF, NewBlockF);
+ SIUse->removeIncomingValue(StartBlock);
// Update any other PHI nodes in EndBlock.
- for (auto II = EndBlock->begin(); PHINode *Phi = dyn_cast<PHINode>(II);
- ++II) {
- if (Phi != SIUse)
- Phi->addIncoming(Phi->getIncomingValueForBlock(StartBlock), NewBlock);
+ for (PHINode &Phi : EndBlock->phis()) {
+ if (SIUse == &Phi)
+ continue;
+ Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlockT);
+ Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlockF);
+ Phi.removeIncomingValue(StartBlock);
}
+
+ // Update the appropriate successor of the start block to point to the new
+ // unfolded block.
+ unsigned SuccNum = StartBlockTerm->getSuccessor(1) == EndBlock ? 1 : 0;
+ StartBlockTerm->setSuccessor(SuccNum, NewBlockT);
+ DTU->applyUpdates({{DominatorTree::Delete, StartBlock, EndBlock},
+ {DominatorTree::Insert, StartBlock, NewBlockT}});
}
- StartBlockTerm->eraseFromParent();
- BranchInst::Create(TT, FT, SI->getCondition(), StartBlock);
- DTU->applyUpdates({{DominatorTree::Insert, StartBlock, TT},
- {DominatorTree::Insert, StartBlock, FT}});
// Preserve loop info
if (Loop *L = LI->getLoopFor(SI->getParent())) {
@@ -372,6 +397,11 @@ struct ThreadingPath {
/// Path is a list of basic blocks.
const PathType &getPath() const { return Path; }
void setPath(const PathType &NewPath) { Path = NewPath; }
+ void push_back(BasicBlock *BB) { Path.push_back(BB); }
+ void push_front(BasicBlock *BB) { Path.push_front(BB); }
+ void appendExcludingFirst(const PathType &OtherPath) {
+ Path.insert(Path.end(), OtherPath.begin() + 1, OtherPath.end());
+ }
void print(raw_ostream &OS) const {
OS << Path << " [ " << ExitVal << ", " << DBB->getName() << " ]";
@@ -483,10 +513,8 @@ private:
void addToQueue(Value *Val, BasicBlock *BB,
std::deque<std::pair<Value *, BasicBlock *>> &Q,
SmallSet<Value *, 16> &SeenValues) {
- if (SeenValues.contains(Val))
- return;
- Q.push_back({Val, BB});
- SeenValues.insert(Val);
+ if (SeenValues.insert(Val).second)
+ Q.push_back({Val, BB});
}
bool isValidSelectInst(SelectInst *SI) {
@@ -530,9 +558,9 @@ private:
struct AllSwitchPaths {
AllSwitchPaths(const MainSwitch *MSwitch, OptimizationRemarkEmitter *ORE,
- LoopInfo *LI)
+ LoopInfo *LI, Loop *L)
: Switch(MSwitch->getInstr()), SwitchBlock(Switch->getParent()), ORE(ORE),
- LI(LI) {}
+ LI(LI), SwitchOuterLoop(L) {}
std::vector<ThreadingPath> &getThreadingPaths() { return TPaths; }
unsigned getNumThreadingPaths() { return TPaths.size(); }
@@ -540,10 +568,7 @@ struct AllSwitchPaths {
BasicBlock *getSwitchBlock() { return SwitchBlock; }
void run() {
- VisitedBlocks Visited;
- PathsType LoopPaths = paths(SwitchBlock, Visited, /* PathDepth = */ 1);
- StateDefMap StateDef = getStateDefMap(LoopPaths);
-
+ StateDefMap StateDef = getStateDefMap();
if (StateDef.empty()) {
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable",
@@ -553,42 +578,118 @@ struct AllSwitchPaths {
return;
}
- for (const PathType &Path : LoopPaths) {
- ThreadingPath TPath;
-
- const BasicBlock *PrevBB = Path.back();
- for (const BasicBlock *BB : Path) {
- if (StateDef.contains(BB)) {
- const PHINode *Phi = dyn_cast<PHINode>(StateDef[BB]);
- assert(Phi && "Expected a state-defining instr to be a phi node.");
-
- const Value *V = Phi->getIncomingValueForBlock(PrevBB);
- if (const ConstantInt *C = dyn_cast<const ConstantInt>(V)) {
- TPath.setExitValue(C);
- TPath.setDeterminator(BB);
- TPath.setPath(Path);
- }
- }
+ auto *SwitchPhi = cast<PHINode>(Switch->getOperand(0));
+ auto *SwitchPhiDefBB = SwitchPhi->getParent();
+ VisitedBlocks VB;
+ // Get paths from the determinator BBs to SwitchPhiDefBB
+ std::vector<ThreadingPath> PathsToPhiDef =
+ getPathsFromStateDefMap(StateDef, SwitchPhi, VB);
+ if (SwitchPhiDefBB == SwitchBlock) {
+ TPaths = std::move(PathsToPhiDef);
+ return;
+ }
- // Switch block is the determinator, this is the final exit value.
- if (TPath.isExitValueSet() && BB == Path.front())
- break;
+ // Find and append paths from SwitchPhiDefBB to SwitchBlock.
+ PathsType PathsToSwitchBB =
+ paths(SwitchPhiDefBB, SwitchBlock, VB, /* PathDepth = */ 1);
+ if (PathsToSwitchBB.empty())
+ return;
- PrevBB = BB;
+ std::vector<ThreadingPath> TempList;
+ for (const ThreadingPath &Path : PathsToPhiDef) {
+ for (const PathType &PathToSw : PathsToSwitchBB) {
+ ThreadingPath PathCopy(Path);
+ PathCopy.appendExcludingFirst(PathToSw);
+ TempList.push_back(PathCopy);
}
-
- if (TPath.isExitValueSet() && isSupported(TPath))
- TPaths.push_back(TPath);
}
+ TPaths = std::move(TempList);
}
private:
// Value: an instruction that defines a switch state;
// Key: the parent basic block of that instruction.
typedef DenseMap<const BasicBlock *, const PHINode *> StateDefMap;
+ std::vector<ThreadingPath> getPathsFromStateDefMap(StateDefMap &StateDef,
+ PHINode *Phi,
+ VisitedBlocks &VB) {
+ std::vector<ThreadingPath> Res;
+ auto *PhiBB = Phi->getParent();
+ VB.insert(PhiBB);
+
+ VisitedBlocks UniqueBlocks;
+ for (auto *IncomingBB : Phi->blocks()) {
+ if (!UniqueBlocks.insert(IncomingBB).second)
+ continue;
+ if (!SwitchOuterLoop->contains(IncomingBB))
+ continue;
+
+ Value *IncomingValue = Phi->getIncomingValueForBlock(IncomingBB);
+ // We found the determinator. This is the start of our path.
+ if (auto *C = dyn_cast<ConstantInt>(IncomingValue)) {
+ // SwitchBlock is the determinator, unsupported unless its also the def.
+ if (PhiBB == SwitchBlock &&
+ SwitchBlock != cast<PHINode>(Switch->getOperand(0))->getParent())
+ continue;
+ ThreadingPath NewPath;
+ NewPath.setDeterminator(PhiBB);
+ NewPath.setExitValue(C);
+ // Don't add SwitchBlock at the start, this is handled later.
+ if (IncomingBB != SwitchBlock)
+ NewPath.push_back(IncomingBB);
+ NewPath.push_back(PhiBB);
+ Res.push_back(NewPath);
+ continue;
+ }
+ // Don't get into a cycle.
+ if (VB.contains(IncomingBB) || IncomingBB == SwitchBlock)
+ continue;
+ // Recurse up the PHI chain.
+ auto *IncomingPhi = dyn_cast<PHINode>(IncomingValue);
+ if (!IncomingPhi)
+ continue;
+ auto *IncomingPhiDefBB = IncomingPhi->getParent();
+ if (!StateDef.contains(IncomingPhiDefBB))
+ continue;
+
+ // Direct predecessor, just add to the path.
+ if (IncomingPhiDefBB == IncomingBB) {
+ std::vector<ThreadingPath> PredPaths =
+ getPathsFromStateDefMap(StateDef, IncomingPhi, VB);
+ for (ThreadingPath &Path : PredPaths) {
+ Path.push_back(PhiBB);
+ Res.push_back(std::move(Path));
+ }
+ continue;
+ }
+ // Not a direct predecessor, find intermediate paths to append to the
+ // existing path.
+ if (VB.contains(IncomingPhiDefBB))
+ continue;
+
+ PathsType IntermediatePaths;
+ IntermediatePaths =
+ paths(IncomingPhiDefBB, IncomingBB, VB, /* PathDepth = */ 1);
+ if (IntermediatePaths.empty())
+ continue;
+
+ std::vector<ThreadingPath> PredPaths =
+ getPathsFromStateDefMap(StateDef, IncomingPhi, VB);
+ for (const ThreadingPath &Path : PredPaths) {
+ for (const PathType &IPath : IntermediatePaths) {
+ ThreadingPath NewPath(Path);
+ NewPath.appendExcludingFirst(IPath);
+ NewPath.push_back(PhiBB);
+ Res.push_back(NewPath);
+ }
+ }
+ }
+ VB.erase(PhiBB);
+ return Res;
+ }
- PathsType paths(BasicBlock *BB, VisitedBlocks &Visited,
- unsigned PathDepth) const {
+ PathsType paths(BasicBlock *BB, BasicBlock *ToBB, VisitedBlocks &Visited,
+ unsigned PathDepth) {
PathsType Res;
// Stop exploring paths after visiting MaxPathLength blocks
@@ -603,11 +704,12 @@ private:
}
Visited.insert(BB);
+ if (++NumVisited > MaxNumVisitiedPaths)
+ return Res;
// Stop if we have reached the BB out of loop, since its successors have no
// impact on the DFA.
- // TODO: Do we need to stop exploring if BB is the outer loop of the switch?
- if (!LI->getLoopFor(BB))
+ if (!SwitchOuterLoop->contains(BB))
return Res;
// Some blocks have multiple edges to the same successor, and this set
@@ -617,9 +719,9 @@ private:
if (!Successors.insert(Succ).second)
continue;
- // Found a cycle through the SwitchBlock
- if (Succ == SwitchBlock) {
- Res.push_back({BB});
+ // Found a cycle through the final block.
+ if (Succ == ToBB) {
+ Res.push_back({BB, ToBB});
continue;
}
@@ -627,11 +729,19 @@ private:
if (Visited.contains(Succ))
continue;
- PathsType SuccPaths = paths(Succ, Visited, PathDepth + 1);
- for (const PathType &Path : SuccPaths) {
- PathType NewPath(Path);
- NewPath.push_front(BB);
- Res.push_back(NewPath);
+ auto *CurrLoop = LI->getLoopFor(BB);
+ // Unlikely to be beneficial.
+ if (Succ == CurrLoop->getHeader())
+ continue;
+ // Skip for now, revisit this condition later to see the impact on
+ // coverage and compile time.
+ if (LI->getLoopFor(Succ) != CurrLoop)
+ continue;
+
+ PathsType SuccPaths = paths(Succ, ToBB, Visited, PathDepth + 1);
+ for (PathType &Path : SuccPaths) {
+ Path.push_front(BB);
+ Res.push_back(Path);
if (Res.size() >= MaxNumPaths) {
return Res;
}
@@ -644,26 +754,15 @@ private:
return Res;
}
- /// Walk the use-def chain and collect all the state-defining instructions.
- ///
- /// Return an empty map if unpredictable values encountered inside the basic
- /// blocks of \p LoopPaths.
- StateDefMap getStateDefMap(const PathsType &LoopPaths) const {
+ /// Walk the use-def chain and collect all the state-defining blocks and the
+ /// PHI nodes in those blocks that define the state.
+ StateDefMap getStateDefMap() const {
StateDefMap Res;
-
- // Basic blocks belonging to any of the loops around the switch statement.
- SmallPtrSet<BasicBlock *, 16> LoopBBs;
- for (const PathType &Path : LoopPaths) {
- for (BasicBlock *BB : Path)
- LoopBBs.insert(BB);
- }
-
- Value *FirstDef = Switch->getOperand(0);
-
- assert(isa<PHINode>(FirstDef) && "The first definition must be a phi.");
+ PHINode *FirstDef = dyn_cast<PHINode>(Switch->getOperand(0));
+ assert(FirstDef && "The first definition must be a phi.");
SmallVector<PHINode *, 8> Stack;
- Stack.push_back(dyn_cast<PHINode>(FirstDef));
+ Stack.push_back(FirstDef);
SmallSet<Value *, 16> SeenValues;
while (!Stack.empty()) {
@@ -673,85 +772,28 @@ private:
SeenValues.insert(CurPhi);
for (BasicBlock *IncomingBB : CurPhi->blocks()) {
- Value *Incoming = CurPhi->getIncomingValueForBlock(IncomingBB);
- bool IsOutsideLoops = LoopBBs.count(IncomingBB) == 0;
- if (Incoming == FirstDef || isa<ConstantInt>(Incoming) ||
- SeenValues.contains(Incoming) || IsOutsideLoops) {
+ PHINode *IncomingPhi =
+ dyn_cast<PHINode>(CurPhi->getIncomingValueForBlock(IncomingBB));
+ if (!IncomingPhi)
+ continue;
+ bool IsOutsideLoops = !SwitchOuterLoop->contains(IncomingBB);
+ if (SeenValues.contains(IncomingPhi) || IsOutsideLoops)
continue;
- }
-
- // Any unpredictable value inside the loops means we must bail out.
- if (!isa<PHINode>(Incoming))
- return StateDefMap();
- Stack.push_back(cast<PHINode>(Incoming));
+ Stack.push_back(IncomingPhi);
}
}
return Res;
}
- /// The determinator BB should precede the switch-defining BB.
- ///
- /// Otherwise, it is possible that the state defined in the determinator block
- /// defines the state for the next iteration of the loop, rather than for the
- /// current one.
- ///
- /// Currently supported paths:
- /// \code
- /// < switch bb1 determ def > [ 42, determ ]
- /// < switch_and_def bb1 determ > [ 42, determ ]
- /// < switch_and_def_and_determ bb1 > [ 42, switch_and_def_and_determ ]
- /// \endcode
- ///
- /// Unsupported paths:
- /// \code
- /// < switch bb1 def determ > [ 43, determ ]
- /// < switch_and_determ bb1 def > [ 43, switch_and_determ ]
- /// \endcode
- bool isSupported(const ThreadingPath &TPath) {
- Instruction *SwitchCondI = dyn_cast<Instruction>(Switch->getCondition());
- assert(SwitchCondI);
- if (!SwitchCondI)
- return false;
-
- const BasicBlock *SwitchCondDefBB = SwitchCondI->getParent();
- const BasicBlock *SwitchCondUseBB = Switch->getParent();
- const BasicBlock *DeterminatorBB = TPath.getDeterminatorBB();
-
- assert(
- SwitchCondUseBB == TPath.getPath().front() &&
- "The first BB in a threading path should have the switch instruction");
- if (SwitchCondUseBB != TPath.getPath().front())
- return false;
-
- // Make DeterminatorBB the first element in Path.
- PathType Path = TPath.getPath();
- auto ItDet = llvm::find(Path, DeterminatorBB);
- std::rotate(Path.begin(), ItDet, Path.end());
-
- bool IsDetBBSeen = false;
- bool IsDefBBSeen = false;
- bool IsUseBBSeen = false;
- for (BasicBlock *BB : Path) {
- if (BB == DeterminatorBB)
- IsDetBBSeen = true;
- if (BB == SwitchCondDefBB)
- IsDefBBSeen = true;
- if (BB == SwitchCondUseBB)
- IsUseBBSeen = true;
- if (IsDetBBSeen && IsUseBBSeen && !IsDefBBSeen)
- return false;
- }
-
- return true;
- }
-
+ unsigned NumVisited = 0;
SwitchInst *Switch;
BasicBlock *SwitchBlock;
OptimizationRemarkEmitter *ORE;
std::vector<ThreadingPath> TPaths;
LoopInfo *LI;
+ Loop *SwitchOuterLoop;
};
struct TransformDFA {
@@ -905,9 +947,9 @@ private:
BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
LLVM_DEBUG(dbgs() << TPath << "\n");
- PathType NewPath(TPath.getPath());
- NewPath.push_back(SwitchBlock);
- TPath.setPath(NewPath);
+ // TODO: Fix exit path creation logic so that we dont need this
+ // placeholder.
+ TPath.push_front(SwitchBlock);
}
// Transform the ThreadingPaths and keep track of the cloned values
@@ -1310,8 +1352,11 @@ bool DFAJumpThreading::run(Function &F) {
<< " is a candidate\n");
MainSwitch Switch(SI, LI, ORE);
- if (!Switch.getInstr())
+ if (!Switch.getInstr()) {
+ LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is not a "
+ << "candidate for jump threading\n");
continue;
+ }
LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is a "
<< "candidate for jump threading\n");
@@ -1321,7 +1366,8 @@ bool DFAJumpThreading::run(Function &F) {
if (!Switch.getSelectInsts().empty())
MadeChanges = true;
- AllSwitchPaths SwitchPaths(&Switch, ORE, LI);
+ AllSwitchPaths SwitchPaths(&Switch, ORE, LI,
+ LI->getLoopFor(&BB)->getOutermostLoop());
SwitchPaths.run();
if (SwitchPaths.getNumThreadingPaths() > 0) {
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-07 17:45:15 +0000