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