[ThinLTO] Handle chains of aliases

[tejohnson]

Summary

At -O0, globalopt is not run during the compile step, and we can have a
chain of an alias having an immediate aliasee of another alias. We were
not correctly summarizing this (we always got the base object when
recording the aliasee), and also not handling it properly in ThinLTO
dead stripping, which would only mark the base object as live. This
could result in the intermediate alias incorrectly being marked dead and
dropped to a declaration.

Fix by correctly representing an alias to another alias in the summary.
Also change the dead stripping computation so that it marks all aliases
in the chain as live.

This required adding a version of stripInBoundsOffsets() that doesn't
follow aliases (this is the interface called by getBaseObject, and we
want to be able to strip in bounds offsets from the immediate aliasee).

[tejohnson]

ping

[tejohnson]

ping

[davidxl]

include/llvm/IR/ModuleSummaryIndex.h

427 ↗

(On Diff #173973)

Can this be refactored as

return const_cast<const GlobalValueSummary *>(this)->getBaseObject();

to avoid code duplication?

lib/Analysis/ModuleSummaryAnalysis.cpp

446 ↗

(On Diff #173973)

Add a comment for the function?

lib/IR/Value.cpp

475 ↗

(On Diff #173973)

Add some documentation on the InBounds kinds?

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

427 ↗

(On Diff #173973)

Yep. Although needs another const_cast on the return value to remove the const again.

[tejohnson]

Address comments

[pcc]

Isn't this just a bug in promotion? It should probably internalize any non-prevailing aliases like lib/Linker does.

[davidxl]

lib/IR/Value.cpp

469 ↗

(On Diff #177754)

Perhaps there is no need to change the name of this kind -- proper documentation is probably enough.

471 ↗

(On Diff #177754)

Name the new one PSK_InBoundsNoAliases so that existing enumerator's semantics do not change.

473 ↗

(On Diff #177754)

Perhaps leave the semantics of this enum unchanged?

[tejohnson]

In D54507#1327394, @pcc wrote:

Isn't this just a bug in promotion? It should probably internalize any non-prevailing aliases like lib/Linker does.

Can you clarify? The summary doesn't contain any references to the intermediate aliasee so it looks completely unreferenced.

[pcc]

In D54507#1327487, @tejohnson wrote:

In D54507#1327394, @pcc wrote:

Isn't this just a bug in promotion? It should probably internalize any non-prevailing aliases like lib/Linker does.

Can you clarify? The summary doesn't contain any references to the intermediate aliasee so it looks completely unreferenced.

And indeed it isn't. The important thing to keep alive is the base object, which is what the code already does.

My first idea was that we would change the code in convertToDeclaration here:
http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/FunctionImport.cpp#923
so that we would RAUW all alias references to point to the external and all non-alias references to point to the aliasee. But unfortunately it doesn't seem easy to implement "replace some uses with" on constants.

Probably the simplest fix is to make sure that each aliasee is canonicalized to point to the base object before calling convertToDeclaration. This seems pretty straightforward using ConstantExpr::getWithOperands. This also takes us one step closer to the canonical alias form we discussed last year: we would just need to apply the same canonicalization *before* writing the bitcode file.

[tejohnson]

In D54507#1327573, @pcc wrote:

In D54507#1327487, @tejohnson wrote:

In D54507#1327394, @pcc wrote:

Isn't this just a bug in promotion? It should probably internalize any non-prevailing aliases like lib/Linker does.

Can you clarify? The summary doesn't contain any references to the intermediate aliasee so it looks completely unreferenced.

And indeed it isn't. The important thing to keep alive is the base object, which is what the code already does.

My first idea was that we would change the code in convertToDeclaration here:
http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/FunctionImport.cpp#923
so that we would RAUW all alias references to point to the external and all non-alias references to point to the aliasee. But unfortunately it doesn't seem easy to implement "replace some uses with" on constants.

Probably the simplest fix is to make sure that each aliasee is canonicalized to point to the base object before calling convertToDeclaration.

Do you mean make sure that each "alias" is canonicalized to point to the base object? I.e. if we have an alias relationship "A aliases B aliases C", then convert it to "A aliases C" and "B aliases C"? Presumably that would fix the issue, but the summary is still not accurately reflecting the IR (although not sure where else it would be problematic).

This seems pretty straightforward using ConstantExpr::getWithOperands. This also takes us one step closer to the canonical alias form we discussed last year: we would just need to apply the same canonicalization *before* writing the bitcode file.

Yes this alias canonicalization would also fix the issue, before the summary is generated. Unfortunately it's not something I have had time to work on since that first attempt.

[pcc]

In D54507#1327609, @tejohnson wrote:

In D54507#1327573, @pcc wrote:

In D54507#1327487, @tejohnson wrote:

In D54507#1327394, @pcc wrote:

Isn't this just a bug in promotion? It should probably internalize any non-prevailing aliases like lib/Linker does.

Can you clarify? The summary doesn't contain any references to the intermediate aliasee so it looks completely unreferenced.

And indeed it isn't. The important thing to keep alive is the base object, which is what the code already does.

My first idea was that we would change the code in convertToDeclaration here:
http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/FunctionImport.cpp#923
so that we would RAUW all alias references to point to the external and all non-alias references to point to the aliasee. But unfortunately it doesn't seem easy to implement "replace some uses with" on constants.

Probably the simplest fix is to make sure that each aliasee is canonicalized to point to the base object before calling convertToDeclaration.

Do you mean make sure that each "alias" is canonicalized to point to the base object? I.e. if we have an alias relationship "A aliases B aliases C", then convert it to "A aliases C" and "B aliases C"?

Yes, exactly.

Presumably that would fix the issue, but the summary is still not accurately reflecting the IR (although not sure where else it would be problematic).

I don't think it would be problematic. In this case the summary contains the more accurate representation of reality because references to globals in alias definitions, unlike all other references, are not subject to linker preemption, and we shouldn't allow the less-accurate representation in the IR to leak anywhere else.

This seems pretty straightforward using ConstantExpr::getWithOperands. This also takes us one step closer to the canonical alias form we discussed last year: we would just need to apply the same canonicalization *before* writing the bitcode file.

Yes this alias canonicalization would also fix the issue, before the summary is generated. Unfortunately it's not something I have had time to work on since that first attempt.

Yes but note that I am not proposing that we canonicalize everywhere right now. We just need to canonicalize here: http://llvm-cs.pcc.me.uk/lib/LTO/LTOBackend.cpp#490 (before dropDeadSymbols).

[tejohnson]

In D54507#1327677, @pcc wrote:

In D54507#1327609, @tejohnson wrote:

In D54507#1327573, @pcc wrote:

In D54507#1327487, @tejohnson wrote:

In D54507#1327394, @pcc wrote:

Isn't this just a bug in promotion? It should probably internalize any non-prevailing aliases like lib/Linker does.

Can you clarify? The summary doesn't contain any references to the intermediate aliasee so it looks completely unreferenced.

And indeed it isn't. The important thing to keep alive is the base object, which is what the code already does.

My first idea was that we would change the code in convertToDeclaration here:
http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/FunctionImport.cpp#923
so that we would RAUW all alias references to point to the external and all non-alias references to point to the aliasee. But unfortunately it doesn't seem easy to implement "replace some uses with" on constants.

Probably the simplest fix is to make sure that each aliasee is canonicalized to point to the base object before calling convertToDeclaration.

Do you mean make sure that each "alias" is canonicalized to point to the base object? I.e. if we have an alias relationship "A aliases B aliases C", then convert it to "A aliases C" and "B aliases C"?

Yes, exactly.

Presumably that would fix the issue, but the summary is still not accurately reflecting the IR (although not sure where else it would be problematic).

I don't think it would be problematic. In this case the summary contains the more accurate representation of reality because references to globals in alias definitions, unlike all other references, are not subject to linker preemption, and we shouldn't allow the less-accurate representation in the IR to leak anywhere else.

Philosophically, I think the summary should summarize the IR that we have (in the bitcode file), not the IR that we want. So I'm not completely comfortable with this approach - I'm actually thinking it may be better to add a skeleton alias canonicalization pass (taken from that draft alias canonicalization patch D29781) that is invoked during thinlto preparation. For now, it can just do this flatting of alias chains, and eventually expanded into the full canonicalization (and invoked in all paths as described in that patch description). I don't want to sign up to do the whole hog canonicalization currently since this bug only shows up at -O0 and I don't have the bandwidth to focus on it ATM. Does that seem like a reasonable interim approach?

This seems pretty straightforward using ConstantExpr::getWithOperands. This also takes us one step closer to the canonical alias form we discussed last year: we would just need to apply the same canonicalization *before* writing the bitcode file.

Yes this alias canonicalization would also fix the issue, before the summary is generated. Unfortunately it's not something I have had time to work on since that first attempt.

Yes but note that I am not proposing that we canonicalize everywhere right now. We just need to canonicalize here: http://llvm-cs.pcc.me.uk/lib/LTO/LTOBackend.cpp#490 (before dropDeadSymbols).

[pcc]

In D54507#1328447, @tejohnson wrote:

In D54507#1327677, @pcc wrote:

In D54507#1327609, @tejohnson wrote:

In D54507#1327573, @pcc wrote:

In D54507#1327487, @tejohnson wrote:

In D54507#1327394, @pcc wrote:

Isn't this just a bug in promotion? It should probably internalize any non-prevailing aliases like lib/Linker does.

Can you clarify? The summary doesn't contain any references to the intermediate aliasee so it looks completely unreferenced.

And indeed it isn't. The important thing to keep alive is the base object, which is what the code already does.

My first idea was that we would change the code in convertToDeclaration here:
http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/FunctionImport.cpp#923
so that we would RAUW all alias references to point to the external and all non-alias references to point to the aliasee. But unfortunately it doesn't seem easy to implement "replace some uses with" on constants.

Probably the simplest fix is to make sure that each aliasee is canonicalized to point to the base object before calling convertToDeclaration.

Do you mean make sure that each "alias" is canonicalized to point to the base object? I.e. if we have an alias relationship "A aliases B aliases C", then convert it to "A aliases C" and "B aliases C"?

Yes, exactly.

Presumably that would fix the issue, but the summary is still not accurately reflecting the IR (although not sure where else it would be problematic).

I don't think it would be problematic. In this case the summary contains the more accurate representation of reality because references to globals in alias definitions, unlike all other references, are not subject to linker preemption, and we shouldn't allow the less-accurate representation in the IR to leak anywhere else.

Philosophically, I think the summary should summarize the IR that we have (in the bitcode file), not the IR that we want. So I'm not completely comfortable with this approach - I'm actually thinking it may be better to add a skeleton alias canonicalization pass (taken from that draft alias canonicalization patch D29781) that is invoked during thinlto preparation. For now, it can just do this flatting of alias chains, and eventually expanded into the full canonicalization (and invoked in all paths as described in that patch description). I don't want to sign up to do the whole hog canonicalization currently since this bug only shows up at -O0 and I don't have the bandwidth to focus on it ATM. Does that seem like a reasonable interim approach?

Sounds reasonable enough. It seems a little better to do this during LTO because it would allow us to upgrade old bitcode but I'm happy for it to be a pass as well. I left some comments on D29781 about the overall approach there.

[tejohnson]

In D54507#1328732, @pcc wrote:

In D54507#1328447, @tejohnson wrote:

In D54507#1327677, @pcc wrote:

In D54507#1327609, @tejohnson wrote:

In D54507#1327573, @pcc wrote:

In D54507#1327487, @tejohnson wrote:

In D54507#1327394, @pcc wrote:

Isn't this just a bug in promotion? It should probably internalize any non-prevailing aliases like lib/Linker does.

Can you clarify? The summary doesn't contain any references to the intermediate aliasee so it looks completely unreferenced.

And indeed it isn't. The important thing to keep alive is the base object, which is what the code already does.

My first idea was that we would change the code in convertToDeclaration here:
http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/FunctionImport.cpp#923
so that we would RAUW all alias references to point to the external and all non-alias references to point to the aliasee. But unfortunately it doesn't seem easy to implement "replace some uses with" on constants.

Probably the simplest fix is to make sure that each aliasee is canonicalized to point to the base object before calling convertToDeclaration.

Do you mean make sure that each "alias" is canonicalized to point to the base object? I.e. if we have an alias relationship "A aliases B aliases C", then convert it to "A aliases C" and "B aliases C"?

Yes, exactly.

Presumably that would fix the issue, but the summary is still not accurately reflecting the IR (although not sure where else it would be problematic).

I don't think it would be problematic. In this case the summary contains the more accurate representation of reality because references to globals in alias definitions, unlike all other references, are not subject to linker preemption, and we shouldn't allow the less-accurate representation in the IR to leak anywhere else.

Philosophically, I think the summary should summarize the IR that we have (in the bitcode file), not the IR that we want. So I'm not completely comfortable with this approach - I'm actually thinking it may be better to add a skeleton alias canonicalization pass (taken from that draft alias canonicalization patch D29781) that is invoked during thinlto preparation. For now, it can just do this flatting of alias chains, and eventually expanded into the full canonicalization (and invoked in all paths as described in that patch description). I don't want to sign up to do the whole hog canonicalization currently since this bug only shows up at -O0 and I don't have the bandwidth to focus on it ATM. Does that seem like a reasonable interim approach?

Sounds reasonable enough. It seems a little better to do this during LTO because it would allow us to upgrade old bitcode but I'm happy for it to be a pass as well. I left some comments on D29781 about the overall approach there.

Uploading patch to do this now. Will update the summary if we go with this approach. Note that the clang side patch which I will upload separately contains the invocations of the new pass for the new PM (mirroring how this was done for NameAnonGlobals).

[tejohnson]

Update per comments.

[pcc]

lib/Transforms/Utils/CanonicalizeAliases.cpp

52

This isn't quite right; it will rewrite

ga1 = alias ga2
ga2 = alias gep(gv, 0, 1)

as

ga1 = alias gv

i.e. you will drop the offset from the alias. The implementation in https://reviews.llvm.org/D29781#1328720 handles this case correctly.

[tejohnson]

lib/Transforms/Utils/CanonicalizeAliases.cpp

52

You're right. We want to look at the direct aliasee (recursively). Made that change and enhanced the test case to cover this.

[tejohnson]

Address comments

[tejohnson]

lib/Transforms/Utils/CanonicalizeAliases.cpp

52

Actually, I think my new approach won't quite work if both aliases in the chain involve expressions - probably needs something like your ConstantExpr case in D29781. Need to construct an example.

[pcc]

lib/Transforms/Utils/CanonicalizeAliases.cpp

41

I think you can change this to namespace { and then the functions below don't need to be static.

49

With the current code you don't actually need the recursive call here, it could just be

while (auto *GA2 = dyn_cast<GlobalAlias>(Aliasee))
  Aliasee = GA2->getAliasee();

(but ignore if you plan to make this recursive).

52

This is just GA->setAliasee(Aliasee), no?

52

Yes, here's an example that won't canonicalize correctly:

ga1 = alias gep(ga2, 0, 1)
ga2 = alias gv

[tejohnson]

New version which more closely mirrors logic proposed in D29781 comments. One difference is that I update all aliases in the chain in one recursive pass. In any case, this should make it easy to implement D29781 on top as a follow on.

lib/Transforms/Utils/CanonicalizeAliases.cpp

49

I decided to make it recursive, so we can fix up all aliases in the chain in one go.

52

Added that case to my test as well.

52

Right, that was leftover from an older flawed version.

[tejohnson]

Fix algorithm, update test.

[pcc]

lib/Transforms/Utils/CanonicalizeAliases.cpp

61

You don't need to track this yourself, getWithOperands will do it for you.
http://llvm-cs.pcc.me.uk/lib/IR/Constants.cpp#1185

70

Remove braces

[tejohnson]

Address comments

[tejohnson]

ping - @pcc does this look ok now?

[pcc]

LGTM

lib/Transforms/IPO/PassManagerBuilder.cpp

749

Move comment.

[tejohnson]

Address comment

include/llvm/InitializePasses.h

 void initializeBlockExtractorPass(PassRegistry &);
 void initializeBlockFrequencyInfoWrapperPassPass(PassRegistry&);
 void initializeBoundsCheckingLegacyPassPass(PassRegistry&);
 void initializeBranchFolderPassPass(PassRegistry&);
 void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry&);
 void initializeBranchRelaxationPass(PassRegistry&);
 void initializeBreakCriticalEdgesPass(PassRegistry&);
 void initializeBreakFalseDepsPass(PassRegistry&);
+void initializeCanonicalizeAliasesLegacyPassPass(PassRegistry &);
 void initializeCFGOnlyPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&);
 void initializeCFGPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGViewerLegacyPassPass(PassRegistry&);
 void initializeCFIInstrInserterPass(PassRegistry&);
 void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
 void initializeCFLSteensAAWrapperPassPass(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();
 

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 {
+
+/// Simple pass that canonicalizes aliases.
+class CanonicalizeAliasesPass : public PassInfoMixin<CanonicalizeAliasesPass> {
+public:
+  CanonicalizeAliasesPass() = default;
+
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CANONICALIZE_ALIASESH

lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
 #include "llvm/Transforms/Scalar/Sink.h"
 #include "llvm/Transforms/Scalar/SpeculateAroundPHIs.h"
 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
 #include "llvm/Transforms/Scalar/WarnMissedTransforms.h"
 #include "llvm/Transforms/Utils/AddDiscriminators.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
+#include "llvm/Transforms/Utils/CanonicalizeAliases.h"
 #include "llvm/Transforms/Utils/EntryExitInstrumenter.h"
 #include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
 #include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LowerInvoke.h"
 #include "llvm/Transforms/Utils/Mem2Reg.h"
 #include "llvm/Transforms/Utils/NameAnonGlobals.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"

lib/Passes/PassRegistry.def

 #undef MODULE_ALIAS_ANALYSIS
 #undef MODULE_ANALYSIS
 
 #ifndef MODULE_PASS
 #define MODULE_PASS(NAME, CREATE_PASS)
 #endif
 MODULE_PASS("always-inline", AlwaysInlinerPass())
 MODULE_PASS("called-value-propagation", CalledValuePropagationPass())
+MODULE_PASS("canonicalize-aliases", CanonicalizeAliasesPass())
 MODULE_PASS("cg-profile", CGProfilePass())
 MODULE_PASS("constmerge", ConstantMergePass())
 MODULE_PASS("cross-dso-cfi", CrossDSOCFIPass())
 MODULE_PASS("deadargelim", DeadArgumentEliminationPass())
 MODULE_PASS("elim-avail-extern", EliminateAvailableExternallyPass())
 MODULE_PASS("forceattrs", ForceFunctionAttrsPass())
 MODULE_PASS("function-import", FunctionImportPass())
 MODULE_PASS("globaldce", GlobalDCEPass())

lib/Transforms/IPO/PassManagerBuilder.cpp

if (OptLevel == 0) {
     }
 
     addExtensionsToPM(EP_EnabledOnOptLevel0, MPM);
 
     // Rename anon globals to be able to export them in the summary.
     // This has to be done after we add the extensions to the pass manager
     // as there could be passes (e.g. Adddress sanitizer) which introduce
     // new unnamed globals.
-    if (PrepareForLTO || PrepareForThinLTO)
+    if (PrepareForLTO || PrepareForThinLTO) {
+      MPM.add(createCanonicalizeAliasesPass());
       MPM.add(createNameAnonGlobalPass());
+    }
     return;
   }
 
   // Add LibraryInfo if we have some.
   if (LibraryInfo)
     MPM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
 
   addInitialAliasAnalysisPasses(MPM);
void PassManagerBuilder::populateModulePassManager(
 
   // 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) {
     // Ensure we perform any last passes, but do so before renaming anonymous
     // globals in case the passes add any.
     addExtensionsToPM(EP_OptimizerLast, MPM);
+    MPM.add(createCanonicalizeAliasesPass());
     // Rename anon globals to be able to export them in the summary.
     MPM.add(createNameAnonGlobalPass());
     return;
   }
 
   if (PerformThinLTO)
     // Optimize globals now when performing ThinLTO, this enables more
     // optimizations later.
if (EnableHotColdSplit)
     MPM.add(createHotColdSplittingPass());
 
   // LoopSink (and other loop passes since the last simplifyCFG) might have
   // resulted in single-entry-single-exit or empty blocks. Clean up the CFG.
   MPM.add(createCFGSimplificationPass());
 
   addExtensionsToPM(EP_OptimizerLast, MPM);
 
   // Rename anon globals to be able to handle them in the summary
-  if (PrepareForLTO)
+  if (PrepareForLTO) {
+    MPM.add(createCanonicalizeAliasesPass());
     MPM.add(createNameAnonGlobalPass());
   }
+}
 
 void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   // Load sample profile before running the LTO optimization pipeline.
   if (!PGOSampleUse.empty()) {
     PM.add(createPruneEHPass());
     PM.add(createSampleProfileLoaderPass(PGOSampleUse));
   }
 

lib/Transforms/Utils/CMakeLists.txt

 add_llvm_library(LLVMTransformUtils
   ASanStackFrameLayout.cpp
   AddDiscriminators.cpp
   BasicBlockUtils.cpp
   BreakCriticalEdges.cpp
   BuildLibCalls.cpp
   BypassSlowDivision.cpp
   CallPromotionUtils.cpp
+  CanonicalizeAliases.cpp
   CloneFunction.cpp
   CloneModule.cpp
   CodeExtractor.cpp
   CtorUtils.cpp
   DemoteRegToStack.cpp
   EntryExitInstrumenter.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.
+//
+//===----------------------------------------------------------------------===//
+//
+// Currently this file implements partial alias canonicalization, to
+// flatten chains of aliases (also done by GlobalOpt, but not on for
+// O0 compiles). E.g.
+//  @a = alias i8, i8 *@b
+//  @b = alias i8, i8 *@g
+//
+// will be converted to:
+//  @a = alias i8, i8 *@g  <-- @a is now an alias to base object @g
+//  @b = alias i8, i8 *@g
+//
+// Eventually this file will implement full alias canonicalation, 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;
+
+namespace {
+
+static Constant *canonicalizeAlias(Constant *C, bool &Changed) {
+  if (auto *GA = dyn_cast<GlobalAlias>(C)) {
+    auto *NewAliasee = canonicalizeAlias(GA->getAliasee(), Changed);
+    if (NewAliasee != GA->getAliasee()) {
+      GA->setAliasee(NewAliasee);
+      Changed = true;
+    }
+    return NewAliasee;
+  }
+
+  auto *CE = dyn_cast<ConstantExpr>(C);
+  if (!CE)
+    return C;
+
+  std::vector<Constant *> Ops;
+  bool Modified = false;
+  for (Use &U : CE->operands()) {
+    auto *NewOp = canonicalizeAlias(cast<Constant>(U), Changed);
+    if (NewOp != cast<Constant>(U))
+      Modified = true;
+    Ops.push_back(NewOp);
+  }
+  return Modified ? CE->getWithOperands(Ops) : CE;
+}
+
+/// Convert aliases to canonical form.
+static bool canonicalizeAliases(Module &M) {
+  bool Changed = false;
+  for (auto &GA : M.aliases()) {
+    canonicalizeAlias(&GA, Changed);
+  }
+  return Changed;
+}
+
+// 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 CanonicalizeAliasesPass::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();
+}
+} // namespace llvm

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
+; RUN: opt -S -passes=canonicalize-aliases < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK-DAG: @analias = alias void (), void ()* @aliasee
+; CHECK-DAG: @anotheralias = alias void (), void ()* @aliasee
+; CHECK-DAG: define void @aliasee()
+
+@analias = alias void (), void ()* @anotheralias
+@anotheralias = alias void (), bitcast (void ()* @aliasee to void ()*)
+
+; Function Attrs: nounwind uwtable
+define void @aliasee() #0 {
+entry:
+    ret void
+}
+
+%struct.S1 = type { i32, i32, i32 }
+
+; CHECK-DAG: @S = global %struct.S1 { i32 31, i32 32, i32 33 }
+; CHECK-DAG: @Salias = alias i32, getelementptr inbounds (%struct.S1, %struct.S1* @S, i32 0, i32 1)
+; CHECK-DAG: @Salias2 = alias i32, getelementptr inbounds (%struct.S1, %struct.S1* @S, i32 0, i32 1)
+; CHECK-DAG: @Salias3 = alias i32, getelementptr inbounds (%struct.S1, %struct.S1* @S, i32 0, i32 1)
+
+@S = global %struct.S1 { i32 31, i32 32, i32 33 }, align 4
+@Salias = alias i32, getelementptr inbounds (%struct.S1, %struct.S1* @S, i32 0, i32 1)
+@Salias2 = alias i32, i32* @Salias
+@Salias3 = alias i32, i32* @Salias2
+
+; CHECK-DAG: @Salias4 = alias %struct.S1, %struct.S1* @S
+; CHECK-DAG: @Salias5 = alias i32, getelementptr inbounds (%struct.S1, %struct.S1* @S, i32 0, i32 1)
+
+@Salias4 = alias %struct.S1, %struct.S1* @S
+@Salias5 = alias i32, getelementptr inbounds (%struct.S1, %struct.S1* @Salias4, i32 0, i32 1)