LLVM  14.0.0git
LoopUnrollAnalyzer.cpp
Go to the documentation of this file.
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 
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  }
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 
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 }
llvm::InstVisitor< UnrolledInstAnalyzer, bool >::visitCastInst
bool visitCastInst(CastInst &I)
Definition: InstVisitor.h:261
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::CastInst::castIsValid
static bool castIsValid(Instruction::CastOps op, Type *SrcTy, Type *DstTy)
This method can be used to determine if a cast from SrcTy to DstTy using Opcode op is valid or not.
Definition: Instructions.cpp:3423
llvm::SimplifyCmpInst
Value * SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
Definition: InstructionSimplify.cpp:5333
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::ScalarEvolution::getPointerBase
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
Definition: ScalarEvolution.cpp:4365
llvm::SimplifyCastInst
Value * SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
Definition: InstructionSimplify.cpp:4676
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::ConstantDataSequential
ConstantDataSequential - A vector or array constant whose element type is a simple 1/2/4/8-byte integ...
Definition: Constants.h:569
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:410
llvm::JumpTable::Simplified
@ Simplified
Definition: TargetOptions.h:47
llvm::Instruction
Definition: Instruction.h:45
llvm::InstVisitor< UnrolledInstAnalyzer, bool >::visitPHINode
bool visitPHINode(PHINode &I)
Definition: InstVisitor.h:176
LoopInfo.h
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4066
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
uint64_t
llvm::SimplifyBinOp
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
Definition: InstructionSimplify.cpp:5315
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::ConstantDataSequential::getElementType
Type * getElementType() const
Return the element type of the array/vector.
Definition: Constants.cpp:2882
llvm::HighlightColor::Address
@ Address
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ConstantDataSequential::getElementAsConstant
Constant * getElementAsConstant(unsigned i) const
Return a Constant for a specified index's element.
Definition: Constants.cpp:3250
llvm::BinaryOperator
Definition: InstrTypes.h:189
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::ConstantInt::getSExtValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:148
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
LoopUnrollAnalyzer.h
llvm::InstVisitor< UnrolledInstAnalyzer, bool >::visitBinaryOperator
bool visitBinaryOperator(BinaryOperator &I)
Definition: InstVisitor.h:263
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:12612
llvm::ScalarEvolution::getMinusSCEV
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
Definition: ScalarEvolution.cpp:4199
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:3932
llvm::InstVisitor< UnrolledInstAnalyzer, bool >::visitCmpInst
bool visitCmpInst(CmpInst &I)
Definition: InstVisitor.h:264
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::APInt::getActiveBits
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1427
llvm::PHINode
Definition: Instructions.h:2625
llvm::SCEV::isZero
bool isZero() const
Return true if the expression is a constant zero.
Definition: ScalarEvolution.cpp:409
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Type::getPrimitiveSizeInBits
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:128
llvm::ConstantDataSequential::getNumElements
unsigned getNumElements() const
Return the number of elements in the array or vector.
Definition: Constants.cpp:2908