2133 lines · cpp
1//===-- ConstraintElimination.cpp - Eliminate conds using constraints. ----===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Eliminate conditions based on constraints collected from dominating10// conditions.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/Transforms/Scalar/ConstraintElimination.h"15#include "llvm/ADT/STLExtras.h"16#include "llvm/ADT/ScopeExit.h"17#include "llvm/ADT/SmallVector.h"18#include "llvm/ADT/Statistic.h"19#include "llvm/Analysis/ConstraintSystem.h"20#include "llvm/Analysis/GlobalsModRef.h"21#include "llvm/Analysis/LoopInfo.h"22#include "llvm/Analysis/MemoryBuiltins.h"23#include "llvm/Analysis/OptimizationRemarkEmitter.h"24#include "llvm/Analysis/ScalarEvolution.h"25#include "llvm/Analysis/ScalarEvolutionExpressions.h"26#include "llvm/Analysis/TargetLibraryInfo.h"27#include "llvm/Analysis/ValueTracking.h"28#include "llvm/IR/DataLayout.h"29#include "llvm/IR/DebugInfo.h"30#include "llvm/IR/Dominators.h"31#include "llvm/IR/Function.h"32#include "llvm/IR/IRBuilder.h"33#include "llvm/IR/InstrTypes.h"34#include "llvm/IR/Instructions.h"35#include "llvm/IR/Module.h"36#include "llvm/IR/PatternMatch.h"37#include "llvm/IR/Verifier.h"38#include "llvm/Pass.h"39#include "llvm/Support/CommandLine.h"40#include "llvm/Support/Debug.h"41#include "llvm/Support/DebugCounter.h"42#include "llvm/Support/MathExtras.h"43#include "llvm/Transforms/Utils/Cloning.h"44#include "llvm/Transforms/Utils/ValueMapper.h"45 46#include <optional>47#include <string>48 49using namespace llvm;50using namespace PatternMatch;51 52#define DEBUG_TYPE "constraint-elimination"53 54STATISTIC(NumCondsRemoved, "Number of instructions removed");55DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",56 "Controls which conditions are eliminated");57 58static cl::opt<unsigned>59 MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden,60 cl::desc("Maximum number of rows to keep in constraint system"));61 62static cl::opt<bool> DumpReproducers(63 "constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden,64 cl::desc("Dump IR to reproduce successful transformations."));65 66static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();67static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();68 69static Instruction *getContextInstForUse(Use &U) {70 Instruction *UserI = cast<Instruction>(U.getUser());71 if (auto *Phi = dyn_cast<PHINode>(UserI))72 UserI = Phi->getIncomingBlock(U)->getTerminator();73 return UserI;74}75 76namespace {77/// Struct to express a condition of the form %Op0 Pred %Op1.78struct ConditionTy {79 CmpPredicate Pred;80 Value *Op0 = nullptr;81 Value *Op1 = nullptr;82 83 ConditionTy() = default;84 ConditionTy(CmpPredicate Pred, Value *Op0, Value *Op1)85 : Pred(Pred), Op0(Op0), Op1(Op1) {}86};87 88/// Represents either89/// * a condition that holds on entry to a block (=condition fact)90/// * an assume (=assume fact)91/// * a use of a compare instruction to simplify.92/// It also tracks the Dominator DFS in and out numbers for each entry.93struct FactOrCheck {94 enum class EntryTy {95 ConditionFact, /// A condition that holds on entry to a block.96 InstFact, /// A fact that holds after Inst executed (e.g. an assume or97 /// min/mix intrinsic.98 InstCheck, /// An instruction to simplify (e.g. an overflow math99 /// intrinsics).100 UseCheck /// An use of a compare instruction to simplify.101 };102 103 union {104 Instruction *Inst;105 Use *U;106 ConditionTy Cond;107 };108 109 /// A pre-condition that must hold for the current fact to be added to the110 /// system.111 ConditionTy DoesHold;112 113 unsigned NumIn;114 unsigned NumOut;115 EntryTy Ty;116 117 FactOrCheck(EntryTy Ty, DomTreeNode *DTN, Instruction *Inst)118 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),119 Ty(Ty) {}120 121 FactOrCheck(DomTreeNode *DTN, Use *U)122 : U(U), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),123 Ty(EntryTy::UseCheck) {}124 125 FactOrCheck(DomTreeNode *DTN, CmpPredicate Pred, Value *Op0, Value *Op1,126 ConditionTy Precond = {})127 : Cond(Pred, Op0, Op1), DoesHold(Precond), NumIn(DTN->getDFSNumIn()),128 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {}129 130 static FactOrCheck getConditionFact(DomTreeNode *DTN, CmpPredicate Pred,131 Value *Op0, Value *Op1,132 ConditionTy Precond = {}) {133 return FactOrCheck(DTN, Pred, Op0, Op1, Precond);134 }135 136 static FactOrCheck getInstFact(DomTreeNode *DTN, Instruction *Inst) {137 return FactOrCheck(EntryTy::InstFact, DTN, Inst);138 }139 140 static FactOrCheck getCheck(DomTreeNode *DTN, Use *U) {141 return FactOrCheck(DTN, U);142 }143 144 static FactOrCheck getCheck(DomTreeNode *DTN, CallInst *CI) {145 return FactOrCheck(EntryTy::InstCheck, DTN, CI);146 }147 148 bool isCheck() const {149 return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;150 }151 152 Instruction *getContextInst() const {153 assert(!isConditionFact());154 if (Ty == EntryTy::UseCheck)155 return getContextInstForUse(*U);156 return Inst;157 }158 159 Instruction *getInstructionToSimplify() const {160 assert(isCheck());161 if (Ty == EntryTy::InstCheck)162 return Inst;163 // The use may have been simplified to a constant already.164 return dyn_cast<Instruction>(*U);165 }166 167 bool isConditionFact() const { return Ty == EntryTy::ConditionFact; }168};169 170/// Keep state required to build worklist.171struct State {172 DominatorTree &DT;173 LoopInfo &LI;174 ScalarEvolution &SE;175 TargetLibraryInfo &TLI;176 SmallVector<FactOrCheck, 64> WorkList;177 178 State(DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE,179 TargetLibraryInfo &TLI)180 : DT(DT), LI(LI), SE(SE), TLI(TLI) {}181 182 /// Process block \p BB and add known facts to work-list.183 void addInfoFor(BasicBlock &BB);184 185 /// Try to add facts for loop inductions (AddRecs) in EQ/NE compares186 /// controlling the loop header.187 void addInfoForInductions(BasicBlock &BB);188 189 /// Returns true if we can add a known condition from BB to its successor190 /// block Succ.191 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {192 return DT.dominates(BasicBlockEdge(&BB, Succ), Succ);193 }194};195 196class ConstraintInfo;197 198struct StackEntry {199 unsigned NumIn;200 unsigned NumOut;201 bool IsSigned = false;202 /// Variables that can be removed from the system once the stack entry gets203 /// removed.204 SmallVector<Value *, 2> ValuesToRelease;205 206 StackEntry(unsigned NumIn, unsigned NumOut, bool IsSigned,207 SmallVector<Value *, 2> ValuesToRelease)208 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),209 ValuesToRelease(std::move(ValuesToRelease)) {}210};211 212struct ConstraintTy {213 SmallVector<int64_t, 8> Coefficients;214 SmallVector<ConditionTy, 2> Preconditions;215 216 SmallVector<SmallVector<int64_t, 8>> ExtraInfo;217 218 bool IsSigned = false;219 220 ConstraintTy() = default;221 222 ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned, bool IsEq,223 bool IsNe)224 : Coefficients(std::move(Coefficients)), IsSigned(IsSigned), IsEq(IsEq),225 IsNe(IsNe) {}226 227 unsigned size() const { return Coefficients.size(); }228 229 unsigned empty() const { return Coefficients.empty(); }230 231 /// Returns true if all preconditions for this list of constraints are232 /// satisfied given \p Info.233 bool isValid(const ConstraintInfo &Info) const;234 235 bool isEq() const { return IsEq; }236 237 bool isNe() const { return IsNe; }238 239 /// Check if the current constraint is implied by the given ConstraintSystem.240 ///241 /// \return true or false if the constraint is proven to be respectively true,242 /// or false. When the constraint cannot be proven to be either true or false,243 /// std::nullopt is returned.244 std::optional<bool> isImpliedBy(const ConstraintSystem &CS) const;245 246private:247 bool IsEq = false;248 bool IsNe = false;249};250 251/// Wrapper encapsulating separate constraint systems and corresponding value252/// mappings for both unsigned and signed information. Facts are added to and253/// conditions are checked against the corresponding system depending on the254/// signed-ness of their predicates. While the information is kept separate255/// based on signed-ness, certain conditions can be transferred between the two256/// systems.257class ConstraintInfo {258 259 ConstraintSystem UnsignedCS;260 ConstraintSystem SignedCS;261 262 const DataLayout &DL;263 264public:265 ConstraintInfo(const DataLayout &DL, ArrayRef<Value *> FunctionArgs)266 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs), DL(DL) {267 auto &Value2Index = getValue2Index(false);268 // Add Arg > -1 constraints to unsigned system for all function arguments.269 for (Value *Arg : FunctionArgs) {270 ConstraintTy VarPos(SmallVector<int64_t, 8>(Value2Index.size() + 1, 0),271 false, false, false);272 VarPos.Coefficients[Value2Index[Arg]] = -1;273 UnsignedCS.addVariableRow(VarPos.Coefficients);274 }275 }276 277 DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {278 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();279 }280 const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {281 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();282 }283 284 ConstraintSystem &getCS(bool Signed) {285 return Signed ? SignedCS : UnsignedCS;286 }287 const ConstraintSystem &getCS(bool Signed) const {288 return Signed ? SignedCS : UnsignedCS;289 }290 291 void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }292 void popLastNVariables(bool Signed, unsigned N) {293 getCS(Signed).popLastNVariables(N);294 }295 296 bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const;297 298 void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,299 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack);300 301 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of302 /// constraints, using indices from the corresponding constraint system.303 /// New variables that need to be added to the system are collected in304 /// \p NewVariables.305 ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,306 SmallVectorImpl<Value *> &NewVariables,307 bool ForceSignedSystem = false) const;308 309 /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of310 /// constraints using getConstraint. Returns an empty constraint if the result311 /// cannot be used to query the existing constraint system, e.g. because it312 /// would require adding new variables. Also tries to convert signed313 /// predicates to unsigned ones if possible to allow using the unsigned system314 /// which increases the effectiveness of the signed <-> unsigned transfer315 /// logic.316 ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0,317 Value *Op1) const;318 319 /// Try to add information from \p A \p Pred \p B to the unsigned/signed320 /// system if \p Pred is signed/unsigned.321 void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,322 unsigned NumIn, unsigned NumOut,323 SmallVectorImpl<StackEntry> &DFSInStack);324 325private:326 /// Adds facts into constraint system. \p ForceSignedSystem can be set when327 /// the \p Pred is eq/ne, and signed constraint system is used when it's328 /// specified.329 void addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,330 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack,331 bool ForceSignedSystem);332};333 334/// Represents a (Coefficient * Variable) entry after IR decomposition.335struct DecompEntry {336 int64_t Coefficient;337 Value *Variable;338 /// True if the variable is known positive in the current constraint.339 bool IsKnownNonNegative;340 341 DecompEntry(int64_t Coefficient, Value *Variable,342 bool IsKnownNonNegative = false)343 : Coefficient(Coefficient), Variable(Variable),344 IsKnownNonNegative(IsKnownNonNegative) {}345};346 347/// Represents an Offset + Coefficient1 * Variable1 + ... decomposition.348struct Decomposition {349 int64_t Offset = 0;350 SmallVector<DecompEntry, 3> Vars;351 352 Decomposition(int64_t Offset) : Offset(Offset) {}353 Decomposition(Value *V, bool IsKnownNonNegative = false) {354 Vars.emplace_back(1, V, IsKnownNonNegative);355 }356 Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars)357 : Offset(Offset), Vars(Vars) {}358 359 /// Add \p OtherOffset and return true if the operation overflows, i.e. the360 /// new decomposition is invalid.361 [[nodiscard]] bool add(int64_t OtherOffset) {362 return AddOverflow(Offset, OtherOffset, Offset);363 }364 365 /// Add \p Other and return true if the operation overflows, i.e. the new366 /// decomposition is invalid.367 [[nodiscard]] bool add(const Decomposition &Other) {368 if (add(Other.Offset))369 return true;370 append_range(Vars, Other.Vars);371 return false;372 }373 374 /// Subtract \p Other and return true if the operation overflows, i.e. the new375 /// decomposition is invalid.376 [[nodiscard]] bool sub(const Decomposition &Other) {377 Decomposition Tmp = Other;378 if (Tmp.mul(-1))379 return true;380 if (add(Tmp.Offset))381 return true;382 append_range(Vars, Tmp.Vars);383 return false;384 }385 386 /// Multiply all coefficients by \p Factor and return true if the operation387 /// overflows, i.e. the new decomposition is invalid.388 [[nodiscard]] bool mul(int64_t Factor) {389 if (MulOverflow(Offset, Factor, Offset))390 return true;391 for (auto &Var : Vars)392 if (MulOverflow(Var.Coefficient, Factor, Var.Coefficient))393 return true;394 return false;395 }396};397 398// Variable and constant offsets for a chain of GEPs, with base pointer BasePtr.399struct OffsetResult {400 Value *BasePtr;401 APInt ConstantOffset;402 SmallMapVector<Value *, APInt, 4> VariableOffsets;403 GEPNoWrapFlags NW;404 405 OffsetResult() : BasePtr(nullptr), ConstantOffset(0, uint64_t(0)) {}406 407 OffsetResult(GEPOperator &GEP, const DataLayout &DL)408 : BasePtr(GEP.getPointerOperand()), NW(GEP.getNoWrapFlags()) {409 ConstantOffset = APInt(DL.getIndexTypeSizeInBits(BasePtr->getType()), 0);410 }411};412} // namespace413 414// Try to collect variable and constant offsets for \p GEP, partly traversing415// nested GEPs. Returns an OffsetResult with nullptr as BasePtr of collecting416// the offset fails.417static OffsetResult collectOffsets(GEPOperator &GEP, const DataLayout &DL) {418 OffsetResult Result(GEP, DL);419 unsigned BitWidth = Result.ConstantOffset.getBitWidth();420 if (!GEP.collectOffset(DL, BitWidth, Result.VariableOffsets,421 Result.ConstantOffset))422 return {};423 424 // If we have a nested GEP, check if we can combine the constant offset of the425 // inner GEP with the outer GEP.426 if (auto *InnerGEP = dyn_cast<GetElementPtrInst>(Result.BasePtr)) {427 SmallMapVector<Value *, APInt, 4> VariableOffsets2;428 APInt ConstantOffset2(BitWidth, 0);429 bool CanCollectInner = InnerGEP->collectOffset(430 DL, BitWidth, VariableOffsets2, ConstantOffset2);431 // TODO: Support cases with more than 1 variable offset.432 if (!CanCollectInner || Result.VariableOffsets.size() > 1 ||433 VariableOffsets2.size() > 1 ||434 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.size() >= 1)) {435 // More than 1 variable index, use outer result.436 return Result;437 }438 Result.BasePtr = InnerGEP->getPointerOperand();439 Result.ConstantOffset += ConstantOffset2;440 if (Result.VariableOffsets.size() == 0 && VariableOffsets2.size() == 1)441 Result.VariableOffsets = VariableOffsets2;442 Result.NW &= InnerGEP->getNoWrapFlags();443 }444 return Result;445}446 447static Decomposition decompose(Value *V,448 SmallVectorImpl<ConditionTy> &Preconditions,449 bool IsSigned, const DataLayout &DL);450 451static bool canUseSExt(ConstantInt *CI) {452 const APInt &Val = CI->getValue();453 return Val.sgt(MinSignedConstraintValue) && Val.slt(MaxConstraintValue);454}455 456static Decomposition decomposeGEP(GEPOperator &GEP,457 SmallVectorImpl<ConditionTy> &Preconditions,458 bool IsSigned, const DataLayout &DL) {459 // Do not reason about pointers where the index size is larger than 64 bits,460 // as the coefficients used to encode constraints are 64 bit integers.461 if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)462 return &GEP;463 464 assert(!IsSigned && "The logic below only supports decomposition for "465 "unsigned predicates at the moment.");466 const auto &[BasePtr, ConstantOffset, VariableOffsets, NW] =467 collectOffsets(GEP, DL);468 // We support either plain gep nuw, or gep nusw with non-negative offset,469 // which implies gep nuw.470 if (!BasePtr || NW == GEPNoWrapFlags::none())471 return &GEP;472 473 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr));474 for (auto [Index, Scale] : VariableOffsets) {475 auto IdxResult = decompose(Index, Preconditions, IsSigned, DL);476 if (IdxResult.mul(Scale.getSExtValue()))477 return &GEP;478 if (Result.add(IdxResult))479 return &GEP;480 481 if (!NW.hasNoUnsignedWrap()) {482 // Try to prove nuw from nusw and nneg.483 assert(NW.hasNoUnsignedSignedWrap() && "Must have nusw flag");484 if (!isKnownNonNegative(Index, DL))485 Preconditions.emplace_back(CmpInst::ICMP_SGE, Index,486 ConstantInt::get(Index->getType(), 0));487 }488 }489 return Result;490}491 492// Decomposes \p V into a constant offset + list of pairs { Coefficient,493// Variable } where Coefficient * Variable. The sum of the constant offset and494// pairs equals \p V.495static Decomposition decompose(Value *V,496 SmallVectorImpl<ConditionTy> &Preconditions,497 bool IsSigned, const DataLayout &DL) {498 499 auto MergeResults = [&Preconditions, IsSigned,500 &DL](Value *A, Value *B,501 bool IsSignedB) -> std::optional<Decomposition> {502 auto ResA = decompose(A, Preconditions, IsSigned, DL);503 auto ResB = decompose(B, Preconditions, IsSignedB, DL);504 if (ResA.add(ResB))505 return std::nullopt;506 return ResA;507 };508 509 Type *Ty = V->getType()->getScalarType();510 if (Ty->isPointerTy() && !IsSigned) {511 if (auto *GEP = dyn_cast<GEPOperator>(V))512 return decomposeGEP(*GEP, Preconditions, IsSigned, DL);513 if (isa<ConstantPointerNull>(V))514 return int64_t(0);515 516 return V;517 }518 519 // Don't handle integers > 64 bit. Our coefficients are 64-bit large, so520 // coefficient add/mul may wrap, while the operation in the full bit width521 // would not.522 if (!Ty->isIntegerTy() || Ty->getIntegerBitWidth() > 64)523 return V;524 525 bool IsKnownNonNegative = false;526 527 // Decompose \p V used with a signed predicate.528 if (IsSigned) {529 if (auto *CI = dyn_cast<ConstantInt>(V)) {530 if (canUseSExt(CI))531 return CI->getSExtValue();532 }533 Value *Op0;534 Value *Op1;535 536 if (match(V, m_SExt(m_Value(Op0))))537 V = Op0;538 else if (match(V, m_NNegZExt(m_Value(Op0)))) {539 V = Op0;540 IsKnownNonNegative = true;541 } else if (match(V, m_NSWTrunc(m_Value(Op0)))) {542 if (Op0->getType()->getScalarSizeInBits() <= 64)543 V = Op0;544 }545 546 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {547 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))548 return *Decomp;549 return {V, IsKnownNonNegative};550 }551 552 if (match(V, m_NSWSub(m_Value(Op0), m_Value(Op1)))) {553 auto ResA = decompose(Op0, Preconditions, IsSigned, DL);554 auto ResB = decompose(Op1, Preconditions, IsSigned, DL);555 if (!ResA.sub(ResB))556 return ResA;557 return {V, IsKnownNonNegative};558 }559 560 ConstantInt *CI;561 if (match(V, m_NSWMul(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI)) {562 auto Result = decompose(Op0, Preconditions, IsSigned, DL);563 if (!Result.mul(CI->getSExtValue()))564 return Result;565 return {V, IsKnownNonNegative};566 }567 568 // (shl nsw x, shift) is (mul nsw x, (1<<shift)), with the exception of569 // shift == bw-1.570 if (match(V, m_NSWShl(m_Value(Op0), m_ConstantInt(CI)))) {571 uint64_t Shift = CI->getValue().getLimitedValue();572 if (Shift < Ty->getIntegerBitWidth() - 1) {573 assert(Shift < 64 && "Would overflow");574 auto Result = decompose(Op0, Preconditions, IsSigned, DL);575 if (!Result.mul(int64_t(1) << Shift))576 return Result;577 return {V, IsKnownNonNegative};578 }579 }580 581 return {V, IsKnownNonNegative};582 }583 584 if (auto *CI = dyn_cast<ConstantInt>(V)) {585 if (CI->uge(MaxConstraintValue))586 return V;587 return int64_t(CI->getZExtValue());588 }589 590 Value *Op0;591 if (match(V, m_ZExt(m_Value(Op0)))) {592 IsKnownNonNegative = true;593 V = Op0;594 } else if (match(V, m_SExt(m_Value(Op0)))) {595 V = Op0;596 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,597 ConstantInt::get(Op0->getType(), 0));598 } else if (auto *Trunc = dyn_cast<TruncInst>(V)) {599 if (Trunc->getSrcTy()->getScalarSizeInBits() <= 64) {600 if (Trunc->hasNoUnsignedWrap() || Trunc->hasNoSignedWrap()) {601 V = Trunc->getOperand(0);602 if (!Trunc->hasNoUnsignedWrap())603 Preconditions.emplace_back(CmpInst::ICMP_SGE, V,604 ConstantInt::get(V->getType(), 0));605 }606 }607 }608 609 Value *Op1;610 ConstantInt *CI;611 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {612 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))613 return *Decomp;614 return {V, IsKnownNonNegative};615 }616 617 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&618 canUseSExt(CI)) {619 Preconditions.emplace_back(620 CmpInst::ICMP_UGE, Op0,621 ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));622 if (auto Decomp = MergeResults(Op0, CI, true))623 return *Decomp;624 return {V, IsKnownNonNegative};625 }626 627 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {628 if (!isKnownNonNegative(Op0, DL))629 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,630 ConstantInt::get(Op0->getType(), 0));631 if (!isKnownNonNegative(Op1, DL))632 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,633 ConstantInt::get(Op1->getType(), 0));634 635 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))636 return *Decomp;637 return {V, IsKnownNonNegative};638 }639 640 // Decompose or as an add if there are no common bits between the operands.641 if (match(V, m_DisjointOr(m_Value(Op0), m_ConstantInt(CI)))) {642 if (auto Decomp = MergeResults(Op0, CI, IsSigned))643 return *Decomp;644 return {V, IsKnownNonNegative};645 }646 647 if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {648 if (CI->getSExtValue() < 0 || CI->getSExtValue() >= 64)649 return {V, IsKnownNonNegative};650 auto Result = decompose(Op1, Preconditions, IsSigned, DL);651 if (!Result.mul(int64_t{1} << CI->getSExtValue()))652 return Result;653 return {V, IsKnownNonNegative};654 }655 656 if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&657 (!CI->isNegative())) {658 auto Result = decompose(Op1, Preconditions, IsSigned, DL);659 if (!Result.mul(CI->getSExtValue()))660 return Result;661 return {V, IsKnownNonNegative};662 }663 664 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) {665 auto ResA = decompose(Op0, Preconditions, IsSigned, DL);666 auto ResB = decompose(Op1, Preconditions, IsSigned, DL);667 if (!ResA.sub(ResB))668 return ResA;669 return {V, IsKnownNonNegative};670 }671 672 return {V, IsKnownNonNegative};673}674 675ConstraintTy676ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,677 SmallVectorImpl<Value *> &NewVariables,678 bool ForceSignedSystem) const {679 assert(NewVariables.empty() && "NewVariables must be empty when passed in");680 assert((!ForceSignedSystem || CmpInst::isEquality(Pred)) &&681 "signed system can only be forced on eq/ne");682 683 bool IsEq = false;684 bool IsNe = false;685 686 // Try to convert Pred to one of ULE/ULT/SLE/SLT.687 switch (Pred) {688 case CmpInst::ICMP_UGT:689 case CmpInst::ICMP_UGE:690 case CmpInst::ICMP_SGT:691 case CmpInst::ICMP_SGE: {692 Pred = CmpInst::getSwappedPredicate(Pred);693 std::swap(Op0, Op1);694 break;695 }696 case CmpInst::ICMP_EQ:697 if (!ForceSignedSystem && match(Op1, m_Zero())) {698 Pred = CmpInst::ICMP_ULE;699 } else {700 IsEq = true;701 Pred = CmpInst::ICMP_ULE;702 }703 break;704 case CmpInst::ICMP_NE:705 if (!ForceSignedSystem && match(Op1, m_Zero())) {706 Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT);707 std::swap(Op0, Op1);708 } else {709 IsNe = true;710 Pred = CmpInst::ICMP_ULE;711 }712 break;713 default:714 break;715 }716 717 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&718 Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)719 return {};720 721 SmallVector<ConditionTy, 4> Preconditions;722 bool IsSigned = ForceSignedSystem || CmpInst::isSigned(Pred);723 auto &Value2Index = getValue2Index(IsSigned);724 auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(),725 Preconditions, IsSigned, DL);726 auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(),727 Preconditions, IsSigned, DL);728 int64_t Offset1 = ADec.Offset;729 int64_t Offset2 = BDec.Offset;730 Offset1 *= -1;731 732 auto &VariablesA = ADec.Vars;733 auto &VariablesB = BDec.Vars;734 735 // First try to look up \p V in Value2Index and NewVariables. Otherwise add a736 // new entry to NewVariables.737 SmallDenseMap<Value *, unsigned> NewIndexMap;738 auto GetOrAddIndex = [&Value2Index, &NewVariables,739 &NewIndexMap](Value *V) -> unsigned {740 auto V2I = Value2Index.find(V);741 if (V2I != Value2Index.end())742 return V2I->second;743 auto Insert =744 NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1});745 if (Insert.second)746 NewVariables.push_back(V);747 return Insert.first->second;748 };749 750 // Make sure all variables have entries in Value2Index or NewVariables.751 for (const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))752 GetOrAddIndex(KV.Variable);753 754 // Build result constraint, by first adding all coefficients from A and then755 // subtracting all coefficients from B.756 ConstraintTy Res(757 SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0),758 IsSigned, IsEq, IsNe);759 // Collect variables that are known to be positive in all uses in the760 // constraint.761 SmallDenseMap<Value *, bool> KnownNonNegativeVariables;762 auto &R = Res.Coefficients;763 for (const auto &KV : VariablesA) {764 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;765 auto I =766 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});767 I.first->second &= KV.IsKnownNonNegative;768 }769 770 for (const auto &KV : VariablesB) {771 auto &Coeff = R[GetOrAddIndex(KV.Variable)];772 if (SubOverflow(Coeff, KV.Coefficient, Coeff))773 return {};774 auto I =775 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});776 I.first->second &= KV.IsKnownNonNegative;777 }778 779 int64_t OffsetSum;780 if (AddOverflow(Offset1, Offset2, OffsetSum))781 return {};782 if (Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT)783 if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum))784 return {};785 R[0] = OffsetSum;786 Res.Preconditions = std::move(Preconditions);787 788 // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new789 // variables.790 while (!NewVariables.empty()) {791 int64_t Last = R.back();792 if (Last != 0)793 break;794 R.pop_back();795 Value *RemovedV = NewVariables.pop_back_val();796 NewIndexMap.erase(RemovedV);797 }798 799 // Add extra constraints for variables that are known positive.800 for (auto &KV : KnownNonNegativeVariables) {801 if (!KV.second ||802 (!Value2Index.contains(KV.first) && !NewIndexMap.contains(KV.first)))803 continue;804 auto &C = Res.ExtraInfo.emplace_back(805 Value2Index.size() + NewVariables.size() + 1, 0);806 C[GetOrAddIndex(KV.first)] = -1;807 }808 return Res;809}810 811ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,812 Value *Op0,813 Value *Op1) const {814 Constant *NullC = Constant::getNullValue(Op0->getType());815 // Handle trivially true compares directly to avoid adding V UGE 0 constraints816 // for all variables in the unsigned system.817 if ((Pred == CmpInst::ICMP_ULE && Op0 == NullC) ||818 (Pred == CmpInst::ICMP_UGE && Op1 == NullC)) {819 auto &Value2Index = getValue2Index(false);820 // Return constraint that's trivially true.821 return ConstraintTy(SmallVector<int64_t, 8>(Value2Index.size(), 0), false,822 false, false);823 }824 825 // If both operands are known to be non-negative, change signed predicates to826 // unsigned ones. This increases the reasoning effectiveness in combination827 // with the signed <-> unsigned transfer logic.828 if (CmpInst::isSigned(Pred) &&829 isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&830 isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))831 Pred = ICmpInst::getUnsignedPredicate(Pred);832 833 SmallVector<Value *> NewVariables;834 ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables);835 if (!NewVariables.empty())836 return {};837 return R;838}839 840bool ConstraintTy::isValid(const ConstraintInfo &Info) const {841 return Coefficients.size() > 0 &&842 all_of(Preconditions, [&Info](const ConditionTy &C) {843 return Info.doesHold(C.Pred, C.Op0, C.Op1);844 });845}846 847std::optional<bool>848ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const {849 bool IsConditionImplied = CS.isConditionImplied(Coefficients);850 851 if (IsEq || IsNe) {852 auto NegatedOrEqual = ConstraintSystem::negateOrEqual(Coefficients);853 bool IsNegatedOrEqualImplied =854 !NegatedOrEqual.empty() && CS.isConditionImplied(NegatedOrEqual);855 856 // In order to check that `%a == %b` is true (equality), both conditions `%a857 // >= %b` and `%a <= %b` must hold true. When checking for equality (`IsEq`858 // is true), we return true if they both hold, false in the other cases.859 if (IsConditionImplied && IsNegatedOrEqualImplied)860 return IsEq;861 862 auto Negated = ConstraintSystem::negate(Coefficients);863 bool IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated);864 865 auto StrictLessThan = ConstraintSystem::toStrictLessThan(Coefficients);866 bool IsStrictLessThanImplied =867 !StrictLessThan.empty() && CS.isConditionImplied(StrictLessThan);868 869 // In order to check that `%a != %b` is true (non-equality), either870 // condition `%a > %b` or `%a < %b` must hold true. When checking for871 // non-equality (`IsNe` is true), we return true if one of the two holds,872 // false in the other cases.873 if (IsNegatedImplied || IsStrictLessThanImplied)874 return IsNe;875 876 return std::nullopt;877 }878 879 if (IsConditionImplied)880 return true;881 882 auto Negated = ConstraintSystem::negate(Coefficients);883 auto IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated);884 if (IsNegatedImplied)885 return false;886 887 // Neither the condition nor its negated holds, did not prove anything.888 return std::nullopt;889}890 891bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A,892 Value *B) const {893 auto R = getConstraintForSolving(Pred, A, B);894 return R.isValid(*this) &&895 getCS(R.IsSigned).isConditionImplied(R.Coefficients);896}897 898void ConstraintInfo::transferToOtherSystem(899 CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,900 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {901 auto IsKnownNonNegative = [this](Value *V) {902 return doesHold(CmpInst::ICMP_SGE, V, ConstantInt::get(V->getType(), 0)) ||903 isKnownNonNegative(V, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1);904 };905 // Check if we can combine facts from the signed and unsigned systems to906 // derive additional facts.907 if (!A->getType()->isIntegerTy())908 return;909 // FIXME: This currently depends on the order we add facts. Ideally we910 // would first add all known facts and only then try to add additional911 // facts.912 switch (Pred) {913 default:914 break;915 case CmpInst::ICMP_ULT:916 case CmpInst::ICMP_ULE:917 // If B is a signed positive constant, then A >=s 0 and A <s (or <=s) B.918 if (IsKnownNonNegative(B)) {919 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn,920 NumOut, DFSInStack);921 addFact(ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,922 DFSInStack);923 }924 break;925 case CmpInst::ICMP_UGE:926 case CmpInst::ICMP_UGT:927 // If A is a signed positive constant, then B >=s 0 and A >s (or >=s) B.928 if (IsKnownNonNegative(A)) {929 addFact(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0), NumIn,930 NumOut, DFSInStack);931 addFact(ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,932 DFSInStack);933 }934 break;935 case CmpInst::ICMP_SLT:936 if (IsKnownNonNegative(A))937 addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack);938 break;939 case CmpInst::ICMP_SGT: {940 if (doesHold(CmpInst::ICMP_SGE, B, Constant::getAllOnesValue(B->getType())))941 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn,942 NumOut, DFSInStack);943 if (IsKnownNonNegative(B))944 addFact(CmpInst::ICMP_UGT, A, B, NumIn, NumOut, DFSInStack);945 946 break;947 }948 case CmpInst::ICMP_SGE:949 if (IsKnownNonNegative(B))950 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);951 break;952 }953}954 955#ifndef NDEBUG956 957static void dumpConstraint(ArrayRef<int64_t> C,958 const DenseMap<Value *, unsigned> &Value2Index) {959 ConstraintSystem CS(Value2Index);960 CS.addVariableRowFill(C);961 CS.dump();962}963#endif964 965void State::addInfoForInductions(BasicBlock &BB) {966 auto *L = LI.getLoopFor(&BB);967 if (!L || L->getHeader() != &BB)968 return;969 970 Value *A;971 Value *B;972 CmpPredicate Pred;973 974 if (!match(BB.getTerminator(),975 m_Br(m_ICmp(Pred, m_Value(A), m_Value(B)), m_Value(), m_Value())))976 return;977 PHINode *PN = dyn_cast<PHINode>(A);978 if (!PN) {979 Pred = CmpInst::getSwappedPredicate(Pred);980 std::swap(A, B);981 PN = dyn_cast<PHINode>(A);982 }983 984 if (!PN || PN->getParent() != &BB || PN->getNumIncomingValues() != 2 ||985 !SE.isSCEVable(PN->getType()))986 return;987 988 BasicBlock *InLoopSucc = nullptr;989 if (Pred == CmpInst::ICMP_NE)990 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(0);991 else if (Pred == CmpInst::ICMP_EQ)992 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(1);993 else994 return;995 996 if (!L->contains(InLoopSucc) || !L->isLoopExiting(&BB) || InLoopSucc == &BB)997 return;998 999 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.getSCEV(PN));1000 BasicBlock *LoopPred = L->getLoopPredecessor();1001 if (!AR || AR->getLoop() != L || !LoopPred)1002 return;1003 1004 const SCEV *StartSCEV = AR->getStart();1005 Value *StartValue = nullptr;1006 if (auto *C = dyn_cast<SCEVConstant>(StartSCEV)) {1007 StartValue = C->getValue();1008 } else {1009 StartValue = PN->getIncomingValueForBlock(LoopPred);1010 assert(SE.getSCEV(StartValue) == StartSCEV && "inconsistent start value");1011 }1012 1013 DomTreeNode *DTN = DT.getNode(InLoopSucc);1014 auto IncUnsigned = SE.getMonotonicPredicateType(AR, CmpInst::ICMP_UGT);1015 auto IncSigned = SE.getMonotonicPredicateType(AR, CmpInst::ICMP_SGT);1016 bool MonotonicallyIncreasingUnsigned =1017 IncUnsigned == ScalarEvolution::MonotonicallyIncreasing;1018 bool MonotonicallyIncreasingSigned =1019 IncSigned == ScalarEvolution::MonotonicallyIncreasing;1020 // If SCEV guarantees that AR does not wrap, PN >= StartValue can be added1021 // unconditionally.1022 if (MonotonicallyIncreasingUnsigned)1023 WorkList.push_back(1024 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_UGE, PN, StartValue));1025 if (MonotonicallyIncreasingSigned)1026 WorkList.push_back(1027 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_SGE, PN, StartValue));1028 1029 APInt StepOffset;1030 if (auto *C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))1031 StepOffset = C->getAPInt();1032 else1033 return;1034 1035 // Make sure the bound B is loop-invariant.1036 if (!L->isLoopInvariant(B))1037 return;1038 1039 // Handle negative steps.1040 if (StepOffset.isNegative()) {1041 // TODO: Extend to allow steps > -1.1042 if (!(-StepOffset).isOne())1043 return;1044 1045 // AR may wrap.1046 // Add StartValue >= PN conditional on B <= StartValue which guarantees that1047 // the loop exits before wrapping with a step of -1.1048 WorkList.push_back(FactOrCheck::getConditionFact(1049 DTN, CmpInst::ICMP_UGE, StartValue, PN,1050 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));1051 WorkList.push_back(FactOrCheck::getConditionFact(1052 DTN, CmpInst::ICMP_SGE, StartValue, PN,1053 ConditionTy(CmpInst::ICMP_SLE, B, StartValue)));1054 // Add PN > B conditional on B <= StartValue which guarantees that the loop1055 // exits when reaching B with a step of -1.1056 WorkList.push_back(FactOrCheck::getConditionFact(1057 DTN, CmpInst::ICMP_UGT, PN, B,1058 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));1059 WorkList.push_back(FactOrCheck::getConditionFact(1060 DTN, CmpInst::ICMP_SGT, PN, B,1061 ConditionTy(CmpInst::ICMP_SLE, B, StartValue)));1062 return;1063 }1064 1065 // Make sure AR either steps by 1 or that the value we compare against is a1066 // GEP based on the same start value and all offsets are a multiple of the1067 // step size, to guarantee that the induction will reach the value.1068 if (StepOffset.isZero() || StepOffset.isNegative())1069 return;1070 1071 if (!StepOffset.isOne()) {1072 // Check whether B-Start is known to be a multiple of StepOffset.1073 const SCEV *BMinusStart = SE.getMinusSCEV(SE.getSCEV(B), StartSCEV);1074 if (isa<SCEVCouldNotCompute>(BMinusStart) ||1075 !SE.getConstantMultiple(BMinusStart).urem(StepOffset).isZero())1076 return;1077 }1078 1079 // AR may wrap. Add PN >= StartValue conditional on StartValue <= B which1080 // guarantees that the loop exits before wrapping in combination with the1081 // restrictions on B and the step above.1082 if (!MonotonicallyIncreasingUnsigned)1083 WorkList.push_back(FactOrCheck::getConditionFact(1084 DTN, CmpInst::ICMP_UGE, PN, StartValue,1085 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));1086 if (!MonotonicallyIncreasingSigned)1087 WorkList.push_back(FactOrCheck::getConditionFact(1088 DTN, CmpInst::ICMP_SGE, PN, StartValue,1089 ConditionTy(CmpInst::ICMP_SLE, StartValue, B)));1090 1091 WorkList.push_back(FactOrCheck::getConditionFact(1092 DTN, CmpInst::ICMP_ULT, PN, B,1093 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));1094 WorkList.push_back(FactOrCheck::getConditionFact(1095 DTN, CmpInst::ICMP_SLT, PN, B,1096 ConditionTy(CmpInst::ICMP_SLE, StartValue, B)));1097 1098 // Try to add condition from header to the dedicated exit blocks. When exiting1099 // either with EQ or NE in the header, we know that the induction value must1100 // be u<= B, as other exits may only exit earlier.1101 assert(!StepOffset.isNegative() && "induction must be increasing");1102 assert((Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) &&1103 "unsupported predicate");1104 ConditionTy Precond = {CmpInst::ICMP_ULE, StartValue, B};1105 SmallVector<BasicBlock *> ExitBBs;1106 L->getExitBlocks(ExitBBs);1107 for (BasicBlock *EB : ExitBBs) {1108 // Bail out on non-dedicated exits.1109 if (DT.dominates(&BB, EB)) {1110 WorkList.emplace_back(FactOrCheck::getConditionFact(1111 DT.getNode(EB), CmpInst::ICMP_ULE, A, B, Precond));1112 }1113 }1114}1115 1116static bool getConstraintFromMemoryAccess(GetElementPtrInst &GEP,1117 uint64_t AccessSize,1118 CmpPredicate &Pred, Value *&A,1119 Value *&B, const DataLayout &DL,1120 const TargetLibraryInfo &TLI) {1121 auto Offset = collectOffsets(cast<GEPOperator>(GEP), DL);1122 if (!Offset.NW.hasNoUnsignedWrap())1123 return false;1124 1125 if (Offset.VariableOffsets.size() != 1)1126 return false;1127 1128 uint64_t BitWidth = Offset.ConstantOffset.getBitWidth();1129 auto &[Index, Scale] = Offset.VariableOffsets.front();1130 // Bail out on non-canonical GEPs.1131 if (Index->getType()->getScalarSizeInBits() != BitWidth)1132 return false;1133 1134 ObjectSizeOpts Opts;1135 // Workaround for gep inbounds, ptr null, idx.1136 Opts.NullIsUnknownSize = true;1137 // Be conservative since we are not clear on whether an out of bounds access1138 // to the padding is UB or not.1139 Opts.RoundToAlign = true;1140 std::optional<TypeSize> Size =1141 getBaseObjectSize(Offset.BasePtr, DL, &TLI, Opts);1142 if (!Size || Size->isScalable())1143 return false;1144 1145 // Index * Scale + ConstOffset + AccessSize <= AllocSize1146 // With nuw flag, we know that the index addition doesn't have unsigned wrap.1147 // If (AllocSize - (ConstOffset + AccessSize)) wraps around, there is no valid1148 // value for Index.1149 APInt MaxIndex = (APInt(BitWidth, Size->getFixedValue() - AccessSize,1150 /*isSigned=*/false, /*implicitTrunc=*/true) -1151 Offset.ConstantOffset)1152 .udiv(Scale);1153 Pred = ICmpInst::ICMP_ULE;1154 A = Index;1155 B = ConstantInt::get(Index->getType(), MaxIndex);1156 return true;1157}1158 1159void State::addInfoFor(BasicBlock &BB) {1160 addInfoForInductions(BB);1161 auto &DL = BB.getDataLayout();1162 1163 // True as long as the current instruction is guaranteed to execute.1164 bool GuaranteedToExecute = true;1165 // Queue conditions and assumes.1166 for (Instruction &I : BB) {1167 if (auto *Cmp = dyn_cast<ICmpInst>(&I)) {1168 for (Use &U : Cmp->uses()) {1169 auto *UserI = getContextInstForUse(U);1170 auto *DTN = DT.getNode(UserI->getParent());1171 if (!DTN)1172 continue;1173 WorkList.push_back(FactOrCheck::getCheck(DTN, &U));1174 }1175 continue;1176 }1177 1178 auto AddFactFromMemoryAccess = [&](Value *Ptr, Type *AccessType) {1179 auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);1180 if (!GEP)1181 return;1182 TypeSize AccessSize = DL.getTypeStoreSize(AccessType);1183 if (!AccessSize.isFixed())1184 return;1185 if (GuaranteedToExecute) {1186 CmpPredicate Pred;1187 Value *A, *B;1188 if (getConstraintFromMemoryAccess(*GEP, AccessSize.getFixedValue(),1189 Pred, A, B, DL, TLI)) {1190 // The memory access is guaranteed to execute when BB is entered,1191 // hence the constraint holds on entry to BB.1192 WorkList.emplace_back(FactOrCheck::getConditionFact(1193 DT.getNode(I.getParent()), Pred, A, B));1194 }1195 } else {1196 WorkList.emplace_back(1197 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));1198 }1199 };1200 1201 if (auto *LI = dyn_cast<LoadInst>(&I)) {1202 if (!LI->isVolatile())1203 AddFactFromMemoryAccess(LI->getPointerOperand(), LI->getAccessType());1204 }1205 if (auto *SI = dyn_cast<StoreInst>(&I)) {1206 if (!SI->isVolatile())1207 AddFactFromMemoryAccess(SI->getPointerOperand(), SI->getAccessType());1208 }1209 1210 auto *II = dyn_cast<IntrinsicInst>(&I);1211 Intrinsic::ID ID = II ? II->getIntrinsicID() : Intrinsic::not_intrinsic;1212 switch (ID) {1213 case Intrinsic::assume: {1214 Value *A, *B;1215 CmpPredicate Pred;1216 if (!match(I.getOperand(0), m_ICmp(Pred, m_Value(A), m_Value(B))))1217 break;1218 if (GuaranteedToExecute) {1219 // The assume is guaranteed to execute when BB is entered, hence Cond1220 // holds on entry to BB.1221 WorkList.emplace_back(FactOrCheck::getConditionFact(1222 DT.getNode(I.getParent()), Pred, A, B));1223 } else {1224 WorkList.emplace_back(1225 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));1226 }1227 break;1228 }1229 // Enqueue ssub_with_overflow for simplification.1230 case Intrinsic::ssub_with_overflow:1231 case Intrinsic::ucmp:1232 case Intrinsic::scmp:1233 WorkList.push_back(1234 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));1235 break;1236 // Enqueue the intrinsics to add extra info.1237 case Intrinsic::umin:1238 case Intrinsic::umax:1239 case Intrinsic::smin:1240 case Intrinsic::smax:1241 // TODO: handle llvm.abs as well1242 WorkList.push_back(1243 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));1244 [[fallthrough]];1245 case Intrinsic::uadd_sat:1246 case Intrinsic::usub_sat:1247 // TODO: Check if it is possible to instead only added the min/max facts1248 // when simplifying uses of the min/max intrinsics.1249 if (!isGuaranteedNotToBePoison(&I))1250 break;1251 [[fallthrough]];1252 case Intrinsic::abs:1253 WorkList.push_back(FactOrCheck::getInstFact(DT.getNode(&BB), &I));1254 break;1255 }1256 1257 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);1258 }1259 1260 if (auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) {1261 for (auto &Case : Switch->cases()) {1262 BasicBlock *Succ = Case.getCaseSuccessor();1263 Value *V = Case.getCaseValue();1264 if (!canAddSuccessor(BB, Succ))1265 continue;1266 WorkList.emplace_back(FactOrCheck::getConditionFact(1267 DT.getNode(Succ), CmpInst::ICMP_EQ, Switch->getCondition(), V));1268 }1269 return;1270 }1271 1272 auto *Br = dyn_cast<BranchInst>(BB.getTerminator());1273 if (!Br || !Br->isConditional())1274 return;1275 1276 Value *Cond = Br->getCondition();1277 1278 // If the condition is a chain of ORs/AND and the successor only has the1279 // current block as predecessor, queue conditions for the successor.1280 Value *Op0, *Op1;1281 if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||1282 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {1283 bool IsOr = match(Cond, m_LogicalOr());1284 bool IsAnd = match(Cond, m_LogicalAnd());1285 // If there's a select that matches both AND and OR, we need to commit to1286 // one of the options. Arbitrarily pick OR.1287 if (IsOr && IsAnd)1288 IsAnd = false;1289 1290 BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0);1291 if (canAddSuccessor(BB, Successor)) {1292 SmallVector<Value *> CondWorkList;1293 SmallPtrSet<Value *, 8> SeenCond;1294 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {1295 if (SeenCond.insert(V).second)1296 CondWorkList.push_back(V);1297 };1298 QueueValue(Op1);1299 QueueValue(Op0);1300 while (!CondWorkList.empty()) {1301 Value *Cur = CondWorkList.pop_back_val();1302 if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) {1303 WorkList.emplace_back(FactOrCheck::getConditionFact(1304 DT.getNode(Successor),1305 IsOr ? Cmp->getInverseCmpPredicate() : Cmp->getCmpPredicate(),1306 Cmp->getOperand(0), Cmp->getOperand(1)));1307 continue;1308 }1309 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {1310 QueueValue(Op1);1311 QueueValue(Op0);1312 continue;1313 }1314 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {1315 QueueValue(Op1);1316 QueueValue(Op0);1317 continue;1318 }1319 }1320 }1321 return;1322 }1323 1324 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());1325 if (!CmpI)1326 return;1327 if (canAddSuccessor(BB, Br->getSuccessor(0)))1328 WorkList.emplace_back(FactOrCheck::getConditionFact(1329 DT.getNode(Br->getSuccessor(0)), CmpI->getCmpPredicate(),1330 CmpI->getOperand(0), CmpI->getOperand(1)));1331 if (canAddSuccessor(BB, Br->getSuccessor(1)))1332 WorkList.emplace_back(FactOrCheck::getConditionFact(1333 DT.getNode(Br->getSuccessor(1)), CmpI->getInverseCmpPredicate(),1334 CmpI->getOperand(0), CmpI->getOperand(1)));1335}1336 1337#ifndef NDEBUG1338static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred,1339 Value *LHS, Value *RHS) {1340 OS << "icmp " << Pred << ' ';1341 LHS->printAsOperand(OS, /*PrintType=*/true);1342 OS << ", ";1343 RHS->printAsOperand(OS, /*PrintType=*/false);1344}1345#endif1346 1347namespace {1348/// Helper to keep track of a condition and if it should be treated as negated1349/// for reproducer construction.1350/// Pred == Predicate::BAD_ICMP_PREDICATE indicates that this entry is a1351/// placeholder to keep the ReproducerCondStack in sync with DFSInStack.1352struct ReproducerEntry {1353 ICmpInst::Predicate Pred;1354 Value *LHS;1355 Value *RHS;1356 1357 ReproducerEntry(ICmpInst::Predicate Pred, Value *LHS, Value *RHS)1358 : Pred(Pred), LHS(LHS), RHS(RHS) {}1359};1360} // namespace1361 1362/// Helper function to generate a reproducer function for simplifying \p Cond.1363/// The reproducer function contains a series of @llvm.assume calls, one for1364/// each condition in \p Stack. For each condition, the operand instruction are1365/// cloned until we reach operands that have an entry in \p Value2Index. Those1366/// will then be added as function arguments. \p DT is used to order cloned1367/// instructions. The reproducer function will get added to \p M, if it is1368/// non-null. Otherwise no reproducer function is generated.1369static void generateReproducer(CmpInst *Cond, Module *M,1370 ArrayRef<ReproducerEntry> Stack,1371 ConstraintInfo &Info, DominatorTree &DT) {1372 if (!M)1373 return;1374 1375 LLVMContext &Ctx = Cond->getContext();1376 1377 LLVM_DEBUG(dbgs() << "Creating reproducer for " << *Cond << "\n");1378 1379 ValueToValueMapTy Old2New;1380 SmallVector<Value *> Args;1381 SmallPtrSet<Value *, 8> Seen;1382 // Traverse Cond and its operands recursively until we reach a value that's in1383 // Value2Index or not an instruction, or not a operation that1384 // ConstraintElimination can decompose. Such values will be considered as1385 // external inputs to the reproducer, they are collected and added as function1386 // arguments later.1387 auto CollectArguments = [&](ArrayRef<Value *> Ops, bool IsSigned) {1388 auto &Value2Index = Info.getValue2Index(IsSigned);1389 SmallVector<Value *, 4> WorkList(Ops);1390 while (!WorkList.empty()) {1391 Value *V = WorkList.pop_back_val();1392 if (!Seen.insert(V).second)1393 continue;1394 if (Old2New.find(V) != Old2New.end())1395 continue;1396 if (isa<Constant>(V))1397 continue;1398 1399 auto *I = dyn_cast<Instruction>(V);1400 if (Value2Index.contains(V) || !I ||1401 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {1402 Old2New[V] = V;1403 Args.push_back(V);1404 LLVM_DEBUG(dbgs() << " found external input " << *V << "\n");1405 } else {1406 append_range(WorkList, I->operands());1407 }1408 }1409 };1410 1411 for (auto &Entry : Stack)1412 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)1413 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred));1414 CollectArguments(Cond, ICmpInst::isSigned(Cond->getPredicate()));1415 1416 SmallVector<Type *> ParamTys;1417 for (auto *P : Args)1418 ParamTys.push_back(P->getType());1419 1420 FunctionType *FTy = FunctionType::get(Cond->getType(), ParamTys,1421 /*isVarArg=*/false);1422 Function *F = Function::Create(FTy, Function::ExternalLinkage,1423 Cond->getModule()->getName() +1424 Cond->getFunction()->getName() + "repro",1425 M);1426 // Add arguments to the reproducer function for each external value collected.1427 for (unsigned I = 0; I < Args.size(); ++I) {1428 F->getArg(I)->setName(Args[I]->getName());1429 Old2New[Args[I]] = F->getArg(I);1430 }1431 1432 BasicBlock *Entry = BasicBlock::Create(Ctx, "entry", F);1433 IRBuilder<> Builder(Entry);1434 Builder.CreateRet(Builder.getTrue());1435 Builder.SetInsertPoint(Entry->getTerminator());1436 1437 // Clone instructions in \p Ops and their operands recursively until reaching1438 // an value in Value2Index (external input to the reproducer). Update Old2New1439 // mapping for the original and cloned instructions. Sort instructions to1440 // clone by dominance, then insert the cloned instructions in the function.1441 auto CloneInstructions = [&](ArrayRef<Value *> Ops, bool IsSigned) {1442 SmallVector<Value *, 4> WorkList(Ops);1443 SmallVector<Instruction *> ToClone;1444 auto &Value2Index = Info.getValue2Index(IsSigned);1445 while (!WorkList.empty()) {1446 Value *V = WorkList.pop_back_val();1447 if (Old2New.find(V) != Old2New.end())1448 continue;1449 1450 auto *I = dyn_cast<Instruction>(V);1451 if (!Value2Index.contains(V) && I) {1452 Old2New[V] = nullptr;1453 ToClone.push_back(I);1454 append_range(WorkList, I->operands());1455 }1456 }1457 1458 sort(ToClone,1459 [&DT](Instruction *A, Instruction *B) { return DT.dominates(A, B); });1460 for (Instruction *I : ToClone) {1461 Instruction *Cloned = I->clone();1462 Old2New[I] = Cloned;1463 Old2New[I]->setName(I->getName());1464 Cloned->insertBefore(Builder.GetInsertPoint());1465 Cloned->dropUnknownNonDebugMetadata();1466 Cloned->setDebugLoc({});1467 }1468 };1469 1470 // Materialize the assumptions for the reproducer using the entries in Stack.1471 // That is, first clone the operands of the condition recursively until we1472 // reach an external input to the reproducer and add them to the reproducer1473 // function. Then add an ICmp for the condition (with the inverse predicate if1474 // the entry is negated) and an assert using the ICmp.1475 for (auto &Entry : Stack) {1476 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)1477 continue;1478 1479 LLVM_DEBUG(dbgs() << " Materializing assumption ";1480 dumpUnpackedICmp(dbgs(), Entry.Pred, Entry.LHS, Entry.RHS);1481 dbgs() << "\n");1482 CloneInstructions({Entry.LHS, Entry.RHS}, CmpInst::isSigned(Entry.Pred));1483 1484 auto *Cmp = Builder.CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);1485 Builder.CreateAssumption(Cmp);1486 }1487 1488 // Finally, clone the condition to reproduce and remap instruction operands in1489 // the reproducer using Old2New.1490 CloneInstructions(Cond, CmpInst::isSigned(Cond->getPredicate()));1491 Entry->getTerminator()->setOperand(0, Cond);1492 remapInstructionsInBlocks({Entry}, Old2New);1493 1494 assert(!verifyFunction(*F, &dbgs()));1495}1496 1497static std::optional<bool> checkCondition(CmpInst::Predicate Pred, Value *A,1498 Value *B, Instruction *CheckInst,1499 ConstraintInfo &Info) {1500 LLVM_DEBUG(dbgs() << "Checking " << *CheckInst << "\n");1501 1502 auto R = Info.getConstraintForSolving(Pred, A, B);1503 if (R.empty() || !R.isValid(Info)) {1504 LLVM_DEBUG(dbgs() << " failed to decompose condition\n");1505 return std::nullopt;1506 }1507 1508 auto &CSToUse = Info.getCS(R.IsSigned);1509 1510 // If there was extra information collected during decomposition, apply1511 // it now and remove it immediately once we are done with reasoning1512 // about the constraint.1513 for (auto &Row : R.ExtraInfo)1514 CSToUse.addVariableRow(Row);1515 auto InfoRestorer = make_scope_exit([&]() {1516 for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)1517 CSToUse.popLastConstraint();1518 });1519 1520 if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) {1521 if (!DebugCounter::shouldExecute(EliminatedCounter))1522 return std::nullopt;1523 1524 LLVM_DEBUG({1525 dbgs() << "Condition ";1526 dumpUnpackedICmp(1527 dbgs(), *ImpliedCondition ? Pred : CmpInst::getInversePredicate(Pred),1528 A, B);1529 dbgs() << " implied by dominating constraints\n";1530 CSToUse.dump();1531 });1532 return ImpliedCondition;1533 }1534 1535 return std::nullopt;1536}1537 1538static bool checkAndReplaceCondition(1539 ICmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,1540 Instruction *ContextInst, Module *ReproducerModule,1541 ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT,1542 SmallVectorImpl<Instruction *> &ToRemove) {1543 auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) {1544 generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);1545 Constant *ConstantC = ConstantInt::getBool(1546 CmpInst::makeCmpResultType(Cmp->getType()), IsTrue);1547 bool Changed = false;1548 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut, ContextInst,1549 &Changed](Use &U) {1550 auto *UserI = getContextInstForUse(U);1551 auto *DTN = DT.getNode(UserI->getParent());1552 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)1553 return false;1554 if (UserI->getParent() == ContextInst->getParent() &&1555 UserI->comesBefore(ContextInst))1556 return false;1557 1558 // Conditions in an assume trivially simplify to true. Skip uses1559 // in assume calls to not destroy the available information.1560 auto *II = dyn_cast<IntrinsicInst>(U.getUser());1561 bool ShouldReplace = !II || II->getIntrinsicID() != Intrinsic::assume;1562 Changed |= ShouldReplace;1563 return ShouldReplace;1564 });1565 NumCondsRemoved++;1566 1567 // Update the debug value records that satisfy the same condition used1568 // in replaceUsesWithIf.1569 SmallVector<DbgVariableRecord *> DVRUsers;1570 findDbgUsers(Cmp, DVRUsers);1571 1572 for (auto *DVR : DVRUsers) {1573 auto *DTN = DT.getNode(DVR->getParent());1574 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)1575 continue;1576 1577 auto *MarkedI = DVR->getInstruction();1578 if (MarkedI->getParent() == ContextInst->getParent() &&1579 MarkedI->comesBefore(ContextInst))1580 continue;1581 1582 DVR->replaceVariableLocationOp(Cmp, ConstantC);1583 }1584 1585 if (Cmp->use_empty())1586 ToRemove.push_back(Cmp);1587 1588 return Changed;1589 };1590 1591 if (auto ImpliedCondition =1592 checkCondition(Cmp->getPredicate(), Cmp->getOperand(0),1593 Cmp->getOperand(1), Cmp, Info))1594 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);1595 1596 // When the predicate is samesign and unsigned, we can also make use of the1597 // signed predicate information.1598 if (Cmp->hasSameSign() && Cmp->isUnsigned())1599 if (auto ImpliedCondition =1600 checkCondition(Cmp->getSignedPredicate(), Cmp->getOperand(0),1601 Cmp->getOperand(1), Cmp, Info))1602 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);1603 1604 return false;1605}1606 1607static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info,1608 SmallVectorImpl<Instruction *> &ToRemove) {1609 auto ReplaceMinMaxWithOperand = [&](MinMaxIntrinsic *MinMax, bool UseLHS) {1610 // TODO: generate reproducer for min/max.1611 MinMax->replaceAllUsesWith(MinMax->getOperand(UseLHS ? 0 : 1));1612 ToRemove.push_back(MinMax);1613 return true;1614 };1615 1616 ICmpInst::Predicate Pred =1617 ICmpInst::getNonStrictPredicate(MinMax->getPredicate());1618 if (auto ImpliedCondition = checkCondition(1619 Pred, MinMax->getOperand(0), MinMax->getOperand(1), MinMax, Info))1620 return ReplaceMinMaxWithOperand(MinMax, *ImpliedCondition);1621 if (auto ImpliedCondition = checkCondition(1622 Pred, MinMax->getOperand(1), MinMax->getOperand(0), MinMax, Info))1623 return ReplaceMinMaxWithOperand(MinMax, !*ImpliedCondition);1624 return false;1625}1626 1627static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info,1628 SmallVectorImpl<Instruction *> &ToRemove) {1629 Value *LHS = I->getOperand(0);1630 Value *RHS = I->getOperand(1);1631 if (checkCondition(I->getGTPredicate(), LHS, RHS, I, Info).value_or(false)) {1632 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 1));1633 ToRemove.push_back(I);1634 return true;1635 }1636 if (checkCondition(I->getLTPredicate(), LHS, RHS, I, Info).value_or(false)) {1637 I->replaceAllUsesWith(ConstantInt::getSigned(I->getType(), -1));1638 ToRemove.push_back(I);1639 return true;1640 }1641 if (checkCondition(ICmpInst::ICMP_EQ, LHS, RHS, I, Info).value_or(false)) {1642 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 0));1643 ToRemove.push_back(I);1644 return true;1645 }1646 return false;1647}1648 1649static void1650removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info,1651 Module *ReproducerModule,1652 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,1653 SmallVectorImpl<StackEntry> &DFSInStack) {1654 Info.popLastConstraint(E.IsSigned);1655 // Remove variables in the system that went out of scope.1656 auto &Mapping = Info.getValue2Index(E.IsSigned);1657 for (Value *V : E.ValuesToRelease)1658 Mapping.erase(V);1659 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());1660 DFSInStack.pop_back();1661 if (ReproducerModule)1662 ReproducerCondStack.pop_back();1663}1664 1665/// Check if either the first condition of an AND or OR is implied by the1666/// (negated in case of OR) second condition or vice versa.1667static bool checkOrAndOpImpliedByOther(1668 FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule,1669 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,1670 SmallVectorImpl<StackEntry> &DFSInStack,1671 SmallVectorImpl<Instruction *> &ToRemove) {1672 Instruction *JoinOp = CB.getContextInst();1673 if (JoinOp->use_empty())1674 return false;1675 1676 CmpInst *CmpToCheck = cast<CmpInst>(CB.getInstructionToSimplify());1677 unsigned OtherOpIdx = JoinOp->getOperand(0) == CmpToCheck ? 1 : 0;1678 1679 // Don't try to simplify the first condition of a select by the second, as1680 // this may make the select more poisonous than the original one.1681 // TODO: check if the first operand may be poison.1682 if (OtherOpIdx != 0 && isa<SelectInst>(JoinOp))1683 return false;1684 1685 unsigned OldSize = DFSInStack.size();1686 auto InfoRestorer = make_scope_exit([&]() {1687 // Remove entries again.1688 while (OldSize < DFSInStack.size()) {1689 StackEntry E = DFSInStack.back();1690 removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack,1691 DFSInStack);1692 }1693 });1694 bool IsOr = match(JoinOp, m_LogicalOr());1695 SmallVector<Value *, 4> Worklist({JoinOp->getOperand(OtherOpIdx)});1696 // Do a traversal of the AND/OR tree to add facts from leaf compares.1697 while (!Worklist.empty()) {1698 Value *Val = Worklist.pop_back_val();1699 Value *LHS, *RHS;1700 CmpPredicate Pred;1701 if (match(Val, m_ICmp(Pred, m_Value(LHS), m_Value(RHS)))) {1702 // For OR, check if the negated condition implies CmpToCheck.1703 if (IsOr)1704 Pred = CmpInst::getInversePredicate(Pred);1705 // Optimistically add fact from the other compares in the AND/OR.1706 Info.addFact(Pred, LHS, RHS, CB.NumIn, CB.NumOut, DFSInStack);1707 continue;1708 }1709 if (IsOr ? match(Val, m_LogicalOr(m_Value(LHS), m_Value(RHS)))1710 : match(Val, m_LogicalAnd(m_Value(LHS), m_Value(RHS)))) {1711 Worklist.push_back(LHS);1712 Worklist.push_back(RHS);1713 }1714 }1715 if (OldSize == DFSInStack.size())1716 return false;1717 1718 // Check if the second condition can be simplified now.1719 if (auto ImpliedCondition =1720 checkCondition(CmpToCheck->getPredicate(), CmpToCheck->getOperand(0),1721 CmpToCheck->getOperand(1), CmpToCheck, Info)) {1722 if (IsOr == *ImpliedCondition)1723 JoinOp->replaceAllUsesWith(1724 ConstantInt::getBool(JoinOp->getType(), *ImpliedCondition));1725 else1726 JoinOp->replaceAllUsesWith(JoinOp->getOperand(OtherOpIdx));1727 ToRemove.push_back(JoinOp);1728 return true;1729 }1730 1731 return false;1732}1733 1734void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,1735 unsigned NumIn, unsigned NumOut,1736 SmallVectorImpl<StackEntry> &DFSInStack) {1737 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, false);1738 // If the Pred is eq/ne, also add the fact to signed system.1739 if (CmpInst::isEquality(Pred))1740 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, true);1741}1742 1743void ConstraintInfo::addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B,1744 unsigned NumIn, unsigned NumOut,1745 SmallVectorImpl<StackEntry> &DFSInStack,1746 bool ForceSignedSystem) {1747 // If the constraint has a pre-condition, skip the constraint if it does not1748 // hold.1749 SmallVector<Value *> NewVariables;1750 auto R = getConstraint(Pred, A, B, NewVariables, ForceSignedSystem);1751 1752 // TODO: Support non-equality for facts as well.1753 if (!R.isValid(*this) || R.isNe())1754 return;1755 1756 LLVM_DEBUG(dbgs() << "Adding '"; dumpUnpackedICmp(dbgs(), Pred, A, B);1757 dbgs() << "'\n");1758 auto &CSToUse = getCS(R.IsSigned);1759 if (R.Coefficients.empty())1760 return;1761 1762 bool Added = CSToUse.addVariableRowFill(R.Coefficients);1763 if (!Added)1764 return;1765 1766 // If R has been added to the system, add the new variables and queue it for1767 // removal once it goes out-of-scope.1768 SmallVector<Value *, 2> ValuesToRelease;1769 auto &Value2Index = getValue2Index(R.IsSigned);1770 for (Value *V : NewVariables) {1771 Value2Index.insert({V, Value2Index.size() + 1});1772 ValuesToRelease.push_back(V);1773 }1774 1775 LLVM_DEBUG({1776 dbgs() << " constraint: ";1777 dumpConstraint(R.Coefficients, getValue2Index(R.IsSigned));1778 dbgs() << "\n";1779 });1780 1781 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,1782 std::move(ValuesToRelease));1783 1784 if (!R.IsSigned) {1785 for (Value *V : NewVariables) {1786 ConstraintTy VarPos(SmallVector<int64_t, 8>(Value2Index.size() + 1, 0),1787 false, false, false);1788 VarPos.Coefficients[Value2Index[V]] = -1;1789 CSToUse.addVariableRow(VarPos.Coefficients);1790 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,1791 SmallVector<Value *, 2>());1792 }1793 }1794 1795 if (R.isEq()) {1796 // Also add the inverted constraint for equality constraints.1797 for (auto &Coeff : R.Coefficients)1798 Coeff *= -1;1799 CSToUse.addVariableRowFill(R.Coefficients);1800 1801 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,1802 SmallVector<Value *, 2>());1803 }1804}1805 1806static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B,1807 SmallVectorImpl<Instruction *> &ToRemove) {1808 bool Changed = false;1809 IRBuilder<> Builder(II->getParent(), II->getIterator());1810 Value *Sub = nullptr;1811 for (User *U : make_early_inc_range(II->users())) {1812 if (match(U, m_ExtractValue<0>(m_Value()))) {1813 if (!Sub)1814 Sub = Builder.CreateSub(A, B);1815 U->replaceAllUsesWith(Sub);1816 Changed = true;1817 } else if (match(U, m_ExtractValue<1>(m_Value()))) {1818 U->replaceAllUsesWith(Builder.getFalse());1819 Changed = true;1820 } else1821 continue;1822 1823 if (U->use_empty()) {1824 auto *I = cast<Instruction>(U);1825 ToRemove.push_back(I);1826 I->setOperand(0, PoisonValue::get(II->getType()));1827 Changed = true;1828 }1829 }1830 1831 if (II->use_empty()) {1832 II->eraseFromParent();1833 Changed = true;1834 }1835 return Changed;1836}1837 1838static bool1839tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info,1840 SmallVectorImpl<Instruction *> &ToRemove) {1841 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,1842 ConstraintInfo &Info) {1843 auto R = Info.getConstraintForSolving(Pred, A, B);1844 if (R.size() < 2 || !R.isValid(Info))1845 return false;1846 1847 auto &CSToUse = Info.getCS(R.IsSigned);1848 return CSToUse.isConditionImplied(R.Coefficients);1849 };1850 1851 bool Changed = false;1852 if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {1853 // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and1854 // can be simplified to a regular sub.1855 Value *A = II->getArgOperand(0);1856 Value *B = II->getArgOperand(1);1857 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||1858 !DoesConditionHold(CmpInst::ICMP_SGE, B,1859 ConstantInt::get(A->getType(), 0), Info))1860 return false;1861 Changed = replaceSubOverflowUses(II, A, B, ToRemove);1862 }1863 return Changed;1864}1865 1866static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI,1867 ScalarEvolution &SE,1868 OptimizationRemarkEmitter &ORE,1869 TargetLibraryInfo &TLI) {1870 bool Changed = false;1871 DT.updateDFSNumbers();1872 SmallVector<Value *> FunctionArgs(llvm::make_pointer_range(F.args()));1873 ConstraintInfo Info(F.getDataLayout(), FunctionArgs);1874 State S(DT, LI, SE, TLI);1875 std::unique_ptr<Module> ReproducerModule(1876 DumpReproducers ? new Module(F.getName(), F.getContext()) : nullptr);1877 1878 // First, collect conditions implied by branches and blocks with their1879 // Dominator DFS in and out numbers.1880 for (BasicBlock &BB : F) {1881 if (!DT.getNode(&BB))1882 continue;1883 S.addInfoFor(BB);1884 }1885 1886 // Next, sort worklist by dominance, so that dominating conditions to check1887 // and facts come before conditions and facts dominated by them. If a1888 // condition to check and a fact have the same numbers, conditional facts come1889 // first. Assume facts and checks are ordered according to their relative1890 // order in the containing basic block. Also make sure conditions with1891 // constant operands come before conditions without constant operands. This1892 // increases the effectiveness of the current signed <-> unsigned fact1893 // transfer logic.1894 stable_sort(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {1895 auto HasNoConstOp = [](const FactOrCheck &B) {1896 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);1897 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);1898 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);1899 };1900 // If both entries have the same In numbers, conditional facts come first.1901 // Otherwise use the relative order in the basic block.1902 if (A.NumIn == B.NumIn) {1903 if (A.isConditionFact() && B.isConditionFact()) {1904 bool NoConstOpA = HasNoConstOp(A);1905 bool NoConstOpB = HasNoConstOp(B);1906 return NoConstOpA < NoConstOpB;1907 }1908 if (A.isConditionFact())1909 return true;1910 if (B.isConditionFact())1911 return false;1912 auto *InstA = A.getContextInst();1913 auto *InstB = B.getContextInst();1914 return InstA->comesBefore(InstB);1915 }1916 return A.NumIn < B.NumIn;1917 });1918 1919 SmallVector<Instruction *> ToRemove;1920 1921 // Finally, process ordered worklist and eliminate implied conditions.1922 SmallVector<StackEntry, 16> DFSInStack;1923 SmallVector<ReproducerEntry> ReproducerCondStack;1924 for (FactOrCheck &CB : S.WorkList) {1925 // First, pop entries from the stack that are out-of-scope for CB. Remove1926 // the corresponding entry from the constraint system.1927 while (!DFSInStack.empty()) {1928 auto &E = DFSInStack.back();1929 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut1930 << "\n");1931 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");1932 assert(E.NumIn <= CB.NumIn);1933 if (CB.NumOut <= E.NumOut)1934 break;1935 LLVM_DEBUG({1936 dbgs() << "Removing ";1937 dumpConstraint(Info.getCS(E.IsSigned).getLastConstraint(),1938 Info.getValue2Index(E.IsSigned));1939 dbgs() << "\n";1940 });1941 removeEntryFromStack(E, Info, ReproducerModule.get(), ReproducerCondStack,1942 DFSInStack);1943 }1944 1945 // For a block, check if any CmpInsts become known based on the current set1946 // of constraints.1947 if (CB.isCheck()) {1948 Instruction *Inst = CB.getInstructionToSimplify();1949 if (!Inst)1950 continue;1951 LLVM_DEBUG(dbgs() << "Processing condition to simplify: " << *Inst1952 << "\n");1953 if (auto *II = dyn_cast<WithOverflowInst>(Inst)) {1954 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);1955 } else if (auto *Cmp = dyn_cast<ICmpInst>(Inst)) {1956 bool Simplified = checkAndReplaceCondition(1957 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),1958 ReproducerModule.get(), ReproducerCondStack, S.DT, ToRemove);1959 if (!Simplified &&1960 match(CB.getContextInst(), m_LogicalOp(m_Value(), m_Value()))) {1961 Simplified = checkOrAndOpImpliedByOther(1962 CB, Info, ReproducerModule.get(), ReproducerCondStack, DFSInStack,1963 ToRemove);1964 }1965 Changed |= Simplified;1966 } else if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {1967 Changed |= checkAndReplaceMinMax(MinMax, Info, ToRemove);1968 } else if (auto *CmpIntr = dyn_cast<CmpIntrinsic>(Inst)) {1969 Changed |= checkAndReplaceCmp(CmpIntr, Info, ToRemove);1970 }1971 continue;1972 }1973 1974 auto AddFact = [&](CmpPredicate Pred, Value *A, Value *B) {1975 LLVM_DEBUG(dbgs() << "Processing fact to add to the system: ";1976 dumpUnpackedICmp(dbgs(), Pred, A, B); dbgs() << "\n");1977 if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {1978 LLVM_DEBUG(1979 dbgs()1980 << "Skip adding constraint because system has too many rows.\n");1981 return;1982 }1983 1984 Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);1985 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())1986 ReproducerCondStack.emplace_back(Pred, A, B);1987 1988 if (ICmpInst::isRelational(Pred)) {1989 // If samesign is present on the ICmp, simply flip the sign of the1990 // predicate, transferring the information from the signed system to the1991 // unsigned system, and viceversa.1992 if (Pred.hasSameSign())1993 Info.addFact(ICmpInst::getFlippedSignednessPredicate(Pred), A, B,1994 CB.NumIn, CB.NumOut, DFSInStack);1995 else1996 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut,1997 DFSInStack);1998 }1999 2000 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {2001 // Add dummy entries to ReproducerCondStack to keep it in sync with2002 // DFSInStack.2003 for (unsigned I = 0,2004 E = (DFSInStack.size() - ReproducerCondStack.size());2005 I < E; ++I) {2006 ReproducerCondStack.emplace_back(ICmpInst::BAD_ICMP_PREDICATE,2007 nullptr, nullptr);2008 }2009 }2010 };2011 2012 CmpPredicate Pred;2013 if (!CB.isConditionFact()) {2014 Value *X;2015 if (match(CB.Inst, m_Intrinsic<Intrinsic::abs>(m_Value(X)))) {2016 // If is_int_min_poison is true then we may assume llvm.abs >= 0.2017 if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())2018 AddFact(CmpInst::ICMP_SGE, CB.Inst,2019 ConstantInt::get(CB.Inst->getType(), 0));2020 AddFact(CmpInst::ICMP_SGE, CB.Inst, X);2021 continue;2022 }2023 2024 if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {2025 Pred = ICmpInst::getNonStrictPredicate(MinMax->getPredicate());2026 AddFact(Pred, MinMax, MinMax->getLHS());2027 AddFact(Pred, MinMax, MinMax->getRHS());2028 continue;2029 }2030 if (auto *USatI = dyn_cast<SaturatingInst>(CB.Inst)) {2031 switch (USatI->getIntrinsicID()) {2032 default:2033 llvm_unreachable("Unexpected intrinsic.");2034 case Intrinsic::uadd_sat:2035 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getLHS());2036 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getRHS());2037 break;2038 case Intrinsic::usub_sat:2039 AddFact(ICmpInst::ICMP_ULE, USatI, USatI->getLHS());2040 break;2041 }2042 continue;2043 }2044 2045 auto &DL = F.getDataLayout();2046 auto AddFactsAboutIndices = [&](Value *Ptr, Type *AccessType) {2047 CmpPredicate Pred;2048 Value *A, *B;2049 if (getConstraintFromMemoryAccess(2050 *cast<GetElementPtrInst>(Ptr),2051 DL.getTypeStoreSize(AccessType).getFixedValue(), Pred, A, B, DL,2052 TLI))2053 AddFact(Pred, A, B);2054 };2055 2056 if (auto *LI = dyn_cast<LoadInst>(CB.Inst)) {2057 AddFactsAboutIndices(LI->getPointerOperand(), LI->getAccessType());2058 continue;2059 }2060 if (auto *SI = dyn_cast<StoreInst>(CB.Inst)) {2061 AddFactsAboutIndices(SI->getPointerOperand(), SI->getAccessType());2062 continue;2063 }2064 }2065 2066 Value *A = nullptr, *B = nullptr;2067 if (CB.isConditionFact()) {2068 Pred = CB.Cond.Pred;2069 A = CB.Cond.Op0;2070 B = CB.Cond.Op1;2071 if (CB.DoesHold.Pred != CmpInst::BAD_ICMP_PREDICATE &&2072 !Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) {2073 LLVM_DEBUG({2074 dbgs() << "Not adding fact ";2075 dumpUnpackedICmp(dbgs(), Pred, A, B);2076 dbgs() << " because precondition ";2077 dumpUnpackedICmp(dbgs(), CB.DoesHold.Pred, CB.DoesHold.Op0,2078 CB.DoesHold.Op1);2079 dbgs() << " does not hold.\n";2080 });2081 continue;2082 }2083 } else {2084 bool Matched = match(CB.Inst, m_Intrinsic<Intrinsic::assume>(2085 m_ICmp(Pred, m_Value(A), m_Value(B))));2086 (void)Matched;2087 assert(Matched && "Must have an assume intrinsic with a icmp operand");2088 }2089 AddFact(Pred, A, B);2090 }2091 2092 if (ReproducerModule && !ReproducerModule->functions().empty()) {2093 std::string S;2094 raw_string_ostream StringS(S);2095 ReproducerModule->print(StringS, nullptr);2096 OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);2097 Rem << ore::NV("module") << S;2098 ORE.emit(Rem);2099 }2100 2101#ifndef NDEBUG2102 unsigned SignedEntries =2103 count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });2104 assert(Info.getCS(false).size() - FunctionArgs.size() ==2105 DFSInStack.size() - SignedEntries &&2106 "updates to CS and DFSInStack are out of sync");2107 assert(Info.getCS(true).size() == SignedEntries &&2108 "updates to CS and DFSInStack are out of sync");2109#endif2110 2111 for (Instruction *I : ToRemove)2112 I->eraseFromParent();2113 return Changed;2114}2115 2116PreservedAnalyses ConstraintEliminationPass::run(Function &F,2117 FunctionAnalysisManager &AM) {2118 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);2119 auto &LI = AM.getResult<LoopAnalysis>(F);2120 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);2121 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);2122 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);2123 if (!eliminateConstraints(F, DT, LI, SE, ORE, TLI))2124 return PreservedAnalyses::all();2125 2126 PreservedAnalyses PA;2127 PA.preserve<DominatorTreeAnalysis>();2128 PA.preserve<LoopAnalysis>();2129 PA.preserve<ScalarEvolutionAnalysis>();2130 PA.preserveSet<CFGAnalyses>();2131 return PA;2132}2133