[llvm-reduce] Add reduction for aliases and special globals.

[fhahn]

Summary

This patch adds a new reduction pass that tries to remove aliases and
special globals. It runs early, as most of those likely can be removed
up-front in practice.

This substantially improves llvm-reduce for IR generated by the swift
compiler, which can generate a lot of aliases and special globals, which
lead to lots of invalid reductions.

Removing aliases and special globals together is mostly done for
convenience, because both show up in IR generated by the swift compiler.

I am not sure if it is feasible to add a test case where globals cause problems,
because I think they only cause problems on large inputs where we spend a lot
of time removing globals in llvm.used & co.

[arsenm]

llvm/tools/llvm-reduce/deltas/ReduceAliasAndSpecialGlobals.cpp

21 ↗

(On Diff #301085)

I almost think reducing these should be a separate step

32 ↗

(On Diff #301085)

Would it make more sense to replace this with the aliasee as a first step, and rely on ordinary global reduction as a separate phase?

[lebedev.ri]

I agree with @arsenm here.

llvm/tools/llvm-reduce/deltas/ReduceAliasAndSpecialGlobals.cpp

21 ↗

(On Diff #301085)

+1, the rest of the patch is obvious.

[fhahn]

Update patch to only include alias reduction.

[lebedev.ri]

LGTM, thanks. I was hitting this problem occasionaly, but didn't get to write this reduction.

llvm/tools/llvm-reduce/deltas/ReduceAliases.cpp

35–37

Comment needs updating

llvm/tools/llvm-reduce/deltas/ReduceAliases.h

2

Unsufficient ---- padding

12

missing //

[fhahn]

llvm/tools/llvm-reduce/deltas/ReduceAliasAndSpecialGlobals.cpp

21 ↗

(On Diff #301085)

Done, moved to D90302

32 ↗

(On Diff #301085)

The updated code now replaces the alias with the aliasee directly.

llvm/test/Reduce/remove-alias.ll

 ; RUN: llvm-reduce --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
 ; RUN: FileCheck --check-prefixes=CHECK-FINAL --input-file=%t %s
 
 ; Test handling of 'alias'.
 
 ; CHECK-INTERESTINGNESS: define void @fn3
 
 ; CHECK-FINAL: @g1 = global
 ; CHECK-FINAL: @g2 = global
 
-; CHECK-FINAL: $a1
-; CHECK-FINAL: $a2
-; CHECK-FINAL: $a3
-; CHECK-FINAL: $a4
+; CHECK-FINAL-NOT: $a1
+; CHECK-FINAL-NOT: $a2
+; CHECK-FINAL-NOT: $a3
+; CHECK-FINAL-NOT: $a4
 ; CHECK-FINAL: $a5
 ; CHECK-FINAL: $a6
 
 ; CHECK-FINAL-NOT: @llvm.used
 ; CHECK-FINAL-NOT: @llvm.compiler.used
 
-; CHECK-FINAL: define void @fn1
-; CHECK-FINAL: define void @fn2
+; CHECK-FINAL-NOT: define void @fn1
+; CHECK-FINAL-NOT: define void @fn2
 ; CHECK-FINAL: define void @fn3
-; CHECK-FINAL: define void @fn4
+; CHECK-FINAL-NOT: define void @fn4
 
 @g1 = global [ 4 x i32 ] zeroinitializer
 @g2 = global [ 4 x i32 ] zeroinitializer
 
 @"$a1" = alias void (), void ()* @fn1
 @"$a2" = alias void (), void ()* @fn2
 @"$a3" = alias void (), void ()* @fn3
 @"$a4" = alias void (), void ()* @fn4

llvm/tools/llvm-reduce/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   AllTargetsAsmParsers
   AllTargetsCodeGens
   AllTargetsDescs
   AllTargetsInfos
   Core
   IRReader
   Support
   Target
   TransformUtils
   )
 
 add_llvm_tool(llvm-reduce
   TestRunner.cpp
   deltas/Delta.cpp
+  deltas/ReduceAliases.cpp
   deltas/ReduceArguments.cpp
   deltas/ReduceAttributes.cpp
   deltas/ReduceBasicBlocks.cpp
   deltas/ReduceFunctionBodies.cpp
   deltas/ReduceFunctions.cpp
   deltas/ReduceGlobalVars.cpp
   deltas/ReduceInstructions.cpp
   deltas/ReduceMetadata.cpp
   deltas/ReduceOperandBundles.cpp
   llvm-reduce.cpp
 
   DEPENDS
   intrinsics_gen
   )

llvm/tools/llvm-reduce/DeltaManager.h

 //===- DeltaManager.h - Runs Delta Passes to reduce Input -----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file calls each specialized Delta pass in order to reduce the input IR
 // file.
 //
 //===----------------------------------------------------------------------===//
 
 #include "TestRunner.h"
 #include "deltas/Delta.h"
+#include "deltas/ReduceAliases.h"
 #include "deltas/ReduceArguments.h"
 #include "deltas/ReduceAttributes.h"
 #include "deltas/ReduceBasicBlocks.h"
 #include "deltas/ReduceFunctionBodies.h"
 #include "deltas/ReduceFunctions.h"
 #include "deltas/ReduceGlobalVars.h"
 #include "deltas/ReduceInstructions.h"
 #include "deltas/ReduceMetadata.h"
 #include "deltas/ReduceOperandBundles.h"
 
 namespace llvm {
 
 // TODO: Add CLI option to run only specified Passes (for unit tests)
 inline void runDeltaPasses(TestRunner &Tester) {
+  reduceAliasesDeltaPass(Tester);
   reduceFunctionBodiesDeltaPass(Tester);
   reduceFunctionsDeltaPass(Tester);
   reduceBasicBlocksDeltaPass(Tester);
   reduceGlobalsDeltaPass(Tester);
   reduceMetadataDeltaPass(Tester);
   reduceArgumentsDeltaPass(Tester);
   reduceInstructionsDeltaPass(Tester);
   reduceOperandBundesDeltaPass(Tester);
   reduceAttributesDeltaPass(Tester);
   // TODO: Implement the remaining Delta Passes
 }
 
 } // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceAliases.h

+//===- ReduceAliases.h - Specialized Delta Pass ---------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce aliases in the provided Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+
+namespace llvm {
+void reduceAliasesDeltaPass(TestRunner &Test);
+} // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceAliases.cpp

+//===- ReduceAliases.cpp - Specialized Delta Pass -------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce aliases in the provided Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceAliases.h"
+#include "Delta.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/GlobalValue.h"
+
+using namespace llvm;
+
+/// Removes all aliases aren't inside any of the
+/// desired Chunks.
+static void extractAliasesFromModule(const std::vector<Chunk> &ChunksToKeep,
+                                     Module *Program) {
+  Oracle O(ChunksToKeep);
+
+  for (auto &GA : make_early_inc_range(Program->aliases())) {
+    if (!O.shouldKeep()) {
+      GA.replaceAllUsesWith(GA.getAliasee());
+      GA.eraseFromParent();
+    }
+  }
+}
+
+/// Counts the amount of aliases and prints their respective name & index.
+static int countAliases(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  errs() << "----------------------------\n";
+  errs() << "Aliases Index Reference:\n";
+  int Count = 0;
+  for (auto &GA : Program->aliases())
+    errs() << "\t" << ++Count << ": " << GA.getName() << "\n";
+
+  errs() << "----------------------------\n";
+  return Count;
+}
+
+void llvm::reduceAliasesDeltaPass(TestRunner &Test) {
+  errs() << "*** Reducing Aliases ...\n";
+  int Functions = countAliases(Test.getProgram());
+  runDeltaPass(Test, Functions, extractAliasesFromModule);
+  errs() << "----------------------------\n";
+}