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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Eliminate conditions based on constraints collected from dominating 10 // 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/OptimizationRemarkEmitter.h" 23 #include "llvm/Analysis/ScalarEvolution.h" 24 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 25 #include "llvm/Analysis/ValueTracking.h" 26 #include "llvm/IR/DataLayout.h" 27 #include "llvm/IR/Dominators.h" 28 #include "llvm/IR/Function.h" 29 #include "llvm/IR/IRBuilder.h" 30 #include "llvm/IR/InstrTypes.h" 31 #include "llvm/IR/Instructions.h" 32 #include "llvm/IR/PatternMatch.h" 33 #include "llvm/IR/Verifier.h" 34 #include "llvm/Pass.h" 35 #include "llvm/Support/CommandLine.h" 36 #include "llvm/Support/Debug.h" 37 #include "llvm/Support/DebugCounter.h" 38 #include "llvm/Support/MathExtras.h" 39 #include "llvm/Transforms/Utils/Cloning.h" 40 #include "llvm/Transforms/Utils/ValueMapper.h" 41 42 #include <cmath> 43 #include <optional> 44 #include <string> 45 46 using namespace llvm; 47 using namespace PatternMatch; 48 49 #define DEBUG_TYPE "constraint-elimination" 50 51 STATISTIC(NumCondsRemoved, "Number of instructions removed"); 52 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated", 53 "Controls which conditions are eliminated"); 54 55 static cl::opt<unsigned> 56 MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden, 57 cl::desc("Maximum number of rows to keep in constraint system")); 58 59 static cl::opt<bool> DumpReproducers( 60 "constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, 61 cl::desc("Dump IR to reproduce successful transformations.")); 62 63 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max(); 64 static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min(); 65 66 // A helper to multiply 2 signed integers where overflowing is allowed. 67 static int64_t multiplyWithOverflow(int64_t A, int64_t B) { 68 int64_t Result; 69 MulOverflow(A, B, Result); 70 return Result; 71 } 72 73 // A helper to add 2 signed integers where overflowing is allowed. 74 static int64_t addWithOverflow(int64_t A, int64_t B) { 75 int64_t Result; 76 AddOverflow(A, B, Result); 77 return Result; 78 } 79 80 static Instruction *getContextInstForUse(Use &U) { 81 Instruction *UserI = cast<Instruction>(U.getUser()); 82 if (auto *Phi = dyn_cast<PHINode>(UserI)) 83 UserI = Phi->getIncomingBlock(U)->getTerminator(); 84 return UserI; 85 } 86 87 namespace { 88 /// Struct to express a condition of the form %Op0 Pred %Op1. 89 struct ConditionTy { 90 CmpInst::Predicate Pred; 91 Value *Op0; 92 Value *Op1; 93 94 ConditionTy() 95 : Pred(CmpInst::BAD_ICMP_PREDICATE), Op0(nullptr), Op1(nullptr) {} 96 ConditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1) 97 : Pred(Pred), Op0(Op0), Op1(Op1) {} 98 }; 99 100 /// Represents either 101 /// * a condition that holds on entry to a block (=condition fact) 102 /// * an assume (=assume fact) 103 /// * a use of a compare instruction to simplify. 104 /// It also tracks the Dominator DFS in and out numbers for each entry. 105 struct FactOrCheck { 106 enum class EntryTy { 107 ConditionFact, /// A condition that holds on entry to a block. 108 InstFact, /// A fact that holds after Inst executed (e.g. an assume or 109 /// min/mix intrinsic. 110 InstCheck, /// An instruction to simplify (e.g. an overflow math 111 /// intrinsics). 112 UseCheck /// An use of a compare instruction to simplify. 113 }; 114 115 union { 116 Instruction *Inst; 117 Use *U; 118 ConditionTy Cond; 119 }; 120 121 /// A pre-condition that must hold for the current fact to be added to the 122 /// system. 123 ConditionTy DoesHold; 124 125 unsigned NumIn; 126 unsigned NumOut; 127 EntryTy Ty; 128 129 FactOrCheck(EntryTy Ty, DomTreeNode *DTN, Instruction *Inst) 130 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), 131 Ty(Ty) {} 132 133 FactOrCheck(DomTreeNode *DTN, Use *U) 134 : U(U), DoesHold(CmpInst::BAD_ICMP_PREDICATE, nullptr, nullptr), 135 NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), 136 Ty(EntryTy::UseCheck) {} 137 138 FactOrCheck(DomTreeNode *DTN, CmpInst::Predicate Pred, Value *Op0, Value *Op1, 139 ConditionTy Precond = ConditionTy()) 140 : Cond(Pred, Op0, Op1), DoesHold(Precond), NumIn(DTN->getDFSNumIn()), 141 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {} 142 143 static FactOrCheck getConditionFact(DomTreeNode *DTN, CmpInst::Predicate Pred, 144 Value *Op0, Value *Op1, 145 ConditionTy Precond = ConditionTy()) { 146 return FactOrCheck(DTN, Pred, Op0, Op1, Precond); 147 } 148 149 static FactOrCheck getInstFact(DomTreeNode *DTN, Instruction *Inst) { 150 return FactOrCheck(EntryTy::InstFact, DTN, Inst); 151 } 152 153 static FactOrCheck getCheck(DomTreeNode *DTN, Use *U) { 154 return FactOrCheck(DTN, U); 155 } 156 157 static FactOrCheck getCheck(DomTreeNode *DTN, CallInst *CI) { 158 return FactOrCheck(EntryTy::InstCheck, DTN, CI); 159 } 160 161 bool isCheck() const { 162 return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck; 163 } 164 165 Instruction *getContextInst() const { 166 if (Ty == EntryTy::UseCheck) 167 return getContextInstForUse(*U); 168 return Inst; 169 } 170 171 Instruction *getInstructionToSimplify() const { 172 assert(isCheck()); 173 if (Ty == EntryTy::InstCheck) 174 return Inst; 175 // The use may have been simplified to a constant already. 176 return dyn_cast<Instruction>(*U); 177 } 178 179 bool isConditionFact() const { return Ty == EntryTy::ConditionFact; } 180 }; 181 182 /// Keep state required to build worklist. 183 struct State { 184 DominatorTree &DT; 185 LoopInfo &LI; 186 ScalarEvolution &SE; 187 SmallVector<FactOrCheck, 64> WorkList; 188 189 State(DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE) 190 : DT(DT), LI(LI), SE(SE) {} 191 192 /// Process block \p BB and add known facts to work-list. 193 void addInfoFor(BasicBlock &BB); 194 195 /// Try to add facts for loop inductions (AddRecs) in EQ/NE compares 196 /// controlling the loop header. 197 void addInfoForInductions(BasicBlock &BB); 198 199 /// Returns true if we can add a known condition from BB to its successor 200 /// block Succ. 201 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const { 202 return DT.dominates(BasicBlockEdge(&BB, Succ), Succ); 203 } 204 }; 205 206 class ConstraintInfo; 207 208 struct StackEntry { 209 unsigned NumIn; 210 unsigned NumOut; 211 bool IsSigned = false; 212 /// Variables that can be removed from the system once the stack entry gets 213 /// removed. 214 SmallVector<Value *, 2> ValuesToRelease; 215 216 StackEntry(unsigned NumIn, unsigned NumOut, bool IsSigned, 217 SmallVector<Value *, 2> ValuesToRelease) 218 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned), 219 ValuesToRelease(ValuesToRelease) {} 220 }; 221 222 struct ConstraintTy { 223 SmallVector<int64_t, 8> Coefficients; 224 SmallVector<ConditionTy, 2> Preconditions; 225 226 SmallVector<SmallVector<int64_t, 8>> ExtraInfo; 227 228 bool IsSigned = false; 229 230 ConstraintTy() = default; 231 232 ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned, bool IsEq, 233 bool IsNe) 234 : Coefficients(Coefficients), IsSigned(IsSigned), IsEq(IsEq), IsNe(IsNe) { 235 } 236 237 unsigned size() const { return Coefficients.size(); } 238 239 unsigned empty() const { return Coefficients.empty(); } 240 241 /// Returns true if all preconditions for this list of constraints are 242 /// satisfied given \p CS and the corresponding \p Value2Index mapping. 243 bool isValid(const ConstraintInfo &Info) const; 244 245 bool isEq() const { return IsEq; } 246 247 bool isNe() const { return IsNe; } 248 249 /// Check if the current constraint is implied by the given ConstraintSystem. 250 /// 251 /// \return true or false if the constraint is proven to be respectively true, 252 /// or false. When the constraint cannot be proven to be either true or false, 253 /// std::nullopt is returned. 254 std::optional<bool> isImpliedBy(const ConstraintSystem &CS) const; 255 256 private: 257 bool IsEq = false; 258 bool IsNe = false; 259 }; 260 261 /// Wrapper encapsulating separate constraint systems and corresponding value 262 /// mappings for both unsigned and signed information. Facts are added to and 263 /// conditions are checked against the corresponding system depending on the 264 /// signed-ness of their predicates. While the information is kept separate 265 /// based on signed-ness, certain conditions can be transferred between the two 266 /// systems. 267 class ConstraintInfo { 268 269 ConstraintSystem UnsignedCS; 270 ConstraintSystem SignedCS; 271 272 const DataLayout &DL; 273 274 public: 275 ConstraintInfo(const DataLayout &DL, ArrayRef<Value *> FunctionArgs) 276 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs), DL(DL) { 277 auto &Value2Index = getValue2Index(false); 278 // Add Arg > -1 constraints to unsigned system for all function arguments. 279 for (Value *Arg : FunctionArgs) { 280 ConstraintTy VarPos(SmallVector<int64_t, 8>(Value2Index.size() + 1, 0), 281 false, false, false); 282 VarPos.Coefficients[Value2Index[Arg]] = -1; 283 UnsignedCS.addVariableRow(VarPos.Coefficients); 284 } 285 } 286 287 DenseMap<Value *, unsigned> &getValue2Index(bool Signed) { 288 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index(); 289 } 290 const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const { 291 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index(); 292 } 293 294 ConstraintSystem &getCS(bool Signed) { 295 return Signed ? SignedCS : UnsignedCS; 296 } 297 const ConstraintSystem &getCS(bool Signed) const { 298 return Signed ? SignedCS : UnsignedCS; 299 } 300 301 void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); } 302 void popLastNVariables(bool Signed, unsigned N) { 303 getCS(Signed).popLastNVariables(N); 304 } 305 306 bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const; 307 308 void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn, 309 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack); 310 311 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of 312 /// constraints, using indices from the corresponding constraint system. 313 /// New variables that need to be added to the system are collected in 314 /// \p NewVariables. 315 ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, 316 SmallVectorImpl<Value *> &NewVariables) const; 317 318 /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of 319 /// constraints using getConstraint. Returns an empty constraint if the result 320 /// cannot be used to query the existing constraint system, e.g. because it 321 /// would require adding new variables. Also tries to convert signed 322 /// predicates to unsigned ones if possible to allow using the unsigned system 323 /// which increases the effectiveness of the signed <-> unsigned transfer 324 /// logic. 325 ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0, 326 Value *Op1) const; 327 328 /// Try to add information from \p A \p Pred \p B to the unsigned/signed 329 /// system if \p Pred is signed/unsigned. 330 void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B, 331 unsigned NumIn, unsigned NumOut, 332 SmallVectorImpl<StackEntry> &DFSInStack); 333 }; 334 335 /// Represents a (Coefficient * Variable) entry after IR decomposition. 336 struct DecompEntry { 337 int64_t Coefficient; 338 Value *Variable; 339 /// True if the variable is known positive in the current constraint. 340 bool IsKnownNonNegative; 341 342 DecompEntry(int64_t Coefficient, Value *Variable, 343 bool IsKnownNonNegative = false) 344 : Coefficient(Coefficient), Variable(Variable), 345 IsKnownNonNegative(IsKnownNonNegative) {} 346 }; 347 348 /// Represents an Offset + Coefficient1 * Variable1 + ... decomposition. 349 struct Decomposition { 350 int64_t Offset = 0; 351 SmallVector<DecompEntry, 3> Vars; 352 353 Decomposition(int64_t Offset) : Offset(Offset) {} 354 Decomposition(Value *V, bool IsKnownNonNegative = false) { 355 Vars.emplace_back(1, V, IsKnownNonNegative); 356 } 357 Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars) 358 : Offset(Offset), Vars(Vars) {} 359 360 void add(int64_t OtherOffset) { 361 Offset = addWithOverflow(Offset, OtherOffset); 362 } 363 364 void add(const Decomposition &Other) { 365 add(Other.Offset); 366 append_range(Vars, Other.Vars); 367 } 368 369 void mul(int64_t Factor) { 370 Offset = multiplyWithOverflow(Offset, Factor); 371 for (auto &Var : Vars) 372 Var.Coefficient = multiplyWithOverflow(Var.Coefficient, Factor); 373 } 374 }; 375 376 // Variable and constant offsets for a chain of GEPs, with base pointer BasePtr. 377 struct OffsetResult { 378 Value *BasePtr; 379 APInt ConstantOffset; 380 MapVector<Value *, APInt> VariableOffsets; 381 bool AllInbounds; 382 383 OffsetResult() : BasePtr(nullptr), ConstantOffset(0, uint64_t(0)) {} 384 385 OffsetResult(GEPOperator &GEP, const DataLayout &DL) 386 : BasePtr(GEP.getPointerOperand()), AllInbounds(GEP.isInBounds()) { 387 ConstantOffset = APInt(DL.getIndexTypeSizeInBits(BasePtr->getType()), 0); 388 } 389 }; 390 } // namespace 391 392 // Try to collect variable and constant offsets for \p GEP, partly traversing 393 // nested GEPs. Returns an OffsetResult with nullptr as BasePtr of collecting 394 // the offset fails. 395 static OffsetResult collectOffsets(GEPOperator &GEP, const DataLayout &DL) { 396 OffsetResult Result(GEP, DL); 397 unsigned BitWidth = Result.ConstantOffset.getBitWidth(); 398 if (!GEP.collectOffset(DL, BitWidth, Result.VariableOffsets, 399 Result.ConstantOffset)) 400 return {}; 401 402 // If we have a nested GEP, check if we can combine the constant offset of the 403 // inner GEP with the outer GEP. 404 if (auto *InnerGEP = dyn_cast<GetElementPtrInst>(Result.BasePtr)) { 405 MapVector<Value *, APInt> VariableOffsets2; 406 APInt ConstantOffset2(BitWidth, 0); 407 bool CanCollectInner = InnerGEP->collectOffset( 408 DL, BitWidth, VariableOffsets2, ConstantOffset2); 409 // TODO: Support cases with more than 1 variable offset. 410 if (!CanCollectInner || Result.VariableOffsets.size() > 1 || 411 VariableOffsets2.size() > 1 || 412 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.size() >= 1)) { 413 // More than 1 variable index, use outer result. 414 return Result; 415 } 416 Result.BasePtr = InnerGEP->getPointerOperand(); 417 Result.ConstantOffset += ConstantOffset2; 418 if (Result.VariableOffsets.size() == 0 && VariableOffsets2.size() == 1) 419 Result.VariableOffsets = VariableOffsets2; 420 Result.AllInbounds &= InnerGEP->isInBounds(); 421 } 422 return Result; 423 } 424 425 static Decomposition decompose(Value *V, 426 SmallVectorImpl<ConditionTy> &Preconditions, 427 bool IsSigned, const DataLayout &DL); 428 429 static bool canUseSExt(ConstantInt *CI) { 430 const APInt &Val = CI->getValue(); 431 return Val.sgt(MinSignedConstraintValue) && Val.slt(MaxConstraintValue); 432 } 433 434 static Decomposition decomposeGEP(GEPOperator &GEP, 435 SmallVectorImpl<ConditionTy> &Preconditions, 436 bool IsSigned, const DataLayout &DL) { 437 // Do not reason about pointers where the index size is larger than 64 bits, 438 // as the coefficients used to encode constraints are 64 bit integers. 439 if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64) 440 return &GEP; 441 442 assert(!IsSigned && "The logic below only supports decomposition for " 443 "unsigned predicates at the moment."); 444 const auto &[BasePtr, ConstantOffset, VariableOffsets, AllInbounds] = 445 collectOffsets(GEP, DL); 446 if (!BasePtr || !AllInbounds) 447 return &GEP; 448 449 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr)); 450 for (auto [Index, Scale] : VariableOffsets) { 451 auto IdxResult = decompose(Index, Preconditions, IsSigned, DL); 452 IdxResult.mul(Scale.getSExtValue()); 453 Result.add(IdxResult); 454 455 // If Op0 is signed non-negative, the GEP is increasing monotonically and 456 // can be de-composed. 457 if (!isKnownNonNegative(Index, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 458 Preconditions.emplace_back(CmpInst::ICMP_SGE, Index, 459 ConstantInt::get(Index->getType(), 0)); 460 } 461 return Result; 462 } 463 464 // Decomposes \p V into a constant offset + list of pairs { Coefficient, 465 // Variable } where Coefficient * Variable. The sum of the constant offset and 466 // pairs equals \p V. 467 static Decomposition decompose(Value *V, 468 SmallVectorImpl<ConditionTy> &Preconditions, 469 bool IsSigned, const DataLayout &DL) { 470 471 auto MergeResults = [&Preconditions, IsSigned, &DL](Value *A, Value *B, 472 bool IsSignedB) { 473 auto ResA = decompose(A, Preconditions, IsSigned, DL); 474 auto ResB = decompose(B, Preconditions, IsSignedB, DL); 475 ResA.add(ResB); 476 return ResA; 477 }; 478 479 Type *Ty = V->getType()->getScalarType(); 480 if (Ty->isPointerTy() && !IsSigned) { 481 if (auto *GEP = dyn_cast<GEPOperator>(V)) 482 return decomposeGEP(*GEP, Preconditions, IsSigned, DL); 483 if (isa<ConstantPointerNull>(V)) 484 return int64_t(0); 485 486 return V; 487 } 488 489 // Don't handle integers > 64 bit. Our coefficients are 64-bit large, so 490 // coefficient add/mul may wrap, while the operation in the full bit width 491 // would not. 492 if (!Ty->isIntegerTy() || Ty->getIntegerBitWidth() > 64) 493 return V; 494 495 // Decompose \p V used with a signed predicate. 496 if (IsSigned) { 497 if (auto *CI = dyn_cast<ConstantInt>(V)) { 498 if (canUseSExt(CI)) 499 return CI->getSExtValue(); 500 } 501 Value *Op0; 502 Value *Op1; 503 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) 504 return MergeResults(Op0, Op1, IsSigned); 505 506 ConstantInt *CI; 507 if (match(V, m_NSWMul(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI)) { 508 auto Result = decompose(Op0, Preconditions, IsSigned, DL); 509 Result.mul(CI->getSExtValue()); 510 return Result; 511 } 512 513 return V; 514 } 515 516 if (auto *CI = dyn_cast<ConstantInt>(V)) { 517 if (CI->uge(MaxConstraintValue)) 518 return V; 519 return int64_t(CI->getZExtValue()); 520 } 521 522 Value *Op0; 523 bool IsKnownNonNegative = false; 524 if (match(V, m_ZExt(m_Value(Op0)))) { 525 IsKnownNonNegative = true; 526 V = Op0; 527 } 528 529 Value *Op1; 530 ConstantInt *CI; 531 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) { 532 return MergeResults(Op0, Op1, IsSigned); 533 } 534 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) { 535 if (!isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 536 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0, 537 ConstantInt::get(Op0->getType(), 0)); 538 if (!isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 539 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1, 540 ConstantInt::get(Op1->getType(), 0)); 541 542 return MergeResults(Op0, Op1, IsSigned); 543 } 544 545 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() && 546 canUseSExt(CI)) { 547 Preconditions.emplace_back( 548 CmpInst::ICMP_UGE, Op0, 549 ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1)); 550 return MergeResults(Op0, CI, true); 551 } 552 553 // Decompose or as an add if there are no common bits between the operands. 554 if (match(V, m_DisjointOr(m_Value(Op0), m_ConstantInt(CI)))) 555 return MergeResults(Op0, CI, IsSigned); 556 557 if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) { 558 if (CI->getSExtValue() < 0 || CI->getSExtValue() >= 64) 559 return {V, IsKnownNonNegative}; 560 auto Result = decompose(Op1, Preconditions, IsSigned, DL); 561 Result.mul(int64_t{1} << CI->getSExtValue()); 562 return Result; 563 } 564 565 if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) && 566 (!CI->isNegative())) { 567 auto Result = decompose(Op1, Preconditions, IsSigned, DL); 568 Result.mul(CI->getSExtValue()); 569 return Result; 570 } 571 572 if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI)) 573 return {-1 * CI->getSExtValue(), {{1, Op0}}}; 574 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) 575 return {0, {{1, Op0}, {-1, Op1}}}; 576 577 return {V, IsKnownNonNegative}; 578 } 579 580 ConstraintTy 581 ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, 582 SmallVectorImpl<Value *> &NewVariables) const { 583 assert(NewVariables.empty() && "NewVariables must be empty when passed in"); 584 bool IsEq = false; 585 bool IsNe = false; 586 587 // Try to convert Pred to one of ULE/SLT/SLE/SLT. 588 switch (Pred) { 589 case CmpInst::ICMP_UGT: 590 case CmpInst::ICMP_UGE: 591 case CmpInst::ICMP_SGT: 592 case CmpInst::ICMP_SGE: { 593 Pred = CmpInst::getSwappedPredicate(Pred); 594 std::swap(Op0, Op1); 595 break; 596 } 597 case CmpInst::ICMP_EQ: 598 if (match(Op1, m_Zero())) { 599 Pred = CmpInst::ICMP_ULE; 600 } else { 601 IsEq = true; 602 Pred = CmpInst::ICMP_ULE; 603 } 604 break; 605 case CmpInst::ICMP_NE: 606 if (match(Op1, m_Zero())) { 607 Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT); 608 std::swap(Op0, Op1); 609 } else { 610 IsNe = true; 611 Pred = CmpInst::ICMP_ULE; 612 } 613 break; 614 default: 615 break; 616 } 617 618 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT && 619 Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT) 620 return {}; 621 622 SmallVector<ConditionTy, 4> Preconditions; 623 bool IsSigned = CmpInst::isSigned(Pred); 624 auto &Value2Index = getValue2Index(IsSigned); 625 auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(), 626 Preconditions, IsSigned, DL); 627 auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(), 628 Preconditions, IsSigned, DL); 629 int64_t Offset1 = ADec.Offset; 630 int64_t Offset2 = BDec.Offset; 631 Offset1 *= -1; 632 633 auto &VariablesA = ADec.Vars; 634 auto &VariablesB = BDec.Vars; 635 636 // First try to look up \p V in Value2Index and NewVariables. Otherwise add a 637 // new entry to NewVariables. 638 DenseMap<Value *, unsigned> NewIndexMap; 639 auto GetOrAddIndex = [&Value2Index, &NewVariables, 640 &NewIndexMap](Value *V) -> unsigned { 641 auto V2I = Value2Index.find(V); 642 if (V2I != Value2Index.end()) 643 return V2I->second; 644 auto Insert = 645 NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1}); 646 if (Insert.second) 647 NewVariables.push_back(V); 648 return Insert.first->second; 649 }; 650 651 // Make sure all variables have entries in Value2Index or NewVariables. 652 for (const auto &KV : concat<DecompEntry>(VariablesA, VariablesB)) 653 GetOrAddIndex(KV.Variable); 654 655 // Build result constraint, by first adding all coefficients from A and then 656 // subtracting all coefficients from B. 657 ConstraintTy Res( 658 SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0), 659 IsSigned, IsEq, IsNe); 660 // Collect variables that are known to be positive in all uses in the 661 // constraint. 662 DenseMap<Value *, bool> KnownNonNegativeVariables; 663 auto &R = Res.Coefficients; 664 for (const auto &KV : VariablesA) { 665 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient; 666 auto I = 667 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative}); 668 I.first->second &= KV.IsKnownNonNegative; 669 } 670 671 for (const auto &KV : VariablesB) { 672 if (SubOverflow(R[GetOrAddIndex(KV.Variable)], KV.Coefficient, 673 R[GetOrAddIndex(KV.Variable)])) 674 return {}; 675 auto I = 676 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative}); 677 I.first->second &= KV.IsKnownNonNegative; 678 } 679 680 int64_t OffsetSum; 681 if (AddOverflow(Offset1, Offset2, OffsetSum)) 682 return {}; 683 if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT)) 684 if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum)) 685 return {}; 686 R[0] = OffsetSum; 687 Res.Preconditions = std::move(Preconditions); 688 689 // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new 690 // variables. 691 while (!NewVariables.empty()) { 692 int64_t Last = R.back(); 693 if (Last != 0) 694 break; 695 R.pop_back(); 696 Value *RemovedV = NewVariables.pop_back_val(); 697 NewIndexMap.erase(RemovedV); 698 } 699 700 // Add extra constraints for variables that are known positive. 701 for (auto &KV : KnownNonNegativeVariables) { 702 if (!KV.second || 703 (!Value2Index.contains(KV.first) && !NewIndexMap.contains(KV.first))) 704 continue; 705 SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1, 0); 706 C[GetOrAddIndex(KV.first)] = -1; 707 Res.ExtraInfo.push_back(C); 708 } 709 return Res; 710 } 711 712 ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred, 713 Value *Op0, 714 Value *Op1) const { 715 Constant *NullC = Constant::getNullValue(Op0->getType()); 716 // Handle trivially true compares directly to avoid adding V UGE 0 constraints 717 // for all variables in the unsigned system. 718 if ((Pred == CmpInst::ICMP_ULE && Op0 == NullC) || 719 (Pred == CmpInst::ICMP_UGE && Op1 == NullC)) { 720 auto &Value2Index = getValue2Index(false); 721 // Return constraint that's trivially true. 722 return ConstraintTy(SmallVector<int64_t, 8>(Value2Index.size(), 0), false, 723 false, false); 724 } 725 726 // If both operands are known to be non-negative, change signed predicates to 727 // unsigned ones. This increases the reasoning effectiveness in combination 728 // with the signed <-> unsigned transfer logic. 729 if (CmpInst::isSigned(Pred) && 730 isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) && 731 isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1)) 732 Pred = CmpInst::getUnsignedPredicate(Pred); 733 734 SmallVector<Value *> NewVariables; 735 ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables); 736 if (!NewVariables.empty()) 737 return {}; 738 return R; 739 } 740 741 bool ConstraintTy::isValid(const ConstraintInfo &Info) const { 742 return Coefficients.size() > 0 && 743 all_of(Preconditions, [&Info](const ConditionTy &C) { 744 return Info.doesHold(C.Pred, C.Op0, C.Op1); 745 }); 746 } 747 748 std::optional<bool> 749 ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const { 750 bool IsConditionImplied = CS.isConditionImplied(Coefficients); 751 752 if (IsEq || IsNe) { 753 auto NegatedOrEqual = ConstraintSystem::negateOrEqual(Coefficients); 754 bool IsNegatedOrEqualImplied = 755 !NegatedOrEqual.empty() && CS.isConditionImplied(NegatedOrEqual); 756 757 // In order to check that `%a == %b` is true (equality), both conditions `%a 758 // >= %b` and `%a <= %b` must hold true. When checking for equality (`IsEq` 759 // is true), we return true if they both hold, false in the other cases. 760 if (IsConditionImplied && IsNegatedOrEqualImplied) 761 return IsEq; 762 763 auto Negated = ConstraintSystem::negate(Coefficients); 764 bool IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated); 765 766 auto StrictLessThan = ConstraintSystem::toStrictLessThan(Coefficients); 767 bool IsStrictLessThanImplied = 768 !StrictLessThan.empty() && CS.isConditionImplied(StrictLessThan); 769 770 // In order to check that `%a != %b` is true (non-equality), either 771 // condition `%a > %b` or `%a < %b` must hold true. When checking for 772 // non-equality (`IsNe` is true), we return true if one of the two holds, 773 // false in the other cases. 774 if (IsNegatedImplied || IsStrictLessThanImplied) 775 return IsNe; 776 777 return std::nullopt; 778 } 779 780 if (IsConditionImplied) 781 return true; 782 783 auto Negated = ConstraintSystem::negate(Coefficients); 784 auto IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated); 785 if (IsNegatedImplied) 786 return false; 787 788 // Neither the condition nor its negated holds, did not prove anything. 789 return std::nullopt; 790 } 791 792 bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A, 793 Value *B) const { 794 auto R = getConstraintForSolving(Pred, A, B); 795 return R.isValid(*this) && 796 getCS(R.IsSigned).isConditionImplied(R.Coefficients); 797 } 798 799 void ConstraintInfo::transferToOtherSystem( 800 CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn, 801 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) { 802 auto IsKnownNonNegative = [this](Value *V) { 803 return doesHold(CmpInst::ICMP_SGE, V, ConstantInt::get(V->getType(), 0)) || 804 isKnownNonNegative(V, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1); 805 }; 806 // Check if we can combine facts from the signed and unsigned systems to 807 // derive additional facts. 808 if (!A->getType()->isIntegerTy()) 809 return; 810 // FIXME: This currently depends on the order we add facts. Ideally we 811 // would first add all known facts and only then try to add additional 812 // facts. 813 switch (Pred) { 814 default: 815 break; 816 case CmpInst::ICMP_ULT: 817 case CmpInst::ICMP_ULE: 818 // If B is a signed positive constant, then A >=s 0 and A <s (or <=s) B. 819 if (IsKnownNonNegative(B)) { 820 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn, 821 NumOut, DFSInStack); 822 addFact(CmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut, 823 DFSInStack); 824 } 825 break; 826 case CmpInst::ICMP_UGE: 827 case CmpInst::ICMP_UGT: 828 // If A is a signed positive constant, then B >=s 0 and A >s (or >=s) B. 829 if (IsKnownNonNegative(A)) { 830 addFact(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0), NumIn, 831 NumOut, DFSInStack); 832 addFact(CmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut, 833 DFSInStack); 834 } 835 break; 836 case CmpInst::ICMP_SLT: 837 if (IsKnownNonNegative(A)) 838 addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack); 839 break; 840 case CmpInst::ICMP_SGT: { 841 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), -1))) 842 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn, 843 NumOut, DFSInStack); 844 if (IsKnownNonNegative(B)) 845 addFact(CmpInst::ICMP_UGT, A, B, NumIn, NumOut, DFSInStack); 846 847 break; 848 } 849 case CmpInst::ICMP_SGE: 850 if (IsKnownNonNegative(B)) 851 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack); 852 break; 853 } 854 } 855 856 #ifndef NDEBUG 857 858 static void dumpConstraint(ArrayRef<int64_t> C, 859 const DenseMap<Value *, unsigned> &Value2Index) { 860 ConstraintSystem CS(Value2Index); 861 CS.addVariableRowFill(C); 862 CS.dump(); 863 } 864 #endif 865 866 void State::addInfoForInductions(BasicBlock &BB) { 867 auto *L = LI.getLoopFor(&BB); 868 if (!L || L->getHeader() != &BB) 869 return; 870 871 Value *A; 872 Value *B; 873 CmpInst::Predicate Pred; 874 875 if (!match(BB.getTerminator(), 876 m_Br(m_ICmp(Pred, m_Value(A), m_Value(B)), m_Value(), m_Value()))) 877 return; 878 PHINode *PN = dyn_cast<PHINode>(A); 879 if (!PN) { 880 Pred = CmpInst::getSwappedPredicate(Pred); 881 std::swap(A, B); 882 PN = dyn_cast<PHINode>(A); 883 } 884 885 if (!PN || PN->getParent() != &BB || PN->getNumIncomingValues() != 2 || 886 !SE.isSCEVable(PN->getType())) 887 return; 888 889 BasicBlock *InLoopSucc = nullptr; 890 if (Pred == CmpInst::ICMP_NE) 891 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(0); 892 else if (Pred == CmpInst::ICMP_EQ) 893 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(1); 894 else 895 return; 896 897 if (!L->contains(InLoopSucc) || !L->isLoopExiting(&BB) || InLoopSucc == &BB) 898 return; 899 900 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.getSCEV(PN)); 901 BasicBlock *LoopPred = L->getLoopPredecessor(); 902 if (!AR || AR->getLoop() != L || !LoopPred) 903 return; 904 905 const SCEV *StartSCEV = AR->getStart(); 906 Value *StartValue = nullptr; 907 if (auto *C = dyn_cast<SCEVConstant>(StartSCEV)) { 908 StartValue = C->getValue(); 909 } else { 910 StartValue = PN->getIncomingValueForBlock(LoopPred); 911 assert(SE.getSCEV(StartValue) == StartSCEV && "inconsistent start value"); 912 } 913 914 DomTreeNode *DTN = DT.getNode(InLoopSucc); 915 auto Inc = SE.getMonotonicPredicateType(AR, CmpInst::ICMP_UGT); 916 bool MonotonicallyIncreasing = 917 Inc && *Inc == ScalarEvolution::MonotonicallyIncreasing; 918 if (MonotonicallyIncreasing) { 919 // SCEV guarantees that AR does not wrap, so PN >= StartValue can be added 920 // unconditionally. 921 WorkList.push_back( 922 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_UGE, PN, StartValue)); 923 } 924 925 APInt StepOffset; 926 if (auto *C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) 927 StepOffset = C->getAPInt(); 928 else 929 return; 930 931 // Make sure the bound B is loop-invariant. 932 if (!L->isLoopInvariant(B)) 933 return; 934 935 // Handle negative steps. 936 if (StepOffset.isNegative()) { 937 // TODO: Extend to allow steps > -1. 938 if (!(-StepOffset).isOne()) 939 return; 940 941 // AR may wrap. 942 // Add StartValue >= PN conditional on B <= StartValue which guarantees that 943 // the loop exits before wrapping with a step of -1. 944 WorkList.push_back(FactOrCheck::getConditionFact( 945 DTN, CmpInst::ICMP_UGE, StartValue, PN, 946 ConditionTy(CmpInst::ICMP_ULE, B, StartValue))); 947 // Add PN > B conditional on B <= StartValue which guarantees that the loop 948 // exits when reaching B with a step of -1. 949 WorkList.push_back(FactOrCheck::getConditionFact( 950 DTN, CmpInst::ICMP_UGT, PN, B, 951 ConditionTy(CmpInst::ICMP_ULE, B, StartValue))); 952 return; 953 } 954 955 // Make sure AR either steps by 1 or that the value we compare against is a 956 // GEP based on the same start value and all offsets are a multiple of the 957 // step size, to guarantee that the induction will reach the value. 958 if (StepOffset.isZero() || StepOffset.isNegative()) 959 return; 960 961 if (!StepOffset.isOne()) { 962 auto *UpperGEP = dyn_cast<GetElementPtrInst>(B); 963 if (!UpperGEP || UpperGEP->getPointerOperand() != StartValue || 964 !UpperGEP->isInBounds()) 965 return; 966 967 MapVector<Value *, APInt> UpperVariableOffsets; 968 APInt UpperConstantOffset(StepOffset.getBitWidth(), 0); 969 const DataLayout &DL = BB.getModule()->getDataLayout(); 970 if (!UpperGEP->collectOffset(DL, StepOffset.getBitWidth(), 971 UpperVariableOffsets, UpperConstantOffset)) 972 return; 973 // All variable offsets and the constant offset have to be a multiple of the 974 // step. 975 if (!UpperConstantOffset.urem(StepOffset).isZero() || 976 any_of(UpperVariableOffsets, [&StepOffset](const auto &P) { 977 return !P.second.urem(StepOffset).isZero(); 978 })) 979 return; 980 } 981 982 // AR may wrap. Add PN >= StartValue conditional on StartValue <= B which 983 // guarantees that the loop exits before wrapping in combination with the 984 // restrictions on B and the step above. 985 if (!MonotonicallyIncreasing) { 986 WorkList.push_back(FactOrCheck::getConditionFact( 987 DTN, CmpInst::ICMP_UGE, PN, StartValue, 988 ConditionTy(CmpInst::ICMP_ULE, StartValue, B))); 989 } 990 WorkList.push_back(FactOrCheck::getConditionFact( 991 DTN, CmpInst::ICMP_ULT, PN, B, 992 ConditionTy(CmpInst::ICMP_ULE, StartValue, B))); 993 } 994 995 void State::addInfoFor(BasicBlock &BB) { 996 addInfoForInductions(BB); 997 998 // True as long as long as the current instruction is guaranteed to execute. 999 bool GuaranteedToExecute = true; 1000 // Queue conditions and assumes. 1001 for (Instruction &I : BB) { 1002 if (auto Cmp = dyn_cast<ICmpInst>(&I)) { 1003 for (Use &U : Cmp->uses()) { 1004 auto *UserI = getContextInstForUse(U); 1005 auto *DTN = DT.getNode(UserI->getParent()); 1006 if (!DTN) 1007 continue; 1008 WorkList.push_back(FactOrCheck::getCheck(DTN, &U)); 1009 } 1010 continue; 1011 } 1012 1013 if (match(&I, m_Intrinsic<Intrinsic::ssub_with_overflow>())) { 1014 WorkList.push_back( 1015 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I))); 1016 continue; 1017 } 1018 1019 if (isa<MinMaxIntrinsic>(&I)) { 1020 WorkList.push_back(FactOrCheck::getInstFact(DT.getNode(&BB), &I)); 1021 continue; 1022 } 1023 1024 Value *A, *B; 1025 CmpInst::Predicate Pred; 1026 // For now, just handle assumes with a single compare as condition. 1027 if (match(&I, m_Intrinsic<Intrinsic::assume>( 1028 m_ICmp(Pred, m_Value(A), m_Value(B))))) { 1029 if (GuaranteedToExecute) { 1030 // The assume is guaranteed to execute when BB is entered, hence Cond 1031 // holds on entry to BB. 1032 WorkList.emplace_back(FactOrCheck::getConditionFact( 1033 DT.getNode(I.getParent()), Pred, A, B)); 1034 } else { 1035 WorkList.emplace_back( 1036 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I)); 1037 } 1038 } 1039 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I); 1040 } 1041 1042 if (auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) { 1043 for (auto &Case : Switch->cases()) { 1044 BasicBlock *Succ = Case.getCaseSuccessor(); 1045 Value *V = Case.getCaseValue(); 1046 if (!canAddSuccessor(BB, Succ)) 1047 continue; 1048 WorkList.emplace_back(FactOrCheck::getConditionFact( 1049 DT.getNode(Succ), CmpInst::ICMP_EQ, Switch->getCondition(), V)); 1050 } 1051 return; 1052 } 1053 1054 auto *Br = dyn_cast<BranchInst>(BB.getTerminator()); 1055 if (!Br || !Br->isConditional()) 1056 return; 1057 1058 Value *Cond = Br->getCondition(); 1059 1060 // If the condition is a chain of ORs/AND and the successor only has the 1061 // current block as predecessor, queue conditions for the successor. 1062 Value *Op0, *Op1; 1063 if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) || 1064 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) { 1065 bool IsOr = match(Cond, m_LogicalOr()); 1066 bool IsAnd = match(Cond, m_LogicalAnd()); 1067 // If there's a select that matches both AND and OR, we need to commit to 1068 // one of the options. Arbitrarily pick OR. 1069 if (IsOr && IsAnd) 1070 IsAnd = false; 1071 1072 BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0); 1073 if (canAddSuccessor(BB, Successor)) { 1074 SmallVector<Value *> CondWorkList; 1075 SmallPtrSet<Value *, 8> SeenCond; 1076 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) { 1077 if (SeenCond.insert(V).second) 1078 CondWorkList.push_back(V); 1079 }; 1080 QueueValue(Op1); 1081 QueueValue(Op0); 1082 while (!CondWorkList.empty()) { 1083 Value *Cur = CondWorkList.pop_back_val(); 1084 if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) { 1085 WorkList.emplace_back(FactOrCheck::getConditionFact( 1086 DT.getNode(Successor), 1087 IsOr ? CmpInst::getInversePredicate(Cmp->getPredicate()) 1088 : Cmp->getPredicate(), 1089 Cmp->getOperand(0), Cmp->getOperand(1))); 1090 continue; 1091 } 1092 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) { 1093 QueueValue(Op1); 1094 QueueValue(Op0); 1095 continue; 1096 } 1097 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) { 1098 QueueValue(Op1); 1099 QueueValue(Op0); 1100 continue; 1101 } 1102 } 1103 } 1104 return; 1105 } 1106 1107 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition()); 1108 if (!CmpI) 1109 return; 1110 if (canAddSuccessor(BB, Br->getSuccessor(0))) 1111 WorkList.emplace_back(FactOrCheck::getConditionFact( 1112 DT.getNode(Br->getSuccessor(0)), CmpI->getPredicate(), 1113 CmpI->getOperand(0), CmpI->getOperand(1))); 1114 if (canAddSuccessor(BB, Br->getSuccessor(1))) 1115 WorkList.emplace_back(FactOrCheck::getConditionFact( 1116 DT.getNode(Br->getSuccessor(1)), 1117 CmpInst::getInversePredicate(CmpI->getPredicate()), CmpI->getOperand(0), 1118 CmpI->getOperand(1))); 1119 } 1120 1121 #ifndef NDEBUG 1122 static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred, 1123 Value *LHS, Value *RHS) { 1124 OS << "icmp " << Pred << ' '; 1125 LHS->printAsOperand(OS, /*PrintType=*/true); 1126 OS << ", "; 1127 RHS->printAsOperand(OS, /*PrintType=*/false); 1128 } 1129 #endif 1130 1131 namespace { 1132 /// Helper to keep track of a condition and if it should be treated as negated 1133 /// for reproducer construction. 1134 /// Pred == Predicate::BAD_ICMP_PREDICATE indicates that this entry is a 1135 /// placeholder to keep the ReproducerCondStack in sync with DFSInStack. 1136 struct ReproducerEntry { 1137 ICmpInst::Predicate Pred; 1138 Value *LHS; 1139 Value *RHS; 1140 1141 ReproducerEntry(ICmpInst::Predicate Pred, Value *LHS, Value *RHS) 1142 : Pred(Pred), LHS(LHS), RHS(RHS) {} 1143 }; 1144 } // namespace 1145 1146 /// Helper function to generate a reproducer function for simplifying \p Cond. 1147 /// The reproducer function contains a series of @llvm.assume calls, one for 1148 /// each condition in \p Stack. For each condition, the operand instruction are 1149 /// cloned until we reach operands that have an entry in \p Value2Index. Those 1150 /// will then be added as function arguments. \p DT is used to order cloned 1151 /// instructions. The reproducer function will get added to \p M, if it is 1152 /// non-null. Otherwise no reproducer function is generated. 1153 static void generateReproducer(CmpInst *Cond, Module *M, 1154 ArrayRef<ReproducerEntry> Stack, 1155 ConstraintInfo &Info, DominatorTree &DT) { 1156 if (!M) 1157 return; 1158 1159 LLVMContext &Ctx = Cond->getContext(); 1160 1161 LLVM_DEBUG(dbgs() << "Creating reproducer for " << *Cond << "\n"); 1162 1163 ValueToValueMapTy Old2New; 1164 SmallVector<Value *> Args; 1165 SmallPtrSet<Value *, 8> Seen; 1166 // Traverse Cond and its operands recursively until we reach a value that's in 1167 // Value2Index or not an instruction, or not a operation that 1168 // ConstraintElimination can decompose. Such values will be considered as 1169 // external inputs to the reproducer, they are collected and added as function 1170 // arguments later. 1171 auto CollectArguments = [&](ArrayRef<Value *> Ops, bool IsSigned) { 1172 auto &Value2Index = Info.getValue2Index(IsSigned); 1173 SmallVector<Value *, 4> WorkList(Ops); 1174 while (!WorkList.empty()) { 1175 Value *V = WorkList.pop_back_val(); 1176 if (!Seen.insert(V).second) 1177 continue; 1178 if (Old2New.find(V) != Old2New.end()) 1179 continue; 1180 if (isa<Constant>(V)) 1181 continue; 1182 1183 auto *I = dyn_cast<Instruction>(V); 1184 if (Value2Index.contains(V) || !I || 1185 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) { 1186 Old2New[V] = V; 1187 Args.push_back(V); 1188 LLVM_DEBUG(dbgs() << " found external input " << *V << "\n"); 1189 } else { 1190 append_range(WorkList, I->operands()); 1191 } 1192 } 1193 }; 1194 1195 for (auto &Entry : Stack) 1196 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE) 1197 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred)); 1198 CollectArguments(Cond, ICmpInst::isSigned(Cond->getPredicate())); 1199 1200 SmallVector<Type *> ParamTys; 1201 for (auto *P : Args) 1202 ParamTys.push_back(P->getType()); 1203 1204 FunctionType *FTy = FunctionType::get(Cond->getType(), ParamTys, 1205 /*isVarArg=*/false); 1206 Function *F = Function::Create(FTy, Function::ExternalLinkage, 1207 Cond->getModule()->getName() + 1208 Cond->getFunction()->getName() + "repro", 1209 M); 1210 // Add arguments to the reproducer function for each external value collected. 1211 for (unsigned I = 0; I < Args.size(); ++I) { 1212 F->getArg(I)->setName(Args[I]->getName()); 1213 Old2New[Args[I]] = F->getArg(I); 1214 } 1215 1216 BasicBlock *Entry = BasicBlock::Create(Ctx, "entry", F); 1217 IRBuilder<> Builder(Entry); 1218 Builder.CreateRet(Builder.getTrue()); 1219 Builder.SetInsertPoint(Entry->getTerminator()); 1220 1221 // Clone instructions in \p Ops and their operands recursively until reaching 1222 // an value in Value2Index (external input to the reproducer). Update Old2New 1223 // mapping for the original and cloned instructions. Sort instructions to 1224 // clone by dominance, then insert the cloned instructions in the function. 1225 auto CloneInstructions = [&](ArrayRef<Value *> Ops, bool IsSigned) { 1226 SmallVector<Value *, 4> WorkList(Ops); 1227 SmallVector<Instruction *> ToClone; 1228 auto &Value2Index = Info.getValue2Index(IsSigned); 1229 while (!WorkList.empty()) { 1230 Value *V = WorkList.pop_back_val(); 1231 if (Old2New.find(V) != Old2New.end()) 1232 continue; 1233 1234 auto *I = dyn_cast<Instruction>(V); 1235 if (!Value2Index.contains(V) && I) { 1236 Old2New[V] = nullptr; 1237 ToClone.push_back(I); 1238 append_range(WorkList, I->operands()); 1239 } 1240 } 1241 1242 sort(ToClone, 1243 [&DT](Instruction *A, Instruction *B) { return DT.dominates(A, B); }); 1244 for (Instruction *I : ToClone) { 1245 Instruction *Cloned = I->clone(); 1246 Old2New[I] = Cloned; 1247 Old2New[I]->setName(I->getName()); 1248 Cloned->insertBefore(&*Builder.GetInsertPoint()); 1249 Cloned->dropUnknownNonDebugMetadata(); 1250 Cloned->setDebugLoc({}); 1251 } 1252 }; 1253 1254 // Materialize the assumptions for the reproducer using the entries in Stack. 1255 // That is, first clone the operands of the condition recursively until we 1256 // reach an external input to the reproducer and add them to the reproducer 1257 // function. Then add an ICmp for the condition (with the inverse predicate if 1258 // the entry is negated) and an assert using the ICmp. 1259 for (auto &Entry : Stack) { 1260 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE) 1261 continue; 1262 1263 LLVM_DEBUG(dbgs() << " Materializing assumption "; 1264 dumpUnpackedICmp(dbgs(), Entry.Pred, Entry.LHS, Entry.RHS); 1265 dbgs() << "\n"); 1266 CloneInstructions({Entry.LHS, Entry.RHS}, CmpInst::isSigned(Entry.Pred)); 1267 1268 auto *Cmp = Builder.CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS); 1269 Builder.CreateAssumption(Cmp); 1270 } 1271 1272 // Finally, clone the condition to reproduce and remap instruction operands in 1273 // the reproducer using Old2New. 1274 CloneInstructions(Cond, CmpInst::isSigned(Cond->getPredicate())); 1275 Entry->getTerminator()->setOperand(0, Cond); 1276 remapInstructionsInBlocks({Entry}, Old2New); 1277 1278 assert(!verifyFunction(*F, &dbgs())); 1279 } 1280 1281 static std::optional<bool> checkCondition(CmpInst::Predicate Pred, Value *A, 1282 Value *B, Instruction *CheckInst, 1283 ConstraintInfo &Info, unsigned NumIn, 1284 unsigned NumOut, 1285 Instruction *ContextInst) { 1286 LLVM_DEBUG(dbgs() << "Checking " << *CheckInst << "\n"); 1287 1288 auto R = Info.getConstraintForSolving(Pred, A, B); 1289 if (R.empty() || !R.isValid(Info)){ 1290 LLVM_DEBUG(dbgs() << " failed to decompose condition\n"); 1291 return std::nullopt; 1292 } 1293 1294 auto &CSToUse = Info.getCS(R.IsSigned); 1295 1296 // If there was extra information collected during decomposition, apply 1297 // it now and remove it immediately once we are done with reasoning 1298 // about the constraint. 1299 for (auto &Row : R.ExtraInfo) 1300 CSToUse.addVariableRow(Row); 1301 auto InfoRestorer = make_scope_exit([&]() { 1302 for (unsigned I = 0; I < R.ExtraInfo.size(); ++I) 1303 CSToUse.popLastConstraint(); 1304 }); 1305 1306 if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) { 1307 if (!DebugCounter::shouldExecute(EliminatedCounter)) 1308 return std::nullopt; 1309 1310 LLVM_DEBUG({ 1311 dbgs() << "Condition "; 1312 dumpUnpackedICmp( 1313 dbgs(), *ImpliedCondition ? Pred : CmpInst::getInversePredicate(Pred), 1314 A, B); 1315 dbgs() << " implied by dominating constraints\n"; 1316 CSToUse.dump(); 1317 }); 1318 return ImpliedCondition; 1319 } 1320 1321 return std::nullopt; 1322 } 1323 1324 static bool checkAndReplaceCondition( 1325 CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, 1326 Instruction *ContextInst, Module *ReproducerModule, 1327 ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT, 1328 SmallVectorImpl<Instruction *> &ToRemove) { 1329 auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) { 1330 generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT); 1331 Constant *ConstantC = ConstantInt::getBool( 1332 CmpInst::makeCmpResultType(Cmp->getType()), IsTrue); 1333 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut, 1334 ContextInst](Use &U) { 1335 auto *UserI = getContextInstForUse(U); 1336 auto *DTN = DT.getNode(UserI->getParent()); 1337 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut) 1338 return false; 1339 if (UserI->getParent() == ContextInst->getParent() && 1340 UserI->comesBefore(ContextInst)) 1341 return false; 1342 1343 // Conditions in an assume trivially simplify to true. Skip uses 1344 // in assume calls to not destroy the available information. 1345 auto *II = dyn_cast<IntrinsicInst>(U.getUser()); 1346 return !II || II->getIntrinsicID() != Intrinsic::assume; 1347 }); 1348 NumCondsRemoved++; 1349 if (Cmp->use_empty()) 1350 ToRemove.push_back(Cmp); 1351 return true; 1352 }; 1353 1354 if (auto ImpliedCondition = checkCondition( 1355 Cmp->getPredicate(), Cmp->getOperand(0), Cmp->getOperand(1), Cmp, 1356 Info, NumIn, NumOut, ContextInst)) 1357 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition); 1358 return false; 1359 } 1360 1361 static void 1362 removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info, 1363 Module *ReproducerModule, 1364 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack, 1365 SmallVectorImpl<StackEntry> &DFSInStack) { 1366 Info.popLastConstraint(E.IsSigned); 1367 // Remove variables in the system that went out of scope. 1368 auto &Mapping = Info.getValue2Index(E.IsSigned); 1369 for (Value *V : E.ValuesToRelease) 1370 Mapping.erase(V); 1371 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size()); 1372 DFSInStack.pop_back(); 1373 if (ReproducerModule) 1374 ReproducerCondStack.pop_back(); 1375 } 1376 1377 /// Check if either the first condition of an AND or OR is implied by the 1378 /// (negated in case of OR) second condition or vice versa. 1379 static bool checkOrAndOpImpliedByOther( 1380 FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule, 1381 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack, 1382 SmallVectorImpl<StackEntry> &DFSInStack) { 1383 1384 CmpInst::Predicate Pred; 1385 Value *A, *B; 1386 Instruction *JoinOp = CB.getContextInst(); 1387 CmpInst *CmpToCheck = cast<CmpInst>(CB.getInstructionToSimplify()); 1388 unsigned OtherOpIdx = JoinOp->getOperand(0) == CmpToCheck ? 1 : 0; 1389 1390 // Don't try to simplify the first condition of a select by the second, as 1391 // this may make the select more poisonous than the original one. 1392 // TODO: check if the first operand may be poison. 1393 if (OtherOpIdx != 0 && isa<SelectInst>(JoinOp)) 1394 return false; 1395 1396 if (!match(JoinOp->getOperand(OtherOpIdx), 1397 m_ICmp(Pred, m_Value(A), m_Value(B)))) 1398 return false; 1399 1400 // For OR, check if the negated condition implies CmpToCheck. 1401 bool IsOr = match(JoinOp, m_LogicalOr()); 1402 if (IsOr) 1403 Pred = CmpInst::getInversePredicate(Pred); 1404 1405 // Optimistically add fact from first condition. 1406 unsigned OldSize = DFSInStack.size(); 1407 Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack); 1408 if (OldSize == DFSInStack.size()) 1409 return false; 1410 1411 bool Changed = false; 1412 // Check if the second condition can be simplified now. 1413 if (auto ImpliedCondition = 1414 checkCondition(CmpToCheck->getPredicate(), CmpToCheck->getOperand(0), 1415 CmpToCheck->getOperand(1), CmpToCheck, Info, CB.NumIn, 1416 CB.NumOut, CB.getContextInst())) { 1417 if (IsOr && isa<SelectInst>(JoinOp)) { 1418 JoinOp->setOperand( 1419 OtherOpIdx == 0 ? 2 : 0, 1420 ConstantInt::getBool(JoinOp->getType(), *ImpliedCondition)); 1421 } else 1422 JoinOp->setOperand( 1423 1 - OtherOpIdx, 1424 ConstantInt::getBool(JoinOp->getType(), *ImpliedCondition)); 1425 1426 Changed = true; 1427 } 1428 1429 // Remove entries again. 1430 while (OldSize < DFSInStack.size()) { 1431 StackEntry E = DFSInStack.back(); 1432 removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack, 1433 DFSInStack); 1434 } 1435 return Changed; 1436 } 1437 1438 void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B, 1439 unsigned NumIn, unsigned NumOut, 1440 SmallVectorImpl<StackEntry> &DFSInStack) { 1441 // If the constraint has a pre-condition, skip the constraint if it does not 1442 // hold. 1443 SmallVector<Value *> NewVariables; 1444 auto R = getConstraint(Pred, A, B, NewVariables); 1445 1446 // TODO: Support non-equality for facts as well. 1447 if (!R.isValid(*this) || R.isNe()) 1448 return; 1449 1450 LLVM_DEBUG(dbgs() << "Adding '"; dumpUnpackedICmp(dbgs(), Pred, A, B); 1451 dbgs() << "'\n"); 1452 bool Added = false; 1453 auto &CSToUse = getCS(R.IsSigned); 1454 if (R.Coefficients.empty()) 1455 return; 1456 1457 Added |= CSToUse.addVariableRowFill(R.Coefficients); 1458 1459 // If R has been added to the system, add the new variables and queue it for 1460 // removal once it goes out-of-scope. 1461 if (Added) { 1462 SmallVector<Value *, 2> ValuesToRelease; 1463 auto &Value2Index = getValue2Index(R.IsSigned); 1464 for (Value *V : NewVariables) { 1465 Value2Index.insert({V, Value2Index.size() + 1}); 1466 ValuesToRelease.push_back(V); 1467 } 1468 1469 LLVM_DEBUG({ 1470 dbgs() << " constraint: "; 1471 dumpConstraint(R.Coefficients, getValue2Index(R.IsSigned)); 1472 dbgs() << "\n"; 1473 }); 1474 1475 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, 1476 std::move(ValuesToRelease)); 1477 1478 if (!R.IsSigned) { 1479 for (Value *V : NewVariables) { 1480 ConstraintTy VarPos(SmallVector<int64_t, 8>(Value2Index.size() + 1, 0), 1481 false, false, false); 1482 VarPos.Coefficients[Value2Index[V]] = -1; 1483 CSToUse.addVariableRow(VarPos.Coefficients); 1484 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, 1485 SmallVector<Value *, 2>()); 1486 } 1487 } 1488 1489 if (R.isEq()) { 1490 // Also add the inverted constraint for equality constraints. 1491 for (auto &Coeff : R.Coefficients) 1492 Coeff *= -1; 1493 CSToUse.addVariableRowFill(R.Coefficients); 1494 1495 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, 1496 SmallVector<Value *, 2>()); 1497 } 1498 } 1499 } 1500 1501 static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, 1502 SmallVectorImpl<Instruction *> &ToRemove) { 1503 bool Changed = false; 1504 IRBuilder<> Builder(II->getParent(), II->getIterator()); 1505 Value *Sub = nullptr; 1506 for (User *U : make_early_inc_range(II->users())) { 1507 if (match(U, m_ExtractValue<0>(m_Value()))) { 1508 if (!Sub) 1509 Sub = Builder.CreateSub(A, B); 1510 U->replaceAllUsesWith(Sub); 1511 Changed = true; 1512 } else if (match(U, m_ExtractValue<1>(m_Value()))) { 1513 U->replaceAllUsesWith(Builder.getFalse()); 1514 Changed = true; 1515 } else 1516 continue; 1517 1518 if (U->use_empty()) { 1519 auto *I = cast<Instruction>(U); 1520 ToRemove.push_back(I); 1521 I->setOperand(0, PoisonValue::get(II->getType())); 1522 Changed = true; 1523 } 1524 } 1525 1526 if (II->use_empty()) { 1527 II->eraseFromParent(); 1528 Changed = true; 1529 } 1530 return Changed; 1531 } 1532 1533 static bool 1534 tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, 1535 SmallVectorImpl<Instruction *> &ToRemove) { 1536 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B, 1537 ConstraintInfo &Info) { 1538 auto R = Info.getConstraintForSolving(Pred, A, B); 1539 if (R.size() < 2 || !R.isValid(Info)) 1540 return false; 1541 1542 auto &CSToUse = Info.getCS(R.IsSigned); 1543 return CSToUse.isConditionImplied(R.Coefficients); 1544 }; 1545 1546 bool Changed = false; 1547 if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) { 1548 // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and 1549 // can be simplified to a regular sub. 1550 Value *A = II->getArgOperand(0); 1551 Value *B = II->getArgOperand(1); 1552 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) || 1553 !DoesConditionHold(CmpInst::ICMP_SGE, B, 1554 ConstantInt::get(A->getType(), 0), Info)) 1555 return false; 1556 Changed = replaceSubOverflowUses(II, A, B, ToRemove); 1557 } 1558 return Changed; 1559 } 1560 1561 static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, 1562 ScalarEvolution &SE, 1563 OptimizationRemarkEmitter &ORE) { 1564 bool Changed = false; 1565 DT.updateDFSNumbers(); 1566 SmallVector<Value *> FunctionArgs; 1567 for (Value &Arg : F.args()) 1568 FunctionArgs.push_back(&Arg); 1569 ConstraintInfo Info(F.getParent()->getDataLayout(), FunctionArgs); 1570 State S(DT, LI, SE); 1571 std::unique_ptr<Module> ReproducerModule( 1572 DumpReproducers ? new Module(F.getName(), F.getContext()) : nullptr); 1573 1574 // First, collect conditions implied by branches and blocks with their 1575 // Dominator DFS in and out numbers. 1576 for (BasicBlock &BB : F) { 1577 if (!DT.getNode(&BB)) 1578 continue; 1579 S.addInfoFor(BB); 1580 } 1581 1582 // Next, sort worklist by dominance, so that dominating conditions to check 1583 // and facts come before conditions and facts dominated by them. If a 1584 // condition to check and a fact have the same numbers, conditional facts come 1585 // first. Assume facts and checks are ordered according to their relative 1586 // order in the containing basic block. Also make sure conditions with 1587 // constant operands come before conditions without constant operands. This 1588 // increases the effectiveness of the current signed <-> unsigned fact 1589 // transfer logic. 1590 stable_sort(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) { 1591 auto HasNoConstOp = [](const FactOrCheck &B) { 1592 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0); 1593 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1); 1594 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1); 1595 }; 1596 // If both entries have the same In numbers, conditional facts come first. 1597 // Otherwise use the relative order in the basic block. 1598 if (A.NumIn == B.NumIn) { 1599 if (A.isConditionFact() && B.isConditionFact()) { 1600 bool NoConstOpA = HasNoConstOp(A); 1601 bool NoConstOpB = HasNoConstOp(B); 1602 return NoConstOpA < NoConstOpB; 1603 } 1604 if (A.isConditionFact()) 1605 return true; 1606 if (B.isConditionFact()) 1607 return false; 1608 auto *InstA = A.getContextInst(); 1609 auto *InstB = B.getContextInst(); 1610 return InstA->comesBefore(InstB); 1611 } 1612 return A.NumIn < B.NumIn; 1613 }); 1614 1615 SmallVector<Instruction *> ToRemove; 1616 1617 // Finally, process ordered worklist and eliminate implied conditions. 1618 SmallVector<StackEntry, 16> DFSInStack; 1619 SmallVector<ReproducerEntry> ReproducerCondStack; 1620 for (FactOrCheck &CB : S.WorkList) { 1621 // First, pop entries from the stack that are out-of-scope for CB. Remove 1622 // the corresponding entry from the constraint system. 1623 while (!DFSInStack.empty()) { 1624 auto &E = DFSInStack.back(); 1625 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut 1626 << "\n"); 1627 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n"); 1628 assert(E.NumIn <= CB.NumIn); 1629 if (CB.NumOut <= E.NumOut) 1630 break; 1631 LLVM_DEBUG({ 1632 dbgs() << "Removing "; 1633 dumpConstraint(Info.getCS(E.IsSigned).getLastConstraint(), 1634 Info.getValue2Index(E.IsSigned)); 1635 dbgs() << "\n"; 1636 }); 1637 removeEntryFromStack(E, Info, ReproducerModule.get(), ReproducerCondStack, 1638 DFSInStack); 1639 } 1640 1641 LLVM_DEBUG(dbgs() << "Processing "); 1642 1643 // For a block, check if any CmpInsts become known based on the current set 1644 // of constraints. 1645 if (CB.isCheck()) { 1646 Instruction *Inst = CB.getInstructionToSimplify(); 1647 if (!Inst) 1648 continue; 1649 LLVM_DEBUG(dbgs() << "condition to simplify: " << *Inst << "\n"); 1650 if (auto *II = dyn_cast<WithOverflowInst>(Inst)) { 1651 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove); 1652 } else if (auto *Cmp = dyn_cast<ICmpInst>(Inst)) { 1653 bool Simplified = checkAndReplaceCondition( 1654 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(), 1655 ReproducerModule.get(), ReproducerCondStack, S.DT, ToRemove); 1656 if (!Simplified && 1657 match(CB.getContextInst(), m_LogicalOp(m_Value(), m_Value()))) { 1658 Simplified = 1659 checkOrAndOpImpliedByOther(CB, Info, ReproducerModule.get(), 1660 ReproducerCondStack, DFSInStack); 1661 } 1662 Changed |= Simplified; 1663 } 1664 continue; 1665 } 1666 1667 auto AddFact = [&](CmpInst::Predicate Pred, Value *A, Value *B) { 1668 LLVM_DEBUG(dbgs() << "fact to add to the system: "; 1669 dumpUnpackedICmp(dbgs(), Pred, A, B); dbgs() << "\n"); 1670 if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) { 1671 LLVM_DEBUG( 1672 dbgs() 1673 << "Skip adding constraint because system has too many rows.\n"); 1674 return; 1675 } 1676 1677 Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack); 1678 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) 1679 ReproducerCondStack.emplace_back(Pred, A, B); 1680 1681 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack); 1682 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) { 1683 // Add dummy entries to ReproducerCondStack to keep it in sync with 1684 // DFSInStack. 1685 for (unsigned I = 0, 1686 E = (DFSInStack.size() - ReproducerCondStack.size()); 1687 I < E; ++I) { 1688 ReproducerCondStack.emplace_back(ICmpInst::BAD_ICMP_PREDICATE, 1689 nullptr, nullptr); 1690 } 1691 } 1692 }; 1693 1694 ICmpInst::Predicate Pred; 1695 if (!CB.isConditionFact()) { 1696 if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) { 1697 Pred = ICmpInst::getNonStrictPredicate(MinMax->getPredicate()); 1698 AddFact(Pred, MinMax, MinMax->getLHS()); 1699 AddFact(Pred, MinMax, MinMax->getRHS()); 1700 continue; 1701 } 1702 } 1703 1704 Value *A = nullptr, *B = nullptr; 1705 if (CB.isConditionFact()) { 1706 Pred = CB.Cond.Pred; 1707 A = CB.Cond.Op0; 1708 B = CB.Cond.Op1; 1709 if (CB.DoesHold.Pred != CmpInst::BAD_ICMP_PREDICATE && 1710 !Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) 1711 continue; 1712 } else { 1713 bool Matched = match(CB.Inst, m_Intrinsic<Intrinsic::assume>( 1714 m_ICmp(Pred, m_Value(A), m_Value(B)))); 1715 (void)Matched; 1716 assert(Matched && "Must have an assume intrinsic with a icmp operand"); 1717 } 1718 AddFact(Pred, A, B); 1719 } 1720 1721 if (ReproducerModule && !ReproducerModule->functions().empty()) { 1722 std::string S; 1723 raw_string_ostream StringS(S); 1724 ReproducerModule->print(StringS, nullptr); 1725 StringS.flush(); 1726 OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F); 1727 Rem << ore::NV("module") << S; 1728 ORE.emit(Rem); 1729 } 1730 1731 #ifndef NDEBUG 1732 unsigned SignedEntries = 1733 count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; }); 1734 assert(Info.getCS(false).size() - FunctionArgs.size() == 1735 DFSInStack.size() - SignedEntries && 1736 "updates to CS and DFSInStack are out of sync"); 1737 assert(Info.getCS(true).size() == SignedEntries && 1738 "updates to CS and DFSInStack are out of sync"); 1739 #endif 1740 1741 for (Instruction *I : ToRemove) 1742 I->eraseFromParent(); 1743 return Changed; 1744 } 1745 1746 PreservedAnalyses ConstraintEliminationPass::run(Function &F, 1747 FunctionAnalysisManager &AM) { 1748 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 1749 auto &LI = AM.getResult<LoopAnalysis>(F); 1750 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 1751 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F); 1752 if (!eliminateConstraints(F, DT, LI, SE, ORE)) 1753 return PreservedAnalyses::all(); 1754 1755 PreservedAnalyses PA; 1756 PA.preserve<DominatorTreeAnalysis>(); 1757 PA.preserve<LoopAnalysis>(); 1758 PA.preserve<ScalarEvolutionAnalysis>(); 1759 PA.preserveSet<CFGAnalyses>(); 1760 return PA; 1761 } 1762