1//===- IndexToLLVM.cpp - Index to LLVM dialect conversion -------*- 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#include "mlir/Conversion/IndexToLLVM/IndexToLLVM.h"
10
11#include "mlir/Analysis/DataLayoutAnalysis.h"
12#include "mlir/Conversion/ConvertToLLVM/ToLLVMInterface.h"
13#include "mlir/Conversion/LLVMCommon/Pattern.h"
14#include "mlir/Dialect/Index/IR/IndexAttrs.h"
15#include "mlir/Dialect/Index/IR/IndexDialect.h"
16#include "mlir/Dialect/Index/IR/IndexOps.h"
17#include "mlir/Dialect/LLVMIR/LLVMArithOps.h"
18#include "mlir/Dialect/LLVMIR/LLVMConstantOps.h"
19#include "mlir/Dialect/LLVMIR/LLVMConversionOps.h"
20#include "mlir/Dialect/LLVMIR/LLVMIntegerIntrinsicOps.h"
21#include "mlir/Pass/Pass.h"
22
23using namespace mlir;
24using namespace index;
25
26namespace {
27
28//===----------------------------------------------------------------------===//
29// ConvertIndexCeilDivS
30//===----------------------------------------------------------------------===//
31
32/// Convert `ceildivs(n, m)` into `x = m > 0 ? -1 : 1` and then
33/// `n*m > 0 ? (n+x)/m + 1 : -(-n/m)`.
34struct ConvertIndexCeilDivS : mlir::ConvertOpToLLVMPattern<CeilDivSOp> {
35 using ConvertOpToLLVMPattern::ConvertOpToLLVMPattern;
36
37 LogicalResult
38 matchAndRewrite(CeilDivSOp op, CeilDivSOpAdaptor adaptor,
39 ConversionPatternRewriter &rewriter) const override {
40 Location loc = op.getLoc();
41 Value n = adaptor.getLhs();
42 Value m = adaptor.getRhs();
43 Value zero = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: n.getType(), value: 0);
44 Value posOne = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: n.getType(), value: 1);
45 Value negOne = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: n.getType(), value: -1);
46
47 // Compute `x`.
48 Value mPos =
49 LLVM::ICmpOp::create(builder&: rewriter, location: loc, predicate: LLVM::ICmpPredicate::sgt, lhs: m, rhs: zero);
50 Value x = LLVM::SelectOp::create(builder&: rewriter, location: loc, condition: mPos, trueValue: negOne, falseValue: posOne);
51
52 // Compute the positive result.
53 Value nPlusX = LLVM::AddOp::create(builder&: rewriter, location: loc, lhs: n, rhs: x);
54 Value nPlusXDivM = LLVM::SDivOp::create(builder&: rewriter, location: loc, lhs: nPlusX, rhs: m);
55 Value posRes = LLVM::AddOp::create(builder&: rewriter, location: loc, lhs: nPlusXDivM, rhs: posOne);
56
57 // Compute the negative result.
58 Value negN = LLVM::SubOp::create(builder&: rewriter, location: loc, lhs: zero, rhs: n);
59 Value negNDivM = LLVM::SDivOp::create(builder&: rewriter, location: loc, lhs: negN, rhs: m);
60 Value negRes = LLVM::SubOp::create(builder&: rewriter, location: loc, lhs: zero, rhs: negNDivM);
61
62 // Pick the positive result if `n` and `m` have the same sign and `n` is
63 // non-zero, i.e. `(n > 0) == (m > 0) && n != 0`.
64 Value nPos =
65 LLVM::ICmpOp::create(builder&: rewriter, location: loc, predicate: LLVM::ICmpPredicate::sgt, lhs: n, rhs: zero);
66 Value sameSign = LLVM::ICmpOp::create(builder&: rewriter, location: loc,
67 predicate: LLVM::ICmpPredicate::eq, lhs: nPos, rhs: mPos);
68 Value nNonZero =
69 LLVM::ICmpOp::create(builder&: rewriter, location: loc, predicate: LLVM::ICmpPredicate::ne, lhs: n, rhs: zero);
70 Value cmp = LLVM::AndOp::create(builder&: rewriter, location: loc, lhs: sameSign, rhs: nNonZero);
71 rewriter.replaceOpWithNewOp<LLVM::SelectOp>(op, args&: cmp, args&: posRes, args&: negRes);
72 return success();
73 }
74};
75
76//===----------------------------------------------------------------------===//
77// ConvertIndexCeilDivU
78//===----------------------------------------------------------------------===//
79
80/// Convert `ceildivu(n, m)` into `n == 0 ? 0 : (n-1)/m + 1`.
81struct ConvertIndexCeilDivU : mlir::ConvertOpToLLVMPattern<CeilDivUOp> {
82 using ConvertOpToLLVMPattern::ConvertOpToLLVMPattern;
83
84 LogicalResult
85 matchAndRewrite(CeilDivUOp op, CeilDivUOpAdaptor adaptor,
86 ConversionPatternRewriter &rewriter) const override {
87 Location loc = op.getLoc();
88 Value n = adaptor.getLhs();
89 Value m = adaptor.getRhs();
90 Value zero = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: n.getType(), value: 0);
91 Value one = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: n.getType(), value: 1);
92
93 // Compute the non-zero result.
94 Value minusOne = LLVM::SubOp::create(builder&: rewriter, location: loc, lhs: n, rhs: one);
95 Value quotient = LLVM::UDivOp::create(builder&: rewriter, location: loc, lhs: minusOne, rhs: m);
96 Value plusOne = LLVM::AddOp::create(builder&: rewriter, location: loc, lhs: quotient, rhs: one);
97
98 // Pick the result.
99 Value cmp =
100 LLVM::ICmpOp::create(builder&: rewriter, location: loc, predicate: LLVM::ICmpPredicate::eq, lhs: n, rhs: zero);
101 rewriter.replaceOpWithNewOp<LLVM::SelectOp>(op, args&: cmp, args&: zero, args&: plusOne);
102 return success();
103 }
104};
105
106//===----------------------------------------------------------------------===//
107// ConvertIndexFloorDivS
108//===----------------------------------------------------------------------===//
109
110/// Convert `floordivs(n, m)` into `x = m < 0 ? 1 : -1` and then
111/// `n*m < 0 ? -1 - (x-n)/m : n/m`.
112struct ConvertIndexFloorDivS : mlir::ConvertOpToLLVMPattern<FloorDivSOp> {
113 using ConvertOpToLLVMPattern::ConvertOpToLLVMPattern;
114
115 LogicalResult
116 matchAndRewrite(FloorDivSOp op, FloorDivSOpAdaptor adaptor,
117 ConversionPatternRewriter &rewriter) const override {
118 Location loc = op.getLoc();
119 Value n = adaptor.getLhs();
120 Value m = adaptor.getRhs();
121 Value zero = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: n.getType(), value: 0);
122 Value posOne = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: n.getType(), value: 1);
123 Value negOne = LLVM::ConstantOp::create(builder&: rewriter, location: loc, type: n.getType(), value: -1);
124
125 // Compute `x`.
126 Value mNeg =
127 LLVM::ICmpOp::create(builder&: rewriter, location: loc, predicate: LLVM::ICmpPredicate::slt, lhs: m, rhs: zero);
128 Value x = LLVM::SelectOp::create(builder&: rewriter, location: loc, condition: mNeg, trueValue: posOne, falseValue: negOne);
129
130 // Compute the negative result.
131 Value xMinusN = LLVM::SubOp::create(builder&: rewriter, location: loc, lhs: x, rhs: n);
132 Value xMinusNDivM = LLVM::SDivOp::create(builder&: rewriter, location: loc, lhs: xMinusN, rhs: m);
133 Value negRes = LLVM::SubOp::create(builder&: rewriter, location: loc, lhs: negOne, rhs: xMinusNDivM);
134
135 // Compute the positive result.
136 Value posRes = LLVM::SDivOp::create(builder&: rewriter, location: loc, lhs: n, rhs: m);
137
138 // Pick the negative result if `n` and `m` have different signs and `n` is
139 // non-zero, i.e. `(n < 0) != (m < 0) && n != 0`.
140 Value nNeg =
141 LLVM::ICmpOp::create(builder&: rewriter, location: loc, predicate: LLVM::ICmpPredicate::slt, lhs: n, rhs: zero);
142 Value diffSign = LLVM::ICmpOp::create(builder&: rewriter, location: loc,
143 predicate: LLVM::ICmpPredicate::ne, lhs: nNeg, rhs: mNeg);
144 Value nNonZero =
145 LLVM::ICmpOp::create(builder&: rewriter, location: loc, predicate: LLVM::ICmpPredicate::ne, lhs: n, rhs: zero);
146 Value cmp = LLVM::AndOp::create(builder&: rewriter, location: loc, lhs: diffSign, rhs: nNonZero);
147 rewriter.replaceOpWithNewOp<LLVM::SelectOp>(op, args&: cmp, args&: negRes, args&: posRes);
148 return success();
149 }
150};
151
152//===----------------------------------------------------------------------===//
153// CovnertIndexCast
154//===----------------------------------------------------------------------===//
155
156/// Convert a cast op. If the materialized index type is the same as the other
157/// type, fold away the op. Otherwise, truncate or extend the op as appropriate.
158/// Signed casts sign extend when the result bitwidth is larger. Unsigned casts
159/// zero extend when the result bitwidth is larger.
160template <typename CastOp, typename ExtOp>
161struct ConvertIndexCast : public mlir::ConvertOpToLLVMPattern<CastOp> {
162 using mlir::ConvertOpToLLVMPattern<CastOp>::ConvertOpToLLVMPattern;
163
164 LogicalResult
165 matchAndRewrite(CastOp op, typename CastOp::Adaptor adaptor,
166 ConversionPatternRewriter &rewriter) const override {
167 Type in = adaptor.getInput().getType();
168 Type out = this->getTypeConverter()->convertType(op.getType());
169 if (in == out)
170 rewriter.replaceOp(op, adaptor.getInput());
171 else if (in.getIntOrFloatBitWidth() > out.getIntOrFloatBitWidth())
172 rewriter.replaceOpWithNewOp<LLVM::TruncOp>(op, out, adaptor.getInput());
173 else
174 rewriter.replaceOpWithNewOp<ExtOp>(op, out, adaptor.getInput());
175 return success();
176 }
177};
178
179using ConvertIndexCastS = ConvertIndexCast<CastSOp, LLVM::SExtOp>;
180using ConvertIndexCastU = ConvertIndexCast<CastUOp, LLVM::ZExtOp>;
181
182//===----------------------------------------------------------------------===//
183// ConvertIndexCmp
184//===----------------------------------------------------------------------===//
185
186/// Assert that the LLVM comparison enum lines up with index's enum.
187static constexpr bool checkPredicates(LLVM::ICmpPredicate lhs,
188 IndexCmpPredicate rhs) {
189 return static_cast<int>(lhs) == static_cast<int>(rhs);
190}
191
192static_assert(
193 LLVM::getMaxEnumValForICmpPredicate() ==
194 getMaxEnumValForIndexCmpPredicate() &&
195 checkPredicates(lhs: LLVM::ICmpPredicate::eq, rhs: IndexCmpPredicate::EQ) &&
196 checkPredicates(lhs: LLVM::ICmpPredicate::ne, rhs: IndexCmpPredicate::NE) &&
197 checkPredicates(lhs: LLVM::ICmpPredicate::sge, rhs: IndexCmpPredicate::SGE) &&
198 checkPredicates(lhs: LLVM::ICmpPredicate::sgt, rhs: IndexCmpPredicate::SGT) &&
199 checkPredicates(lhs: LLVM::ICmpPredicate::sle, rhs: IndexCmpPredicate::SLE) &&
200 checkPredicates(lhs: LLVM::ICmpPredicate::slt, rhs: IndexCmpPredicate::SLT) &&
201 checkPredicates(lhs: LLVM::ICmpPredicate::uge, rhs: IndexCmpPredicate::UGE) &&
202 checkPredicates(lhs: LLVM::ICmpPredicate::ugt, rhs: IndexCmpPredicate::UGT) &&
203 checkPredicates(lhs: LLVM::ICmpPredicate::ule, rhs: IndexCmpPredicate::ULE) &&
204 checkPredicates(lhs: LLVM::ICmpPredicate::ult, rhs: IndexCmpPredicate::ULT),
205 "LLVM ICmpPredicate mismatches IndexCmpPredicate");
206
207struct ConvertIndexCmp : public mlir::ConvertOpToLLVMPattern<CmpOp> {
208 using ConvertOpToLLVMPattern::ConvertOpToLLVMPattern;
209
210 LogicalResult
211 matchAndRewrite(CmpOp op, CmpOpAdaptor adaptor,
212 ConversionPatternRewriter &rewriter) const override {
213 // The LLVM enum has the same values as the index predicate enums.
214 rewriter.replaceOpWithNewOp<LLVM::ICmpOp>(
215 op, args: *LLVM::symbolizeICmpPredicate(static_cast<uint32_t>(op.getPred())),
216 args: adaptor.getLhs(), args: adaptor.getRhs());
217 return success();
218 }
219};
220
221//===----------------------------------------------------------------------===//
222// ConvertIndexSizeOf
223//===----------------------------------------------------------------------===//
224
225/// Lower `index.sizeof` to a constant with the value of the index bitwidth.
226struct ConvertIndexSizeOf : public mlir::ConvertOpToLLVMPattern<SizeOfOp> {
227 using ConvertOpToLLVMPattern::ConvertOpToLLVMPattern;
228
229 LogicalResult
230 matchAndRewrite(SizeOfOp op, SizeOfOpAdaptor adaptor,
231 ConversionPatternRewriter &rewriter) const override {
232 rewriter.replaceOpWithNewOp<LLVM::ConstantOp>(
233 op, args: getTypeConverter()->getIndexType(),
234 args: getTypeConverter()->getIndexTypeBitwidth());
235 return success();
236 }
237};
238
239//===----------------------------------------------------------------------===//
240// ConvertIndexConstant
241//===----------------------------------------------------------------------===//
242
243/// Convert an index constant. Truncate the value as appropriate.
244struct ConvertIndexConstant : public mlir::ConvertOpToLLVMPattern<ConstantOp> {
245 using ConvertOpToLLVMPattern::ConvertOpToLLVMPattern;
246
247 LogicalResult
248 matchAndRewrite(ConstantOp op, ConstantOpAdaptor adaptor,
249 ConversionPatternRewriter &rewriter) const override {
250 Type type = getTypeConverter()->getIndexType();
251 APInt value = op.getValue().trunc(width: type.getIntOrFloatBitWidth());
252 rewriter.replaceOpWithNewOp<LLVM::ConstantOp>(
253 op, args&: type, args: IntegerAttr::get(type, value));
254 return success();
255 }
256};
257
258//===----------------------------------------------------------------------===//
259// Trivial Conversions
260//===----------------------------------------------------------------------===//
261
262using ConvertIndexAdd = mlir::OneToOneConvertToLLVMPattern<AddOp, LLVM::AddOp>;
263using ConvertIndexSub = mlir::OneToOneConvertToLLVMPattern<SubOp, LLVM::SubOp>;
264using ConvertIndexMul = mlir::OneToOneConvertToLLVMPattern<MulOp, LLVM::MulOp>;
265using ConvertIndexDivS =
266 mlir::OneToOneConvertToLLVMPattern<DivSOp, LLVM::SDivOp>;
267using ConvertIndexDivU =
268 mlir::OneToOneConvertToLLVMPattern<DivUOp, LLVM::UDivOp>;
269using ConvertIndexRemS =
270 mlir::OneToOneConvertToLLVMPattern<RemSOp, LLVM::SRemOp>;
271using ConvertIndexRemU =
272 mlir::OneToOneConvertToLLVMPattern<RemUOp, LLVM::URemOp>;
273using ConvertIndexMaxS =
274 mlir::OneToOneConvertToLLVMPattern<MaxSOp, LLVM::SMaxOp>;
275using ConvertIndexMaxU =
276 mlir::OneToOneConvertToLLVMPattern<MaxUOp, LLVM::UMaxOp>;
277using ConvertIndexMinS =
278 mlir::OneToOneConvertToLLVMPattern<MinSOp, LLVM::SMinOp>;
279using ConvertIndexMinU =
280 mlir::OneToOneConvertToLLVMPattern<MinUOp, LLVM::UMinOp>;
281using ConvertIndexShl = mlir::OneToOneConvertToLLVMPattern<ShlOp, LLVM::ShlOp>;
282using ConvertIndexShrS =
283 mlir::OneToOneConvertToLLVMPattern<ShrSOp, LLVM::AShrOp>;
284using ConvertIndexShrU =
285 mlir::OneToOneConvertToLLVMPattern<ShrUOp, LLVM::LShrOp>;
286using ConvertIndexAnd = mlir::OneToOneConvertToLLVMPattern<AndOp, LLVM::AndOp>;
287using ConvertIndexOr = mlir::OneToOneConvertToLLVMPattern<OrOp, LLVM::OrOp>;
288using ConvertIndexXor = mlir::OneToOneConvertToLLVMPattern<XOrOp, LLVM::XOrOp>;
289using ConvertIndexBoolConstant =
290 mlir::OneToOneConvertToLLVMPattern<BoolConstantOp, LLVM::ConstantOp>;
291
292} // namespace
293
294//===----------------------------------------------------------------------===//
295// Pattern Population
296//===----------------------------------------------------------------------===//
297
298void index::populateIndexToLLVMConversionPatterns(
299 const LLVMTypeConverter &typeConverter, RewritePatternSet &patterns) {
300 patterns.insert<
301 // clang-format off
302 ConvertIndexAdd,
303 ConvertIndexSub,
304 ConvertIndexMul,
305 ConvertIndexDivS,
306 ConvertIndexDivU,
307 ConvertIndexRemS,
308 ConvertIndexRemU,
309 ConvertIndexMaxS,
310 ConvertIndexMaxU,
311 ConvertIndexMinS,
312 ConvertIndexMinU,
313 ConvertIndexShl,
314 ConvertIndexShrS,
315 ConvertIndexShrU,
316 ConvertIndexAnd,
317 ConvertIndexOr,
318 ConvertIndexXor,
319 ConvertIndexCeilDivS,
320 ConvertIndexCeilDivU,
321 ConvertIndexFloorDivS,
322 ConvertIndexCastS,
323 ConvertIndexCastU,
324 ConvertIndexCmp,
325 ConvertIndexSizeOf,
326 ConvertIndexConstant,
327 ConvertIndexBoolConstant
328 // clang-format on
329 >(arg: typeConverter);
330}
331
332//===----------------------------------------------------------------------===//
333// ODS-Generated Definitions
334//===----------------------------------------------------------------------===//
335
336namespace mlir {
337#define GEN_PASS_DEF_CONVERTINDEXTOLLVMPASS
338#include "mlir/Conversion/Passes.h.inc"
339} // namespace mlir
340
341//===----------------------------------------------------------------------===//
342// Pass Definition
343//===----------------------------------------------------------------------===//
344
345namespace {
346struct ConvertIndexToLLVMPass
347 : public impl::ConvertIndexToLLVMPassBase<ConvertIndexToLLVMPass> {
348 using Base::Base;
349
350 void runOnOperation() override;
351};
352} // namespace
353
354void ConvertIndexToLLVMPass::runOnOperation() {
355 // Configure dialect conversion.
356 ConversionTarget target(getContext());
357 target.addIllegalDialect<IndexDialect>();
358 target.addLegalDialect<LLVM::LLVMDialect>();
359
360 // Set LLVM lowering options.
361 const auto &dataLayoutAnalysis = getAnalysis<DataLayoutAnalysis>();
362 LowerToLLVMOptions options(&getContext(),
363 dataLayoutAnalysis.getAtOrAbove(operation: getOperation()));
364 if (indexBitwidth != kDeriveIndexBitwidthFromDataLayout)
365 options.overrideIndexBitwidth(bitwidth: indexBitwidth);
366 LLVMTypeConverter typeConverter(&getContext(), options, &dataLayoutAnalysis);
367
368 // Populate patterns and run the conversion.
369 RewritePatternSet patterns(&getContext());
370 populateIndexToLLVMConversionPatterns(typeConverter, patterns);
371
372 if (failed(
373 Result: applyPartialConversion(op: getOperation(), target, patterns: std::move(patterns))))
374 return signalPassFailure();
375}
376
377//===----------------------------------------------------------------------===//
378// ConvertToLLVMPatternInterface implementation
379//===----------------------------------------------------------------------===//
380
381namespace {
382/// Implement the interface to convert Index to LLVM.
383struct IndexToLLVMDialectInterface : public ConvertToLLVMPatternInterface {
384 IndexToLLVMDialectInterface(Dialect *dialect)
385 : ConvertToLLVMPatternInterface(dialect) {}
386
387 void loadDependentDialects(MLIRContext *context) const final {
388 context->loadDialect<LLVM::LLVMDialect>();
389 }
390
391 /// Hook for derived dialect interface to provide conversion patterns
392 /// and mark dialect legal for the conversion target.
393 void populateConvertToLLVMConversionPatterns(
394 ConversionTarget &target, LLVMTypeConverter &typeConverter,
395 RewritePatternSet &patterns) const final {
396 populateIndexToLLVMConversionPatterns(typeConverter, patterns);
397 }
398};
399} // namespace
400
401void mlir::index::registerConvertIndexToLLVMInterface(
402 DialectRegistry &registry) {
403 registry.addExtension(extensionFn: +[](MLIRContext *ctx, index::IndexDialect *dialect) {
404 dialect->addInterfaces<IndexToLLVMDialectInterface>();
405 });
406}
407