[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

I almost think reducing these should be a separate step

32

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

+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

34–36 ↗

(On Diff #301248)

Comment needs updating

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

1 ↗

(On Diff #301248)

Unsufficient ---- padding

11 ↗

(On Diff #301248)

missing //

[fhahn]

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

21

Done, moved to D90302

32

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: $a1
-; CHECK-FINAL: $a2
-; CHECK-FINAL: $a3
-; CHECK-FINAL: $a4
+; CHECK-FINAL-NOT: = alias
 
-; 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
 
 @"$a1" = alias void (), void ()* @fn1
 @"$a2" = alias void (), void ()* @fn2
 @"$a3" = alias void (), void ()* @fn3
 @"$a4" = alias void (), void ()* @fn4
 
 define void @fn1() {
   ret void

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/ReduceAliasAndSpecialGlobals.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/ReduceAliasAndSpecialGlobals.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) {
+  reduceAliasAndSpecialGlobalsDeltaPass(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/ReduceAliasAndSpecialGlobals.h

+//===- ReduceAliasAndSpecialGlobals.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 and special globals in the provided Module.
+
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+
+namespace llvm {
+void reduceAliasAndSpecialGlobalsDeltaPass(TestRunner &Test);
+} // namespace llvm

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

+//===- ReduceAliasAndSpecialGlobals.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 and special globals in the provided Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceAliasAndSpecialGlobals.h"
+#include "Delta.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/GlobalValue.h"
+
+using namespace llvm;
+
+static auto SpecialGlobalNames = {"llvm.used", "llvm.compiler.used"};
+
+/// Removes all aliases and special globals that aren't inside any of the
+/// desired Chunks.
+static void
+extractAliasAndSpecialGlobalsFromModule(const std::vector<Chunk> &ChunksToKeep,
+                                        Module *Program) {
+  Oracle O(ChunksToKeep);
+
+  for (auto &GA : make_early_inc_range(Program->aliases())) {
+    if (!O.shouldKeep()) {
+      GA.replaceAllUsesWith(UndefValue::get(GA.getType()));
+      GA.eraseFromParent();
+    }
+  }
+
+  for (const char *Name : SpecialGlobalNames) {
+    if (auto *Used = Program->getNamedGlobal(Name)) {
+      Used->replaceAllUsesWith(UndefValue::get(Used->getType()));
+      Used->eraseFromParent();
+    }
+  }
+}
+
+/// Counts the amount of aliases and special globals and prints their
+/// respective name & index
+static int countAliasAndSpecialGlobals(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  errs() << "----------------------------\n";
+  errs() << "Aliases And Special Globals Index Reference:\n";
+  int Count = 0;
+  for (auto &GA : Program->aliases())
+    errs() << "\t" << ++Count << ": " << GA.getName() << "\n";
+
+  for (const char *Name : SpecialGlobalNames) {
+    if (auto *Used = Program->getNamedGlobal(Name))
+      errs() << "\t" << ++Count << ": " << Used->getName() << "\n";
+  }
+
+  errs() << "----------------------------\n";
+  return Count;
+}
+
+void llvm::reduceAliasAndSpecialGlobalsDeltaPass(TestRunner &Test) {
+  errs() << "*** Reducing Aliases and Special Globals...\n";
+  int Functions = countAliasAndSpecialGlobals(Test.getProgram());
+  runDeltaPass(Test, Functions, extractAliasAndSpecialGlobalsFromModule);
+  errs() << "----------------------------\n";
+}