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