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