Disallow duplication of imported entities

[aaboud]

Summary

Fixed DIBuilder to verify that same imported entity will not be added twice to the "imports" list of the DICompileUnit.

[aaboud]

I will add the following test: Clang/test/Codegen/debug-info-imported-entity.cpp

// RUN: %clang_cc1 -triple x86_64-unk-unk -o - -emit-llvm -debug-info-kind=limited %s | FileCheck %s

namespace std { class A; }
using std::A; using ::A;

// CHECK: [[CompileUnit:![0-9]+]] = distinct !DICompileUnit({{.+}} imports: [[Imports:![0-9]+]])
// CHECK: [[Imports]] = !{[[ImportedEntity:![0-9]+]]}
// CHECK: [[ImportedEntity]] = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: [[CompileUnit]], entity: !"_ZTSSt1A", line: 4)

[dblaikie]

(please include the fix in the patch for review)

I think the fix could probably happen at a higher level to avoid the linear
search. Perhaps we could get the canonical decl for a using decl - that way
a redecl wouldn't be a 'new' thing? I suppose we'd still need a map of
them, that perhaps we don't have already.

[aprantl]

That, or we make AllImportedUnits a SmallSet (which is arguably more expensive).

[aaboud]

In D17884#368253, @aprantl wrote:

That, or we make AllImportedUnits a SmallSet (which is arguably more expensive).

SmallSet is not good enough, as the order will be arbitrary and we will get non-deterministic order of imported entries that have same context.
I thought to use VectorSet, but it does not have the embrace_push function!

[aaboud]

In D17884#368250, @dblaikie wrote:

(please include the fix in the patch for review)

I am not sure what this comment mean!
What do you want me to include in the patch?

[aprantl]

The confusion probably comes from the fact that the test is in CFE, but the change is in LLVM. Maybe it would make sense to also add a unittest. We have a couple for DIBuilder.

[hintonda]

lib/IR/DIBuilder.cpp

171 ↗

(On Diff #49815)

Since these are maintained in a DenseMap in LLVMContextImpl, which is already unique, is there a way to use that directly instead of maintaining an additional vector?

[hintonda]

It's actually a DenseSet, which makes it even easier. Here's a partial diff -- the rest is just removing references to AllImportedModules.

diff --git a/lib/IR/DIBuilder.cpp b/lib/IR/DIBuilder.cpp
index b7841fe..9288207 100644
--- a/lib/IR/DIBuilder.cpp
+++ b/lib/IR/DIBuilder.cpp
@@ -19,6 +19,7 @@
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Dwarf.h"
+#include "LLVMContextImpl.h"

 using namespace llvm;
 using namespace llvm::dwarf;
@@ -110,10 +111,10 @@ void DIBuilder::finalize() {
   if (!AllGVs.empty())
     CUNode->replaceGlobalVariables(MDTuple::get(VMContext, AllGVs));

-  if (!AllImportedModules.empty())
+  if (!VMContext.pImpl->DIImportedEntitys.empty())
     CUNode->replaceImportedEntities(MDTuple::get(
-        VMContext, SmallVector<Metadata *, 16>(AllImportedModules.begin(),
-                                               AllImportedModules.end())));
+        VMContext, SmallVector<Metadata *, 16>(VMContext.pImpl->DIImportedEntitys.begin(),
+                                               VMContext.pImpl->DIImportedEntitys.end())));

[aaboud]

In D17884#368482, @hintonda wrote:

It's actually a DenseSet, which makes it even easier. Here's a partial diff -- the rest is just removing references to AllImportedModules.

diff --git a/lib/IR/DIBuilder.cpp b/lib/IR/DIBuilder.cpp
index b7841fe..9288207 100644
--- a/lib/IR/DIBuilder.cpp
+++ b/lib/IR/DIBuilder.cpp
@@ -19,6 +19,7 @@
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Dwarf.h"
+#include "LLVMContextImpl.h"

 using namespace llvm;
 using namespace llvm::dwarf;
@@ -110,10 +111,10 @@ void DIBuilder::finalize() {
   if (!AllGVs.empty())
     CUNode->replaceGlobalVariables(MDTuple::get(VMContext, AllGVs));

-  if (!AllImportedModules.empty())
+  if (!VMContext.pImpl->DIImportedEntitys.empty())
     CUNode->replaceImportedEntities(MDTuple::get(
-        VMContext, SmallVector<Metadata *, 16>(AllImportedModules.begin(),
-                                               AllImportedModules.end())));
+        VMContext, SmallVector<Metadata *, 16>(VMContext.pImpl->DIImportedEntitys.begin(),
+                                               VMContext.pImpl->DIImportedEntitys.end())));

It is still a set that has non-deterministic order, i.e. the order of the metadata will be different from one run to another...impossible for testing and might add more unwanted results...
The only solution is to have a VectorSet, or a vector + a Set.

[hintonda]

Could you use a SetVector or SmallSetVector instead of a DenseSet for DIImportedEntities? It's equivalent to what you've proposed, but since it knows when it inserts a new one, maintaining the vector is much cheaper.

[aaboud]

Another try to verify that we add imported entity only once.
This is the cheapest solution, though it might not be elegant enough.

Also, added a unittest to check same imported entities are added only once to the "imports" field in DICompileUnit.

[aaboud]

Another try, this time I am uploading suggested solution by Don Hinton.
He is suggesting to make "imports" field in DICompileUnit of new type "unique vector".
Then we can get rid of AllImportedEntitys container and use directly the LLVMContext::impl::DIImportedEntitys instead

[dblaikie]

Pretty sure we shouldn't be adding things to LLVMContext for this, but I
haven't looked closely at the patch/followed the discussion that got us
there in the first place. Will come back to this when I get a chance
(probably later this week) but I'm mentioning it in case others
reading/interacting on the thread can figure it out before then.

[aaboud]

In D17884#369172, @dblaikie wrote:

Pretty sure we shouldn't be adding things to LLVMContext for this, but I
haven't looked closely at the patch/followed the discussion that got us
there in the first place. Will come back to this when I get a chance
(probably later this week) but I'm mentioning it in case others
reading/interacting on the thread can figure it out before then.

Thanks David,
Please, when you have time to review this, check also patch 49934 (Diff 2).
It is a simpler solution, but not sure also that it is the right one.

[aaboud]

I just figure out why this approach will not work.
The idea here was to get rid of AllImportedModules list and use the DIImportedEntitys list from the LLVMContextImpl class, assuming that they contain the same info, which is wrong.
AllImportedModules list is per DICompileUnit, while DIImportedEntitys contains all the imported entities from all Compile units.

We cannot get rid of AllImportedModules, thus I will revert this patch to Diff 2.

[aaboud]

Reverting the patch to Diff 2.

[hintonda]

Good catch. LGTM...

[dblaikie]

I'm confused. This patch looks like it's missing parts - there is no DIImportedEntitys (btw: should be DIImportedEntities, if it does exist/is added) in the LLVMContext in trunk at the moment. This patch seems to use it, but doesn't introduce it. Should I be looking elsewhere, at some preparatory patch?

[hintonda]

It's an instance of the X Macro technique. In this case:

lib/IR/LLVMContextImp.h: 937
#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
  DenseSet<CLASS *, CLASS##Info> CLASS##s;
#include "llvm/IR/Metadata.def"

include/llvm/IR/Metadata.def: 110
HANDLE_SPECIALIZED_MDNODE_LEAF_UNIQUABLE(DIImportedEntity)

[dblaikie]

Seems like a bit more an implementation detail than we'd really want to depend on, but the cost is so low & isolated, & it's so inobtrusive that if/when this does change, it's not going to cost us anymore to fix it then than it would to fix it now so let's go with it.

Please commit when ready.

llvm/trunk/lib/IR/DIBuilder.cpp

 #include "llvm/IR/DIBuilder.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Dwarf.h"
+#include "LLVMContextImpl.h"
 
 using namespace llvm;
 using namespace llvm::dwarf;
 
 namespace {
 class HeaderBuilder {
   /// \brief Whether there are any fields yet.
   ///
DICompileUnit *DIBuilder::createCompileUnit(
   trackIfUnresolved(CUNode);
   return CUNode;
 }
 
 static DIImportedEntity *
 createImportedModule(LLVMContext &C, dwarf::Tag Tag, DIScope *Context,
                      Metadata *NS, unsigned Line, StringRef Name,
                      SmallVectorImpl<TrackingMDNodeRef> &AllImportedModules) {
+  unsigned EntitiesCount = C.pImpl->DIImportedEntitys.size();
   auto *M = DIImportedEntity::get(C, Tag, Context, DINodeRef(NS), Line, Name);
+  if (EntitiesCount < C.pImpl->DIImportedEntitys.size())
+    // A new Imported Entity was just added to the context.
+    // Add it to the Imported Modules list.
     AllImportedModules.emplace_back(M);
   return M;
 }
 
 DIImportedEntity *DIBuilder::createImportedModule(DIScope *Context,
                                                   DINamespace *NS,
                                                   unsigned Line) {
   return ::createImportedModule(VMContext, dwarf::DW_TAG_imported_module,
                                 Context, NS, Line, StringRef(), AllImportedModules);

llvm/trunk/unittests/IR/IRBuilderTest.cpp

TEST_F(IRBuilderTest, DebugLoc) {
   Call1->setDebugLoc(DL2);
   Builder.SetInsertPoint(Call1->getParent(), Call1->getIterator());
   EXPECT_EQ(DL2, Builder.getCurrentDebugLocation());
   auto Call2 = Builder.CreateCall(Callee, None);
   EXPECT_EQ(DL2, Call2->getDebugLoc());
 
   DIB.finalize();
 }
+
+TEST_F(IRBuilderTest, DIImportedEntity) {
+  IRBuilder<> Builder(BB);
+  DIBuilder DIB(*M);
+  auto File = DIB.createFile("F.CBL", "/");
+  auto CU = DIB.createCompileUnit(dwarf::DW_LANG_Cobol74, "F.CBL", "/",
+    "llvm-cobol74", true, "", 0);
+  auto IE1 = DIB.createImportedDeclaration(CU, nullptr, 1);
+  auto IE2 = DIB.createImportedDeclaration(CU, nullptr, 1);
+  auto IE3 = DIB.createImportedModule(CU, (DIImportedEntity*)nullptr, 2);
+  auto IE4 = DIB.createImportedModule(CU, (DIImportedEntity*)nullptr, 2);
+  DIB.finalize();
+  EXPECT_TRUE(verifyModule(*M));
+  EXPECT_TRUE(CU->getImportedEntities().size() == 2);
+}
 }