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