[mlir][LLVM] Delay debug intrinsic import to ensure dominance

[Dinistro]

Summary

This commit ensures that debug intrinsics are imported after all other
instructions of a function were imported.

Debug intrinsics in LLVM are excluded from the define-before-use
invariant, i.e., they can reference SSA values that do not dominate
them. So far, we had implemented checks to stop the import of such
intrinsics, but there were always additional cases that were not
covered (the latest being terminators that define such used values).

[Dinistro]

This revision solves the same fundamental problem as https://reviews.llvm.org/D157386. This revision is less generic, and thus requires much less boilerplate code to work.

[zero9178]

LGTM. I very much prefer this version over the other. It properly takes dominance into account, caches the dominance info and is a lot more straightforward in terms of controlflow

[gysit]

Thanks for iteration. I think simplicity wins here!

LGTM modulo some nit comments.

mlir/include/mlir/Target/LLVMIR/ModuleImport.h

215

nit: should we rename to clearRegionMappings or clearRegionState?

236–238

ultra nit:

mlir/lib/Target/LLVMIR/ModuleImport.cpp

1802

Would it make sense to call setNonDebugMetadataAttrs in case a downstream user wants to import custom metadata?

[gysit]

LGTM

Forgot to accept :)

[Dinistro]

address review comments

mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td

let llvmBuilder = [{
     builder.CreateCall(fn, {
         llvm::MetadataAsValue::get(ctx,
             llvm::ValueAsMetadata::get(moduleTranslation.lookupValue(opInst.getOperand(0)))),
         llvm::MetadataAsValue::get(ctx, moduleTranslation.translateDebugInfo($varInfo)),
         llvm::MetadataAsValue::get(ctx, llvm::DIExpression::get(ctx, std::nullopt)),
       });
   }];
   let mlirBuilder = [{
-    // Drop debug intrinsics with a non-empty debug expression.
-    // TODO: Support debug intrinsics that evaluate a debug expression.
-    auto *dbgIntr = cast<llvm::DbgVariableIntrinsic>(inst);
-    if (dbgIntr->hasArgList() || dbgIntr->getExpression()->getNumElements() != 0)
-      return success();
-    // Convert the value/address operand late since it cannot be a debug
-    // metadata argument list at this stage. Generating the conversion using an
-    // argument variable would not work here, since the builder variables are
-    // converted before entering the builder, which would result in an error
-    // when attempting to convert an argument list.
-
-    FailureOr<Value> argOperand = moduleImport.convertMetadataValue(llvmOperands[0]);
-    // Drop the intrinsic when its operand could not be converted. This can
-    // happen for use before definition cases that are allowed for debug
-    // intrinsics.
-    // TODO: Implement a two pass solution that translates the debug intrinsics
-    // after the entire function as been translated.
-    if (failed(argOperand))
-      return success();
-
-    // Ensure that the debug instrinsic is inserted right after its operand is
-    // defined. Otherwise, the operand might not necessarily dominate the
-    // intrinsic.
-    OpBuilder::InsertionGuard guard($_builder);
-    $_builder.setInsertionPointAfterValue(*argOperand);
-    $_op = $_builder.create<$_qualCppClassName>($_location,
-        *argOperand, $_var_attr($varInfo));
+    // Add debug intrindic to the list of intrinsics that need to be converted once the
+    // full function was converted.
+    moduleImport.addDebugIntrinsic(inst);
   }];
   let assemblyFormat = [{
     qualified($varInfo) `=` $}] # argName #
       [{ `:` qualified(type($}] # argName # [{)) attr-dict
   }];
 }
 
 def LLVM_DbgDeclareOp : LLVM_DbgIntrOp<"dbg.declare", "addr",

mlir/include/mlir/Target/LLVMIR/ModuleImport.h

 #include "mlir/IR/BuiltinOps.h"
 #include "mlir/Target/LLVMIR/Import.h"
 #include "mlir/Target/LLVMIR/LLVMImportInterface.h"
 #include "mlir/Target/LLVMIR/TypeFromLLVM.h"
 
 namespace llvm {
 class BasicBlock;
 class CallBase;
+class DbgVariableIntrinsic;
 class Function;
 class Instruction;
 class Value;
 } // namespace llvm
 
 namespace mlir {
 namespace LLVM {
 
LoopAnnotationAttr translateLoopAnnotationAttr(const llvm::MDNode *node,
                                                  Location loc) const;
 
   /// Returns the alias scope attributes that map to the alias scope nodes
   /// starting from the metadata `node`. Returns failure, if any of the
   /// attributes cannot be found.
   FailureOr<SmallVector<AliasScopeAttr>>
   lookupAliasScopeAttrs(const llvm::MDNode *node) const;
 
+  /// Adds a debug intrinsics to the list of intrinsics that should be converted
+  /// after the function conversion has finished.
+  void addDebugIntrinsic(llvm::CallInst *intrinsic);
+
 private:
   /// Clears the block and value mapping before processing a new region.
   void clearBlockAndValueMapping() {
     valueMapping.clear();
     noResultOpMapping.clear();
     blockMapping.clear();
+    debugIntrinsics.clear();
   }
   /// Sets the constant insertion point to the start of the given block.
   void setConstantInsertionPointToStart(Block *block) {
     constantInsertionBlock = block;
     constantInsertionOp = nullptr;
   }
 
   /// Converts an LLVM global variable into an MLIR LLVM dialect global
   /// operation if a conversion exists. Otherwise, returns failure.
   LogicalResult convertGlobal(llvm::GlobalVariable *globalVar);
   /// Imports the magic globals "global_ctors" and "global_dtors".
   LogicalResult convertGlobalCtorsAndDtors(llvm::GlobalVariable *globalVar);
   /// Returns personality of `func` as a FlatSymbolRefAttr.
   FlatSymbolRefAttr getPersonalityAsAttr(llvm::Function *func);
   /// Imports `bb` into `block`, which must be initially empty.
   LogicalResult processBasicBlock(llvm::BasicBlock *bb, Block *block);
+  /// Converts all debug intrinsics in `debugIntrinsics`. Assumes that the
+  /// function that these intrinsics are part of was already fully converted to
+  /// MLIR.
+  LogicalResult processDebugIntrinsics();
+  /// Converts a single debug intrinsic.
+  LogicalResult processDebugIntrinsic(llvm::DbgVariableIntrinsic *dbgIntr,
+                                      DominanceInfo &domInfo);
   /// Converts an LLVM intrinsic to an MLIR LLVM dialect operation if an MLIR
   /// counterpart exists. Otherwise, returns failure.
   LogicalResult convertIntrinsic(llvm::CallInst *inst);
   /// Converts an LLVM instruction to an MLIR LLVM dialect operation if an MLIR
   /// counterpart exists. Otherwise, returns failure.
   LogicalResult convertInstruction(llvm::Instruction *inst);
   /// Converts the metadata attached to the original instruction `inst` if
   /// a dialect interfaces supports the specific kind of metadata and attaches
private:
   /// Function-local mapping between original and imported block.
   DenseMap<llvm::BasicBlock *, Block *> blockMapping;
   /// Function-local mapping between original and imported values.
   DenseMap<llvm::Value *, Value> valueMapping;
   /// Function-local mapping between original instructions and imported
   /// operations for all operations that return no result. All operations that
   /// return a result have a valueMapping entry instead.
   DenseMap<llvm::Instruction *, Operation *> noResultOpMapping;
+  /// Function-local list of debug intrinsics that need to be imported after the
+  /// function conversion has finished.
+  SetVector<llvm::Instruction *> debugIntrinsics;
   /// Mapping between LLVM alias scope and domain metadata nodes and
   /// attributes in the LLVM dialect corresponding to these nodes.
   DenseMap<const llvm::MDNode *, Attribute> aliasScopeMapping;
   /// Mapping between LLVM TBAA metadata nodes and LLVM dialect TBAA attributes
   /// corresponding to these nodes.
   DenseMap<const llvm::MDNode *, Attribute> tbaaMapping;
   /// Mapping between LLVM comdat structs and symbol references to LLVM dialect
   /// comdat selector operations corresponding to these structs.

mlir/lib/Target/LLVMIR/ModuleImport.cpp

 #include "mlir/IR/Builders.h"
 #include "mlir/IR/Matchers.h"
 #include "mlir/Interfaces/DataLayoutInterfaces.h"
 #include "mlir/Tools/mlir-translate/Translation.h"
 
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringSet.h"
+#include "llvm/ADT/TypeSwitch.h"
 #include "llvm/IR/Comdat.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Operator.h"
aliasScopes.push_back(
         dyn_cast_or_null<AliasScopeAttr>(aliasScopeMapping.lookup(node)));
   }
   // Return failure if one of the alias scope lookups failed.
   if (llvm::is_contained(aliasScopes, nullptr))
     return failure();
   return aliasScopes;
 }
 
+void ModuleImport::addDebugIntrinsic(llvm::CallInst *intrinsic) {
+  debugIntrinsics.insert(intrinsic);
+}
+
 LogicalResult ModuleImport::convertMetadata() {
   OpBuilder::InsertionGuard guard(builder);
   builder.setInsertionPointToEnd(mlirModule.getBody());
   for (const llvm::Function &func : llvmModule->functions()) {
     for (const llvm::Instruction &inst : llvm::instructions(func)) {
       // Convert access group metadata nodes.
       if (llvm::MDNode *node =
               inst.getMetadata(llvm::LLVMContext::MD_access_group))
LogicalResult ModuleImport::convertInstruction(llvm::Instruction *inst) {
 
   return emitError(loc) << "unhandled instruction: " << diag(*inst);
 }
 
 LogicalResult ModuleImport::processInstruction(llvm::Instruction *inst) {
   // FIXME: Support uses of SubtargetData.
   // FIXME: Add support for call / operand attributes.
   // FIXME: Add support for the indirectbr, cleanupret, catchret, catchswitch,
-  // callbr, vaarg, landingpad, catchpad, cleanuppad instructions.
+  // callbr, vaarg, catchpad, cleanuppad instructions.
 
   // Convert LLVM intrinsics calls to MLIR intrinsics.
-  if (auto *callInst = dyn_cast<llvm::CallInst>(inst)) {
-    llvm::Function *callee = callInst->getCalledFunction();
-    if (callee && callee->isIntrinsic())
-      return convertIntrinsic(callInst);
-  }
+  if (auto *intrinsic = dyn_cast<llvm::IntrinsicInst>(inst))
+    return convertIntrinsic(intrinsic);
 
   // Convert all remaining LLVM instructions to MLIR operations.
   return convertInstruction(inst);
 }
 
 FlatSymbolRefAttr ModuleImport::getPersonalityAsAttr(llvm::Function *f) {
   if (!f->hasPersonalityFn())
     return nullptr;
for (const auto &it : llvm::enumerate(func->args())) {
     mapValue(&it.value(), blockArg);
   }
 
   // Process the blocks in topological order. The ordered traversal ensures
   // operands defined in a dominating block have a valid mapping to an MLIR
   // value once a block is translated.
   SetVector<llvm::BasicBlock *> blocks = getTopologicallySortedBlocks(func);
   setConstantInsertionPointToStart(lookupBlock(blocks.front()));
-  for (llvm::BasicBlock *bb : blocks) {
+  for (llvm::BasicBlock *bb : blocks)
     if (failed(processBasicBlock(bb, lookupBlock(bb))))
       return failure();
-  }
+
+  // Process the debug intrinsics that require a delayed conversion after
+  // everything else was converted.
+  if (failed(processDebugIntrinsics()))
+    return failure();
+
+  return success();
 
+LogicalResult
+ModuleImport::processDebugIntrinsic(llvm::DbgVariableIntrinsic *dbgIntr,
+                                    DominanceInfo &domInfo) {
+  Location loc = translateLoc(dbgIntr->getDebugLoc());
+  auto emitUnsupportedWarning = [&]() {
+    if (emitExpensiveWarnings)
+      emitWarning(loc) << "dropped intrinsic: " << diag(*dbgIntr);
+    return success();
+  };
+  // Drop debug intrinsics with a non-empty debug expression.
+  // TODO: Support debug intrinsics that evaluate a debug expression.
+  if (dbgIntr->hasArgList() || dbgIntr->getExpression()->getNumElements() != 0)
+    return emitUnsupportedWarning();
+  FailureOr<Value> argOperand = convertMetadataValue(dbgIntr->getArgOperand(0));
+  if (failed(argOperand))
+    return failure();
+
+  // Ensure that the debug instrinsic is inserted right after its operand is
+  // defined. Otherwise, the operand might not necessarily dominate the
+  // intrinsic. If the defining operation is a terminator, insert the intrinsic
+  // into a dominated block.
+  OpBuilder::InsertionGuard guard(builder);
+  if (Operation *op = argOperand->getDefiningOp();
+      op && op->hasTrait<OpTrait::IsTerminator>()) {
+    // Find a dominated block that can hold the debug intrinsic.
+    auto dominatedBlocks = domInfo.getNode(op->getBlock())->children();
+    // If no block is dominated by the terminator, this intrinisc cannot be
+    // converted.
+    if (dominatedBlocks.empty())
+      return emitUnsupportedWarning();
+    // Set insertion point before the terminator, to avoid inserting something
+    // before landingpads.
+    Block *dominatedBlock = (*dominatedBlocks.begin())->getBlock();
+    builder.setInsertionPoint(dominatedBlock->getTerminator());
+  } else {
+    builder.setInsertionPointAfterValue(*argOperand);
+  }
+  DILocalVariableAttr localVariableAttr =
+      matchLocalVariableAttr(dbgIntr->getArgOperand(1));
+  Operation *op =
+      llvm::TypeSwitch<llvm::DbgVariableIntrinsic *, Operation *>(dbgIntr)
+          .Case([&](llvm::DbgDeclareInst *) {
+            return builder.create<LLVM::DbgDeclareOp>(loc, *argOperand,
+                                                      localVariableAttr);
+          })
+          .Case([&](llvm::DbgValueInst *) {
+            return builder.create<LLVM::DbgValueOp>(loc, *argOperand,
+                                                    localVariableAttr);
+          });
+  mapNoResultOp(dbgIntr, op);
+  return success();
+}
+
+LogicalResult ModuleImport::processDebugIntrinsics() {
+  DominanceInfo domInfo;
+  for (llvm::Instruction *inst : debugIntrinsics) {
+    auto *intrCall = cast<llvm::DbgVariableIntrinsic>(inst);
+    if (failed(processDebugIntrinsic(intrCall, domInfo)))
+      return failure();
+  }
   return success();
 }
 
 LogicalResult ModuleImport::processBasicBlock(llvm::BasicBlock *bb,
                                               Block *block) {
   builder.setInsertionPointToStart(block);
   for (llvm::Instruction &inst : *bb) {
     if (failed(processInstruction(&inst)))
       return failure();
 
+    // Skip additional processing when the instructions is a debug intrinsics
+    // that was not yet converted.
+    if (debugIntrinsics.contains(&inst))
+      continue;
+
     // Set the non-debug metadata attributes on the imported operation and emit
     // a warning if an instruction other than a phi instruction is dropped
     // during the import.
     if (Operation *op = lookupOperation(&inst)) {
       setNonDebugMetadataAttrs(&inst, op);
     } else if (inst.getOpcode() != llvm::Instruction::PHI) {
       if (emitExpensiveWarnings) {
         Location loc = debugImporter->translateLoc(inst.getDebugLoc());

mlir/test/Target/LLVMIR/Import/debug-info.ll

 !2 = !DIFile(filename: "debug-info.ll", directory: "/")
 !3 = !DISubprogram(name: "variadic_func", scope: !2, file: !2, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, type: !4)
 !4 = !DISubroutineType(types: !5)
 !5 = !{null, null}
 
 ; // -----
 
 define void @dbg_use_before_def(ptr %arg) {
+  ; CHECK: llvm.getelementptr
+  ; CHECK-NEXT: llvm.intr.dbg.value
   call void @llvm.dbg.value(metadata ptr %dbg_arg, metadata !7, metadata !DIExpression()), !dbg !9
   %dbg_arg = getelementptr double, ptr %arg, i64 16
   ret void
 }
 
 declare void @llvm.dbg.value(metadata, metadata, metadata)
 
 !llvm.dbg.cu = !{!1}

 !5 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !3, flags: DIFlagArtificial | DIFlagObjectPointer)
 !6 = !DIDerivedType(tag: DW_TAG_member, name: "call_field", file: !2, baseType: !5)
 !7 = !DILocalVariable(scope: !8, name: "var", file: !2, type: !5);
 !8 = distinct !DISubprogram(name: "dbg_use_before_def", scope: !2, file: !2, spFlags: DISPFlagDefinition, unit: !1)
 !9 = !DILocation(line: 1, column: 2, scope: !8)
 
 ; // -----
 
+declare i64 @callee()
+declare i32 @personality(...)
+
+; CHECK-LABEL: @dbg_broken_dominance_invoke
+define void @dbg_broken_dominance_invoke() personality ptr @personality {
+  %1 = invoke i64 @callee()
+          to label %b1 unwind label %b2
+b1:
+; CHECK: llvm.intr.dbg.value
+  call void @llvm.dbg.value(metadata i64 %1, metadata !7, metadata !DIExpression()), !dbg !9
+  ret void
+b2:
+  %2 = landingpad { ptr, i32 }
+          cleanup
+  ret void
+}
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!1}
+!llvm.module.flags = !{!0}
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = distinct !DICompileUnit(language: DW_LANG_C, file: !2)
+!2 = !DIFile(filename: "debug-info.ll", directory: "/")
+!7 = !DILocalVariable(scope: !8, name: "var", file: !2);
+!8 = distinct !DISubprogram(name: "dbg_broken_dominance_invoke", scope: !2, file: !2, spFlags: DISPFlagDefinition, unit: !1)
+!9 = !DILocation(line: 1, column: 2, scope: !8)
+
+; // -----
+
+declare i64 @callee()
+declare i32 @personality(...)
+
+; CHECK-LABEL: @dbg_broken_dominance_invoke_reordered
+define void @dbg_broken_dominance_invoke_reordered() personality ptr @personality {
+  %1 = invoke i64 @callee()
+          to label %b2 unwind label %b1
+b1:
+; CHECK: landingpad
+; CHECK: llvm.intr.dbg.value
+  %2 = landingpad { ptr, i32 }
+          cleanup
+  call void @llvm.dbg.value(metadata i64 %1, metadata !7, metadata !DIExpression()), !dbg !9
+  ret void
+b2:
+  ret void
+}
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!1}
+!llvm.module.flags = !{!0}
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = distinct !DICompileUnit(language: DW_LANG_C, file: !2)
+!2 = !DIFile(filename: "debug-info.ll", directory: "/")
+!7 = !DILocalVariable(scope: !8, name: "var", file: !2);
+!8 = distinct !DISubprogram(name: "dbg_broken_dominance_invoke", scope: !2, file: !2, spFlags: DISPFlagDefinition, unit: !1)
+!9 = !DILocation(line: 1, column: 2, scope: !8)
+
+; // -----
+
 ; CHECK-DAG: #[[NAMESPACE:.+]] = #llvm.di_namespace<name = "std", exportSymbols = false>
 ; CHECK-DAG: #[[SUBPROGRAM:.+]] =  #llvm.di_subprogram<compileUnit = #{{.*}}, scope = #[[NAMESPACE]], name = "namespace"
 
 define void @namespace(ptr %arg) {
   call void @llvm.dbg.value(metadata ptr %arg, metadata !7, metadata !DIExpression()), !dbg !9
   ret void
 }
 

mlir/test/Target/LLVMIR/Import/import-failure.ll

define void @unhandled_intrinsic() gc "example" {
   ret void
 }
 
 ; // -----
 
 declare void @llvm.dbg.value(metadata, metadata, metadata)
 
 ; CHECK:      import-failure.ll
-; CHECK-SAME: warning: dropped instruction: call void @llvm.dbg.value(metadata i64 %arg1, metadata !3, metadata !DIExpression(DW_OP_plus_uconst, 42, DW_OP_stack_value)), !dbg !5
+; CHECK-SAME: warning: dropped intrinsic: call void @llvm.dbg.value(metadata i64 %arg1, metadata !3, metadata !DIExpression(DW_OP_plus_uconst, 42, DW_OP_stack_value)), !dbg !5
 ; CHECK:      import-failure.ll
-; CHECK-SAME: warning: dropped instruction: call void @llvm.dbg.value(metadata !DIArgList(i64 %arg1, i64 undef), metadata !3, metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_constu, 1, DW_OP_mul, DW_OP_plus, DW_OP_stack_value)), !dbg !5
+; CHECK-SAME: warning: dropped intrinsic: call void @llvm.dbg.value(metadata !DIArgList(i64 %arg1, i64 undef), metadata !3, metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_constu, 1, DW_OP_mul, DW_OP_plus, DW_OP_stack_value)), !dbg !5
 define void @dropped_instruction(i64 %arg1) {
   call void @llvm.dbg.value(metadata i64 %arg1, metadata !3, metadata !DIExpression(DW_OP_plus_uconst, 42, DW_OP_stack_value)), !dbg !5
   call void @llvm.dbg.value(metadata !DIArgList(i64 %arg1, i64 undef), metadata !3, metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_constu, 1, DW_OP_mul, DW_OP_plus, DW_OP_stack_value)), !dbg !5
   ret void
 }
 
 !llvm.dbg.cu = !{!1}
 !llvm.module.flags = !{!0}