LCOV - code coverage report
Current view: top level - lib/Analysis - LoopUnrollAnalyzer.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 69 71 97.2 %
Date: 2018-02-21 17:27:13 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             : 
      18             : using namespace llvm;
      19             : 
      20             : /// \brief 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       31230 : bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
      29       31230 :   if (!SE.isSCEVable(I->getType()))
      30             :     return false;
      31             : 
      32       16255 :   const SCEV *S = SE.getSCEV(I);
      33             :   if (auto *SC = dyn_cast<SCEVConstant>(S)) {
      34          16 :     SimplifiedValues[I] = SC->getValue();
      35           8 :     return true;
      36             :   }
      37             : 
      38             :   auto *AR = dyn_cast<SCEVAddRecExpr>(S);
      39       11533 :   if (!AR || AR->getLoop() != L)
      40             :     return false;
      41             : 
      42       11453 :   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       13226 :     SimplifiedValues[I] = SC->getValue();
      46        6613 :     return true;
      47             :   }
      48             : 
      49             :   // Check if the offset from the base address becomes a constant.
      50        4840 :   auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
      51        4836 :   if (!Base)
      52             :     return false;
      53             :   auto *Offset =
      54        4836 :       dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
      55             :   if (!Offset)
      56             :     return false;
      57             :   SimplifiedAddress Address;
      58             :   Address.Base = Base->getValue();
      59        4820 :   Address.Offset = Offset->getValue();
      60        9640 :   SimplifiedAddresses[I] = Address;
      61        4820 :   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       10475 : bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
      70             :   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
      71       10475 :   if (!isa<Constant>(LHS))
      72       17050 :     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
      73             :       LHS = SimpleLHS;
      74       10475 :   if (!isa<Constant>(RHS))
      75        2491 :     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
      76             :       RHS = SimpleRHS;
      77             : 
      78             :   Value *SimpleV = nullptr;
      79       20950 :   const DataLayout &DL = I.getModule()->getDataLayout();
      80             :   if (auto FI = dyn_cast<FPMathOperator>(&I))
      81           0 :     SimpleV =
      82           0 :         SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
      83             :   else
      84       10475 :     SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
      85             : 
      86             :   if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
      87       13200 :     SimplifiedValues[&I] = C;
      88             : 
      89       10475 :   if (SimpleV)
      90             :     return true;
      91        3815 :   return Base::visitBinaryOperator(I);
      92             : }
      93             : 
      94             : /// Try to fold load I.
      95        3948 : bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
      96             :   Value *AddrOp = I.getPointerOperand();
      97             : 
      98        3948 :   auto AddressIt = SimplifiedAddresses.find(AddrOp);
      99        3948 :   if (AddressIt == SimplifiedAddresses.end())
     100             :     return false;
     101        2454 :   ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
     102             : 
     103        2454 :   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        4380 :   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        2163 :   if (CDS->getElementType() != I.getType())
     118             :     return false;
     119             : 
     120         145 :   unsigned ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
     121         145 :   if (SimplifiedAddrOp->getValue().getActiveBits() > 64)
     122             :     return false;
     123             :   int64_t SimplifiedAddrOpV = SimplifiedAddrOp->getSExtValue();
     124         145 :   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         143 :   uint64_t Index = static_cast<uint64_t>(SimplifiedAddrOpV) / ElemSize;
     130         143 :   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         143 :   Constant *CV = CDS->getElementAsConstant(Index);
     137             :   assert(CV && "Constant expected.");
     138         286 :   SimplifiedValues[&I] = CV;
     139             : 
     140         143 :   return true;
     141             : }
     142             : 
     143             : /// Try to simplify cast instruction.
     144        4067 : bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
     145             :   // Propagate constants through casts.
     146             :   Constant *COp = dyn_cast<Constant>(I.getOperand(0));
     147             :   if (!COp)
     148        2069 :     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        4090 :   if (COp && CastInst::castIsValid(I.getOpcode(), COp, I.getType())) {
     156        2041 :     if (Constant *C =
     157        4082 :             ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
     158        4082 :       SimplifiedValues[&I] = C;
     159        2041 :       return true;
     160             :     }
     161             :   }
     162             : 
     163        2026 :   return Base::visitCastInst(I);
     164             : }
     165             : 
     166             : /// Try to simplify cmp instruction.
     167        6885 : bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
     168             :   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
     169             : 
     170             :   // First try to handle simplified comparisons.
     171        6885 :   if (!isa<Constant>(LHS))
     172       13516 :     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
     173             :       LHS = SimpleLHS;
     174        6885 :   if (!isa<Constant>(RHS))
     175         154 :     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
     176             :       RHS = SimpleRHS;
     177             : 
     178        7111 :   if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
     179         144 :     auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
     180         144 :     if (SimplifiedLHS != SimplifiedAddresses.end()) {
     181          80 :       auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
     182          80 :       if (SimplifiedRHS != SimplifiedAddresses.end()) {
     183             :         SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
     184             :         SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
     185          40 :         if (LHSAddr.Base == RHSAddr.Base) {
     186          40 :           LHS = LHSAddr.Offset;
     187          40 :           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        6689 :       if (CLHS->getType() == CRHS->getType()) {
     196        6687 :         if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
     197       13374 :           SimplifiedValues[&I] = C;
     198        6687 :           return true;
     199             :         }
     200             :       }
     201             :     }
     202             :   }
     203             : 
     204         198 :   return Base::visitCmpInst(I);
     205             : }
     206             : 
     207        9122 : bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
     208             :   // Run base visitor first. This way we can gather some useful for later
     209             :   // analysis information.
     210        9122 :   if (Base::visitPHINode(PN))
     211             :     return true;
     212             : 
     213             :   // The loop induction PHI nodes are definitionally free.
     214        5014 :   return PN.getParent() == L->getHeader();
     215             : }

Generated by: LCOV version 1.13