diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp index b650971624a7..a56a37a618bc 100644 --- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -1,784 +1,787 @@ //===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file implements the Correlated Value Propagation pass. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/Local.h" #include #include using namespace llvm; #define DEBUG_TYPE "correlated-value-propagation" STATISTIC(NumPhis, "Number of phis propagated"); STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value"); STATISTIC(NumSelects, "Number of selects propagated"); STATISTIC(NumMemAccess, "Number of memory access targets propagated"); STATISTIC(NumCmps, "Number of comparisons propagated"); STATISTIC(NumReturns, "Number of return values propagated"); STATISTIC(NumDeadCases, "Number of switch cases removed"); STATISTIC(NumSDivs, "Number of sdiv converted to udiv"); STATISTIC(NumUDivs, "Number of udivs whose width was decreased"); STATISTIC(NumAShrs, "Number of ashr converted to lshr"); STATISTIC(NumSRems, "Number of srem converted to urem"); STATISTIC(NumOverflows, "Number of overflow checks removed"); static cl::opt DontProcessAdds("cvp-dont-process-adds", cl::init(true)); namespace { class CorrelatedValuePropagation : public FunctionPass { public: static char ID; CorrelatedValuePropagation(): FunctionPass(ID) { initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry()); } bool runOnFunction(Function &F) override; void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.addRequired(); AU.addPreserved(); AU.addPreserved(); } }; } // end anonymous namespace char CorrelatedValuePropagation::ID = 0; INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation", "Value Propagation", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation", "Value Propagation", false, false) // Public interface to the Value Propagation pass Pass *llvm::createCorrelatedValuePropagationPass() { return new CorrelatedValuePropagation(); } static bool processSelect(SelectInst *S, LazyValueInfo *LVI) { if (S->getType()->isVectorTy()) return false; if (isa(S->getOperand(0))) return false; Constant *C = LVI->getConstant(S->getCondition(), S->getParent(), S); if (!C) return false; ConstantInt *CI = dyn_cast(C); if (!CI) return false; Value *ReplaceWith = S->getTrueValue(); Value *Other = S->getFalseValue(); if (!CI->isOne()) std::swap(ReplaceWith, Other); if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType()); S->replaceAllUsesWith(ReplaceWith); S->eraseFromParent(); ++NumSelects; return true; } /// Try to simplify a phi with constant incoming values that match the edge /// values of a non-constant value on all other edges: /// bb0: /// %isnull = icmp eq i8* %x, null /// br i1 %isnull, label %bb2, label %bb1 /// bb1: /// br label %bb2 /// bb2: /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ] /// --> /// %r = %x static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT) { // Collect incoming constants and initialize possible common value. SmallVector, 4> IncomingConstants; Value *CommonValue = nullptr; for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { Value *Incoming = P->getIncomingValue(i); if (auto *IncomingConstant = dyn_cast(Incoming)) { IncomingConstants.push_back(std::make_pair(IncomingConstant, i)); } else if (!CommonValue) { // The potential common value is initialized to the first non-constant. CommonValue = Incoming; } else if (Incoming != CommonValue) { // There can be only one non-constant common value. return false; } } if (!CommonValue || IncomingConstants.empty()) return false; // The common value must be valid in all incoming blocks. BasicBlock *ToBB = P->getParent(); if (auto *CommonInst = dyn_cast(CommonValue)) if (!DT->dominates(CommonInst, ToBB)) return false; // We have a phi with exactly 1 variable incoming value and 1 or more constant // incoming values. See if all constant incoming values can be mapped back to // the same incoming variable value. for (auto &IncomingConstant : IncomingConstants) { Constant *C = IncomingConstant.first; BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second); if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P)) return false; } // All constant incoming values map to the same variable along the incoming // edges of the phi. The phi is unnecessary. P->replaceAllUsesWith(CommonValue); P->eraseFromParent(); ++NumPhiCommon; return true; } static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ) { bool Changed = false; BasicBlock *BB = P->getParent(); for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { Value *Incoming = P->getIncomingValue(i); if (isa(Incoming)) continue; Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P); // Look if the incoming value is a select with a scalar condition for which // LVI can tells us the value. In that case replace the incoming value with // the appropriate value of the select. This often allows us to remove the // select later. if (!V) { SelectInst *SI = dyn_cast(Incoming); if (!SI) continue; Value *Condition = SI->getCondition(); if (!Condition->getType()->isVectorTy()) { if (Constant *C = LVI->getConstantOnEdge( Condition, P->getIncomingBlock(i), BB, P)) { if (C->isOneValue()) { V = SI->getTrueValue(); } else if (C->isZeroValue()) { V = SI->getFalseValue(); } // Once LVI learns to handle vector types, we could also add support // for vector type constants that are not all zeroes or all ones. } } // Look if the select has a constant but LVI tells us that the incoming // value can never be that constant. In that case replace the incoming // value with the other value of the select. This often allows us to // remove the select later. if (!V) { Constant *C = dyn_cast(SI->getFalseValue()); if (!C) continue; if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, P->getIncomingBlock(i), BB, P) != LazyValueInfo::False) continue; V = SI->getTrueValue(); } LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n'); } P->setIncomingValue(i, V); Changed = true; } if (Value *V = SimplifyInstruction(P, SQ)) { P->replaceAllUsesWith(V); P->eraseFromParent(); Changed = true; } if (!Changed) Changed = simplifyCommonValuePhi(P, LVI, DT); if (Changed) ++NumPhis; return Changed; } static bool processMemAccess(Instruction *I, LazyValueInfo *LVI) { Value *Pointer = nullptr; if (LoadInst *L = dyn_cast(I)) Pointer = L->getPointerOperand(); else Pointer = cast(I)->getPointerOperand(); if (isa(Pointer)) return false; Constant *C = LVI->getConstant(Pointer, I->getParent(), I); if (!C) return false; ++NumMemAccess; I->replaceUsesOfWith(Pointer, C); return true; } /// See if LazyValueInfo's ability to exploit edge conditions or range /// information is sufficient to prove this comparison. Even for local /// conditions, this can sometimes prove conditions instcombine can't by /// exploiting range information. static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) { Value *Op0 = Cmp->getOperand(0); auto *C = dyn_cast(Cmp->getOperand(1)); if (!C) return false; // As a policy choice, we choose not to waste compile time on anything where // the comparison is testing local values. While LVI can sometimes reason // about such cases, it's not its primary purpose. We do make sure to do // the block local query for uses from terminator instructions, but that's // handled in the code for each terminator. auto *I = dyn_cast(Op0); if (I && I->getParent() == Cmp->getParent()) return false; LazyValueInfo::Tristate Result = LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp); if (Result == LazyValueInfo::Unknown) return false; ++NumCmps; Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result); Cmp->replaceAllUsesWith(TorF); Cmp->eraseFromParent(); return true; } /// Simplify a switch instruction by removing cases which can never fire. If the /// uselessness of a case could be determined locally then constant propagation /// would already have figured it out. Instead, walk the predecessors and /// statically evaluate cases based on information available on that edge. Cases /// that cannot fire no matter what the incoming edge can safely be removed. If /// a case fires on every incoming edge then the entire switch can be removed /// and replaced with a branch to the case destination. static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI, DominatorTree *DT) { DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy); Value *Cond = SI->getCondition(); BasicBlock *BB = SI->getParent(); // If the condition was defined in same block as the switch then LazyValueInfo // currently won't say anything useful about it, though in theory it could. if (isa(Cond) && cast(Cond)->getParent() == BB) return false; // If the switch is unreachable then trying to improve it is a waste of time. pred_iterator PB = pred_begin(BB), PE = pred_end(BB); if (PB == PE) return false; // Analyse each switch case in turn. bool Changed = false; DenseMap SuccessorsCount; for (auto *Succ : successors(BB)) SuccessorsCount[Succ]++; for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) { ConstantInt *Case = CI->getCaseValue(); // Check to see if the switch condition is equal to/not equal to the case // value on every incoming edge, equal/not equal being the same each time. LazyValueInfo::Tristate State = LazyValueInfo::Unknown; for (pred_iterator PI = PB; PI != PE; ++PI) { // Is the switch condition equal to the case value? LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ, Cond, Case, *PI, BB, SI); // Give up on this case if nothing is known. if (Value == LazyValueInfo::Unknown) { State = LazyValueInfo::Unknown; break; } // If this was the first edge to be visited, record that all other edges // need to give the same result. if (PI == PB) { State = Value; continue; } // If this case is known to fire for some edges and known not to fire for // others then there is nothing we can do - give up. if (Value != State) { State = LazyValueInfo::Unknown; break; } } if (State == LazyValueInfo::False) { // This case never fires - remove it. BasicBlock *Succ = CI->getCaseSuccessor(); Succ->removePredecessor(BB); CI = SI->removeCase(CI); CE = SI->case_end(); // The condition can be modified by removePredecessor's PHI simplification // logic. Cond = SI->getCondition(); ++NumDeadCases; Changed = true; if (--SuccessorsCount[Succ] == 0) DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}}); continue; } if (State == LazyValueInfo::True) { // This case always fires. Arrange for the switch to be turned into an // unconditional branch by replacing the switch condition with the case // value. SI->setCondition(Case); NumDeadCases += SI->getNumCases(); Changed = true; break; } // Increment the case iterator since we didn't delete it. ++CI; } if (Changed) // If the switch has been simplified to the point where it can be replaced // by a branch then do so now. ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false, /*TLI = */ nullptr, &DTU); return Changed; } // See if we can prove that the given overflow intrinsic will not overflow. static bool willNotOverflow(WithOverflowInst *WO, LazyValueInfo *LVI) { Value *RHS = WO->getRHS(); ConstantRange RRange = LVI->getConstantRange(RHS, WO->getParent(), WO); ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion( WO->getBinaryOp(), RRange, WO->getNoWrapKind()); // As an optimization, do not compute LRange if we do not need it. if (NWRegion.isEmptySet()) return false; Value *LHS = WO->getLHS(); ConstantRange LRange = LVI->getConstantRange(LHS, WO->getParent(), WO); return NWRegion.contains(LRange); } static void processOverflowIntrinsic(WithOverflowInst *WO) { IRBuilder<> B(WO); Value *NewOp = B.CreateBinOp( WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), WO->getName()); - if (WO->isSigned()) - cast(NewOp)->setHasNoSignedWrap(); - else - cast(NewOp)->setHasNoUnsignedWrap(); + // Constant-holing could have happened. + if (auto *Inst = dyn_cast(NewOp)) { + if (WO->isSigned()) + Inst->setHasNoSignedWrap(); + else + Inst->setHasNoUnsignedWrap(); + } Value *NewI = B.CreateInsertValue(UndefValue::get(WO->getType()), NewOp, 0); NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(WO->getContext()), 1); WO->replaceAllUsesWith(NewI); WO->eraseFromParent(); ++NumOverflows; } /// Infer nonnull attributes for the arguments at the specified callsite. static bool processCallSite(CallSite CS, LazyValueInfo *LVI) { SmallVector ArgNos; unsigned ArgNo = 0; if (auto *WO = dyn_cast(CS.getInstruction())) { if (willNotOverflow(WO, LVI)) { processOverflowIntrinsic(WO); return true; } } // Deopt bundle operands are intended to capture state with minimal // perturbance of the code otherwise. If we can find a constant value for // any such operand and remove a use of the original value, that's // desireable since it may allow further optimization of that value (e.g. via // single use rules in instcombine). Since deopt uses tend to, // idiomatically, appear along rare conditional paths, it's reasonable likely // we may have a conditional fact with which LVI can fold. if (auto DeoptBundle = CS.getOperandBundle(LLVMContext::OB_deopt)) { bool Progress = false; for (const Use &ConstU : DeoptBundle->Inputs) { Use &U = const_cast(ConstU); Value *V = U.get(); if (V->getType()->isVectorTy()) continue; if (isa(V)) continue; Constant *C = LVI->getConstant(V, CS.getParent(), CS.getInstruction()); if (!C) continue; U.set(C); Progress = true; } if (Progress) return true; } for (Value *V : CS.args()) { PointerType *Type = dyn_cast(V->getType()); // Try to mark pointer typed parameters as non-null. We skip the // relatively expensive analysis for constants which are obviously either // null or non-null to start with. if (Type && !CS.paramHasAttr(ArgNo, Attribute::NonNull) && !isa(V) && LVI->getPredicateAt(ICmpInst::ICMP_EQ, V, ConstantPointerNull::get(Type), CS.getInstruction()) == LazyValueInfo::False) ArgNos.push_back(ArgNo); ArgNo++; } assert(ArgNo == CS.arg_size() && "sanity check"); if (ArgNos.empty()) return false; AttributeList AS = CS.getAttributes(); LLVMContext &Ctx = CS.getInstruction()->getContext(); AS = AS.addParamAttribute(Ctx, ArgNos, Attribute::get(Ctx, Attribute::NonNull)); CS.setAttributes(AS); return true; } static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI) { Constant *Zero = ConstantInt::get(SDI->getType(), 0); for (Value *O : SDI->operands()) { auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI); if (Result != LazyValueInfo::True) return false; } return true; } /// Try to shrink a udiv/urem's width down to the smallest power of two that's /// sufficient to contain its operands. static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) { assert(Instr->getOpcode() == Instruction::UDiv || Instr->getOpcode() == Instruction::URem); if (Instr->getType()->isVectorTy()) return false; // Find the smallest power of two bitwidth that's sufficient to hold Instr's // operands. auto OrigWidth = Instr->getType()->getIntegerBitWidth(); ConstantRange OperandRange(OrigWidth, /*isFullset=*/false); for (Value *Operand : Instr->operands()) { OperandRange = OperandRange.unionWith( LVI->getConstantRange(Operand, Instr->getParent())); } // Don't shrink below 8 bits wide. unsigned NewWidth = std::max( PowerOf2Ceil(OperandRange.getUnsignedMax().getActiveBits()), 8); // NewWidth might be greater than OrigWidth if OrigWidth is not a power of // two. if (NewWidth >= OrigWidth) return false; ++NumUDivs; IRBuilder<> B{Instr}; auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth); auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy, Instr->getName() + ".lhs.trunc"); auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy, Instr->getName() + ".rhs.trunc"); auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName()); auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext"); if (auto *BinOp = dyn_cast(BO)) if (BinOp->getOpcode() == Instruction::UDiv) BinOp->setIsExact(Instr->isExact()); Instr->replaceAllUsesWith(Zext); Instr->eraseFromParent(); return true; } static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) { if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI)) return false; ++NumSRems; auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1), SDI->getName(), SDI); BO->setDebugLoc(SDI->getDebugLoc()); SDI->replaceAllUsesWith(BO); SDI->eraseFromParent(); // Try to process our new urem. processUDivOrURem(BO, LVI); return true; } /// See if LazyValueInfo's ability to exploit edge conditions or range /// information is sufficient to prove the both operands of this SDiv are /// positive. If this is the case, replace the SDiv with a UDiv. Even for local /// conditions, this can sometimes prove conditions instcombine can't by /// exploiting range information. static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) { if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI)) return false; ++NumSDivs; auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1), SDI->getName(), SDI); BO->setDebugLoc(SDI->getDebugLoc()); BO->setIsExact(SDI->isExact()); SDI->replaceAllUsesWith(BO); SDI->eraseFromParent(); // Try to simplify our new udiv. processUDivOrURem(BO, LVI); return true; } static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) { if (SDI->getType()->isVectorTy()) return false; Constant *Zero = ConstantInt::get(SDI->getType(), 0); if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) != LazyValueInfo::True) return false; ++NumAShrs; auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1), SDI->getName(), SDI); BO->setDebugLoc(SDI->getDebugLoc()); BO->setIsExact(SDI->isExact()); SDI->replaceAllUsesWith(BO); SDI->eraseFromParent(); return true; } static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) { using OBO = OverflowingBinaryOperator; if (DontProcessAdds) return false; if (AddOp->getType()->isVectorTy()) return false; bool NSW = AddOp->hasNoSignedWrap(); bool NUW = AddOp->hasNoUnsignedWrap(); if (NSW && NUW) return false; BasicBlock *BB = AddOp->getParent(); Value *LHS = AddOp->getOperand(0); Value *RHS = AddOp->getOperand(1); ConstantRange LRange = LVI->getConstantRange(LHS, BB, AddOp); // Initialize RRange only if we need it. If we know that guaranteed no wrap // range for the given LHS range is empty don't spend time calculating the // range for the RHS. Optional RRange; auto LazyRRange = [&] () { if (!RRange) RRange = LVI->getConstantRange(RHS, BB, AddOp); return RRange.getValue(); }; bool Changed = false; if (!NUW) { ConstantRange NUWRange = ConstantRange::makeGuaranteedNoWrapRegion( BinaryOperator::Add, LRange, OBO::NoUnsignedWrap); if (!NUWRange.isEmptySet()) { bool NewNUW = NUWRange.contains(LazyRRange()); AddOp->setHasNoUnsignedWrap(NewNUW); Changed |= NewNUW; } } if (!NSW) { ConstantRange NSWRange = ConstantRange::makeGuaranteedNoWrapRegion( BinaryOperator::Add, LRange, OBO::NoSignedWrap); if (!NSWRange.isEmptySet()) { bool NewNSW = NSWRange.contains(LazyRRange()); AddOp->setHasNoSignedWrap(NewNSW); Changed |= NewNSW; } } return Changed; } static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) { if (Constant *C = LVI->getConstant(V, At->getParent(), At)) return C; // TODO: The following really should be sunk inside LVI's core algorithm, or // at least the outer shims around such. auto *C = dyn_cast(V); if (!C) return nullptr; Value *Op0 = C->getOperand(0); Constant *Op1 = dyn_cast(C->getOperand(1)); if (!Op1) return nullptr; LazyValueInfo::Tristate Result = LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At); if (Result == LazyValueInfo::Unknown) return nullptr; return (Result == LazyValueInfo::True) ? ConstantInt::getTrue(C->getContext()) : ConstantInt::getFalse(C->getContext()); } static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ) { bool FnChanged = false; // Visiting in a pre-order depth-first traversal causes us to simplify early // blocks before querying later blocks (which require us to analyze early // blocks). Eagerly simplifying shallow blocks means there is strictly less // work to do for deep blocks. This also means we don't visit unreachable // blocks. for (BasicBlock *BB : depth_first(&F.getEntryBlock())) { bool BBChanged = false; for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { Instruction *II = &*BI++; switch (II->getOpcode()) { case Instruction::Select: BBChanged |= processSelect(cast(II), LVI); break; case Instruction::PHI: BBChanged |= processPHI(cast(II), LVI, DT, SQ); break; case Instruction::ICmp: case Instruction::FCmp: BBChanged |= processCmp(cast(II), LVI); break; case Instruction::Load: case Instruction::Store: BBChanged |= processMemAccess(II, LVI); break; case Instruction::Call: case Instruction::Invoke: BBChanged |= processCallSite(CallSite(II), LVI); break; case Instruction::SRem: BBChanged |= processSRem(cast(II), LVI); break; case Instruction::SDiv: BBChanged |= processSDiv(cast(II), LVI); break; case Instruction::UDiv: case Instruction::URem: BBChanged |= processUDivOrURem(cast(II), LVI); break; case Instruction::AShr: BBChanged |= processAShr(cast(II), LVI); break; case Instruction::Add: BBChanged |= processAdd(cast(II), LVI); break; } } Instruction *Term = BB->getTerminator(); switch (Term->getOpcode()) { case Instruction::Switch: BBChanged |= processSwitch(cast(Term), LVI, DT); break; case Instruction::Ret: { auto *RI = cast(Term); // Try to determine the return value if we can. This is mainly here to // simplify the writing of unit tests, but also helps to enable IPO by // constant folding the return values of callees. auto *RetVal = RI->getReturnValue(); if (!RetVal) break; // handle "ret void" if (isa(RetVal)) break; // nothing to do if (auto *C = getConstantAt(RetVal, RI, LVI)) { ++NumReturns; RI->replaceUsesOfWith(RetVal, C); BBChanged = true; } } } FnChanged |= BBChanged; } return FnChanged; } bool CorrelatedValuePropagation::runOnFunction(Function &F) { if (skipFunction(F)) return false; LazyValueInfo *LVI = &getAnalysis().getLVI(); DominatorTree *DT = &getAnalysis().getDomTree(); return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F)); } PreservedAnalyses CorrelatedValuePropagationPass::run(Function &F, FunctionAnalysisManager &AM) { LazyValueInfo *LVI = &AM.getResult(F); DominatorTree *DT = &AM.getResult(F); bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F)); if (!Changed) return PreservedAnalyses::all(); PreservedAnalyses PA; PA.preserve(); PA.preserve(); return PA; } diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll b/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll index db758b8459b7..9edf4789b8e4 100644 --- a/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll @@ -1,717 +1,726 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -S -correlated-propagation < %s | FileCheck %s ; Check that debug locations are preserved. For more info see: ; https://llvm.org/docs/SourceLevelDebugging.html#fixing-errors ; RUN: opt < %s -enable-debugify -correlated-propagation -S 2>&1 | \ ; RUN: FileCheck %s -check-prefix=DEBUG ; DEBUG: CheckModuleDebugify: PASS declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32) declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32) declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32) declare { i32, i1 } @llvm.umul.with.overflow.i32(i32, i32) declare void @llvm.trap() define i32 @signed_add(i32 %x, i32 %y) { ; CHECK-LABEL: @signed_add( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i32 [[Y:%.*]], 0 ; CHECK-NEXT: br i1 [[CMP]], label [[LAND_LHS_TRUE:%.*]], label [[LOR_LHS_FALSE:%.*]] ; CHECK: land.lhs.true: ; CHECK-NEXT: [[TMP0:%.*]] = sub nsw i32 2147483647, [[Y]] ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP3]], label [[TRAP:%.*]], label [[CONT:%.*]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cont: ; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[TMP4]], [[X:%.*]] ; CHECK-NEXT: br i1 [[CMP1]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: lor.lhs.false: ; CHECK-NEXT: [[CMP2:%.*]] = icmp slt i32 [[Y]], 0 ; CHECK-NEXT: br i1 [[CMP2]], label [[LAND_LHS_TRUE3:%.*]], label [[COND_FALSE]] ; CHECK: land.lhs.true3: ; CHECK-NEXT: [[TMP5:%.*]] = sub nsw i32 -2147483648, [[Y]] ; CHECK-NEXT: [[TMP6:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP5]], 0 ; CHECK-NEXT: [[TMP7:%.*]] = insertvalue { i32, i1 } [[TMP6]], i1 false, 1 ; CHECK-NEXT: [[TMP8:%.*]] = extractvalue { i32, i1 } [[TMP7]], 1 ; CHECK-NEXT: br i1 [[TMP8]], label [[TRAP]], label [[CONT4:%.*]] ; CHECK: cont4: ; CHECK-NEXT: [[TMP9:%.*]] = extractvalue { i32, i1 } [[TMP7]], 0 ; CHECK-NEXT: [[CMP5:%.*]] = icmp sgt i32 [[TMP9]], [[X]] ; CHECK-NEXT: br i1 [[CMP5]], label [[COND_END]], label [[COND_FALSE]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP10:%.*]] = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[X]], i32 [[Y]]) ; CHECK-NEXT: [[TMP11:%.*]] = extractvalue { i32, i1 } [[TMP10]], 0 ; CHECK-NEXT: [[TMP12:%.*]] = extractvalue { i32, i1 } [[TMP10]], 1 ; CHECK-NEXT: br i1 [[TMP12]], label [[TRAP]], label [[COND_END]] ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[CONT4]] ], [ 0, [[CONT]] ], [ [[TMP11]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp sgt i32 %y, 0 br i1 %cmp, label %land.lhs.true, label %lor.lhs.false land.lhs.true: ; preds = %entry %0 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 2147483647, i32 %y) %1 = extractvalue { i32, i1 } %0, 1 br i1 %1, label %trap, label %cont trap: ; preds = %land.lhs.true, %land.lhs.true3, %cond.false tail call void @llvm.trap() unreachable cont: ; preds = %land.lhs.true %2 = extractvalue { i32, i1 } %0, 0 %cmp1 = icmp slt i32 %2, %x br i1 %cmp1, label %cond.end, label %cond.false lor.lhs.false: ; preds = %entry %cmp2 = icmp slt i32 %y, 0 br i1 %cmp2, label %land.lhs.true3, label %cond.false land.lhs.true3: ; preds = %lor.lhs.false %3 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 -2147483648, i32 %y) %4 = extractvalue { i32, i1 } %3, 1 br i1 %4, label %trap, label %cont4 cont4: ; preds = %land.lhs.true3 %5 = extractvalue { i32, i1 } %3, 0 %cmp5 = icmp sgt i32 %5, %x br i1 %cmp5, label %cond.end, label %cond.false cond.false: ; preds = %cont, %cont4, %lor.lhs.false %6 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %x, i32 %y) %7 = extractvalue { i32, i1 } %6, 0 %8 = extractvalue { i32, i1 } %6, 1 br i1 %8, label %trap, label %cond.end cond.end: ; preds = %cond.false, %cont, %cont4 %cond = phi i32 [ 0, %cont4 ], [ 0, %cont ], [ %7, %cond.false ] ret i32 %cond } define i32 @unsigned_add(i32 %x, i32 %y) { ; CHECK-LABEL: @unsigned_add( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[TMP0:%.*]] = sub nuw i32 -1, [[Y:%.*]] ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP3]], label [[TRAP:%.*]], label [[CONT:%.*]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cont: ; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i32 [[TMP4]], [[X:%.*]] ; CHECK-NEXT: br i1 [[CMP1]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP5:%.*]] = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[X]], i32 [[Y]]) ; CHECK-NEXT: [[TMP6:%.*]] = extractvalue { i32, i1 } [[TMP5]], 0 ; CHECK-NEXT: [[TMP7:%.*]] = extractvalue { i32, i1 } [[TMP5]], 1 ; CHECK-NEXT: br i1 [[TMP7]], label [[TRAP]], label [[COND_END]] ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[CONT]] ], [ [[TMP6]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 -1, i32 %y) %1 = extractvalue { i32, i1 } %0, 1 br i1 %1, label %trap, label %cont trap: ; preds = %cond.false, %entry tail call void @llvm.trap() unreachable cont: ; preds = %entry %2 = extractvalue { i32, i1 } %0, 0 %cmp1 = icmp ult i32 %2, %x br i1 %cmp1, label %cond.end, label %cond.false cond.false: ; preds = %cont %3 = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 %y) %4 = extractvalue { i32, i1 } %3, 0 %5 = extractvalue { i32, i1 } %3, 1 br i1 %5, label %trap, label %cond.end cond.end: ; preds = %cond.false, %cont %cond = phi i32 [ 0, %cont ], [ %4, %cond.false ] ret i32 %cond } define i32 @signed_sub(i32 %x, i32 %y) { ; CHECK-LABEL: @signed_sub( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[Y:%.*]], 0 ; CHECK-NEXT: br i1 [[CMP]], label [[LAND_LHS_TRUE:%.*]], label [[LOR_LHS_FALSE:%.*]] ; CHECK: land.lhs.true: ; CHECK-NEXT: [[TMP0:%.*]] = add nsw i32 [[Y]], 2147483647 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP3]], label [[TRAP:%.*]], label [[CONT:%.*]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cont: ; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[TMP4]], [[X:%.*]] ; CHECK-NEXT: br i1 [[CMP1]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: lor.lhs.false: ; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[Y]], 0 ; CHECK-NEXT: br i1 [[CMP2]], label [[COND_FALSE]], label [[LAND_LHS_TRUE3:%.*]] ; CHECK: land.lhs.true3: ; CHECK-NEXT: [[TMP5:%.*]] = add nsw i32 [[Y]], -2147483648 ; CHECK-NEXT: [[TMP6:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP5]], 0 ; CHECK-NEXT: [[TMP7:%.*]] = insertvalue { i32, i1 } [[TMP6]], i1 false, 1 ; CHECK-NEXT: [[TMP8:%.*]] = extractvalue { i32, i1 } [[TMP7]], 1 ; CHECK-NEXT: br i1 [[TMP8]], label [[TRAP]], label [[CONT4:%.*]] ; CHECK: cont4: ; CHECK-NEXT: [[TMP9:%.*]] = extractvalue { i32, i1 } [[TMP7]], 0 ; CHECK-NEXT: [[CMP5:%.*]] = icmp sgt i32 [[TMP9]], [[X]] ; CHECK-NEXT: br i1 [[CMP5]], label [[COND_END]], label [[COND_FALSE]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP10:%.*]] = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 [[X]], i32 [[Y]]) ; CHECK-NEXT: [[TMP11:%.*]] = extractvalue { i32, i1 } [[TMP10]], 0 ; CHECK-NEXT: [[TMP12:%.*]] = extractvalue { i32, i1 } [[TMP10]], 1 ; CHECK-NEXT: br i1 [[TMP12]], label [[TRAP]], label [[COND_END]] ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[CONT4]] ], [ 0, [[CONT]] ], [ [[TMP11]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp slt i32 %y, 0 br i1 %cmp, label %land.lhs.true, label %lor.lhs.false land.lhs.true: ; preds = %entry %0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %y, i32 2147483647) %1 = extractvalue { i32, i1 } %0, 1 br i1 %1, label %trap, label %cont trap: ; preds = %land.lhs.true, %land.lhs.true3, %cond.false tail call void @llvm.trap() unreachable cont: ; preds = %land.lhs.true %2 = extractvalue { i32, i1 } %0, 0 %cmp1 = icmp slt i32 %2, %x br i1 %cmp1, label %cond.end, label %cond.false lor.lhs.false: ; preds = %entry %cmp2 = icmp eq i32 %y, 0 br i1 %cmp2, label %cond.false, label %land.lhs.true3 land.lhs.true3: ; preds = %lor.lhs.false %3 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %y, i32 -2147483648) %4 = extractvalue { i32, i1 } %3, 1 br i1 %4, label %trap, label %cont4 cont4: ; preds = %land.lhs.true3 %5 = extractvalue { i32, i1 } %3, 0 %cmp5 = icmp sgt i32 %5, %x br i1 %cmp5, label %cond.end, label %cond.false cond.false: ; preds = %lor.lhs.false, %cont, %cont4 %6 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %x, i32 %y) %7 = extractvalue { i32, i1 } %6, 0 %8 = extractvalue { i32, i1 } %6, 1 br i1 %8, label %trap, label %cond.end cond.end: ; preds = %cond.false, %cont, %cont4 %cond = phi i32 [ 0, %cont4 ], [ 0, %cont ], [ %7, %cond.false ] ret i32 %cond } define i32 @unsigned_sub(i32 %x, i32 %y) { ; CHECK-LABEL: @unsigned_sub( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP0:%.*]] = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[X]], i32 [[Y]]) ; CHECK-NEXT: [[TMP1:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = extractvalue { i32, i1 } [[TMP0]], 1 ; CHECK-NEXT: br i1 [[TMP2]], label [[TRAP:%.*]], label [[COND_END]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP1]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp ult i32 %x, %y br i1 %cmp, label %cond.end, label %cond.false cond.false: ; preds = %entry %0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %x, i32 %y) %1 = extractvalue { i32, i1 } %0, 0 %2 = extractvalue { i32, i1 } %0, 1 br i1 %2, label %trap, label %cond.end trap: ; preds = %cond.false tail call void @llvm.trap() unreachable cond.end: ; preds = %cond.false, %entry %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ] ret i32 %cond } define i32 @signed_add_r1(i32 %x) { ; CHECK-LABEL: @signed_add_r1( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 2147483647 ; CHECK-NEXT: br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP0:%.*]] = add nsw i32 [[X]], 1 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP4]], label [[TRAP:%.*]], label [[COND_END]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP3]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp eq i32 %x, 2147483647 br i1 %cmp, label %cond.end, label %cond.false cond.false: ; preds = %entry %0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %x, i32 1) %1 = extractvalue { i32, i1 } %0, 0 %2 = extractvalue { i32, i1 } %0, 1 br i1 %2, label %trap, label %cond.end trap: ; preds = %cond.false tail call void @llvm.trap() unreachable cond.end: ; preds = %cond.false, %entry %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ] ret i32 %cond } define i32 @unsigned_add_r1(i32 %x) { ; CHECK-LABEL: @unsigned_add_r1( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], -1 ; CHECK-NEXT: br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP0:%.*]] = add nuw i32 [[X]], 1 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP4]], label [[TRAP:%.*]], label [[COND_END]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP3]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp eq i32 %x, -1 br i1 %cmp, label %cond.end, label %cond.false cond.false: ; preds = %entry %0 = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 1) %1 = extractvalue { i32, i1 } %0, 0 %2 = extractvalue { i32, i1 } %0, 1 br i1 %2, label %trap, label %cond.end trap: ; preds = %cond.false tail call void @llvm.trap() unreachable cond.end: ; preds = %cond.false, %entry %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ] ret i32 %cond } define i32 @signed_sub_r1(i32 %x) { ; CHECK-LABEL: @signed_sub_r1( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], -2147483648 ; CHECK-NEXT: br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP0:%.*]] = sub nsw i32 [[X]], 1 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP4]], label [[TRAP:%.*]], label [[COND_END]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP3]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp eq i32 %x, -2147483648 br i1 %cmp, label %cond.end, label %cond.false cond.false: ; preds = %entry %0 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %x, i32 1) %1 = extractvalue { i32, i1 } %0, 0 %2 = extractvalue { i32, i1 } %0, 1 br i1 %2, label %trap, label %cond.end trap: ; preds = %cond.false tail call void @llvm.trap() unreachable cond.end: ; preds = %cond.false, %entry %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ] ret i32 %cond } define i32 @unsigned_sub_r1(i32 %x) { ; CHECK-LABEL: @unsigned_sub_r1( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 0 ; CHECK-NEXT: br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP0:%.*]] = sub nuw i32 [[X]], 1 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP4]], label [[TRAP:%.*]], label [[COND_END]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP3]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp eq i32 %x, 0 br i1 %cmp, label %cond.end, label %cond.false cond.false: ; preds = %entry %0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %x, i32 1) %1 = extractvalue { i32, i1 } %0, 0 %2 = extractvalue { i32, i1 } %0, 1 br i1 %2, label %trap, label %cond.end trap: ; preds = %cond.false tail call void @llvm.trap() unreachable cond.end: ; preds = %cond.false, %entry %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ] ret i32 %cond } define i32 @signed_add_rn1(i32 %x) { ; CHECK-LABEL: @signed_add_rn1( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], -2147483648 ; CHECK-NEXT: br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP0:%.*]] = add nsw i32 [[X]], -1 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP4]], label [[TRAP:%.*]], label [[COND_END]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP3]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp eq i32 %x, -2147483648 br i1 %cmp, label %cond.end, label %cond.false cond.false: ; preds = %entry %0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %x, i32 -1) %1 = extractvalue { i32, i1 } %0, 0 %2 = extractvalue { i32, i1 } %0, 1 br i1 %2, label %trap, label %cond.end trap: ; preds = %cond.false tail call void @llvm.trap() unreachable cond.end: ; preds = %cond.false, %entry %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ] ret i32 %cond } define i32 @signed_sub_rn1(i32 %x) { ; CHECK-LABEL: @signed_sub_rn1( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 2147483647 ; CHECK-NEXT: br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[TMP0:%.*]] = sub nsw i32 [[X]], -1 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP4]], label [[TRAP:%.*]], label [[COND_END]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP3]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp eq i32 %x, 2147483647 br i1 %cmp, label %cond.end, label %cond.false cond.false: ; preds = %entry %0 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %x, i32 -1) %1 = extractvalue { i32, i1 } %0, 0 %2 = extractvalue { i32, i1 } %0, 1 br i1 %2, label %trap, label %cond.end trap: ; preds = %cond.false tail call void @llvm.trap() unreachable cond.end: ; preds = %cond.false, %entry %cond = phi i32 [ 0, %entry ], [ %1, %cond.false ] ret i32 %cond } define i32 @unsigned_mul(i32 %x) { ; CHECK-LABEL: @unsigned_mul( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP:%.*]] = icmp ugt i32 [[X:%.*]], 10000 ; CHECK-NEXT: br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[MULO1:%.*]] = mul nuw i32 [[X]], 100 ; CHECK-NEXT: [[TMP0:%.*]] = insertvalue { i32, i1 } undef, i32 [[MULO1]], 0 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } [[TMP0]], i1 false, 1 ; CHECK-NEXT: [[RES:%.*]] = extractvalue { i32, i1 } [[TMP1]], 0 ; CHECK-NEXT: [[OV:%.*]] = extractvalue { i32, i1 } [[TMP1]], 1 ; CHECK-NEXT: br i1 [[OV]], label [[TRAP:%.*]], label [[COND_END]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[RES]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp = icmp ugt i32 %x, 10000 br i1 %cmp, label %cond.end, label %cond.false cond.false: ; preds = %entry %mulo = tail call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %x, i32 100) %res = extractvalue { i32, i1 } %mulo, 0 %ov = extractvalue { i32, i1 } %mulo, 1 br i1 %ov, label %trap, label %cond.end trap: ; preds = %cond.false tail call void @llvm.trap() unreachable cond.end: ; preds = %cond.false, %entry %cond = phi i32 [ 0, %entry ], [ %res, %cond.false ] ret i32 %cond } define i32 @signed_mul(i32 %x) { ; CHECK-LABEL: @signed_mul( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP1:%.*]] = icmp sgt i32 [[X:%.*]], 10000 ; CHECK-NEXT: [[CMP2:%.*]] = icmp slt i32 [[X]], -10000 ; CHECK-NEXT: [[CMP3:%.*]] = or i1 [[CMP1]], [[CMP2]] ; CHECK-NEXT: br i1 [[CMP3]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]] ; CHECK: cond.false: ; CHECK-NEXT: [[MULO1:%.*]] = mul nsw i32 [[X]], 100 ; CHECK-NEXT: [[TMP0:%.*]] = insertvalue { i32, i1 } undef, i32 [[MULO1]], 0 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } [[TMP0]], i1 false, 1 ; CHECK-NEXT: [[RES:%.*]] = extractvalue { i32, i1 } [[TMP1]], 0 ; CHECK-NEXT: [[OV:%.*]] = extractvalue { i32, i1 } [[TMP1]], 1 ; CHECK-NEXT: br i1 [[OV]], label [[TRAP:%.*]], label [[COND_END]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cond.end: ; CHECK-NEXT: [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[RES]], [[COND_FALSE]] ] ; CHECK-NEXT: ret i32 [[COND]] ; entry: %cmp1 = icmp sgt i32 %x, 10000 %cmp2 = icmp slt i32 %x, -10000 %cmp3 = or i1 %cmp1, %cmp2 br i1 %cmp3, label %cond.end, label %cond.false cond.false: ; preds = %entry %mulo = tail call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %x, i32 100) %res = extractvalue { i32, i1 } %mulo, 0 %ov = extractvalue { i32, i1 } %mulo, 1 br i1 %ov, label %trap, label %cond.end trap: ; preds = %cond.false tail call void @llvm.trap() unreachable cond.end: ; preds = %cond.false, %entry %cond = phi i32 [ 0, %entry ], [ %res, %cond.false ] ret i32 %cond } declare i32 @bar(i32) define void @unsigned_loop(i32 %i) { ; CHECK-LABEL: @unsigned_loop( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[CMP3:%.*]] = icmp eq i32 [[I:%.*]], 0 ; CHECK-NEXT: br i1 [[CMP3]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]] ; CHECK: while.body.preheader: ; CHECK-NEXT: br label [[WHILE_BODY:%.*]] ; CHECK: while.body: ; CHECK-NEXT: [[I_ADDR_04:%.*]] = phi i32 [ [[TMP4:%.*]], [[CONT:%.*]] ], [ [[I]], [[WHILE_BODY_PREHEADER]] ] ; CHECK-NEXT: [[CALL:%.*]] = tail call i32 @bar(i32 [[I_ADDR_04]]) ; CHECK-NEXT: [[TMP0:%.*]] = sub nuw i32 [[I_ADDR_04]], 1 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP3]], label [[TRAP:%.*]], label [[CONT]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cont: ; CHECK-NEXT: [[TMP4]] = extractvalue { i32, i1 } [[TMP2]], 0 ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[TMP4]], 0 ; CHECK-NEXT: br i1 [[CMP]], label [[WHILE_END]], label [[WHILE_BODY]] ; CHECK: while.end: ; CHECK-NEXT: ret void ; entry: %cmp3 = icmp eq i32 %i, 0 br i1 %cmp3, label %while.end, label %while.body.preheader while.body.preheader: ; preds = %entry br label %while.body while.body: ; preds = %while.body.preheader, %cont %i.addr.04 = phi i32 [ %2, %cont ], [ %i, %while.body.preheader ] %call = tail call i32 @bar(i32 %i.addr.04) %0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %i.addr.04, i32 1) %1 = extractvalue { i32, i1 } %0, 1 br i1 %1, label %trap, label %cont trap: ; preds = %while.body tail call void @llvm.trap() unreachable cont: ; preds = %while.body %2 = extractvalue { i32, i1 } %0, 0 %cmp = icmp eq i32 %2, 0 br i1 %cmp, label %while.end, label %while.body while.end: ; preds = %cont, %entry ret void } define void @intrinsic_into_phi(i32 %n) { ; CHECK-LABEL: @intrinsic_into_phi( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[CONT:%.*]] ; CHECK: for.cond: ; CHECK-NEXT: [[TMP0:%.*]] = add nsw i32 [[DOTLCSSA:%.*]], 1 ; CHECK-NEXT: [[TMP1:%.*]] = insertvalue { i32, i1 } undef, i32 [[TMP0]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = insertvalue { i32, i1 } [[TMP1]], i1 false, 1 ; CHECK-NEXT: [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP2]], 1 ; CHECK-NEXT: br i1 [[TMP3]], label [[TRAP:%.*]], label [[CONT]] ; CHECK: trap: ; CHECK-NEXT: tail call void @llvm.trap() ; CHECK-NEXT: unreachable ; CHECK: cont: ; CHECK-NEXT: [[TMP4:%.*]] = phi { i32, i1 } [ zeroinitializer, [[ENTRY:%.*]] ], [ [[TMP2]], [[FOR_COND:%.*]] ] ; CHECK-NEXT: [[TMP5:%.*]] = extractvalue { i32, i1 } [[TMP4]], 0 ; CHECK-NEXT: [[CALL9:%.*]] = tail call i32 @bar(i32 [[TMP5]]) ; CHECK-NEXT: [[TOBOOL10:%.*]] = icmp eq i32 [[CALL9]], 0 ; CHECK-NEXT: br i1 [[TOBOOL10]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]] ; CHECK: while.body.preheader: ; CHECK-NEXT: br label [[WHILE_BODY:%.*]] ; CHECK: while.cond: ; CHECK-NEXT: [[TMP6:%.*]] = extractvalue { i32, i1 } [[TMP8:%.*]], 0 ; CHECK-NEXT: [[CALL:%.*]] = tail call i32 @bar(i32 [[TMP6]]) ; CHECK-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[CALL]], 0 ; CHECK-NEXT: br i1 [[TOBOOL]], label [[WHILE_END]], label [[WHILE_BODY]] ; CHECK: while.body: ; CHECK-NEXT: [[TMP7:%.*]] = phi i32 [ [[TMP6]], [[WHILE_COND:%.*]] ], [ [[TMP5]], [[WHILE_BODY_PREHEADER]] ] ; CHECK-NEXT: [[TMP8]] = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[TMP7]], i32 1) ; CHECK-NEXT: [[TMP9:%.*]] = extractvalue { i32, i1 } [[TMP8]], 1 ; CHECK-NEXT: br i1 [[TMP9]], label [[TRAP]], label [[WHILE_COND]] ; CHECK: while.end: ; CHECK-NEXT: [[DOTLCSSA]] = phi i32 [ [[TMP5]], [[CONT]] ], [ [[TMP6]], [[WHILE_COND]] ] ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[DOTLCSSA]], [[N:%.*]] ; CHECK-NEXT: br i1 [[CMP]], label [[FOR_COND]], label [[CLEANUP2:%.*]] ; CHECK: cleanup2: ; CHECK-NEXT: ret void ; entry: br label %cont for.cond: ; preds = %while.end %0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %.lcssa, i32 1) %1 = extractvalue { i32, i1 } %0, 1 br i1 %1, label %trap, label %cont trap: ; preds = %for.cond, %while.body tail call void @llvm.trap() unreachable cont: ; preds = %entry, %for.cond %2 = phi { i32, i1 } [ zeroinitializer, %entry ], [ %0, %for.cond ] %3 = extractvalue { i32, i1 } %2, 0 %call9 = tail call i32 @bar(i32 %3) %tobool10 = icmp eq i32 %call9, 0 br i1 %tobool10, label %while.end, label %while.body.preheader while.body.preheader: ; preds = %cont br label %while.body while.cond: ; preds = %while.body %4 = extractvalue { i32, i1 } %6, 0 %call = tail call i32 @bar(i32 %4) %tobool = icmp eq i32 %call, 0 br i1 %tobool, label %while.end, label %while.body while.body: ; preds = %while.body.preheader, %while.cond %5 = phi i32 [ %4, %while.cond ], [ %3, %while.body.preheader ] %6 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %5, i32 1) %7 = extractvalue { i32, i1 } %6, 1 br i1 %7, label %trap, label %while.cond while.end: ; preds = %while.cond, %cont %.lcssa = phi i32 [ %3, %cont ], [ %4, %while.cond ] %cmp = icmp slt i32 %.lcssa, %n br i1 %cmp, label %for.cond, label %cleanup2 cleanup2: ; preds = %while.end ret void } + +define { i8, i1 } @signed_mul_constant_folding() { +; CHECK-LABEL: @signed_mul_constant_folding( +; CHECK-NEXT: ret { i8, i1 } { i8 2, i1 false } + %mul = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 1, i8 2) + ret { i8, i1 } %mul +} + +declare { i8, i1 } @llvm.umul.with.overflow.i8(i8, i8)