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