llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

   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/ScopeExit.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/Analysis/ConstraintSystem.h"
  20 #include "llvm/Analysis/GlobalsModRef.h"
  21 #include "llvm/IR/DataLayout.h"
  22 #include "llvm/IR/Dominators.h"
  23 #include "llvm/IR/Function.h"
  24 #include "llvm/IR/Instructions.h"
  25 #include "llvm/IR/PatternMatch.h"
  26 #include "llvm/InitializePasses.h"
  27 #include "llvm/Pass.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/DebugCounter.h"
  30 #include "llvm/Transforms/Scalar.h"
  31
  32 #include <string>
  33
  34 using namespace llvm;
  35 using namespace PatternMatch;
  36
  37 #define DEBUG_TYPE "constraint-elimination"
  38
  39 STATISTIC(NumCondsRemoved, "Number of instructions removed");
  40 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
  41               "Controls which conditions are eliminated");
  42
  43 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();
  44
  45 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The
  46 // sum of the pairs equals \p V.  The first pair is the constant-factor and X
  47 // must be nullptr. If the expression cannot be decomposed, returns an empty
  48 // vector.
  49 static SmallVector<std::pair<int64_t, Value *>, 4> decompose(Value *V) {
  50   if (auto *CI = dyn_cast<ConstantInt>(V)) {
  51     if (CI->isNegative() || CI->uge(MaxConstraintValue))
  52       return {};
  53     return {{CI->getSExtValue(), nullptr}};
  54   }
  55   auto *GEP = dyn_cast<GetElementPtrInst>(V);
  56   if (GEP && GEP->getNumOperands() == 2 && GEP->isInBounds()) {
  57     Value *Op0, *Op1;
  58     ConstantInt *CI;
  59
  60     // If the index is zero-extended, it is guaranteed to be positive.
  61     if (match(GEP->getOperand(GEP->getNumOperands() - 1),
  62               m_ZExt(m_Value(Op0)))) {
  63       if (match(Op0, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))))
  64         return {{0, nullptr},
  65                 {1, GEP->getPointerOperand()},
  66                 {std::pow(int64_t(2), CI->getSExtValue()), Op1}};
  67       if (match(Op0, m_NSWAdd(m_Value(Op1), m_ConstantInt(CI))))
  68         return {{CI->getSExtValue(), nullptr},
  69                 {1, GEP->getPointerOperand()},
  70                 {1, Op1}};
  71       return {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
  72     }
  73
  74     if (match(GEP->getOperand(GEP->getNumOperands() - 1), m_ConstantInt(CI)) &&
  75         !CI->isNegative())
  76       return {{CI->getSExtValue(), nullptr}, {1, GEP->getPointerOperand()}};
  77
  78     SmallVector<std::pair<int64_t, Value *>, 4> Result;
  79     if (match(GEP->getOperand(GEP->getNumOperands() - 1),
  80               m_NUWShl(m_Value(Op0), m_ConstantInt(CI))))
  81       Result = {{0, nullptr},
  82                 {1, GEP->getPointerOperand()},
  83                 {std::pow(int64_t(2), CI->getSExtValue()), Op0}};
  84     else if (match(GEP->getOperand(GEP->getNumOperands() - 1),
  85                    m_NSWAdd(m_Value(Op0), m_ConstantInt(CI))))
  86       Result = {{CI->getSExtValue(), nullptr},
  87                 {1, GEP->getPointerOperand()},
  88                 {1, Op0}};
  89     else {
  90       Op0 = GEP->getOperand(GEP->getNumOperands() - 1);
  91       Result = {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
  92     }
  93     return Result;
  94   }
  95
  96   Value *Op0;
  97   if (match(V, m_ZExt(m_Value(Op0))))
  98     V = Op0;
  99
 100   Value *Op1;
 101   ConstantInt *CI;
 102   if (match(V, m_NUWAdd(m_Value(Op0), m_ConstantInt(CI))))
 103     return {{CI->getSExtValue(), nullptr}, {1, Op0}};
 104   if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1))))
 105     return {{0, nullptr}, {1, Op0}, {1, Op1}};
 106
 107   if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))))
 108     return {{-1 * CI->getSExtValue(), nullptr}, {1, Op0}};
 109   if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
 110     return {{0, nullptr}, {1, Op0}, {1, Op1}};
 111
 112   return {{0, nullptr}, {1, V}};
 113 }
 114
 115 struct ConstraintTy {
 116   SmallVector<int64_t, 8> Coefficients;
 117
 118   ConstraintTy(SmallVector<int64_t, 8> Coefficients)
 119       : Coefficients(Coefficients) {}
 120
 121   unsigned size() const { return Coefficients.size(); }
 122 };
 123
 124 /// Turn a condition \p CmpI into a vector of constraints, using indices from \p
 125 /// Value2Index. Additional indices for newly discovered values are added to \p
 126 /// NewIndices.
 127 static SmallVector<ConstraintTy, 4>
 128 getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
 129               const DenseMap<Value *, unsigned> &Value2Index,
 130               DenseMap<Value *, unsigned> &NewIndices) {
 131   int64_t Offset1 = 0;
 132   int64_t Offset2 = 0;
 133
 134   // First try to look up \p V in Value2Index and NewIndices. Otherwise add a
 135   // new entry to NewIndices.
 136   auto GetOrAddIndex = [&Value2Index, &NewIndices](Value *V) -> unsigned {
 137     auto V2I = Value2Index.find(V);
 138     if (V2I != Value2Index.end())
 139       return V2I->second;
 140     auto NewI = NewIndices.find(V);
 141     if (NewI != NewIndices.end())
 142       return NewI->second;
 143     auto Insert =
 144         NewIndices.insert({V, Value2Index.size() + NewIndices.size() + 1});
 145     return Insert.first->second;
 146   };
 147
 148   if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE)
 149     return getConstraint(CmpInst::getSwappedPredicate(Pred), Op1, Op0,
 150                          Value2Index, NewIndices);
 151
 152   if (Pred == CmpInst::ICMP_EQ) {
 153     auto A =
 154         getConstraint(CmpInst::ICMP_UGE, Op0, Op1, Value2Index, NewIndices);
 155     auto B =
 156         getConstraint(CmpInst::ICMP_ULE, Op0, Op1, Value2Index, NewIndices);
 157     append_range(A, B);
 158     return A;
 159   }
 160
 161   if (Pred == CmpInst::ICMP_NE && match(Op1, m_Zero())) {
 162     return getConstraint(CmpInst::ICMP_UGT, Op0, Op1, Value2Index, NewIndices);
 163   }
 164
 165   // Only ULE and ULT predicates are supported at the moment.
 166   if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT)
 167     return {};
 168
 169   auto ADec = decompose(Op0->stripPointerCastsSameRepresentation());
 170   auto BDec = decompose(Op1->stripPointerCastsSameRepresentation());
 171   // Skip if decomposing either of the values failed.
 172   if (ADec.empty() || BDec.empty())
 173     return {};
 174
 175   // Skip trivial constraints without any variables.
 176   if (ADec.size() == 1 && BDec.size() == 1)
 177     return {};
 178
 179   Offset1 = ADec[0].first;
 180   Offset2 = BDec[0].first;
 181   Offset1 *= -1;
 182
 183   // Create iterator ranges that skip the constant-factor.
 184   auto VariablesA = llvm::drop_begin(ADec);
 185   auto VariablesB = llvm::drop_begin(BDec);
 186
 187   // Make sure all variables have entries in Value2Index or NewIndices.
 188   for (const auto &KV :
 189        concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB))
 190     GetOrAddIndex(KV.second);
 191
 192   // Build result constraint, by first adding all coefficients from A and then
 193   // subtracting all coefficients from B.
 194   SmallVector<int64_t, 8> R(Value2Index.size() + NewIndices.size() + 1, 0);
 195   for (const auto &KV : VariablesA)
 196     R[GetOrAddIndex(KV.second)] += KV.first;
 197
 198   for (const auto &KV : VariablesB)
 199     R[GetOrAddIndex(KV.second)] -= KV.first;
 200
 201   R[0] = Offset1 + Offset2 + (Pred == CmpInst::ICMP_ULT ? -1 : 0);
 202   return {R};
 203 }
 204
 205 static SmallVector<ConstraintTy, 4>
 206 getConstraint(CmpInst *Cmp, const DenseMap<Value *, unsigned> &Value2Index,
 207               DenseMap<Value *, unsigned> &NewIndices) {
 208   return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0),
 209                        Cmp->getOperand(1), Value2Index, NewIndices);
 210 }
 211
 212 namespace {
 213 /// Represents either a condition that holds on entry to a block or a basic
 214 /// block, with their respective Dominator DFS in and out numbers.
 215 struct ConstraintOrBlock {
 216   unsigned NumIn;
 217   unsigned NumOut;
 218   bool IsBlock;
 219   bool Not;
 220   union {
 221     BasicBlock *BB;
 222     CmpInst *Condition;
 223   };
 224
 225   ConstraintOrBlock(DomTreeNode *DTN)
 226       : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
 227         BB(DTN->getBlock()) {}
 228   ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
 229       : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
 230         Not(Not), Condition(Condition) {}
 231 };
 232
 233 struct StackEntry {
 234   unsigned NumIn;
 235   unsigned NumOut;
 236   CmpInst *Condition;
 237   bool IsNot;
 238
 239   StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot)
 240       : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot) {}
 241 };
 242 } // namespace
 243
 244 #ifndef NDEBUG
 245 static void dumpWithNames(ConstraintTy &C,
 246                           DenseMap<Value *, unsigned> &Value2Index) {
 247   SmallVector<std::string> Names(Value2Index.size(), "");
 248   for (auto &KV : Value2Index) {
 249     Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
 250   }
 251   ConstraintSystem CS;
 252   CS.addVariableRowFill(C.Coefficients);
 253   CS.dump(Names);
 254 }
 255 #endif
 256
 257 static bool eliminateConstraints(Function &F, DominatorTree &DT) {
 258   bool Changed = false;
 259   DT.updateDFSNumbers();
 260   ConstraintSystem CS;
 261
 262   SmallVector<ConstraintOrBlock, 64> WorkList;
 263
 264   // First, collect conditions implied by branches and blocks with their
 265   // Dominator DFS in and out numbers.
 266   for (BasicBlock &BB : F) {
 267     if (!DT.getNode(&BB))
 268       continue;
 269     WorkList.emplace_back(DT.getNode(&BB));
 270
 271     auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
 272     if (!Br || !Br->isConditional())
 273       continue;
 274
 275     // Returns true if we can add a known condition from BB to its successor
 276     // block Succ. Each predecessor of Succ can either be BB or be dominated by
 277     // Succ (e.g. the case when adding a condition from a pre-header to a loop
 278     // header).
 279     auto CanAdd = [&BB, &DT](BasicBlock *Succ) {
 280       return all_of(predecessors(Succ), [&BB, &DT, Succ](BasicBlock *Pred) {
 281         return Pred == &BB || DT.dominates(Succ, Pred);
 282       });
 283     };
 284     // If the condition is an OR of 2 compares and the false successor only has
 285     // the current block as predecessor, queue both negated conditions for the
 286     // false successor.
 287     Value *Op0, *Op1;
 288     if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1))) &&
 289         match(Op0, m_Cmp()) && match(Op1, m_Cmp())) {
 290       BasicBlock *FalseSuccessor = Br->getSuccessor(1);
 291       if (CanAdd(FalseSuccessor)) {
 292         WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op0),
 293                               true);
 294         WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op1),
 295                               true);
 296       }
 297       continue;
 298     }
 299
 300     // If the condition is an AND of 2 compares and the true successor only has
 301     // the current block as predecessor, queue both conditions for the true
 302     // successor.
 303     if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) &&
 304         match(Op0, m_Cmp()) && match(Op1, m_Cmp())) {
 305       BasicBlock *TrueSuccessor = Br->getSuccessor(0);
 306       if (CanAdd(TrueSuccessor)) {
 307         WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op0),
 308                               false);
 309         WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op1),
 310                               false);
 311       }
 312       continue;
 313     }
 314
 315     auto *CmpI = dyn_cast<CmpInst>(Br->getCondition());
 316     if (!CmpI)
 317       continue;
 318     if (CanAdd(Br->getSuccessor(0)))
 319       WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
 320     if (CanAdd(Br->getSuccessor(1)))
 321       WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
 322   }
 323
 324   // Next, sort worklist by dominance, so that dominating blocks and conditions
 325   // come before blocks and conditions dominated by them. If a block and a
 326   // condition have the same numbers, the condition comes before the block, as
 327   // it holds on entry to the block.
 328   sort(WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
 329     return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
 330   });
 331
 332   // Finally, process ordered worklist and eliminate implied conditions.
 333   SmallVector<StackEntry, 16> DFSInStack;
 334   DenseMap<Value *, unsigned> Value2Index;
 335   for (ConstraintOrBlock &CB : WorkList) {
 336     // First, pop entries from the stack that are out-of-scope for CB. Remove
 337     // the corresponding entry from the constraint system.
 338     while (!DFSInStack.empty()) {
 339       auto &E = DFSInStack.back();
 340       LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
 341                         << "\n");
 342       LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
 343       assert(E.NumIn <= CB.NumIn);
 344       if (CB.NumOut <= E.NumOut)
 345         break;
 346       LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot
 347                         << "\n");
 348       DFSInStack.pop_back();
 349       CS.popLastConstraint();
 350     }
 351
 352     LLVM_DEBUG({
 353       dbgs() << "Processing ";
 354       if (CB.IsBlock)
 355         dbgs() << *CB.BB;
 356       else
 357         dbgs() << *CB.Condition;
 358       dbgs() << "\n";
 359     });
 360
 361     // For a block, check if any CmpInsts become known based on the current set
 362     // of constraints.
 363     if (CB.IsBlock) {
 364       for (Instruction &I : *CB.BB) {
 365         auto *Cmp = dyn_cast<CmpInst>(&I);
 366         if (!Cmp)
 367           continue;
 368
 369         DenseMap<Value *, unsigned> NewIndices;
 370         auto R = getConstraint(Cmp, Value2Index, NewIndices);
 371         if (R.size() != 1)
 372           continue;
 373
 374         // Check if all coefficients of new indices are 0 after building the
 375         // constraint. Skip if any of the new indices has a non-null
 376         // coefficient.
 377         bool HasNewIndex = false;
 378         for (unsigned I = 0; I < NewIndices.size(); ++I) {
 379           int64_t Last = R[0].Coefficients.pop_back_val();
 380           if (Last != 0) {
 381             HasNewIndex = true;
 382             break;
 383           }
 384         }
 385         if (HasNewIndex || R[0].size() == 1)
 386           continue;
 387
 388         if (CS.isConditionImplied(R[0].Coefficients)) {
 389           if (!DebugCounter::shouldExecute(EliminatedCounter))
 390             continue;
 391
 392           LLVM_DEBUG(dbgs() << "Condition " << *Cmp
 393                             << " implied by dominating constraints\n");
 394           LLVM_DEBUG({
 395             for (auto &E : reverse(DFSInStack))
 396               dbgs() << "   C " << *E.Condition << " " << E.IsNot << "\n";
 397           });
 398           Cmp->replaceAllUsesWith(
 399               ConstantInt::getTrue(F.getParent()->getContext()));
 400           NumCondsRemoved++;
 401           Changed = true;
 402         }
 403         if (CS.isConditionImplied(
 404                 ConstraintSystem::negate(R[0].Coefficients))) {
 405           if (!DebugCounter::shouldExecute(EliminatedCounter))
 406             continue;
 407
 408           LLVM_DEBUG(dbgs() << "Condition !" << *Cmp
 409                             << " implied by dominating constraints\n");
 410           LLVM_DEBUG({
 411             for (auto &E : reverse(DFSInStack))
 412               dbgs() << "   C " << *E.Condition << " " << E.IsNot << "\n";
 413           });
 414           Cmp->replaceAllUsesWith(
 415               ConstantInt::getFalse(F.getParent()->getContext()));
 416           NumCondsRemoved++;
 417           Changed = true;
 418         }
 419       }
 420       continue;
 421     }
 422
 423     // Set up a function to restore the predicate at the end of the scope if it
 424     // has been negated. Negate the predicate in-place, if required.
 425     auto *CI = dyn_cast<CmpInst>(CB.Condition);
 426     auto PredicateRestorer = make_scope_exit([CI, &CB]() {
 427       if (CB.Not && CI)
 428         CI->setPredicate(CI->getInversePredicate());
 429     });
 430     if (CB.Not) {
 431       if (CI) {
 432         CI->setPredicate(CI->getInversePredicate());
 433       } else {
 434         LLVM_DEBUG(dbgs() << "Can only negate compares so far.\n");
 435         continue;
 436       }
 437     }
 438
 439     // Otherwise, add the condition to the system and stack, if we can transform
 440     // it into a constraint.
 441     DenseMap<Value *, unsigned> NewIndices;
 442     auto R = getConstraint(CB.Condition, Value2Index, NewIndices);
 443     if (R.empty())
 444       continue;
 445
 446     for (auto &KV : NewIndices)
 447       Value2Index.insert(KV);
 448
 449     LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n");
 450     bool Added = false;
 451     for (auto &C : R) {
 452       auto Coeffs = C.Coefficients;
 453       LLVM_DEBUG({
 454         dbgs() << "  constraint: ";
 455         dumpWithNames(C, Value2Index);
 456       });
 457       Added |= CS.addVariableRowFill(Coeffs);
 458       // If R has been added to the system, queue it for removal once it goes
 459       // out-of-scope.
 460       if (Added)
 461         DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not);
 462     }
 463   }
 464
 465   assert(CS.size() == DFSInStack.size() &&
 466          "updates to CS and DFSInStack are out of sync");
 467   return Changed;
 468 }
 469
 470 PreservedAnalyses ConstraintEliminationPass::run(Function &F,
 471                                                  FunctionAnalysisManager &AM) {
 472   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 473   if (!eliminateConstraints(F, DT))
 474     return PreservedAnalyses::all();
 475
 476   PreservedAnalyses PA;
 477   PA.preserve<DominatorTreeAnalysis>();
 478   PA.preserveSet<CFGAnalyses>();
 479   return PA;
 480 }
 481
 482 namespace {
 483
 484 class ConstraintElimination : public FunctionPass {
 485 public:
 486   static char ID;
 487
 488   ConstraintElimination() : FunctionPass(ID) {
 489     initializeConstraintEliminationPass(*PassRegistry::getPassRegistry());
 490   }
 491
 492   bool runOnFunction(Function &F) override {
 493     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 494     return eliminateConstraints(F, DT);
 495   }
 496
 497   void getAnalysisUsage(AnalysisUsage &AU) const override {
 498     AU.setPreservesCFG();
 499     AU.addRequired<DominatorTreeWrapperPass>();
 500     AU.addPreserved<GlobalsAAWrapperPass>();
 501     AU.addPreserved<DominatorTreeWrapperPass>();
 502   }
 503 };
 504
 505 } // end anonymous namespace
 506
 507 char ConstraintElimination::ID = 0;
 508
 509 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
 510                       "Constraint Elimination", false, false)
 511 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 512 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
 513 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
 514                     "Constraint Elimination", false, false)
 515
 516 FunctionPass *llvm::createConstraintEliminationPass() {
 517   return new ConstraintElimination();
 518 }