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