[Porting MergeSimilarFunctions 2/n] Changes to DataLayout

[hiraditya]

Summary

Depends on https://reviews.llvm.org/D52896

Maybe I can merge both the patches together?

[hiraditya]

rebase

[vish99]

Changes to sync D52898 with D52966

[vish99]

Reverting back to diff 222348, the previous diff was against a wrong branch

[vish99]

Changes to merge the 5 patches together

clang/unittests/Tooling/Syntax/TreeTest.cpp

syntax::TranslationUnit *buildTree(llvm::StringRef Code) {
     BuildSyntaxTreeAction Recorder(Root, this->Arena);
     if (!Compiler.ExecuteAction(Recorder)) {
       ADD_FAILURE() << "failed to run the frontend";
       std::abort();
     }
     return Root;
   }
 
+  void expectTreeDumpEqual(StringRef code, StringRef tree) {
+    SCOPED_TRACE(code);
+
+    auto *Root = buildTree(code);
+    std::string Expected = tree.trim().str();
+    std::string Actual =
+        std::string(llvm::StringRef(Root->dump(*Arena)).trim());
+    EXPECT_EQ(Expected, Actual) << "the resulting dump is:\n" << Actual;
+  }
+
   // Adds a file to the test VFS.
   void addFile(llvm::StringRef Path, llvm::StringRef Contents) {
     if (!FS->addFile(Path, time_t(),
                      llvm::MemoryBuffer::getMemBufferCopy(Contents))) {
       ADD_FAILURE() << "could not add a file to VFS: " << Path;
     }
   }
 
llvm::IntrusiveRefCntPtr<FileManager> FileMgr =
       new FileManager(FileSystemOptions(), FS);
   llvm::IntrusiveRefCntPtr<SourceManager> SourceMgr =
       new SourceManager(*Diags, *FileMgr);
   std::shared_ptr<CompilerInvocation> Invocation;
   // Set after calling buildTree().
   std::unique_ptr<syntax::Arena> Arena;
 };
 
-TEST_F(SyntaxTreeTest, Basic) {
-  std::pair</*Input*/ std::string, /*Expected*/ std::string> Cases[] = {
-      {
-          R"cpp(
+TEST_F(SyntaxTreeTest, Simple) {
+  expectTreeDumpEqual(
 int main() {}
 void foo() {}
     )cpp",
-          R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-int
 | |-SimpleDeclarator
 | | |-main
 | | `-ParametersAndQualifiers
 | |   |-(
 | |   `-)
 | `-CompoundStatement
 |   |-{
 |   `-}
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-foo
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
   `-CompoundStatement
     |-{
     `-}
-)txt"},
-      // if.
-      {
-          R"cpp(
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, If) {
+  expectTreeDumpEqual(
 int main() {
   if (true) {}
   if (true) {} else if (false) {}
 }
         )cpp",
-          R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-int
   |-SimpleDeclarator
   | |-main
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
`-CompoundStatement
     |   |-(
     |   |-UnknownExpression
     |   | `-false
     |   |-)
     |   `-CompoundStatement
     |     |-{
     |     `-}
     `-}
-        )txt"},
-      // for.
-      {R"cpp(
+        )txt");
+}
+
+TEST_F(SyntaxTreeTest, For) {
+  expectTreeDumpEqual(
+      R"cpp(
 void test() {
   for (;;)  {}
 }
 )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
   `-CompoundStatement
     |-{
     |-ForStatement
     | |-for
     | |-(
     | |-;
     | |-;
     | |-)
     | `-CompoundStatement
     |   |-{
     |   `-}
     `-}
-        )txt"},
-      // declaration statement.
-      {"void test() { int a = 10; }",
-       R"txt(
+        )txt");
+}
+
+TEST_F(SyntaxTreeTest, RangeBasedFor) {
+  expectTreeDumpEqual(
+      R"cpp(
+void test() {
+  int a[3];
+  for (int x : a) ;
+}
+      )cpp",
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
   `-CompoundStatement
     |-{
     |-DeclarationStatement
     | |-SimpleDeclaration
     | | |-int
     | | `-SimpleDeclarator
     | |   |-a
-    | |   |-=
-    | |   `-UnknownExpression
-    | |     `-10
-    | `-;
+    | |   `-ArraySubscript
+    | |     |-[
+    | |     |-UnknownExpression
+    | |     | `-3
+    | |     `-]
+    | `-;
+    |-RangeBasedForStatement
+    | |-for
+    | |-(
+    | |-SimpleDeclaration
+    | | |-int
+    | | |-SimpleDeclarator
+    | | | `-x
+    | | `-:
+    | |-UnknownExpression
+    | | `-a
+    | |-)
+    | `-EmptyStatement
+    |   `-;
     `-}
-)txt"},
-      {"void test() { ; }", R"txt(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, DeclarationStatement) {
+  expectTreeDumpEqual("void test() { int a = 10; }",
+                      R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
   `-CompoundStatement
     |-{
-    |-EmptyStatement
+    |-DeclarationStatement
+    | |-SimpleDeclaration
+    | | |-int
+    | | `-SimpleDeclarator
+    | |   |-a
+    | |   |-=
+    | |   `-UnknownExpression
+    | |     `-10
     | `-;
     `-}
-)txt"},
-      // switch, case and default.
-      {R"cpp(
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, Switch) {
+  expectTreeDumpEqual(
+      R"cpp(
 void test() {
   switch (true) {
     case 0:
     default:;
   }
 }
 )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
`-CompoundStatement
     |   | |-:
     |   | `-DefaultStatement
     |   |   |-default
     |   |   |-:
     |   |   `-EmptyStatement
     |   |     `-;
     |   `-}
     `-}
-)txt"},
-      // while.
-      {R"cpp(
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, While) {
+  expectTreeDumpEqual(
+      R"cpp(
 void test() {
   while (true) { continue; break; }
 }
 )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
`-CompoundStatement
     |   |-ContinueStatement
     |   | |-continue
     |   | `-;
     |   |-BreakStatement
     |   | |-break
     |   | `-;
     |   `-}
     `-}
-)txt"},
-      // return.
-      {R"cpp(
-int test() { return 1; }
-      )cpp",
-       R"txt(
-*: TranslationUnit
-`-SimpleDeclaration
-  |-int
-  |-SimpleDeclarator
-  | |-test
-  | `-ParametersAndQualifiers
-  |   |-(
-  |   `-)
-  `-CompoundStatement
-    |-{
-    |-ReturnStatement
-    | |-return
-    | |-UnknownExpression
-    | | `-1
-    | `-;
-    `-}
-)txt"},
-      // Range-based for.
-      {R"cpp(
-void test() {
-  int a[3];
-  for (int x : a) ;
+)txt");
 }
-      )cpp",
-       R"txt(
-*: TranslationUnit
-`-SimpleDeclaration
-  |-void
-  |-SimpleDeclarator
-  | |-test
-  | `-ParametersAndQualifiers
-  |   |-(
-  |   `-)
-  `-CompoundStatement
-    |-{
-    |-DeclarationStatement
-    | |-SimpleDeclaration
-    | | |-int
-    | | `-SimpleDeclarator
-    | |   |-a
-    | |   `-ArraySubscript
-    | |     |-[
-    | |     |-UnknownExpression
-    | |     | `-3
-    | |     `-]
-    | `-;
-    |-RangeBasedForStatement
-    | |-for
-    | |-(
-    | |-SimpleDeclaration
-    | | |-int
-    | | |-SimpleDeclarator
-    | | | `-x
-    | | `-:
-    | |-UnknownExpression
-    | | `-a
-    | |-)
-    | `-EmptyStatement
-    |   `-;
-    `-}
-       )txt"},
-      // Unhandled statements should end up as 'unknown statement'.
-      // This example uses a 'label statement', which does not yet have a syntax
-      // counterpart.
-      {"void main() { foo: return 100; }", R"txt(
+
+TEST_F(SyntaxTreeTest, UnhandledStatement) {
+  expectTreeDumpEqual("void main() { foo: return 100; }",
+                      R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-main
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
   `-CompoundStatement
     |-{
     |-UnknownStatement
     | |-foo
     | |-:
     | `-ReturnStatement
     |   |-return
     |   |-UnknownExpression
     |   | `-100
     |   `-;
     `-}
-)txt"},
-      // expressions should be wrapped in 'ExpressionStatement' when they appear
-      // in a statement position.
-      {R"cpp(
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, Expressions) {
+  expectTreeDumpEqual(
+      R"cpp(
 void test() {
   test();
   if (true) test(); else test();
 }
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
`-CompoundStatement
     | |-else
     | `-ExpressionStatement
     |   |-UnknownExpression
     |   | |-test
     |   | |-(
     |   | `-)
     |   `-;
     `-}
-)txt"},
-      // Multiple declarators group into a single SimpleDeclaration.
-      {R"cpp(
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, MultipleDeclaratorsGrouping) {
+  expectTreeDumpEqual(
+      R"cpp(
       int *a, b;
   )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-int
   |-SimpleDeclarator
   | |-*
   | `-a
   |-,
   |-SimpleDeclarator
   | `-b
   `-;
-  )txt"},
-      {R"cpp(
+  )txt");
+  expectTreeDumpEqual(
+      R"cpp(
     typedef int *a, b;
   )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-typedef
   |-int
   |-SimpleDeclarator
   | |-*
   | `-a
   |-,
   |-SimpleDeclarator
   | `-b
   `-;
-  )txt"},
-      // Multiple declarators inside a statement.
-      {R"cpp(
+  )txt");
+}
+
+TEST_F(SyntaxTreeTest, MultipleDeclaratorsInsideStatement) {
+  expectTreeDumpEqual(
+      R"cpp(
 void foo() {
       int *a, b;
       typedef int *ta, tb;
 }
   )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-foo
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
`-CompoundStatement
     | | |-SimpleDeclarator
     | | | |-*
     | | | `-ta
     | | |-,
     | | `-SimpleDeclarator
     | |   `-tb
     | `-;
     `-}
-  )txt"},
-      {R"cpp(
+  )txt");
+}
+
+TEST_F(SyntaxTreeTest, Namespaces) {
+  expectTreeDumpEqual(
+      R"cpp(
 namespace a { namespace b {} }
 namespace a::b {}
 namespace {}
 
 namespace foo = a;
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-NamespaceDefinition
 | |-namespace
 | |-a
 | |-{
 | |-NamespaceDefinition
 | | |-namespace
 | | |-b

 | |-{
 | `-}
 `-NamespaceAliasDefinition
   |-namespace
   |-foo
   |-=
   |-a
   `-;
-)txt"},
-      // Free-standing classes, must live inside a SimpleDeclaration.
-      {R"cpp(
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, UsingDirective) {
+  expectTreeDumpEqual(
+      R"cpp(
+namespace ns {}
+using namespace ::ns;
+    )cpp",
+      R"txt(
+*: TranslationUnit
+|-NamespaceDefinition
+| |-namespace
+| |-ns
+| |-{
+| `-}
+`-UsingNamespaceDirective
+  |-using
+  |-namespace
+  |-::
+  |-ns
+  `-;
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, UsingDeclaration) {
+  expectTreeDumpEqual(
+      R"cpp(
+namespace ns { int a; }
+using ns::a;
+    )cpp",
+      R"txt(
+*: TranslationUnit
+|-NamespaceDefinition
+| |-namespace
+| |-ns
+| |-{
+| |-SimpleDeclaration
+| | |-int
+| | |-SimpleDeclarator
+| | | `-a
+| | `-;
+| `-}
+`-UsingDeclaration
+  |-using
+  |-ns
+  |-::
+  |-a
+  `-;
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, FreeStandingClasses) {
+  expectTreeDumpEqual(
+      R"cpp(
 sturct X;
 struct X {};
 
 struct Y *y1;
 struct Y {} *y2;
 
 struct {} *a1;
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-sturct
 | |-X
 | `-;
 |-SimpleDeclaration
 | |-struct
 | |-X

 `-SimpleDeclaration
   |-struct
   |-{
   |-}
   |-SimpleDeclarator
   | |-*
   | `-a1
   `-;
-)txt"},
-      {R"cpp(
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, Templates) {
+  expectTreeDumpEqual(
+      R"cpp(
 template <class T> struct cls {};
 template <class T> int var = 10;
 template <class T> int fun() {}
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-TemplateDeclaration
 | |-template
 | |-<
 | |-UnknownDeclaration
 | | |-class
 | | `-T
 | |->
`-SimpleDeclaration
     |-SimpleDeclarator
     | |-fun
     | `-ParametersAndQualifiers
     |   |-(
     |   `-)
     `-CompoundStatement
       |-{
       `-}
-)txt"},
-      {R"cpp(
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, NestedTemplates) {
+  expectTreeDumpEqual(
+      R"cpp(
 template <class T>
 struct X {
   template <class U>
   U foo();
 };
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-TemplateDeclaration
   |-template
   |-<
   |-UnknownDeclaration
   | |-class
   | `-T
   |->
`-SimpleDeclaration
     |   |-SimpleDeclarator
     |   | |-foo
     |   | `-ParametersAndQualifiers
     |   |   |-(
     |   |   `-)
     |   `-;
     |-}
     `-;
-)txt"},
-      {R"cpp(
-template <class T> struct X {};
-template <class T> struct X<T*> {};
-template <> struct X<int> {};
+)txt");
+}
 
-template struct X<double>;
-extern template struct X<float>;
-)cpp",
-       R"txt(
-*: TranslationUnit
-|-TemplateDeclaration
-| |-template
-| |-<
-| |-UnknownDeclaration
-| | |-class
-| | `-T
-| |->
-| `-SimpleDeclaration
-|   |-struct
-|   |-X
-|   |-{
-|   |-}
-|   `-;
-|-TemplateDeclaration
-| |-template
-| |-<
-| |-UnknownDeclaration
-| | |-class
-| | `-T
-| |->
-| `-SimpleDeclaration
-|   |-struct
-|   |-X
-|   |-<
-|   |-T
-|   |-*
-|   |->
-|   |-{
-|   |-}
-|   `-;
-|-TemplateDeclaration
-| |-template
-| |-<
-| |->
-| `-SimpleDeclaration
-|   |-struct
-|   |-X
-|   |-<
-|   |-int
-|   |->
-|   |-{
-|   |-}
-|   `-;
-|-ExplicitTemplateInstantiation
-| |-template
-| `-SimpleDeclaration
-|   |-struct
-|   |-X
-|   |-<
-|   |-double
-|   |->
-|   `-;
-`-ExplicitTemplateInstantiation
-  |-extern
-  |-template
-  `-SimpleDeclaration
-    |-struct
-    |-X
-    |-<
-    |-float
-    |->
-    `-;
-)txt"},
-      {R"cpp(
+TEST_F(SyntaxTreeTest, Templates2) {
+  expectTreeDumpEqual(
+      R"cpp(
 template <class T> struct X { struct Y; };
 template <class T> struct X<T>::Y {};
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-TemplateDeclaration
 | |-template
 | |-<
 | |-UnknownDeclaration
 | | |-class
 | | `-T
 | |->
`-SimpleDeclaration
     |-<
     |-T
     |->
     |-::
     |-Y
     |-{
     |-}
     `-;
-       )txt"},
-      {R"cpp(
-namespace ns {}
-using namespace ::ns;
-    )cpp",
-       R"txt(
-*: TranslationUnit
-|-NamespaceDefinition
-| |-namespace
-| |-ns
-| |-{
-| `-}
-`-UsingNamespaceDirective
-  |-using
-  |-namespace
-  |-::
-  |-ns
-  `-;
-       )txt"},
-      {R"cpp(
-namespace ns { int a; }
-using ns::a;
-    )cpp",
-       R"txt(
-*: TranslationUnit
-|-NamespaceDefinition
-| |-namespace
-| |-ns
-| |-{
-| |-SimpleDeclaration
-| | |-int
-| | |-SimpleDeclarator
-| | | `-a
-| | `-;
-| `-}
-`-UsingDeclaration
-  |-using
-  |-ns
-  |-::
-  |-a
-  `-;
-       )txt"},
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, TemplatesUsingUsing) {
+  expectTreeDumpEqual(
+      R"cpp(
 template <class T> struct X {
   using T::foo;
   using typename T::bar;
 };
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-TemplateDeclaration
   |-template
   |-<
   |-UnknownDeclaration
   | |-class
   | `-T
   |->
`-SimpleDeclaration
     | |-using
     | |-typename
     | |-T
     | |-::
     | |-bar
     | `-;
     |-}
     `-;
-       )txt"},
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, ExplicitTemplateInstantations) {
+  expectTreeDumpEqual(
+      R"cpp(
+template <class T> struct X {};
+template <class T> struct X<T*> {};
+template <> struct X<int> {};
+
+template struct X<double>;
+extern template struct X<float>;
+)cpp",
+      R"txt(
+*: TranslationUnit
+|-TemplateDeclaration
+| |-template
+| |-<
+| |-UnknownDeclaration
+| | |-class
+| | `-T
+| |->
+| `-SimpleDeclaration
+|   |-struct
+|   |-X
+|   |-{
+|   |-}
+|   `-;
+|-TemplateDeclaration
+| |-template
+| |-<
+| |-UnknownDeclaration
+| | |-class
+| | `-T
+| |->
+| `-SimpleDeclaration
+|   |-struct
+|   |-X
+|   |-<
+|   |-T
+|   |-*
+|   |->
+|   |-{
+|   |-}
+|   `-;
+|-TemplateDeclaration
+| |-template
+| |-<
+| |->
+| `-SimpleDeclaration
+|   |-struct
+|   |-X
+|   |-<
+|   |-int
+|   |->
+|   |-{
+|   |-}
+|   `-;
+|-ExplicitTemplateInstantiation
+| |-template
+| `-SimpleDeclaration
+|   |-struct
+|   |-X
+|   |-<
+|   |-double
+|   |->
+|   `-;
+`-ExplicitTemplateInstantiation
+  |-extern
+  |-template
+  `-SimpleDeclaration
+    |-struct
+    |-X
+    |-<
+    |-float
+    |->
+    `-;
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, UsingType) {
+  expectTreeDumpEqual(
+      R"cpp(
 using type = int;
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-TypeAliasDeclaration
   |-using
   |-type
   |-=
   |-int
   `-;
-       )txt"},
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, EmptyDeclaration) {
+  expectTreeDumpEqual(
+      R"cpp(
 ;
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-EmptyDeclaration
   `-;
-       )txt"},
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, StaticAssert) {
+  expectTreeDumpEqual(
+      R"cpp(
 static_assert(true, "message");
 static_assert(true);
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-StaticAssertDeclaration
 | |-static_assert
 | |-(
 | |-UnknownExpression
 | | `-true
 | |-,
 | |-UnknownExpression
 | | `-"message"
 | |-)
 | `-;
 `-StaticAssertDeclaration
   |-static_assert
   |-(
   |-UnknownExpression
   | `-true
   |-)
   `-;
-       )txt"},
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, ExternC) {
+  expectTreeDumpEqual(
+      R"cpp(
 extern "C" int a;
 extern "C" { int b; int c; }
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-LinkageSpecificationDeclaration
 | |-extern
 | |-"C"
 | `-SimpleDeclaration
 |   |-int
 |   |-SimpleDeclarator
 |   | `-a
 |   `-;
 `-LinkageSpecificationDeclaration
   |-extern
   |-"C"
   |-{
   |-SimpleDeclaration
   | |-int
   | |-SimpleDeclarator
   | | `-b
   | `-;
   |-SimpleDeclaration
   | |-int
   | |-SimpleDeclarator
   | | `-c
   | `-;
   `-}
-       )txt"},
-      // Some nodes are non-modifiable, they are marked with 'I:'.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, NonModifiableNodes) {
+  expectTreeDumpEqual(
+      R"cpp(
 #define HALF_IF if (1+
 #define HALF_IF_2 1) {}
 void test() {
   HALF_IF HALF_IF_2 else {}
 })cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
`-CompoundStatement
     | |-I: CompoundStatement
     | | |-I: {
     | | `-I: }
     | |-else
     | `-CompoundStatement
     |   |-{
     |   `-}
     `-}
-       )txt"},
-      // All nodes can be mutated.
-      {R"cpp(
+       )txt");
+  expectTreeDumpEqual(
+      R"cpp(
 #define OPEN {
 #define CLOSE }
 
 void test() {
   OPEN
     1;
   CLOSE
 
   OPEN
     2;
   }
 }
 )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-test
   | `-ParametersAndQualifiers
   |   |-(
   |   `-)
`-CompoundStatement
     |-CompoundStatement
     | |-{
     | |-ExpressionStatement
     | | |-UnknownExpression
     | | | `-2
     | | `-;
     | `-}
     `-}
-       )txt"},
-      // Array subscripts in declarators.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, ArraySubscriptsInDeclarators) {
+  expectTreeDumpEqual(
+      R"cpp(
 int a[10];
 int b[1][2][3];
 int c[] = {1,2,3};
 void f(int xs[static 10]);
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-int
 | |-SimpleDeclarator
 | | |-a
 | | `-ArraySubscript
 | |   |-[
 | |   |-UnknownExpression
`-SimpleDeclaration
   |   |   `-ArraySubscript
   |   |     |-[
   |   |     |-static
   |   |     |-UnknownExpression
   |   |     | `-10
   |   |     `-]
   |   `-)
   `-;
-       )txt"},
-      // Parameter lists in declarators.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, ParameterListsInDeclarators) {
+  expectTreeDumpEqual(
+      R"cpp(
 int a() const;
 int b() volatile;
 int c() &;
 int d() &&;
 int foo(int a, int b);
 int foo(
   const int a,
   volatile int b,
   const volatile int c,
   int* d,
   int& e,
   int&& f
 );
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-int
 | |-SimpleDeclarator
 | | |-a
 | | `-ParametersAndQualifiers
 | |   |-(
 | |   |-)
`-SimpleDeclaration
   |   |-,
   |   |-SimpleDeclaration
   |   | |-int
   |   | `-SimpleDeclarator
   |   |   |-&&
   |   |   `-f
   |   `-)
   `-;
-       )txt"},
-      // Trailing const qualifier.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, TrailingConst) {
+  expectTreeDumpEqual(
+      R"cpp(
 struct X {
   int foo() const;
 }
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-struct
   |-X
   |-{
   |-SimpleDeclaration
   | |-int
   | |-SimpleDeclarator
   | | |-foo
   | | `-ParametersAndQualifiers
   | |   |-(
   | |   |-)
   | |   `-const
   | `-;
   `-}
-    )txt"},
-      // Trailing return type in parameter lists.
-      {R"cpp(
+    )txt");
+}
+
+TEST_F(SyntaxTreeTest, TrailingReturn) {
+  expectTreeDumpEqual(
+      R"cpp(
 auto foo() -> int;
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-auto
   |-SimpleDeclarator
   | |-foo
   | `-ParametersAndQualifiers
   |   |-(
   |   |-)
   |   `-TrailingReturnType
   |     |-->
   |     `-int
   `-;
-       )txt"},
-      // Exception specification in parameter lists.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, ExceptionSpecification) {
+  expectTreeDumpEqual(
+      R"cpp(
 int a() noexcept;
 int b() noexcept(true);
 int c() throw();
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-int
 | |-SimpleDeclarator
 | | |-a
 | | `-ParametersAndQualifiers
 | |   |-(
 | |   |-)
`-SimpleDeclaration
   | |-c
   | `-ParametersAndQualifiers
   |   |-(
   |   |-)
   |   |-throw
   |   |-(
   |   `-)
   `-;
-       )txt"},
-      // Declarators in parentheses.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, DeclaratorsInParentheses) {
+  expectTreeDumpEqual(
+      R"cpp(
 int (a);
 int *(b);
 int (*c)(int);
 int *(d)(int);
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-int
 | |-SimpleDeclarator
 | | `-ParenDeclarator
 | |   |-(
 | |   |-a
 | |   `-)
`-SimpleDeclaration
   | | |-d
   | | `-)
   | `-ParametersAndQualifiers
   |   |-(
   |   |-SimpleDeclaration
   |   | `-int
   |   `-)
   `-;
-       )txt"},
-      // CV qualifiers.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, ConstVolatileQualifiers) {
+  expectTreeDumpEqual(
+      R"cpp(
 const int west = -1;
 int const east = 1;
 const int const universal = 0;
 const int const *const *volatile b;
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-const
 | |-int
 | |-SimpleDeclarator
 | | |-west
 | | |-=
 | | `-UnknownExpression
`-SimpleDeclaration
   |-const
   |-SimpleDeclarator
   | |-*
   | |-const
   | |-*
   | |-volatile
   | `-b
   `-;
-       )txt"},
-      // Ranges of declarators with trailing return types.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, RangesOfDeclaratorsWithTrailingReturnTypes) {
+  expectTreeDumpEqual(
+      R"cpp(
 auto foo() -> auto(*)(int) -> double*;
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-auto
   |-SimpleDeclarator
   | |-foo
   | `-ParametersAndQualifiers
   |   |-(
   |   |-)
`-SimpleDeclaration
   |         | `-int
   |         |-)
   |         `-TrailingReturnType
   |           |-->
   |           |-double
   |           `-SimpleDeclarator
   |             `-*
   `-;
-       )txt"},
-      // Member pointers.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, MemberPointers) {
+  expectTreeDumpEqual(
+      R"cpp(
 struct X {};
 int X::* a;
 const int X::* b;
     )cpp",
-       R"txt(
 *: TranslationUnit
 |-SimpleDeclaration
 | |-struct
 | |-X
 | |-{
 | |-}
 | `-;
 |-SimpleDeclaration
`-SimpleDeclaration
   |-int
   |-SimpleDeclarator
   | |-MemberPointer
   | | |-X
   | | |-::
   | | `-*
   | `-b
   `-;
-       )txt"},
-      // All-in-one tests.
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, ComplexDeclarator) {
+  expectTreeDumpEqual(
+      R"cpp(
 void x(char a, short (*b)(int));
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-x
   | `-ParametersAndQualifiers
   |   |-(
   |   |-SimpleDeclaration
`-SimpleDeclaration
   |   |   | `-)
   |   |   `-ParametersAndQualifiers
   |   |     |-(
   |   |     |-SimpleDeclaration
   |   |     | `-int
   |   |     `-)
   |   `-)
   `-;
-       )txt"},
-      {R"cpp(
+       )txt");
+}
+
+TEST_F(SyntaxTreeTest, ComplexDeclarator2) {
+  expectTreeDumpEqual(
+      R"cpp(
 void x(char a, short (*b)(int), long (**c)(long long));
     )cpp",
-       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-void
   |-SimpleDeclarator
   | |-x
   | `-ParametersAndQualifiers
   |   |-(
   |   |-SimpleDeclaration
`-SimpleDeclaration
   |   |   `-ParametersAndQualifiers
   |   |     |-(
   |   |     |-SimpleDeclaration
   |   |     | |-long
   |   |     | `-long
   |   |     `-)
   |   `-)
   `-;
-       )txt"},
-  };
-
-  for (const auto &T : Cases) {
-    SCOPED_TRACE(T.first);
-
-    auto *Root = buildTree(T.first);
-    std::string Expected = llvm::StringRef(T.second).trim().str();
-    std::string Actual =
-        std::string(llvm::StringRef(Root->dump(*Arena)).trim());
-    EXPECT_EQ(Expected, Actual) << "the resulting dump is:\n" << Actual;
-  }
+       )txt");
 }
 
 TEST_F(SyntaxTreeTest, Mutations) {
   using Transformation = std::function<void(
       const llvm::Annotations & /*Input*/, syntax::TranslationUnit * /*Root*/)>;
   auto CheckTransformation = [this](std::string Input, std::string Expected,
                                     Transformation Transform) -> void {
     llvm::Annotations Source(Input);

llvm/include/llvm/IR/ModuleSummaryIndex.h

FunctionSummary calculateCallGraphRoot() {
     if (Edges.empty()) {
       // Failed to find root - return an empty node
       return FunctionSummary::makeDummyFunctionSummary({});
     }
     auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
     return CallGraphRoot;
   }
 
+  bool hasSimilarFunction(unsigned id) { return SimilarFunctions.count(id); }
+
+  void addToSimilarFunctions(unsigned id, GlobalValue::GUID GUID) {
+    if (id == 0)
+      return; // invalid id.
+    if (DuplicateFunctions.count(GUID))
+      return;
+    ValueInfo VI = getValueInfo(GUID);
+    if (!VI)
+      return;
+    // assert(VI.getSummaryList().size() == 1);
+    if (VI.getSummaryList().size() != 1)
+      return;
+    GlobalValueSummary *S = VI.getSummaryList()[0].get();
+    if (!isa<FunctionSummary>(S))
+      return;
+    assert(isa<FunctionSummary>(S) && "Not a function summary!");
+    if (FunctionSimilarityHashes.count(GUID)) {
+      // Erase the GUID having multiple visits in the ModuleSummaryIndex.
+      FunctionSimilarityHashes.erase(GUID);
+      DuplicateFunctions.insert(GUID);
+      return;
+    }
+
+    FunctionSimilarityHashes[GUID] = id;
+  }
+
+  void populateReverseSimilarityHashMap() {
+    for (auto &p : FunctionSimilarityHashes)
+      SimilarFunctions[p.second].push_back(p.first);
+  }
+
+  void removeSingleEntriesFromSimHashMaps() {
+    // Iterate over the hash to remove entries with no duplicates.
+    for (auto I = SimilarFunctions.begin(), E = SimilarFunctions.end();
+         I != E;) {
+      auto Next = std::next(I);
+      assert(I->second.size() && "Empty Entry!");
+      if (I->second.size() == 1) {
+        FunctionSimilarityHashes.erase(I->second[0]);
+        SimilarFunctions.erase(I);
+      }
+      I = Next;
+    }
+  }
+
+  std::map<unsigned, std::vector<GlobalValue::GUID>> &getSimilarFunctions() {
+    return SimilarFunctions;
+  }
+
+  const std::map<unsigned, std::vector<GlobalValue::GUID>> &
+  getSimilarFunctions() const {
+    return SimilarFunctions;
+  }
+
+  unsigned getSimilarityHash(GlobalValue::GUID ID) const {
+    return FunctionSimilarityHashes.find(ID)->second;
+  }
+
+  std::map<GlobalValue::GUID, unsigned> &getSimilarFunctionsHash() {
+    return FunctionSimilarityHashes;
+  }
+
+  const std::map<GlobalValue::GUID, unsigned> &getSimilarFunctionsHash() const {
+    return FunctionSimilarityHashes;
+  }
+
+  void addToHostSimilarFunction(GlobalValue::GUID ID) {
+    HostSimilarFunction.insert(ID);
+  }
+
+  std::set<GlobalValue::GUID> &getHostSimilarFunction() {
+    return HostSimilarFunction;
+  }
+
+  const std::set<GlobalValue::GUID> &getHostSimilarFunction() const {
+    return HostSimilarFunction;
+  }
+
   bool withGlobalValueDeadStripping() const {
     return WithGlobalValueDeadStripping;
   }
   void setWithGlobalValueDeadStripping() {
     WithGlobalValueDeadStripping = true;
   }
 
   bool withAttributePropagation() const { return WithAttributePropagation; }

llvm/include/llvm/InitializePasses.h

 void initializeMemCpyOptLegacyPassPass(PassRegistry&);
 void initializeMemDepPrinterPass(PassRegistry&);
 void initializeMemDerefPrinterPass(PassRegistry&);
 void initializeMemoryDependenceWrapperPassPass(PassRegistry&);
 void initializeMemorySSAPrinterLegacyPassPass(PassRegistry&);
 void initializeMemorySSAWrapperPassPass(PassRegistry&);
 void initializeMemorySanitizerLegacyPassPass(PassRegistry&);
 void initializeMergeFunctionsLegacyPassPass(PassRegistry&);
+void initializeMergeFunctionsPass(PassRegistry&);
+void initializeMergeSimilarFunctionsPass(PassRegistry&);
 void initializeMergeICmpsLegacyPassPass(PassRegistry &);
 void initializeMergedLoadStoreMotionLegacyPassPass(PassRegistry&);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeModuleSummaryIndexWrapperPassPass(PassRegistry&);
 void initializeModuloScheduleTestPass(PassRegistry&);
 void initializeMustExecutePrinterPass(PassRegistry&);
 void initializeMustBeExecutedContextPrinterPass(PassRegistry&);

llvm/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createPostDomTree();
       (void) llvm::createInstructionNamerPass();
       (void) llvm::createMetaRenamerPass();
       (void) llvm::createAttributorLegacyPass();
       (void) llvm::createAttributorCGSCCLegacyPass();
       (void) llvm::createPostOrderFunctionAttrsLegacyPass();
       (void) llvm::createReversePostOrderFunctionAttrsPass();
       (void) llvm::createMergeFunctionsPass();
+      (void) llvm::createMergeSimilarFunctionsPass();
       (void) llvm::createMergeICmpsLegacyPass();
       (void) llvm::createExpandMemCmpPass();
       std::string buf;
       llvm::raw_string_ostream os(buf);
       (void) llvm::createPrintModulePass(os);
       (void) llvm::createPrintFunctionPass(os);
       (void) llvm::createModuleDebugInfoPrinterPass();
       (void) llvm::createPartialInliningPass();

llvm/include/llvm/Transforms/IPO.h

 ModulePass *createMergeFunctionsPass();
 
 //===----------------------------------------------------------------------===//
 /// createHotColdSplittingPass - This pass outlines cold blocks into a separate
 /// function(s).
 ModulePass *createHotColdSplittingPass();
 
 //===----------------------------------------------------------------------===//
+/// createMergeSimilarFunctionsPass - This pass discovers similar functions and
+/// merges them.
+///
+ModulePass *
+createMergeSimilarFunctionsPass(const ModuleSummaryIndex *S = nullptr);
+
+//===----------------------------------------------------------------------===//
 /// createPartialInliningPass - This pass inlines parts of functions.
 ///
 ModulePass *createPartialInliningPass();
 
 //===----------------------------------------------------------------------===//
 /// createBarrierNoopPass - This pass is purely a module pass barrier in a pass
 /// manager.
 ModulePass *createBarrierNoopPass();

llvm/include/llvm/Transforms/Utils/Cloning.h

 /// non-null.
 ///
 /// VMap contains no non-identity GlobalValue mappings and debug info metadata
 /// will not be cloned.
 ///
 Function *CloneFunction(Function *F, ValueToValueMapTy &VMap,
                         ClonedCodeInfo *CodeInfo = nullptr);
 
+/// Used to control @fn CloneFunctionInto.
+enum class CloneType {
+  InvalidCloneType,
+  /// Cloning will result in module level changes.
+  ModuleLevelChanges,
+  /// !ModuleLevelChanges, When no module level changes will be made to the
+  /// cloned function.
+  NoModuleLevelChanges,
+  /// Cloning will be used for extracting functions by passes like function
+  /// merging, it does not require module level changes but debug info needs
+  /// special treatment like: DISubprogram is not cloned.
+  ExtractingFunctions,
+};
+
 /// Clone OldFunc into NewFunc, transforming the old arguments into references
 /// to VMap values.  Note that if NewFunc already has basic blocks, the ones
 /// cloned into it will be added to the end of the function.  This function
 /// fills in a list of return instructions, and can optionally remap types
 /// and/or append the specified suffix to all values cloned.
 ///
 /// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue
 /// mappings.
 ///
 void CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
-                       ValueToValueMapTy &VMap, bool ModuleLevelChanges,
+                       ValueToValueMapTy &VMap, CloneType CT,
                        SmallVectorImpl<ReturnInst*> &Returns,
                        const char *NameSuffix = "",
                        ClonedCodeInfo *CodeInfo = nullptr,
                        ValueMapTypeRemapper *TypeMapper = nullptr,
                        ValueMaterializer *Materializer = nullptr);
 
 void CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
                                const Instruction *StartingInst,

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

cl::values(clEnumValN(FunctionSummary::FSHT_None, "none", "None."),
                           "all-non-critical", "All non-critical edges."),
                clEnumValN(FunctionSummary::FSHT_All, "all", "All edges.")));
 
 cl::opt<std::string> ModuleSummaryDotFile(
     "module-summary-dot-file", cl::init(""), cl::Hidden,
     cl::value_desc("filename"),
     cl::desc("File to emit dot graph of new summary into."));
 
+cl::opt<bool> UseGlobalAliases(
+    "mergesimilarfunc-global-aliases", cl::Hidden, cl::init(false),
+    cl::desc("Enable writing alias by enabling global aliases"));
+
+cl::opt<unsigned> MergeMinInsts(
+    "mergesimilarfunc-min-insts", cl::Hidden, cl::init(4),
+    cl::desc("Min instructions required to even consider single block fns"));
+
+// Minimize the name pollution caused by the enum values.
+namespace Opt {
+cl::opt<enum MergeLevelEnum> MergeLevel(
+    "mergesimilarfunc-level", cl::Hidden, cl::ZeroOrMore,
+    cl::desc("Level of function merging:"), cl::init(size),
+    cl::values(clEnumVal(none, "function merging disabled"),
+               clEnumVal(size, "only try to merge functions that are optimized "
+                               "for size"),
+               clEnumVal(all, "attempt to merge all similar functions")));
+}
+
+namespace llvm {
+
+static const char *MERGED_SUFFIX = "__merged";
+
+/// Returns the type id for a type to be hashed. We turn pointer types into
+/// integers here because the actual compare logic below considers pointers and
+/// integers of the same size as equal.
+static Type::TypeID getTypeIDForHash(Type *Ty) {
+  if (Ty->isPointerTy())
+    return Type::IntegerTyID;
+  return Ty->getTypeID();
+}
+
+bool isAliasCapable(const Function* G) {
+  return
+    UseGlobalAliases && G->hasGlobalUnnamedAddr()
+    && (G->hasExternalLinkage() || G->hasLocalLinkage() || G->hasWeakLinkage());
+}
+
+bool isComparisonCandidate(const Function *F) {
+  if (Opt::MergeLevel == Opt::size) {
+    // Only consider functions that are to be optimized for size.
+    // By default, that is all functions at -Os/-Oz and nothing at -O2.
+    bool Os = F->getAttributes().
+      hasAttribute(AttributeList::FunctionIndex, Attribute::OptimizeForSize);
+    bool Oz = F->getAttributes().
+      hasAttribute(AttributeList::FunctionIndex, Attribute::MinSize);
+    if (!Os && !Oz)
+      return false;
+  }
+
+  // Ignore declarations and tiny functions - no point in merging those
+  if (F->isDeclaration()) return false;
+  if (F->getName().endswith(MERGED_SUFFIX)) return false;
+  if (F->hasAvailableExternallyLinkage()) return false;
+  if (F->hasFnAttribute(Attribute::AlwaysInline)) return false;
+  if (F->size() == 1 && F->begin()->size() < MergeMinInsts)
+    return isAliasCapable(F);
+
+  return true;
+}
+
+unsigned profileFunction(const Function *F) {
+  FunctionType *FTy = F->getFunctionType();
+  if (!isComparisonCandidate(F))
+    return 0;
+  if (F->hasGC() || FTy->isVarArg() || !F->hasExactDefinition())
+    return 0;
+  FoldingSetNodeID ID;
+  ID.AddInteger(F->size());
+  ID.AddInteger(F->getCallingConv());
+  // Add pure attribute, has side-effects attribute.
+  ID.AddBoolean(F->hasFnAttribute(Attribute::NoUnwind));
+  ID.AddBoolean(F->hasFnAttribute(Attribute::NoReturn));
+  //ID.AddBoolean(F->hasGC());
+  //ID.AddBoolean(F->isInterposable());
+  //ID.AddBoolean(FTy->isVarArg());
+  ID.AddInteger(getTypeIDForHash(FTy->getReturnType()));
+  for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
+    ID.AddInteger(getTypeIDForHash(FTy->getParamType(i)));
+  return ID.ComputeHash();
+}
+}
+
 // Walk through the operands of a given User via worklist iteration and populate
 // the set of GlobalValue references encountered. Invoked either on an
 // Instruction or a GlobalVariable (which walks its initializer).
 // Return true if any of the operands contains blockaddress. This is important
 // to know when computing summary for global var, because if global variable
 // references basic block address we can't import it separately from function
 // containing that basic block. For simplicity we currently don't import such
 // global vars at all. When importing function we aren't interested if any
GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
                                     /* Live = */ false, F.isDSOLocal(),
                                     F.hasLinkOnceODRLinkage() && F.hasGlobalUnnamedAddr());
   FunctionSummary::FFlags FunFlags{
       F.hasFnAttribute(Attribute::ReadNone),
       F.hasFnAttribute(Attribute::ReadOnly),
       F.hasFnAttribute(Attribute::NoRecurse), F.returnDoesNotAlias(),
       // FIXME: refactor this to use the same code that inliner is using.
       // Don't try to import functions with noinline attribute.
-      F.getAttributes().hasFnAttribute(Attribute::NoInline),
-      F.hasFnAttribute(Attribute::AlwaysInline)};
+      F.getAttributes().hasFnAttribute(Attribute::NoInline)};
   auto FuncSummary = std::make_unique<FunctionSummary>(
       Flags, NumInsts, FunFlags, /*EntryCount=*/0, std::move(Refs),
       CallGraphEdges.takeVector(), TypeTests.takeVector(),
       TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
       TypeTestAssumeConstVCalls.takeVector(),
       TypeCheckedLoadConstVCalls.takeVector());
   if (NonRenamableLocal)
     CantBePromoted.insert(F.getGUID());

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

// Parse version
     Expected<unsigned> MaybeRecord = Stream.readRecord(Entry.ID, Record);
     if (!MaybeRecord)
       return MaybeRecord.takeError();
     if (MaybeRecord.get() != bitc::FS_VERSION)
       return error("Invalid Summary Block: version expected");
   }
   const uint64_t Version = Record[0];
   const bool IsOldProfileFormat = Version == 1;
-  if (Version < 1 || Version > ModuleSummaryIndex::BitcodeSummaryVersion)
+  if (Version < 1 || Version > 7)
     return error("Invalid summary version " + Twine(Version) +
-                 ". Version should be in the range [1-" +
-                 Twine(ModuleSummaryIndex::BitcodeSummaryVersion) +
-                 "].");
+                 ". Version should be in the range [1-7].");
   Record.clear();
 
   // Keep around the last seen summary to be used when we see an optional
   // "OriginalName" attachement.
   GlobalValueSummary *LastSeenSummary = nullptr;
   GlobalValue::GUID LastSeenGUID = 0;
 
   // We can expect to see any number of type ID information records before
case bitc::FS_PERMODULE_PROFILE: {
       setSpecialRefs(Refs, NumRORefs, NumWORefs);
       auto FS = std::make_unique<FunctionSummary>(
           Flags, InstCount, getDecodedFFlags(RawFunFlags), /*EntryCount=*/0,
           std::move(Refs), std::move(Calls), std::move(PendingTypeTests),
           std::move(PendingTypeTestAssumeVCalls),
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
           std::move(PendingTypeCheckedLoadConstVCalls));
+      PendingTypeTests.clear();
+      PendingTypeTestAssumeVCalls.clear();
+      PendingTypeCheckedLoadVCalls.clear();
+      PendingTypeTestAssumeConstVCalls.clear();
+      PendingTypeCheckedLoadConstVCalls.clear();
       auto VIAndOriginalGUID = getValueInfoFromValueId(ValueID);
       FS->setModulePath(getThisModule()->first());
       FS->setOriginalName(VIAndOriginalGUID.second);
       TheIndex.addGlobalValueSummary(VIAndOriginalGUID.first, std::move(FS));
       break;
     }
     // FS_ALIAS: [valueid, flags, valueid]
     // Aliases must be emitted (and parsed) after all FS_PERMODULE entries, as
case bitc::FS_COMBINED_PROFILE: {
       setSpecialRefs(Refs, NumRORefs, NumWORefs);
       auto FS = std::make_unique<FunctionSummary>(
           Flags, InstCount, getDecodedFFlags(RawFunFlags), EntryCount,
           std::move(Refs), std::move(Edges), std::move(PendingTypeTests),
           std::move(PendingTypeTestAssumeVCalls),
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
           std::move(PendingTypeCheckedLoadConstVCalls));
+      PendingTypeTests.clear();
+      PendingTypeTestAssumeVCalls.clear();
+      PendingTypeCheckedLoadVCalls.clear();
+      PendingTypeTestAssumeConstVCalls.clear();
+      PendingTypeCheckedLoadConstVCalls.clear();
       LastSeenSummary = FS.get();
       LastSeenGUID = VI.getGUID();
       FS->setModulePath(ModuleIdMap[ModuleId]);
       TheIndex.addGlobalValueSummary(VI, std::move(FS));
       break;
     }
     // FS_COMBINED_ALIAS: [valueid, modid, flags, valueid]
     // Aliases must be emitted (and parsed) after all FS_COMBINED entries, as

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

else {
     }
 
     Stream.EmitRecord(bitc::FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS, NameVals,
                       FSModVTableRefsAbbrev);
   }
   NameVals.clear();
 }
 
+// Current version for the summary.
+// This is bumped whenever we introduce changes in the way some record are
+// interpreted, like flags for instance.
+static const uint64_t INDEX_VERSION = 7;
+
 /// Emit the per-module summary section alongside the rest of
 /// the module's bitcode.
 void ModuleBitcodeWriterBase::writePerModuleGlobalValueSummary() {
   // By default we compile with ThinLTO if the module has a summary, but the
   // client can request full LTO with a module flag.
   bool IsThinLTO = true;
   if (auto *MD =
           mdconst::extract_or_null<ConstantInt>(M.getModuleFlag("ThinLTO")))

llvm/lib/ExecutionEngine/Orc/IndirectionUtils.cpp

void moveFunctionBody(Function &OrigF, ValueToValueMapTy &VMap,
   else
     assert(VMap[&OrigF] == NewF && "Incorrect function mapping in VMap.");
   assert(NewF && "Function mapping missing from VMap.");
   assert(NewF->getParent() != OrigF.getParent() &&
          "moveFunctionBody should only be used to move bodies between "
          "modules.");
 
   SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned.
-  CloneFunctionInto(NewF, &OrigF, VMap, /*ModuleLevelChanges=*/true, Returns,
+  CloneFunctionInto(NewF, &OrigF, VMap, CloneType::ModuleLevelChanges, Returns,
                     "", nullptr, nullptr, Materializer);
   OrigF.deleteBody();
 }
 
 GlobalVariable* cloneGlobalVariableDecl(Module &Dst, const GlobalVariable &GV,
                                         ValueToValueMapTy *VMap) {
   GlobalVariable *NewGV = new GlobalVariable(
       Dst, GV.getValueType(), GV.isConstant(),

llvm/lib/Target/AMDGPU/R600OpenCLImageTypeLoweringPass.cpp

for (auto &Arg: F->args()) {
       NewFArgIt->setName(ArgName);
       VMap[&Arg] = &(*NewFArgIt++);
       if (IsImageType(ArgTypeFromMD(KernelMDNode, Arg.getArgNo()))) {
         (NewFArgIt++)->setName(Twine("__size_") + ArgName);
         (NewFArgIt++)->setName(Twine("__format_") + ArgName);
       }
     }
     SmallVector<ReturnInst*, 8> Returns;
-    CloneFunctionInto(NewF, F, VMap, /*ModuleLevelChanges=*/false, Returns);
+    CloneFunctionInto(NewF, F, VMap, CloneType::NoModuleLevelChanges, Returns);
 
     // Build new MDNode.
     SmallVector<Metadata *, 6> KernelMDArgs;
     KernelMDArgs.push_back(ConstantAsMetadata::get(NewF));
     for (unsigned i = 0; i < NumKernelArgMDNodes; ++i)
       KernelMDArgs.push_back(MDNode::get(*Context, NewArgMDs.ArgVector[i]));
     MDNode *NewMDNode = MDNode::get(*Context, KernelMDArgs);
 

llvm/lib/Target/AMDGPU/SIRegisterInfo.cpp

default: {
         int64_t Offset = FrameInfo.getObjectOffset(Index);
         if (Offset == 0) {
           // XXX - This never happens because of emergency scavenging slot at 0?
           BuildMI(*MBB, MI, DL, TII->get(AMDGPU::V_LSHRREV_B32_e64), ResultReg)
             .addImm(ST.getWavefrontSizeLog2())
             .addReg(FrameReg);
         } else {
           if (auto MIB = TII->getAddNoCarry(*MBB, MI, DL, ResultReg, *RS)) {
-            Register ScaledReg =
-              RS->scavengeRegister(&AMDGPU::VGPR_32RegClass, MIB, 0);
+            // Reuse ResultReg in intermediate step.
+            Register ScaledReg = ResultReg;
 
             BuildMI(*MBB, *MIB, DL, TII->get(AMDGPU::V_LSHRREV_B32_e64),
                     ScaledReg)
               .addImm(ST.getWavefrontSizeLog2())
               .addReg(FrameReg);
 
             const bool IsVOP2 = MIB->getOpcode() == AMDGPU::V_ADD_U32_e32;
 

llvm/lib/Target/AMDGPU/SIRegisterInfo.td

 foreach Index = 0-105 in {
   def SGPR#Index :
     SIReg <"s"#Index, Index>,
     DwarfRegNum<[!if(!le(Index, 63), !add(Index, 32), !add(Index, 1024))]>;
 }
 
 // VGPR registers
 foreach Index = 0-255 in {
+  // Set a cost value for vgprs other than the argument registers (v0-v31).
+  // The ratio of index/allocation_granularity is taken as the cost value.
+  // Considered the allocation granularity as 4 here.
+  let CostPerUse=!if(!gt(Index, 31), !srl(Index, 2), 0) in {
   def VGPR#Index :
       SIReg <"v"#Index, Index>,
       DwarfRegNum<[!add(Index, 2560)]> {
     let HWEncoding{8} = 1;
   }
   }
+}
 
 // AccVGPR registers
 foreach Index = 0-255 in {
   def AGPR#Index :
       SIReg <"a"#Index, Index>,
       DwarfRegNum<[!add(Index, 3072)]> {
     let HWEncoding{8} = 1;
   }

llvm/lib/Transforms/Coroutines/CoroSplit.cpp

void CoroCloner::create() {
   auto savedDLLStorageClass = NewF->getDLLStorageClass();
 
   // NewF's linkage (which CloneFunctionInto does *not* change) might not
   // be compatible with the visibility of OrigF (which it *does* change),
   // so protect against that.
   auto savedLinkage = NewF->getLinkage();
   NewF->setLinkage(llvm::GlobalValue::ExternalLinkage);
 
-  CloneFunctionInto(NewF, &OrigF, VMap, /*ModuleLevelChanges=*/true, Returns);
+  CloneFunctionInto(NewF, &OrigF, VMap, CloneType::ModuleLevelChanges, Returns);
 
   NewF->setLinkage(savedLinkage);
   NewF->setVisibility(savedVisibility);
   NewF->setUnnamedAddr(savedUnnamedAddr);
   NewF->setDLLStorageClass(savedDLLStorageClass);
 
   auto &Context = NewF->getContext();
 

llvm/lib/Transforms/IPO/CMakeLists.txt

add_llvm_component_library(LLVMipo
   InferFunctionAttrs.cpp
   InlineSimple.cpp
   Inliner.cpp
   Internalize.cpp
   LoopExtractor.cpp
   LowerTypeTests.cpp
   MergeFunctions.cpp
   OpenMPOpt.cpp
+  MergeSimilarFunctions.cpp
   PartialInlining.cpp
   PassManagerBuilder.cpp
   PruneEH.cpp
   SampleProfile.cpp
   SCCP.cpp
   StripDeadPrototypes.cpp
   StripSymbols.cpp
   SyntheticCountsPropagation.cpp

llvm/lib/Transforms/IPO/IPO.cpp

void llvm::initializeIPO(PassRegistry &Registry) {
   initializeSimpleInlinerPass(Registry);
   initializeInferFunctionAttrsLegacyPassPass(Registry);
   initializeInternalizeLegacyPassPass(Registry);
   initializeLoopExtractorPass(Registry);
   initializeBlockExtractorPass(Registry);
   initializeSingleLoopExtractorPass(Registry);
   initializeLowerTypeTestsPass(Registry);
   initializeMergeFunctionsLegacyPassPass(Registry);
+  initializeMergeFunctionsPass(Registry);
+  initializeMergeSimilarFunctionsPass(Registry);
   initializePartialInlinerLegacyPassPass(Registry);
   initializeAttributorLegacyPassPass(Registry);
   initializeAttributorCGSCCLegacyPassPass(Registry);
   initializePostOrderFunctionAttrsLegacyPassPass(Registry);
   initializeReversePostOrderFunctionAttrsLegacyPassPass(Registry);
   initializePruneEHPass(Registry);
   initializeIPSCCPLegacyPassPass(Registry);
   initializeStripDeadPrototypesLegacyPassPass(Registry);

llvm/lib/Transforms/IPO/MergeSimilarFunctions.cpp

+//===- MergeSimilarFunctions.cpp - Merge similar functions ----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass merges both equivalent and similar functions to reduce code size.
+//
+// For a more detailed explanation of the approach, see:
+// Edler von Koch et al. "Exploiting Function Similarity for Code Size
+// Reduction", LCTES 2014.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "mergesimilarfunc"
+#include "llvm/Transforms/IPO.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InlineAsm.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include <vector>
+#include <list>
+using namespace llvm;
+
+STATISTIC(NumFunctionsMerged, "Number of functions merged");
+STATISTIC(NumThunksWritten, "Number of thunks generated");
+STATISTIC(NumAliasesWritten, "Number of aliases generated");
+STATISTIC(NumDoubleWeak, "Number of new functions created");
+STATISTIC(NumMultiMerged, "Number of multi-merged functions");
+
+STATISTIC(NumSimilarFunctionsMerged, "Number of similar functions merged");
+
+static cl::opt<unsigned> MergeMinInsts(
+    "mergesimilarfunc-min-insts", cl::Hidden, cl::init(4),
+    cl::desc("Min instructions required to even consider single block fns"));
+
+static cl::opt<unsigned> MergeDifferingMinInsts(
+    "mergesimilarfunc-diff-min-insts", cl::Hidden, cl::init(15),
+    cl::desc("Min instructions required to try merging differing functions"));
+
+static cl::opt<unsigned> MergeMaxDiffering(
+    "mergesimilarfunc-max-diff", cl::Hidden, cl::init(8),
+    cl::desc("Maximum number of differing instructions allowed"));
+
+static cl::opt<unsigned> MergeMinSimilarity(
+    "mergesimilarfunc-min-similarity", cl::Hidden, cl::init(70),
+    cl::desc("Minimum percentage of similar instructions required"));
+
+static cl::opt<bool> OptPrintMerges("mergesimilarfunc-print-merges", cl::Hidden,
+                                    cl::init(false));
+
+static cl::opt<bool> UseGlobalAliases(
+    "mergesimilarfunc-global-aliases", cl::Hidden, cl::init(false),
+    cl::desc("Enable writing alias by enabling global aliases"));
+
+void PrintMerges(const char *Desc, Function *Old, Function *New) {
+  if (OptPrintMerges) {
+    dbgs() << "=== [" << Desc << "] replacing " << Old->getName() << " with "
+           << New->getName() << "\n";
+  }
+}
+
+// Minimize the name pollution caused by the enum values.
+namespace Opt {
+enum MergeLevelEnum { none, size, all };
+static cl::opt<enum MergeLevelEnum> MergeLevel(
+    "mergesimilarfunc-level", cl::Hidden, cl::ZeroOrMore,
+    cl::desc("Level of function merging:"), cl::init(size),
+    cl::values(clEnumVal(none, "function merging disabled"),
+               clEnumVal(size, "only try to merge functions that are optimized "
+                               "for size"),
+               clEnumVal(all, "attempt to merge all similar functions")));
+}
+
+static const char *MERGED_SUFFIX = "__merged";
+
+/// Returns the type id for a type to be hashed. We turn pointer types into
+/// integers here because the actual compare logic below considers pointers and
+/// integers of the same size as equal.
+static Type::TypeID getTypeIDForHash(Type *Ty) {
+  if (Ty->isPointerTy())
+    return Type::IntegerTyID;
+  return Ty->getTypeID();
+}
+
+/// Creates a hash-code for the function which is the same for any two
+/// functions that will compare equal, without looking at the instructions
+/// inside the function.
+static unsigned profileFunction(const Function *F) {
+  FunctionType *FTy = F->getFunctionType();
+
+  FoldingSetNodeID ID;
+  ID.AddInteger(F->size());
+  ID.AddInteger(F->getCallingConv());
+  ID.AddBoolean(F->hasGC());
+  ID.AddBoolean(F->isInterposable());
+  ID.AddBoolean(FTy->isVarArg());
+  ID.AddInteger(getTypeIDForHash(FTy->getReturnType()));
+  for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
+    ID.AddInteger(getTypeIDForHash(FTy->getParamType(i)));
+  return ID.ComputeHash();
+}
+
+
+/// Replace Inst1 by a switch statement that executes Inst1 or one of Inst2s
+/// depending on the value of SwitchVal. If a value in Inst2s is NULL, it
+/// defaults to executing Inst1. Returns set of terminator instructions of newly
+/// created switch blocks in Ret.
+///
+/// For instance, the transformation may look as follows:
+///         ...Head...
+///           Inst1           with all of Insts2s without parents
+///         ...Tail...
+///  into
+///         ...Head...
+///           Switch
+///         /     |       \                    .
+///    (default) (1)       (2)
+///      Inst1   Inst2s[0] Inst2s[1]
+///     Ret[0]   Ret[1]    Ret[2]
+///        \      |       /
+///         ...Tail...
+///
+static void SplitBlockAndInsertSwitch(
+    Value *SwitchVal, Instruction *Inst1,
+    SmallVectorImpl<Instruction *> &Inst2s,
+    SmallVectorImpl<Instruction *> &Ret) {
+  // Split block
+  BasicBlock *Head = Inst1->getParent();
+  BasicBlock *Tail = Head->splitBasicBlock(Inst1);
+
+  // Create default block
+  LLVMContext &C = Head->getContext();
+  BasicBlock *DefaultBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
+
+  // Insert switch instruction at end of Head
+  Instruction *HeadOldTerm = Head->getTerminator();
+  SwitchInst *Switch = SwitchInst::Create(SwitchVal, DefaultBlock,
+                                               Inst2s.size());
+  ReplaceInstWithInst(HeadOldTerm, Switch);
+
+  // Move instructions into the blocks
+  if (Inst1->isTerminator()) {
+    Inst1->removeFromParent();
+    DefaultBlock->getInstList().push_back(Inst1);
+    Ret.push_back(cast<Instruction>(Inst1));
+  } else {
+    Instruction *DefaultTerm = BranchInst::Create(Tail, DefaultBlock);
+    Inst1->moveBefore(DefaultTerm);
+    Ret.push_back(DefaultTerm);
+  }
+
+  for (unsigned InstPos = 0, InstNum = Inst2s.size(); InstPos < InstNum;
+       ++InstPos) {
+    Instruction *Inst2 = Inst2s[InstPos];
+    if (!Inst2) {
+      Ret.push_back(NULL);
+      continue;
+    }
+
+    BasicBlock *CaseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
+
+    // Update the debug information of the merged instruction by marking it as
+    // 'inlined' at this location. If only Inst1 or Inst2 has debug
+    // information, we try to do something sensible that won't break the
+    // verifier.
+    if (Inst1->getDebugLoc()) {
+      if (Inst2->getDebugLoc()) {
+        const DebugLoc &I2Loc = Inst2->getDebugLoc();
+        Inst2->setDebugLoc(
+            DebugLoc::get(I2Loc.getLine(), I2Loc.getCol(), I2Loc.getScope(),
+                          /*InlinedAt*/ Inst1->getDebugLoc().getAsMDNode()));
+      } else {
+        Inst2->setDebugLoc(Inst1->getDebugLoc());
+      }
+    } else if (Inst2->getDebugLoc()) {
+      Inst2->setDebugLoc(DebugLoc());
+    }
+
+    if (Inst2->isTerminator()) {
+      assert(Inst1->isTerminator() &&
+        "Inst1 and Inst2 must both be terminators or non-terminators!");
+      CaseBlock->getInstList().push_back(Inst2);
+      Ret.push_back(cast<Instruction>(Inst2));
+    } else {
+      Instruction *CaseTerm = BranchInst::Create(Tail, CaseBlock);
+      Inst2->insertBefore(CaseTerm);
+      Ret.push_back(CaseTerm);
+    }
+
+    Switch->addCase(ConstantInt::get(cast<IntegerType>(SwitchVal->getType()),
+                                     InstPos+1),
+                    CaseBlock);
+  }
+
+  // If Inst1 (and Inst2s) are Terminator Inst's, Tail will be empty and can be
+  // deleted now. We also need to update PHI nodes to add the additional
+  // incoming blocks from the SwitchInst.
+  if (Inst1->isTerminator()) {
+    for (succ_iterator I = succ_begin(DefaultBlock), E = succ_end(DefaultBlock);
+         I != E; ++I) {
+      BasicBlock *Successor = *I;
+      PHINode *Phi;
+
+      for (BasicBlock::iterator II = Successor->begin();
+           (Phi = dyn_cast<PHINode>(II)); ++II)
+        for (unsigned ValId = 0, ValEnd = Phi->getNumIncomingValues();
+             ValId != ValEnd; ++ValId)
+          if (Phi->getIncomingBlock(ValId) == Tail) {
+            Phi->setIncomingBlock(ValId, DefaultBlock);
+            SmallVectorImpl<Instruction *>::iterator
+              SwitchI = Ret.begin(), SwitchE = Ret.end();
+            for (++SwitchI; SwitchI != SwitchE; ++SwitchI) {
+              if (!*SwitchI)
+                continue;
+              Phi->addIncoming(Phi->getIncomingValue(ValId),
+                               (*SwitchI)->getParent());
+            }
+          }
+    }
+
+    Tail->eraseFromParent();
+  }
+}
+
+/// Insert function NewF into module, placing it immediately after the
+/// existing function PredF. If PredF does not exist, insert at the end.
+static void insertFunctionAfter(Function *NewF, Function *PredF) {
+  Module *M = PredF->getParent();
+  Module::FunctionListType &FList = M->getFunctionList();
+
+  for (Module::FunctionListType::iterator I = FList.begin(), E = FList.end();
+      I != E; ++I) {
+    if (PredF == &*I) {
+      FList.insertAfter(I, NewF);
+      return;
+    }
+  }
+
+  // Couldn't find PredF, insert at end
+  FList.push_back(NewF);
+}
+
+/// Create a cast instruction if needed to cast V to type DstType. We treat
+/// pointer and integer types of the same bitwidth as equivalent, so this can be
+/// used to cast them to each other where needed. The function returns the Value
+/// itself if no cast is needed, or a new CastInst instance inserted before
+/// InsertBefore. The integer type equivalent to pointers must be passed as
+/// IntPtrType (get it from DataLayout). This is guaranteed to generate no-op
+/// casts, otherwise it will assert.
+static Value *createCastIfNeeded(Value *V, Type *DstType,
+                                 Value *InstrOrBB, Type *IntPtrType, const DataLayout *DL) {
+  if (V->getType() == DstType)
+    return V;
+
+  BasicBlock *InsertAtEnd = dyn_cast<BasicBlock>(InstrOrBB);
+  Instruction *InsertBefore = dyn_cast<Instruction>(InstrOrBB);
+  BasicBlock *InsertBB = InsertAtEnd ? InsertAtEnd : InsertBefore->getParent();
+
+  CastInst *Result;
+  Type *OrigType = V->getType();
+
+  if (OrigType->isStructTy()) {
+    assert(DstType->isStructTy());
+    assert(OrigType->getStructNumElements() == DstType->getStructNumElements());
+
+    IRBuilder<> Builder(InsertBB);
+    if (InsertBefore)
+      Builder.SetInsertPoint(InsertBefore);
+    Value *Result = UndefValue::get(DstType);
+    for (unsigned int I = 0, E = OrigType->getStructNumElements(); I < E; ++I) {
+      Value *ExtractedValue
+        = Builder.CreateExtractValue(V, ArrayRef<unsigned int>(I));
+      Value *Element = createCastIfNeeded(ExtractedValue,
+                                          DstType->getStructElementType(I),
+                                          InstrOrBB, IntPtrType, DL);
+      Result =
+          Builder.CreateInsertValue(Result, Element, ArrayRef<unsigned int>(I));
+    }
+    return Result;
+  }
+  assert(!DstType->isStructTy());
+
+  if (OrigType->isPointerTy()
+      && (DstType->isIntegerTy() || DstType->isPointerTy())) {
+    if (InsertBefore)
+      Result = CastInst::CreatePointerCast(V, DstType, "", InsertBefore);
+    else
+      Result = CastInst::CreatePointerCast(V, DstType, "", InsertAtEnd);
+  } else if (OrigType->isIntegerTy() && DstType->isPointerTy()
+             && OrigType == IntPtrType) {
+    // Int -> Ptr
+    if (InsertBefore) {
+      Result = CastInst::Create(CastInst::IntToPtr, V, DstType, "",
+                                InsertBefore);
+    } else {
+      Result = CastInst::Create(CastInst::IntToPtr, V, DstType, "",
+                                InsertAtEnd);
+    }
+  } else {
+    llvm_unreachable("Can only cast int -> ptr or ptr -> (ptr or int)");
+  }
+
+  assert(cast<CastInst>(Result)->isNoopCast(*DL) &&
+      "Cast is not a no-op cast. Potential loss of precision");
+
+  return Result;
+}
+
+namespace {
+
+/// ComparableFunction - A struct that pairs together functions with a
+/// DataLayout so that we can keep them together as elements in the DenseSet.
+class ComparableFunction {
+public:
+  ComparableFunction() : Func(0), IsNew(false) { }
+
+  ComparableFunction(const ComparableFunction &that)
+    : Func(that.Func), IsNew(that.IsNew) {
+  }
+
+  ComparableFunction(Function *Func) : Func(Func), IsNew(true) { }
+
+  ~ComparableFunction() { }
+
+  ComparableFunction &operator=(const ComparableFunction &that) {
+    Func = that.Func;
+    IsNew = that.IsNew;
+    return *this;
+  }
+
+  Function *getFunc() const { return Func; }
+  bool isNew() const { return IsNew; }
+
+  // Drops AssertingVH reference to the function. Outside of debug mode, this
+  // does nothing.
+  void release() {
+    assert(Func &&
+           "Attempted to release function twice, or release empty/tombstone!");
+    Func = NULL;
+  }
+
+  void markCompared() {
+    IsNew = false;
+  }
+private:
+  AssertingVH<Function> Func;
+  bool IsNew;
+};
+
+}
+
+namespace {
+
+/// FunctionComparator - Compares two functions to determine whether or not
+/// they will generate machine code with the same behaviour. DataLayout is
+/// used if available. The comparator always fails conservatively (erring on the
+/// side of claiming that two functions are different).
+class FunctionComparator {
+public:
+  FunctionComparator(const DataLayout *DL, Function *F1, Function *F2)
+    : isDifferent(false), isNotMergeable(false),
+      BasicBlockCount(0), InstructionCount(0), DifferingInstructionsCount(0),
+      F1(F1), F2(F2), SimilarityMetric(0), DL(DL), ID(CurID++) {}
+
+  ~FunctionComparator() {}
+
+  /// Test whether the two functions have equivalent behaviour. Returns true if
+  /// they are equal or can be merged, false if not.
+  bool compare();
+
+  /// Indicate whether the two functions are an exact match after comparison
+  bool isExactMatch();
+
+  /// Indicate whether the two functions candidates for merging after comparison
+  bool isMergeCandidate();
+
+  /// Get a similarity metric between the two functions. Higher means more
+  /// similar.
+  unsigned getSimilarityMetric() {
+    if (!SimilarityMetric)
+      SimilarityMetric = (unsigned)(((float)InstructionCount -
+            DifferingInstructionsCount)/InstructionCount*10000);
+    return SimilarityMetric;
+  }
+
+  Function *getF1() { return F1; }
+  Function *getF2() { return F2; }
+  ValueToValueMapTy &getF1toF2Map() { return id_map; }
+  ValueToValueMapTy &getF2toF1Map() { return seen_values; }
+  const DataLayout *getDataLayout() { return DL; }
+
+  /// Assign or look up previously assigned numbers for the two values, and
+  /// return whether the numbers are equal. Numbers are assigned in the order
+  /// visited. If NoSelfRef is set, F1 and F2 are not assigned to each other
+  /// (treated as 'equal').
+  bool enumerate(const Value *V1, const Value *V2, bool NoSelfRef=false);
+
+  /// Compare two Types, treating all pointer types as equal.
+  bool isEquivalentType(Type *Ty1, Type *Ty2) const;
+
+  /// Instructions that differ between the two functions (F1's -> F2's inst).
+  MapVector<const Instruction *, const Instruction *> DifferingInstructions;
+
+  /// Instructions that reference F1/F2 itself (recursive calls etc.)
+  /// These may need special treatment when merging differing functions.
+  MapVector<const Instruction *, const Instruction *> SelfRefInstructions;
+
+  /// Return the unique ID for the object.
+  unsigned getID() { return ID; }
+
+  bool isDifferent;
+  bool isNotMergeable;
+
+  // Comparison statistics
+  unsigned BasicBlockCount;
+  unsigned InstructionCount;
+  unsigned DifferingInstructionsCount;
+
+private:
+  /// Test whether two basic blocks have equivalent behaviour. Returns true if