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     if (brInst->isConditional()) {
638       Value condition = processValue(brInst->getCondition());
639       if (!condition)
640         return failure();
641       state.addOperands(condition);
642     }
643 
644     std::array<int32_t, 3> operandSegmentSizes = {1, 0, 0};
645     for (int i : llvm::seq<int>(0, brInst->getNumSuccessors())) {
646       auto *succ = brInst->getSuccessor(i);
647       SmallVector<Value, 4> blockArguments;
648       if (failed(processBranchArgs(brInst, succ, blockArguments)))
649         return failure();
650       state.addSuccessors(blocks[succ]);
651       state.addOperands(blockArguments);
652       operandSegmentSizes[i + 1] = blockArguments.size();
653     }
654 
655     if (brInst->isConditional()) {
656       state.addAttribute(LLVM::CondBrOp::getOperandSegmentSizeAttr(),
657                          b.getI32VectorAttr(operandSegmentSizes));
658     }
659 
660     b.createOperation(state);
661     return success();
662   }
663   case llvm::Instruction::PHI: {
664     LLVMType type = processType(inst->getType());
665     if (!type)
666       return failure();
667     v = b.getInsertionBlock()->addArgument(type);
668     return success();
669   }
670   case llvm::Instruction::Call: {
671     llvm::CallInst *ci = cast<llvm::CallInst>(inst);
672     SmallVector<Value, 4> ops;
673     ops.reserve(inst->getNumOperands());
674     for (auto &op : ci->arg_operands()) {
675       Value arg = processValue(op.get());
676       if (!arg)
677         return failure();
678       ops.push_back(arg);
679     }
680 
681     SmallVector<Type, 2> tys;
682     if (!ci->getType()->isVoidTy()) {
683       LLVMType type = processType(inst->getType());
684       if (!type)
685         return failure();
686       tys.push_back(type);
687     }
688     Operation *op;
689     if (llvm::Function *callee = ci->getCalledFunction()) {
690       op = b.create<CallOp>(loc, tys, b.getSymbolRefAttr(callee->getName()),
691                             ops);
692     } else {
693       Value calledValue = processValue(ci->getCalledValue());
694       if (!calledValue)
695         return failure();
696       ops.insert(ops.begin(), calledValue);
697       op = b.create<CallOp>(loc, tys, ops, ArrayRef<NamedAttribute>());
698     }
699     if (!ci->getType()->isVoidTy())
700       v = op->getResult(0);
701     return success();
702   }
703   case llvm::Instruction::LandingPad: {
704     llvm::LandingPadInst *lpi = cast<llvm::LandingPadInst>(inst);
705     SmallVector<Value, 4> ops;
706 
707     for (unsigned i = 0, ie = lpi->getNumClauses(); i < ie; i++)
708       ops.push_back(processConstant(lpi->getClause(i)));
709 
710     b.create<LandingpadOp>(loc, processType(lpi->getType()), lpi->isCleanup(),
711                            ops);
712     return success();
713   }
714   case llvm::Instruction::Invoke: {
715     llvm::InvokeInst *ii = cast<llvm::InvokeInst>(inst);
716 
717     SmallVector<Type, 2> tys;
718     if (!ii->getType()->isVoidTy())
719       tys.push_back(processType(inst->getType()));
720 
721     SmallVector<Value, 4> ops;
722     ops.reserve(inst->getNumOperands() + 1);
723     for (auto &op : ii->arg_operands())
724       ops.push_back(processValue(op.get()));
725 
726     SmallVector<Value, 4> normalArgs, unwindArgs;
727     processBranchArgs(ii, ii->getNormalDest(), normalArgs);
728     processBranchArgs(ii, ii->getUnwindDest(), unwindArgs);
729 
730     Operation *op;
731     if (llvm::Function *callee = ii->getCalledFunction()) {
732       op = b.create<InvokeOp>(loc, tys, b.getSymbolRefAttr(callee->getName()),
733                               ops, blocks[ii->getNormalDest()], normalArgs,
734                               blocks[ii->getUnwindDest()], unwindArgs);
735     } else {
736       ops.insert(ops.begin(), processValue(ii->getCalledValue()));
737       op = b.create<InvokeOp>(loc, tys, ops, blocks[ii->getNormalDest()],
738                               normalArgs, blocks[ii->getUnwindDest()],
739                               unwindArgs);
740     }
741 
742     if (!ii->getType()->isVoidTy())
743       v = op->getResult(0);
744     return success();
745   }
746   case llvm::Instruction::GetElementPtr: {
747     // FIXME: Support inbounds GEPs.
748     llvm::GetElementPtrInst *gep = cast<llvm::GetElementPtrInst>(inst);
749     SmallVector<Value, 4> ops;
750     for (auto *op : gep->operand_values()) {
751       Value value = processValue(op);
752       if (!value)
753         return failure();
754       ops.push_back(value);
755     }
756     Type type = processType(inst->getType());
757     if (!type)
758       return failure();
759     v = b.create<GEPOp>(loc, type, ops, ArrayRef<NamedAttribute>());
760     return success();
761   }
762   }
763 }
764 
765 LogicalResult Importer::processFunction(llvm::Function *f) {
766   blocks.clear();
767   instMap.clear();
768   unknownInstMap.clear();
769 
770   LLVMType functionType = processType(f->getFunctionType());
771   if (!functionType)
772     return failure();
773 
774   b.setInsertionPoint(module.getBody(), getFuncInsertPt());
775   LLVMFuncOp fop = b.create<LLVMFuncOp>(UnknownLoc::get(context), f->getName(),
776                                         functionType);
777   if (f->isDeclaration())
778     return success();
779 
780   // Eagerly create all blocks.
781   SmallVector<Block *, 4> blockList;
782   for (llvm::BasicBlock &bb : *f) {
783     blockList.push_back(b.createBlock(&fop.body(), fop.body().end()));
784     blocks[&bb] = blockList.back();
785   }
786   currentEntryBlock = blockList[0];
787 
788   // Add function arguments to the entry block.
789   for (auto kv : llvm::enumerate(f->args()))
790     instMap[&kv.value()] = blockList[0]->addArgument(
791         functionType.getFunctionParamType(kv.index()));
792 
793   for (auto bbs : llvm::zip(*f, blockList)) {
794     if (failed(processBasicBlock(&std::get<0>(bbs), std::get<1>(bbs))))
795       return failure();
796   }
797 
798   // Now that all instructions are guaranteed to have been visited, ensure
799   // any unknown uses we encountered are remapped.
800   for (auto &llvmAndUnknown : unknownInstMap) {
801     assert(instMap.count(llvmAndUnknown.first));
802     Value newValue = instMap[llvmAndUnknown.first];
803     Value oldValue = llvmAndUnknown.second->getResult(0);
804     oldValue.replaceAllUsesWith(newValue);
805     llvmAndUnknown.second->erase();
806   }
807   return success();
808 }
809 
810 LogicalResult Importer::processBasicBlock(llvm::BasicBlock *bb, Block *block) {
811   b.setInsertionPointToStart(block);
812   for (llvm::Instruction &inst : *bb) {
813     if (failed(processInstruction(&inst)))
814       return failure();
815   }
816   return success();
817 }
818 
819 OwningModuleRef
820 mlir::translateLLVMIRToModule(std::unique_ptr<llvm::Module> llvmModule,
821                               MLIRContext *context) {
822   OwningModuleRef module(ModuleOp::create(
823       FileLineColLoc::get("", /*line=*/0, /*column=*/0, context)));
824 
825   Importer deserializer(context, module.get());
826   for (llvm::GlobalVariable &gv : llvmModule->globals()) {
827     if (!deserializer.processGlobal(&gv))
828       return {};
829   }
830   for (llvm::Function &f : llvmModule->functions()) {
831     if (failed(deserializer.processFunction(&f)))
832       return {};
833   }
834 
835   return module;
836 }
837 
838 // Deserializes the LLVM bitcode stored in `input` into an MLIR module in the
839 // LLVM dialect.
840 OwningModuleRef translateLLVMIRToModule(llvm::SourceMgr &sourceMgr,
841                                         MLIRContext *context) {
842   LLVMDialect *dialect = context->getRegisteredDialect<LLVMDialect>();
843   assert(dialect && "Could not find LLVMDialect?");
844 
845   llvm::SMDiagnostic err;
846   std::unique_ptr<llvm::Module> llvmModule =
847       llvm::parseIR(*sourceMgr.getMemoryBuffer(sourceMgr.getMainFileID()), err,
848                     dialect->getLLVMContext(),
849                     /*UpgradeDebugInfo=*/true,
850                     /*DataLayoutString=*/"");
851   if (!llvmModule) {
852     std::string errStr;
853     llvm::raw_string_ostream errStream(errStr);
854     err.print(/*ProgName=*/"", errStream);
855     emitError(UnknownLoc::get(context)) << errStream.str();
856     return {};
857   }
858   return translateLLVMIRToModule(std::move(llvmModule), context);
859 }
860 
861 static TranslateToMLIRRegistration
862     fromLLVM("import-llvm",
863              [](llvm::SourceMgr &sourceMgr, MLIRContext *context) {
864                return translateLLVMIRToModule(sourceMgr, context);
865              });
866