WIP alternative to r325686 (Implement name based structure type mapping).

[• espindola]

Summary

The long term idea on how to improve the llvm type system is to have a single pointer type which makes the type graph a DAG.

Before that we need some heuristics as graph isomorphism has no known fast algorithm.

One of the heuristics we have is based on the name of the type. That is fairly unfortunate as the name should have no semantic meaning according to the spec. I think we should strive to not add more.

In r325686 another use of the name was added to handle the case when IRMover is given a non empty module and that module has multiple isomorphic types. That can happens as only the IRMover merges isomorphic types. The clang output, for example, can have duplicated types.

This patch changes the IRMover to merge isomorphic types on the destination module.

I now think that this should probably be made into an optimization pass that is run by clang. That way the types are merged before the file is written.

This patch still needs comments and to have the refactoring bits split out.

[• espindola]

Fix test failures.

[evgeny777]

lib/Linker/IRMover.cpp

1459

You're mutating types while processing values in the module. This looks dangerous and actually triggers assertion when your patch is used to link real application (I can provide details and even test case, if you like). Can you do this in two steps instead:

• create a list of objects you want to swap types for
• process this list after TypeMap is fully filled.

[• espindola]

I found a fundamental issue with this:

void ConstantExpr::destroyConstantImpl() {

getType()->getContext().pImpl->ExprConstants.remove(this);

}

Which means we cannot mutate the type without also rebuilding the constant uniquing tables.

I am out of ideas that are no really expensive like implementing a move constructor on Module and always starting the linker with an empty module.

I guess we really need to finish the changes for having a single pointer type.

I will LGTM the original change and ask for a second review on it in case someone has a better idea.

include/llvm/IR/GlobalValue.h

public:
 
   bool hasSection() const { return !getSection().empty(); }
   StringRef getSection() const;
 
   /// Global values are always pointers.
   PointerType *getType() const { return cast<PointerType>(User::getType()); }
 
   Type *getValueType() const { return ValueType; }
+  void mutateValueType(Type *Ty) { ValueType = Ty; }
 
   void setDSOLocal(bool Local) { IsDSOLocal = Local; }
 
   bool isDSOLocal() const {
     return IsDSOLocal;
   }
 
   static LinkageTypes getLinkOnceLinkage(bool ODR) {

include/llvm/IR/TypeFinder.h

public:
   size_t size() const { return StructTypes.size(); }
   iterator erase(iterator I, iterator E) { return StructTypes.erase(I, E); }
 
   StructType *&operator[](unsigned Idx) { return StructTypes[Idx]; }
 
   DenseSet<const MDNode *> &getVisitedMetadata() { return VisitedMetadata; }
 
 private:
-  /// incorporateType - This method adds the type to the list of used
-  /// structures if it's not in there already.
+  /// This method adds the type to the list of used structures if it's not in
+  /// there already.
   void incorporateType(Type *Ty);
-
-  /// incorporateValue - This method is used to walk operand lists finding types
-  /// hiding in constant expressions and other operands that won't be walked in
-  /// other ways.  GlobalValues, basic blocks, instructions, and inst operands
-  /// are all explicitly enumerated.
-  void incorporateValue(const Value *V);
-
-  /// incorporateMDNode - This method is used to walk the operands of an MDNode
-  /// to find types hiding within.
-  void incorporateMDNode(const MDNode *V);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_IR_TYPEFINDER_H

include/llvm/IR/ValueVisitor.h

+#ifndef LLVM_IR_VALUEVISITOR_H
+#define LLVM_IR_VALUEVISITOR_H
+
+#include <functional>
+
+namespace llvm {
+class Module;
+class MDNode;
+class Value;
+
+void visitAllValues(Module &M, std::function<void(Value &)> Visit);
+void visitAllValues(const Module &M, std::function<void(const Value &)> Visit);
+
+} // namespace llvm
+
+#endif

lib/IR/CMakeLists.txt

add_llvm_library(LLVMCore
   Statepoint.cpp
   Type.cpp
   TypeFinder.cpp
   Use.cpp
   User.cpp
   Value.cpp
   ValueSymbolTable.cpp
   ValueTypes.cpp
+  ValueVisitor.cpp
   Verifier.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/IR
 
   DEPENDS
   intrinsics_gen
   )

lib/IR/TypeFinder.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
+#include "llvm/IR/ValueVisitor.h"
 #include "llvm/Support/Casting.h"
 #include <utility>
 
 using namespace llvm;
 
 void TypeFinder::run(const Module &M, bool onlyNamed) {
   OnlyNamed = onlyNamed;
-
-  // Get types from global variables.
-  for (const auto &G : M.globals()) {
-    incorporateType(G.getType());
-    if (G.hasInitializer())
-      incorporateValue(G.getInitializer());
-  }
-
-  // Get types from aliases.
-  for (const auto &A : M.aliases()) {
-    incorporateType(A.getType());
-    if (const Value *Aliasee = A.getAliasee())
-      incorporateValue(Aliasee);
-  }
-
-  // Get types from functions.
-  SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
-  for (const Function &FI : M) {
-    incorporateType(FI.getType());
-
-    for (const Use &U : FI.operands())
-      incorporateValue(U.get());
-
-    // First incorporate the arguments.
-    for (const auto &A : FI.args())
-      incorporateValue(&A);
-
-    for (const BasicBlock &BB : FI)
-      for (const Instruction &I : BB) {
-        // Incorporate the type of the instruction.
-        incorporateType(I.getType());
-
-        // Incorporate non-instruction operand types. (We are incorporating all
-        // instructions with this loop.)
-        for (const auto &O : I.operands())
-          if (&*O && !isa<Instruction>(&*O))
-            incorporateValue(&*O);
-
-        // Incorporate types hiding in metadata.
-        I.getAllMetadataOtherThanDebugLoc(MDForInst);
-        for (const auto &MD : MDForInst)
-          incorporateMDNode(MD.second);
-        MDForInst.clear();
-      }
-  }
-
-  for (const auto &NMD : M.named_metadata())
-    for (const auto &MDOp : NMD.operands())
-      incorporateMDNode(MDOp);
+  visitAllValues(M, [&](const Value &V) { incorporateType(V.getType()); });
 }
 
 void TypeFinder::clear() {
   VisitedConstants.clear();
   VisitedTypes.clear();
   StructTypes.clear();
 }
 
-/// incorporateType - This method adds the type to the list of used structures
-/// if it's not in there already.
+/// This method adds the type to the list of used structures if it's not in
+/// there already.
 void TypeFinder::incorporateType(Type *Ty) {
   // Check to see if we've already visited this type.
   if (!VisitedTypes.insert(Ty).second)
     return;
 
   SmallVector<Type *, 4> TypeWorklist;
   TypeWorklist.push_back(Ty);
   do {
     Ty = TypeWorklist.pop_back_val();
 
     // If this is a structure or opaque type, add a name for the type.
     if (StructType *STy = dyn_cast<StructType>(Ty))
       if (!OnlyNamed || STy->hasName())
         StructTypes.push_back(STy);
 
     // Add all unvisited subtypes to worklist for processing
     for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(),
                                         E = Ty->subtype_rend();
          I != E; ++I)
       if (VisitedTypes.insert(*I).second)
         TypeWorklist.push_back(*I);
   } while (!TypeWorklist.empty());
 }
-
-/// incorporateValue - This method is used to walk operand lists finding types
-/// hiding in constant expressions and other operands that won't be walked in
-/// other ways.  GlobalValues, basic blocks, instructions, and inst operands are
-/// all explicitly enumerated.
-void TypeFinder::incorporateValue(const Value *V) {
-  if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
-    if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
-      return incorporateMDNode(N);
-    if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
-      return incorporateValue(MDV->getValue());
-    return;
-  }
-
-  if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
-
-  // Already visited?
-  if (!VisitedConstants.insert(V).second)
-    return;
-
-  // Check this type.
-  incorporateType(V->getType());
-
-  // If this is an instruction, we incorporate it separately.
-  if (isa<Instruction>(V))
-    return;
-
-  // Look in operands for types.
-  const User *U = cast<User>(V);
-  for (const auto &I : U->operands())
-    incorporateValue(&*I);
-}
-
-/// incorporateMDNode - This method is used to walk the operands of an MDNode to
-/// find types hiding within.
-void TypeFinder::incorporateMDNode(const MDNode *V) {
-  // Already visited?
-  if (!VisitedMetadata.insert(V).second)
-    return;
-
-  // Look in operands for types.
-  for (Metadata *Op : V->operands()) {
-    if (!Op)
-      continue;
-    if (auto *N = dyn_cast<MDNode>(Op)) {
-      incorporateMDNode(N);
-      continue;
-    }
-    if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
-      incorporateValue(C->getValue());
-      continue;
-    }
-  }
-}

lib/IR/ValueVisitor.cpp

+#include "llvm/IR/ValueVisitor.h"
+#include "llvm/IR/Module.h"
+
+using namespace llvm;
+
+namespace {
+class ValueVisitor {
+  DenseSet<Value *> Visited;
+  DenseSet<MDNode *> VisitedMDNode;
+  Module &M;
+  std::function<void(Value &)> Visit;
+  void visitValue(Value &V);
+  void visitMDNode(MDNode &MD);
+  void visitMetadata(Metadata &MD);
+
+public:
+  ValueVisitor(Module &M, std::function<void(Value &)> Visit)
+      : M(M), Visit(Visit) {}
+  void run();
+};
+} // namespace
+
+void ValueVisitor::visitValue(Value &V) {
+  if (!Visited.insert(&V).second)
+    return;
+
+  Visit(V);
+
+  if (isa<Argument>(V) || isa<InlineAsm>(V))
+    return;
+
+  if (auto *GV = dyn_cast<GlobalVariable>(&V)) {
+    if (GV->hasInitializer())
+      visitValue(*GV->getInitializer());
+    return;
+  }
+
+  if (auto *GIS = dyn_cast<GlobalIndirectSymbol>(&V)) {
+    if (auto *Ind = GIS->getIndirectSymbol())
+      visitValue(*Ind);
+    return;
+  }
+
+  if (auto *BB = dyn_cast<BasicBlock>(&V)) {
+    for (Instruction &I : *BB)
+      visitValue(I);
+    return;
+  }
+
+  if (auto *I = dyn_cast<Instruction>(&V)) {
+    for (auto &O : I->operands())
+      visitValue(*O);
+    SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
+    I->getAllMetadataOtherThanDebugLoc(MDForInst);
+    for (auto &MD : MDForInst)
+      visitMDNode(*MD.second);
+    return;
+  }
+
+  if (auto *M = dyn_cast<MetadataAsValue>(&V)) {
+    visitMetadata(*M->getMetadata());
+    return;
+  }
+
+  if (auto *F = dyn_cast<Function>(&V)) {
+    for (Use &U : F->operands())
+      visitValue(*U.get());
+    for (auto &A : F->args())
+      visitValue(A);
+    for (BasicBlock &BB : *F)
+      visitValue(BB);
+    return;
+  }
+
+  User &U = cast<User>(V);
+  for (auto &I : U.operands())
+    visitValue(*I);
+}
+
+void ValueVisitor::visitMetadata(Metadata &MD) {
+  if (auto *N = dyn_cast<MDNode>(&MD))
+    visitMDNode(*N);
+  else if (auto *MDV = dyn_cast<ValueAsMetadata>(&MD))
+    visitValue(*MDV->getValue());
+}
+
+void ValueVisitor::visitMDNode(MDNode &MD) {
+  if (VisitedMDNode.insert(&MD).second)
+    for (Metadata *Op : MD.operands())
+      if (Op)
+        visitMetadata(*Op);
+}
+
+void ValueVisitor::run() {
+  for (auto &G : M.globals())
+    visitValue(G);
+  for (auto &A : M.aliases())
+    visitValue(A);
+  for (Function &F : M)
+    visitValue(F);
+  for (auto &IF : M.ifuncs())
+    visitValue(IF);
+  for (auto &NMD : M.named_metadata())
+    for (auto *MDOp : NMD.operands())
+      visitMDNode(*MDOp);
+}
+
+void llvm::visitAllValues(Module &M, std::function<void(Value &)> Visit) {
+  ValueVisitor Visitor(M, Visit);
+  Visitor.run();
+}
+
+void llvm::visitAllValues(const Module &M,
+                          std::function<void(const Value &)> Visit) {
+  visitAllValues(const_cast<Module &>(M), [&](Value &V) { Visit(V); });
+}

lib/Linker/IRMover.cpp

 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/IR/GVMaterializer.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/TypeFinder.h"
+#include "llvm/IR/ValueVisitor.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include <utility>
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
 // TypeMap implementation.
 //===----------------------------------------------------------------------===//
case Type::StructTyID: {
     // If the type is opaque, we can just use it directly.
     if (STy->isOpaque()) {
       DstStructTypesSet.addOpaque(STy);
       return *Entry = Ty;
     }
 
     if (StructType *OldT =
             DstStructTypesSet.findNonOpaque(ElementTypes, IsPacked)) {
+      if (OldT != STy)
         STy->setName("");
       return *Entry = OldT;
     }
 
     if (!AnyChange) {
       DstStructTypesSet.addNonOpaque(STy);
       return *Entry = Ty;
     }
 

 
 bool IRMover::IdentifiedStructTypeSet::hasType(StructType *Ty) {
   if (Ty->isOpaque())
     return OpaqueStructTypes.count(Ty);
   auto I = NonOpaqueStructTypes.find(Ty);
   return I == NonOpaqueStructTypes.end() ? false : *I == Ty;
 }
 
+static void simplifyTypes(Module &M) {
+  TypeFinder StructTypes;
+  StructTypes.run(M, /* OnlyNamed */ false);
+  IRMover::IdentifiedStructTypeSet IdentifiedStructTypes;
+  for (StructType *Ty : StructTypes) {
+    if (Ty->isOpaque())
+      IdentifiedStructTypes.addOpaque(Ty);
+    else
+      IdentifiedStructTypes.addNonOpaque(Ty);
+  }
+  TypeMapTy TypeMap(IdentifiedStructTypes);
+  visitAllValues(M, [&](Value &V) {
+    if (auto *GV = dyn_cast<GlobalValue>(&V))
+      GV->mutateValueType(TypeMap.get(GV->getValueType()));
+    if (auto *I = dyn_cast<GetElementPtrInst>(&V)) {
+      I->setResultElementType(TypeMap.get(I->getResultElementType()));
+      I->setSourceElementType(TypeMap.get(I->getSourceElementType()));
+    }
+    if (auto *I = dyn_cast<CallInst>(&V))
+      I->mutateFunctionType(TypeMap.get(I->getFunctionType()));
+    if (auto *I = dyn_cast<InvokeInst>(&V))
+      I->mutateFunctionType(TypeMap.get(I->getFunctionType()));
+    if (auto *I = dyn_cast<AllocaInst>(&V))
+      I->setAllocatedType(TypeMap.get(I->getAllocatedType()));
+    V.mutateType(TypeMap.get(V.getType()));
+  });
+}
+
 IRMover::IRMover(Module &M) : Composite(M) {
+  simplifyTypes(M);
   TypeFinder StructTypes;
   StructTypes.run(M, /* OnlyNamed */ false);
   for (StructType *Ty : StructTypes) {
     if (Ty->isOpaque())
       IdentifiedStructTypes.addOpaque(Ty);
     else
       IdentifiedStructTypes.addNonOpaque(Ty);
   }

test/Linker/Inputs/struct-mapping.ll

+%struct.Baz = type { i64, i64, %struct.Foo }
+%struct.Foo = type { i64, i64 }
+
+@baz = global %struct.Baz zeroinitializer

test/Linker/struct-mapping.ll

+; RUN: llvm-link --initial-module=%s %p/Inputs/struct-mapping.ll -S -o - | FileCheck %s
+
+; Here we check that new type mapping merged isomorphic types.
+
+; CHECK-NOT: Foo
+; CHECK: %struct.Bar = type { i64, i64 }
+; CHECK-NEXT: %struct.Baz = type { i64, i64, %struct.Bar }
+; CHECK-NOT: Foo
+
+; CHECK: @bar = global %struct.Bar zeroinitializer
+; CHECK: @foo = global %struct.Bar zeroinitializer
+; CHECK: @baz = global %struct.Baz zeroinitializer
+
+%struct.Bar = type { i64, i64 }
+%struct.Foo = type { i64, i64 }
+
+@bar = global %struct.Bar zeroinitializer
+@foo = global %struct.Foo zeroinitializer

tools/llvm-link/llvm-link.cpp

 static cl::opt<std::string>
     SummaryIndex("summary-index", cl::desc("Module summary index filename"),
                  cl::init(""), cl::value_desc("filename"));
 
 static cl::opt<std::string>
 OutputFilename("o", cl::desc("Override output filename"), cl::init("-"),
                cl::value_desc("filename"));
 
+static cl::opt<std::string>
+    InitialModule("initial-module",
+                  cl::desc("Link to existing destination module"), cl::init(""),
+                  cl::value_desc("filename"));
+
 static cl::opt<bool>
 Internalize("internalize", cl::desc("Internalize linked symbols"));
 
 static cl::opt<bool>
     DisableDITypeMap("disable-debug-info-type-map",
                      cl::desc("Don't use a uniquing type map for debug info"));
 
 static cl::opt<bool>
int main(int argc, char **argv) {
   Context.setDiagnosticHandler(
     llvm::make_unique<LLVMLinkDiagnosticHandler>(), true);
   llvm_shutdown_obj Y;  // Call llvm_shutdown() on exit.
   cl::ParseCommandLineOptions(argc, argv, "llvm linker\n");
 
   if (!DisableDITypeMap)
     Context.enableDebugTypeODRUniquing();
 
-  auto Composite = make_unique<Module>("llvm-link", Context);
+  auto Composite = InitialModule.empty()
+                       ? make_unique<Module>("llvm-link", Context)
+                       : loadFile(argv[0], InitialModule, Context);
   Linker L(*Composite);
 
   unsigned Flags = Linker::Flags::None;
   if (OnlyNeeded)
     Flags |= Linker::Flags::LinkOnlyNeeded;
 
   // First add all the regular input files
   if (!linkFiles(argv[0], Context, L, InputFilenames, Flags))