1//===- IntegerDivisibilityAnalysis.cpp - Integer divisibility ---*- 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 dataflow analysis class for integer divisibility
10// inference. Operations participate in the analysis by implementing
11// `InferIntDivisibilityOpInterface`.
12//
13//===----------------------------------------------------------------------===//
14
15#include "mlir/Analysis/DataFlow/IntegerDivisibilityAnalysis.h"
16
17#include "mlir/Dialect/Utils/StaticValueUtils.h"
18#include "mlir/Interfaces/LoopLikeInterface.h"
19#include "llvm/Support/Debug.h"
20
21#define DEBUG_TYPE "int-divisibility-analysis"
22
23using llvm::dbgs;
24
25namespace mlir::dataflow {
26
27void IntegerDivisibilityAnalysis::setToEntryState(
28 IntegerDivisibilityLattice *lattice) {
29 propagateIfChanged(state: lattice,
30 changed: lattice->join(rhs: IntegerDivisibility::getMinDivisibility()));
31}
32
33LogicalResult IntegerDivisibilityAnalysis::visitOperation(
34 Operation *op, ArrayRef<const IntegerDivisibilityLattice *> operands,
35 ArrayRef<IntegerDivisibilityLattice *> results) {
36 auto inferrable = dyn_cast<InferIntDivisibilityOpInterface>(Val: op);
37 if (!inferrable) {
38 setAllToEntryStates(results);
39 return success();
40 }
41
42 LLVM_DEBUG(dbgs() << "Inferring divisibility for " << *op << "\n");
43 auto argDivs = llvm::map_to_vector(
44 C&: operands, F: [](const IntegerDivisibilityLattice *lattice) {
45 return lattice->getValue();
46 });
47 auto joinCallback = [&](Value v, const IntegerDivisibility &newDiv) {
48 auto result = dyn_cast<OpResult>(Val&: v);
49 if (!result) {
50 return;
51 }
52 assert(llvm::is_contained(op->getResults(), result));
53
54 LLVM_DEBUG(dbgs() << "Inferred divisibility " << newDiv << "\n");
55 IntegerDivisibilityLattice *lattice = results[result.getResultNumber()];
56 IntegerDivisibility oldDiv = lattice->getValue();
57
58 ChangeResult changed = lattice->join(rhs: newDiv);
59
60 // Catch loop results with loop-variant divisibility and conservatively
61 // set them to divisibility 1 (no information) so we don't ratchet
62 // indefinitely (the dataflow analysis in MLIR doesn't attempt to work
63 // out trip counts and often can't).
64 bool isYieldedResult = llvm::any_of(Range: v.getUsers(), P: [](Operation *op) {
65 return op->hasTrait<OpTrait::IsTerminator>();
66 });
67 if (isYieldedResult && !oldDiv.isUninitialized() &&
68 !(lattice->getValue() == oldDiv)) {
69 LLVM_DEBUG(llvm::dbgs() << "Loop variant loop result detected\n");
70 changed |= lattice->join(rhs: IntegerDivisibility::getMinDivisibility());
71 }
72 propagateIfChanged(state: lattice, changed);
73 };
74
75 inferrable.inferResultDivisibility(argDivs, setResultDivs: joinCallback);
76 return success();
77}
78
79void IntegerDivisibilityAnalysis::visitNonControlFlowArguments(
80 Operation *op, const RegionSuccessor &successor, ValueRange successorInputs,
81 ArrayRef<IntegerDivisibilityLattice *> argLattices,
82 GetLatticeFn getLattice) {
83 // Get the constant divisibility, or query the lattice for Values.
84 auto getDivFromOfr = [&](std::optional<OpFoldResult> ofr,
85 bool isUnsigned) -> uint64_t {
86 if (ofr.has_value()) {
87 if (auto constBound = getConstantIntValue(ofr: *ofr)) {
88 return constBound.value();
89 }
90 auto value = cast<Value>(Val&: ofr.value());
91 const IntegerDivisibilityLattice *lattice = getLattice(value);
92 if (lattice != nullptr && !lattice->getValue().isUninitialized()) {
93 return isUnsigned ? lattice->getValue().getValue().udiv()
94 : lattice->getValue().getValue().sdiv();
95 }
96 }
97 return isUnsigned
98 ? IntegerDivisibility::getMinDivisibility().getValue().udiv()
99 : IntegerDivisibility::getMinDivisibility().getValue().sdiv();
100 };
101
102 // Infer bounds for loop arguments that have static bounds
103 if (auto loop = dyn_cast<LoopLikeOpInterface>(Val: op)) {
104 std::optional<SmallVector<Value>> ivs = loop.getLoopInductionVars();
105 std::optional<SmallVector<OpFoldResult>> lbs = loop.getLoopLowerBounds();
106 std::optional<SmallVector<OpFoldResult>> steps = loop.getLoopSteps();
107 if (!ivs || !lbs || !steps) {
108 return SparseForwardDataFlowAnalysis::visitNonControlFlowArguments(
109 op, successor, nonSuccessorInputs: successorInputs, nonSuccessorInputLattices: argLattices, getLattice);
110 }
111 for (auto [iv, lb, step] : llvm::zip_equal(t&: *ivs, u&: *lbs, args&: *steps)) {
112 IntegerDivisibilityLattice *ivEntry = getLatticeElement(value: iv);
113 uint64_t stepUDiv = getDivFromOfr(step, /*unsigned=*/true);
114 uint64_t stepSDiv = getDivFromOfr(step, /*unsigned=*/false);
115 uint64_t lbUDiv = getDivFromOfr(lb, /*unsigned=*/true);
116 uint64_t lbSDiv = getDivFromOfr(lb, /*unsigned=*/false);
117 ConstantIntDivisibility lbDiv(lbUDiv, lbSDiv);
118 ConstantIntDivisibility stepDiv(stepUDiv, stepSDiv);
119
120 // Loop induction variables are computed as `lb + i * step`. The
121 // divisibility for `i * step` is just the divisibility of `step`, so
122 // the total divisibility is obtained by unioning the step divisibility
123 // with the lower bound divisibility, which takes the GCD of the two.
124 ConstantIntDivisibility ivDiv = stepDiv.getUnion(other: lbDiv);
125 propagateIfChanged(state: ivEntry, changed: ivEntry->join(rhs: ivDiv));
126 }
127 return;
128 }
129
130 return SparseForwardDataFlowAnalysis::visitNonControlFlowArguments(
131 op, successor, nonSuccessorInputs: successorInputs, nonSuccessorInputLattices: argLattices, getLattice);
132}
133} // namespace mlir::dataflow
134