69#define DEBUG_TYPE "guard-widening"
71STATISTIC(GuardsEliminated,
"Number of eliminated guards");
72STATISTIC(CondBranchEliminated,
"Number of eliminated conditional branches");
73STATISTIC(FreezeAdded,
"Number of freeze instruction introduced");
77 cl::desc(
"Whether or not we should widen guards "
78 "expressed as branches by widenable conditions"),
86 assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
87 "Bad guard intrinsic?");
88 return GI->getArgOperand(0);
95 return cast<BranchInst>(
I)->getCondition();
102 assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
103 "Bad guard intrinsic?");
104 GI->setArgOperand(0, NewCond);
107 cast<BranchInst>(
I)->setCondition(NewCond);
131 return cast<Instruction>(WC);
135class GuardWideningImpl {
159 bool eliminateInstrViaWidening(
167 WS_IllegalOrNegative,
182 static StringRef scoreTypeToString(WideningScore WS);
186 WideningScore computeWideningScore(
Instruction *DominatedInstr,
195 return canBeHoistedTo(V, InsertPos, Visited);
204 [&](
const Value *V) {
return canBeHoistedTo(V, InsertPos); });
212 for (
Value *V : Checks)
213 makeAvailableAt(V, InsertPos);
251 void setBase(
const Value *NewBase) {
Base = NewBase; }
254 const Value *getBase()
const {
return Base; }
256 const APInt &getOffsetValue()
const {
return getOffset()->getValue(); }
258 ICmpInst *getCheckInst()
const {
return CheckInst; }
262 Base->printAsOperand(
OS, PrintTypes);
264 Offset->printAsOperand(
OS, PrintTypes);
266 Length->printAsOperand(
OS, PrintTypes);
280 for (
auto CheckCond : ToParse) {
281 if (!parseRangeChecks(CheckCond, Checks))
300 return mergeChecks(ChecksToHoist, ChecksToWiden,
nullptr)
308 Instruction *InsertPt = findInsertionPointForWideCondition(ToWiden);
309 auto MergedCheck = mergeChecks(ChecksToHoist, ChecksToWiden, InsertPt);
311 : hoistChecks(ChecksToHoist,
312 getCondition(ToWiden), InsertPt);
318 setCondition(ToWiden, Result);
325 std::function<
bool(
BasicBlock *)> BlockFilter)
326 : DT(DT), PDT(PDT), LI(LI), AC(AC), MSSAU(MSSAU), Root(Root),
327 BlockFilter(BlockFilter) {}
342bool GuardWideningImpl::run() {
344 bool Changed =
false;
347 auto *BB = (*DFI)->getBlock();
348 if (!BlockFilter(BB))
351 auto &CurrentList = GuardsInBlock[BB];
355 CurrentList.push_back(cast<Instruction>(&
I));
357 for (
auto *II : CurrentList)
358 Changed |= eliminateInstrViaWidening(II, DFI, GuardsInBlock);
361 assert(EliminatedGuardsAndBranches.
empty() || Changed);
362 for (
auto *
I : EliminatedGuardsAndBranches)
363 if (!WidenedGuards.
count(
I)) {
364 assert(isa<ConstantInt>(getCondition(
I)) &&
"Should be!");
366 eliminateGuard(
I, MSSAU);
369 "Eliminated something other than guard or branch?");
370 ++CondBranchEliminated;
377bool GuardWideningImpl::eliminateInstrViaWidening(
386 if (ChecksToHoist.
empty() ||
387 (ChecksToHoist.
size() == 1 && isa<ConstantInt>(ChecksToHoist.
front())))
391 auto BestScoreSoFar = WS_IllegalOrNegative;
395 for (
unsigned i = 0, e = DFSI.
getPathLength(); i != e; ++i) {
396 auto *CurBB = DFSI.
getPath(i)->getBlock();
397 if (!BlockFilter(CurBB))
399 assert(GuardsInBlock.
count(CurBB) &&
"Must have been populated by now!");
400 const auto &GuardsInCurBB = GuardsInBlock.
find(CurBB)->second;
402 auto I = GuardsInCurBB.begin();
403 auto E =
Instr->getParent() == CurBB ?
find(GuardsInCurBB, Instr)
404 : GuardsInCurBB.
end();
409 for (
auto &
I : *CurBB) {
410 if (
Index == GuardsInCurBB.size())
412 if (GuardsInCurBB[
Index] == &
I)
416 "Guards expected to be in order!");
420 assert((i == (e - 1)) == (
Instr->getParent() == CurBB) &&
"Bad DFS?");
423 auto *WideningPoint = findInsertionPointForWideCondition(Candidate);
428 auto Score = computeWideningScore(Instr, Candidate, WideningPoint,
429 ChecksToHoist, CandidateChecks);
430 LLVM_DEBUG(
dbgs() <<
"Score between " << *Instr <<
" and " << *Candidate
431 <<
" is " << scoreTypeToString(Score) <<
"\n");
432 if (Score > BestScoreSoFar) {
433 BestScoreSoFar = Score;
434 BestSoFar = Candidate;
439 if (BestScoreSoFar == WS_IllegalOrNegative) {
440 LLVM_DEBUG(
dbgs() <<
"Did not eliminate guard " << *Instr <<
"\n");
444 assert(BestSoFar != Instr &&
"Should have never visited same guard!");
447 LLVM_DEBUG(
dbgs() <<
"Widening " << *Instr <<
" into " << *BestSoFar
448 <<
" with score " << scoreTypeToString(BestScoreSoFar)
452 widenGuard(ChecksToHoist, ChecksToWiden, BestSoFar);
454 setCondition(Instr, NewGuardCondition);
455 EliminatedGuardsAndBranches.push_back(Instr);
456 WidenedGuards.
insert(BestSoFar);
460GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
466 bool HoistingOutOfLoop =
false;
468 if (DominatingGuardLoop != DominatedInstrLoop) {
471 if (DominatingGuardLoop &&
472 !DominatingGuardLoop->
contains(DominatedInstrLoop))
473 return WS_IllegalOrNegative;
475 HoistingOutOfLoop =
true;
478 if (!canBeHoistedTo(ChecksToHoist, WideningPoint))
479 return WS_IllegalOrNegative;
483 if (!canBeHoistedTo(getCondition(ToWiden), WideningPoint))
484 return WS_IllegalOrNegative;
494 if (isWideningCondProfitable(ChecksToHoist, ChecksToWiden))
495 return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
497 if (HoistingOutOfLoop)
503 if (
auto *UniqueSucc = BB->getUniqueSuccessor())
505 auto *
Term = BB->getTerminator();
507 const BasicBlock *IfTrue =
nullptr, *IfFalse =
nullptr;
508 using namespace PatternMatch;
513 if (
auto *ConstCond = dyn_cast<ConstantInt>(
Cond))
514 return ConstCond->isAllOnesValue() ? IfTrue : IfFalse;
516 if (IfFalse->getPostdominatingDeoptimizeCall())
529 auto MaybeHoistingToHotterBlock = [&]() {
530 const auto *DominatingBlock = WideningPoint->
getParent();
531 const auto *DominatedBlock = DominatedInstr->
getParent();
536 assert(DT.
dominates(DominatingBlock, DominatedBlock) &&
"No dominance");
537 while (DominatedBlock != DominatingBlock) {
538 auto *LikelySucc = GetLikelySuccessor(DominatingBlock);
545 DominatingBlock = LikelySucc;
549 if (DominatedBlock == DominatingBlock)
553 if (!DT.
dominates(DominatingBlock, DominatedBlock))
558 return !PDT->
dominates(DominatedBlock, DominatingBlock);
561 return MaybeHoistingToHotterBlock() ? WS_IllegalOrNegative : WS_Neutral;
564bool GuardWideningImpl::canBeHoistedTo(
567 auto *Inst = dyn_cast<Instruction>(V);
572 Inst->mayReadFromMemory())
578 assert(!isa<PHINode>(Loc) &&
579 "PHIs should return false for isSafeToSpeculativelyExecute");
581 "We did a DFS from the block entry!");
582 return all_of(Inst->operands(),
583 [&](
Value *
Op) { return canBeHoistedTo(Op, Loc, Visited); });
587 auto *Inst = dyn_cast<Instruction>(V);
592 !Inst->mayReadFromMemory() &&
593 "Should've checked with canBeHoistedTo!");
595 for (
Value *
Op : Inst->operands())
596 makeAvailableAt(
Op, Loc);
598 Inst->moveBefore(Loc);
604 auto *
I = dyn_cast<Instruction>(V);
608 auto *Res =
I->getInsertionPointAfterDef();
616 Instruction *User = cast<Instruction>(U);
617 return Res != User && DT.dominates(I, User) && !DT.dominates(Res, User);
628 return new FreezeInst(Orig,
"gw.freeze", InsertPt);
629 if (isa<Constant>(Orig) || isa<GlobalValue>(Orig))
630 return new FreezeInst(Orig,
"gw.freeze", InsertPtAtDef);
641 auto handleConstantOrGlobal = [&](
Use &
U) {
643 if (!isa<Constant>(Def) && !isa<GlobalValue>(Def))
646 if (Visited.
insert(Def).second) {
653 if (CacheOfFreezes.
count(Def))
654 U.set(CacheOfFreezes[Def]);
659 while (!Worklist.
empty()) {
661 if (!Visited.
insert(V).second)
676 return isa<Instruction>(Op) && !getFreezeInsertPt(Op, DT);
682 for (
Use &U :
I->operands())
683 if (!handleConstantOrGlobal(U))
687 I->dropPoisonGeneratingFlagsAndMetadata();
690 for (
Value *V : NeedFreeze) {
696 V->replaceUsesWithIf(
697 FI, [&](
const Use & U)->
bool {
return U.getUser() != FI; });
703std::optional<Value *>
717 if (ChecksToWiden.
size() == 1 && ChecksToHoist.
size() == 1 &&
731 if (std::optional<ConstantRange> Intersect =
735 if (Intersect->getEquivalentICmp(Pred, NewRHSAP)) {
739 assert(canBeHoistedTo(LHS, InsertPt) &&
"must be");
740 makeAvailableAt(LHS, InsertPt);
751 if (parseRangeChecks(ChecksToWiden, Checks) &&
752 parseRangeChecks(ChecksToHoist, Checks) &&
753 combineRangeChecks(Checks, CombinedChecks)) {
755 for (
auto &RC : CombinedChecks) {
756 makeAvailableAt(RC.getCheckInst(), InsertPt);
758 Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result,
"",
761 Result = RC.getCheckInst();
763 assert(Result &&
"Failed to find result value");
764 Result->setName(
"wide.chk");
765 Result = freezeAndPush(Result, InsertPt);
780 makeAvailableAt(ChecksToHoist, InsertPt);
781 makeAvailableAt(OldCondition, InsertPt);
783 Result = freezeAndPush(Result, InsertPt);
785 Result->setName(
"wide.chk");
789bool GuardWideningImpl::parseRangeChecks(
793 auto *IC = dyn_cast<ICmpInst>(CheckCond);
794 if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
795 (IC->getPredicate() != ICmpInst::ICMP_ULT &&
796 IC->getPredicate() != ICmpInst::ICMP_UGT))
799 const Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
800 if (IC->getPredicate() == ICmpInst::ICMP_UGT)
803 auto &
DL = IC->getModule()->getDataLayout();
805 GuardWideningImpl::RangeCheck
Check(
806 CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
824 auto *BaseInst = dyn_cast<Instruction>(
Check.getBase());
826 "Unreachable instruction?");
830 Check.setBase(OpLHS);
838 Check.setBase(OpLHS);
850bool GuardWideningImpl::combineRangeChecks(
853 unsigned OldCount = Checks.
size();
854 while (!Checks.
empty()) {
857 const Value *CurrentBase = Checks.
front().getBase();
858 const Value *CurrentLength = Checks.
front().getLength();
862 auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
863 return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
866 copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
869 assert(CurrentChecks.
size() != 0 &&
"We know we have at least one!");
871 if (CurrentChecks.
size() < 3) {
879 llvm::sort(CurrentChecks, [&](
const GuardWideningImpl::RangeCheck &LHS,
880 const GuardWideningImpl::RangeCheck &RHS) {
881 return LHS.getOffsetValue().slt(
RHS.getOffsetValue());
890 if ((MaxOffset->
getValue() - MinOffset->getValue())
894 APInt MaxDiff = MaxOffset->
getValue() - MinOffset->getValue();
896 auto OffsetOK = [&](
const GuardWideningImpl::RangeCheck &RC) {
897 return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
942 assert(RangeChecksOut.
size() <= OldCount &&
"We pessimized!");
943 return RangeChecksOut.
size() != OldCount;
947StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
949 case WS_IllegalOrNegative:
950 return "IllegalOrNegative";
955 case WS_VeryPositive:
956 return "VeryPositive";
970 std::unique_ptr<MemorySSAUpdater> MSSAU;
972 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAA->getMSSA());
973 if (!GuardWideningImpl(DT, &PDT, LI, AC, MSSAU ? MSSAU.get() :
nullptr,
989 RootBB = L.getHeader();
991 return BB == RootBB || L.contains(BB);
993 std::unique_ptr<MemorySSAUpdater> MSSAU;
995 MSSAU = std::make_unique<MemorySSAUpdater>(AR.
MSSA);
996 if (!GuardWideningImpl(AR.
DT,
nullptr, AR.
LI, AR.
AC,
997 MSSAU ? MSSAU.get() :
nullptr, AR.
DT.
getNode(RootBB),
1017 if (skipFunction(
F))
1019 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1020 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1021 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1022 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1023 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
1024 std::unique_ptr<MemorySSAUpdater> MSSAU;
1026 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
1027 return GuardWideningImpl(DT, &PDT, LI, AC, MSSAU ? MSSAU.get() :
nullptr,
1044struct LoopGuardWideningLegacyPass :
public LoopPass {
1047 LoopGuardWideningLegacyPass() :
LoopPass(
ID) {
1054 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1055 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1056 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
1057 *
L->getHeader()->getParent());
1058 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
1059 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() :
nullptr;
1060 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
1061 std::unique_ptr<MemorySSAUpdater> MSSAU;
1063 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
1067 RootBB =
L->getHeader();
1069 return BB == RootBB ||
L->contains(BB);
1071 return GuardWideningImpl(DT, PDT, LI, AC, MSSAU ? MSSAU.get() :
nullptr,
1072 DT.
getNode(RootBB), BlockFilter)
1085char GuardWideningLegacyPass::ID = 0;
1086char LoopGuardWideningLegacyPass::ID = 0;
1107 return new GuardWideningLegacyPass();
1111 return new LoopGuardWideningLegacyPass();
static SDValue Widen(SelectionDAG *CurDAG, SDValue N)
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool runOnFunction(Function &F, bool PostInlining)
static cl::opt< bool > WidenBranchGuards("guard-widening-widen-branch-guards", cl::Hidden, cl::desc("Whether or not we should widen guards " "expressed as branches by widenable conditions"), cl::init(true))
static bool isSupportedGuardInstruction(const Instruction *Insn)
static Instruction * getFreezeInsertPt(Value *V, const DominatorTree &DT)
modulo schedule Modulo Schedule test pass
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class for arbitrary precision integers.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool isMinValue() const
Determine if this is the smallest unsigned value.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
A container for analyses that lazily runs them and caches their results.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const_iterator getFirstNonPHIOrDbgOrAlloca() const
Returns an iterator to the first instruction in this block that is not a PHINode, a debug intrinsic,...
const CallInst * getPostdominatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...
Represents analyses that only rely on functions' control flow.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
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.
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
std::optional< ConstantRange > exactIntersectWith(const ConstantRange &CR) const
Intersect the two ranges and return the result if it can be represented exactly, otherwise return std...
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Implements a dense probed hash-table based set.
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass class - This class is used to implement most global optimizations.
This instruction compares its operands according to the predicate given to the constructor.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
const BasicBlock * getParent() const
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
A wrapper class for inspecting calls to intrinsic functions.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
An analysis that produces MemorySSA for a function.
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Legacy analysis pass which computes MemorySSA.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
LLVMContext & getContext() const
All values hold a context through their type.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
unsigned getPathLength() const
getPathLength - Return the length of the path from the entry node to the current node,...
NodeRef getPath(unsigned n) const
getPath - Return the n'th node in the path from the entry node to the current node.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< InstrNode * > Instr
NodeAddr< DefNode * > Def
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
FunctionPass * createGuardWideningPass()
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
void initializeLoopGuardWideningLegacyPassPass(PassRegistry &)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
df_iterator< T > df_begin(const T &G)
Value * extractWidenableCondition(const User *U)
void parseWidenableGuard(const User *U, llvm::SmallVectorImpl< Value * > &Checks)
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void setWidenableBranchCond(BranchInst *WidenableBR, Value *Cond)
Given a branch we know is widenable (defined per Analysis/GuardUtils.h), set it's condition such that...
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
bool parseWidenableBranch(const User *U, Value *&Condition, Value *&WidenableCondition, BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB)
If U is widenable branch looking like: cond = ... wc = call i1 @llvm.experimental....
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
canCreateUndefOrPoison returns true if Op can create undef or poison from non-undef & non-poison oper...
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
bool isGuardAsWidenableBranch(const User *U)
Returns true iff U has semantics of a guard expressed in a form of a widenable conditional branch to ...
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
void initializeGuardWideningLegacyPassPass(PassRegistry &)
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
df_iterator< T > df_end(const T &G)
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Pass * createLoopGuardWideningPass()
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...