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/ADT/SmallVector.h" 15 #include "llvm/ADT/Statistic.h" 16 #include "llvm/Analysis/ConstraintSystem.h" 17 #include "llvm/Analysis/GlobalsModRef.h" 18 #include "llvm/IR/DataLayout.h" 19 #include "llvm/IR/Dominators.h" 20 #include "llvm/IR/Function.h" 21 #include "llvm/IR/Instructions.h" 22 #include "llvm/IR/PatternMatch.h" 23 #include "llvm/InitializePasses.h" 24 #include "llvm/Pass.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/DebugCounter.h" 27 #include "llvm/Transforms/Scalar.h" 28 29 using namespace llvm; 30 using namespace PatternMatch; 31 32 #define DEBUG_TYPE "constraint-elimination" 33 34 STATISTIC(NumCondsRemoved, "Number of instructions removed"); 35 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated", 36 "Controls which conditions are eliminated"); 37 38 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max(); 39 40 static Optional<std::pair<int64_t, Value *>> decompose(Value *V) { 41 if (auto *CI = dyn_cast<ConstantInt>(V)) { 42 if (CI->isNegative() || CI->uge(MaxConstraintValue)) 43 return {}; 44 return {{CI->getSExtValue(), nullptr}}; 45 } 46 auto *GEP = dyn_cast<GetElementPtrInst>(V); 47 if (GEP && GEP->getNumOperands() == 2 && 48 isa<ConstantInt>(GEP->getOperand(GEP->getNumOperands() - 1))) { 49 return {{cast<ConstantInt>(GEP->getOperand(GEP->getNumOperands() - 1)) 50 ->getSExtValue(), 51 GEP->getPointerOperand()}}; 52 } 53 return {{0, V}}; 54 } 55 56 /// Turn a condition \p CmpI into a constraint vector, using indices from \p 57 /// Value2Index. If \p ShouldAdd is true, new indices are added for values not 58 /// yet in \p Value2Index. 59 static SmallVector<int64_t, 8> 60 getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, 61 DenseMap<Value *, unsigned> &Value2Index, bool ShouldAdd) { 62 Value *A, *B; 63 64 int64_t Offset1 = 0; 65 int64_t Offset2 = 0; 66 67 auto TryToGetIndex = [ShouldAdd, 68 &Value2Index](Value *V) -> Optional<unsigned> { 69 if (ShouldAdd) { 70 Value2Index.insert({V, Value2Index.size() + 1}); 71 return Value2Index[V]; 72 } 73 auto I = Value2Index.find(V); 74 if (I == Value2Index.end()) 75 return None; 76 return I->second; 77 }; 78 79 if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE) 80 return getConstraint(CmpInst::getSwappedPredicate(Pred), Op1, Op0, 81 Value2Index, ShouldAdd); 82 83 if (Pred == CmpInst::ICMP_ULE || Pred == CmpInst::ICMP_ULT) { 84 auto ADec = decompose(Op0); 85 auto BDec = decompose(Op1); 86 if (!ADec || !BDec) 87 return {}; 88 std::tie(Offset1, A) = *ADec; 89 std::tie(Offset2, B) = *BDec; 90 Offset1 *= -1; 91 92 if (!A && !B) 93 return {}; 94 95 auto AIdx = A ? TryToGetIndex(A) : None; 96 auto BIdx = B ? TryToGetIndex(B) : None; 97 if ((A && !AIdx) || (B && !BIdx)) 98 return {}; 99 100 SmallVector<int64_t, 8> R(Value2Index.size() + 1, 0); 101 if (AIdx) 102 R[*AIdx] = 1; 103 if (BIdx) 104 R[*BIdx] = -1; 105 R[0] = Offset1 + Offset2 + (Pred == CmpInst::ICMP_ULT ? -1 : 0); 106 return R; 107 } 108 109 return {}; 110 } 111 112 static SmallVector<int64_t, 8> 113 getConstraint(CmpInst *Cmp, DenseMap<Value *, unsigned> &Value2Index, 114 bool ShouldAdd) { 115 return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0), 116 Cmp->getOperand(1), Value2Index, ShouldAdd); 117 } 118 119 namespace { 120 /// Represents either a condition that holds on entry to a block or a basic 121 /// block, with their respective Dominator DFS in and out numbers. 122 struct ConstraintOrBlock { 123 unsigned NumIn; 124 unsigned NumOut; 125 bool IsBlock; 126 bool Not; 127 union { 128 BasicBlock *BB; 129 CmpInst *Condition; 130 }; 131 132 ConstraintOrBlock(DomTreeNode *DTN) 133 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true), 134 BB(DTN->getBlock()) {} 135 ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not) 136 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false), 137 Not(Not), Condition(Condition) {} 138 }; 139 140 struct StackEntry { 141 unsigned NumIn; 142 unsigned NumOut; 143 CmpInst *Condition; 144 bool IsNot; 145 146 StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot) 147 : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot) {} 148 }; 149 } // namespace 150 151 static bool eliminateConstraints(Function &F, DominatorTree &DT) { 152 bool Changed = false; 153 DT.updateDFSNumbers(); 154 ConstraintSystem CS; 155 156 SmallVector<ConstraintOrBlock, 64> WorkList; 157 158 // First, collect conditions implied by branches and blocks with their 159 // Dominator DFS in and out numbers. 160 for (BasicBlock &BB : F) { 161 if (!DT.getNode(&BB)) 162 continue; 163 WorkList.emplace_back(DT.getNode(&BB)); 164 165 auto *Br = dyn_cast<BranchInst>(BB.getTerminator()); 166 if (!Br || !Br->isConditional()) 167 continue; 168 auto *CmpI = dyn_cast<CmpInst>(Br->getCondition()); 169 if (!CmpI) 170 continue; 171 if (Br->getSuccessor(0)->getSinglePredecessor()) 172 WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false); 173 if (Br->getSuccessor(1)->getSinglePredecessor()) 174 WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true); 175 } 176 177 // Next, sort worklist by dominance, so that dominating blocks and conditions 178 // come before blocks and conditions dominated by them. If a block and a 179 // condition have the same numbers, the condition comes before the block, as 180 // it holds on entry to the block. 181 sort(WorkList.begin(), WorkList.end(), 182 [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) { 183 return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock); 184 }); 185 186 // Finally, process ordered worklist and eliminate implied conditions. 187 SmallVector<StackEntry, 16> DFSInStack; 188 DenseMap<Value *, unsigned> Value2Index; 189 for (ConstraintOrBlock &CB : WorkList) { 190 // First, pop entries from the stack that are out-of-scope for CB. Remove 191 // the corresponding entry from the constraint system. 192 while (!DFSInStack.empty()) { 193 auto &E = DFSInStack.back(); 194 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut 195 << "\n"); 196 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n"); 197 assert(E.NumIn <= CB.NumIn); 198 if (CB.NumOut <= E.NumOut) 199 break; 200 LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot 201 << "\n"); 202 DFSInStack.pop_back(); 203 CS.popLastConstraint(); 204 } 205 206 LLVM_DEBUG({ 207 dbgs() << "Processing "; 208 if (CB.IsBlock) 209 dbgs() << *CB.BB; 210 else 211 dbgs() << *CB.Condition; 212 dbgs() << "\n"; 213 }); 214 215 // For a block, check if any CmpInsts become known based on the current set 216 // of constraints. 217 if (CB.IsBlock) { 218 for (Instruction &I : *CB.BB) { 219 auto *Cmp = dyn_cast<CmpInst>(&I); 220 if (!Cmp) 221 continue; 222 auto R = getConstraint(Cmp, Value2Index, false); 223 if (R.empty()) 224 continue; 225 if (CS.isConditionImplied(R)) { 226 if (!DebugCounter::shouldExecute(EliminatedCounter)) 227 continue; 228 229 LLVM_DEBUG(dbgs() << "Condition " << *Cmp 230 << " implied by dominating constraints\n"); 231 LLVM_DEBUG({ 232 for (auto &E : reverse(DFSInStack)) 233 dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n"; 234 }); 235 Cmp->replaceAllUsesWith( 236 ConstantInt::getTrue(F.getParent()->getContext())); 237 NumCondsRemoved++; 238 Changed = true; 239 } 240 if (CS.isConditionImplied(ConstraintSystem::negate(R))) { 241 if (!DebugCounter::shouldExecute(EliminatedCounter)) 242 continue; 243 244 LLVM_DEBUG(dbgs() << "Condition !" << *Cmp 245 << " implied by dominating constraints\n"); 246 LLVM_DEBUG({ 247 for (auto &E : reverse(DFSInStack)) 248 dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n"; 249 }); 250 Cmp->replaceAllUsesWith( 251 ConstantInt::getFalse(F.getParent()->getContext())); 252 NumCondsRemoved++; 253 Changed = true; 254 } 255 } 256 continue; 257 } 258 259 // Otherwise, add the condition to the system and stack, if we can transform 260 // it into a constraint. 261 auto R = getConstraint(CB.Condition, Value2Index, true); 262 if (R.empty()) 263 continue; 264 265 LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n"); 266 if (CB.Not) 267 R = ConstraintSystem::negate(R); 268 269 CS.addVariableRowFill(R); 270 DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not); 271 } 272 273 return Changed; 274 } 275 276 namespace { 277 278 class ConstraintElimination : public FunctionPass { 279 public: 280 static char ID; 281 282 ConstraintElimination() : FunctionPass(ID) { 283 initializeConstraintEliminationPass(*PassRegistry::getPassRegistry()); 284 } 285 286 bool runOnFunction(Function &F) override { 287 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 288 return eliminateConstraints(F, DT); 289 } 290 291 void getAnalysisUsage(AnalysisUsage &AU) const override { 292 AU.setPreservesCFG(); 293 AU.addRequired<DominatorTreeWrapperPass>(); 294 AU.addPreserved<GlobalsAAWrapperPass>(); 295 AU.addPreserved<DominatorTreeWrapperPass>(); 296 } 297 }; 298 299 } // end anonymous namespace 300 301 char ConstraintElimination::ID = 0; 302 303 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination", 304 "Constraint Elimination", false, false) 305 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 306 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 307 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination", 308 "Constraint Elimination", false, false) 309 310 FunctionPass *llvm::createConstraintEliminationPass() { 311 return new ConstraintElimination(); 312 } 313