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