[AsmPrinter] Print aliases in topological order

[timshen]

Summary

Print aliases in topological order, that is, for any alias a = b,
b must be printed before a. This is because on some targets (e.g. PowerPC)
linker expects aliases in such an order to generate correct TOC information.

For example, on PowerPC, GCC will produce following symbol:

~ % readelf -s tcmalloc_gcc.pic.o|grep '_Znam\b'
  1057: 00000000000001e4   100 FUNC    GLOBAL DEFAULT [<localentry>: 8]   508 _Znam

But LLVM without this change will produce:

~ % readelf -s tcmalloc_llvm.pic.o|grep '_Znam\b'
   870: 0000000000000000   100 FUNC    GLOBAL DEFAULT   94 _Znam

I'm not sure if it's the right change, since I don't know who is supposed to do this ordering.

[echristo]

This seems to be as good as anywhere else to do this.

It's also crazy, but well spotted. One inline nit.

-eric

lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1199

Nit: No braces around single conditionals.

[timshen]

Removed unnecessary braces.

[timshen]

Thanks!

lib/CodeGen/AsmPrinter/AsmPrinter.cpp

if (MAI->getWeakRefDirective()) {
     for (const auto &F : M) {
       if (!F.hasExternalWeakLinkage())
         continue;
       OutStreamer->EmitSymbolAttribute(getSymbol(&F), MCSA_WeakReference);
     }
   }
 
   OutStreamer->AddBlankLine();
-  for (const auto &Alias : M.aliases()) {
+  const auto printAlias = [this, &M](const GlobalAlias &Alias) {
     MCSymbol *Name = getSymbol(&Alias);
 
     if (Alias.hasExternalLinkage() || !MAI->getWeakRefDirective())
       OutStreamer->EmitSymbolAttribute(Name, MCSA_Global);
     else if (Alias.hasWeakLinkage() || Alias.hasLinkOnceLinkage())
       OutStreamer->EmitSymbolAttribute(Name, MCSA_WeakReference);
     else
       assert(Alias.hasLocalLinkage() && "Invalid alias linkage");
const auto printAlias = [this, &M](const GlobalAlias &Alias) {
     const GlobalObject *BaseObject = Alias.getBaseObject();
     if (MAI->hasDotTypeDotSizeDirective() && Alias.getValueType()->isSized() &&
         (!BaseObject || BaseObject->hasPrivateLinkage())) {
       const DataLayout &DL = M.getDataLayout();
       uint64_t Size = DL.getTypeAllocSize(Alias.getValueType());
       OutStreamer->emitELFSize(cast<MCSymbolELF>(Name),
                                MCConstantExpr::create(Size, OutContext));
     }
+  };
+  // Print aliases in topological order, that is, for each alias a = b,
+  // b must be printed before a.
+  // This is because on some targets (e.g. PowerPC) linker expects aliases in
+  // such an order to generate correct TOC information.
+  SmallVector<const GlobalAlias *, 16> AliasStack;
+  SmallPtrSet<const GlobalAlias *, 16> AliasVisited;
+  for (const auto &Alias : M.aliases()) {
+    for (const GlobalAlias *Cur = &Alias; Cur;
+         Cur = dyn_cast<GlobalAlias>(Cur->getAliasee())) {
+      if (!AliasVisited.insert(Cur).second)
+        break;
+      AliasStack.push_back(Cur);
+    }
+    for (const GlobalAlias *AncestorAlias : reverse(AliasStack))
+      printAlias(*AncestorAlias);
+    AliasStack.clear();
   }
 
   GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>();
   assert(MI && "AsmPrinter didn't require GCModuleInfo?");
   for (GCModuleInfo::iterator I = MI->end(), E = MI->begin(); I != E; )
     if (GCMetadataPrinter *MP = GetOrCreateGCPrinter(**--I))
       MP->finishAssembly(M, *MI, *this);
 

test/CodeGen/Generic/asm-printer-topological-order.ll

+; RUN: llc < %s | FileCheck %s
+
+@TestA = alias void (), void ()* @TestC
+@TestB = alias void (), void ()* @TestC
+@TestC = alias void (), void ()* @TestD
+
+define void @TestD() {
+entry:
+  ret void
+}
+
+; CHECK-LABEL: TestD:
+; CHECK: TestC = TestD
+; CHECK-DAG: TestB = TestC
+; CHECK-DAG: TestA = TestC