1//===- llvm/Analysis/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#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONDIVISION_H
14#define LLVM_ANALYSIS_SCALAREVOLUTIONDIVISION_H
15
16#include "llvm/Analysis/ScalarEvolutionExpressions.h"
17
18namespace llvm {
19
20class SCEV;
21
22class ScalarEvolution;
23
24struct SCEVCouldNotCompute;
25
26struct SCEVDivision : public SCEVVisitor<SCEVDivision, void> {
27public:
28 /// Computes the Quotient and Remainder of the division of Numerator by
29 /// Denominator. We are not actually performing the division here. Instead, we
30 /// are trying to find SCEV expressions Quotient and Remainder that satisfy:
31 ///
32 /// Numerator = Denominator * Quotient + Remainder
33 ///
34 /// There may be multiple valid answers for Quotient and Remainder. This
35 /// function finds one of them. Especially, there is always a trivial
36 /// solution: (Quotient, Remainder) = (0, Numerator).
37 ///
38 /// Note the following:
39 /// * The condition Remainder < Denominator is NOT necessarily required.
40 /// * Division of constants is performed as signed.
41 /// * The multiplication of Quotient and Denominator may wrap.
42 /// * The addition of Quotient*Denominator and Remainder may wrap.
43 LLVM_ABI static void divide(ScalarEvolution &SE, const SCEV *Numerator,
44 const SCEV *Denominator, const SCEV **Quotient,
45 const SCEV **Remainder);
46
47 // Except in the trivial case described above, we do not know how to divide
48 // Expr by Denominator for the following functions with empty implementation.
49 void visitPtrToAddrExpr(const SCEVPtrToAddrExpr *Numerator) {}
50 void visitTruncateExpr(const SCEVTruncateExpr *Numerator) {}
51 void visitZeroExtendExpr(const SCEVZeroExtendExpr *Numerator) {}
52 void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {}
53 void visitUDivExpr(const SCEVUDivExpr *Numerator) {}
54 void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {}
55 void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {}
56 void visitSMinExpr(const SCEVSMinExpr *Numerator) {}
57 void visitUMinExpr(const SCEVUMinExpr *Numerator) {}
58 void visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Numerator) {}
59 void visitUnknown(const SCEVUnknown *Numerator) {}
60 void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {}
61
62 LLVM_ABI void visitConstant(const SCEVConstant *Numerator);
63
64 LLVM_ABI void visitVScale(const SCEVVScale *Numerator);
65
66 LLVM_ABI void visitAddRecExpr(const SCEVAddRecExpr *Numerator);
67
68 LLVM_ABI void visitAddExpr(const SCEVAddExpr *Numerator);
69
70 LLVM_ABI void visitMulExpr(const SCEVMulExpr *Numerator);
71
72private:
73 SCEVDivision(ScalarEvolution &S, const SCEV *Numerator,
74 const SCEV *Denominator);
75
76 // Convenience function for giving up on the division. We set the quotient to
77 // be equal to zero and the remainder to be equal to the numerator.
78 void cannotDivide(const SCEV *Numerator);
79
80 ScalarEvolution &SE;
81 const SCEV *Denominator, *Quotient, *Remainder, *Zero, *One;
82};
83
84class SCEVDivisionPrinterPass
85 : public RequiredPassInfoMixin<SCEVDivisionPrinterPass> {
86 raw_ostream &OS;
87 void runImpl(Function &F, ScalarEvolution &SE);
88
89public:
90 explicit SCEVDivisionPrinterPass(raw_ostream &OS) : OS(OS) {}
91 LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
92};
93
94} // end namespace llvm
95
96#endif // LLVM_ANALYSIS_SCALAREVOLUTIONDIVISION_H
97