1 //===- ModuleTranslation.cpp - MLIR to LLVM 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 // 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 "DebugTranslation.h"
17 #include "mlir/Dialect/LLVMIR/LLVMDialect.h"
18 #include "mlir/IR/Attributes.h"
19 #include "mlir/IR/Module.h"
20 #include "mlir/IR/StandardTypes.h"
21 #include "mlir/Support/LLVM.h"
22 
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/IRBuilder.h"
28 #include "llvm/IR/LLVMContext.h"
29 #include "llvm/IR/Module.h"
30 #include "llvm/Transforms/Utils/Cloning.h"
31 
32 using namespace mlir;
33 using namespace mlir::LLVM;
34 using namespace mlir::LLVM::detail;
35 
36 #include "mlir/Dialect/LLVMIR/LLVMConversionEnumsToLLVM.inc"
37 
38 /// Builds a constant of a sequential LLVM type `type`, potentially containing
39 /// other sequential types recursively, from the individual constant values
40 /// provided in `constants`. `shape` contains the number of elements in nested
41 /// sequential types. Reports errors at `loc` and returns nullptr on error.
42 static llvm::Constant *
43 buildSequentialConstant(ArrayRef<llvm::Constant *> &constants,
44                         ArrayRef<int64_t> shape, llvm::Type *type,
45                         Location loc) {
46   if (shape.empty()) {
47     llvm::Constant *result = constants.front();
48     constants = constants.drop_front();
49     return result;
50   }
51 
52   if (!isa<llvm::SequentialType>(type)) {
53     emitError(loc) << "expected sequential LLVM types wrapping a scalar";
54     return nullptr;
55   }
56 
57   llvm::Type *elementType = type->getSequentialElementType();
58   SmallVector<llvm::Constant *, 8> nested;
59   nested.reserve(shape.front());
60   for (int64_t i = 0; i < shape.front(); ++i) {
61     nested.push_back(buildSequentialConstant(constants, shape.drop_front(),
62                                              elementType, loc));
63     if (!nested.back())
64       return nullptr;
65   }
66 
67   if (shape.size() == 1 && type->isVectorTy())
68     return llvm::ConstantVector::get(nested);
69   return llvm::ConstantArray::get(
70       llvm::ArrayType::get(elementType, shape.front()), nested);
71 }
72 
73 /// Returns the first non-sequential type nested in sequential types.
74 static llvm::Type *getInnermostElementType(llvm::Type *type) {
75   while (isa<llvm::SequentialType>(type))
76     type = type->getSequentialElementType();
77   return type;
78 }
79 
80 /// Create an LLVM IR constant of `llvmType` from the MLIR attribute `attr`.
81 /// This currently supports integer, floating point, splat and dense element
82 /// attributes and combinations thereof.  In case of error, report it to `loc`
83 /// and return nullptr.
84 llvm::Constant *ModuleTranslation::getLLVMConstant(llvm::Type *llvmType,
85                                                    Attribute attr,
86                                                    Location loc) {
87   if (!attr)
88     return llvm::UndefValue::get(llvmType);
89   if (llvmType->isStructTy()) {
90     emitError(loc, "struct types are not supported in constants");
91     return nullptr;
92   }
93   if (auto intAttr = attr.dyn_cast<IntegerAttr>())
94     return llvm::ConstantInt::get(llvmType, intAttr.getValue());
95   if (auto floatAttr = attr.dyn_cast<FloatAttr>())
96     return llvm::ConstantFP::get(llvmType, floatAttr.getValue());
97   if (auto funcAttr = attr.dyn_cast<FlatSymbolRefAttr>())
98     return functionMapping.lookup(funcAttr.getValue());
99   if (auto splatAttr = attr.dyn_cast<SplatElementsAttr>()) {
100     auto *sequentialType = cast<llvm::SequentialType>(llvmType);
101     auto elementType = sequentialType->getElementType();
102     uint64_t numElements = sequentialType->getNumElements();
103     // Splat value is a scalar. Extract it only if the element type is not
104     // another sequence type. The recursion terminates because each step removes
105     // one outer sequential type.
106     llvm::Constant *child = getLLVMConstant(
107         elementType,
108         isa<llvm::SequentialType>(elementType) ? splatAttr
109                                                : splatAttr.getSplatValue(),
110         loc);
111     if (!child)
112       return nullptr;
113     if (llvmType->isVectorTy())
114       return llvm::ConstantVector::getSplat(numElements, child);
115     if (llvmType->isArrayTy()) {
116       auto arrayType = llvm::ArrayType::get(elementType, numElements);
117       SmallVector<llvm::Constant *, 8> constants(numElements, child);
118       return llvm::ConstantArray::get(arrayType, constants);
119     }
120   }
121 
122   if (auto elementsAttr = attr.dyn_cast<ElementsAttr>()) {
123     assert(elementsAttr.getType().hasStaticShape());
124     assert(elementsAttr.getNumElements() != 0 &&
125            "unexpected empty elements attribute");
126     assert(!elementsAttr.getType().getShape().empty() &&
127            "unexpected empty elements attribute shape");
128 
129     SmallVector<llvm::Constant *, 8> constants;
130     constants.reserve(elementsAttr.getNumElements());
131     llvm::Type *innermostType = getInnermostElementType(llvmType);
132     for (auto n : elementsAttr.getValues<Attribute>()) {
133       constants.push_back(getLLVMConstant(innermostType, n, loc));
134       if (!constants.back())
135         return nullptr;
136     }
137     ArrayRef<llvm::Constant *> constantsRef = constants;
138     llvm::Constant *result = buildSequentialConstant(
139         constantsRef, elementsAttr.getType().getShape(), llvmType, loc);
140     assert(constantsRef.empty() && "did not consume all elemental constants");
141     return result;
142   }
143 
144   if (auto stringAttr = attr.dyn_cast<StringAttr>()) {
145     return llvm::ConstantDataArray::get(
146         llvmModule->getContext(), ArrayRef<char>{stringAttr.getValue().data(),
147                                                  stringAttr.getValue().size()});
148   }
149   emitError(loc, "unsupported constant value");
150   return nullptr;
151 }
152 
153 /// Convert MLIR integer comparison predicate to LLVM IR comparison predicate.
154 static llvm::CmpInst::Predicate getLLVMCmpPredicate(ICmpPredicate p) {
155   switch (p) {
156   case LLVM::ICmpPredicate::eq:
157     return llvm::CmpInst::Predicate::ICMP_EQ;
158   case LLVM::ICmpPredicate::ne:
159     return llvm::CmpInst::Predicate::ICMP_NE;
160   case LLVM::ICmpPredicate::slt:
161     return llvm::CmpInst::Predicate::ICMP_SLT;
162   case LLVM::ICmpPredicate::sle:
163     return llvm::CmpInst::Predicate::ICMP_SLE;
164   case LLVM::ICmpPredicate::sgt:
165     return llvm::CmpInst::Predicate::ICMP_SGT;
166   case LLVM::ICmpPredicate::sge:
167     return llvm::CmpInst::Predicate::ICMP_SGE;
168   case LLVM::ICmpPredicate::ult:
169     return llvm::CmpInst::Predicate::ICMP_ULT;
170   case LLVM::ICmpPredicate::ule:
171     return llvm::CmpInst::Predicate::ICMP_ULE;
172   case LLVM::ICmpPredicate::ugt:
173     return llvm::CmpInst::Predicate::ICMP_UGT;
174   case LLVM::ICmpPredicate::uge:
175     return llvm::CmpInst::Predicate::ICMP_UGE;
176   }
177   llvm_unreachable("incorrect comparison predicate");
178 }
179 
180 static llvm::CmpInst::Predicate getLLVMCmpPredicate(FCmpPredicate p) {
181   switch (p) {
182   case LLVM::FCmpPredicate::_false:
183     return llvm::CmpInst::Predicate::FCMP_FALSE;
184   case LLVM::FCmpPredicate::oeq:
185     return llvm::CmpInst::Predicate::FCMP_OEQ;
186   case LLVM::FCmpPredicate::ogt:
187     return llvm::CmpInst::Predicate::FCMP_OGT;
188   case LLVM::FCmpPredicate::oge:
189     return llvm::CmpInst::Predicate::FCMP_OGE;
190   case LLVM::FCmpPredicate::olt:
191     return llvm::CmpInst::Predicate::FCMP_OLT;
192   case LLVM::FCmpPredicate::ole:
193     return llvm::CmpInst::Predicate::FCMP_OLE;
194   case LLVM::FCmpPredicate::one:
195     return llvm::CmpInst::Predicate::FCMP_ONE;
196   case LLVM::FCmpPredicate::ord:
197     return llvm::CmpInst::Predicate::FCMP_ORD;
198   case LLVM::FCmpPredicate::ueq:
199     return llvm::CmpInst::Predicate::FCMP_UEQ;
200   case LLVM::FCmpPredicate::ugt:
201     return llvm::CmpInst::Predicate::FCMP_UGT;
202   case LLVM::FCmpPredicate::uge:
203     return llvm::CmpInst::Predicate::FCMP_UGE;
204   case LLVM::FCmpPredicate::ult:
205     return llvm::CmpInst::Predicate::FCMP_ULT;
206   case LLVM::FCmpPredicate::ule:
207     return llvm::CmpInst::Predicate::FCMP_ULE;
208   case LLVM::FCmpPredicate::une:
209     return llvm::CmpInst::Predicate::FCMP_UNE;
210   case LLVM::FCmpPredicate::uno:
211     return llvm::CmpInst::Predicate::FCMP_UNO;
212   case LLVM::FCmpPredicate::_true:
213     return llvm::CmpInst::Predicate::FCMP_TRUE;
214   }
215   llvm_unreachable("incorrect comparison predicate");
216 }
217 
218 static llvm::AtomicRMWInst::BinOp getLLVMAtomicBinOp(AtomicBinOp op) {
219   switch (op) {
220   case LLVM::AtomicBinOp::xchg:
221     return llvm::AtomicRMWInst::BinOp::Xchg;
222   case LLVM::AtomicBinOp::add:
223     return llvm::AtomicRMWInst::BinOp::Add;
224   case LLVM::AtomicBinOp::sub:
225     return llvm::AtomicRMWInst::BinOp::Sub;
226   case LLVM::AtomicBinOp::_and:
227     return llvm::AtomicRMWInst::BinOp::And;
228   case LLVM::AtomicBinOp::nand:
229     return llvm::AtomicRMWInst::BinOp::Nand;
230   case LLVM::AtomicBinOp::_or:
231     return llvm::AtomicRMWInst::BinOp::Or;
232   case LLVM::AtomicBinOp::_xor:
233     return llvm::AtomicRMWInst::BinOp::Xor;
234   case LLVM::AtomicBinOp::max:
235     return llvm::AtomicRMWInst::BinOp::Max;
236   case LLVM::AtomicBinOp::min:
237     return llvm::AtomicRMWInst::BinOp::Min;
238   case LLVM::AtomicBinOp::umax:
239     return llvm::AtomicRMWInst::BinOp::UMax;
240   case LLVM::AtomicBinOp::umin:
241     return llvm::AtomicRMWInst::BinOp::UMin;
242   case LLVM::AtomicBinOp::fadd:
243     return llvm::AtomicRMWInst::BinOp::FAdd;
244   case LLVM::AtomicBinOp::fsub:
245     return llvm::AtomicRMWInst::BinOp::FSub;
246   }
247   llvm_unreachable("incorrect atomic binary operator");
248 }
249 
250 static llvm::AtomicOrdering getLLVMAtomicOrdering(AtomicOrdering ordering) {
251   switch (ordering) {
252   case LLVM::AtomicOrdering::not_atomic:
253     return llvm::AtomicOrdering::NotAtomic;
254   case LLVM::AtomicOrdering::unordered:
255     return llvm::AtomicOrdering::Unordered;
256   case LLVM::AtomicOrdering::monotonic:
257     return llvm::AtomicOrdering::Monotonic;
258   case LLVM::AtomicOrdering::acquire:
259     return llvm::AtomicOrdering::Acquire;
260   case LLVM::AtomicOrdering::release:
261     return llvm::AtomicOrdering::Release;
262   case LLVM::AtomicOrdering::acq_rel:
263     return llvm::AtomicOrdering::AcquireRelease;
264   case LLVM::AtomicOrdering::seq_cst:
265     return llvm::AtomicOrdering::SequentiallyConsistent;
266   }
267   llvm_unreachable("incorrect atomic ordering");
268 }
269 
270 ModuleTranslation::ModuleTranslation(Operation *module,
271                                      std::unique_ptr<llvm::Module> llvmModule)
272     : mlirModule(module), llvmModule(std::move(llvmModule)),
273       debugTranslation(
274           std::make_unique<DebugTranslation>(module, *this->llvmModule)) {
275   assert(satisfiesLLVMModule(mlirModule) &&
276          "mlirModule should honor LLVM's module semantics.");
277 }
278 ModuleTranslation::~ModuleTranslation() {}
279 
280 /// Given a single MLIR operation, create the corresponding LLVM IR operation
281 /// using the `builder`.  LLVM IR Builder does not have a generic interface so
282 /// this has to be a long chain of `if`s calling different functions with a
283 /// different number of arguments.
284 LogicalResult ModuleTranslation::convertOperation(Operation &opInst,
285                                                   llvm::IRBuilder<> &builder) {
286   auto extractPosition = [](ArrayAttr attr) {
287     SmallVector<unsigned, 4> position;
288     position.reserve(attr.size());
289     for (Attribute v : attr)
290       position.push_back(v.cast<IntegerAttr>().getValue().getZExtValue());
291     return position;
292   };
293 
294 #include "mlir/Dialect/LLVMIR/LLVMConversions.inc"
295 
296   // Emit function calls.  If the "callee" attribute is present, this is a
297   // direct function call and we also need to look up the remapped function
298   // itself.  Otherwise, this is an indirect call and the callee is the first
299   // operand, look it up as a normal value.  Return the llvm::Value representing
300   // the function result, which may be of llvm::VoidTy type.
301   auto convertCall = [this, &builder](Operation &op) -> llvm::Value * {
302     auto operands = lookupValues(op.getOperands());
303     ArrayRef<llvm::Value *> operandsRef(operands);
304     if (auto attr = op.getAttrOfType<FlatSymbolRefAttr>("callee")) {
305       return builder.CreateCall(functionMapping.lookup(attr.getValue()),
306                                 operandsRef);
307     } else {
308       return builder.CreateCall(operandsRef.front(), operandsRef.drop_front());
309     }
310   };
311 
312   // Emit calls.  If the called function has a result, remap the corresponding
313   // value.  Note that LLVM IR dialect CallOp has either 0 or 1 result.
314   if (isa<LLVM::CallOp>(opInst)) {
315     llvm::Value *result = convertCall(opInst);
316     if (opInst.getNumResults() != 0) {
317       valueMapping[opInst.getResult(0)] = result;
318       return success();
319     }
320     // Check that LLVM call returns void for 0-result functions.
321     return success(result->getType()->isVoidTy());
322   }
323 
324   if (auto invOp = dyn_cast<LLVM::InvokeOp>(opInst)) {
325     auto operands = lookupValues(opInst.getOperands());
326     ArrayRef<llvm::Value *> operandsRef(operands);
327     if (auto attr = opInst.getAttrOfType<FlatSymbolRefAttr>("callee"))
328       builder.CreateInvoke(functionMapping.lookup(attr.getValue()),
329                            blockMapping[invOp.getSuccessor(0)],
330                            blockMapping[invOp.getSuccessor(1)], operandsRef);
331     else
332       builder.CreateInvoke(
333           operandsRef.front(), blockMapping[invOp.getSuccessor(0)],
334           blockMapping[invOp.getSuccessor(1)], operandsRef.drop_front());
335     return success();
336   }
337 
338   if (auto lpOp = dyn_cast<LLVM::LandingpadOp>(opInst)) {
339     llvm::Type *ty = lpOp.getType().dyn_cast<LLVMType>().getUnderlyingType();
340     llvm::LandingPadInst *lpi =
341         builder.CreateLandingPad(ty, lpOp.getNumOperands());
342 
343     // Add clauses
344     for (auto operand : lookupValues(lpOp.getOperands())) {
345       // All operands should be constant - checked by verifier
346       if (auto constOperand = dyn_cast<llvm::Constant>(operand))
347         lpi->addClause(constOperand);
348     }
349     return success();
350   }
351 
352   // Emit branches.  We need to look up the remapped blocks and ignore the block
353   // arguments that were transformed into PHI nodes.
354   if (auto brOp = dyn_cast<LLVM::BrOp>(opInst)) {
355     builder.CreateBr(blockMapping[brOp.getSuccessor(0)]);
356     return success();
357   }
358   if (auto condbrOp = dyn_cast<LLVM::CondBrOp>(opInst)) {
359     builder.CreateCondBr(valueMapping.lookup(condbrOp.getOperand(0)),
360                          blockMapping[condbrOp.getSuccessor(0)],
361                          blockMapping[condbrOp.getSuccessor(1)]);
362     return success();
363   }
364 
365   // Emit addressof.  We need to look up the global value referenced by the
366   // operation and store it in the MLIR-to-LLVM value mapping.  This does not
367   // emit any LLVM instruction.
368   if (auto addressOfOp = dyn_cast<LLVM::AddressOfOp>(opInst)) {
369     LLVM::GlobalOp global = addressOfOp.getGlobal();
370     // The verifier should not have allowed this.
371     assert(global && "referencing an undefined global");
372 
373     valueMapping[addressOfOp.getResult()] = globalsMapping.lookup(global);
374     return success();
375   }
376 
377   return opInst.emitError("unsupported or non-LLVM operation: ")
378          << opInst.getName();
379 }
380 
381 /// Convert block to LLVM IR.  Unless `ignoreArguments` is set, emit PHI nodes
382 /// to define values corresponding to the MLIR block arguments.  These nodes
383 /// are not connected to the source basic blocks, which may not exist yet.
384 LogicalResult ModuleTranslation::convertBlock(Block &bb, bool ignoreArguments) {
385   llvm::IRBuilder<> builder(blockMapping[&bb]);
386   auto *subprogram = builder.GetInsertBlock()->getParent()->getSubprogram();
387 
388   // Before traversing operations, make block arguments available through
389   // value remapping and PHI nodes, but do not add incoming edges for the PHI
390   // nodes just yet: those values may be defined by this or following blocks.
391   // This step is omitted if "ignoreArguments" is set.  The arguments of the
392   // first block have been already made available through the remapping of
393   // LLVM function arguments.
394   if (!ignoreArguments) {
395     auto predecessors = bb.getPredecessors();
396     unsigned numPredecessors =
397         std::distance(predecessors.begin(), predecessors.end());
398     for (auto arg : bb.getArguments()) {
399       auto wrappedType = arg.getType().dyn_cast<LLVM::LLVMType>();
400       if (!wrappedType)
401         return emitError(bb.front().getLoc(),
402                          "block argument does not have an LLVM type");
403       llvm::Type *type = wrappedType.getUnderlyingType();
404       llvm::PHINode *phi = builder.CreatePHI(type, numPredecessors);
405       valueMapping[arg] = phi;
406     }
407   }
408 
409   // Traverse operations.
410   for (auto &op : bb) {
411     // Set the current debug location within the builder.
412     builder.SetCurrentDebugLocation(
413         debugTranslation->translateLoc(op.getLoc(), subprogram));
414 
415     if (failed(convertOperation(op, builder)))
416       return failure();
417   }
418 
419   return success();
420 }
421 
422 /// Create named global variables that correspond to llvm.mlir.global
423 /// definitions.
424 LogicalResult ModuleTranslation::convertGlobals() {
425   for (auto op : getModuleBody(mlirModule).getOps<LLVM::GlobalOp>()) {
426     llvm::Type *type = op.getType().getUnderlyingType();
427     llvm::Constant *cst = llvm::UndefValue::get(type);
428     if (op.getValueOrNull()) {
429       // String attributes are treated separately because they cannot appear as
430       // in-function constants and are thus not supported by getLLVMConstant.
431       if (auto strAttr = op.getValueOrNull().dyn_cast_or_null<StringAttr>()) {
432         cst = llvm::ConstantDataArray::getString(
433             llvmModule->getContext(), strAttr.getValue(), /*AddNull=*/false);
434         type = cst->getType();
435       } else if (!(cst = getLLVMConstant(type, op.getValueOrNull(),
436                                          op.getLoc()))) {
437         return failure();
438       }
439     } else if (Block *initializer = op.getInitializerBlock()) {
440       llvm::IRBuilder<> builder(llvmModule->getContext());
441       for (auto &op : initializer->without_terminator()) {
442         if (failed(convertOperation(op, builder)) ||
443             !isa<llvm::Constant>(valueMapping.lookup(op.getResult(0))))
444           return emitError(op.getLoc(), "unemittable constant value");
445       }
446       ReturnOp ret = cast<ReturnOp>(initializer->getTerminator());
447       cst = cast<llvm::Constant>(valueMapping.lookup(ret.getOperand(0)));
448     }
449 
450     auto linkage = convertLinkageToLLVM(op.linkage());
451     bool anyExternalLinkage =
452         (linkage == llvm::GlobalVariable::ExternalLinkage ||
453          linkage == llvm::GlobalVariable::ExternalWeakLinkage);
454     auto addrSpace = op.addr_space().getLimitedValue();
455     auto *var = new llvm::GlobalVariable(
456         *llvmModule, type, op.constant(), linkage,
457         anyExternalLinkage ? nullptr : cst, op.sym_name(),
458         /*InsertBefore=*/nullptr, llvm::GlobalValue::NotThreadLocal, addrSpace);
459 
460     globalsMapping.try_emplace(op, var);
461   }
462 
463   return success();
464 }
465 
466 /// Get the SSA value passed to the current block from the terminator operation
467 /// of its predecessor.
468 static Value getPHISourceValue(Block *current, Block *pred,
469                                unsigned numArguments, unsigned index) {
470   auto &terminator = *pred->getTerminator();
471   if (isa<LLVM::BrOp>(terminator)) {
472     return terminator.getOperand(index);
473   }
474 
475   // For conditional branches, we need to check if the current block is reached
476   // through the "true" or the "false" branch and take the relevant operands.
477   auto condBranchOp = dyn_cast<LLVM::CondBrOp>(terminator);
478   assert(condBranchOp &&
479          "only branch operations can be terminators of a block that "
480          "has successors");
481   assert((condBranchOp.getSuccessor(0) != condBranchOp.getSuccessor(1)) &&
482          "successors with arguments in LLVM conditional branches must be "
483          "different blocks");
484 
485   return condBranchOp.getSuccessor(0) == current
486              ? terminator.getSuccessorOperand(0, index)
487              : terminator.getSuccessorOperand(1, index);
488 }
489 
490 void ModuleTranslation::connectPHINodes(LLVMFuncOp func) {
491   // Skip the first block, it cannot be branched to and its arguments correspond
492   // to the arguments of the LLVM function.
493   for (auto it = std::next(func.begin()), eit = func.end(); it != eit; ++it) {
494     Block *bb = &*it;
495     llvm::BasicBlock *llvmBB = blockMapping.lookup(bb);
496     auto phis = llvmBB->phis();
497     auto numArguments = bb->getNumArguments();
498     assert(numArguments == std::distance(phis.begin(), phis.end()));
499     for (auto &numberedPhiNode : llvm::enumerate(phis)) {
500       auto &phiNode = numberedPhiNode.value();
501       unsigned index = numberedPhiNode.index();
502       for (auto *pred : bb->getPredecessors()) {
503         phiNode.addIncoming(valueMapping.lookup(getPHISourceValue(
504                                 bb, pred, numArguments, index)),
505                             blockMapping.lookup(pred));
506       }
507     }
508   }
509 }
510 
511 // TODO(mlir-team): implement an iterative version
512 static void topologicalSortImpl(llvm::SetVector<Block *> &blocks, Block *b) {
513   blocks.insert(b);
514   for (Block *bb : b->getSuccessors()) {
515     if (blocks.count(bb) == 0)
516       topologicalSortImpl(blocks, bb);
517   }
518 }
519 
520 /// Sort function blocks topologically.
521 static llvm::SetVector<Block *> topologicalSort(LLVMFuncOp f) {
522   // For each blocks that has not been visited yet (i.e. that has no
523   // predecessors), add it to the list and traverse its successors in DFS
524   // preorder.
525   llvm::SetVector<Block *> blocks;
526   for (Block &b : f.getBlocks()) {
527     if (blocks.count(&b) == 0)
528       topologicalSortImpl(blocks, &b);
529   }
530   assert(blocks.size() == f.getBlocks().size() && "some blocks are not sorted");
531 
532   return blocks;
533 }
534 
535 LogicalResult ModuleTranslation::convertOneFunction(LLVMFuncOp func) {
536   // Clear the block and value mappings, they are only relevant within one
537   // function.
538   blockMapping.clear();
539   valueMapping.clear();
540   llvm::Function *llvmFunc = functionMapping.lookup(func.getName());
541 
542   // Translate the debug information for this function.
543   debugTranslation->translate(func, *llvmFunc);
544 
545   // Add function arguments to the value remapping table.
546   // If there was noalias info then we decorate each argument accordingly.
547   unsigned int argIdx = 0;
548   for (auto kvp : llvm::zip(func.getArguments(), llvmFunc->args())) {
549     llvm::Argument &llvmArg = std::get<1>(kvp);
550     BlockArgument mlirArg = std::get<0>(kvp);
551 
552     if (auto attr = func.getArgAttrOfType<BoolAttr>(argIdx, "llvm.noalias")) {
553       // NB: Attribute already verified to be boolean, so check if we can indeed
554       // attach the attribute to this argument, based on its type.
555       auto argTy = mlirArg.getType().dyn_cast<LLVM::LLVMType>();
556       if (!argTy.getUnderlyingType()->isPointerTy())
557         return func.emitError(
558             "llvm.noalias attribute attached to LLVM non-pointer argument");
559       if (attr.getValue())
560         llvmArg.addAttr(llvm::Attribute::AttrKind::NoAlias);
561     }
562     valueMapping[mlirArg] = &llvmArg;
563     argIdx++;
564   }
565 
566   // First, create all blocks so we can jump to them.
567   llvm::LLVMContext &llvmContext = llvmFunc->getContext();
568   for (auto &bb : func) {
569     auto *llvmBB = llvm::BasicBlock::Create(llvmContext);
570     llvmBB->insertInto(llvmFunc);
571     blockMapping[&bb] = llvmBB;
572   }
573 
574   // Then, convert blocks one by one in topological order to ensure defs are
575   // converted before uses.
576   auto blocks = topologicalSort(func);
577   for (auto indexedBB : llvm::enumerate(blocks)) {
578     auto *bb = indexedBB.value();
579     if (failed(convertBlock(*bb, /*ignoreArguments=*/indexedBB.index() == 0)))
580       return failure();
581   }
582 
583   // Finally, after all blocks have been traversed and values mapped, connect
584   // the PHI nodes to the results of preceding blocks.
585   connectPHINodes(func);
586   return success();
587 }
588 
589 LogicalResult ModuleTranslation::checkSupportedModuleOps(Operation *m) {
590   for (Operation &o : getModuleBody(m).getOperations())
591     if (!isa<LLVM::LLVMFuncOp>(&o) && !isa<LLVM::GlobalOp>(&o) &&
592         !o.isKnownTerminator())
593       return o.emitOpError("unsupported module-level operation");
594   return success();
595 }
596 
597 LogicalResult ModuleTranslation::convertFunctions() {
598   // Declare all functions first because there may be function calls that form a
599   // call graph with cycles.
600   for (auto function : getModuleBody(mlirModule).getOps<LLVMFuncOp>()) {
601     llvm::FunctionCallee llvmFuncCst = llvmModule->getOrInsertFunction(
602         function.getName(),
603         cast<llvm::FunctionType>(function.getType().getUnderlyingType()));
604     assert(isa<llvm::Function>(llvmFuncCst.getCallee()));
605     functionMapping[function.getName()] =
606         cast<llvm::Function>(llvmFuncCst.getCallee());
607   }
608 
609   // Convert functions.
610   for (auto function : getModuleBody(mlirModule).getOps<LLVMFuncOp>()) {
611     // Ignore external functions.
612     if (function.isExternal())
613       continue;
614 
615     if (failed(convertOneFunction(function)))
616       return failure();
617   }
618 
619   return success();
620 }
621 
622 /// A helper to look up remapped operands in the value remapping table.`
623 SmallVector<llvm::Value *, 8>
624 ModuleTranslation::lookupValues(ValueRange values) {
625   SmallVector<llvm::Value *, 8> remapped;
626   remapped.reserve(values.size());
627   for (Value v : values)
628     remapped.push_back(valueMapping.lookup(v));
629   return remapped;
630 }
631 
632 std::unique_ptr<llvm::Module>
633 ModuleTranslation::prepareLLVMModule(Operation *m) {
634   auto *dialect = m->getContext()->getRegisteredDialect<LLVM::LLVMDialect>();
635   assert(dialect && "LLVM dialect must be registered");
636 
637   auto llvmModule = llvm::CloneModule(dialect->getLLVMModule());
638   if (!llvmModule)
639     return nullptr;
640 
641   llvm::LLVMContext &llvmContext = llvmModule->getContext();
642   llvm::IRBuilder<> builder(llvmContext);
643 
644   // Inject declarations for `malloc` and `free` functions that can be used in
645   // memref allocation/deallocation coming from standard ops lowering.
646   llvmModule->getOrInsertFunction("malloc", builder.getInt8PtrTy(),
647                                   builder.getInt64Ty());
648   llvmModule->getOrInsertFunction("free", builder.getVoidTy(),
649                                   builder.getInt8PtrTy());
650 
651   return llvmModule;
652 }
653