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