lib/Analysis/LoopUnrollAnalyzer.cpp

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