1//===- ScalarEvolutionDivision.h - See below --------------------*- 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 defines the class that knows how to divide SCEV's.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Analysis/ScalarEvolutionDivision.h"
14#include "llvm/ADT/APInt.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/Analysis/ScalarEvolution.h"
18#include "llvm/IR/InstIterator.h"
19#include "llvm/IR/Instructions.h"
20#include "llvm/Support/Casting.h"
21#include <cassert>
22
23#define DEBUG_TYPE "scev-division"
24
25namespace llvm {
26class Type;
27} // namespace llvm
28
29using namespace llvm;
30
31static inline int sizeOfSCEV(const SCEV *S) {
32 struct FindSCEVSize {
33 int Size = 0;
34
35 FindSCEVSize() = default;
36
37 bool follow(const SCEV *S) {
38 ++Size;
39 // Keep looking at all operands of S.
40 return true;
41 }
42
43 bool isDone() const { return false; }
44 };
45
46 FindSCEVSize F;
47 SCEVTraversal<FindSCEVSize> ST(F);
48 ST.visitAll(Root: S);
49 return F.Size;
50}
51
52// Computes the Quotient and Remainder of the division of Numerator by
53// Denominator.
54void SCEVDivision::divide(ScalarEvolution &SE, const SCEV *Numerator,
55 const SCEV *Denominator, const SCEV **Quotient,
56 const SCEV **Remainder) {
57 assert(Numerator && Denominator && "Uninitialized SCEV");
58 assert(Numerator->getType() == Denominator->getType() &&
59 "Numerator and Denominator must have the same type");
60
61 SCEVDivision D(SE, Numerator, Denominator);
62
63 // Check for the trivial case here to avoid having to check for it in the
64 // rest of the code.
65 if (Numerator == Denominator) {
66 *Quotient = D.One;
67 *Remainder = D.Zero;
68 return;
69 }
70
71 if (Numerator->isZero()) {
72 *Quotient = D.Zero;
73 *Remainder = D.Zero;
74 return;
75 }
76
77 // A simple case when N/1. The quotient is N.
78 if (Denominator->isOne()) {
79 *Quotient = Numerator;
80 *Remainder = D.Zero;
81 return;
82 }
83
84 // Split the Denominator when it is a product.
85 if (const SCEVMulExpr *T = dyn_cast<SCEVMulExpr>(Val: Denominator)) {
86 const SCEV *Q, *R;
87 *Quotient = Numerator;
88 for (const SCEV *Op : T->operands()) {
89 divide(SE, Numerator: *Quotient, Denominator: Op, Quotient: &Q, Remainder: &R);
90 *Quotient = Q;
91
92 // Bail out when the Numerator is not divisible by one of the terms of
93 // the Denominator.
94 if (!R->isZero()) {
95 *Quotient = D.Zero;
96 *Remainder = Numerator;
97 return;
98 }
99 }
100 *Remainder = D.Zero;
101 return;
102 }
103
104 D.visit(S: Numerator);
105 *Quotient = D.Quotient;
106 *Remainder = D.Remainder;
107}
108
109void SCEVDivision::visitConstant(const SCEVConstant *Numerator) {
110 if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Val: Denominator)) {
111 APInt NumeratorVal = Numerator->getAPInt();
112 APInt DenominatorVal = D->getAPInt();
113 assert(NumeratorVal.getBitWidth() == DenominatorVal.getBitWidth() &&
114 "Numerator and Denominator must have the same bit width");
115
116 APInt QuotientVal(NumeratorVal.getBitWidth(), 0);
117 APInt RemainderVal(NumeratorVal.getBitWidth(), 0);
118 APInt::sdivrem(LHS: NumeratorVal, RHS: DenominatorVal, Quotient&: QuotientVal, Remainder&: RemainderVal);
119 Quotient = SE.getConstant(Val: QuotientVal);
120 Remainder = SE.getConstant(Val: RemainderVal);
121 return;
122 }
123}
124
125void SCEVDivision::visitVScale(const SCEVVScale *Numerator) {
126 return cannotDivide(Numerator);
127}
128
129void SCEVDivision::visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
130 const SCEV *StartQ, *StartR, *StepQ, *StepR;
131 if (!Numerator->isAffine())
132 return cannotDivide(Numerator);
133 divide(SE, Numerator: Numerator->getStart(), Denominator, Quotient: &StartQ, Remainder: &StartR);
134 divide(SE, Numerator: Numerator->getStepRecurrence(SE), Denominator, Quotient: &StepQ, Remainder: &StepR);
135 // Bail out if the types do not match.
136 Type *Ty = Denominator->getType();
137 if (Ty != StartQ->getType() || Ty != StartR->getType() ||
138 Ty != StepQ->getType() || Ty != StepR->getType())
139 return cannotDivide(Numerator);
140
141 Quotient = SE.getAddRecExpr(Start: StartQ, Step: StepQ, L: Numerator->getLoop(),
142 Flags: SCEV::NoWrapFlags::FlagAnyWrap);
143 Remainder = SE.getAddRecExpr(Start: StartR, Step: StepR, L: Numerator->getLoop(),
144 Flags: SCEV::NoWrapFlags::FlagAnyWrap);
145}
146
147void SCEVDivision::visitAddExpr(const SCEVAddExpr *Numerator) {
148 SmallVector<SCEVUse, 2> Qs, Rs;
149 Type *Ty = Denominator->getType();
150
151 for (const SCEV *Op : Numerator->operands()) {
152 const SCEV *Q, *R;
153 divide(SE, Numerator: Op, Denominator, Quotient: &Q, Remainder: &R);
154
155 // Bail out if types do not match.
156 if (Ty != Q->getType() || Ty != R->getType())
157 return cannotDivide(Numerator);
158
159 Qs.push_back(Elt: Q);
160 Rs.push_back(Elt: R);
161 }
162
163 if (Qs.size() == 1) {
164 Quotient = Qs[0];
165 Remainder = Rs[0];
166 return;
167 }
168
169 Quotient = SE.getAddExpr(Ops&: Qs);
170 Remainder = SE.getAddExpr(Ops&: Rs);
171}
172
173void SCEVDivision::visitMulExpr(const SCEVMulExpr *Numerator) {
174 SmallVector<SCEVUse, 2> Qs;
175 Type *Ty = Denominator->getType();
176
177 bool FoundDenominatorTerm = false;
178 for (const SCEV *Op : Numerator->operands()) {
179 // Bail out if types do not match.
180 if (Ty != Op->getType())
181 return cannotDivide(Numerator);
182
183 if (FoundDenominatorTerm) {
184 Qs.push_back(Elt: Op);
185 continue;
186 }
187
188 // Check whether Denominator divides one of the product operands.
189 const SCEV *Q, *R;
190 divide(SE, Numerator: Op, Denominator, Quotient: &Q, Remainder: &R);
191 if (!R->isZero()) {
192 Qs.push_back(Elt: Op);
193 continue;
194 }
195
196 // Bail out if types do not match.
197 if (Ty != Q->getType())
198 return cannotDivide(Numerator);
199
200 FoundDenominatorTerm = true;
201 Qs.push_back(Elt: Q);
202 }
203
204 if (FoundDenominatorTerm) {
205 Remainder = Zero;
206 if (Qs.size() == 1)
207 Quotient = Qs[0];
208 else
209 Quotient = SE.getMulExpr(Ops&: Qs);
210 return;
211 }
212
213 if (!isa<SCEVUnknown>(Val: Denominator))
214 return cannotDivide(Numerator);
215
216 // The Remainder is obtained by replacing Denominator by 0 in Numerator.
217 ValueToSCEVMapTy RewriteMap;
218 RewriteMap[cast<SCEVUnknown>(Val: Denominator)->getValue()] = Zero;
219 Remainder = SCEVParameterRewriter::rewrite(Scev: Numerator, SE, Map&: RewriteMap);
220
221 if (Remainder->isZero()) {
222 // The Quotient is obtained by replacing Denominator by 1 in Numerator.
223 RewriteMap[cast<SCEVUnknown>(Val: Denominator)->getValue()] = One;
224 Quotient = SCEVParameterRewriter::rewrite(Scev: Numerator, SE, Map&: RewriteMap);
225 return;
226 }
227
228 // Quotient is (Numerator - Remainder) divided by Denominator.
229 const SCEV *Q, *R;
230 const SCEV *Diff = SE.getMinusSCEV(LHS: Numerator, RHS: Remainder);
231 // This SCEV does not seem to simplify: fail the division here.
232 if (sizeOfSCEV(S: Diff) > sizeOfSCEV(S: Numerator))
233 return cannotDivide(Numerator);
234 divide(SE, Numerator: Diff, Denominator, Quotient: &Q, Remainder: &R);
235 if (R != Zero)
236 return cannotDivide(Numerator);
237 Quotient = Q;
238}
239
240SCEVDivision::SCEVDivision(ScalarEvolution &S, const SCEV *Numerator,
241 const SCEV *Denominator)
242 : SE(S), Denominator(Denominator) {
243 Zero = SE.getZero(Ty: Denominator->getType());
244 One = SE.getOne(Ty: Denominator->getType());
245
246 // We generally do not know how to divide Expr by Denominator. We initialize
247 // the division to a "cannot divide" state to simplify the rest of the code.
248 cannotDivide(Numerator);
249}
250
251// Convenience function for giving up on the division. We set the quotient to
252// be equal to zero and the remainder to be equal to the numerator.
253void SCEVDivision::cannotDivide(const SCEV *Numerator) {
254 Quotient = Zero;
255 Remainder = Numerator;
256}
257
258void SCEVDivisionPrinterPass::runImpl(Function &F, ScalarEvolution &SE) {
259 OS << "Printing analysis 'Scalar Evolution Division' for function '"
260 << F.getName() << "':\n";
261 for (Instruction &Inst : instructions(F)) {
262 BinaryOperator *Div = dyn_cast<BinaryOperator>(Val: &Inst);
263 if (!Div || Div->getOpcode() != Instruction::SDiv)
264 continue;
265
266 const SCEV *Numerator = SE.getSCEV(V: Div->getOperand(i_nocapture: 0));
267 const SCEV *Denominator = SE.getSCEV(V: Div->getOperand(i_nocapture: 1));
268 const SCEV *Quotient, *Remainder;
269 SCEVDivision::divide(SE, Numerator, Denominator, Quotient: &Quotient, Remainder: &Remainder);
270
271 OS << "Instruction: " << *Div << "\n";
272 OS.indent(NumSpaces: 2) << "Numerator: " << *Numerator << "\n";
273 OS.indent(NumSpaces: 2) << "Denominator: " << *Denominator << "\n";
274 OS.indent(NumSpaces: 2) << "Quotient: " << *Quotient << "\n";
275 OS.indent(NumSpaces: 2) << "Remainder: " << *Remainder << "\n";
276 }
277}
278
279PreservedAnalyses SCEVDivisionPrinterPass::run(Function &F,
280 FunctionAnalysisManager &AM) {
281 ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
282 runImpl(F, SE);
283 return PreservedAnalyses::all();
284}
285