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