[SCEVDivision] Add SCEVDivisionPrinterPass with corresponding tests #155832
+240
−2
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
@llvm/pr-subscribers-llvm-analysis @llvm/pr-subscribers-testing-tools Author: Ryotaro Kasuga (kasuga-fj) ChangesThis patch introduces Related discussion: #154745 Full diff: https://github.com/llvm/llvm-project/pull/155832.diff 6 Files Affected:
diff --git a/llvm/include/llvm/Analysis/ScalarEvolutionDivision.h b/llvm/include/llvm/Analysis/ScalarEvolutionDivision.h
index 3283d438ccb51..cf6db50fddbe3 100644
--- a/llvm/include/llvm/Analysis/ScalarEvolutionDivision.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolutionDivision.h
@@ -68,6 +68,15 @@ struct SCEVDivision : public SCEVVisitor<SCEVDivision, void> {
const SCEV *Denominator, *Quotient, *Remainder, *Zero, *One;
};
+class SCEVDivisionPrinterPass : public PassInfoMixin<SCEVDivisionPrinterPass> {
+ raw_ostream &OS;
+ void runImpl(Function &F, ScalarEvolution &SE);
+
+public:
+ explicit SCEVDivisionPrinterPass(raw_ostream &OS) : OS(OS) {}
+ PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
} // end namespace llvm
#endif // LLVM_ANALYSIS_SCALAREVOLUTIONDIVISION_H
diff --git a/llvm/lib/Analysis/ScalarEvolutionDivision.cpp b/llvm/lib/Analysis/ScalarEvolutionDivision.cpp
index d03930d9e2d99..bce41f9f5329e 100644
--- a/llvm/lib/Analysis/ScalarEvolutionDivision.cpp
+++ b/llvm/lib/Analysis/ScalarEvolutionDivision.cpp
@@ -15,10 +15,14 @@
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
#include "llvm/Support/Casting.h"
#include <cassert>
#include <cstdint>
+#define DEBUG_TYPE "scev-division"
+
namespace llvm {
class Type;
} // namespace llvm
@@ -257,3 +261,31 @@ void SCEVDivision::cannotDivide(const SCEV *Numerator) {
Quotient = Zero;
Remainder = Numerator;
}
+
+void SCEVDivisionPrinterPass::runImpl(Function &F, ScalarEvolution &SE) {
+ OS << "Printing analysis 'Scalar Evolution Division' for function '"
+ << F.getName() << "':\n";
+ for (Instruction &Inst : instructions(F)) {
+ BinaryOperator *Div = dyn_cast<BinaryOperator>(&Inst);
+ if (!Div || Div->getOpcode() != Instruction::SDiv)
+ continue;
+
+ const SCEV *Numerator = SE.getSCEV(Div->getOperand(0));
+ const SCEV *Denominator = SE.getSCEV(Div->getOperand(1));
+ const SCEV *Quotient, *Remainder;
+ SCEVDivision::divide(SE, Numerator, Denominator, &Quotient, &Remainder);
+
+ OS << "Instruction: " << *Div << "\n";
+ OS.indent(2) << "Numerator: " << *Numerator << "\n";
+ OS.indent(2) << "Denominator: " << *Denominator << "\n";
+ OS.indent(2) << "Quotient: " << *Quotient << "\n";
+ OS.indent(2) << "Remainder: " << *Remainder << "\n";
+ }
+}
+
+PreservedAnalyses SCEVDivisionPrinterPass::run(Function &F,
+ FunctionAnalysisManager &AM) {
+ ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
+ runImpl(F, SE);
+ return PreservedAnalyses::all();
+}
diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index b7edeea082762..d75304b5e11f6 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -69,6 +69,7 @@
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
+#include "llvm/Analysis/ScalarEvolutionDivision.h"
#include "llvm/Analysis/ScopedNoAliasAA.h"
#include "llvm/Analysis/StackLifetime.h"
#include "llvm/Analysis/StackSafetyAnalysis.h"
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
index 1b111dc20d35c..4b462b9c6845c 100644
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -518,6 +518,7 @@ FUNCTION_PASS("print<phi-values>", PhiValuesPrinterPass(errs()))
FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(errs()))
FUNCTION_PASS("print<regions>", RegionInfoPrinterPass(errs()))
FUNCTION_PASS("print<scalar-evolution>", ScalarEvolutionPrinterPass(errs()))
+FUNCTION_PASS("print<scev-division>", SCEVDivisionPrinterPass(errs()))
FUNCTION_PASS("print<stack-safety-local>", StackSafetyPrinterPass(errs()))
FUNCTION_PASS("print<uniformity>", UniformityInfoPrinterPass(errs()))
FUNCTION_PASS("prof-inject", ProfileInjectorPass())
diff --git a/llvm/test/Analysis/ScalarEvolutionDivision/sdiv.ll b/llvm/test/Analysis/ScalarEvolutionDivision/sdiv.ll
new file mode 100644
index 0000000000000..02db29eee6a85
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolutionDivision/sdiv.ll
@@ -0,0 +1,210 @@
+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s "-passes=print<scev-division>" -disable-output 2>&1 | FileCheck %s
+
+define i8 @add(i8 %x, i8 %y) {
+; CHECK-LABEL: 'add'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %add, %y
+; CHECK-NEXT: Numerator: (%x + %y)
+; CHECK-NEXT: Denominator: %y
+; CHECK-NEXT: Quotient: 1
+; CHECK-NEXT: Remainder: %x
+;
+ %add = add i8 %x, %y
+ %div = sdiv i8 %add, %y
+ ret i8 %div
+}
+
+define i8 @mul_add_mul(i8 %a, i8 %b, i8 %c) {
+; CHECK-LABEL: 'mul_add_mul'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %add, %a
+; CHECK-NEXT: Numerator: ((2 * %c) + (%a * %b))
+; CHECK-NEXT: Denominator: %a
+; CHECK-NEXT: Quotient: %b
+; CHECK-NEXT: Remainder: (2 * %c)
+;
+ %mul0 = mul nsw nuw i8 %a, %b
+ %tmp = add nsw nuw i8 %mul0, %c
+ %mul1 = mul nsw nuw i8 %a, %c
+ %add = add nsw nuw i8 %tmp, %c
+ %div = sdiv i8 %add, %a
+ ret i8 %div
+}
+
+; FIXME: We need nsw on mul.
+define i8 @mul(i8 %x, i8 %y) {
+; CHECK-LABEL: 'mul'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %mul, %y
+; CHECK-NEXT: Numerator: (%x * %y)
+; CHECK-NEXT: Denominator: %y
+; CHECK-NEXT: Quotient: %x
+; CHECK-NEXT: Remainder: 0
+;
+ %mul = mul i8 %x, %y
+ %div = sdiv i8 %mul, %y
+ ret i8 %div
+}
+
+define i8 @mul_nsw(i8 %x, i8 %y) {
+; CHECK-LABEL: 'mul_nsw'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %mul, %y
+; CHECK-NEXT: Numerator: (%x * %y)
+; CHECK-NEXT: Denominator: %y
+; CHECK-NEXT: Quotient: %x
+; CHECK-NEXT: Remainder: 0
+;
+ %mul = mul nsw i8 %x, %y
+ %div = sdiv i8 %mul, %y
+ ret i8 %div
+}
+
+; FIXME: We need nsw on mul.
+define i8 @mul_nuw(i8 %x, i8 %y) {
+; CHECK-LABEL: 'mul_nuw'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %mul, %y
+; CHECK-NEXT: Numerator: (%x * %y)
+; CHECK-NEXT: Denominator: %y
+; CHECK-NEXT: Quotient: %x
+; CHECK-NEXT: Remainder: 0
+;
+ %mul = mul nuw i8 %x, %y
+ %div = sdiv i8 %mul, %y
+ ret i8 %div
+}
+
+define i8 @add_mul_add(i8 %a, i8 %b, i8 %c) {
+; CHECK-LABEL: 'add_mul_add'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %mul, %a
+; CHECK-NEXT: Numerator: ((%a + %b) * (%a + %c))
+; CHECK-NEXT: Denominator: %a
+; CHECK-NEXT: Quotient: 0
+; CHECK-NEXT: Remainder: ((%a + %b) * (%a + %c))
+;
+ %add0 = add nsw nuw i8 %a, %b
+ %add1 = add nsw nuw i8 %a, %c
+ %mul = mul nsw nuw i8 %add0, %add1
+ %div = sdiv i8 %mul, %a
+ ret i8 %div
+}
+
+; for (i = 0; i < n; i++)
+; div = i / den;
+;
+define void @addrec_iv(i8 %n, i8 %den) {
+; CHECK-LABEL: 'addrec_iv'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %i, %den
+; CHECK-NEXT: Numerator: {0,+,1}<nuw><nsw><%loop>
+; CHECK-NEXT: Denominator: %den
+; CHECK-NEXT: Quotient: 0
+; CHECK-NEXT: Remainder: {0,+,1}<nuw><nsw><%loop>
+;
+entry:
+ %guard = icmp sgt i8 %n, 0
+ br i1 %guard, label %loop, label %exit
+
+loop:
+ %i = phi i8 [ 0, %entry ], [ %i.inc, %loop ]
+ %div = sdiv i8 %i, %den
+ %i.inc = add nsw i8 %i, 1
+ %exitcond = icmp eq i8 %i.inc, %n
+ br i1 %exitcond, label %exit, label %loop
+
+exit:
+ ret void
+}
+
+; for (i = 0; i < n; i++)
+; div = (step * i) / step;
+;
+define void @addrec_step0(i8 %n, i8 %step) {
+; CHECK-LABEL: 'addrec_step0'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %num, %step
+; CHECK-NEXT: Numerator: {0,+,%step}<nuw><nsw><%loop>
+; CHECK-NEXT: Denominator: %step
+; CHECK-NEXT: Quotient: {0,+,1}<nuw><nsw><%loop>
+; CHECK-NEXT: Remainder: 0
+;
+entry:
+ %guard = icmp sgt i8 %n, 0
+ br i1 %guard, label %loop, label %exit
+
+loop:
+ %i = phi i8 [ 0, %entry ], [ %i.inc, %loop ]
+ %num = phi i8 [ 0, %entry ], [ %num.next, %loop ]
+ %div = sdiv i8 %num, %step
+ %i.inc = add nsw i8 %i, 1
+ %num.next = add nsw nuw i8 %num, %step
+ %exitcond = icmp eq i8 %i.inc, %n
+ br i1 %exitcond, label %exit, label %loop
+
+exit:
+ ret void
+}
+
+; for (unsigned char i = 0; i < n; i++)
+; if (cond)
+; div = (step * i) / step;
+;
+; FIXME: The quotient can cause signed wrap, e.g., when %step is 0 and %n is
+; larger than 127.
+define void @addrec_step1(i8 %n, i8 %step) {
+; CHECK-LABEL: 'addrec_step1'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %num, %step
+; CHECK-NEXT: Numerator: {0,+,%step}<nuw><nsw><%loop.header>
+; CHECK-NEXT: Denominator: %step
+; CHECK-NEXT: Quotient: {0,+,1}<nuw><nsw><%loop.header>
+; CHECK-NEXT: Remainder: 0
+;
+entry:
+ %guard = icmp ne i8 %n, 0
+ br i1 %guard, label %loop.header, label %exit
+
+loop.header:
+ %i = phi i8 [ 0, %entry ], [ %i.inc, %loop.latch ]
+ %num = phi i8 [ 0, %entry ], [ %num.next, %loop.latch ]
+ %cond = freeze i1 poison
+ br i1 %cond, label %division, label %loop.latch
+
+division:
+ %div = sdiv i8 %num, %step
+ br label %loop.latch
+
+loop.latch:
+ %i.inc = add nuw i8 %i, 1
+ %num.next = add nsw nuw i8 %num, %step
+ %exitcond = icmp eq i8 %i.inc, %n
+ br i1 %exitcond, label %exit, label %loop.header
+
+exit:
+ ret void
+}
+
+; for (i = 0; i < n; i++)
+; div = (a + b) * i / a;
+;
+; FIXME: Both the quotient and the remainder can cause signed/unsigned wrap,
+; e.g., when %a + %b = 0 && %a != 0.
+define void @addrec_a_b(i8 %n, i8 %a, i8 %b) {
+; CHECK-LABEL: 'addrec_a_b'
+; CHECK-NEXT: Instruction: %div = sdiv i8 %num, %step
+; CHECK-NEXT: Numerator: {0,+,(%a + %b)}<nuw><nsw><%loop>
+; CHECK-NEXT: Denominator: (%a + %b)
+; CHECK-NEXT: Quotient: {0,+,1}<nuw><nsw><%loop>
+; CHECK-NEXT: Remainder: 0
+;
+entry:
+ %guard = icmp sgt i8 %n, 0
+ %step = add nsw nuw i8 %a, %b
+ br i1 %guard, label %loop, label %exit
+
+loop:
+ %i = phi i8 [ 0, %entry ], [ %i.inc, %loop ]
+ %num = phi i8 [ 0, %entry ], [ %num.next, %loop ]
+ %div = sdiv i8 %num, %step
+ %i.inc = add nsw i8 %i, 1
+ %num.next = add nsw nuw i8 %num, %step
+ %exitcond = icmp eq i8 %i.inc, %n
+ br i1 %exitcond, label %exit, label %loop
+
+exit:
+ ret void
+}
diff --git a/llvm/utils/UpdateTestChecks/common.py b/llvm/utils/UpdateTestChecks/common.py
index 835092c468695..a1f188fbf8d69 100644
--- a/llvm/utils/UpdateTestChecks/common.py
+++ b/llvm/utils/UpdateTestChecks/common.py
@@ -39,6 +39,7 @@
"Delinearization",
"Loop Access Analysis",
"Scalar Evolution Analysis",
+ "Scalar Evolution Division",
}
|
kasuga-fj
commented
Aug 28, 2025
There was a problem hiding this comment.
While writing tests, I felt that we should first clarify the behavior of SCEVDivision::divide. Maybe something like the following?
- Given the
NumeratorandDenominator, find a pair(Quotient, Remainder)such thatNumerator = Quotient * Denominator + Remainder- The multiplication of
QuotientandDenominatordoes not wrap in a signed sense - The addition of
Quotient*DenominatorandRemainderdoes not wrap in a signed sense
- The condition
Remainder < Denominatoris not necessarily required - Multiple pairs
(Quotient, Remainder)may satisfy the above conditions, and this function returns one of them- Especially,
(Quotient, Remainder) = (0, Numerator)is a trivial one
- Especially,
There was a problem hiding this comment.
I've listed some cases with suspicious behavior that came to mind for now.
nikic
reviewed
Aug 28, 2025
| ; CHECK-NEXT: Numerator: (%x * %y) | ||
| ; CHECK-NEXT: Denominator: %y | ||
| ; CHECK-NEXT: Quotient: %x | ||
| ; CHECK-NEXT: Remainder: 0 |
There was a problem hiding this comment.
Here we have %x * %y == %x * %y + 0, so this is actually also correct.
There was a problem hiding this comment.
Removed FIXME comments
It looks like the current implementation only follows the first point, but not the other two (no signed wrap). As long as Delinearization doesn't actually require these to not wrap, this behavior would be fine to keep... |
kasuga-fj
commented
Aug 28, 2025
| ; CHECK-NEXT: Numerator: (%x * %y) | ||
| ; CHECK-NEXT: Denominator: %y | ||
| ; CHECK-NEXT: Quotient: %x | ||
| ; CHECK-NEXT: Remainder: 0 |
There was a problem hiding this comment.
Removed FIXME comments
Comment on lines
+28
to
+40
| /// Computes the Quotient and Remainder of the division of Numerator by | ||
| /// Denominator. We are not actually performing the division here. Instead, we | ||
| /// are trying to find SCEV expressions Quotient and Remainder that satisfy: | ||
| /// | ||
| /// Numerator = Denominator * Quotient + Remainder | ||
| /// | ||
| /// There may be multiple valid answers for Quotient and Remainder. This | ||
| /// function finds one of them. Especially, there is always a trivial | ||
| /// solution: (Quotient, Remainder) = (0, Numerator). | ||
| /// | ||
| /// Note the following: | ||
| /// * The condition Remainder < Denominator is NOT necessarily required. | ||
| /// * Division of constants is performed as signed. |
In my current understanding, we should perform the latter two (or a similar) checks somewhere, but not necessarily here. And I’m not sure what the best place for it would be. For now, it seems reasonable to keep the existing behavior. (And the current issue is that such checks are not performed at all, so DA may produce incorrect results.) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This patch introduces
SCEVDivisionPrinterPassand registers it under the nameprint<scev-division>, primarily for testing purposes. This pass invokesSCEVDivision::divideupon encounteringsdiv, and prints the numerator, denominator, quotient, and remainder. It also adds several test cases, some of which are currently incorrect and require fixing.Along with that, this patch added some comments to clarify the behavior of
SCEVDivision::divide, as follows:NumeratorandDenominator, find a pair(Quotient, Remainder)s.t.Numerator = Quotient * Denominator + RemainderRemainder < Denominatoris NOT necessarily required(Quotient, Remainder), and this function finds one of them(0, Numerator)QuotientandDenominatorQuotient * DenominatorandRemainderRelated discussion: #154745