Go to the documentation of this file.
87 #define DEBUG_TYPE "loop-unswitch"
89 STATISTIC(NumBranches,
"Number of branches unswitched");
90 STATISTIC(NumSwitches,
"Number of switches unswitched");
91 STATISTIC(NumGuards,
"Number of guards unswitched");
92 STATISTIC(NumSelects ,
"Number of selects unswitched");
93 STATISTIC(NumTrivial ,
"Number of unswitches that are trivial");
94 STATISTIC(NumSimplify,
"Number of simplifications of unswitched code");
95 STATISTIC(TotalInsts,
"Total number of instructions analyzed");
105 cl::desc(
"Max number of memory uses to explore during "
106 "partial unswitching analysis"),
111 class LUAnalysisCache {
112 using UnswitchedValsMap =
114 using UnswitchedValsIt = UnswitchedValsMap::iterator;
116 struct LoopProperties {
117 unsigned CanBeUnswitchedCount;
118 unsigned WasUnswitchedCount;
119 unsigned SizeEstimation;
120 UnswitchedValsMap UnswitchedVals;
125 using LoopPropsMap = std::map<const Loop *, LoopProperties>;
126 using LoopPropsMapIt = LoopPropsMap::iterator;
128 LoopPropsMap LoopsProperties;
129 UnswitchedValsMap *CurLoopInstructions =
nullptr;
130 LoopProperties *CurrentLoopProperties =
nullptr;
149 LUAnalysisCache() : MaxSize(
Threshold) {}
157 void forgetLoop(
const Loop *L);
169 bool costAllowsUnswitching();
174 void cloneData(
const Loop *NewLoop,
const Loop *OldLoop,
178 class LoopUnswitch :
public LoopPass {
185 std::vector<Loop*> LoopProcessWorklist;
187 LUAnalysisCache BranchesInfo;
189 bool OptimizeForSize;
190 bool RedoLoop =
false;
192 Loop *CurrentLoop =
nullptr;
196 std::unique_ptr<MemorySSAUpdater> MSSAU;
206 std::vector<BasicBlock*> LoopBlocks;
208 std::vector<BasicBlock*> NewBlocks;
210 bool HasBranchDivergence;
215 explicit LoopUnswitch(
bool Os =
false,
bool HasBranchDivergence =
false)
217 HasBranchDivergence(HasBranchDivergence) {
222 bool processCurrentLoop();
223 bool isUnreachableDueToPreviousUnswitching(
BasicBlock *);
239 if (HasBranchDivergence)
245 void releaseMemory()
override { BranchesInfo.forgetLoop(CurrentLoop); }
247 void initLoopData() {
254 void splitExitEdges(
Loop *L,
257 bool tryTrivialLoopUnswitch(
bool &Changed);
268 void rewriteLoopBodyWithConditionConstant(
Loop *L,
Value *LIC,
277 void simplifyCode(std::vector<Instruction *> &Worklist,
Loop *L);
291 LoopPropsMapIt PropsIt;
293 std::tie(PropsIt, Inserted) =
294 LoopsProperties.insert(std::make_pair(L, LoopProperties()));
296 LoopProperties &Props = PropsIt->second;
316 Props.SizeEstimation =
Metrics.NumInsts;
317 Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
318 Props.WasUnswitchedCount = 0;
319 MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;
323 <<
", contents cannot be "
330 CurrentLoopProperties = &Props;
331 CurLoopInstructions = &Props.UnswitchedVals;
337 void LUAnalysisCache::forgetLoop(
const Loop *L) {
338 LoopPropsMapIt LIt = LoopsProperties.find(L);
340 if (LIt != LoopsProperties.end()) {
341 LoopProperties &Props = LIt->second;
342 MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount) *
343 Props.SizeEstimation;
344 LoopsProperties.erase(LIt);
347 CurrentLoopProperties =
nullptr;
348 CurLoopInstructions =
nullptr;
355 (*CurLoopInstructions)[
SI].insert(V);
360 return (*CurLoopInstructions)[
SI].count(V);
363 bool LUAnalysisCache::costAllowsUnswitching() {
364 return CurrentLoopProperties->CanBeUnswitchedCount > 0;
370 void LUAnalysisCache::cloneData(
const Loop *NewLoop,
const Loop *OldLoop,
372 LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
373 LoopProperties &OldLoopProps = *CurrentLoopProperties;
374 UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;
378 --OldLoopProps.CanBeUnswitchedCount;
379 ++OldLoopProps.WasUnswitchedCount;
380 NewLoopProps.WasUnswitchedCount = 0;
381 unsigned Quota = OldLoopProps.CanBeUnswitchedCount;
382 NewLoopProps.CanBeUnswitchedCount = Quota / 2;
383 OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;
385 NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;
390 for (
const auto &
I : Insts) {
393 const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);
394 assert(NewInst &&
"All instructions that are in SrcBB must be in VMap.");
396 NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];
413 return new LoopUnswitch(Os, HasBranchDivergence);
440 if (CacheIt != Cache.
end())
441 return CacheIt->second;
447 if (
Cond->getType()->isVectorTy())
451 if (isa<Constant>(
Cond))
return nullptr;
463 if (BO->getOpcode() == Instruction::And ||
464 BO->getOpcode() == Instruction::Or) {
467 switch (ParentChain) {
469 NewChain = BO->getOpcode() == Instruction::And ?
OC_OpChainAnd :
473 NewChain = BO->getOpcode() == Instruction::Or ?
OC_OpChainOr :
477 NewChain = BO->getOpcode() == Instruction::And ?
OC_OpChainAnd :
491 ParentChain = NewChain;
496 ParentChain, Cache, MSSAU)) {
502 ParentChain = NewChain;
504 ParentChain, Cache, MSSAU)) {
511 Cache[
Cond] =
nullptr;
518 static std::pair<Value *, OperatorChain>
528 "Do not expect a partial LIV with mixed operator chain");
529 return {FCond, OpChain};
536 AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
538 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
540 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
541 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
543 MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
544 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
545 assert(DT &&
"Cannot update MemorySSA without a valid DomTree.");
550 SanitizeMemory =
F->hasFnAttribute(Attribute::SanitizeMemory);
557 bool Changed =
false;
563 Changed |= processCurrentLoop();
574 bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(
BasicBlock *
BB) {
577 while (CurrentLoop->
contains(DomBB)) {
581 DomBB = Node->getBlock();
587 if (!isa<ConstantInt>(
Cond))
609 ICmpInst *CI = dyn_cast<ICmpInst>(&LoopCond);
615 if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
618 auto HasUndefInPHI = [](
PHINode &PN) {
619 for (
Value *Opd : PN.incoming_values()) {
620 if (isa<UndefValue>(Opd))
625 PHINode *LPHI = dyn_cast<PHINode>(LHS);
626 PHINode *RPHI = dyn_cast<PHINode>(RHS);
627 if ((LPHI && HasUndefInPHI(*LPHI)) || (RPHI && HasUndefInPHI(*RPHI)))
631 if (isa<UndefValue>(
SI.getTrueValue()) ||
632 isa<UndefValue>(
SI.getFalseValue()))
638 if ((LSI && HasUndefInSelect(*LSI)) || (RSI && HasUndefInSelect(*RSI)))
644 bool LoopUnswitch::processCurrentLoop() {
645 bool Changed =
false;
664 if (!BranchesInfo.countLoop(
666 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
672 if (tryTrivialLoopUnswitch(Changed)) {
678 if (OptimizeForSize ||
698 for (
const auto BB : CurrentLoop->
blocks()) {
699 for (
auto &
I : *
BB) {
700 auto *CB = dyn_cast<CallBase>(&
I);
703 if (CB->isConvergent())
705 if (
auto *II = dyn_cast<InvokeInst>(&
I))
706 if (!II->getUnwindDest()->canSplitPredecessors())
708 if (
auto *II = dyn_cast<IntrinsicInst>(&
I))
709 if (II->getIntrinsicID() == Intrinsic::experimental_guard)
710 Guards.push_back(II);
716 Changed, MSSAU.get())
742 if (SanitizeMemory &&
746 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
750 if (isUnreachableDueToPreviousUnswitching(*
I))
755 if (BI->isConditional()) {
759 Changed, MSSAU.get())
771 std::tie(LoopCond, OpChain) =
774 unsigned NumCases =
SI->getNumCases();
775 if (LoopCond && NumCases) {
786 if (BranchesInfo.isUnswitched(
SI, AllZero))
789 UnswitchVal = AllZero;
794 if (BranchesInfo.isUnswitched(
SI, AllOne))
797 UnswitchVal = AllOne;
800 "Expect to unswitch on trivial chain");
804 for (
auto Case :
SI->cases()) {
805 Constant *UnswitchValCandidate = Case.getCaseValue();
806 if (!BranchesInfo.isUnswitched(
SI, UnswitchValCandidate)) {
807 UnswitchVal = UnswitchValCandidate;
816 if (unswitchIfProfitable(LoopCond, UnswitchVal)) {
822 BranchesInfo.setUnswitched(
SI, UnswitchVal);
833 Changed, MSSAU.get())
853 "need at least a partially invariant condition");
854 LLVM_DEBUG(
dbgs() <<
"loop-unswitch: Found partially invariant condition "
855 << *
Info->InstToDuplicate[0] <<
"\n");
858 Value *LoopCond =
Info->InstToDuplicate[0];
865 if (
Info->PathIsNoop) {
866 if (HasBranchDivergence &&
867 getAnalysis<LegacyDivergenceAnalysis>().isDivergent(LoopCond)) {
870 <<
" at non-trivial condition '"
871 << *
Info->KnownValue <<
"' == " << *LoopCond <<
"\n"
872 <<
". Condition is divergent.\n");
880 if (
Info->KnownValue->isOneValue())
885 emitPreheaderBranchOnCondition(LoopCond,
Info->KnownValue, TrueDest,
886 FalseDest, OldBr, TI,
887 Info->InstToDuplicate);
894 if (unswitchIfProfitable(LoopCond,
Info->KnownValue,
896 Info->InstToDuplicate)) {
915 std::set<BasicBlock*> &Visited) {
916 if (!Visited.insert(
BB).second) {
924 if (ExitBB)
return false;
939 if (
I.mayHaveSideEffects())
949 std::set<BasicBlock*> Visited;
960 bool LoopUnswitch::unswitchIfProfitable(
Value *LoopCond,
Constant *Val,
964 if (!BranchesInfo.costAllowsUnswitching()) {
967 <<
" at non-trivial condition '" << *Val
968 <<
"' == " << *LoopCond <<
"\n"
969 <<
". Cost too high.\n");
972 if (HasBranchDivergence &&
973 getAnalysis<LegacyDivergenceAnalysis>().isDivergent(LoopCond)) {
976 <<
" at non-trivial condition '" << *Val
977 <<
"' == " << *LoopCond <<
"\n"
978 <<
". Condition is divergent.\n");
982 unswitchNontrivialCondition(LoopCond, Val, CurrentLoop, TI, ToDuplicate);
989 void LoopUnswitch::emitPreheaderBranchOnCondition(
994 assert(TrueDest != FalseDest &&
"Branch targets should be different");
998 Value *BranchVal = LIC;
999 bool Swapped =
false;
1001 if (!ToDuplicate.
empty()) {
1004 auto *
New =
I->clone();
1005 New->insertBefore(OldBranch);
1011 MemorySSA *MSSA = MSSAU->getMemorySSA();
1017 auto *DefiningAccess = MemA->getDefiningAccess();
1019 while (L->
contains(DefiningAccess->getBlock())) {
1022 if (
auto *MemPhi = dyn_cast<MemoryPhi>(DefiningAccess)) {
1027 cast<MemoryDef>(DefiningAccess)->getDefiningAccess();
1030 MSSAU->createMemoryAccessInBB(New, DefiningAccess,
New->getParent(),
1034 BranchVal = Old2New[ToDuplicate[0]];
1037 if (!isa<ConstantInt>(Val) ||
1050 auto *OldBranchParent = OldBranch->
getParent();
1066 if (TrueDest != OldBranchSucc)
1068 if (FalseDest != OldBranchSucc)
1072 if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) {
1077 MSSAU->applyUpdates(Updates, *DT,
true);
1100 <<
" blocks] in Function "
1102 <<
" on cond: " << *Val <<
" == " << *
Cond <<
"\n");
1105 if (
auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
1106 SEWP->getSE().forgetTopmostLoop(L);
1127 auto *OldBranch = dyn_cast<BranchInst>(LoopPreheader->
getTerminator());
1128 assert(OldBranch &&
"Failed to split the preheader");
1129 emitPreheaderBranchOnCondition(
Cond, Val, NewExit, NewPH, OldBranch, TI);
1141 rewriteLoopBodyWithConditionConstant(L,
Cond, Val,
false);
1152 bool LoopUnswitch::tryTrivialLoopUnswitch(
bool &Changed) {
1178 if (!CurrentLoop->
contains(CurrentBB) || !Visited.
insert(CurrentBB).second)
1185 if (
I.mayHaveSideEffects())
1188 if (
BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1199 }
else if (
SwitchInst *
SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1206 CurrentBB =
SI->findCaseValue(
Cond)->getCaseSuccessor();
1212 CurrentTerm = CurrentBB->getTerminator();
1220 if (
BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
1226 Changed, MSSAU.get())
1241 }
else if ((LoopExitBB =
1248 if (!LoopExitBB || isa<PHINode>(LoopExitBB->
begin()))
1254 unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB,
1258 }
else if (
SwitchInst *
SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1261 Changed, MSSAU.get())
1266 if (!LoopCond || LoopCond !=
SI->getCondition())
1275 for (
auto Case :
SI->cases()) {
1277 if ((LoopExitCandidate =
1284 if (BranchesInfo.isUnswitched(
SI, CaseVal))
1286 LoopExitBB = LoopExitCandidate;
1294 if (!LoopExitBB || isa<PHINode>(LoopExitBB->
begin()))
1297 unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB,
1301 BranchesInfo.setUnswitched(
SI, CondVal);
1310 void LoopUnswitch::splitExitEdges(
1313 for (
unsigned I = 0,
E = ExitBlocks.size();
I !=
E; ++
I) {
1328 void LoopUnswitch::unswitchNontrivialCondition(
1334 <<
" blocks] in Function " <<
F->getName() <<
" when '"
1335 << *Val <<
"' == " << *LIC <<
"\n");
1339 if (
auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
1340 SEWP->getSE().forgetTopmostLoop(L);
1351 SplitEdge(LoopPreheader, LoopHeader, DT, LI, MSSAU.get());
1352 LoopBlocks.push_back(NewPreheader);
1362 splitExitEdges(L, ExitBlocks);
1374 NewBlocks.reserve(LoopBlocks.size());
1376 for (
unsigned I = 0,
E = LoopBlocks.size();
I !=
E; ++
I) {
1379 NewBlocks.push_back(NewBB);
1380 VMap[LoopBlocks[
I]] = NewBB;
1385 F->getBasicBlockList().splice(NewPreheader->
getIterator(),
1386 F->getBasicBlockList(),
1387 NewBlocks[0]->getIterator(),
F->end());
1394 BranchesInfo.cloneData(NewLoop, L, VMap);
1403 for (
unsigned EBI = 0, EBE = ExitBlocks.size(); EBI != EBE; ++EBI) {
1404 BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[EBI]]);
1407 ExitBBLoop->addBasicBlockToLoop(NewExit, *LI);
1410 "Exit block should have been split to have one successor!");
1416 Value *V = PN.getIncomingValueForBlock(ExitBlocks[EBI]);
1419 PN.addIncoming(V, NewExit);
1435 for (
unsigned NBI = 0, NBE = NewBlocks.size(); NBI != NBE; ++NBI) {
1439 if (
auto *II = dyn_cast<AssumeInst>(&
I))
1447 "Preheader splitting did not work correctly!");
1454 MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, VMap);
1458 emitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,
1462 MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMap, *DT);
1471 LoopProcessWorklist.push_back(NewLoop);
1481 if (ToDuplicate.
empty()) {
1484 rewriteLoopBodyWithConditionConstant(L, LIC, Val,
false);
1489 if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
1490 LICHandle && !isa<Constant>(LICHandle))
1491 rewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val,
1496 auto *CC = cast<ConstantInt>(Val);
1497 if (CC->isOneValue()) {
1498 rewriteLoopBodyWithConditionConstant(NewLoop, VMap[LIC], Val,
1501 rewriteLoopBodyWithConditionConstant(L, LIC, Val,
true);
1510 {DisableUnswitchMD});
1520 std::vector<Instruction *> &Worklist) {
1527 std::vector<Instruction *> &Worklist,
Loop *L,
1532 for (
unsigned i = 0,
e =
I->getNumOperands();
i !=
e; ++
i)
1534 Worklist.push_back(
Use);
1537 for (
User *U :
I->users())
1538 Worklist.push_back(cast<Instruction>(U));
1540 I->replaceAllUsesWith(V);
1541 if (!
I->mayHaveSideEffects()) {
1544 I->eraseFromParent();
1552 void LoopUnswitch::rewriteLoopBodyWithConditionConstant(
Loop *L,
Value *LIC,
1555 assert(!isa<Constant>(LIC) &&
"Why are we unswitching on a constant?");
1566 std::vector<Instruction*> Worklist;
1571 if (IsEqual || (isa<ConstantInt>(Val) &&
1578 !cast<ConstantInt>(Val)->getZExtValue());
1584 Worklist.push_back(UI);
1590 simplifyCode(Worklist, L);
1604 if (
Value *Replacement = simplifyInstructionWithNotEqual(UI, LIC, Val)) {
1620 Worklist.push_back(UI);
1624 if (!
SI || !isa<ConstantInt>(Val))
continue;
1630 *
SI->findCaseValue(cast<ConstantInt>(Val));
1632 if (DeadCase == *
SI->case_default())
1643 if (!
SI->findCaseDest(SISucc))
continue;
1647 if (Latch && DT->
dominates(SISucc, Latch))
1654 SplitEdge(Switch, SISucc, DT, LI, MSSAU.get());
1680 simplifyCode(Worklist, L);
1691 void LoopUnswitch::simplifyCode(std::vector<Instruction *> &Worklist,
Loop *L) {
1693 while (!Worklist.empty()) {
1695 Worklist.pop_back();
1702 for (
unsigned i = 0,
e =
I->getNumOperands();
i !=
e; ++
i)
1704 Worklist.push_back(
Use);
1707 MSSAU->removeMemoryAccess(
I);
1708 I->eraseFromParent();
1731 if (!SinglePred)
continue;
1732 assert(SinglePred == Pred &&
"CFG broken");
1736 auto SuccIt = Succ->
begin();
1737 while (
PHINode *PN = dyn_cast<PHINode>(SuccIt++)) {
1740 Worklist.push_back(
Use);
1742 Worklist.push_back(cast<Instruction>(U));
1764 ICmpInst *CI = dyn_cast<ICmpInst>(Inst);
1768 if ((Op0 == Invariant && Op1 == Val) || (Op0 == Val && Op1 == Invariant)) {
pred_range predecessors(BasicBlock *BB)
static IntegerType * getInt1Ty(LLVMContext &C)
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Value handle that is nullable, but tries to track the Value.
A parsed version of the target data layout string in and methods for querying it.
@ OC_OpChainAnd
There are only ANDs.
InstListType::iterator iterator
Instruction iterators...
const Function * getParent() const
Return the enclosing method, or null if none.
Represents a single loop in the control flow graph.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
static constexpr UpdateKind Insert
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.
DomTreeNodeBase * getIDom() const
succ_range successors(Instruction *I)
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
bool empty() const
empty - Check if the array is empty.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
block_iterator block_end() const
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
LLVM Basic Block Representation.
llvm::MDNode * makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, llvm::ArrayRef< llvm::StringRef > RemovePrefixes, llvm::ArrayRef< llvm::MDNode * > AddAttrs)
Create a new LoopID after the loop has been transformed.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
BasicBlockT * getCaseSuccessor() const
Resolves successor for current case.
This is the shared class of boolean and integer constants.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Pass * createLoopUnswitchPass(bool OptimizeForSize=false, bool hasBranchDivergence=false)
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
Legacy analysis pass which computes MemorySSA.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
iterator begin()
Instruction iterator methods.
INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops", false, false) INITIALIZE_PASS_END(LoopUnswitch
Represent the analysis usage information of a pass.
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
iterator_range< block_iterator > blocks() const
Option class for critical edge splitting.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
static Constant * getAllOnesValue(Type *Ty)
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
STATISTIC(NumFunctions, "Total number of functions")
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
Analysis containing CSE Info
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
static bool equalityPropUnSafe(Value &LoopCond)
FIXME: Remove this workaround when freeze related patches are done.
Value * getCondition() const
block_iterator block_begin() const
bool isIntegerTy() const
True if this is an instance of IntegerType.
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
ArrayRef< BasicBlock * >::const_iterator block_iterator
This is an important base class in LLVM.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
This instruction compares its operands according to the predicate given to the constructor.
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
This is an important class for using LLVM in a threaded context.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Encapsulates MemorySSA, including all data associated with memory accesses.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
initializer< Ty > init(const Ty &Val)
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
static MDString * get(LLVMContext &Context, StringRef Str)
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
iterator find(const_arg_type_t< KeyT > Val)
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void initializeLoopUnswitchPass(PassRegistry &)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB, BasicBlock *&ExitBB, std::set< BasicBlock * > &Visited)
Check to see if all paths from BB exit the loop with no side effects (including infinite loops).
@ OC_OpChainOr
There are only ORs.
This class represents the LLVM 'select' instruction.
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
static cl::opt< unsigned > MSSAThreshold("loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)
bool isUnconditional() const
@ OC_OpChainMixed
There are ANDs and ORs.
An immutable pass that tracks lazily created AssumptionCache objects.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
SmallVector< MachineOperand, 4 > Cond
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr) const
If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivi...
A cache of @llvm.assume calls within a function.
Type * getType() const
All values are typed, get the type of this value.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
LLVMContext & getContext() const
All values hold a context through their type.
self_iterator getIterator()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static Value * findLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, OperatorChain &ParentChain, DenseMap< Value *, Value * > &Cache, MemorySSAUpdater *MSSAU)
Cond is a condition that occurs in L.
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
static void removeFromWorklist(Instruction *I, std::vector< Instruction * > &Worklist)
Remove all instances of I from the worklist vector specified.
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
StringRef getName() const
Return a constant reference to the value's name.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
static ConstantInt * getFalse(LLVMContext &Context)
const Instruction & front() const
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
LLVMContext & getContext() const
Get the context in which this basic block lives.
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
static ConstantInt * getTrue(LLVMContext &Context)
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
static BasicBlock * isTrivialLoopExitBlock(Loop *L, BasicBlock *BB)
Return true if the specified block unconditionally leads to an exit from the specified loop,...
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Interval::pred_iterator pred_end(Interval *I)
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
CriticalEdgeSplittingOptions & setPreserveLCSSA()
BlockT * getHeader() const
iterator find(const KeyT &Val)
Optional< IVConditionInfo > hasPartialIVCondition(Loop &L, unsigned MSSAThreshold, MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
A wrapper class for inspecting calls to intrinsic functions.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Pass interface - Implemented by all 'passes'.
unsigned getNumOperands() const
static void replaceUsesOfWith(Instruction *I, Value *V, std::vector< Instruction * > &Worklist, Loop *L, LPPassManager *LPM, MemorySSAUpdater *MSSAU)
When we find that I really equals V, remove I from the program, replacing all uses with V and update ...
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
const BasicBlock * getParent() const
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Predicate getPredicate() const
Return the predicate for this instruction.
void swapProfMetadata()
If the instruction has "branch_weights" MD_prof metadata and the MDNode has three operands (including...
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
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
This function has undefined behavior.
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once.
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
AnalysisUsage & addRequired()
bool VerifyMemorySSA
Enables verification of MemorySSA.
OperatorChain
Operator chain lattice.
Value * getOperand(unsigned i) const
Conditional or Unconditional Branch instruction.
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
This is an alternative analysis pass to BranchProbabilityInfoWrapperPass.
@ OC_OpChainNone
There is no operator.
LLVM Value Representation.
iterator_range< user_iterator > users()
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
static constexpr UpdateKind Delete
A Use represents the edge between a Value definition and its users.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.