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