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