[llvm-reduce] Add reduction for special globals like llvm.used.

[fhahn]

Summary

This patch adds a reduction of 'special' globals that lead to further
reductions (e.g. alias or regular globals reduction) being less efficient
because there are special constraints on values referenced in those
special globals. For example, values in @llvm.used and
@llvm.compiler.used need to be named, so replacing all uses of an
alias/global with undef or a different unnamed constant results in
invalid IR.

More details:
https://llvm.org/docs/LangRef.html#intrinsic-global-variables

[fhahn]

Fix comment, padding.

[fhahn]

rebase after landing alias reduction

[fhahn]

ping :)

[lebedev.ri]

A nit and a question, but i don't really have an opinion on the functionality here.

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

24

static StringRef

35

Do we want to be more fine-grained than that?
Should this be per-use?

[fhahn]

Use const char * instead of auto.

[fhahn]

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

24

Update to use const char *.

35

Hm, I guess it might be helpful, but I haven't encountered any cases where it would be needed/beneficial in practice. I would prefer to only cross that bridge once it becomes an issue, but I can also update this patch.

[fhahn]

Use StringRef instead of const char *

[lebedev.ri]

Thanks. I don't really have comments on the idea, but the logic seems in-line with the rest.

[MaskRay]

http://lab.llvm.org:8011/#/builders/114 (the string "clang-cmake-aarch64-global-isel" contains "global") failed for the past month... Fixed it with f314bcffa3c6083079831dde4e7bc124a25e0c04

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-NOT: global
 
-; 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: = alias
 
 ; CHECK-FINAL-NOT: @llvm.used
 ; CHECK-FINAL-NOT: @llvm.compiler.used
 
 ; CHECK-FINAL-NOT: define void @fn1
 ; CHECK-FINAL-NOT: define void @fn2
 ; CHECK-FINAL: define void @fn3
 ; CHECK-FINAL-NOT: define void @fn4

llvm/tools/llvm-reduce/CMakeLists.txt

add_llvm_tool(llvm-reduce
   deltas/ReduceAttributes.cpp
   deltas/ReduceBasicBlocks.cpp
   deltas/ReduceFunctionBodies.cpp
   deltas/ReduceFunctions.cpp
   deltas/ReduceGlobalVars.cpp
   deltas/ReduceInstructions.cpp
   deltas/ReduceMetadata.cpp
   deltas/ReduceOperandBundles.cpp
+  deltas/ReduceSpecialGlobals.cpp
   llvm-reduce.cpp
 
   DEPENDS
   intrinsics_gen
   )

llvm/tools/llvm-reduce/DeltaManager.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"
+#include "deltas/ReduceSpecialGlobals.h"
 
 namespace llvm {
 
 // TODO: Add CLI option to run only specified Passes (for unit tests)
 inline void runDeltaPasses(TestRunner &Tester) {
+  reduceSpecialGlobalsDeltaPass(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/ReduceSpecialGlobals.h

+//===- ReduceSpecialGlobals.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 special globals, like @llvm.used, in the provided Module.
+//
+// For more details about special globals, see
+// https://llvm.org/docs/LangRef.html#intrinsic-global-variables
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+
+namespace llvm {
+void reduceSpecialGlobalsDeltaPass(TestRunner &Test);
+} // namespace llvm

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

+//===- ReduceSpecialGlobals.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 special globals, like @llvm.used, in the provided Module.
+//
+// For more details about special globals, see
+// https://llvm.org/docs/LangRef.html#intrinsic-global-variables
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceSpecialGlobals.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 special globals aren't inside any of the
+/// desired Chunks.
+static void
+extractSpecialGlobalsFromModule(const std::vector<Chunk> &ChunksToKeep,
+                                Module *Program) {
+  Oracle O(ChunksToKeep);
+
+  for (const char *Name : SpecialGlobalNames) {
+    if (auto *Used = Program->getNamedGlobal(Name)) {
+      Used->replaceAllUsesWith(UndefValue::get(Used->getType()));
+      Used->eraseFromParent();
+    }
+  }
+}
+
+/// Counts the amount of special globals and prints their
+/// respective name & index
+static int countSpecialGlobals(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  errs() << "----------------------------\n";
+  errs() << "Special Globals Index Reference:\n";
+  int Count = 0;
+  for (const char *Name : SpecialGlobalNames) {
+    if (auto *Used = Program->getNamedGlobal(Name))
+      errs() << "\t" << ++Count << ": " << Used->getName() << "\n";
+  }
+  errs() << "----------------------------\n";
+  return Count;
+}
+
+void llvm::reduceSpecialGlobalsDeltaPass(TestRunner &Test) {
+  errs() << "*** Reducing Special Globals ...\n";
+  int Functions = countSpecialGlobals(Test.getProgram());
+  runDeltaPass(Test, Functions, extractSpecialGlobalsFromModule);
+  errs() << "----------------------------\n";
+}