Add alias canonicalization pass when preparing for ThinLTO

[tejohnson]

Summary

This patch implements an alias canonicalization pass to convert aliases
to the form discussed in https://llvm.org/bugs/show_bug.cgi?id=27866.
This changes aliases and aliasees into aliases with a private anonymous
value.

It was also discussed on the mailing list (see "Weak symbol/alias
semantics" thread here:

http://lists.llvm.org/pipermail/llvm-dev/2017-January/109038.html),

as it simplifies needed fixes for ThinLTO weak symbol/alias handling.

Therefore, to start with I have only enabled the canonicalization pass
when preparing for ThinLTO. After this, I plan to add a bitcode upgrade
mechanism and use it for ThinLTO, and then enable the pass and upgrade
mechanism in other cases. Eventually IR producers can be changed, but
that is a longer term solution.

[mehdi_amini]

lib/Transforms/Utils/CanonicalizeAliases.cpp

35

Why materialized_uses?

36

That deserves a comment. I'd even desugarize the loop with an assert that there is only one use as "documentation" of the invariant you're relying on here. (alternatively, or at the same time, add a comment)

99

Instead of reimplementing a custom RAUW (the duplication isn't great here), would it be possible to perform the regular one, and then reattach the aliases?

110

New PM version of the pass?

[tejohnson]

lib/Transforms/Utils/CanonicalizeAliases.cpp

35

IIRC this was required when I was doing via a bitcode upgrade, because uses() asserts that the module is materialized and I believe it isn't on some paths (maybe when we are importing and the whole module isn't materialized?). It isn't strictly necessary with this patch, but will probably need to go back in when I add a follow on bitcode upgrade interface. I will remove it for now though.

36

Will do

99

Hmm, maybe. Will take a stab at it.

110

Good idea! Will add

[tejohnson]

I should also add that I have been investigating how hard it would be to do this during GlobalAlias::create. It turns out to be much more complicated, unfortunately (a few notes below). It seems like it would be more straightforward to add a pass as done here and then a bitcode upgrade path for now, and eventually teach producers such as clang to do the right thing.

BTW I will be on vacation for a week+ so might not have time to do follow-up work here until I am back Feb 27.

Complications with canonicalization during GlobalAlias::create:

• When we canonicalize an alias being created, where the aliasee is another alias that has already been canonicalized (since we are converting each alias as we read it in from the LLVM assembly) - means having to repeatedly look through uses of the already-canonicalized alias to find the one in the alias being canonicalized in this call, so that we can rename it to the anonymous private.
• To do the above, need to inspect the aliasee's GV for each alias being created - but there isn't already a way to find the aliasee's GV while stripping both pointer casts and inbound indices, but not follow aliases (i.e. normally getBaseObject() will look through aliases).

I have a fix for the first one, but it seems inefficient to have to re-scan uses of the aliasee that was a converted alias (not sure how common that is though). The second one I don't have a complete fix for. It probably needs an additional facility on stripPointerCastsAndOffsets.

[pcc]

For canonicalization this seems like a better approach. It walks the alias operands so you don't hit the issue with alias vs non-alias users. I wrote it as a function inside LTO but it could easily be moved into a pass.

diff --git a/llvm/lib/LTO/LTOBackend.cpp b/llvm/lib/LTO/LTOBackend.cpp
index 926c419e34a..bbca8f5b6e7 100644
--- a/llvm/lib/LTO/LTOBackend.cpp
+++ b/llvm/lib/LTO/LTOBackend.cpp
@@ -439,8 +439,49 @@ Error lto::backend(Config &C, AddStreamFn AddStream,
   return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
 }
 
-static void dropDeadSymbols(Module &Mod, const GVSummaryMapTy &DefinedGlobals,
+static Constant *resolveAliases(Constant *C) {
+  if (auto *GA = dyn_cast<GlobalAlias>(C))
+    return resolveAliases(GA->getAliasee());
+
+  if (auto *GO = dyn_cast<GlobalObject>(C)) {
+    if (!GO->hasLocalLinkage()) {
+      // Replace GO with an alias that points to it.
+      auto *GA = GlobalAlias::create("", GO);
+      GA->setLinkage(GO->getLinkage());
+      GA->copyAttributesFrom(GO);
+      GA->takeName(GO);
+      GO->replaceAllUsesWith(GA);
+      GA->setAliasee(GO);
+      GO->setLinkage(GlobalValue::PrivateLinkage);
+
+      // This will end up giving a suffixed name to GO.
+      GO->setName(GA->getName());
+    }
+    return GO;
+  }
+
+  auto *CE = dyn_cast<ConstantExpr>(C);
+  if (!CE)
+    return C;
+
+  std::vector<Constant *> Ops;
+  for (Use &U : CE->operands())
+    Ops.push_back(resolveAliases(cast<Constant>(U)));
+  return CE->getWithOperands(Ops);
+}
+
+static void dropDeadSymbols(Module &Mod, const Triple &TT,
+                            const GVSummaryMapTy &DefinedGlobals,
                             const ModuleSummaryIndex &Index) {
+  for (GlobalAlias &GA : Mod.aliases()) {
+    // Don't handle COFF weak externals, since unlike regular aliases they
+    // operate on the symbol level.
+    if (GA.hasWeakLinkage() && TT.isOSBinFormatCOFF())
+      continue;
+
+    GA.setAliasee(resolveAliases(GA.getAliasee()));
+  }
+
   std::vector<GlobalValue*> DeadGVs;
   for (auto &GV : Mod.global_values())
     if (GlobalValueSummary *GVS = DefinedGlobals.lookup(GV.getGUID()))
@@ -488,7 +529,7 @@ Error lto::thinBackend(Config &Conf, unsigned Task, AddStreamFn AddStream,
 
   renameModuleForThinLTO(Mod, CombinedIndex);
 
-  dropDeadSymbols(Mod, DefinedGlobals, CombinedIndex);
+  dropDeadSymbols(Mod, TM->getTargetTriple(), DefinedGlobals, CombinedIndex);
 
   thinLTOResolvePrevailingInModule(Mod, DefinedGlobals);

lib/Transforms/Utils/CanonicalizeAliases.cpp

58

I don't think this is entirely correct. A bitcast can have both alias and non-alias uses, so you would need to create different ConstantExprs for each. It actually seems simpler to visit the alias's operands than the use list.

include/llvm/InitializePasses.h

 void initializeBasicAAWrapperPassPass(PassRegistry&);
 void initializeBlockExtractorPassPass(PassRegistry&);
 void initializeBlockFrequencyInfoWrapperPassPass(PassRegistry&);
 void initializeBoundsCheckingPass(PassRegistry&);
 void initializeBranchFolderPassPass(PassRegistry&);
 void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry&);
 void initializeBranchRelaxationPass(PassRegistry&);
 void initializeBreakCriticalEdgesPass(PassRegistry&);
+void initializeCanonicalizeAliasesLegacyPassPass(PassRegistry &);
 void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&);
 void initializeCFGPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGViewerLegacyPassPass(PassRegistry&);
 void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
 void initializeCFLSteensAAWrapperPassPass(PassRegistry&);
 void initializeCallGraphDOTPrinterPass(PassRegistry&);

include/llvm/Transforms/Scalar.h

 //===----------------------------------------------------------------------===//
 //
 // LoopDataPrefetch - Perform data prefetching in loops.
 //
 FunctionPass *createLoopDataPrefetchPass();
 
 ///===---------------------------------------------------------------------===//
 ModulePass *createNameAnonGlobalPass();
+ModulePass *createCanonicalizeAliasesPass();
 
 //===----------------------------------------------------------------------===//
 //
 // LibCallsShrinkWrap - Shrink-wraps a call to function if the result is not
 // used.
 //
 FunctionPass *createLibCallsShrinkWrapPass();
 } // End llvm namespace
 
 #endif

include/llvm/Transforms/Utils/CanonicalizeAliases.h

+//===-- CanonicalizeAliases.h - Alias Canonicalization Pass -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file canonicalizes aliases.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_CANONICALIZE_ALIASES_H
+#define LLVM_TRANSFORMS_UTILS_CANONICALIZE_ALIASES_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+bool canonicalizeAliases(Module &M);
+
+/// Simple pass that canonicalizes aliases.
+class CanonicalizeAliases : public PassInfoMixin<CanonicalizeAliases> {
+public:
+  CanonicalizeAliases() = default;
+
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CANONICALIZE_ALIASESH

lib/Transforms/IPO/PassManagerBuilder.cpp

if (OptLevel == 0) {
     // that pass manager. To prevent this we insert a no-op module pass to reset
     // the pass manager to get the same behavior as EP_OptimizerLast in non-O0
     // builds. The function merging pass is
     if (MergeFunctions)
       MPM.add(createMergeFunctionsPass());
     else if (!GlobalExtensions->empty() || !Extensions.empty())
       MPM.add(createBarrierNoopPass());
 
-    if (PrepareForThinLTO)
+    if (PrepareForThinLTO) {
+      MPM.add(createCanonicalizeAliasesPass());
       // Rename anon globals to be able to export them in the summary.
       MPM.add(createNameAnonGlobalPass());
+    }
 
     addExtensionsToPM(EP_EnabledOnOptLevel0, MPM);
     return;
   }
 
   // Add LibraryInfo if we have some.
   if (LibraryInfo)
     MPM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
void PassManagerBuilder::populateModulePassManager(
 
   if (!DisableUnitAtATime)
     MPM.add(createReversePostOrderFunctionAttrsPass());
 
   // If we are planning to perform ThinLTO later, let's not bloat the code with
   // unrolling/vectorization/... now. We'll first run the inliner + CGSCC passes
   // during ThinLTO and perform the rest of the optimizations afterward.
   if (PrepareForThinLTO) {
+    MPM.add(createCanonicalizeAliasesPass());
     // Reduce the size of the IR as much as possible.
     MPM.add(createGlobalOptimizerPass());
     // Rename anon globals to be able to export them in the summary.
     MPM.add(createNameAnonGlobalPass());
     return;
   }
 
   if (PerformThinLTO)

lib/Transforms/Utils/CMakeLists.txt

 add_llvm_library(LLVMTransformUtils
   ASanStackFrameLayout.cpp
   AddDiscriminators.cpp
   BasicBlockUtils.cpp
   BreakCriticalEdges.cpp
   BuildLibCalls.cpp
   BypassSlowDivision.cpp
+  CanonicalizeAliases.cpp
   CloneFunction.cpp
   CloneModule.cpp
   CmpInstAnalysis.cpp
   CodeExtractor.cpp
   CtorUtils.cpp
   DemoteRegToStack.cpp
   EscapeEnumerator.cpp
   Evaluator.cpp

lib/Transforms/Utils/CanonicalizeAliases.cpp

+//===- CanonicalizeAliases.cpp - ThinLTO Support: Canonicalize Aliases ----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements alias canonicalization, so that all aliasees
+// are private anonymous values. E.g.
+//  @a = alias i8, i8 *@g
+//  @g = global i8 0
+//
+// will be converted to:
+//  @0 = private global
+//  @a = alias i8, i8* @0
+//  @g = alias i8, i8* @0
+//
+// This simplifies optimization and ThinLTO linking of the original symbols.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/CanonicalizeAliases.h"
+
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/ValueHandle.h"
+
+using namespace llvm;
+
+/// Check if the given user is an alias (looking through bit casts).
+static bool userIsAlias(Value *V) {
+  if (isa<GlobalAlias>(V))
+    return true;
+  if (BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {
+    for (Use &U : BC->materialized_uses()) {
+      return userIsAlias(U.getUser());
+    }
+  }
+  return false;
+}
+
+/// Like replaceAllUsesWith but doesn't replace any uses that are
+/// aliases, so that we can just replace uses of the original value
+/// with the new private aliasee, but keep the original value name
+/// as an alias to it.
+static void replaceAllUsesWithExceptAliases(Value *Old, Value *New) {
+  assert(New && "Value::replaceAllUsesWith(<null>) is invalid!");
+  assert(New->getType() == Old->getType() &&
+         "replaceAllUses of value with new value of different type!");
+
+  // Notify all ValueHandles (if present) that this value is going away.
+  if (Old->hasValueHandle())
+    ValueHandleBase::ValueIsRAUWd(Old, New);
+  if (Old->isUsedByMetadata())
+    ValueAsMetadata::handleRAUW(Old, New);
+
+  for (Use &U : Old->materialized_uses()) {
+    if (userIsAlias(U.getUser()))
+      continue;
+    // Must handle Constants specially, we cannot call replaceUsesOfWith on a
+    // constant because they are uniqued.
+    if (auto *C = dyn_cast<Constant>(U.getUser())) {
+      if (!isa<GlobalValue>(C)) {
+        C->handleOperandChange(Old, New);
+        continue;
+      }
+    }
+
+    U.set(New);
+  }
+}
+
+namespace llvm {
+/// Convert aliases to canonical form.
+bool canonicalizeAliases(Module &M) {
+  bool Changed = false;
+  for (auto &GA : M.aliases()) {
+    // Check if the aliasee is private already
+    GlobalObject *GO = GA.getBaseObject();
+    if (!GO || GO->hasPrivateLinkage())
+      continue;
+
+    // Don't make malformed IR (will be caught by verifier) worse.
+    if (GO->isDeclarationForLinker())
+      continue;
+
+    // Create a new alias to aliasee that keeps the original aliasee name
+    // and linkage.
+    auto *NewGA = GlobalAlias::create("", GO);
+    NewGA->takeName(GO);
+
+    // Make the original aliasee anonymous
+    GO->setName("");
+
+    // Change linkage of renamed original aliasee to private
+    GO->setLinkage(GlobalValue::PrivateLinkage);
+
+    // RAUW all uses of original aliasee with the new alias.
+    replaceAllUsesWithExceptAliases(GO, NewGA);
+
+    Changed = true;
+  }
+  return Changed;
+}
+}
+
+namespace {
+
+// Legacy pass that canonicalizes aliases.
+class CanonicalizeAliasesLegacyPass : public ModulePass {
+
+public:
+  /// Pass identification, replacement for typeid
+  static char ID;
+
+  /// Specify pass name for debug output
+  StringRef getPassName() const override { return "Canonicalize Aliases"; }
+
+  explicit CanonicalizeAliasesLegacyPass() : ModulePass(ID) {}
+
+  bool runOnModule(Module &M) override { return canonicalizeAliases(M); }
+};
+char CanonicalizeAliasesLegacyPass::ID = 0;
+
+} // anonymous namespace
+
+PreservedAnalyses CanonicalizeAliases::run(Module &M,
+                                           ModuleAnalysisManager &AM) {
+  if (!canonicalizeAliases(M))
+    return PreservedAnalyses::all();
+
+  return PreservedAnalyses::none();
+}
+
+INITIALIZE_PASS_BEGIN(CanonicalizeAliasesLegacyPass, "canonicalize-aliases",
+                      "Canonicalize aliases", false, false)
+INITIALIZE_PASS_END(CanonicalizeAliasesLegacyPass, "canonicalize-aliases",
+                    "Canonicalize aliases", false, false)
+
+namespace llvm {
+ModulePass *createCanonicalizeAliasesPass() {
+  return new CanonicalizeAliasesLegacyPass();
+}
+}

lib/Transforms/Utils/Utils.cpp

 
 using namespace llvm;
 
 /// initializeTransformUtils - Initialize all passes in the TransformUtils
 /// library.
 void llvm::initializeTransformUtils(PassRegistry &Registry) {
   initializeAddDiscriminatorsLegacyPassPass(Registry);
   initializeBreakCriticalEdgesPass(Registry);
+  initializeCanonicalizeAliasesLegacyPassPass(Registry);
   initializeInstNamerPass(Registry);
   initializeLCSSAWrapperPassPass(Registry);
   initializeLibCallsShrinkWrapLegacyPassPass(Registry);
   initializeLoopSimplifyPass(Registry);
   initializeLowerInvokeLegacyPassPass(Registry);
   initializeLowerSwitchPass(Registry);
   initializeNameAnonGlobalLegacyPassPass(Registry);
   initializePromoteLegacyPassPass(Registry);

test/Transforms/CanonicalizeAliases/canonicalize.ll

+; RUN: opt -S -canonicalize-aliases < %s | FileCheck %s
+; RUN: opt -prepare-for-thinlto -O0 -module-summary -o - < %s | llvm-dis -o - | FileCheck %s --check-prefix=NAMEDANON
+
+; CHECK-DAG: @fooalias = alias void (...), bitcast (void ()* @1
+; CHECK-DAG: @foo = alias void (), void ()* @1
+; CHECK-DAG: define private void @1()
+; NAMEDANON-DAG: @fooalias = alias void (...), bitcast (void ()* @anon.d41d8cd98f00b204e9800998ecf8427e.0
+; NAMEDANON-DAG: @foo = alias void (), void ()* @anon.d41d8cd98f00b204e9800998ecf8427e.0
+; NAMEDANON-DAG: define private void @anon.d41d8cd98f00b204e9800998ecf8427e.0()
+@fooalias = alias void (...), bitcast (void ()* @foo to void (...)*)
+define void @foo() {
+    ret void
+}
+
+; CHECK-DAG: @0 = private global
+; CHECK-DAG: @baralias = alias i8, i8* @0
+; CHECK-DAG: @bar = alias i8, i8* @0
+; NAMEDANON-DAG: @anon.d41d8cd98f00b204e9800998ecf8427e.1 = private global
+; NAMEDANON-DAG: @baralias = alias i8, i8* @anon.d41d8cd98f00b204e9800998ecf8427e.1
+; NAMEDANON-DAG: @bar = alias i8, i8* @anon.d41d8cd98f00b204e9800998ecf8427e.1
+@baralias = alias i8, i8 *@bar
+@bar = global i8 0