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