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