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