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
22using 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.
32bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
33 if (!SE.isSCEVable(Ty: I->getType()))
34 return false;
35
36 const SCEV *S = SE.getSCEV(V: I);
37 if (auto *SC = dyn_cast<SCEVConstant>(Val: 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>(Val: S);
48 if (!AR || AR->getLoop() != L)
49 return false;
50
51 const SCEV *ValueAtIteration = AR->evaluateAtIteration(It: IterationNumber, SE);
52 // Check if the AddRec expression becomes a constant.
53 if (auto *SC = dyn_cast<SCEVConstant>(Val: 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>(Val: SE.getPointerBase(V: S));
60 if (!Base)
61 return false;
62 std::optional<APInt> Offset =
63 SE.computeConstantDifference(LHS: ValueAtIteration, RHS: 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.
78bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
79 Value *LHS = I.getOperand(i_nocapture: 0), *RHS = I.getOperand(i_nocapture: 1);
80 if (!isa<Constant>(Val: LHS))
81 if (Value *SimpleLHS = SimplifiedValues.lookup(Val: LHS))
82 LHS = SimpleLHS;
83 if (!isa<Constant>(Val: RHS))
84 if (Value *SimpleRHS = SimplifiedValues.lookup(Val: RHS))
85 RHS = SimpleRHS;
86
87 Value *SimpleV = nullptr;
88 const DataLayout &DL = I.getDataLayout();
89 if (auto FI = dyn_cast<FPMathOperator>(Val: &I))
90 SimpleV =
91 simplifyBinOp(Opcode: I.getOpcode(), LHS, RHS, FMF: FI->getFastMathFlags(), Q: DL);
92 else
93 SimpleV = simplifyBinOp(Opcode: I.getOpcode(), LHS, RHS, Q: 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.
103bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
104 Value *AddrOp = I.getPointerOperand();
105
106 auto AddressIt = SimplifiedAddresses.find(Val: AddrOp);
107 if (AddressIt == SimplifiedAddresses.end())
108 return false;
109
110 auto *GV = dyn_cast<GlobalVariable>(Val: 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(C: GV->getInitializer(), Ty: I.getType(),
118 Offset: AddressIt->second.Offset, DL: I.getDataLayout());
119 if (!Res)
120 return false;
121
122 SimplifiedValues[&I] = Res;
123 return true;
124}
125
126/// Try to simplify cast instruction.
127bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
128 Value *Op = I.getOperand(i_nocapture: 0);
129 if (Value *Simplified = SimplifiedValues.lookup(Val: 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(op: I.getOpcode(), S: Op, DstTy: I.getType())) {
136 const DataLayout &DL = I.getDataLayout();
137 if (Value *V = simplifyCastInst(CastOpc: I.getOpcode(), Op, Ty: I.getType(), Q: DL)) {
138 SimplifiedValues[&I] = V;
139 return true;
140 }
141 }
142
143 return Base::visitCastInst(I);
144}
145
146/// Try to simplify cmp instruction.
147bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
148 Value *LHS = I.getOperand(i_nocapture: 0), *RHS = I.getOperand(i_nocapture: 1);
149
150 // First try to handle simplified comparisons.
151 if (!isa<Constant>(Val: LHS))
152 if (Value *SimpleLHS = SimplifiedValues.lookup(Val: LHS))
153 LHS = SimpleLHS;
154 if (!isa<Constant>(Val: RHS))
155 if (Value *SimpleRHS = SimplifiedValues.lookup(Val: RHS))
156 RHS = SimpleRHS;
157
158 if (!isa<Constant>(Val: LHS) && !isa<Constant>(Val: RHS) && !I.isSigned()) {
159 auto SimplifiedLHS = SimplifiedAddresses.find(Val: LHS);
160 if (SimplifiedLHS != SimplifiedAddresses.end()) {
161 auto SimplifiedRHS = SimplifiedAddresses.find(Val: 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(LHS: LHSAddr.Offset, RHS: RHSAddr.Offset,
172 Pred: I.getPredicate());
173 SimplifiedValues[&I] = ConstantInt::getBool(Ty: I.getType(), V: Res);
174 return true;
175 }
176 }
177 }
178 }
179
180 const DataLayout &DL = I.getDataLayout();
181 if (Value *V = simplifyCmpInst(Predicate: I.getPredicate(), LHS, RHS, Q: DL)) {
182 SimplifiedValues[&I] = V;
183 return true;
184 }
185
186 return Base::visitCmpInst(I);
187}
188
189bool 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(I&: PN))
193 return true;
194
195 // The loop induction PHI nodes are definitionally free.
196 return PN.getParent() == L->getHeader();
197}
198
199bool UnrolledInstAnalyzer::visitInstruction(Instruction &I) {
200 return simplifyInstWithSCEV(I: &I);
201}
202