contrib/llvm/lib/Analysis/LoopUnrollAnalyzer.cpp

   1 //===- LoopUnrollAnalyzer.cpp - Unrolling Effect Estimation -----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements UnrolledInstAnalyzer class. It's used for predicting
  11 // potential effects that loop unrolling might have, such as enabling constant
  12 // propagation and other optimizations.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Analysis/LoopUnrollAnalyzer.h"
  17 #include "llvm/IR/Dominators.h"
  18
  19 using namespace llvm;
  20
  21 /// \brief Try to simplify instruction \param I using its SCEV expression.
  22 ///
  23 /// The idea is that some AddRec expressions become constants, which then
  24 /// could trigger folding of other instructions. However, that only happens
  25 /// for expressions whose start value is also constant, which isn't always the
  26 /// case. In another common and important case the start value is just some
  27 /// address (i.e. SCEVUnknown) - in this case we compute the offset and save
  28 /// it along with the base address instead.
  29 bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
  30   if (!SE.isSCEVable(I->getType()))
  31     return false;
  32
  33   const SCEV *S = SE.getSCEV(I);
  34   if (auto *SC = dyn_cast<SCEVConstant>(S)) {
  35     SimplifiedValues[I] = SC->getValue();
  36     return true;
  37   }
  38
  39   auto *AR = dyn_cast<SCEVAddRecExpr>(S);
  40   if (!AR || AR->getLoop() != L)
  41     return false;
  42
  43   const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
  44   // Check if the AddRec expression becomes a constant.
  45   if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
  46     SimplifiedValues[I] = SC->getValue();
  47     return true;
  48   }
  49
  50   // Check if the offset from the base address becomes a constant.
  51   auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
  52   if (!Base)
  53     return false;
  54   auto *Offset =
  55       dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
  56   if (!Offset)
  57     return false;
  58   SimplifiedAddress Address;
  59   Address.Base = Base->getValue();
  60   Address.Offset = Offset->getValue();
  61   SimplifiedAddresses[I] = Address;
  62   return false;
  63 }
  64
  65 /// Try to simplify binary operator I.
  66 ///
  67 /// TODO: Probably it's worth to hoist the code for estimating the
  68 /// simplifications effects to a separate class, since we have a very similar
  69 /// code in InlineCost already.
  70 bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
  71   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
  72   if (!isa<Constant>(LHS))
  73     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
  74       LHS = SimpleLHS;
  75   if (!isa<Constant>(RHS))
  76     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
  77       RHS = SimpleRHS;
  78
  79   Value *SimpleV = nullptr;
  80   const DataLayout &DL = I.getModule()->getDataLayout();
  81   if (auto FI = dyn_cast<FPMathOperator>(&I))
  82     SimpleV =
  83         SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
  84   else
  85     SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
  86
  87   if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
  88     SimplifiedValues[&I] = C;
  89
  90   if (SimpleV)
  91     return true;
  92   return Base::visitBinaryOperator(I);
  93 }
  94
  95 /// Try to fold load I.
  96 bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
  97   Value *AddrOp = I.getPointerOperand();
  98
  99   auto AddressIt = SimplifiedAddresses.find(AddrOp);
 100   if (AddressIt == SimplifiedAddresses.end())
 101     return false;
 102   ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
 103
 104   auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
 105   // We're only interested in loads that can be completely folded to a
 106   // constant.
 107   if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
 108     return false;
 109
 110   ConstantDataSequential *CDS =
 111       dyn_cast<ConstantDataSequential>(GV->getInitializer());
 112   if (!CDS)
 113     return false;
 114
 115   // We might have a vector load from an array. FIXME: for now we just bail
 116   // out in this case, but we should be able to resolve and simplify such
 117   // loads.
 118   if (CDS->getElementType() != I.getType())
 119     return false;
 120
 121   unsigned ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
 122   if (SimplifiedAddrOp->getValue().getActiveBits() > 64)
 123     return false;
 124   int64_t SimplifiedAddrOpV = SimplifiedAddrOp->getSExtValue();
 125   if (SimplifiedAddrOpV < 0) {
 126     // FIXME: For now we conservatively ignore out of bound accesses, but
 127     // we're allowed to perform the optimization in this case.
 128     return false;
 129   }
 130   uint64_t Index = static_cast<uint64_t>(SimplifiedAddrOpV) / ElemSize;
 131   if (Index >= CDS->getNumElements()) {
 132     // FIXME: For now we conservatively ignore out of bound accesses, but
 133     // we're allowed to perform the optimization in this case.
 134     return false;
 135   }
 136
 137   Constant *CV = CDS->getElementAsConstant(Index);
 138   assert(CV && "Constant expected.");
 139   SimplifiedValues[&I] = CV;
 140
 141   return true;
 142 }
 143
 144 /// Try to simplify cast instruction.
 145 bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
 146   // Propagate constants through casts.
 147   Constant *COp = dyn_cast<Constant>(I.getOperand(0));
 148   if (!COp)
 149     COp = SimplifiedValues.lookup(I.getOperand(0));
 150
 151   // If we know a simplified value for this operand and cast is valid, save the
 152   // result to SimplifiedValues.
 153   // The cast can be invalid, because SimplifiedValues contains results of SCEV
 154   // analysis, which operates on integers (and, e.g., might convert i8* null to
 155   // i32 0).
 156   if (COp && CastInst::castIsValid(I.getOpcode(), COp, I.getType())) {
 157     if (Constant *C =
 158             ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
 159       SimplifiedValues[&I] = C;
 160       return true;
 161     }
 162   }
 163
 164   return Base::visitCastInst(I);
 165 }
 166
 167 /// Try to simplify cmp instruction.
 168 bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
 169   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 170
 171   // First try to handle simplified comparisons.
 172   if (!isa<Constant>(LHS))
 173     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
 174       LHS = SimpleLHS;
 175   if (!isa<Constant>(RHS))
 176     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
 177       RHS = SimpleRHS;
 178
 179   if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
 180     auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
 181     if (SimplifiedLHS != SimplifiedAddresses.end()) {
 182       auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
 183       if (SimplifiedRHS != SimplifiedAddresses.end()) {
 184         SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
 185         SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
 186         if (LHSAddr.Base == RHSAddr.Base) {
 187           LHS = LHSAddr.Offset;
 188           RHS = RHSAddr.Offset;
 189         }
 190       }
 191     }
 192   }
 193
 194   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
 195     if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
 196       if (CLHS->getType() == CRHS->getType()) {
 197         if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
 198           SimplifiedValues[&I] = C;
 199           return true;
 200         }
 201       }
 202     }
 203   }
 204
 205   return Base::visitCmpInst(I);
 206 }
 207
 208 bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
 209   // Run base visitor first. This way we can gather some useful for later
 210   // analysis information.
 211   if (Base::visitPHINode(PN))
 212     return true;
 213
 214   // The loop induction PHI nodes are definitionally free.
 215   return PN.getParent() == L->getHeader();
 216 }