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/ConstantFolding.h"
  17 #include "llvm/Analysis/InstructionSimplify.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  20 #include "llvm/IR/Operator.h"
  21
  22 using namespace llvm;
  23
  24 /// Try to simplify instruction \param I using its SCEV expression.
  25 ///
  26 /// The idea is that some AddRec expressions become constants, which then
  27 /// could trigger folding of other instructions. However, that only happens
  28 /// for expressions whose start value is also constant, which isn't always the
  29 /// case. In another common and important case the start value is just some
  30 /// address (i.e. SCEVUnknown) - in this case we compute the offset and save
  31 /// it along with the base address instead.
  32 bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
  33   if (!SE.isSCEVable(I->getType()))
  34     return false;
  35
  36   const SCEV *S = SE.getSCEV(I);
  37   if (auto *SC = dyn_cast<SCEVConstant>(S)) {
  38     SimplifiedValues[I] = SC->getValue();
  39     return true;
  40   }
  41
  42   // If we have a loop invariant computation, we only need to compute it once.
  43   // Given that, all but the first occurance are free.
  44   if (!IterationNumber->isZero() && SE.isLoopInvariant(S, L))
  45     return true;
  46
  47   auto *AR = dyn_cast<SCEVAddRecExpr>(S);
  48   if (!AR || AR->getLoop() != L)
  49     return false;
  50
  51   const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
  52   // Check if the AddRec expression becomes a constant.
  53   if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
  54     SimplifiedValues[I] = SC->getValue();
  55     return true;
  56   }
  57
  58   // Check if the offset from the base address becomes a constant.
  59   auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
  60   if (!Base)
  61     return false;
  62   std::optional<APInt> Offset =
  63       SE.computeConstantDifference(ValueAtIteration, Base);
  64   if (!Offset)
  65     return false;
  66   SimplifiedAddress Address;
  67   Address.Base = Base->getValue();
  68   Address.Offset = *Offset;
  69   SimplifiedAddresses[I] = Address;
  70   return false;
  71 }
  72
  73 /// Try to simplify binary operator I.
  74 ///
  75 /// TODO: Probably it's worth to hoist the code for estimating the
  76 /// simplifications effects to a separate class, since we have a very similar
  77 /// code in InlineCost already.
  78 bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
  79   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
  80   if (!isa<Constant>(LHS))
  81     if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
  82       LHS = SimpleLHS;
  83   if (!isa<Constant>(RHS))
  84     if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
  85       RHS = SimpleRHS;
  86
  87   Value *SimpleV = nullptr;
  88   const DataLayout &DL = I.getDataLayout();
  89   if (auto FI = dyn_cast<FPMathOperator>(&I))
  90     SimpleV =
  91         simplifyBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
  92   else
  93     SimpleV = simplifyBinOp(I.getOpcode(), LHS, RHS, DL);
  94
  95   if (SimpleV) {
  96     SimplifiedValues[&I] = SimpleV;
  97     return true;
  98   }
  99   return Base::visitBinaryOperator(I);
 100 }
 101
 102 /// Try to fold load I.
 103 bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
 104   Value *AddrOp = I.getPointerOperand();
 105
 106   auto AddressIt = SimplifiedAddresses.find(AddrOp);
 107   if (AddressIt == SimplifiedAddresses.end())
 108     return false;
 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   Constant *Res =
 117       ConstantFoldLoadFromConst(GV->getInitializer(), I.getType(),
 118                                 AddressIt->second.Offset, I.getDataLayout());
 119   if (!Res)
 120     return false;
 121
 122   SimplifiedValues[&I] = Res;
 123   return true;
 124 }
 125
 126 /// Try to simplify cast instruction.
 127 bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
 128   Value *Op = I.getOperand(0);
 129   if (Value *Simplified = SimplifiedValues.lookup(Op))
 130     Op = Simplified;
 131
 132   // The cast can be invalid, because SimplifiedValues contains results of SCEV
 133   // analysis, which operates on integers (and, e.g., might convert i8* null to
 134   // i32 0).
 135   if (CastInst::castIsValid(I.getOpcode(), Op, I.getType())) {
 136     const DataLayout &DL = I.getDataLayout();
 137     if (Value *V = simplifyCastInst(I.getOpcode(), Op, I.getType(), DL)) {
 138       SimplifiedValues[&I] = V;
 139       return true;
 140     }
 141   }
 142
 143   return Base::visitCastInst(I);
 144 }
 145
 146 /// Try to simplify cmp instruction.
 147 bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
 148   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 149
 150   // First try to handle simplified comparisons.
 151   if (!isa<Constant>(LHS))
 152     if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
 153       LHS = SimpleLHS;
 154   if (!isa<Constant>(RHS))
 155     if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
 156       RHS = SimpleRHS;
 157
 158   if (!isa<Constant>(LHS) && !isa<Constant>(RHS) && !I.isSigned()) {
 159     auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
 160     if (SimplifiedLHS != SimplifiedAddresses.end()) {
 161       auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
 162       if (SimplifiedRHS != SimplifiedAddresses.end()) {
 163         SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
 164         SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
 165         if (LHSAddr.Base == RHSAddr.Base) {
 166           // FIXME: This is only correct for equality predicates. For
 167           // unsigned predicates, this only holds if we have nowrap flags,
 168           // which we don't track (for nuw it's valid as-is, for nusw it
 169           // requires converting the predicated to signed). As this is used only
 170           // for cost modelling, this is not a correctness issue.
 171           bool Res = ICmpInst::compare(LHSAddr.Offset, RHSAddr.Offset,
 172                                        I.getPredicate());
 173           SimplifiedValues[&I] = ConstantInt::getBool(I.getType(), Res);
 174           return true;
 175         }
 176       }
 177     }
 178   }
 179
 180   const DataLayout &DL = I.getDataLayout();
 181   if (Value *V = simplifyCmpInst(I.getPredicate(), LHS, RHS, DL)) {
 182     SimplifiedValues[&I] = V;
 183     return true;
 184   }
 185
 186   return Base::visitCmpInst(I);
 187 }
 188
 189 bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
 190   // Run base visitor first. This way we can gather some useful for later
 191   // analysis information.
 192   if (Base::visitPHINode(PN))
 193     return true;
 194
 195   // The loop induction PHI nodes are definitionally free.
 196   return PN.getParent() == L->getHeader();
 197 }
 198
 199 bool UnrolledInstAnalyzer::visitInstruction(Instruction &I) {
 200   return simplifyInstWithSCEV(&I);
 201 }