1//===- MathToFuncs.cpp - Math to outlined implementation conversion -------===//
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/MathToFuncs/MathToFuncs.h"
10
11#include "mlir/Dialect/Arith/IR/Arith.h"
12#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
13#include "mlir/Dialect/Func/IR/FuncOps.h"
14#include "mlir/Dialect/LLVMIR/LLVMDialectDecl.h"
15#include "mlir/Dialect/Math/IR/Math.h"
16#include "mlir/Dialect/SCF/IR/SCF.h"
17#include "mlir/Dialect/Utils/IndexingUtils.h"
18#include "mlir/Dialect/Vector/IR/VectorOps.h"
19#include "mlir/Dialect/Vector/Utils/VectorUtils.h"
20#include "mlir/IR/SymbolTable.h"
21#include "mlir/IR/TypeUtilities.h"
22#include "mlir/Pass/Pass.h"
23#include "mlir/Transforms/DialectConversion.h"
24#include "llvm/ADT/DenseMap.h"
25#include "llvm/ADT/TypeSwitch.h"
26#include "llvm/Support/DebugLog.h"
27
28#include <tuple>
29
30namespace mlir {
31#define GEN_PASS_DEF_CONVERTMATHTOFUNCS
32#include "mlir/Conversion/Passes.h.inc"
33} // namespace mlir
34
35using namespace mlir;
36
37#define DEBUG_TYPE "math-to-funcs"
38
39namespace {
40// Pattern to convert vector operations to scalar operations.
41template <typename Op>
42struct VecOpToScalarOp : public OpRewritePattern<Op> {
43public:
44 using OpRewritePattern<Op>::OpRewritePattern;
45
46 LogicalResult matchAndRewrite(Op op, PatternRewriter &rewriter) const final;
47};
48
49// Callback type for getting pre-generated FuncOp implementing
50// an operation of the given type.
51using GetFuncCallbackTy = function_ref<func::FuncOp(Operation *, Type)>;
52
53// Pattern to convert scalar IPowIOp into a call of outlined
54// software implementation.
55class IPowIOpLowering : public OpRewritePattern<math::IPowIOp> {
56public:
57 IPowIOpLowering(MLIRContext *context, GetFuncCallbackTy cb)
58 : OpRewritePattern<math::IPowIOp>(context), getFuncOpCallback(cb) {}
59
60 /// Convert IPowI into a call to a local function implementing
61 /// the power operation. The local function computes a scalar result,
62 /// so vector forms of IPowI are linearized.
63 LogicalResult matchAndRewrite(math::IPowIOp op,
64 PatternRewriter &rewriter) const final;
65
66private:
67 GetFuncCallbackTy getFuncOpCallback;
68};
69
70// Pattern to convert scalar FPowIOp into a call of outlined
71// software implementation.
72class FPowIOpLowering : public OpRewritePattern<math::FPowIOp> {
73public:
74 FPowIOpLowering(MLIRContext *context, GetFuncCallbackTy cb)
75 : OpRewritePattern<math::FPowIOp>(context), getFuncOpCallback(cb) {}
76
77 /// Convert FPowI into a call to a local function implementing
78 /// the power operation. The local function computes a scalar result,
79 /// so vector forms of FPowI are linearized.
80 LogicalResult matchAndRewrite(math::FPowIOp op,
81 PatternRewriter &rewriter) const final;
82
83private:
84 GetFuncCallbackTy getFuncOpCallback;
85};
86
87// Pattern to convert scalar ctlz into a call of outlined software
88// implementation.
89class CtlzOpLowering : public OpRewritePattern<math::CountLeadingZerosOp> {
90public:
91 CtlzOpLowering(MLIRContext *context, GetFuncCallbackTy cb)
92 : OpRewritePattern<math::CountLeadingZerosOp>(context),
93 getFuncOpCallback(cb) {}
94
95 /// Convert ctlz into a call to a local function implementing
96 /// the count leading zeros operation.
97 LogicalResult matchAndRewrite(math::CountLeadingZerosOp op,
98 PatternRewriter &rewriter) const final;
99
100private:
101 GetFuncCallbackTy getFuncOpCallback;
102};
103} // namespace
104
105template <typename Op>
106LogicalResult
107VecOpToScalarOp<Op>::matchAndRewrite(Op op, PatternRewriter &rewriter) const {
108 Type opType = op.getType();
109 Location loc = op.getLoc();
110 auto vecType = dyn_cast<VectorType>(Val&: opType);
111
112 if (!vecType)
113 return rewriter.notifyMatchFailure(op, "not a vector operation");
114 if (!vecType.hasRank())
115 return rewriter.notifyMatchFailure(op, "unknown vector rank");
116 ArrayRef<int64_t> shape = vecType.getShape();
117 int64_t numElements = vecType.getNumElements();
118
119 Type resultElementType = vecType.getElementType();
120 Attribute initValueAttr;
121 if (isa<FloatType>(Val: resultElementType))
122 initValueAttr = FloatAttr::get(type: resultElementType, value: 0.0);
123 else
124 initValueAttr = IntegerAttr::get(type: resultElementType, value: 0);
125 Value result = arith::ConstantOp::create(
126 builder&: rewriter, location: loc, value: DenseElementsAttr::get(type: vecType, values: initValueAttr));
127 SmallVector<int64_t> strides = computeStrides(sizes: shape);
128 for (int64_t linearIndex = 0; linearIndex < numElements; ++linearIndex) {
129 SmallVector<int64_t> positions = delinearize(linearIndex, strides);
130 SmallVector<Value> operands;
131 for (Value input : op->getOperands())
132 operands.push_back(
133 Elt: vector::ExtractOp::create(builder&: rewriter, location: loc, source: input, position: positions));
134 Value scalarOp = Op::create(
135 rewriter, loc, TypeRange{vecType.getElementType()}, operands,
136 op.getProperties(), op->getDiscardableAttrDictionary().getValue());
137 result =
138 vector::InsertOp::create(builder&: rewriter, location: loc, valueToStore: scalarOp, dest: result, position: positions);
139 }
140 rewriter.replaceOp(op, result);
141 return success();
142}
143
144static FunctionType getElementalFuncTypeForOp(Operation *op) {
145 SmallVector<Type, 1> resultTys(op->getNumResults());
146 SmallVector<Type, 2> inputTys(op->getNumOperands());
147 std::transform(first: op->result_type_begin(), last: op->result_type_end(),
148 result: resultTys.begin(),
149 unary_op: [](Type ty) { return getElementTypeOrSelf(type: ty); });
150 std::transform(first: op->operand_type_begin(), last: op->operand_type_end(),
151 result: inputTys.begin(),
152 unary_op: [](Type ty) { return getElementTypeOrSelf(type: ty); });
153 return FunctionType::get(context: op->getContext(), inputs: inputTys, results: resultTys);
154}
155
156/// Create linkonce_odr function to implement the power function with
157/// the given \p elementType type inside \p symbolTable. The \p elementType
158/// must be IntegerType, an the created function has
159/// 'IntegerType (*)(IntegerType, IntegerType)' function type.
160///
161/// template <typename T>
162/// T __mlir_math_ipowi_*(T b, T p) {
163/// if (p == T(0))
164/// return T(1);
165/// if (p < T(0)) {
166/// if (b == T(1))
167/// return T(1);
168/// if (b == T(-1)) {
169/// if (p & T(1))
170/// return T(-1);
171/// return T(1);
172/// }
173/// return T(0); // |b| > 1 or b == 0
174/// }
175/// T result = T(1);
176/// while (true) {
177/// if (p & T(1))
178/// result *= b;
179/// p >>= T(1);
180/// if (p == T(0))
181/// return result;
182/// b *= b;
183/// }
184/// }
185static func::FuncOp createElementIPowIFunc(Operation *symbolTable,
186 Type elementType,
187 bool setLLVMLinkage) {
188 assert(isa<IntegerType>(elementType) &&
189 "non-integer element type for IPowIOp");
190
191 ImplicitLocOpBuilder builder = ImplicitLocOpBuilder::atBlockEnd(
192 loc: symbolTable->getLoc(), block: &symbolTable->getRegion(index: 0).front());
193
194 std::string funcName("__mlir_math_ipowi");
195 llvm::raw_string_ostream nameOS(funcName);
196 nameOS << '_' << elementType;
197
198 FunctionType funcType = FunctionType::get(
199 context: builder.getContext(), inputs: {elementType, elementType}, results: elementType);
200 auto funcOp = func::FuncOp::create(builder, name: funcName, type: funcType);
201 if (setLLVMLinkage) {
202 LLVM::linkage::Linkage inlineLinkage = LLVM::linkage::Linkage::LinkonceODR;
203 Attribute linkage =
204 LLVM::LinkageAttr::get(context: builder.getContext(), linkage: inlineLinkage);
205 funcOp->setDiscardableAttr(name: "llvm.linkage", value: linkage);
206 }
207 funcOp.setPrivate();
208
209 Block *entryBlock = funcOp.addEntryBlock();
210 Region *funcBody = entryBlock->getParent();
211
212 Value bArg = funcOp.getArgument(idx: 0);
213 Value pArg = funcOp.getArgument(idx: 1);
214 builder.setInsertionPointToEnd(entryBlock);
215 Value zeroValue = arith::ConstantOp::create(
216 builder, result: elementType, value: builder.getIntegerAttr(type: elementType, value: 0));
217 Value oneValue = arith::ConstantOp::create(
218 builder, result: elementType, value: builder.getIntegerAttr(type: elementType, value: 1));
219 Value minusOneValue = arith::ConstantOp::create(
220 builder, result: elementType,
221 value: builder.getIntegerAttr(type: elementType,
222 value: APInt(elementType.getIntOrFloatBitWidth(), -1ULL,
223 /*isSigned=*/true)));
224
225 // if (p == T(0))
226 // return T(1);
227 auto pIsZero =
228 arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::eq, lhs: pArg, rhs: zeroValue);
229 Block *thenBlock = builder.createBlock(parent: funcBody);
230 func::ReturnOp::create(builder, operands: oneValue);
231 Block *fallthroughBlock = builder.createBlock(parent: funcBody);
232 // Set up conditional branch for (p == T(0)).
233 builder.setInsertionPointToEnd(pIsZero->getBlock());
234 cf::CondBranchOp::create(builder, condition: pIsZero, trueDest: thenBlock, falseDest: fallthroughBlock);
235
236 // if (p < T(0)) {
237 builder.setInsertionPointToEnd(fallthroughBlock);
238 auto pIsNeg = arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::sle, lhs: pArg,
239 rhs: zeroValue);
240 // if (b == T(1))
241 builder.createBlock(parent: funcBody);
242 auto bIsOne =
243 arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::eq, lhs: bArg, rhs: oneValue);
244 // return T(1);
245 thenBlock = builder.createBlock(parent: funcBody);
246 func::ReturnOp::create(builder, operands: oneValue);
247 fallthroughBlock = builder.createBlock(parent: funcBody);
248 // Set up conditional branch for (b == T(1)).
249 builder.setInsertionPointToEnd(bIsOne->getBlock());
250 cf::CondBranchOp::create(builder, condition: bIsOne, trueDest: thenBlock, falseDest: fallthroughBlock);
251
252 // if (b == T(-1)) {
253 builder.setInsertionPointToEnd(fallthroughBlock);
254 auto bIsMinusOne = arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::eq,
255 lhs: bArg, rhs: minusOneValue);
256 // if (p & T(1))
257 builder.createBlock(parent: funcBody);
258 auto pIsOdd = arith::CmpIOp::create(
259 builder, predicate: arith::CmpIPredicate::ne,
260 lhs: arith::AndIOp::create(builder, lhs: pArg, rhs: oneValue), rhs: zeroValue);
261 // return T(-1);
262 thenBlock = builder.createBlock(parent: funcBody);
263 func::ReturnOp::create(builder, operands: minusOneValue);
264 fallthroughBlock = builder.createBlock(parent: funcBody);
265 // Set up conditional branch for (p & T(1)).
266 builder.setInsertionPointToEnd(pIsOdd->getBlock());
267 cf::CondBranchOp::create(builder, condition: pIsOdd, trueDest: thenBlock, falseDest: fallthroughBlock);
268
269 // return T(1);
270 // } // b == T(-1)
271 builder.setInsertionPointToEnd(fallthroughBlock);
272 func::ReturnOp::create(builder, operands: oneValue);
273 fallthroughBlock = builder.createBlock(parent: funcBody);
274 // Set up conditional branch for (b == T(-1)).
275 builder.setInsertionPointToEnd(bIsMinusOne->getBlock());
276 cf::CondBranchOp::create(builder, condition: bIsMinusOne, trueDest: pIsOdd->getBlock(),
277 falseDest: fallthroughBlock);
278
279 // return T(0);
280 // } // (p < T(0))
281 builder.setInsertionPointToEnd(fallthroughBlock);
282 func::ReturnOp::create(builder, operands: zeroValue);
283 Block *loopHeader = builder.createBlock(
284 parent: funcBody, insertPt: funcBody->end(), argTypes: {elementType, elementType, elementType},
285 locs: {builder.getLoc(), builder.getLoc(), builder.getLoc()});
286 // Set up conditional branch for (p < T(0)).
287 builder.setInsertionPointToEnd(pIsNeg->getBlock());
288 // Set initial values of 'result', 'b' and 'p' for the loop.
289 cf::CondBranchOp::create(builder, condition: pIsNeg, trueDest: bIsOne->getBlock(), falseDest: loopHeader,
290 falseOperands: ValueRange{oneValue, bArg, pArg});
291
292 // T result = T(1);
293 // while (true) {
294 // if (p & T(1))
295 // result *= b;
296 // p >>= T(1);
297 // if (p == T(0))
298 // return result;
299 // b *= b;
300 // }
301 Value resultTmp = loopHeader->getArgument(i: 0);
302 Value baseTmp = loopHeader->getArgument(i: 1);
303 Value powerTmp = loopHeader->getArgument(i: 2);
304 builder.setInsertionPointToEnd(loopHeader);
305
306 // if (p & T(1))
307 auto powerTmpIsOdd = arith::CmpIOp::create(
308 builder, predicate: arith::CmpIPredicate::ne,
309 lhs: arith::AndIOp::create(builder, lhs: powerTmp, rhs: oneValue), rhs: zeroValue);
310 thenBlock = builder.createBlock(parent: funcBody);
311 // result *= b;
312 Value newResultTmp = arith::MulIOp::create(builder, lhs: resultTmp, rhs: baseTmp);
313 fallthroughBlock = builder.createBlock(parent: funcBody, insertPt: funcBody->end(), argTypes: elementType,
314 locs: builder.getLoc());
315 builder.setInsertionPointToEnd(thenBlock);
316 cf::BranchOp::create(builder, destOperands: newResultTmp, dest: fallthroughBlock);
317 // Set up conditional branch for (p & T(1)).
318 builder.setInsertionPointToEnd(powerTmpIsOdd->getBlock());
319 cf::CondBranchOp::create(builder, condition: powerTmpIsOdd, trueDest: thenBlock, falseDest: fallthroughBlock,
320 falseOperands: resultTmp);
321 // Merged 'result'.
322 newResultTmp = fallthroughBlock->getArgument(i: 0);
323
324 // p >>= T(1);
325 builder.setInsertionPointToEnd(fallthroughBlock);
326 Value newPowerTmp = arith::ShRUIOp::create(builder, lhs: powerTmp, rhs: oneValue);
327
328 // if (p == T(0))
329 auto newPowerIsZero = arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::eq,
330 lhs: newPowerTmp, rhs: zeroValue);
331 // return result;
332 thenBlock = builder.createBlock(parent: funcBody);
333 func::ReturnOp::create(builder, operands: newResultTmp);
334 fallthroughBlock = builder.createBlock(parent: funcBody);
335 // Set up conditional branch for (p == T(0)).
336 builder.setInsertionPointToEnd(newPowerIsZero->getBlock());
337 cf::CondBranchOp::create(builder, condition: newPowerIsZero, trueDest: thenBlock,
338 falseDest: fallthroughBlock);
339
340 // b *= b;
341 // }
342 builder.setInsertionPointToEnd(fallthroughBlock);
343 Value newBaseTmp = arith::MulIOp::create(builder, lhs: baseTmp, rhs: baseTmp);
344 // Pass new values for 'result', 'b' and 'p' to the loop header.
345 cf::BranchOp::create(
346 builder, destOperands: ValueRange{newResultTmp, newBaseTmp, newPowerTmp}, dest: loopHeader);
347 return funcOp;
348}
349
350/// Convert IPowI into a call to a local function implementing
351/// the power operation. The local function computes a scalar result,
352/// so vector forms of IPowI are linearized.
353LogicalResult
354IPowIOpLowering::matchAndRewrite(math::IPowIOp op,
355 PatternRewriter &rewriter) const {
356 auto baseType = dyn_cast<IntegerType>(Val: op.getOperands()[0].getType());
357
358 if (!baseType)
359 return rewriter.notifyMatchFailure(arg&: op, msg: "non-integer base operand");
360
361 // The outlined software implementation must have been already
362 // generated.
363 func::FuncOp elementFunc = getFuncOpCallback(op, baseType);
364 if (!elementFunc)
365 return rewriter.notifyMatchFailure(arg&: op, msg: "missing software implementation");
366
367 rewriter.replaceOpWithNewOp<func::CallOp>(op, args&: elementFunc, args: op.getOperands());
368 return success();
369}
370
371/// Create linkonce_odr function to implement the power function with
372/// the given \p funcType type inside \p symbolTable. The \p funcType must be
373/// 'FloatType (*)(FloatType, IntegerType)' function type.
374///
375/// template <typename T>
376/// Tb __mlir_math_fpowi_*(Tb b, Tp p) {
377/// if (p == Tp{0})
378/// return Tb{1};
379/// bool isNegativePower{p < Tp{0}}
380/// bool isMin{p == std::numeric_limits<Tp>::min()};
381/// if (isMin) {
382/// p = std::numeric_limits<Tp>::max();
383/// } else if (isNegativePower) {
384/// p = -p;
385/// }
386/// Tb result = Tb{1};
387/// Tb origBase = Tb{b};
388/// while (true) {
389/// if (p & Tp{1})
390/// result *= b;
391/// p >>= Tp{1};
392/// if (p == Tp{0})
393/// break;
394/// b *= b;
395/// }
396/// if (isMin) {
397/// result *= origBase;
398/// }
399/// if (isNegativePower) {
400/// result = Tb{1} / result;
401/// }
402/// return result;
403/// }
404static func::FuncOp createElementFPowIFunc(Operation *symbolTable,
405 FunctionType funcType,
406 bool setLLVMLinkage) {
407 auto baseType = cast<FloatType>(Val: funcType.getInput(i: 0));
408 auto powType = cast<IntegerType>(Val: funcType.getInput(i: 1));
409 ImplicitLocOpBuilder builder = ImplicitLocOpBuilder::atBlockEnd(
410 loc: symbolTable->getLoc(), block: &symbolTable->getRegion(index: 0).front());
411
412 std::string funcName("__mlir_math_fpowi");
413 llvm::raw_string_ostream nameOS(funcName);
414 nameOS << '_' << baseType;
415 nameOS << '_' << powType;
416 auto funcOp = func::FuncOp::create(builder, name: funcName, type: funcType);
417 if (setLLVMLinkage) {
418 LLVM::linkage::Linkage inlineLinkage = LLVM::linkage::Linkage::LinkonceODR;
419 Attribute linkage =
420 LLVM::LinkageAttr::get(context: builder.getContext(), linkage: inlineLinkage);
421 funcOp->setDiscardableAttr(name: "llvm.linkage", value: linkage);
422 }
423 funcOp.setPrivate();
424
425 Block *entryBlock = funcOp.addEntryBlock();
426 Region *funcBody = entryBlock->getParent();
427
428 Value bArg = funcOp.getArgument(idx: 0);
429 Value pArg = funcOp.getArgument(idx: 1);
430 builder.setInsertionPointToEnd(entryBlock);
431 Value oneBValue = arith::ConstantOp::create(
432 builder, result: baseType, value: builder.getFloatAttr(type: baseType, value: 1.0));
433 Value zeroPValue = arith::ConstantOp::create(
434 builder, result: powType, value: builder.getIntegerAttr(type: powType, value: 0));
435 Value onePValue = arith::ConstantOp::create(
436 builder, result: powType, value: builder.getIntegerAttr(type: powType, value: 1));
437 Value minPValue = arith::ConstantOp::create(
438 builder, result: powType,
439 value: builder.getIntegerAttr(
440 type: powType, value: llvm::APInt::getSignedMinValue(numBits: powType.getWidth())));
441 Value maxPValue = arith::ConstantOp::create(
442 builder, result: powType,
443 value: builder.getIntegerAttr(
444 type: powType, value: llvm::APInt::getSignedMaxValue(numBits: powType.getWidth())));
445
446 // if (p == Tp{0})
447 // return Tb{1};
448 auto pIsZero = arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::eq, lhs: pArg,
449 rhs: zeroPValue);
450 Block *thenBlock = builder.createBlock(parent: funcBody);
451 func::ReturnOp::create(builder, operands: oneBValue);
452 Block *fallthroughBlock = builder.createBlock(parent: funcBody);
453 // Set up conditional branch for (p == Tp{0}).
454 builder.setInsertionPointToEnd(pIsZero->getBlock());
455 cf::CondBranchOp::create(builder, condition: pIsZero, trueDest: thenBlock, falseDest: fallthroughBlock);
456
457 builder.setInsertionPointToEnd(fallthroughBlock);
458 // bool isNegativePower{p < Tp{0}}
459 auto pIsNeg = arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::sle, lhs: pArg,
460 rhs: zeroPValue);
461 // bool isMin{p == std::numeric_limits<Tp>::min()};
462 auto pIsMin =
463 arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::eq, lhs: pArg, rhs: minPValue);
464
465 // if (isMin) {
466 // p = std::numeric_limits<Tp>::max();
467 // } else if (isNegativePower) {
468 // p = -p;
469 // }
470 Value negP = arith::SubIOp::create(builder, lhs: zeroPValue, rhs: pArg);
471 auto pInit = arith::SelectOp::create(builder, condition: pIsNeg, true_value: negP, false_value: pArg);
472 pInit = arith::SelectOp::create(builder, condition: pIsMin, true_value: maxPValue, false_value: pInit);
473
474 // Tb result = Tb{1};
475 // Tb origBase = Tb{b};
476 // while (true) {
477 // if (p & Tp{1})
478 // result *= b;
479 // p >>= Tp{1};
480 // if (p == Tp{0})
481 // break;
482 // b *= b;
483 // }
484 Block *loopHeader = builder.createBlock(
485 parent: funcBody, insertPt: funcBody->end(), argTypes: {baseType, baseType, powType},
486 locs: {builder.getLoc(), builder.getLoc(), builder.getLoc()});
487 // Set initial values of 'result', 'b' and 'p' for the loop.
488 builder.setInsertionPointToEnd(pInit->getBlock());
489 cf::BranchOp::create(builder, dest: loopHeader, destOperands: ValueRange{oneBValue, bArg, pInit});
490
491 // Create loop body.
492 Value resultTmp = loopHeader->getArgument(i: 0);
493 Value baseTmp = loopHeader->getArgument(i: 1);
494 Value powerTmp = loopHeader->getArgument(i: 2);
495 builder.setInsertionPointToEnd(loopHeader);
496
497 // if (p & Tp{1})
498 auto powerTmpIsOdd = arith::CmpIOp::create(
499 builder, predicate: arith::CmpIPredicate::ne,
500 lhs: arith::AndIOp::create(builder, lhs: powerTmp, rhs: onePValue), rhs: zeroPValue);
501 thenBlock = builder.createBlock(parent: funcBody);
502 // result *= b;
503 Value newResultTmp = arith::MulFOp::create(builder, lhs: resultTmp, rhs: baseTmp);
504 fallthroughBlock = builder.createBlock(parent: funcBody, insertPt: funcBody->end(), argTypes: baseType,
505 locs: builder.getLoc());
506 builder.setInsertionPointToEnd(thenBlock);
507 cf::BranchOp::create(builder, destOperands: newResultTmp, dest: fallthroughBlock);
508 // Set up conditional branch for (p & Tp{1}).
509 builder.setInsertionPointToEnd(powerTmpIsOdd->getBlock());
510 cf::CondBranchOp::create(builder, condition: powerTmpIsOdd, trueDest: thenBlock, falseDest: fallthroughBlock,
511 falseOperands: resultTmp);
512 // Merged 'result'.
513 newResultTmp = fallthroughBlock->getArgument(i: 0);
514
515 // p >>= Tp{1};
516 builder.setInsertionPointToEnd(fallthroughBlock);
517 Value newPowerTmp = arith::ShRUIOp::create(builder, lhs: powerTmp, rhs: onePValue);
518
519 // if (p == Tp{0})
520 auto newPowerIsZero = arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::eq,
521 lhs: newPowerTmp, rhs: zeroPValue);
522 // break;
523 //
524 // The conditional branch is finalized below with a jump to
525 // the loop exit block.
526 fallthroughBlock = builder.createBlock(parent: funcBody);
527
528 // b *= b;
529 // }
530 builder.setInsertionPointToEnd(fallthroughBlock);
531 Value newBaseTmp = arith::MulFOp::create(builder, lhs: baseTmp, rhs: baseTmp);
532 // Pass new values for 'result', 'b' and 'p' to the loop header.
533 cf::BranchOp::create(
534 builder, destOperands: ValueRange{newResultTmp, newBaseTmp, newPowerTmp}, dest: loopHeader);
535
536 // Set up conditional branch for early loop exit:
537 // if (p == Tp{0})
538 // break;
539 Block *loopExit = builder.createBlock(parent: funcBody, insertPt: funcBody->end(), argTypes: baseType,
540 locs: builder.getLoc());
541 builder.setInsertionPointToEnd(newPowerIsZero->getBlock());
542 cf::CondBranchOp::create(builder, condition: newPowerIsZero, trueDest: loopExit, trueOperands: newResultTmp,
543 falseDest: fallthroughBlock, falseOperands: ValueRange{});
544
545 // if (isMin) {
546 // result *= origBase;
547 // }
548 newResultTmp = loopExit->getArgument(i: 0);
549 thenBlock = builder.createBlock(parent: funcBody);
550 fallthroughBlock = builder.createBlock(parent: funcBody, insertPt: funcBody->end(), argTypes: baseType,
551 locs: builder.getLoc());
552 builder.setInsertionPointToEnd(loopExit);
553 cf::CondBranchOp::create(builder, condition: pIsMin, trueDest: thenBlock, falseDest: fallthroughBlock,
554 falseOperands: newResultTmp);
555 builder.setInsertionPointToEnd(thenBlock);
556 newResultTmp = arith::MulFOp::create(builder, lhs: newResultTmp, rhs: bArg);
557 cf::BranchOp::create(builder, destOperands: newResultTmp, dest: fallthroughBlock);
558
559 /// if (isNegativePower) {
560 /// result = Tb{1} / result;
561 /// }
562 newResultTmp = fallthroughBlock->getArgument(i: 0);
563 thenBlock = builder.createBlock(parent: funcBody);
564 Block *returnBlock = builder.createBlock(parent: funcBody, insertPt: funcBody->end(), argTypes: baseType,
565 locs: builder.getLoc());
566 builder.setInsertionPointToEnd(fallthroughBlock);
567 cf::CondBranchOp::create(builder, condition: pIsNeg, trueDest: thenBlock, falseDest: returnBlock,
568 falseOperands: newResultTmp);
569 builder.setInsertionPointToEnd(thenBlock);
570 newResultTmp = arith::DivFOp::create(builder, lhs: oneBValue, rhs: newResultTmp);
571 cf::BranchOp::create(builder, destOperands: newResultTmp, dest: returnBlock);
572
573 // return result;
574 builder.setInsertionPointToEnd(returnBlock);
575 func::ReturnOp::create(builder, operands: returnBlock->getArgument(i: 0));
576
577 return funcOp;
578}
579
580/// Convert FPowI into a call to a local function implementing
581/// the power operation. The local function computes a scalar result,
582/// so vector forms of FPowI are linearized.
583LogicalResult
584FPowIOpLowering::matchAndRewrite(math::FPowIOp op,
585 PatternRewriter &rewriter) const {
586 if (isa<VectorType>(Val: op.getType()))
587 return rewriter.notifyMatchFailure(arg&: op, msg: "non-scalar operation");
588
589 FunctionType funcType = getElementalFuncTypeForOp(op);
590
591 // The outlined software implementation must have been already
592 // generated.
593 func::FuncOp elementFunc = getFuncOpCallback(op, funcType);
594 if (!elementFunc)
595 return rewriter.notifyMatchFailure(arg&: op, msg: "missing software implementation");
596
597 rewriter.replaceOpWithNewOp<func::CallOp>(op, args&: elementFunc, args: op.getOperands());
598 return success();
599}
600
601/// Create function to implement the ctlz function the given \p elementType type
602/// inside \p symbolTable. The \p elementType must be IntegerType, an the
603/// created function has 'IntegerType (*)(IntegerType)' function type.
604///
605/// template <typename T>
606/// T __mlir_math_ctlz_*(T x) {
607/// bits = sizeof(x) * 8;
608/// if (x == 0)
609/// return bits;
610///
611/// uint32_t n = 0;
612/// for (int i = 1; i < bits; ++i) {
613/// if (x < 0) continue;
614/// n++;
615/// x <<= 1;
616/// }
617/// return n;
618/// }
619///
620/// Converts to (for i32):
621///
622/// func.func private @__mlir_math_ctlz_i32(%arg: i32) -> i32 {
623/// %c_32 = arith.constant 32 : index
624/// %c_0 = arith.constant 0 : i32
625/// %arg_eq_zero = arith.cmpi eq, %arg, %c_0 : i1
626/// %out = scf.if %arg_eq_zero {
627/// scf.yield %c_32 : i32
628/// } else {
629/// %c_1index = arith.constant 1 : index
630/// %c_1i32 = arith.constant 1 : i32
631/// %n = arith.constant 0 : i32
632/// %arg_out, %n_out = scf.for %i = %c_1index to %c_32 step %c_1index
633/// iter_args(%arg_iter = %arg, %n_iter = %n) -> (i32, i32) {
634/// %cond = arith.cmpi slt, %arg_iter, %c_0 : i32
635/// %yield_val = scf.if %cond {
636/// scf.yield %arg_iter, %n_iter : i32, i32
637/// } else {
638/// %arg_next = arith.shli %arg_iter, %c_1i32 : i32
639/// %n_next = arith.addi %n_iter, %c_1i32 : i32
640/// scf.yield %arg_next, %n_next : i32, i32
641/// }
642/// scf.yield %yield_val: i32, i32
643/// }
644/// scf.yield %n_out : i32
645/// }
646/// return %out: i32
647/// }
648static func::FuncOp createCtlzFunc(Operation *symbolTable, Type elementType,
649 bool setLLVMLinkage) {
650 if (!isa<IntegerType>(Val: elementType)) {
651 LDBG() << "non-integer element type for CtlzFunc; type was: "
652 << elementType;
653 llvm_unreachable("non-integer element type");
654 }
655 int64_t bitWidth = elementType.getIntOrFloatBitWidth();
656
657 Location loc = symbolTable->getLoc();
658 ImplicitLocOpBuilder builder =
659 ImplicitLocOpBuilder::atBlockEnd(loc, block: &symbolTable->getRegion(index: 0).front());
660
661 std::string funcName("__mlir_math_ctlz");
662 llvm::raw_string_ostream nameOS(funcName);
663 nameOS << '_' << elementType;
664 FunctionType funcType =
665 FunctionType::get(context: builder.getContext(), inputs: {elementType}, results: elementType);
666 auto funcOp = func::FuncOp::create(builder, name: funcName, type: funcType);
667
668 // LinkonceODR ensures that there is only one implementation of this function
669 // across all math.ctlz functions that are lowered in this way.
670 if (setLLVMLinkage) {
671 LLVM::linkage::Linkage inlineLinkage = LLVM::linkage::Linkage::LinkonceODR;
672 Attribute linkage =
673 LLVM::LinkageAttr::get(context: builder.getContext(), linkage: inlineLinkage);
674 funcOp->setDiscardableAttr(name: "llvm.linkage", value: linkage);
675 }
676 funcOp.setPrivate();
677
678 // set the insertion point to the start of the function
679 Block *funcBody = funcOp.addEntryBlock();
680 builder.setInsertionPointToStart(funcBody);
681
682 Value arg = funcOp.getArgument(idx: 0);
683 Type indexType = builder.getIndexType();
684 Value bitWidthValue = arith::ConstantOp::create(
685 builder, result: elementType, value: builder.getIntegerAttr(type: elementType, value: bitWidth));
686 Value zeroValue = arith::ConstantOp::create(
687 builder, result: elementType, value: builder.getIntegerAttr(type: elementType, value: 0));
688
689 Value inputEqZero =
690 arith::CmpIOp::create(builder, predicate: arith::CmpIPredicate::eq, lhs: arg, rhs: zeroValue);
691
692 // if input == 0, return bit width, else enter loop.
693 scf::IfOp ifOp =
694 scf::IfOp::create(builder, resultTypes: elementType, cond: inputEqZero,
695 /*addThenBlock=*/true, /*addElseBlock=*/true);
696 auto thenBuilder = ifOp.getThenBodyBuilder();
697 scf::YieldOp::create(builder&: thenBuilder, location: loc, results: bitWidthValue);
698
699 auto elseBuilder =
700 ImplicitLocOpBuilder::atBlockEnd(loc, block: &ifOp.getElseRegion().front());
701
702 Value oneIndex = arith::ConstantOp::create(builder&: elseBuilder, result: indexType,
703 value: elseBuilder.getIndexAttr(value: 1));
704 Value oneValue = arith::ConstantOp::create(
705 builder&: elseBuilder, result: elementType, value: elseBuilder.getIntegerAttr(type: elementType, value: 1));
706 Value bitWidthIndex = arith::ConstantOp::create(
707 builder&: elseBuilder, result: indexType, value: elseBuilder.getIndexAttr(value: bitWidth));
708 Value nValue = arith::ConstantOp::create(
709 builder&: elseBuilder, result: elementType, value: elseBuilder.getIntegerAttr(type: elementType, value: 0));
710
711 auto loop = scf::ForOp::create(
712 builder&: elseBuilder, lowerBound: oneIndex, upperBound: bitWidthIndex, step: oneIndex,
713 // Initial values for two loop induction variables, the arg which is being
714 // shifted left in each iteration, and the n value which tracks the count
715 // of leading zeros.
716 initArgs: ValueRange{arg, nValue},
717 // Callback to build the body of the for loop
718 // if (arg < 0) {
719 // continue;
720 // } else {
721 // n++;
722 // arg <<= 1;
723 // }
724 odsArg4: [&](OpBuilder &b, Location loc, Value iv, ValueRange args) {
725 Value argIter = args[0];
726 Value nIter = args[1];
727
728 Value argIsNonNegative = arith::CmpIOp::create(
729 builder&: b, location: loc, predicate: arith::CmpIPredicate::slt, lhs: argIter, rhs: zeroValue);
730 scf::IfOp ifOp = scf::IfOp::create(
731 builder&: b, location: loc, cond: argIsNonNegative,
732 thenBuilder: [&](OpBuilder &b, Location loc) {
733 // If arg is negative, continue (effectively, break)
734 scf::YieldOp::create(builder&: b, location: loc, results: ValueRange{argIter, nIter});
735 },
736 elseBuilder: [&](OpBuilder &b, Location loc) {
737 // Otherwise, increment n and shift arg left.
738 Value nNext = arith::AddIOp::create(builder&: b, location: loc, lhs: nIter, rhs: oneValue);
739 Value argNext = arith::ShLIOp::create(builder&: b, location: loc, lhs: argIter, rhs: oneValue);
740 scf::YieldOp::create(builder&: b, location: loc, results: ValueRange{argNext, nNext});
741 });
742 scf::YieldOp::create(builder&: b, location: loc, results: ifOp.getResults());
743 });
744 scf::YieldOp::create(builder&: elseBuilder, results: loop.getResult(i: 1));
745
746 func::ReturnOp::create(builder, operands: ifOp.getResult(i: 0));
747 return funcOp;
748}
749
750/// Convert ctlz into a call to a local function implementing the ctlz
751/// operation.
752LogicalResult CtlzOpLowering::matchAndRewrite(math::CountLeadingZerosOp op,
753 PatternRewriter &rewriter) const {
754 if (isa<VectorType>(Val: op.getType()))
755 return rewriter.notifyMatchFailure(arg&: op, msg: "non-scalar operation");
756
757 Type type = getElementTypeOrSelf(type: op.getResult().getType());
758 func::FuncOp elementFunc = getFuncOpCallback(op, type);
759 if (!elementFunc)
760 return rewriter.notifyMatchFailure(op, reasonCallback: [&](::mlir::Diagnostic &diag) {
761 diag << "Missing software implementation for op " << op->getName()
762 << " and type " << type;
763 });
764
765 rewriter.replaceOpWithNewOp<func::CallOp>(op, args&: elementFunc, args: op.getOperand());
766 return success();
767}
768
769namespace {
770struct ConvertMathToFuncsPass
771 : public impl::ConvertMathToFuncsBase<ConvertMathToFuncsPass> {
772 ConvertMathToFuncsPass() = default;
773 ConvertMathToFuncsPass(const ConvertMathToFuncsOptions &options)
774 : impl::ConvertMathToFuncsBase<ConvertMathToFuncsPass>(options) {}
775
776 void runOnOperation() override;
777
778private:
779 // Return true, if this FPowI operation must be converted
780 // because the width of its exponent's type is greater than
781 // or equal to minWidthOfFPowIExponent option value.
782 bool isFPowIConvertible(math::FPowIOp op);
783
784 // Reture true, if operation is integer type.
785 bool isConvertible(Operation *op);
786
787 // Generate outlined implementations for power operations
788 // and store them in funcImpls map.
789 void generateOpImplementations();
790
791 // A map between tuples of (operation, type, symbol table) and the
792 // corresponding outlined software implementations.
793 DenseMap<std::tuple<OperationName, Type, Operation *>, func::FuncOp>
794 funcImpls;
795};
796} // namespace
797
798bool ConvertMathToFuncsPass::isFPowIConvertible(math::FPowIOp op) {
799 auto expTy =
800 dyn_cast<IntegerType>(Val: getElementTypeOrSelf(type: op.getRhs().getType()));
801 return (expTy && expTy.getWidth() >= minWidthOfFPowIExponent);
802}
803
804bool ConvertMathToFuncsPass::isConvertible(Operation *op) {
805 return isa<IntegerType>(Val: getElementTypeOrSelf(type: op->getResult(idx: 0).getType()));
806}
807
808void ConvertMathToFuncsPass::generateOpImplementations() {
809 ModuleOp module = getOperation();
810
811 module.walk(callback: [&](Operation *op) {
812 TypeSwitch<Operation *>(op)
813 .Case(caseFn: [&](math::CountLeadingZerosOp op) {
814 if (!convertCtlz || !isConvertible(op))
815 return;
816 Type resultType = getElementTypeOrSelf(type: op.getResult().getType());
817
818 // Generate the software implementation of this operation,
819 // if it has not been generated yet.
820 Operation *symbolTable = SymbolTable::getNearestSymbolTable(from: op);
821 auto key = std::make_tuple(args: op->getName(), args&: resultType, args&: symbolTable);
822 auto entry = funcImpls.try_emplace(Key: key, Args: func::FuncOp{});
823 if (entry.second)
824 entry.first->second =
825 createCtlzFunc(symbolTable, elementType: resultType, setLLVMLinkage);
826 })
827 .Case(caseFn: [&](math::IPowIOp op) {
828 if (!isConvertible(op))
829 return;
830
831 Type resultType = getElementTypeOrSelf(type: op.getResult().getType());
832
833 // Generate the software implementation of this operation,
834 // if it has not been generated yet.
835 Operation *symbolTable = SymbolTable::getNearestSymbolTable(from: op);
836 auto key = std::make_tuple(args: op->getName(), args&: resultType, args&: symbolTable);
837 auto entry = funcImpls.try_emplace(Key: key, Args: func::FuncOp{});
838 if (entry.second)
839 entry.first->second =
840 createElementIPowIFunc(symbolTable, elementType: resultType, setLLVMLinkage);
841 })
842 .Case(caseFn: [&](math::FPowIOp op) {
843 if (!isFPowIConvertible(op))
844 return;
845
846 FunctionType funcType = getElementalFuncTypeForOp(op);
847
848 // Generate the software implementation of this operation,
849 // if it has not been generated yet.
850 // FPowI implementations are mapped via the FunctionType
851 // created from the operation's result and operands.
852 Operation *symbolTable = SymbolTable::getNearestSymbolTable(from: op);
853 auto key = std::make_tuple(args: op->getName(), args&: funcType, args&: symbolTable);
854 auto entry = funcImpls.try_emplace(Key: key, Args: func::FuncOp{});
855 if (entry.second)
856 entry.first->second =
857 createElementFPowIFunc(symbolTable, funcType, setLLVMLinkage);
858 });
859 });
860}
861
862void ConvertMathToFuncsPass::runOnOperation() {
863 ModuleOp module = getOperation();
864
865 // Create outlined implementations for power operations.
866 generateOpImplementations();
867
868 RewritePatternSet patterns(&getContext());
869 patterns.add<VecOpToScalarOp<math::IPowIOp>, VecOpToScalarOp<math::FPowIOp>,
870 VecOpToScalarOp<math::CountLeadingZerosOp>>(
871 arg: patterns.getContext());
872
873 // For the given Type Returns FuncOp stored in funcImpls map.
874 auto getFuncOpByType = [&](Operation *op, Type type) -> func::FuncOp {
875 auto key = std::make_tuple(args: op->getName(), args&: type,
876 args: SymbolTable::getNearestSymbolTable(from: op));
877 auto it = funcImpls.find(Val: key);
878 if (it == funcImpls.end())
879 return {};
880
881 return it->second;
882 };
883 patterns.add<IPowIOpLowering, FPowIOpLowering>(arg: patterns.getContext(),
884 args&: getFuncOpByType);
885
886 if (convertCtlz)
887 patterns.add<CtlzOpLowering>(arg: patterns.getContext(), args&: getFuncOpByType);
888
889 ConversionTarget target(getContext());
890 target.addLegalDialect<arith::ArithDialect, cf::ControlFlowDialect,
891 func::FuncDialect, scf::SCFDialect,
892 vector::VectorDialect>();
893
894 target.addDynamicallyLegalOp<math::IPowIOp>(
895 callback: [this](math::IPowIOp op) { return !isConvertible(op); });
896 if (convertCtlz) {
897 target.addDynamicallyLegalOp<math::CountLeadingZerosOp>(
898 callback: [this](math::CountLeadingZerosOp op) { return !isConvertible(op); });
899 }
900 target.addDynamicallyLegalOp<math::FPowIOp>(
901 callback: [this](math::FPowIOp op) { return !isFPowIConvertible(op); });
902 if (failed(Result: applyPartialConversion(op: module, target, patterns: std::move(patterns))))
903 signalPassFailure();
904}
905