LCOV - code coverage report
Current view: top level - lib/Analysis - LoopUnrollAnalyzer.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 90 93 96.8 %
Date: 2017-09-14 15:23:50 Functions: 6 6 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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       31258 : bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
      30       31258 :   if (!SE.isSCEVable(I->getType()))
      31             :     return false;
      32             : 
      33       16283 :   const SCEV *S = SE.getSCEV(I);
      34           8 :   if (auto *SC = dyn_cast<SCEVConstant>(S)) {
      35          16 :     SimplifiedValues[I] = SC->getValue();
      36           8 :     return true;
      37             :   }
      38             : 
      39       11543 :   auto *AR = dyn_cast<SCEVAddRecExpr>(S);
      40       11543 :   if (!AR || AR->getLoop() != L)
      41             :     return false;
      42             : 
      43       11463 :   const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
      44             :   // Check if the AddRec expression becomes a constant.
      45        6619 :   if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
      46       13238 :     SimplifiedValues[I] = SC->getValue();
      47        6619 :     return true;
      48             :   }
      49             : 
      50             :   // Check if the offset from the base address becomes a constant.
      51        9680 :   auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
      52        4836 :   if (!Base)
      53             :     return false;
      54             :   auto *Offset =
      55        9656 :       dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
      56             :   if (!Offset)
      57             :     return false;
      58        4820 :   SimplifiedAddress Address;
      59        4820 :   Address.Base = Base->getValue();
      60        4820 :   Address.Offset = Offset->getValue();
      61        9640 :   SimplifiedAddresses[I] = Address;
      62        4820 :   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       10483 : bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
      71       20966 :   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
      72       10483 :   if (!isa<Constant>(LHS))
      73       20914 :     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
      74        6597 :       LHS = SimpleLHS;
      75       10483 :   if (!isa<Constant>(RHS))
      76        4748 :     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
      77         125 :       RHS = SimpleRHS;
      78             : 
      79       10483 :   Value *SimpleV = nullptr;
      80       20966 :   const DataLayout &DL = I.getModule()->getDataLayout();
      81       10483 :   if (auto FI = dyn_cast<FPMathOperator>(&I))
      82           0 :     SimpleV =
      83           0 :         SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
      84             :   else
      85       20966 :     SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
      86             : 
      87        6600 :   if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
      88       13200 :     SimplifiedValues[&I] = C;
      89             : 
      90       10483 :   if (SimpleV)
      91             :     return true;
      92        3823 :   return Base::visitBinaryOperator(I);
      93             : }
      94             : 
      95             : /// Try to fold load I.
      96        3944 : bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
      97        3944 :   Value *AddrOp = I.getPointerOperand();
      98             : 
      99        3944 :   auto AddressIt = SimplifiedAddresses.find(AddrOp);
     100       11832 :   if (AddressIt == SimplifiedAddresses.end())
     101             :     return false;
     102        2454 :   ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
     103             : 
     104        4653 :   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        4380 :   if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
     108             :     return false;
     109             : 
     110             :   ConstantDataSequential *CDS =
     111        4326 :       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        2163 :   if (CDS->getElementType() != I.getType())
     119             :     return false;
     120             : 
     121         145 :   unsigned ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
     122         290 :   if (SimplifiedAddrOp->getValue().getActiveBits() > 64)
     123             :     return false;
     124         145 :   int64_t SimplifiedAddrOpV = SimplifiedAddrOp->getSExtValue();
     125         145 :   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         143 :   uint64_t Index = static_cast<uint64_t>(SimplifiedAddrOpV) / ElemSize;
     131         143 :   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         143 :   Constant *CV = CDS->getElementAsConstant(Index);
     138             :   assert(CV && "Constant expected.");
     139         286 :   SimplifiedValues[&I] = CV;
     140             : 
     141         143 :   return true;
     142             : }
     143             : 
     144             : /// Try to simplify cast instruction.
     145        4067 : bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
     146             :   // Propagate constants through casts.
     147        8134 :   Constant *COp = dyn_cast<Constant>(I.getOperand(0));
     148             :   if (!COp)
     149        6207 :     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        4090 :   if (COp && CastInst::castIsValid(I.getOpcode(), COp, I.getType())) {
     157        2041 :     if (Constant *C =
     158        4082 :             ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
     159        4082 :       SimplifiedValues[&I] = C;
     160        2041 :       return true;
     161             :     }
     162             :   }
     163             : 
     164        2026 :   return Base::visitCastInst(I);
     165             : }
     166             : 
     167             : /// Try to simplify cmp instruction.
     168        6885 : bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
     169       13770 :   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
     170             : 
     171             :   // First try to handle simplified comparisons.
     172        6885 :   if (!isa<Constant>(LHS))
     173       13742 :     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
     174        6645 :       LHS = SimpleLHS;
     175        6885 :   if (!isa<Constant>(RHS))
     176         308 :     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
     177           0 :       RHS = SimpleRHS;
     178             : 
     179        7111 :   if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
     180         144 :     auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
     181         432 :     if (SimplifiedLHS != SimplifiedAddresses.end()) {
     182          80 :       auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
     183         240 :       if (SimplifiedRHS != SimplifiedAddresses.end()) {
     184          40 :         SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
     185          40 :         SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
     186          40 :         if (LHSAddr.Base == RHSAddr.Base) {
     187          40 :           LHS = LHSAddr.Offset;
     188          40 :           RHS = RHSAddr.Offset;
     189             :         }
     190             :       }
     191             :     }
     192             :   }
     193             : 
     194       13584 :   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
     195       13388 :     if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
     196        6689 :       if (CLHS->getType() == CRHS->getType()) {
     197        6687 :         if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
     198       13374 :           SimplifiedValues[&I] = C;
     199        6687 :           return true;
     200             :         }
     201             :       }
     202             :     }
     203             :   }
     204             : 
     205         198 :   return Base::visitCmpInst(I);
     206             : }
     207             : 
     208        9134 : bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
     209             :   // Run base visitor first. This way we can gather some useful for later
     210             :   // analysis information.
     211        9134 :   if (Base::visitPHINode(PN))
     212             :     return true;
     213             : 
     214             :   // The loop induction PHI nodes are definitionally free.
     215        5026 :   return PN.getParent() == L->getHeader();
     216             : }

Generated by: LCOV version 1.13