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/ValueTracking.h" 22 #include "llvm/IR/Dominators.h" 23 #include "llvm/IR/Function.h" 24 #include "llvm/IR/IRBuilder.h" 25 #include "llvm/IR/Instructions.h" 26 #include "llvm/IR/PatternMatch.h" 27 #include "llvm/InitializePasses.h" 28 #include "llvm/Pass.h" 29 #include "llvm/Support/Debug.h" 30 #include "llvm/Support/DebugCounter.h" 31 #include "llvm/Support/MathExtras.h" 32 #include "llvm/Transforms/Scalar.h" 33 34 #include <string> 35 36 using namespace llvm; 37 using namespace PatternMatch; 38 39 #define DEBUG_TYPE "constraint-elimination" 40 41 STATISTIC(NumCondsRemoved, "Number of instructions removed"); 42 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated", 43 "Controls which conditions are eliminated"); 44 45 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max(); 46 static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min(); 47 48 namespace { 49 50 class ConstraintInfo; 51 52 struct StackEntry { 53 unsigned NumIn; 54 unsigned NumOut; 55 bool IsNot; 56 bool IsSigned = false; 57 /// Variables that can be removed from the system once the stack entry gets 58 /// removed. 59 SmallVector<Value *, 2> ValuesToRelease; 60 61 StackEntry(unsigned NumIn, unsigned NumOut, bool IsNot, bool IsSigned, 62 SmallVector<Value *, 2> ValuesToRelease) 63 : NumIn(NumIn), NumOut(NumOut), IsNot(IsNot), IsSigned(IsSigned), 64 ValuesToRelease(ValuesToRelease) {} 65 }; 66 67 /// Struct to express a pre-condition of the form %Op0 Pred %Op1. 68 struct PreconditionTy { 69 CmpInst::Predicate Pred; 70 Value *Op0; 71 Value *Op1; 72 73 PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1) 74 : Pred(Pred), Op0(Op0), Op1(Op1) {} 75 }; 76 77 struct ConstraintTy { 78 SmallVector<int64_t, 8> Coefficients; 79 SmallVector<PreconditionTy, 2> Preconditions; 80 81 bool IsSigned = false; 82 bool IsEq = false; 83 84 ConstraintTy() = default; 85 86 ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned) 87 : Coefficients(Coefficients), IsSigned(IsSigned) {} 88 89 unsigned size() const { return Coefficients.size(); } 90 91 unsigned empty() const { return Coefficients.empty(); } 92 93 /// Returns true if any constraint has a non-zero coefficient for any of the 94 /// newly added indices. Zero coefficients for new indices are removed. If it 95 /// returns true, no new variable need to be added to the system. 96 bool needsNewIndices(const DenseMap<Value *, unsigned> &NewIndices) { 97 for (unsigned I = 0; I < NewIndices.size(); ++I) { 98 int64_t Last = Coefficients.pop_back_val(); 99 if (Last != 0) 100 return true; 101 } 102 return false; 103 } 104 105 /// Returns true if all preconditions for this list of constraints are 106 /// satisfied given \p CS and the corresponding \p Value2Index mapping. 107 bool isValid(const ConstraintInfo &Info) const; 108 }; 109 110 /// Wrapper encapsulating separate constraint systems and corresponding value 111 /// mappings for both unsigned and signed information. Facts are added to and 112 /// conditions are checked against the corresponding system depending on the 113 /// signed-ness of their predicates. While the information is kept separate 114 /// based on signed-ness, certain conditions can be transferred between the two 115 /// systems. 116 class ConstraintInfo { 117 DenseMap<Value *, unsigned> UnsignedValue2Index; 118 DenseMap<Value *, unsigned> SignedValue2Index; 119 120 ConstraintSystem UnsignedCS; 121 ConstraintSystem SignedCS; 122 123 public: 124 DenseMap<Value *, unsigned> &getValue2Index(bool Signed) { 125 return Signed ? SignedValue2Index : UnsignedValue2Index; 126 } 127 const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const { 128 return Signed ? SignedValue2Index : UnsignedValue2Index; 129 } 130 131 ConstraintSystem &getCS(bool Signed) { 132 return Signed ? SignedCS : UnsignedCS; 133 } 134 const ConstraintSystem &getCS(bool Signed) const { 135 return Signed ? SignedCS : UnsignedCS; 136 } 137 138 void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); } 139 void popLastNVariables(bool Signed, unsigned N) { 140 getCS(Signed).popLastNVariables(N); 141 } 142 143 bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const; 144 145 void addFact(CmpInst::Predicate Pred, Value *A, Value *B, bool IsNegated, 146 unsigned NumIn, unsigned NumOut, 147 SmallVectorImpl<StackEntry> &DFSInStack); 148 149 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of 150 /// constraints, using indices from the corresponding constraint system. 151 /// Additional indices for newly discovered values are added to \p NewIndices. 152 ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, 153 DenseMap<Value *, unsigned> &NewIndices) const; 154 155 /// Turn a condition \p CmpI into a vector of constraints, using indices from 156 /// the corresponding constraint system. Additional indices for newly 157 /// discovered values are added to \p NewIndices. 158 ConstraintTy getConstraint(CmpInst *Cmp, 159 DenseMap<Value *, unsigned> &NewIndices) const { 160 return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0), 161 Cmp->getOperand(1), NewIndices); 162 } 163 164 /// Try to add information from \p A \p Pred \p B to the unsigned/signed 165 /// system if \p Pred is signed/unsigned. 166 void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B, 167 bool IsNegated, unsigned NumIn, unsigned NumOut, 168 SmallVectorImpl<StackEntry> &DFSInStack); 169 }; 170 171 } // namespace 172 173 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The 174 // sum of the pairs equals \p V. The first pair is the constant-factor and X 175 // must be nullptr. If the expression cannot be decomposed, returns an empty 176 // vector. 177 static SmallVector<std::pair<int64_t, Value *>, 4> 178 decompose(Value *V, SmallVector<PreconditionTy, 4> &Preconditions, 179 bool IsSigned) { 180 181 auto CanUseSExt = [](ConstantInt *CI) { 182 const APInt &Val = CI->getValue(); 183 return Val.sgt(MinSignedConstraintValue) && Val.slt(MaxConstraintValue); 184 }; 185 // Decompose \p V used with a signed predicate. 186 if (IsSigned) { 187 if (auto *CI = dyn_cast<ConstantInt>(V)) { 188 if (CanUseSExt(CI)) 189 return {{CI->getSExtValue(), nullptr}}; 190 } 191 192 return {{0, nullptr}, {1, V}}; 193 } 194 195 if (auto *CI = dyn_cast<ConstantInt>(V)) { 196 if (CI->uge(MaxConstraintValue)) 197 return {}; 198 return {{CI->getZExtValue(), nullptr}}; 199 } 200 auto *GEP = dyn_cast<GetElementPtrInst>(V); 201 if (GEP && GEP->getNumOperands() == 2 && GEP->isInBounds()) { 202 Value *Op0, *Op1; 203 ConstantInt *CI; 204 205 // If the index is zero-extended, it is guaranteed to be positive. 206 if (match(GEP->getOperand(GEP->getNumOperands() - 1), 207 m_ZExt(m_Value(Op0)))) { 208 if (match(Op0, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && 209 CanUseSExt(CI)) 210 return {{0, nullptr}, 211 {1, GEP->getPointerOperand()}, 212 {std::pow(int64_t(2), CI->getSExtValue()), Op1}}; 213 if (match(Op0, m_NSWAdd(m_Value(Op1), m_ConstantInt(CI))) && 214 CanUseSExt(CI)) 215 return {{CI->getSExtValue(), nullptr}, 216 {1, GEP->getPointerOperand()}, 217 {1, Op1}}; 218 return {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}}; 219 } 220 221 if (match(GEP->getOperand(GEP->getNumOperands() - 1), m_ConstantInt(CI)) && 222 !CI->isNegative() && CanUseSExt(CI)) 223 return {{CI->getSExtValue(), nullptr}, {1, GEP->getPointerOperand()}}; 224 225 SmallVector<std::pair<int64_t, Value *>, 4> Result; 226 if (match(GEP->getOperand(GEP->getNumOperands() - 1), 227 m_NUWShl(m_Value(Op0), m_ConstantInt(CI))) && 228 CanUseSExt(CI)) 229 Result = {{0, nullptr}, 230 {1, GEP->getPointerOperand()}, 231 {std::pow(int64_t(2), CI->getSExtValue()), Op0}}; 232 else if (match(GEP->getOperand(GEP->getNumOperands() - 1), 233 m_NSWAdd(m_Value(Op0), m_ConstantInt(CI))) && 234 CanUseSExt(CI)) 235 Result = {{CI->getSExtValue(), nullptr}, 236 {1, GEP->getPointerOperand()}, 237 {1, Op0}}; 238 else { 239 Op0 = GEP->getOperand(GEP->getNumOperands() - 1); 240 Result = {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}}; 241 } 242 // If Op0 is signed non-negative, the GEP is increasing monotonically and 243 // can be de-composed. 244 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0, 245 ConstantInt::get(Op0->getType(), 0)); 246 return Result; 247 } 248 249 Value *Op0; 250 if (match(V, m_ZExt(m_Value(Op0)))) 251 V = Op0; 252 253 Value *Op1; 254 ConstantInt *CI; 255 if (match(V, m_NUWAdd(m_Value(Op0), m_ConstantInt(CI))) && 256 !CI->uge(MaxConstraintValue)) 257 return {{CI->getZExtValue(), nullptr}, {1, Op0}}; 258 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() && 259 CanUseSExt(CI)) { 260 Preconditions.emplace_back( 261 CmpInst::ICMP_UGE, Op0, 262 ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1)); 263 return {{CI->getSExtValue(), nullptr}, {1, Op0}}; 264 } 265 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) 266 return {{0, nullptr}, {1, Op0}, {1, Op1}}; 267 268 if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && CanUseSExt(CI)) 269 return {{-1 * CI->getSExtValue(), nullptr}, {1, Op0}}; 270 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) 271 return {{0, nullptr}, {1, Op0}, {-1, Op1}}; 272 273 return {{0, nullptr}, {1, V}}; 274 } 275 276 ConstraintTy 277 ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, 278 DenseMap<Value *, unsigned> &NewIndices) const { 279 bool IsEq = false; 280 // Try to convert Pred to one of ULE/SLT/SLE/SLT. 281 switch (Pred) { 282 case CmpInst::ICMP_UGT: 283 case CmpInst::ICMP_UGE: 284 case CmpInst::ICMP_SGT: 285 case CmpInst::ICMP_SGE: { 286 Pred = CmpInst::getSwappedPredicate(Pred); 287 std::swap(Op0, Op1); 288 break; 289 } 290 case CmpInst::ICMP_EQ: 291 if (match(Op1, m_Zero())) { 292 Pred = CmpInst::ICMP_ULE; 293 } else { 294 IsEq = true; 295 Pred = CmpInst::ICMP_ULE; 296 } 297 break; 298 case CmpInst::ICMP_NE: 299 if (!match(Op1, m_Zero())) 300 return {}; 301 Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT); 302 std::swap(Op0, Op1); 303 break; 304 default: 305 break; 306 } 307 308 // Only ULE and ULT predicates are supported at the moment. 309 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT && 310 Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT) 311 return {}; 312 313 SmallVector<PreconditionTy, 4> Preconditions; 314 bool IsSigned = CmpInst::isSigned(Pred); 315 auto &Value2Index = getValue2Index(IsSigned); 316 auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(), 317 Preconditions, IsSigned); 318 auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(), 319 Preconditions, IsSigned); 320 // Skip if decomposing either of the values failed. 321 if (ADec.empty() || BDec.empty()) 322 return {}; 323 324 int64_t Offset1 = ADec[0].first; 325 int64_t Offset2 = BDec[0].first; 326 Offset1 *= -1; 327 328 // Create iterator ranges that skip the constant-factor. 329 auto VariablesA = llvm::drop_begin(ADec); 330 auto VariablesB = llvm::drop_begin(BDec); 331 332 // First try to look up \p V in Value2Index and NewIndices. Otherwise add a 333 // new entry to NewIndices. 334 auto GetOrAddIndex = [&Value2Index, &NewIndices](Value *V) -> unsigned { 335 auto V2I = Value2Index.find(V); 336 if (V2I != Value2Index.end()) 337 return V2I->second; 338 auto Insert = 339 NewIndices.insert({V, Value2Index.size() + NewIndices.size() + 1}); 340 return Insert.first->second; 341 }; 342 343 // Make sure all variables have entries in Value2Index or NewIndices. 344 for (const auto &KV : 345 concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB)) 346 GetOrAddIndex(KV.second); 347 348 // Build result constraint, by first adding all coefficients from A and then 349 // subtracting all coefficients from B. 350 ConstraintTy Res( 351 SmallVector<int64_t, 8>(Value2Index.size() + NewIndices.size() + 1, 0), 352 IsSigned); 353 Res.IsEq = IsEq; 354 auto &R = Res.Coefficients; 355 for (const auto &KV : VariablesA) 356 R[GetOrAddIndex(KV.second)] += KV.first; 357 358 for (const auto &KV : VariablesB) 359 R[GetOrAddIndex(KV.second)] -= KV.first; 360 361 int64_t OffsetSum; 362 if (AddOverflow(Offset1, Offset2, OffsetSum)) 363 return {}; 364 if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT)) 365 if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum)) 366 return {}; 367 R[0] = OffsetSum; 368 Res.Preconditions = std::move(Preconditions); 369 return Res; 370 } 371 372 bool ConstraintTy::isValid(const ConstraintInfo &Info) const { 373 return Coefficients.size() > 0 && 374 all_of(Preconditions, [&Info](const PreconditionTy &C) { 375 return Info.doesHold(C.Pred, C.Op0, C.Op1); 376 }); 377 } 378 379 bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A, 380 Value *B) const { 381 DenseMap<Value *, unsigned> NewIndices; 382 auto R = getConstraint(Pred, A, B, NewIndices); 383 384 if (!NewIndices.empty()) 385 return false; 386 387 // TODO: properly check NewIndices. 388 return NewIndices.empty() && R.Preconditions.empty() && !R.IsEq && 389 !R.empty() && 390 getCS(CmpInst::isSigned(Pred)).isConditionImplied(R.Coefficients); 391 } 392 393 void ConstraintInfo::transferToOtherSystem( 394 CmpInst::Predicate Pred, Value *A, Value *B, bool IsNegated, unsigned NumIn, 395 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) { 396 // Check if we can combine facts from the signed and unsigned systems to 397 // derive additional facts. 398 if (!A->getType()->isIntegerTy()) 399 return; 400 // FIXME: This currently depends on the order we add facts. Ideally we 401 // would first add all known facts and only then try to add additional 402 // facts. 403 switch (Pred) { 404 default: 405 break; 406 case CmpInst::ICMP_ULT: 407 // If B is a signed positive constant, A >=s 0 and A <s B. 408 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) { 409 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), 410 IsNegated, NumIn, NumOut, DFSInStack); 411 addFact(CmpInst::ICMP_SLT, A, B, IsNegated, NumIn, NumOut, DFSInStack); 412 } 413 break; 414 case CmpInst::ICMP_SLT: 415 if (doesHold(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0))) 416 addFact(CmpInst::ICMP_ULT, A, B, IsNegated, NumIn, NumOut, DFSInStack); 417 break; 418 case CmpInst::ICMP_SGT: 419 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), -1))) 420 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), 421 IsNegated, NumIn, NumOut, DFSInStack); 422 break; 423 case CmpInst::ICMP_SGE: 424 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) { 425 addFact(CmpInst::ICMP_UGE, A, B, IsNegated, NumIn, NumOut, DFSInStack); 426 } 427 break; 428 } 429 } 430 431 namespace { 432 /// Represents either a condition that holds on entry to a block or a basic 433 /// block, with their respective Dominator DFS in and out numbers. 434 struct ConstraintOrBlock { 435 unsigned NumIn; 436 unsigned NumOut; 437 bool IsBlock; 438 bool Not; 439 union { 440 BasicBlock *BB; 441 CmpInst *Condition; 442 }; 443 444 ConstraintOrBlock(DomTreeNode *DTN) 445 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true), 446 BB(DTN->getBlock()) {} 447 ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not) 448 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false), 449 Not(Not), Condition(Condition) {} 450 }; 451 452 /// Keep state required to build worklist. 453 struct State { 454 DominatorTree &DT; 455 SmallVector<ConstraintOrBlock, 64> WorkList; 456 457 State(DominatorTree &DT) : DT(DT) {} 458 459 /// Process block \p BB and add known facts to work-list. 460 void addInfoFor(BasicBlock &BB); 461 462 /// Returns true if we can add a known condition from BB to its successor 463 /// block Succ. Each predecessor of Succ can either be BB or be dominated 464 /// by Succ (e.g. the case when adding a condition from a pre-header to a 465 /// loop header). 466 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const { 467 if (BB.getSingleSuccessor()) { 468 assert(BB.getSingleSuccessor() == Succ); 469 return DT.properlyDominates(&BB, Succ); 470 } 471 return any_of(successors(&BB), 472 [Succ](const BasicBlock *S) { return S != Succ; }) && 473 all_of(predecessors(Succ), [&BB, Succ, this](BasicBlock *Pred) { 474 return Pred == &BB || DT.dominates(Succ, Pred); 475 }); 476 } 477 }; 478 479 } // namespace 480 481 #ifndef NDEBUG 482 static void dumpWithNames(const ConstraintSystem &CS, 483 DenseMap<Value *, unsigned> &Value2Index) { 484 SmallVector<std::string> Names(Value2Index.size(), ""); 485 for (auto &KV : Value2Index) { 486 Names[KV.second - 1] = std::string("%") + KV.first->getName().str(); 487 } 488 CS.dump(Names); 489 } 490 491 static void dumpWithNames(ArrayRef<int64_t> C, 492 DenseMap<Value *, unsigned> &Value2Index) { 493 ConstraintSystem CS; 494 CS.addVariableRowFill(C); 495 dumpWithNames(CS, Value2Index); 496 } 497 #endif 498 499 void State::addInfoFor(BasicBlock &BB) { 500 WorkList.emplace_back(DT.getNode(&BB)); 501 502 // True as long as long as the current instruction is guaranteed to execute. 503 bool GuaranteedToExecute = true; 504 // Scan BB for assume calls. 505 // TODO: also use this scan to queue conditions to simplify, so we can 506 // interleave facts from assumes and conditions to simplify in a single 507 // basic block. And to skip another traversal of each basic block when 508 // simplifying. 509 for (Instruction &I : BB) { 510 Value *Cond; 511 // For now, just handle assumes with a single compare as condition. 512 if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) && 513 isa<ICmpInst>(Cond)) { 514 if (GuaranteedToExecute) { 515 // The assume is guaranteed to execute when BB is entered, hence Cond 516 // holds on entry to BB. 517 WorkList.emplace_back(DT.getNode(&BB), cast<ICmpInst>(Cond), false); 518 } else { 519 // Otherwise the condition only holds in the successors. 520 for (BasicBlock *Succ : successors(&BB)) { 521 if (!canAddSuccessor(BB, Succ)) 522 continue; 523 WorkList.emplace_back(DT.getNode(Succ), cast<ICmpInst>(Cond), false); 524 } 525 } 526 } 527 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I); 528 } 529 530 auto *Br = dyn_cast<BranchInst>(BB.getTerminator()); 531 if (!Br || !Br->isConditional()) 532 return; 533 534 // If the condition is an OR of 2 compares and the false successor only has 535 // the current block as predecessor, queue both negated conditions for the 536 // false successor. 537 Value *Op0, *Op1; 538 if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1))) && 539 isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) { 540 BasicBlock *FalseSuccessor = Br->getSuccessor(1); 541 if (canAddSuccessor(BB, FalseSuccessor)) { 542 WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<ICmpInst>(Op0), 543 true); 544 WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<ICmpInst>(Op1), 545 true); 546 } 547 return; 548 } 549 550 // If the condition is an AND of 2 compares and the true successor only has 551 // the current block as predecessor, queue both conditions for the true 552 // successor. 553 if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) && 554 isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) { 555 BasicBlock *TrueSuccessor = Br->getSuccessor(0); 556 if (canAddSuccessor(BB, TrueSuccessor)) { 557 WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<ICmpInst>(Op0), 558 false); 559 WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<ICmpInst>(Op1), 560 false); 561 } 562 return; 563 } 564 565 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition()); 566 if (!CmpI) 567 return; 568 if (canAddSuccessor(BB, Br->getSuccessor(0))) 569 WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false); 570 if (canAddSuccessor(BB, Br->getSuccessor(1))) 571 WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true); 572 } 573 574 void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B, 575 bool IsNegated, unsigned NumIn, unsigned NumOut, 576 SmallVectorImpl<StackEntry> &DFSInStack) { 577 // If the constraint has a pre-condition, skip the constraint if it does not 578 // hold. 579 DenseMap<Value *, unsigned> NewIndices; 580 auto R = getConstraint(Pred, A, B, NewIndices); 581 if (!R.isValid(*this)) 582 return; 583 584 //LLVM_DEBUG(dbgs() << "Adding " << *Condition << " " << IsNegated << "\n"); 585 bool Added = false; 586 assert(CmpInst::isSigned(Pred) == R.IsSigned && 587 "condition and constraint signs must match"); 588 auto &CSToUse = getCS(R.IsSigned); 589 if (R.Coefficients.empty()) 590 return; 591 592 Added |= CSToUse.addVariableRowFill(R.Coefficients); 593 594 // If R has been added to the system, queue it for removal once it goes 595 // out-of-scope. 596 if (Added) { 597 SmallVector<Value *, 2> ValuesToRelease; 598 for (auto &KV : NewIndices) { 599 getValue2Index(R.IsSigned).insert(KV); 600 ValuesToRelease.push_back(KV.first); 601 } 602 603 LLVM_DEBUG({ 604 dbgs() << " constraint: "; 605 dumpWithNames(R.Coefficients, getValue2Index(R.IsSigned)); 606 }); 607 608 DFSInStack.emplace_back(NumIn, NumOut, IsNegated, R.IsSigned, 609 ValuesToRelease); 610 611 if (R.IsEq) { 612 // Also add the inverted constraint for equality constraints. 613 for (auto &Coeff : R.Coefficients) 614 Coeff *= -1; 615 CSToUse.addVariableRowFill(R.Coefficients); 616 617 DFSInStack.emplace_back(NumIn, NumOut, IsNegated, R.IsSigned, 618 SmallVector<Value *, 2>()); 619 } 620 } 621 } 622 623 static void 624 tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, 625 SmallVectorImpl<Instruction *> &ToRemove) { 626 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B, 627 ConstraintInfo &Info) { 628 DenseMap<Value *, unsigned> NewIndices; 629 auto R = Info.getConstraint(Pred, A, B, NewIndices); 630 if (R.size() < 2 || R.needsNewIndices(NewIndices) || !R.isValid(Info)) 631 return false; 632 633 auto &CSToUse = Info.getCS(CmpInst::isSigned(Pred)); 634 return CSToUse.isConditionImplied(R.Coefficients); 635 }; 636 637 if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) { 638 // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and 639 // can be simplified to a regular sub. 640 Value *A = II->getArgOperand(0); 641 Value *B = II->getArgOperand(1); 642 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) || 643 !DoesConditionHold(CmpInst::ICMP_SGE, B, 644 ConstantInt::get(A->getType(), 0), Info)) 645 return; 646 647 IRBuilder<> Builder(II->getParent(), II->getIterator()); 648 Value *Sub = nullptr; 649 for (User *U : make_early_inc_range(II->users())) { 650 if (match(U, m_ExtractValue<0>(m_Value()))) { 651 if (!Sub) 652 Sub = Builder.CreateSub(A, B); 653 U->replaceAllUsesWith(Sub); 654 } else if (match(U, m_ExtractValue<1>(m_Value()))) 655 U->replaceAllUsesWith(Builder.getFalse()); 656 else 657 continue; 658 659 if (U->use_empty()) { 660 auto *I = cast<Instruction>(U); 661 ToRemove.push_back(I); 662 I->setOperand(0, PoisonValue::get(II->getType())); 663 } 664 } 665 666 if (II->use_empty()) 667 II->eraseFromParent(); 668 } 669 } 670 671 static bool eliminateConstraints(Function &F, DominatorTree &DT) { 672 bool Changed = false; 673 DT.updateDFSNumbers(); 674 675 ConstraintInfo Info; 676 State S(DT); 677 678 // First, collect conditions implied by branches and blocks with their 679 // Dominator DFS in and out numbers. 680 for (BasicBlock &BB : F) { 681 if (!DT.getNode(&BB)) 682 continue; 683 S.addInfoFor(BB); 684 } 685 686 // Next, sort worklist by dominance, so that dominating blocks and conditions 687 // come before blocks and conditions dominated by them. If a block and a 688 // condition have the same numbers, the condition comes before the block, as 689 // it holds on entry to the block. 690 stable_sort(S.WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) { 691 return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock); 692 }); 693 694 SmallVector<Instruction *> ToRemove; 695 696 // Finally, process ordered worklist and eliminate implied conditions. 697 SmallVector<StackEntry, 16> DFSInStack; 698 for (ConstraintOrBlock &CB : S.WorkList) { 699 // First, pop entries from the stack that are out-of-scope for CB. Remove 700 // the corresponding entry from the constraint system. 701 while (!DFSInStack.empty()) { 702 auto &E = DFSInStack.back(); 703 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut 704 << "\n"); 705 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n"); 706 assert(E.NumIn <= CB.NumIn); 707 if (CB.NumOut <= E.NumOut) 708 break; 709 LLVM_DEBUG({ 710 dbgs() << "Removing "; 711 dumpWithNames(Info.getCS(E.IsSigned).getLastConstraint(), 712 Info.getValue2Index(E.IsSigned)); 713 dbgs() << "\n"; 714 }); 715 716 Info.popLastConstraint(E.IsSigned); 717 // Remove variables in the system that went out of scope. 718 auto &Mapping = Info.getValue2Index(E.IsSigned); 719 for (Value *V : E.ValuesToRelease) 720 Mapping.erase(V); 721 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size()); 722 DFSInStack.pop_back(); 723 } 724 725 LLVM_DEBUG({ 726 dbgs() << "Processing "; 727 if (CB.IsBlock) 728 dbgs() << *CB.BB; 729 else 730 dbgs() << *CB.Condition; 731 dbgs() << "\n"; 732 }); 733 734 // For a block, check if any CmpInsts become known based on the current set 735 // of constraints. 736 if (CB.IsBlock) { 737 for (Instruction &I : make_early_inc_range(*CB.BB)) { 738 if (auto *II = dyn_cast<WithOverflowInst>(&I)) { 739 tryToSimplifyOverflowMath(II, Info, ToRemove); 740 continue; 741 } 742 auto *Cmp = dyn_cast<ICmpInst>(&I); 743 if (!Cmp) 744 continue; 745 746 DenseMap<Value *, unsigned> NewIndices; 747 auto R = Info.getConstraint(Cmp, NewIndices); 748 if (R.IsEq || R.empty() || R.needsNewIndices(NewIndices) || 749 !R.isValid(Info)) 750 continue; 751 752 auto &CSToUse = Info.getCS(R.IsSigned); 753 if (CSToUse.isConditionImplied(R.Coefficients)) { 754 if (!DebugCounter::shouldExecute(EliminatedCounter)) 755 continue; 756 757 LLVM_DEBUG({ 758 dbgs() << "Condition " << *Cmp 759 << " implied by dominating constraints\n"; 760 dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned)); 761 }); 762 Cmp->replaceUsesWithIf( 763 ConstantInt::getTrue(F.getParent()->getContext()), [](Use &U) { 764 // Conditions in an assume trivially simplify to true. Skip uses 765 // in assume calls to not destroy the available information. 766 auto *II = dyn_cast<IntrinsicInst>(U.getUser()); 767 return !II || II->getIntrinsicID() != Intrinsic::assume; 768 }); 769 NumCondsRemoved++; 770 Changed = true; 771 } 772 if (CSToUse.isConditionImplied( 773 ConstraintSystem::negate(R.Coefficients))) { 774 if (!DebugCounter::shouldExecute(EliminatedCounter)) 775 continue; 776 777 LLVM_DEBUG({ 778 dbgs() << "Condition !" << *Cmp 779 << " implied by dominating constraints\n"; 780 dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned)); 781 }); 782 Cmp->replaceAllUsesWith( 783 ConstantInt::getFalse(F.getParent()->getContext())); 784 NumCondsRemoved++; 785 Changed = true; 786 } 787 } 788 continue; 789 } 790 791 // Set up a function to restore the predicate at the end of the scope if it 792 // has been negated. Negate the predicate in-place, if required. 793 auto *CI = dyn_cast<ICmpInst>(CB.Condition); 794 auto PredicateRestorer = make_scope_exit([CI, &CB]() { 795 if (CB.Not && CI) 796 CI->setPredicate(CI->getInversePredicate()); 797 }); 798 if (CB.Not) { 799 if (CI) { 800 CI->setPredicate(CI->getInversePredicate()); 801 } else { 802 LLVM_DEBUG(dbgs() << "Can only negate compares so far.\n"); 803 continue; 804 } 805 } 806 807 ICmpInst::Predicate Pred; 808 Value *A, *B; 809 if (match(CB.Condition, m_ICmp(Pred, m_Value(A), m_Value(B)))) { 810 // Otherwise, add the condition to the system and stack, if we can 811 // transform it into a constraint. 812 Info.addFact(Pred, A, B, CB.Not, CB.NumIn, CB.NumOut, DFSInStack); 813 Info.transferToOtherSystem(Pred, A, B, CB.Not, CB.NumIn, CB.NumOut, 814 DFSInStack); 815 } 816 } 817 818 #ifndef NDEBUG 819 unsigned SignedEntries = 820 count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; }); 821 assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries && 822 "updates to CS and DFSInStack are out of sync"); 823 assert(Info.getCS(true).size() == SignedEntries && 824 "updates to CS and DFSInStack are out of sync"); 825 #endif 826 827 for (Instruction *I : ToRemove) 828 I->eraseFromParent(); 829 return Changed; 830 } 831 832 PreservedAnalyses ConstraintEliminationPass::run(Function &F, 833 FunctionAnalysisManager &AM) { 834 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 835 if (!eliminateConstraints(F, DT)) 836 return PreservedAnalyses::all(); 837 838 PreservedAnalyses PA; 839 PA.preserve<DominatorTreeAnalysis>(); 840 PA.preserveSet<CFGAnalyses>(); 841 return PA; 842 } 843 844 namespace { 845 846 class ConstraintElimination : public FunctionPass { 847 public: 848 static char ID; 849 850 ConstraintElimination() : FunctionPass(ID) { 851 initializeConstraintEliminationPass(*PassRegistry::getPassRegistry()); 852 } 853 854 bool runOnFunction(Function &F) override { 855 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 856 return eliminateConstraints(F, DT); 857 } 858 859 void getAnalysisUsage(AnalysisUsage &AU) const override { 860 AU.setPreservesCFG(); 861 AU.addRequired<DominatorTreeWrapperPass>(); 862 AU.addPreserved<GlobalsAAWrapperPass>(); 863 AU.addPreserved<DominatorTreeWrapperPass>(); 864 } 865 }; 866 867 } // end anonymous namespace 868 869 char ConstraintElimination::ID = 0; 870 871 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination", 872 "Constraint Elimination", false, false) 873 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 874 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 875 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination", 876 "Constraint Elimination", false, false) 877 878 FunctionPass *llvm::createConstraintEliminationPass() { 879 return new ConstraintElimination(); 880 } 881