Home | History | Annotate | Download | only in Analysis 
      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   int ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
    122   if (SimplifiedAddrOp->getValue().getActiveBits() >= 64)
    123     return false;
    124   int64_t Index = SimplifiedAddrOp->getSExtValue() / ElemSize;
    125   if (Index >= CDS->getNumElements()) {
    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 
    131   Constant *CV = CDS->getElementAsConstant(Index);
    132   assert(CV && "Constant expected.");
    133   SimplifiedValues[&I] = CV;
    134 
    135   return true;
    136 }
    137 
    138 /// Try to simplify cast instruction.
    139 bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
    140   // Propagate constants through casts.
    141   Constant *COp = dyn_cast<Constant>(I.getOperand(0));
    142   if (!COp)
    143     COp = SimplifiedValues.lookup(I.getOperand(0));
    144 
    145   // If we know a simplified value for this operand and cast is valid, save the
    146   // result to SimplifiedValues.
    147   // The cast can be invalid, because SimplifiedValues contains results of SCEV
    148   // analysis, which operates on integers (and, e.g., might convert i8* null to
    149   // i32 0).
    150   if (COp && CastInst::castIsValid(I.getOpcode(), COp, I.getType())) {
    151     if (Constant *C =
    152             ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
    153       SimplifiedValues[&I] = C;
    154       return true;
    155     }
    156   }
    157 
    158   return Base::visitCastInst(I);
    159 }
    160 
    161 /// Try to simplify cmp instruction.
    162 bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
    163   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
    164 
    165   // First try to handle simplified comparisons.
    166   if (!isa<Constant>(LHS))
    167     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
    168       LHS = SimpleLHS;
    169   if (!isa<Constant>(RHS))
    170     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
    171       RHS = SimpleRHS;
    172 
    173   if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
    174     auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
    175     if (SimplifiedLHS != SimplifiedAddresses.end()) {
    176       auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
    177       if (SimplifiedRHS != SimplifiedAddresses.end()) {
    178         SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
    179         SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
    180         if (LHSAddr.Base == RHSAddr.Base) {
    181           LHS = LHSAddr.Offset;
    182           RHS = RHSAddr.Offset;
    183         }
    184       }
    185     }
    186   }
    187 
    188   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
    189     if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
    190       if (CLHS->getType() == CRHS->getType()) {
    191         if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
    192           SimplifiedValues[&I] = C;
    193           return true;
    194         }
    195       }
    196     }
    197   }
    198 
    199   return Base::visitCmpInst(I);
    200 }
    201 
    202 bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
    203   // Run base visitor first. This way we can gather some useful for later
    204   // analysis information.
    205   if (Base::visitPHINode(PN))
    206     return true;
    207 
    208   // The loop induction PHI nodes are definitionally free.
    209   return PN.getParent() == L->getHeader();
    210 }
    211