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/LoopInfo.h"
  17
  18 using namespace llvm;
  19
  20 /// 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 bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
  29   if (!SE.isSCEVable(I->getType()))
  30     return false;
  31
  32   const SCEV *S = SE.getSCEV(I);
  33   if (auto *SC = dyn_cast<SCEVConstant>(S)) {
  34     SimplifiedValues[I] = SC->getValue();
  35     return true;
  36   }
  37
  38   // If we have a loop invariant computation, we only need to compute it once.
  39   // Given that, all but the first occurance are free.
  40   if (!IterationNumber->isZero() && SE.isLoopInvariant(S, L))
  41     return true;
  42
  43   auto *AR = dyn_cast<SCEVAddRecExpr>(S);
  44   if (!AR || AR->getLoop() != L)
  45     return false;
  46
  47   const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
  48   // Check if the AddRec expression becomes a constant.
  49   if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
  50     SimplifiedValues[I] = SC->getValue();
  51     return true;
  52   }
  53
  54   // Check if the offset from the base address becomes a constant.
  55   auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
  56   if (!Base)
  57     return false;
  58   auto *Offset =
  59       dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
  60   if (!Offset)
  61     return false;
  62   SimplifiedAddress Address;
  63   Address.Base = Base->getValue();
  64   Address.Offset = Offset->getValue();
  65   SimplifiedAddresses[I] = Address;
  66   return false;
  67 }
  68
  69 /// Try to simplify binary operator I.
  70 ///
  71 /// TODO: Probably it's worth to hoist the code for estimating the
  72 /// simplifications effects to a separate class, since we have a very similar
  73 /// code in InlineCost already.
  74 bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
  75   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
  76   if (!isa<Constant>(LHS))
  77     if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
  78       LHS = SimpleLHS;
  79   if (!isa<Constant>(RHS))
  80     if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
  81       RHS = SimpleRHS;
  82
  83   Value *SimpleV = nullptr;
  84   const DataLayout &DL = I.getModule()->getDataLayout();
  85   if (auto FI = dyn_cast<FPMathOperator>(&I))
  86     SimpleV =
  87         SimplifyBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
  88   else
  89     SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
  90
  91   if (SimpleV) {
  92     SimplifiedValues[&I] = SimpleV;
  93     return true;
  94   }
  95   return Base::visitBinaryOperator(I);
  96 }
  97
  98 /// Try to fold load I.
  99 bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
 100   Value *AddrOp = I.getPointerOperand();
 101
 102   auto AddressIt = SimplifiedAddresses.find(AddrOp);
 103   if (AddressIt == SimplifiedAddresses.end())
 104     return false;
 105   ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
 106
 107   auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
 108   // We're only interested in loads that can be completely folded to a
 109   // constant.
 110   if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
 111     return false;
 112
 113   ConstantDataSequential *CDS =
 114       dyn_cast<ConstantDataSequential>(GV->getInitializer());
 115   if (!CDS)
 116     return false;
 117
 118   // We might have a vector load from an array. FIXME: for now we just bail
 119   // out in this case, but we should be able to resolve and simplify such
 120   // loads.
 121   if (CDS->getElementType() != I.getType())
 122     return false;
 123
 124   unsigned ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
 125   if (SimplifiedAddrOp->getValue().getActiveBits() > 64)
 126     return false;
 127   int64_t SimplifiedAddrOpV = SimplifiedAddrOp->getSExtValue();
 128   if (SimplifiedAddrOpV < 0) {
 129     // FIXME: For now we conservatively ignore out of bound accesses, but
 130     // we're allowed to perform the optimization in this case.
 131     return false;
 132   }
 133   uint64_t Index = static_cast<uint64_t>(SimplifiedAddrOpV) / ElemSize;
 134   if (Index >= CDS->getNumElements()) {
 135     // FIXME: For now we conservatively ignore out of bound accesses, but
 136     // we're allowed to perform the optimization in this case.
 137     return false;
 138   }
 139
 140   Constant *CV = CDS->getElementAsConstant(Index);
 141   assert(CV && "Constant expected.");
 142   SimplifiedValues[&I] = CV;
 143
 144   return true;
 145 }
 146
 147 /// Try to simplify cast instruction.
 148 bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
 149   Value *Op = I.getOperand(0);
 150   if (Value *Simplified = SimplifiedValues.lookup(Op))
 151     Op = Simplified;
 152
 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   if (CastInst::castIsValid(I.getOpcode(), Op, I.getType())) {
 157     const DataLayout &DL = I.getModule()->getDataLayout();
 158     if (Value *V = SimplifyCastInst(I.getOpcode(), Op, I.getType(), DL)) {
 159       SimplifiedValues[&I] = V;
 160       return true;
 161     }
 162   }
 163
 164   return Base::visitCastInst(I);
 165 }
 166
 167 /// Try to simplify cmp instruction.
 168 bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
 169   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 170
 171   // First try to handle simplified comparisons.
 172   if (!isa<Constant>(LHS))
 173     if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
 174       LHS = SimpleLHS;
 175   if (!isa<Constant>(RHS))
 176     if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
 177       RHS = SimpleRHS;
 178
 179   if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
 180     auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
 181     if (SimplifiedLHS != SimplifiedAddresses.end()) {
 182       auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
 183       if (SimplifiedRHS != SimplifiedAddresses.end()) {
 184         SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
 185         SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
 186         if (LHSAddr.Base == RHSAddr.Base) {
 187           LHS = LHSAddr.Offset;
 188           RHS = RHSAddr.Offset;
 189         }
 190       }
 191     }
 192   }
 193
 194   const DataLayout &DL = I.getModule()->getDataLayout();
 195   if (Value *V = SimplifyCmpInst(I.getPredicate(), LHS, RHS, DL)) {
 196     SimplifiedValues[&I] = V;
 197     return true;
 198   }
 199
 200   return Base::visitCmpInst(I);
 201 }
 202
 203 bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
 204   // Run base visitor first. This way we can gather some useful for later
 205   // analysis information.
 206   if (Base::visitPHINode(PN))
 207     return true;
 208
 209   // The loop induction PHI nodes are definitionally free.
 210   return PN.getParent() == L->getHeader();
 211 }
 212
 213 bool UnrolledInstAnalyzer::visitInstruction(Instruction &I) {
 214   return simplifyInstWithSCEV(&I);
 215 }