1 //===- ConvertFromLLVMIR.cpp - MLIR to LLVM IR 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 a translation between LLVM IR and the MLIR LLVM dialect.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "mlir/Dialect/LLVMIR/LLVMDialect.h"
14 #include "mlir/IR/Builders.h"
15 #include "mlir/IR/MLIRContext.h"
16 #include "mlir/IR/Module.h"
17 #include "mlir/IR/StandardTypes.h"
18 #include "mlir/Target/LLVMIR.h"
19 #include "mlir/Translation.h"
20 
21 #include "llvm/IR/Attributes.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/Type.h"
26 #include "llvm/IRReader/IRReader.h"
27 #include "llvm/Support/Error.h"
28 #include "llvm/Support/SourceMgr.h"
29 
30 using namespace mlir;
31 using namespace mlir::LLVM;
32 
33 #include "mlir/Dialect/LLVMIR/LLVMConversionEnumsFromLLVM.inc"
34 
35 // Utility to print an LLVM value as a string for passing to emitError().
36 // FIXME: Diagnostic should be able to natively handle types that have
37 // operator << (raw_ostream&) defined.
38 static std::string diag(llvm::Value &v) {
39   std::string s;
40   llvm::raw_string_ostream os(s);
41   os << v;
42   return os.str();
43 }
44 
45 // Handles importing globals and functions from an LLVM module.
46 namespace {
47 class Importer {
48 public:
49   Importer(MLIRContext *context, ModuleOp module)
50       : b(context), context(context), module(module),
51         unknownLoc(FileLineColLoc::get("imported-bitcode", 0, 0, context)) {
52     b.setInsertionPointToStart(module.getBody());
53     dialect = context->getRegisteredDialect<LLVMDialect>();
54   }
55 
56   /// Imports `f` into the current module.
57   LogicalResult processFunction(llvm::Function *f);
58 
59   /// Imports GV as a GlobalOp, creating it if it doesn't exist.
60   GlobalOp processGlobal(llvm::GlobalVariable *GV);
61 
62 private:
63   /// Imports `bb` into `block`, which must be initially empty.
64   LogicalResult processBasicBlock(llvm::BasicBlock *bb, Block *block);
65   /// Imports `inst` and populates instMap[inst] with the imported Value.
66   LogicalResult processInstruction(llvm::Instruction *inst);
67   /// Creates an LLVMType for `type`.
68   LLVMType processType(llvm::Type *type);
69   /// `value` is an SSA-use. Return the remapped version of `value` or a
70   /// placeholder that will be remapped later if this is an instruction that
71   /// has not yet been visited.
72   Value processValue(llvm::Value *value);
73   /// Create the most accurate Location possible using a llvm::DebugLoc and
74   /// possibly an llvm::Instruction to narrow the Location if debug information
75   /// is unavailable.
76   Location processDebugLoc(const llvm::DebugLoc &loc,
77                            llvm::Instruction *inst = nullptr);
78   /// `br` branches to `target`. Append the block arguments to attach to the
79   /// generated branch op to `blockArguments`. These should be in the same order
80   /// as the PHIs in `target`.
81   LogicalResult processBranchArgs(llvm::Instruction *br,
82                                   llvm::BasicBlock *target,
83                                   SmallVectorImpl<Value> &blockArguments);
84   /// Returns the standard type equivalent to be used in attributes for the
85   /// given LLVM IR dialect type.
86   Type getStdTypeForAttr(LLVMType type);
87   /// Return `value` as an attribute to attach to a GlobalOp.
88   Attribute getConstantAsAttr(llvm::Constant *value);
89   /// Return `c` as an MLIR Value. This could either be a ConstantOp, or
90   /// an expanded sequence of ops in the current function's entry block (for
91   /// ConstantExprs or ConstantGEPs).
92   Value processConstant(llvm::Constant *c);
93 
94   /// The current builder, pointing at where the next Instruction should be
95   /// generated.
96   OpBuilder b;
97   /// The current context.
98   MLIRContext *context;
99   /// The current module being created.
100   ModuleOp module;
101   /// The entry block of the current function being processed.
102   Block *currentEntryBlock;
103 
104   /// Globals are inserted before the first function, if any.
105   Block::iterator getGlobalInsertPt() {
106     auto i = module.getBody()->begin();
107     while (!isa<LLVMFuncOp>(i) && !isa<ModuleTerminatorOp>(i))
108       ++i;
109     return i;
110   }
111 
112   /// Functions are always inserted before the module terminator.
113   Block::iterator getFuncInsertPt() {
114     return std::prev(module.getBody()->end());
115   }
116 
117   /// Remapped blocks, for the current function.
118   DenseMap<llvm::BasicBlock *, Block *> blocks;
119   /// Remapped values. These are function-local.
120   DenseMap<llvm::Value *, Value> instMap;
121   /// Instructions that had not been defined when first encountered as a use.
122   /// Maps to the dummy Operation that was created in processValue().
123   DenseMap<llvm::Value *, Operation *> unknownInstMap;
124   /// Uniquing map of GlobalVariables.
125   DenseMap<llvm::GlobalVariable *, GlobalOp> globals;
126   /// Cached FileLineColLoc::get("imported-bitcode", 0, 0).
127   Location unknownLoc;
128   /// Cached dialect.
129   LLVMDialect *dialect;
130 };
131 } // namespace
132 
133 Location Importer::processDebugLoc(const llvm::DebugLoc &loc,
134                                    llvm::Instruction *inst) {
135   if (!loc && inst) {
136     std::string s;
137     llvm::raw_string_ostream os(s);
138     os << "llvm-imported-inst-%";
139     inst->printAsOperand(os, /*PrintType=*/false);
140     return FileLineColLoc::get(os.str(), 0, 0, context);
141   } else if (!loc) {
142     return unknownLoc;
143   }
144   // FIXME: Obtain the filename from DILocationInfo.
145   return FileLineColLoc::get("imported-bitcode", loc.getLine(), loc.getCol(),
146                              context);
147 }
148 
149 LLVMType Importer::processType(llvm::Type *type) {
150   switch (type->getTypeID()) {
151   case llvm::Type::FloatTyID:
152     return LLVMType::getFloatTy(dialect);
153   case llvm::Type::DoubleTyID:
154     return LLVMType::getDoubleTy(dialect);
155   case llvm::Type::IntegerTyID:
156     return LLVMType::getIntNTy(dialect, type->getIntegerBitWidth());
157   case llvm::Type::PointerTyID: {
158     LLVMType elementType = processType(type->getPointerElementType());
159     if (!elementType)
160       return nullptr;
161     return elementType.getPointerTo(type->getPointerAddressSpace());
162   }
163   case llvm::Type::ArrayTyID: {
164     LLVMType elementType = processType(type->getArrayElementType());
165     if (!elementType)
166       return nullptr;
167     return LLVMType::getArrayTy(elementType, type->getArrayNumElements());
168   }
169   case llvm::Type::VectorTyID: {
170     if (type->getVectorIsScalable()) {
171       emitError(unknownLoc) << "scalable vector types not supported";
172       return nullptr;
173     }
174     LLVMType elementType = processType(type->getVectorElementType());
175     if (!elementType)
176       return nullptr;
177     return LLVMType::getVectorTy(elementType, type->getVectorNumElements());
178   }
179   case llvm::Type::VoidTyID:
180     return LLVMType::getVoidTy(dialect);
181   case llvm::Type::FP128TyID:
182     return LLVMType::getFP128Ty(dialect);
183   case llvm::Type::X86_FP80TyID:
184     return LLVMType::getX86_FP80Ty(dialect);
185   case llvm::Type::StructTyID: {
186     SmallVector<LLVMType, 4> elementTypes;
187     elementTypes.reserve(type->getStructNumElements());
188     for (unsigned i = 0, e = type->getStructNumElements(); i != e; ++i) {
189       LLVMType ty = processType(type->getStructElementType(i));
190       if (!ty)
191         return nullptr;
192       elementTypes.push_back(ty);
193     }
194     return LLVMType::getStructTy(dialect, elementTypes,
195                                  cast<llvm::StructType>(type)->isPacked());
196   }
197   case llvm::Type::FunctionTyID: {
198     llvm::FunctionType *fty = cast<llvm::FunctionType>(type);
199     SmallVector<LLVMType, 4> paramTypes;
200     for (unsigned i = 0, e = fty->getNumParams(); i != e; ++i) {
201       LLVMType ty = processType(fty->getParamType(i));
202       if (!ty)
203         return nullptr;
204       paramTypes.push_back(ty);
205     }
206     LLVMType result = processType(fty->getReturnType());
207     if (!result)
208       return nullptr;
209 
210     return LLVMType::getFunctionTy(result, paramTypes, fty->isVarArg());
211   }
212   default: {
213     // FIXME: Diagnostic should be able to natively handle types that have
214     // operator<<(raw_ostream&) defined.
215     std::string s;
216     llvm::raw_string_ostream os(s);
217     os << *type;
218     emitError(unknownLoc) << "unhandled type: " << os.str();
219     return nullptr;
220   }
221   }
222 }
223 
224 // We only need integers, floats, doubles, and vectors and tensors thereof for
225 // attributes. Scalar and vector types are converted to the standard
226 // equivalents. Array types are converted to ranked tensors; nested array types
227 // are converted to multi-dimensional tensors or vectors, depending on the
228 // innermost type being a scalar or a vector.
229 Type Importer::getStdTypeForAttr(LLVMType type) {
230   if (!type)
231     return nullptr;
232 
233   if (type.isIntegerTy())
234     return b.getIntegerType(type.getUnderlyingType()->getIntegerBitWidth());
235 
236   if (type.getUnderlyingType()->isFloatTy())
237     return b.getF32Type();
238 
239   if (type.getUnderlyingType()->isDoubleTy())
240     return b.getF64Type();
241 
242   // LLVM vectors can only contain scalars.
243   if (type.isVectorTy()) {
244     auto numElements = type.getUnderlyingType()->getVectorElementCount();
245     if (numElements.Scalable) {
246       emitError(unknownLoc) << "scalable vectors not supported";
247       return nullptr;
248     }
249     Type elementType = getStdTypeForAttr(type.getVectorElementType());
250     if (!elementType)
251       return nullptr;
252     return VectorType::get(numElements.Min, elementType);
253   }
254 
255   // LLVM arrays can contain other arrays or vectors.
256   if (type.isArrayTy()) {
257     // Recover the nested array shape.
258     SmallVector<int64_t, 4> shape;
259     shape.push_back(type.getArrayNumElements());
260     while (type.getArrayElementType().isArrayTy()) {
261       type = type.getArrayElementType();
262       shape.push_back(type.getArrayNumElements());
263     }
264 
265     // If the innermost type is a vector, use the multi-dimensional vector as
266     // attribute type.
267     if (type.getArrayElementType().isVectorTy()) {
268       LLVMType vectorType = type.getArrayElementType();
269       auto numElements =
270           vectorType.getUnderlyingType()->getVectorElementCount();
271       if (numElements.Scalable) {
272         emitError(unknownLoc) << "scalable vectors not supported";
273         return nullptr;
274       }
275       shape.push_back(numElements.Min);
276 
277       Type elementType = getStdTypeForAttr(vectorType.getVectorElementType());
278       if (!elementType)
279         return nullptr;
280       return VectorType::get(shape, elementType);
281     }
282 
283     // Otherwise use a tensor.
284     Type elementType = getStdTypeForAttr(type.getArrayElementType());
285     if (!elementType)
286       return nullptr;
287     return RankedTensorType::get(shape, elementType);
288   }
289 
290   return nullptr;
291 }
292 
293 // Get the given constant as an attribute. Not all constants can be represented
294 // as attributes.
295 Attribute Importer::getConstantAsAttr(llvm::Constant *value) {
296   if (auto *ci = dyn_cast<llvm::ConstantInt>(value))
297     return b.getIntegerAttr(
298         IntegerType::get(ci->getType()->getBitWidth(), context),
299         ci->getValue());
300   if (auto *c = dyn_cast<llvm::ConstantDataArray>(value))
301     if (c->isString())
302       return b.getStringAttr(c->getAsString());
303   if (auto *c = dyn_cast<llvm::ConstantFP>(value)) {
304     if (c->getType()->isDoubleTy())
305       return b.getFloatAttr(FloatType::getF64(context), c->getValueAPF());
306     else if (c->getType()->isFloatingPointTy())
307       return b.getFloatAttr(FloatType::getF32(context), c->getValueAPF());
308   }
309   if (auto *f = dyn_cast<llvm::Function>(value))
310     return b.getSymbolRefAttr(f->getName());
311 
312   // Convert constant data to a dense elements attribute.
313   if (auto *cd = dyn_cast<llvm::ConstantDataSequential>(value)) {
314     LLVMType type = processType(cd->getElementType());
315     if (!type)
316       return nullptr;
317 
318     auto attrType = getStdTypeForAttr(processType(cd->getType()))
319                         .dyn_cast_or_null<ShapedType>();
320     if (!attrType)
321       return nullptr;
322 
323     if (type.isIntegerTy()) {
324       SmallVector<APInt, 8> values;
325       values.reserve(cd->getNumElements());
326       for (unsigned i = 0, e = cd->getNumElements(); i < e; ++i)
327         values.push_back(cd->getElementAsAPInt(i));
328       return DenseElementsAttr::get(attrType, values);
329     }
330 
331     if (type.isFloatTy() || type.isDoubleTy()) {
332       SmallVector<APFloat, 8> values;
333       values.reserve(cd->getNumElements());
334       for (unsigned i = 0, e = cd->getNumElements(); i < e; ++i)
335         values.push_back(cd->getElementAsAPFloat(i));
336       return DenseElementsAttr::get(attrType, values);
337     }
338 
339     return nullptr;
340   }
341 
342   // Unpack constant aggregates to create dense elements attribute whenever
343   // possible. Return nullptr (failure) otherwise.
344   if (isa<llvm::ConstantAggregate>(value)) {
345     auto outerType = getStdTypeForAttr(processType(value->getType()))
346                          .dyn_cast_or_null<ShapedType>();
347     if (!outerType)
348       return nullptr;
349 
350     SmallVector<Attribute, 8> values;
351     SmallVector<int64_t, 8> shape;
352 
353     for (unsigned i = 0, e = value->getNumOperands(); i < e; ++i) {
354       auto nested = getConstantAsAttr(value->getAggregateElement(i))
355                         .dyn_cast_or_null<DenseElementsAttr>();
356       if (!nested)
357         return nullptr;
358 
359       values.append(nested.attr_value_begin(), nested.attr_value_end());
360     }
361 
362     return DenseElementsAttr::get(outerType, values);
363   }
364 
365   return nullptr;
366 }
367 
368 GlobalOp Importer::processGlobal(llvm::GlobalVariable *GV) {
369   auto it = globals.find(GV);
370   if (it != globals.end())
371     return it->second;
372 
373   OpBuilder b(module.getBody(), getGlobalInsertPt());
374   Attribute valueAttr;
375   if (GV->hasInitializer())
376     valueAttr = getConstantAsAttr(GV->getInitializer());
377   LLVMType type = processType(GV->getValueType());
378   if (!type)
379     return nullptr;
380   GlobalOp op = b.create<GlobalOp>(
381       UnknownLoc::get(context), type, GV->isConstant(),
382       convertLinkageFromLLVM(GV->getLinkage()), GV->getName(), valueAttr);
383   if (GV->hasInitializer() && !valueAttr) {
384     Region &r = op.getInitializerRegion();
385     currentEntryBlock = b.createBlock(&r);
386     b.setInsertionPoint(currentEntryBlock, currentEntryBlock->begin());
387     Value v = processConstant(GV->getInitializer());
388     if (!v)
389       return nullptr;
390     b.create<ReturnOp>(op.getLoc(), ArrayRef<Value>({v}));
391   }
392   return globals[GV] = op;
393 }
394 
395 Value Importer::processConstant(llvm::Constant *c) {
396   OpBuilder bEntry(currentEntryBlock, currentEntryBlock->begin());
397   if (Attribute attr = getConstantAsAttr(c)) {
398     // These constants can be represented as attributes.
399     OpBuilder b(currentEntryBlock, currentEntryBlock->begin());
400     LLVMType type = processType(c->getType());
401     if (!type)
402       return nullptr;
403     return instMap[c] = bEntry.create<ConstantOp>(unknownLoc, type, attr);
404   }
405   if (auto *cn = dyn_cast<llvm::ConstantPointerNull>(c)) {
406     LLVMType type = processType(cn->getType());
407     if (!type)
408       return nullptr;
409     return instMap[c] = bEntry.create<NullOp>(unknownLoc, type);
410   }
411   if (auto *GV = dyn_cast<llvm::GlobalVariable>(c))
412     return bEntry.create<AddressOfOp>(UnknownLoc::get(context),
413                                       processGlobal(GV),
414                                       ArrayRef<NamedAttribute>());
415 
416   if (auto *ce = dyn_cast<llvm::ConstantExpr>(c)) {
417     llvm::Instruction *i = ce->getAsInstruction();
418     OpBuilder::InsertionGuard guard(b);
419     b.setInsertionPoint(currentEntryBlock, currentEntryBlock->begin());
420     if (failed(processInstruction(i)))
421       return nullptr;
422     assert(instMap.count(i));
423 
424     // Remove this zombie LLVM instruction now, leaving us only with the MLIR
425     // op.
426     i->deleteValue();
427     return instMap[c] = instMap[i];
428   }
429   if (auto *ue = dyn_cast<llvm::UndefValue>(c)) {
430     LLVMType type = processType(ue->getType());
431     if (!type)
432       return nullptr;
433     return instMap[c] = bEntry.create<UndefOp>(UnknownLoc::get(context), type);
434   }
435   emitError(unknownLoc) << "unhandled constant: " << diag(*c);
436   return nullptr;
437 }
438 
439 Value Importer::processValue(llvm::Value *value) {
440   auto it = instMap.find(value);
441   if (it != instMap.end())
442     return it->second;
443 
444   // We don't expect to see instructions in dominator order. If we haven't seen
445   // this instruction yet, create an unknown op and remap it later.
446   if (isa<llvm::Instruction>(value)) {
447     OperationState state(UnknownLoc::get(context), "unknown");
448     LLVMType type = processType(value->getType());
449     if (!type)
450       return nullptr;
451     state.addTypes(type);
452     unknownInstMap[value] = b.createOperation(state);
453     return unknownInstMap[value]->getResult(0);
454   }
455 
456   if (auto *c = dyn_cast<llvm::Constant>(value))
457     return processConstant(c);
458 
459   emitError(unknownLoc) << "unhandled value: " << diag(*value);
460   return nullptr;
461 }
462 
463 // Maps from LLVM opcode to MLIR OperationName. This is deliberately ordered
464 // as in llvm/IR/Instructions.def to aid comprehension and spot missing
465 // instructions.
466 #define INST(llvm_n, mlir_n)                                                   \
467   { llvm::Instruction::llvm_n, LLVM::mlir_n##Op::getOperationName() }
468 static const DenseMap<unsigned, StringRef> opcMap = {
469     // Ret is handled specially.
470     // Br is handled specially.
471     // FIXME: switch
472     // FIXME: indirectbr
473     // FIXME: invoke
474     // FIXME: resume
475     // FIXME: unreachable
476     // FIXME: cleanupret
477     // FIXME: catchret
478     // FIXME: catchswitch
479     // FIXME: callbr
480     // FIXME: fneg
481     INST(Add, Add), INST(FAdd, FAdd), INST(Sub, Sub), INST(FSub, FSub),
482     INST(Mul, Mul), INST(FMul, FMul), INST(UDiv, UDiv), INST(SDiv, SDiv),
483     INST(FDiv, FDiv), INST(URem, URem), INST(SRem, SRem), INST(FRem, FRem),
484     INST(Shl, Shl), INST(LShr, LShr), INST(AShr, AShr), INST(And, And),
485     INST(Or, Or), INST(Xor, XOr), INST(Alloca, Alloca), INST(Load, Load),
486     INST(Store, Store),
487     // Getelementptr is handled specially.
488     INST(Ret, Return),
489     // FIXME: fence
490     // FIXME: atomiccmpxchg
491     // FIXME: atomicrmw
492     INST(Trunc, Trunc), INST(ZExt, ZExt), INST(SExt, SExt),
493     INST(FPToUI, FPToUI), INST(FPToSI, FPToSI), INST(UIToFP, UIToFP),
494     INST(SIToFP, SIToFP), INST(FPTrunc, FPTrunc), INST(FPExt, FPExt),
495     INST(PtrToInt, PtrToInt), INST(IntToPtr, IntToPtr), INST(BitCast, Bitcast),
496     INST(AddrSpaceCast, AddrSpaceCast),
497     // FIXME: cleanuppad
498     // FIXME: catchpad
499     // ICmp is handled specially.
500     // FIXME: fcmp
501     // PHI is handled specially.
502     INST(Freeze, Freeze), INST(Call, Call),
503     // FIXME: select
504     // FIXME: vaarg
505     // FIXME: extractelement
506     // FIXME: insertelement
507     // FIXME: shufflevector
508     // FIXME: extractvalue
509     // FIXME: insertvalue
510     // FIXME: landingpad
511 };
512 #undef INST
513 
514 static ICmpPredicate getICmpPredicate(llvm::CmpInst::Predicate p) {
515   switch (p) {
516   default:
517     llvm_unreachable("incorrect comparison predicate");
518   case llvm::CmpInst::Predicate::ICMP_EQ:
519     return LLVM::ICmpPredicate::eq;
520   case llvm::CmpInst::Predicate::ICMP_NE:
521     return LLVM::ICmpPredicate::ne;
522   case llvm::CmpInst::Predicate::ICMP_SLT:
523     return LLVM::ICmpPredicate::slt;
524   case llvm::CmpInst::Predicate::ICMP_SLE:
525     return LLVM::ICmpPredicate::sle;
526   case llvm::CmpInst::Predicate::ICMP_SGT:
527     return LLVM::ICmpPredicate::sgt;
528   case llvm::CmpInst::Predicate::ICMP_SGE:
529     return LLVM::ICmpPredicate::sge;
530   case llvm::CmpInst::Predicate::ICMP_ULT:
531     return LLVM::ICmpPredicate::ult;
532   case llvm::CmpInst::Predicate::ICMP_ULE:
533     return LLVM::ICmpPredicate::ule;
534   case llvm::CmpInst::Predicate::ICMP_UGT:
535     return LLVM::ICmpPredicate::ugt;
536   case llvm::CmpInst::Predicate::ICMP_UGE:
537     return LLVM::ICmpPredicate::uge;
538   }
539   llvm_unreachable("incorrect comparison predicate");
540 }
541 
542 // `br` branches to `target`. Return the branch arguments to `br`, in the
543 // same order of the PHIs in `target`.
544 LogicalResult
545 Importer::processBranchArgs(llvm::Instruction *br, llvm::BasicBlock *target,
546                             SmallVectorImpl<Value> &blockArguments) {
547   for (auto inst = target->begin(); isa<llvm::PHINode>(inst); ++inst) {
548     auto *PN = cast<llvm::PHINode>(&*inst);
549     Value value = processValue(PN->getIncomingValueForBlock(br->getParent()));
550     if (!value)
551       return failure();
552     blockArguments.push_back(value);
553   }
554   return success();
555 }
556 
557 LogicalResult Importer::processInstruction(llvm::Instruction *inst) {
558   // FIXME: Support uses of SubtargetData. Currently inbounds GEPs, fast-math
559   // flags and call / operand attributes are not supported.
560   Location loc = processDebugLoc(inst->getDebugLoc(), inst);
561   Value &v = instMap[inst];
562   assert(!v && "processInstruction must be called only once per instruction!");
563   switch (inst->getOpcode()) {
564   default:
565     return emitError(loc) << "unknown instruction: " << diag(*inst);
566   case llvm::Instruction::Add:
567   case llvm::Instruction::FAdd:
568   case llvm::Instruction::Sub:
569   case llvm::Instruction::FSub:
570   case llvm::Instruction::Mul:
571   case llvm::Instruction::FMul:
572   case llvm::Instruction::UDiv:
573   case llvm::Instruction::SDiv:
574   case llvm::Instruction::FDiv:
575   case llvm::Instruction::URem:
576   case llvm::Instruction::SRem:
577   case llvm::Instruction::FRem:
578   case llvm::Instruction::Shl:
579   case llvm::Instruction::LShr:
580   case llvm::Instruction::AShr:
581   case llvm::Instruction::And:
582   case llvm::Instruction::Or:
583   case llvm::Instruction::Xor:
584   case llvm::Instruction::Alloca:
585   case llvm::Instruction::Load:
586   case llvm::Instruction::Store:
587   case llvm::Instruction::Ret:
588   case llvm::Instruction::Trunc:
589   case llvm::Instruction::ZExt:
590   case llvm::Instruction::SExt:
591   case llvm::Instruction::FPToUI:
592   case llvm::Instruction::FPToSI:
593   case llvm::Instruction::UIToFP:
594   case llvm::Instruction::SIToFP:
595   case llvm::Instruction::FPTrunc:
596   case llvm::Instruction::FPExt:
597   case llvm::Instruction::PtrToInt:
598   case llvm::Instruction::IntToPtr:
599   case llvm::Instruction::AddrSpaceCast:
600   case llvm::Instruction::Freeze:
601   case llvm::Instruction::BitCast: {
602     OperationState state(loc, opcMap.lookup(inst->getOpcode()));
603     SmallVector<Value, 4> ops;
604     ops.reserve(inst->getNumOperands());
605     for (auto *op : inst->operand_values()) {
606       Value value = processValue(op);
607       if (!value)
608         return failure();
609       ops.push_back(value);
610     }
611     state.addOperands(ops);
612     if (!inst->getType()->isVoidTy()) {
613       LLVMType type = processType(inst->getType());
614       if (!type)
615         return failure();
616       state.addTypes(type);
617     }
618     Operation *op = b.createOperation(state);
619     if (!inst->getType()->isVoidTy())
620       v = op->getResult(0);
621     return success();
622   }
623   case llvm::Instruction::ICmp: {
624     Value lhs = processValue(inst->getOperand(0));
625     Value rhs = processValue(inst->getOperand(1));
626     if (!lhs || !rhs)
627       return failure();
628     v = b.create<ICmpOp>(
629         loc, getICmpPredicate(cast<llvm::ICmpInst>(inst)->getPredicate()), lhs,
630         rhs);
631     return success();
632   }
633   case llvm::Instruction::Br: {
634     auto *brInst = cast<llvm::BranchInst>(inst);
635     OperationState state(loc,
636                          brInst->isConditional() ? "llvm.cond_br" : "llvm.br");
637     SmallVector<Value, 4> ops;
638     if (brInst->isConditional()) {
639       Value condition = processValue(brInst->getCondition());
640       if (!condition)
641         return failure();
642       ops.push_back(condition);
643     }
644     state.addOperands(ops);
645     SmallVector<Block *, 4> succs;
646     for (auto *succ : llvm::reverse(brInst->successors())) {
647       SmallVector<Value, 4> blockArguments;
648       if (failed(processBranchArgs(brInst, succ, blockArguments)))
649         return failure();
650       state.addSuccessor(blocks[succ], blockArguments);
651     }
652     b.createOperation(state);
653     return success();
654   }
655   case llvm::Instruction::PHI: {
656     LLVMType type = processType(inst->getType());
657     if (!type)
658       return failure();
659     v = b.getInsertionBlock()->addArgument(type);
660     return success();
661   }
662   case llvm::Instruction::Call: {
663     llvm::CallInst *ci = cast<llvm::CallInst>(inst);
664     SmallVector<Value, 4> ops;
665     ops.reserve(inst->getNumOperands());
666     for (auto &op : ci->arg_operands()) {
667       Value arg = processValue(op.get());
668       if (!arg)
669         return failure();
670       ops.push_back(arg);
671     }
672 
673     SmallVector<Type, 2> tys;
674     if (!ci->getType()->isVoidTy()) {
675       LLVMType type = processType(inst->getType());
676       if (!type)
677         return failure();
678       tys.push_back(type);
679     }
680     Operation *op;
681     if (llvm::Function *callee = ci->getCalledFunction()) {
682       op = b.create<CallOp>(loc, tys, b.getSymbolRefAttr(callee->getName()),
683                             ops);
684     } else {
685       Value calledValue = processValue(ci->getCalledValue());
686       if (!calledValue)
687         return failure();
688       ops.insert(ops.begin(), calledValue);
689       op = b.create<CallOp>(loc, tys, ops, ArrayRef<NamedAttribute>());
690     }
691     if (!ci->getType()->isVoidTy())
692       v = op->getResult(0);
693     return success();
694   }
695   case llvm::Instruction::LandingPad: {
696     llvm::LandingPadInst *lpi = cast<llvm::LandingPadInst>(inst);
697     SmallVector<Value, 4> ops;
698 
699     for (unsigned i = 0, ie = lpi->getNumClauses(); i < ie; i++)
700       ops.push_back(processConstant(lpi->getClause(i)));
701 
702     b.create<LandingpadOp>(loc, processType(lpi->getType()), lpi->isCleanup(),
703                            ops);
704     return success();
705   }
706   case llvm::Instruction::Invoke: {
707     llvm::InvokeInst *ii = cast<llvm::InvokeInst>(inst);
708 
709     SmallVector<Type, 2> tys;
710     if (!ii->getType()->isVoidTy())
711       tys.push_back(processType(inst->getType()));
712 
713     SmallVector<Value, 4> ops;
714     ops.reserve(inst->getNumOperands() + 1);
715     for (auto &op : ii->arg_operands())
716       ops.push_back(processValue(op.get()));
717 
718     SmallVector<Value, 4> normalArgs, unwindArgs;
719     processBranchArgs(ii, ii->getNormalDest(), normalArgs);
720     processBranchArgs(ii, ii->getUnwindDest(), unwindArgs);
721 
722     Operation *op;
723     if (llvm::Function *callee = ii->getCalledFunction()) {
724       op = b.create<InvokeOp>(loc, tys, b.getSymbolRefAttr(callee->getName()),
725                               ops, blocks[ii->getNormalDest()], normalArgs,
726                               blocks[ii->getUnwindDest()], unwindArgs);
727     } else {
728       ops.insert(ops.begin(), processValue(ii->getCalledValue()));
729       op = b.create<InvokeOp>(loc, tys, ops, blocks[ii->getNormalDest()],
730                               normalArgs, blocks[ii->getUnwindDest()],
731                               unwindArgs);
732     }
733 
734     if (!ii->getType()->isVoidTy())
735       v = op->getResult(0);
736     return success();
737   }
738   case llvm::Instruction::GetElementPtr: {
739     // FIXME: Support inbounds GEPs.
740     llvm::GetElementPtrInst *gep = cast<llvm::GetElementPtrInst>(inst);
741     SmallVector<Value, 4> ops;
742     for (auto *op : gep->operand_values()) {
743       Value value = processValue(op);
744       if (!value)
745         return failure();
746       ops.push_back(value);
747     }
748     Type type = processType(inst->getType());
749     if (!type)
750       return failure();
751     v = b.create<GEPOp>(loc, type, ops, ArrayRef<NamedAttribute>());
752     return success();
753   }
754   }
755 }
756 
757 LogicalResult Importer::processFunction(llvm::Function *f) {
758   blocks.clear();
759   instMap.clear();
760   unknownInstMap.clear();
761 
762   LLVMType functionType = processType(f->getFunctionType());
763   if (!functionType)
764     return failure();
765 
766   b.setInsertionPoint(module.getBody(), getFuncInsertPt());
767   LLVMFuncOp fop = b.create<LLVMFuncOp>(UnknownLoc::get(context), f->getName(),
768                                         functionType);
769   if (f->isDeclaration())
770     return success();
771 
772   // Eagerly create all blocks.
773   SmallVector<Block *, 4> blockList;
774   for (llvm::BasicBlock &bb : *f) {
775     blockList.push_back(b.createBlock(&fop.body(), fop.body().end()));
776     blocks[&bb] = blockList.back();
777   }
778   currentEntryBlock = blockList[0];
779 
780   // Add function arguments to the entry block.
781   for (auto kv : llvm::enumerate(f->args()))
782     instMap[&kv.value()] = blockList[0]->addArgument(
783         functionType.getFunctionParamType(kv.index()));
784 
785   for (auto bbs : llvm::zip(*f, blockList)) {
786     if (failed(processBasicBlock(&std::get<0>(bbs), std::get<1>(bbs))))
787       return failure();
788   }
789 
790   // Now that all instructions are guaranteed to have been visited, ensure
791   // any unknown uses we encountered are remapped.
792   for (auto &llvmAndUnknown : unknownInstMap) {
793     assert(instMap.count(llvmAndUnknown.first));
794     Value newValue = instMap[llvmAndUnknown.first];
795     Value oldValue = llvmAndUnknown.second->getResult(0);
796     oldValue.replaceAllUsesWith(newValue);
797     llvmAndUnknown.second->erase();
798   }
799   return success();
800 }
801 
802 LogicalResult Importer::processBasicBlock(llvm::BasicBlock *bb, Block *block) {
803   b.setInsertionPointToStart(block);
804   for (llvm::Instruction &inst : *bb) {
805     if (failed(processInstruction(&inst)))
806       return failure();
807   }
808   return success();
809 }
810 
811 OwningModuleRef
812 mlir::translateLLVMIRToModule(std::unique_ptr<llvm::Module> llvmModule,
813                               MLIRContext *context) {
814   OwningModuleRef module(ModuleOp::create(
815       FileLineColLoc::get("", /*line=*/0, /*column=*/0, context)));
816 
817   Importer deserializer(context, module.get());
818   for (llvm::GlobalVariable &gv : llvmModule->globals()) {
819     if (!deserializer.processGlobal(&gv))
820       return {};
821   }
822   for (llvm::Function &f : llvmModule->functions()) {
823     if (failed(deserializer.processFunction(&f)))
824       return {};
825   }
826 
827   return module;
828 }
829 
830 // Deserializes the LLVM bitcode stored in `input` into an MLIR module in the
831 // LLVM dialect.
832 OwningModuleRef translateLLVMIRToModule(llvm::SourceMgr &sourceMgr,
833                                         MLIRContext *context) {
834   LLVMDialect *dialect = context->getRegisteredDialect<LLVMDialect>();
835   assert(dialect && "Could not find LLVMDialect?");
836 
837   llvm::SMDiagnostic err;
838   std::unique_ptr<llvm::Module> llvmModule =
839       llvm::parseIR(*sourceMgr.getMemoryBuffer(sourceMgr.getMainFileID()), err,
840                     dialect->getLLVMContext(),
841                     /*UpgradeDebugInfo=*/true,
842                     /*DataLayoutString=*/"");
843   if (!llvmModule) {
844     std::string errStr;
845     llvm::raw_string_ostream errStream(errStr);
846     err.print(/*ProgName=*/"", errStream);
847     emitError(UnknownLoc::get(context)) << errStream.str();
848     return {};
849   }
850   return translateLLVMIRToModule(std::move(llvmModule), context);
851 }
852 
853 static TranslateToMLIRRegistration
854     fromLLVM("import-llvm",
855              [](llvm::SourceMgr &sourceMgr, MLIRContext *context) {
856                return translateLLVMIRToModule(sourceMgr, context);
857              });
858