LoopUnrollAnalyzer.cpp

Go to the documentation of this file.

//===- LoopUnrollAnalyzer.cpp - Unrolling Effect Estimation -----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements UnrolledInstAnalyzer class. It's used for predicting
// potential effects that loop unrolling might have, such as enabling constant
// propagation and other optimizations.
//
//===----------------------------------------------------------------------===//
 
#include "llvm/Analysis/LoopUnrollAnalyzer.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Operator.h"
 
using namespace llvm;
 
/// Try to simplify instruction \param I using its SCEV expression.
///
/// The idea is that some AddRec expressions become constants, which then
/// could trigger folding of other instructions. However, that only happens
/// for expressions whose start value is also constant, which isn't always the
/// case. In another common and important case the start value is just some
/// address (i.e. SCEVUnknown) - in this case we compute the offset and save
/// it along with the base address instead.
bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
  if (!SE.isSCEVable(I->getType()))
    return false;
 
  const SCEV *S = SE.getSCEV(I);
  if (auto *SC = dyn_cast<SCEVConstant>(S)) {
    SimplifiedValues[I] = SC->getValue();
    return true;
  }
 
  // If we have a loop invariant computation, we only need to compute it once.
  // Given that, all but the first occurance are free.
  if (!IterationNumber->isZero() && SE.isLoopInvariant(S, L))
    return true;
 
  auto *AR = dyn_cast<SCEVAddRecExpr>(S);
  if (!AR || AR->getLoop() != L)
    return false;
 
  const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
  // Check if the AddRec expression becomes a constant.
  if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
    SimplifiedValues[I] = SC->getValue();
    return true;
  }
 
  // Check if the offset from the base address becomes a constant.
  auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
  if (!Base)
    return false;
  std::optional<APInt> Offset =
      SE.computeConstantDifference(ValueAtIteration, Base);
  if (!Offset)
    return false;
  SimplifiedAddress Address;
  Address.Base = Base->getValue();
  Address.Offset = *Offset;
  SimplifiedAddresses[I] = std::move(Address);
  return false;
}
 
/// Try to simplify binary operator I.
///
/// TODO: Probably it's worth to hoist the code for estimating the
/// simplifications effects to a separate class, since we have a very similar
/// code in InlineCost already.
bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
  if (!isa<Constant>(LHS))
    if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
      LHS = SimpleLHS;
  if (!isa<Constant>(RHS))
    if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
      RHS = SimpleRHS;
 
  Value *SimpleV = nullptr;
  const DataLayout &DL = I.getDataLayout();
  if (auto FI = dyn_cast<FPMathOperator>(&I))
    SimpleV =
        simplifyBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
  else
    SimpleV = simplifyBinOp(I.getOpcode(), LHS, RHS, DL);
 
  if (SimpleV) {
    SimplifiedValues[&I] = SimpleV;
    return true;
  }
  return Base::visitBinaryOperator(I);
}
 
/// Try to fold load I.
bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
  Value *AddrOp = I.getPointerOperand();
 
  auto AddressIt = SimplifiedAddresses.find(AddrOp);
  if (AddressIt == SimplifiedAddresses.end())
    return false;
 
  auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
  // We're only interested in loads that can be completely folded to a
  // constant.
  if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
    return false;
 
  Constant *Res =
      ConstantFoldLoadFromConst(GV->getInitializer(), I.getType(),
                                AddressIt->second.Offset, I.getDataLayout());
  if (!Res)
    return false;
 
  SimplifiedValues[&I] = Res;
  return true;
}
 
/// Try to simplify cast instruction.
bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
  Value *Op = I.getOperand(0);
  if (Value *Simplified = SimplifiedValues.lookup(Op))
    Op = Simplified;
 
  // The cast can be invalid, because SimplifiedValues contains results of SCEV
  // analysis, which operates on integers (and, e.g., might convert i8* null to
  // i32 0).
  if (CastInst::castIsValid(I.getOpcode(), Op, I.getType())) {
    const DataLayout &DL = I.getDataLayout();
    if (Value *V = simplifyCastInst(I.getOpcode(), Op, I.getType(), DL)) {
      SimplifiedValues[&I] = V;
      return true;
    }
  }
 
  return Base::visitCastInst(I);
}
 
/// Try to simplify cmp instruction.
bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 
  // First try to handle simplified comparisons.
  if (!isa<Constant>(LHS))
    if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
      LHS = SimpleLHS;
  if (!isa<Constant>(RHS))
    if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
      RHS = SimpleRHS;
 
  if (!isa<Constant>(LHS) && !isa<Constant>(RHS) && !I.isSigned()) {
    auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
    if (SimplifiedLHS != SimplifiedAddresses.end()) {
      auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
      if (SimplifiedRHS != SimplifiedAddresses.end()) {
        SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
        SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
        if (LHSAddr.Base == RHSAddr.Base) {
          // FIXME: This is only correct for equality predicates. For
          // unsigned predicates, this only holds if we have nowrap flags,
          // which we don't track (for nuw it's valid as-is, for nusw it
          // requires converting the predicated to signed). As this is used only
          // for cost modelling, this is not a correctness issue.
          bool Res = ICmpInst::compare(LHSAddr.Offset, RHSAddr.Offset,
                                       I.getPredicate());
          SimplifiedValues[&I] = ConstantInt::getBool(I.getType(), Res);
          return true;
        }
      }
    }
  }
 
  const DataLayout &DL = I.getDataLayout();
  if (Value *V = simplifyCmpInst(I.getPredicate(), LHS, RHS, DL)) {
    SimplifiedValues[&I] = V;
    return true;
  }
 
  return Base::visitCmpInst(I);
}
 
bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
  // Run base visitor first. This way we can gather some useful for later
  // analysis information.
  if (Base::visitPHINode(PN))
    return true;
 
  // The loop induction PHI nodes are definitionally free.
  return PN.getParent() == L->getHeader();
}
 
/// Returns true if \p I computes the same value on every iteration of the
/// loop: it does not access memory, has no side effects, and all of its
/// operands are defined outside the loop or are themselves such computations.
/// Unlike SCEV-based invariance this works for any type, e.g. floating point.
bool UnrolledInstAnalyzer::isInvariantComputation(Instruction *I) {
  if (!L->contains(I))
    return true;
  if (auto It = InvariantInsts.find(I); It != InvariantInsts.end())
    return It->second;
  auto *II = dyn_cast<IntrinsicInst>(I);
  if (isa<PHINode, AllocaInst>(I) || I->isTerminator() ||
      (II && II->isAssumeLikeIntrinsic()) || I->mayReadOrWriteMemory() ||
      I->mayHaveSideEffects()) {
    InvariantInsts[I] = false;
    return false;
  }
  bool Invariant = all_of(I->operands(), [&](Value *Op) {
    auto *OpI = dyn_cast<Instruction>(Op);
    return !OpI || isInvariantComputation(OpI);
  });
  InvariantInsts[I] = Invariant;
  return Invariant;
}
 
bool UnrolledInstAnalyzer::visitInstruction(Instruction &I) {
  if (simplifyInstWithSCEV(&I))
    return true;
 
  // Invariance of SCEVable values is decided by SCEV above. For other values,
  // e.g. floating point, an invariant computation likewise only has to be
  // performed once after unrolling; all but the first occurrence are free.
  return !SE.isSCEVable(I.getType()) && !IterationNumber->isZero() &&
         isInvariantComputation(&I);
}