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