const TargetTransformInfo &TTI;
unsigned BonusInstThreshold;
const DataLayout *const DL;
- AssumptionTracker *AT;
+ AssumptionCache *AC;
Value *isValueEqualityComparison(TerminatorInst *TI);
BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
std::vector<ValueEqualityComparisonCase> &Cases);
public:
SimplifyCFGOpt(const TargetTransformInfo &TTI, unsigned BonusInstThreshold,
- const DataLayout *DL, AssumptionTracker *AT)
- : TTI(TTI), BonusInstThreshold(BonusInstThreshold), DL(DL), AT(AT) {}
+ const DataLayout *DL, AssumptionCache *AC)
+ : TTI(TTI), BonusInstThreshold(BonusInstThreshold), DL(DL), AC(AC) {}
bool run(BasicBlock *BB);
};
}
/// the PHI, merging the third icmp into the switch.
static bool TryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI, IRBuilder<> &Builder, const TargetTransformInfo &TTI,
- unsigned BonusInstThreshold, const DataLayout *DL, AssumptionTracker *AT) {
+ unsigned BonusInstThreshold, const DataLayout *DL, AssumptionCache *AC) {
BasicBlock *BB = ICI->getParent();
// If the block has any PHIs in it or the icmp has multiple uses, it is too
ICI->eraseFromParent();
}
// BB is now empty, so it is likely to simplify away.
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
}
// Ok, the block is reachable from the default dest. If the constant we're
ICI->replaceAllUsesWith(V);
ICI->eraseFromParent();
// BB is now empty, so it is likely to simplify away.
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
}
// The use of the icmp has to be in the 'end' block, by the only PHI node in
/// EliminateDeadSwitchCases - Compute masked bits for the condition of a switch
/// and use it to remove dead cases.
static bool EliminateDeadSwitchCases(SwitchInst *SI, const DataLayout *DL,
- AssumptionTracker *AT) {
+ AssumptionCache *AC) {
Value *Cond = SI->getCondition();
unsigned Bits = Cond->getType()->getIntegerBitWidth();
APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
- computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AT, SI);
+ computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AC, SI);
// Gather dead cases.
SmallVector<ConstantInt*, 8> DeadCases;
continue;
} else if (Constant *C = ConstantFold(I, ConstantPool, DL)) {
// Instruction is side-effect free and constant.
+
+ // If the instruction has uses outside this block or a phi node slot for
+ // the block, it is not safe to bypass the instruction since it would then
+ // no longer dominate all its uses.
+ for (auto &Use : I->uses()) {
+ User *User = Use.getUser();
+ if (Instruction *I = dyn_cast<Instruction>(User))
+ if (I->getParent() == CaseDest)
+ continue;
+ if (PHINode *Phi = dyn_cast<PHINode>(User))
+ if (Phi->getIncomingBlock(Use) == CaseDest)
+ continue;
+ return false;
+ }
+
ConstantPool.insert(std::make_pair(I, C));
} else {
break;
if (!ConstVal)
return false;
- // Note: If the constant comes from constant-propagating the case value
- // through the CaseDest basic block, it will be safe to remove the
- // instructions in that block. They cannot be used (except in the phi nodes
- // we visit) outside CaseDest, because that block does not dominate its
- // successor. If it did, we would not be in this phi node.
-
// Be conservative about which kinds of constants we support.
if (!ValidLookupTableConstant(ConstVal))
return false;
/// phi nodes in a common successor block with only two different
/// constant values, replace the switch with select.
static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder,
- const DataLayout *DL, AssumptionTracker *AT) {
+ const DataLayout *DL, AssumptionCache *AC) {
Value *const Cond = SI->getCondition();
PHINode *PHI = nullptr;
BasicBlock *CommonDest = nullptr;
// see if that predecessor totally determines the outcome of this switch.
if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
Value *Cond = SI->getCondition();
if (SelectInst *Select = dyn_cast<SelectInst>(Cond))
if (SimplifySwitchOnSelect(SI, Select))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
// If the block only contains the switch, see if we can fold the block
// away into any preds.
++BBI;
if (SI == &*BBI)
if (FoldValueComparisonIntoPredecessors(SI, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
}
// Try to transform the switch into an icmp and a branch.
if (TurnSwitchRangeIntoICmp(SI, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
// Remove unreachable cases.
- if (EliminateDeadSwitchCases(SI, DL, AT))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (EliminateDeadSwitchCases(SI, DL, AC))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
- if (SwitchToSelect(SI, Builder, DL, AT))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ if (SwitchToSelect(SI, Builder, DL, AC))
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
if (ForwardSwitchConditionToPHI(SI))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
if (SwitchToLookupTable(SI, Builder, TTI, DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
return false;
}
if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
if (SimplifyIndirectBrOnSelect(IBI, SI))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
}
return Changed;
}
;
if (I->isTerminator() &&
TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, TTI,
- BonusInstThreshold, DL, AT))
+ BonusInstThreshold, DL, AC))
return true;
}
// predecessor and use logical operations to update the incoming value
// for PHI nodes in common successor.
if (FoldBranchToCommonDest(BI, DL, BonusInstThreshold))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
return false;
}
// switch.
if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
// This block must be empty, except for the setcond inst, if it exists.
// Ignore dbg intrinsics.
++I;
if (&*I == BI) {
if (FoldValueComparisonIntoPredecessors(BI, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
} else if (&*I == cast<Instruction>(BI->getCondition())){
++I;
// Ignore dbg intrinsics.
while (isa<DbgInfoIntrinsic>(I))
++I;
if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
}
}
// branches to us and one of our successors, fold the comparison into the
// predecessor and use logical operations to pick the right destination.
if (FoldBranchToCommonDest(BI, DL, BonusInstThreshold))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
// We have a conditional branch to two blocks that are only reachable
// from BI. We know that the condbr dominates the two blocks, so see if
if (BI->getSuccessor(0)->getSinglePredecessor()) {
if (BI->getSuccessor(1)->getSinglePredecessor()) {
if (HoistThenElseCodeToIf(BI, DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
} else {
// If Successor #1 has multiple preds, we may be able to conditionally
// execute Successor #0 if it branches to Successor #1.
if (Succ0TI->getNumSuccessors() == 1 &&
Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
}
} else if (BI->getSuccessor(1)->getSinglePredecessor()) {
// If Successor #0 has multiple preds, we may be able to conditionally
if (Succ1TI->getNumSuccessors() == 1 &&
Succ1TI->getSuccessor(0) == BI->getSuccessor(0))
if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
}
// If this is a branch on a phi node in the current block, thread control
if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
if (PN->getParent() == BI->getParent())
if (FoldCondBranchOnPHI(BI, DL))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
// Scan predecessor blocks for conditional branches.
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
if (PBI != BI && PBI->isConditional())
if (SimplifyCondBranchToCondBranch(PBI, BI))
- return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
+ return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
return false;
}
/// of the CFG. It returns true if a modification was made.
///
bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
- unsigned BonusInstThreshold,
- const DataLayout *DL, AssumptionTracker *AT) {
- return SimplifyCFGOpt(TTI, BonusInstThreshold, DL, AT).run(BB);
+ unsigned BonusInstThreshold, const DataLayout *DL,
+ AssumptionCache *AC) {
+ return SimplifyCFGOpt(TTI, BonusInstThreshold, DL, AC).run(BB);
}