1 //===- ModuleTranslation.cpp - MLIR to LLVM conversion --------------------===//
2 //
3 // Part of the MLIR 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 implements the translation between an MLIR LLVM dialect module and
10 // the corresponding LLVMIR module. It only handles core LLVM IR operations.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "mlir/Target/LLVMIR/ModuleTranslation.h"
15 
16 #include "mlir/Dialect/LLVMIR/LLVMDialect.h"
17 #include "mlir/IR/Attributes.h"
18 #include "mlir/IR/Module.h"
19 #include "mlir/Support/LLVM.h"
20 
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/DerivedTypes.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/LLVMContext.h"
27 #include "llvm/IR/Module.h"
28 #include "llvm/Transforms/Utils/Cloning.h"
29 
30 using namespace mlir;
31 using namespace mlir::LLVM;
32 
33 /// Create an LLVM IR constant of `llvmType` from the MLIR attribute `attr`.
34 /// This currently supports integer, floating point, splat and dense element
35 /// attributes and combinations thereof.  In case of error, report it to `loc`
36 /// and return nullptr.
37 llvm::Constant *ModuleTranslation::getLLVMConstant(llvm::Type *llvmType,
38                                                    Attribute attr,
39                                                    Location loc) {
40   if (!attr)
41     return llvm::UndefValue::get(llvmType);
42   if (auto intAttr = attr.dyn_cast<IntegerAttr>())
43     return llvm::ConstantInt::get(llvmType, intAttr.getValue());
44   if (auto floatAttr = attr.dyn_cast<FloatAttr>())
45     return llvm::ConstantFP::get(llvmType, floatAttr.getValue());
46   if (auto funcAttr = attr.dyn_cast<FlatSymbolRefAttr>())
47     return functionMapping.lookup(funcAttr.getValue());
48   if (auto splatAttr = attr.dyn_cast<SplatElementsAttr>()) {
49     auto *sequentialType = cast<llvm::SequentialType>(llvmType);
50     auto elementType = sequentialType->getElementType();
51     uint64_t numElements = sequentialType->getNumElements();
52     // Splat value is a scalar. Extract it only if the element type is not
53     // another sequence type. The recursion terminates because each step removes
54     // one outer sequential type.
55     llvm::Constant *child = getLLVMConstant(
56         elementType,
57         isa<llvm::SequentialType>(elementType) ? splatAttr
58                                                : splatAttr.getSplatValue(),
59         loc);
60     if (llvmType->isVectorTy())
61       return llvm::ConstantVector::getSplat(numElements, child);
62     if (llvmType->isArrayTy()) {
63       auto arrayType = llvm::ArrayType::get(elementType, numElements);
64       SmallVector<llvm::Constant *, 8> constants(numElements, child);
65       return llvm::ConstantArray::get(arrayType, constants);
66     }
67   }
68   if (auto elementsAttr = attr.dyn_cast<ElementsAttr>()) {
69     auto *sequentialType = cast<llvm::SequentialType>(llvmType);
70     auto elementType = sequentialType->getElementType();
71     uint64_t numElements = sequentialType->getNumElements();
72     SmallVector<llvm::Constant *, 8> constants;
73     constants.reserve(numElements);
74     for (auto n : elementsAttr.getValues<Attribute>()) {
75       constants.push_back(getLLVMConstant(elementType, n, loc));
76       if (!constants.back())
77         return nullptr;
78     }
79     if (llvmType->isVectorTy())
80       return llvm::ConstantVector::get(constants);
81     if (llvmType->isArrayTy()) {
82       auto arrayType = llvm::ArrayType::get(elementType, numElements);
83       return llvm::ConstantArray::get(arrayType, constants);
84     }
85   }
86   if (auto stringAttr = attr.dyn_cast<StringAttr>()) {
87     return llvm::ConstantDataArray::get(
88         llvmModule->getContext(), ArrayRef<char>{stringAttr.getValue().data(),
89                                                  stringAttr.getValue().size()});
90   }
91   emitError(loc, "unsupported constant value");
92   return nullptr;
93 }
94 
95 /// Convert MLIR integer comparison predicate to LLVM IR comparison predicate.
96 static llvm::CmpInst::Predicate getLLVMCmpPredicate(ICmpPredicate p) {
97   switch (p) {
98   case LLVM::ICmpPredicate::eq:
99     return llvm::CmpInst::Predicate::ICMP_EQ;
100   case LLVM::ICmpPredicate::ne:
101     return llvm::CmpInst::Predicate::ICMP_NE;
102   case LLVM::ICmpPredicate::slt:
103     return llvm::CmpInst::Predicate::ICMP_SLT;
104   case LLVM::ICmpPredicate::sle:
105     return llvm::CmpInst::Predicate::ICMP_SLE;
106   case LLVM::ICmpPredicate::sgt:
107     return llvm::CmpInst::Predicate::ICMP_SGT;
108   case LLVM::ICmpPredicate::sge:
109     return llvm::CmpInst::Predicate::ICMP_SGE;
110   case LLVM::ICmpPredicate::ult:
111     return llvm::CmpInst::Predicate::ICMP_ULT;
112   case LLVM::ICmpPredicate::ule:
113     return llvm::CmpInst::Predicate::ICMP_ULE;
114   case LLVM::ICmpPredicate::ugt:
115     return llvm::CmpInst::Predicate::ICMP_UGT;
116   case LLVM::ICmpPredicate::uge:
117     return llvm::CmpInst::Predicate::ICMP_UGE;
118   }
119   llvm_unreachable("incorrect comparison predicate");
120 }
121 
122 static llvm::CmpInst::Predicate getLLVMCmpPredicate(FCmpPredicate p) {
123   switch (p) {
124   case LLVM::FCmpPredicate::_false:
125     return llvm::CmpInst::Predicate::FCMP_FALSE;
126   case LLVM::FCmpPredicate::oeq:
127     return llvm::CmpInst::Predicate::FCMP_OEQ;
128   case LLVM::FCmpPredicate::ogt:
129     return llvm::CmpInst::Predicate::FCMP_OGT;
130   case LLVM::FCmpPredicate::oge:
131     return llvm::CmpInst::Predicate::FCMP_OGE;
132   case LLVM::FCmpPredicate::olt:
133     return llvm::CmpInst::Predicate::FCMP_OLT;
134   case LLVM::FCmpPredicate::ole:
135     return llvm::CmpInst::Predicate::FCMP_OLE;
136   case LLVM::FCmpPredicate::one:
137     return llvm::CmpInst::Predicate::FCMP_ONE;
138   case LLVM::FCmpPredicate::ord:
139     return llvm::CmpInst::Predicate::FCMP_ORD;
140   case LLVM::FCmpPredicate::ueq:
141     return llvm::CmpInst::Predicate::FCMP_UEQ;
142   case LLVM::FCmpPredicate::ugt:
143     return llvm::CmpInst::Predicate::FCMP_UGT;
144   case LLVM::FCmpPredicate::uge:
145     return llvm::CmpInst::Predicate::FCMP_UGE;
146   case LLVM::FCmpPredicate::ult:
147     return llvm::CmpInst::Predicate::FCMP_ULT;
148   case LLVM::FCmpPredicate::ule:
149     return llvm::CmpInst::Predicate::FCMP_ULE;
150   case LLVM::FCmpPredicate::une:
151     return llvm::CmpInst::Predicate::FCMP_UNE;
152   case LLVM::FCmpPredicate::uno:
153     return llvm::CmpInst::Predicate::FCMP_UNO;
154   case LLVM::FCmpPredicate::_true:
155     return llvm::CmpInst::Predicate::FCMP_TRUE;
156   }
157   llvm_unreachable("incorrect comparison predicate");
158 }
159 
160 /// Given a single MLIR operation, create the corresponding LLVM IR operation
161 /// using the `builder`.  LLVM IR Builder does not have a generic interface so
162 /// this has to be a long chain of `if`s calling different functions with a
163 /// different number of arguments.
164 LogicalResult ModuleTranslation::convertOperation(Operation &opInst,
165                                                   llvm::IRBuilder<> &builder) {
166   auto extractPosition = [](ArrayAttr attr) {
167     SmallVector<unsigned, 4> position;
168     position.reserve(attr.size());
169     for (Attribute v : attr)
170       position.push_back(v.cast<IntegerAttr>().getValue().getZExtValue());
171     return position;
172   };
173 
174 #include "mlir/Dialect/LLVMIR/LLVMConversions.inc"
175 
176   // Emit function calls.  If the "callee" attribute is present, this is a
177   // direct function call and we also need to look up the remapped function
178   // itself.  Otherwise, this is an indirect call and the callee is the first
179   // operand, look it up as a normal value.  Return the llvm::Value representing
180   // the function result, which may be of llvm::VoidTy type.
181   auto convertCall = [this, &builder](Operation &op) -> llvm::Value * {
182     auto operands = lookupValues(op.getOperands());
183     ArrayRef<llvm::Value *> operandsRef(operands);
184     if (auto attr = op.getAttrOfType<FlatSymbolRefAttr>("callee")) {
185       return builder.CreateCall(functionMapping.lookup(attr.getValue()),
186                                 operandsRef);
187     } else {
188       return builder.CreateCall(operandsRef.front(), operandsRef.drop_front());
189     }
190   };
191 
192   // Emit calls.  If the called function has a result, remap the corresponding
193   // value.  Note that LLVM IR dialect CallOp has either 0 or 1 result.
194   if (isa<LLVM::CallOp>(opInst)) {
195     llvm::Value *result = convertCall(opInst);
196     if (opInst.getNumResults() != 0) {
197       valueMapping[opInst.getResult(0)] = result;
198       return success();
199     }
200     // Check that LLVM call returns void for 0-result functions.
201     return success(result->getType()->isVoidTy());
202   }
203 
204   // Emit branches.  We need to look up the remapped blocks and ignore the block
205   // arguments that were transformed into PHI nodes.
206   if (auto brOp = dyn_cast<LLVM::BrOp>(opInst)) {
207     builder.CreateBr(blockMapping[brOp.getSuccessor(0)]);
208     return success();
209   }
210   if (auto condbrOp = dyn_cast<LLVM::CondBrOp>(opInst)) {
211     builder.CreateCondBr(valueMapping.lookup(condbrOp.getOperand(0)),
212                          blockMapping[condbrOp.getSuccessor(0)],
213                          blockMapping[condbrOp.getSuccessor(1)]);
214     return success();
215   }
216 
217   // Emit addressof.  We need to look up the global value referenced by the
218   // operation and store it in the MLIR-to-LLVM value mapping.  This does not
219   // emit any LLVM instruction.
220   if (auto addressOfOp = dyn_cast<LLVM::AddressOfOp>(opInst)) {
221     LLVM::GlobalOp global = addressOfOp.getGlobal();
222     // The verifier should not have allowed this.
223     assert(global && "referencing an undefined global");
224 
225     valueMapping[addressOfOp.getResult()] = globalsMapping.lookup(global);
226     return success();
227   }
228 
229   return opInst.emitError("unsupported or non-LLVM operation: ")
230          << opInst.getName();
231 }
232 
233 /// Convert block to LLVM IR.  Unless `ignoreArguments` is set, emit PHI nodes
234 /// to define values corresponding to the MLIR block arguments.  These nodes
235 /// are not connected to the source basic blocks, which may not exist yet.
236 LogicalResult ModuleTranslation::convertBlock(Block &bb, bool ignoreArguments) {
237   llvm::IRBuilder<> builder(blockMapping[&bb]);
238 
239   // Before traversing operations, make block arguments available through
240   // value remapping and PHI nodes, but do not add incoming edges for the PHI
241   // nodes just yet: those values may be defined by this or following blocks.
242   // This step is omitted if "ignoreArguments" is set.  The arguments of the
243   // first block have been already made available through the remapping of
244   // LLVM function arguments.
245   if (!ignoreArguments) {
246     auto predecessors = bb.getPredecessors();
247     unsigned numPredecessors =
248         std::distance(predecessors.begin(), predecessors.end());
249     for (auto arg : bb.getArguments()) {
250       auto wrappedType = arg.getType().dyn_cast<LLVM::LLVMType>();
251       if (!wrappedType)
252         return emitError(bb.front().getLoc(),
253                          "block argument does not have an LLVM type");
254       llvm::Type *type = wrappedType.getUnderlyingType();
255       llvm::PHINode *phi = builder.CreatePHI(type, numPredecessors);
256       valueMapping[arg] = phi;
257     }
258   }
259 
260   // Traverse operations.
261   for (auto &op : bb) {
262     if (failed(convertOperation(op, builder)))
263       return failure();
264   }
265 
266   return success();
267 }
268 
269 /// Convert the LLVM dialect linkage type to LLVM IR linkage type.
270 llvm::GlobalVariable::LinkageTypes convertLinkageType(LLVM::Linkage linkage) {
271   switch (linkage) {
272   case LLVM::Linkage::Private:
273     return llvm::GlobalValue::PrivateLinkage;
274   case LLVM::Linkage::Internal:
275     return llvm::GlobalValue::InternalLinkage;
276   case LLVM::Linkage::AvailableExternally:
277     return llvm::GlobalValue::AvailableExternallyLinkage;
278   case LLVM::Linkage::Linkonce:
279     return llvm::GlobalValue::LinkOnceAnyLinkage;
280   case LLVM::Linkage::Weak:
281     return llvm::GlobalValue::WeakAnyLinkage;
282   case LLVM::Linkage::Common:
283     return llvm::GlobalValue::CommonLinkage;
284   case LLVM::Linkage::Appending:
285     return llvm::GlobalValue::AppendingLinkage;
286   case LLVM::Linkage::ExternWeak:
287     return llvm::GlobalValue::ExternalWeakLinkage;
288   case LLVM::Linkage::LinkonceODR:
289     return llvm::GlobalValue::LinkOnceODRLinkage;
290   case LLVM::Linkage::WeakODR:
291     return llvm::GlobalValue::WeakODRLinkage;
292   case LLVM::Linkage::External:
293     return llvm::GlobalValue::ExternalLinkage;
294   }
295   llvm_unreachable("unknown linkage type");
296 }
297 
298 /// Create named global variables that correspond to llvm.mlir.global
299 /// definitions.
300 void ModuleTranslation::convertGlobals() {
301   for (auto op : getModuleBody(mlirModule).getOps<LLVM::GlobalOp>()) {
302     llvm::Type *type = op.getType().getUnderlyingType();
303     llvm::Constant *cst = llvm::UndefValue::get(type);
304     if (op.getValueOrNull()) {
305       // String attributes are treated separately because they cannot appear as
306       // in-function constants and are thus not supported by getLLVMConstant.
307       if (auto strAttr = op.getValueOrNull().dyn_cast_or_null<StringAttr>()) {
308         cst = llvm::ConstantDataArray::getString(
309             llvmModule->getContext(), strAttr.getValue(), /*AddNull=*/false);
310         type = cst->getType();
311       } else {
312         cst = getLLVMConstant(type, op.getValueOrNull(), op.getLoc());
313       }
314     } else if (Block *initializer = op.getInitializerBlock()) {
315       llvm::IRBuilder<> builder(llvmModule->getContext());
316       for (auto &op : initializer->without_terminator()) {
317         if (failed(convertOperation(op, builder)) ||
318             !isa<llvm::Constant>(valueMapping.lookup(op.getResult(0)))) {
319           emitError(op.getLoc(), "unemittable constant value");
320           return;
321         }
322       }
323       ReturnOp ret = cast<ReturnOp>(initializer->getTerminator());
324       cst = cast<llvm::Constant>(valueMapping.lookup(ret.getOperand(0)));
325     }
326 
327     auto linkage = convertLinkageType(op.linkage());
328     bool anyExternalLinkage =
329         (linkage == llvm::GlobalVariable::ExternalLinkage ||
330          linkage == llvm::GlobalVariable::ExternalWeakLinkage);
331     auto addrSpace = op.addr_space().getLimitedValue();
332     auto *var = new llvm::GlobalVariable(
333         *llvmModule, type, op.constant(), linkage,
334         anyExternalLinkage ? nullptr : cst, op.sym_name(),
335         /*InsertBefore=*/nullptr, llvm::GlobalValue::NotThreadLocal, addrSpace);
336 
337     globalsMapping.try_emplace(op, var);
338   }
339 }
340 
341 /// Get the SSA value passed to the current block from the terminator operation
342 /// of its predecessor.
343 static Value getPHISourceValue(Block *current, Block *pred,
344                                unsigned numArguments, unsigned index) {
345   auto &terminator = *pred->getTerminator();
346   if (isa<LLVM::BrOp>(terminator)) {
347     return terminator.getOperand(index);
348   }
349 
350   // For conditional branches, we need to check if the current block is reached
351   // through the "true" or the "false" branch and take the relevant operands.
352   auto condBranchOp = dyn_cast<LLVM::CondBrOp>(terminator);
353   assert(condBranchOp &&
354          "only branch operations can be terminators of a block that "
355          "has successors");
356   assert((condBranchOp.getSuccessor(0) != condBranchOp.getSuccessor(1)) &&
357          "successors with arguments in LLVM conditional branches must be "
358          "different blocks");
359 
360   return condBranchOp.getSuccessor(0) == current
361              ? terminator.getSuccessorOperand(0, index)
362              : terminator.getSuccessorOperand(1, index);
363 }
364 
365 void ModuleTranslation::connectPHINodes(LLVMFuncOp func) {
366   // Skip the first block, it cannot be branched to and its arguments correspond
367   // to the arguments of the LLVM function.
368   for (auto it = std::next(func.begin()), eit = func.end(); it != eit; ++it) {
369     Block *bb = &*it;
370     llvm::BasicBlock *llvmBB = blockMapping.lookup(bb);
371     auto phis = llvmBB->phis();
372     auto numArguments = bb->getNumArguments();
373     assert(numArguments == std::distance(phis.begin(), phis.end()));
374     for (auto &numberedPhiNode : llvm::enumerate(phis)) {
375       auto &phiNode = numberedPhiNode.value();
376       unsigned index = numberedPhiNode.index();
377       for (auto *pred : bb->getPredecessors()) {
378         phiNode.addIncoming(valueMapping.lookup(getPHISourceValue(
379                                 bb, pred, numArguments, index)),
380                             blockMapping.lookup(pred));
381       }
382     }
383   }
384 }
385 
386 // TODO(mlir-team): implement an iterative version
387 static void topologicalSortImpl(llvm::SetVector<Block *> &blocks, Block *b) {
388   blocks.insert(b);
389   for (Block *bb : b->getSuccessors()) {
390     if (blocks.count(bb) == 0)
391       topologicalSortImpl(blocks, bb);
392   }
393 }
394 
395 /// Sort function blocks topologically.
396 static llvm::SetVector<Block *> topologicalSort(LLVMFuncOp f) {
397   // For each blocks that has not been visited yet (i.e. that has no
398   // predecessors), add it to the list and traverse its successors in DFS
399   // preorder.
400   llvm::SetVector<Block *> blocks;
401   for (Block &b : f.getBlocks()) {
402     if (blocks.count(&b) == 0)
403       topologicalSortImpl(blocks, &b);
404   }
405   assert(blocks.size() == f.getBlocks().size() && "some blocks are not sorted");
406 
407   return blocks;
408 }
409 
410 LogicalResult ModuleTranslation::convertOneFunction(LLVMFuncOp func) {
411   // Clear the block and value mappings, they are only relevant within one
412   // function.
413   blockMapping.clear();
414   valueMapping.clear();
415   llvm::Function *llvmFunc = functionMapping.lookup(func.getName());
416   // Add function arguments to the value remapping table.
417   // If there was noalias info then we decorate each argument accordingly.
418   unsigned int argIdx = 0;
419   for (auto kvp : llvm::zip(func.getArguments(), llvmFunc->args())) {
420     llvm::Argument &llvmArg = std::get<1>(kvp);
421     BlockArgument mlirArg = std::get<0>(kvp);
422 
423     if (auto attr = func.getArgAttrOfType<BoolAttr>(argIdx, "llvm.noalias")) {
424       // NB: Attribute already verified to be boolean, so check if we can indeed
425       // attach the attribute to this argument, based on its type.
426       auto argTy = mlirArg.getType().dyn_cast<LLVM::LLVMType>();
427       if (!argTy.getUnderlyingType()->isPointerTy())
428         return func.emitError(
429             "llvm.noalias attribute attached to LLVM non-pointer argument");
430       if (attr.getValue())
431         llvmArg.addAttr(llvm::Attribute::AttrKind::NoAlias);
432     }
433     valueMapping[mlirArg] = &llvmArg;
434     argIdx++;
435   }
436 
437   // First, create all blocks so we can jump to them.
438   llvm::LLVMContext &llvmContext = llvmFunc->getContext();
439   for (auto &bb : func) {
440     auto *llvmBB = llvm::BasicBlock::Create(llvmContext);
441     llvmBB->insertInto(llvmFunc);
442     blockMapping[&bb] = llvmBB;
443   }
444 
445   // Then, convert blocks one by one in topological order to ensure defs are
446   // converted before uses.
447   auto blocks = topologicalSort(func);
448   for (auto indexedBB : llvm::enumerate(blocks)) {
449     auto *bb = indexedBB.value();
450     if (failed(convertBlock(*bb, /*ignoreArguments=*/indexedBB.index() == 0)))
451       return failure();
452   }
453 
454   // Finally, after all blocks have been traversed and values mapped, connect
455   // the PHI nodes to the results of preceding blocks.
456   connectPHINodes(func);
457   return success();
458 }
459 
460 LogicalResult ModuleTranslation::checkSupportedModuleOps(Operation *m) {
461   for (Operation &o : getModuleBody(m).getOperations())
462     if (!isa<LLVM::LLVMFuncOp>(&o) && !isa<LLVM::GlobalOp>(&o) &&
463         !o.isKnownTerminator())
464       return o.emitOpError("unsupported module-level operation");
465   return success();
466 }
467 
468 LogicalResult ModuleTranslation::convertFunctions() {
469   // Declare all functions first because there may be function calls that form a
470   // call graph with cycles.
471   for (auto function : getModuleBody(mlirModule).getOps<LLVMFuncOp>()) {
472     llvm::FunctionCallee llvmFuncCst = llvmModule->getOrInsertFunction(
473         function.getName(),
474         cast<llvm::FunctionType>(function.getType().getUnderlyingType()));
475     assert(isa<llvm::Function>(llvmFuncCst.getCallee()));
476     functionMapping[function.getName()] =
477         cast<llvm::Function>(llvmFuncCst.getCallee());
478   }
479 
480   // Convert functions.
481   for (auto function : getModuleBody(mlirModule).getOps<LLVMFuncOp>()) {
482     // Ignore external functions.
483     if (function.isExternal())
484       continue;
485 
486     if (failed(convertOneFunction(function)))
487       return failure();
488   }
489 
490   return success();
491 }
492 
493 /// A helper to look up remapped operands in the value remapping table.`
494 SmallVector<llvm::Value *, 8>
495 ModuleTranslation::lookupValues(ValueRange values) {
496   SmallVector<llvm::Value *, 8> remapped;
497   remapped.reserve(values.size());
498   for (Value v : values)
499     remapped.push_back(valueMapping.lookup(v));
500   return remapped;
501 }
502 
503 std::unique_ptr<llvm::Module>
504 ModuleTranslation::prepareLLVMModule(Operation *m) {
505   auto *dialect = m->getContext()->getRegisteredDialect<LLVM::LLVMDialect>();
506   assert(dialect && "LLVM dialect must be registered");
507 
508   auto llvmModule = llvm::CloneModule(dialect->getLLVMModule());
509   if (!llvmModule)
510     return nullptr;
511 
512   llvm::LLVMContext &llvmContext = llvmModule->getContext();
513   llvm::IRBuilder<> builder(llvmContext);
514 
515   // Inject declarations for `malloc` and `free` functions that can be used in
516   // memref allocation/deallocation coming from standard ops lowering.
517   llvmModule->getOrInsertFunction("malloc", builder.getInt8PtrTy(),
518                                   builder.getInt64Ty());
519   llvmModule->getOrInsertFunction("free", builder.getVoidTy(),
520                                   builder.getInt8PtrTy());
521 
522   return llvmModule;
523 }
524