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/IR/DataLayout.h" 22 #include "llvm/IR/Dominators.h" 23 #include "llvm/IR/Function.h" 24 #include "llvm/IR/Instructions.h" 25 #include "llvm/IR/PatternMatch.h" 26 #include "llvm/InitializePasses.h" 27 #include "llvm/Pass.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/DebugCounter.h" 30 #include "llvm/Transforms/Scalar.h" 31 32 using namespace llvm; 33 using namespace PatternMatch; 34 35 #define DEBUG_TYPE "constraint-elimination" 36 37 STATISTIC(NumCondsRemoved, "Number of instructions removed"); 38 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated", 39 "Controls which conditions are eliminated"); 40 41 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max(); 42 43 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The 44 // sum of the pairs equals \p V. The first pair is the constant-factor and X 45 // must be nullptr. If the expression cannot be decomposed, returns an empty 46 // vector. 47 static SmallVector<std::pair<int64_t, Value *>, 4> decompose(Value *V) { 48 if (auto *CI = dyn_cast<ConstantInt>(V)) { 49 if (CI->isNegative() || CI->uge(MaxConstraintValue)) 50 return {}; 51 return {{CI->getSExtValue(), nullptr}}; 52 } 53 auto *GEP = dyn_cast<GetElementPtrInst>(V); 54 if (GEP && GEP->getNumOperands() == 2) { 55 if (isa<ConstantInt>(GEP->getOperand(GEP->getNumOperands() - 1))) { 56 return {{cast<ConstantInt>(GEP->getOperand(GEP->getNumOperands() - 1)) 57 ->getSExtValue(), 58 nullptr}, 59 {1, GEP->getPointerOperand()}}; 60 } 61 Value *Op0; 62 ConstantInt *CI; 63 if (match(GEP->getOperand(GEP->getNumOperands() - 1), 64 m_NUWShl(m_Value(Op0), m_ConstantInt(CI)))) 65 return {{0, nullptr}, 66 {1, GEP->getPointerOperand()}, 67 {std::pow(int64_t(2), CI->getSExtValue()), Op0}}; 68 if (match(GEP->getOperand(GEP->getNumOperands() - 1), 69 m_ZExt(m_NUWShl(m_Value(Op0), m_ConstantInt(CI))))) 70 return {{0, nullptr}, 71 {1, GEP->getPointerOperand()}, 72 {std::pow(int64_t(2), CI->getSExtValue()), Op0}}; 73 74 return {{0, nullptr}, 75 {1, GEP->getPointerOperand()}, 76 {1, GEP->getOperand(GEP->getNumOperands() - 1)}}; 77 } 78 79 Value *Op0; 80 Value *Op1; 81 ConstantInt *CI; 82 if (match(V, m_NUWAdd(m_Value(Op0), m_ConstantInt(CI)))) 83 return {{CI->getSExtValue(), nullptr}, {1, Op0}}; 84 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) 85 return {{0, nullptr}, {1, Op0}, {1, Op1}}; 86 87 if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI)))) 88 return {{-1 * CI->getSExtValue(), nullptr}, {1, Op0}}; 89 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) 90 return {{0, nullptr}, {1, Op0}, {1, Op1}}; 91 92 return {{0, nullptr}, {1, V}}; 93 } 94 95 struct ConstraintTy { 96 SmallVector<int64_t, 8> Coefficients; 97 98 ConstraintTy(SmallVector<int64_t, 8> Coefficients) 99 : Coefficients(Coefficients) {} 100 101 unsigned size() const { return Coefficients.size(); } 102 }; 103 104 /// Turn a condition \p CmpI into a constraint vector, using indices from \p 105 /// Value2Index. If \p ShouldAdd is true, new indices are added for values not 106 /// yet in \p Value2Index. 107 static SmallVector<ConstraintTy, 4> 108 getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, 109 DenseMap<Value *, unsigned> &Value2Index, bool ShouldAdd) { 110 int64_t Offset1 = 0; 111 int64_t Offset2 = 0; 112 113 auto TryToGetIndex = [ShouldAdd, 114 &Value2Index](Value *V) -> Optional<unsigned> { 115 if (ShouldAdd) { 116 Value2Index.insert({V, Value2Index.size() + 1}); 117 return Value2Index[V]; 118 } 119 auto I = Value2Index.find(V); 120 if (I == Value2Index.end()) 121 return None; 122 return I->second; 123 }; 124 125 if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE) 126 return getConstraint(CmpInst::getSwappedPredicate(Pred), Op1, Op0, 127 Value2Index, ShouldAdd); 128 129 if (Pred == CmpInst::ICMP_EQ) { 130 auto A = getConstraint(CmpInst::ICMP_UGE, Op0, Op1, Value2Index, ShouldAdd); 131 auto B = getConstraint(CmpInst::ICMP_ULE, Op0, Op1, Value2Index, ShouldAdd); 132 append_range(A, B); 133 return A; 134 } 135 136 // Only ULE and ULT predicates are supported at the moment. 137 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT) 138 return {}; 139 140 auto ADec = decompose(Op0); 141 auto BDec = decompose(Op1); 142 // Skip if decomposing either of the values failed. 143 if (ADec.empty() || BDec.empty()) 144 return {}; 145 146 // Skip trivial constraints without any variables. 147 if (ADec.size() == 1 && BDec.size() == 1) 148 return {}; 149 150 Offset1 = ADec[0].first; 151 Offset2 = BDec[0].first; 152 Offset1 *= -1; 153 154 // Create iterator ranges that skip the constant-factor. 155 auto VariablesA = make_range(std::next(ADec.begin()), ADec.end()); 156 auto VariablesB = make_range(std::next(BDec.begin()), BDec.end()); 157 158 // Check if each referenced value in the constraint is already in the system 159 // or can be added (if ShouldAdd is true). 160 for (const auto &KV : 161 concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB)) 162 if (!TryToGetIndex(KV.second)) 163 return {}; 164 165 // Build result constraint, by first adding all coefficients from A and then 166 // subtracting all coefficients from B. 167 SmallVector<int64_t, 8> R(Value2Index.size() + 1, 0); 168 for (const auto &KV : VariablesA) 169 R[Value2Index[KV.second]] += KV.first; 170 171 for (const auto &KV : VariablesB) 172 R[Value2Index[KV.second]] -= KV.first; 173 174 R[0] = Offset1 + Offset2 + (Pred == CmpInst::ICMP_ULT ? -1 : 0); 175 return {R}; 176 } 177 178 static SmallVector<ConstraintTy, 4> 179 getConstraint(CmpInst *Cmp, DenseMap<Value *, unsigned> &Value2Index, 180 bool ShouldAdd) { 181 return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0), 182 Cmp->getOperand(1), Value2Index, ShouldAdd); 183 } 184 185 namespace { 186 /// Represents either a condition that holds on entry to a block or a basic 187 /// block, with their respective Dominator DFS in and out numbers. 188 struct ConstraintOrBlock { 189 unsigned NumIn; 190 unsigned NumOut; 191 bool IsBlock; 192 bool Not; 193 union { 194 BasicBlock *BB; 195 CmpInst *Condition; 196 }; 197 198 ConstraintOrBlock(DomTreeNode *DTN) 199 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true), 200 BB(DTN->getBlock()) {} 201 ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not) 202 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false), 203 Not(Not), Condition(Condition) {} 204 }; 205 206 struct StackEntry { 207 unsigned NumIn; 208 unsigned NumOut; 209 CmpInst *Condition; 210 bool IsNot; 211 212 StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot) 213 : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot) {} 214 }; 215 } // namespace 216 217 static bool eliminateConstraints(Function &F, DominatorTree &DT) { 218 bool Changed = false; 219 DT.updateDFSNumbers(); 220 ConstraintSystem CS; 221 222 SmallVector<ConstraintOrBlock, 64> WorkList; 223 224 // First, collect conditions implied by branches and blocks with their 225 // Dominator DFS in and out numbers. 226 for (BasicBlock &BB : F) { 227 if (!DT.getNode(&BB)) 228 continue; 229 WorkList.emplace_back(DT.getNode(&BB)); 230 231 auto *Br = dyn_cast<BranchInst>(BB.getTerminator()); 232 if (!Br || !Br->isConditional()) 233 continue; 234 235 // If the condition is an OR of 2 compares and the false successor only has 236 // the current block as predecessor, queue both negated conditions for the 237 // false successor. 238 Value *Op0, *Op1; 239 if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1))) && 240 match(Op0, m_Cmp()) && match(Op1, m_Cmp())) { 241 BasicBlock *FalseSuccessor = Br->getSuccessor(1); 242 if (FalseSuccessor->getSinglePredecessor()) { 243 WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op0), 244 true); 245 WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op1), 246 true); 247 } 248 continue; 249 } 250 251 // If the condition is an AND of 2 compares and the true successor only has 252 // the current block as predecessor, queue both conditions for the true 253 // successor. 254 if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) && 255 match(Op0, m_Cmp()) && match(Op1, m_Cmp())) { 256 BasicBlock *TrueSuccessor = Br->getSuccessor(0); 257 if (TrueSuccessor->getSinglePredecessor()) { 258 WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op0), 259 false); 260 WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op1), 261 false); 262 } 263 continue; 264 } 265 266 auto *CmpI = dyn_cast<CmpInst>(Br->getCondition()); 267 if (!CmpI) 268 continue; 269 if (Br->getSuccessor(0)->getSinglePredecessor()) 270 WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false); 271 if (Br->getSuccessor(1)->getSinglePredecessor()) 272 WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true); 273 } 274 275 // Next, sort worklist by dominance, so that dominating blocks and conditions 276 // come before blocks and conditions dominated by them. If a block and a 277 // condition have the same numbers, the condition comes before the block, as 278 // it holds on entry to the block. 279 sort(WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) { 280 return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock); 281 }); 282 283 // Finally, process ordered worklist and eliminate implied conditions. 284 SmallVector<StackEntry, 16> DFSInStack; 285 DenseMap<Value *, unsigned> Value2Index; 286 for (ConstraintOrBlock &CB : WorkList) { 287 // First, pop entries from the stack that are out-of-scope for CB. Remove 288 // the corresponding entry from the constraint system. 289 while (!DFSInStack.empty()) { 290 auto &E = DFSInStack.back(); 291 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut 292 << "\n"); 293 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n"); 294 assert(E.NumIn <= CB.NumIn); 295 if (CB.NumOut <= E.NumOut) 296 break; 297 LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot 298 << "\n"); 299 DFSInStack.pop_back(); 300 CS.popLastConstraint(); 301 } 302 303 LLVM_DEBUG({ 304 dbgs() << "Processing "; 305 if (CB.IsBlock) 306 dbgs() << *CB.BB; 307 else 308 dbgs() << *CB.Condition; 309 dbgs() << "\n"; 310 }); 311 312 // For a block, check if any CmpInsts become known based on the current set 313 // of constraints. 314 if (CB.IsBlock) { 315 for (Instruction &I : *CB.BB) { 316 auto *Cmp = dyn_cast<CmpInst>(&I); 317 if (!Cmp) 318 continue; 319 auto R = getConstraint(Cmp, Value2Index, false); 320 if (R.size() != 1 || R[0].size() == 1) 321 continue; 322 if (CS.isConditionImplied(R[0].Coefficients)) { 323 if (!DebugCounter::shouldExecute(EliminatedCounter)) 324 continue; 325 326 LLVM_DEBUG(dbgs() << "Condition " << *Cmp 327 << " implied by dominating constraints\n"); 328 LLVM_DEBUG({ 329 for (auto &E : reverse(DFSInStack)) 330 dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n"; 331 }); 332 Cmp->replaceAllUsesWith( 333 ConstantInt::getTrue(F.getParent()->getContext())); 334 NumCondsRemoved++; 335 Changed = true; 336 } 337 if (CS.isConditionImplied( 338 ConstraintSystem::negate(R[0].Coefficients))) { 339 if (!DebugCounter::shouldExecute(EliminatedCounter)) 340 continue; 341 342 LLVM_DEBUG(dbgs() << "Condition !" << *Cmp 343 << " implied by dominating constraints\n"); 344 LLVM_DEBUG({ 345 for (auto &E : reverse(DFSInStack)) 346 dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n"; 347 }); 348 Cmp->replaceAllUsesWith( 349 ConstantInt::getFalse(F.getParent()->getContext())); 350 NumCondsRemoved++; 351 Changed = true; 352 } 353 } 354 continue; 355 } 356 357 // Set up a function to restore the predicate at the end of the scope if it 358 // has been negated. Negate the predicate in-place, if required. 359 auto *CI = dyn_cast<CmpInst>(CB.Condition); 360 auto PredicateRestorer = make_scope_exit([CI, &CB]() { 361 if (CB.Not && CI) 362 CI->setPredicate(CI->getInversePredicate()); 363 }); 364 if (CB.Not) { 365 if (CI) { 366 CI->setPredicate(CI->getInversePredicate()); 367 } else { 368 LLVM_DEBUG(dbgs() << "Can only negate compares so far.\n"); 369 continue; 370 } 371 } 372 373 // Otherwise, add the condition to the system and stack, if we can transform 374 // it into a constraint. 375 auto R = getConstraint(CB.Condition, Value2Index, true); 376 if (R.empty()) 377 continue; 378 379 LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n"); 380 bool Added = false; 381 for (auto &C : R) { 382 auto Coeffs = C.Coefficients; 383 384 Added |= CS.addVariableRowFill(Coeffs); 385 // If R has been added to the system, queue it for removal once it goes 386 // out-of-scope. 387 if (Added) 388 DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not); 389 } 390 } 391 392 assert(CS.size() == DFSInStack.size() && 393 "updates to CS and DFSInStack are out of sync"); 394 return Changed; 395 } 396 397 PreservedAnalyses ConstraintEliminationPass::run(Function &F, 398 FunctionAnalysisManager &AM) { 399 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 400 if (!eliminateConstraints(F, DT)) 401 return PreservedAnalyses::all(); 402 403 PreservedAnalyses PA; 404 PA.preserve<DominatorTreeAnalysis>(); 405 PA.preserve<GlobalsAA>(); 406 PA.preserveSet<CFGAnalyses>(); 407 return PA; 408 } 409 410 namespace { 411 412 class ConstraintElimination : public FunctionPass { 413 public: 414 static char ID; 415 416 ConstraintElimination() : FunctionPass(ID) { 417 initializeConstraintEliminationPass(*PassRegistry::getPassRegistry()); 418 } 419 420 bool runOnFunction(Function &F) override { 421 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 422 return eliminateConstraints(F, DT); 423 } 424 425 void getAnalysisUsage(AnalysisUsage &AU) const override { 426 AU.setPreservesCFG(); 427 AU.addRequired<DominatorTreeWrapperPass>(); 428 AU.addPreserved<GlobalsAAWrapperPass>(); 429 AU.addPreserved<DominatorTreeWrapperPass>(); 430 } 431 }; 432 433 } // end anonymous namespace 434 435 char ConstraintElimination::ID = 0; 436 437 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination", 438 "Constraint Elimination", false, false) 439 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 440 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 441 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination", 442 "Constraint Elimination", false, false) 443 444 FunctionPass *llvm::createConstraintEliminationPass() { 445 return new ConstraintElimination(); 446 } 447