LLVM 19.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
19#include "llvm/IR/Operator.h"
20
21using 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.
31bool 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.
77bool 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 }
99}
100
101/// Try to fold load I.
102bool 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
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
144 assert(CV && "Constant expected.");
145 SimplifiedValues[&I] = CV;
146
147 return true;
148}
149
150/// Try to simplify cast instruction.
151bool 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.
171bool 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
206bool 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
216bool UnrolledInstAnalyzer::visitInstruction(Instruction &I) {
217 return simplifyInstWithSCEV(&I);
218}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1463
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:574
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.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:950
ConstantDataSequential - A vector or array constant whose element type is a simple 1/2/4/8-byte integ...
Definition: Constants.h:583
unsigned getNumElements() const
Return the number of elements in the array or vector.
Definition: Constants.cpp:2748
Constant * getElementAsConstant(unsigned i) const
Return a Constant for a specified index's element.
Definition: Constants.cpp:3090
Type * getElementType() const
Return the element type of the array/vector.
Definition: Constants.cpp:2722
This is the shared class of boolean and integer constants.
Definition: Constants.h:80
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:160
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:145
This is an important base class in LLVM.
Definition: Constant.h:41
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
const BasicBlock * getParent() const
Definition: Instruction.h:152
An instruction for reading from memory.
Definition: Instructions.h:184
BlockT * getHeader() const
This class represents an analyzed expression in the program.
bool isZero() const
Return true if the expression is a constant zero.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
LLVM Value Representation.
Definition: Value.h:74
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.