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