PNaCl: Add a pass to convert llvm.global_ctors to __init_array_start/end

This pass converts LLVM's special symbols llvm.global_ctors and
llvm.global_dtors to concrete arrays, __init_array_start/end and
__fini_array_start/end, that are usable by a C library.

The pass sorts the contents of global_ctors/dtors according to the
priority values they contain and removes the priority values.

This pass will allow us to simplify the PNaCl ABI so that less is done
at translation time.

BUG= http://code.google.com/p/nativeclient/issues/detail?id=3018
TEST=test/Transforms/NaCl/expand-ctors*.ll

Review URL: https://codereview.chromium.org/10977030

12 files changed, 259 insertions, 2 deletions

diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index 4c93d480dd..87899fc360 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -261,6 +261,7 @@ void initializeUnpackMachineBundlesPass(PassRegistry&);
 void initializeFinalizeMachineBundlesPass(PassRegistry&);
 void initializeBBVectorizePass(PassRegistry&);
 void initializeMachineFunctionPrinterPassPass(PassRegistry&);
+void initializeExpandCtorsPass(PassRegistry&); // @LOCALMOD
 void initializeNaClCcRewritePass(PassRegistry&); // @LOCALMOD
 }
 
diff --git a/include/llvm/Transforms/NaCl.h b/include/llvm/Transforms/NaCl.h
new file mode 100644
index 0000000000..fe29463a8b
--- /dev/null
+++ b/include/llvm/Transforms/NaCl.h
@@ -0,0 +1,21 @@
+//===-- NaCl.h - NaCl Transformations ---------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_NACL_H
+#define LLVM_TRANSFORMS_NACL_H
+
+namespace llvm {
+
+class ModulePass;
+
+ModulePass *createExpandCtorsPass();
+
+}
+
+#endif
diff --git a/lib/Transforms/CMakeLists.txt b/lib/Transforms/CMakeLists.txt
index de1353e6c1..9fa690971a 100644
--- a/lib/Transforms/CMakeLists.txt
+++ b/lib/Transforms/CMakeLists.txt
@@ -5,3 +5,4 @@ add_subdirectory(Scalar)
 add_subdirectory(IPO)
 add_subdirectory(Vectorize)
 add_subdirectory(Hello)
+add_subdirectory(NaCl)
diff --git a/lib/Transforms/LLVMBuild.txt b/lib/Transforms/LLVMBuild.txt
index f7bca064c7..001ba5d232 100644
--- a/lib/Transforms/LLVMBuild.txt
+++ b/lib/Transforms/LLVMBuild.txt
@@ -16,7 +16,7 @@
 ;===------------------------------------------------------------------------===;
 
 [common]
-subdirectories = IPO InstCombine Instrumentation Scalar Utils Vectorize
+subdirectories = IPO InstCombine Instrumentation Scalar Utils Vectorize NaCl
 
 [component_0]
 type = Group
diff --git a/lib/Transforms/Makefile b/lib/Transforms/Makefile
index fb6fa26f11..ae03ff32c5 100644
--- a/lib/Transforms/Makefile
+++ b/lib/Transforms/Makefile
@@ -8,7 +8,7 @@
 ##===----------------------------------------------------------------------===##
 
 LEVEL = ../..
-PARALLEL_DIRS = Utils Instrumentation Scalar InstCombine IPO Vectorize Hello
+PARALLEL_DIRS = Utils Instrumentation Scalar InstCombine IPO Vectorize Hello NaCl
 
 ifeq ($(NACL_SANDBOX),1)
   PARALLEL_DIRS := $(filter-out Hello, $(PARALLEL_DIRS))
diff --git a/lib/Transforms/NaCl/CMakeLists.txt b/lib/Transforms/NaCl/CMakeLists.txt
new file mode 100644
index 0000000000..d634ad9655
--- /dev/null
+++ b/lib/Transforms/NaCl/CMakeLists.txt
@@ -0,0 +1,5 @@
+add_llvm_library(LLVMTransformsNaCl
+  ExpandCtors.cpp
+  )
+
+add_dependencies(LLVMTransformsNaCl intrinsics_gen)
diff --git a/lib/Transforms/NaCl/ExpandCtors.cpp b/lib/Transforms/NaCl/ExpandCtors.cpp
new file mode 100644
index 0000000000..9c5f2cd2d7
--- /dev/null
+++ b/lib/Transforms/NaCl/ExpandCtors.cpp
@@ -0,0 +1,143 @@
+//===- ExpandCtors.cpp - Convert ctors/dtors to concrete arrays -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass converts LLVM's special symbols llvm.global_ctors and
+// llvm.global_dtors to concrete arrays, __init_array_start/end and
+// __fini_array_start/end, that are usable by a C library.
+//
+// This pass sorts the contents of global_ctors/dtors according to the
+// priority values they contain and removes the priority values.
+//
+//===----------------------------------------------------------------------===//
+
+#include <vector>
+
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Instructions.h"
+#include "llvm/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/NaCl.h"
+#include "llvm/TypeBuilder.h"
+
+using namespace llvm;
+
+namespace {
+  struct ExpandCtors : public ModulePass {
+    static char ID; // Pass identification, replacement for typeid
+    ExpandCtors() : ModulePass(ID) {
+      initializeExpandCtorsPass(*PassRegistry::getPassRegistry());
+    }
+
+    virtual bool runOnModule(Module &M);
+  };
+}
+
+char ExpandCtors::ID = 0;
+INITIALIZE_PASS(ExpandCtors, "nacl-expand-ctors",
+                "Hook up constructor and destructor arrays to libc",
+                false, false)
+
+static void setGlobalVariableValue(Module &M, const char *Name,
+                                   Constant *Value) {
+  GlobalVariable *Var = M.getNamedGlobal(Name);
+  if (!Var) {
+    // This warning can happen in a program that does not use a libc
+    // and so does not call the functions in __init_array_start or
+    // __fini_array_end.  Such a program might be linked with
+    // "-nostdlib".
+    errs() << "Warning: Variable " << Name << " not referenced\n";
+  } else {
+    if (Var->hasInitializer()) {
+      report_fatal_error(std::string("Variable ") + Name +
+                         " already has an initializer");
+    }
+    Var->replaceAllUsesWith(ConstantExpr::getBitCast(Value, Var->getType()));
+    Var->eraseFromParent();
+  }
+}
+
+struct FuncArrayEntry {
+  uint64_t priority;
+  Constant *func;
+};
+
+static bool compareEntries(FuncArrayEntry Entry1, FuncArrayEntry Entry2) {
+  return Entry1.priority < Entry2.priority;
+}
+
+static void defineFuncArray(Module &M, const char *LlvmArrayName,
+                            const char *StartSymbol,
+                            const char *EndSymbol) {
+  std::vector<Constant*> Funcs;
+
+  GlobalVariable *Array = M.getNamedGlobal(LlvmArrayName);
+  if (Array && Array->hasInitializer()) {
+    ConstantArray *InitList = cast<ConstantArray>(Array->getInitializer());
+    std::vector<FuncArrayEntry> FuncsToSort;
+    for (unsigned Index = 0; Index < InitList->getNumOperands(); ++Index) {
+      ConstantStruct *CS = cast<ConstantStruct>(InitList->getOperand(Index));
+      FuncArrayEntry Entry;
+      Entry.priority = cast<ConstantInt>(CS->getOperand(0))->getZExtValue();
+      Entry.func = CS->getOperand(1);
+      FuncsToSort.push_back(Entry);
+    }
+
+    std::sort(FuncsToSort.begin(), FuncsToSort.end(), compareEntries);
+    for (std::vector<FuncArrayEntry>::iterator Iter = FuncsToSort.begin();
+         Iter != FuncsToSort.end();
+         ++Iter) {
+      Funcs.push_back(Iter->func);
+    }
+    // No code should be referencing global_ctors/global_dtors,
+    // because this symbol is internal to LLVM.
+    Array->eraseFromParent();
+  }
+
+  Type *FuncTy = FunctionType::get(Type::getVoidTy(M.getContext()), false);
+  Type *FuncPtrTy = FuncTy->getPointerTo();
+  ArrayType *ArrayTy = ArrayType::get(FuncPtrTy, Funcs.size());
+  GlobalVariable *NewArray =
+      new GlobalVariable(M, ArrayTy, /* isConstant= */ true,
+                         GlobalValue::InternalLinkage,
+                         ConstantArray::get(ArrayTy, Funcs));
+  setGlobalVariableValue(M, StartSymbol, NewArray);
+  // We do this last so that LLVM gives NewArray the name
+  // "__{init,fini}_array_start" without adding any suffixes to
+  // disambiguate from the original GlobalVariable's name.  This is
+  // not essential -- it just makes the output easier to understand
+  // when looking at symbols for debugging.
+  NewArray->setName(StartSymbol);
+
+  // We replace "__{init,fini}_array_end" with the address of the end
+  // of NewArray.  This removes the name "__{init,fini}_array_end"
+  // from the output, which is not ideal for debugging.  Ideally we
+  // would convert "__{init,fini}_array_end" to being a GlobalAlias
+  // that points to the end of the array.  However, unfortunately LLVM
+  // does not generate correct code when a GlobalAlias contains a
+  // GetElementPtr ConstantExpr.
+  Constant *NewArrayEnd =
+      ConstantExpr::getGetElementPtr(NewArray,
+                                     ConstantInt::get(M.getContext(),
+                                                      APInt(32, 1)));
+  setGlobalVariableValue(M, EndSymbol, NewArrayEnd);
+}
+
+bool ExpandCtors::runOnModule(Module &M) {
+  defineFuncArray(M, "llvm.global_ctors",
+                  "__init_array_start", "__init_array_end");
+  defineFuncArray(M, "llvm.global_dtors",
+                  "__fini_array_start", "__fini_array_end");
+  return true;
+}
+
+ModulePass *llvm::createExpandCtorsPass() {
+  return new ExpandCtors();
+}
diff --git a/lib/Transforms/NaCl/LLVMBuild.txt b/lib/Transforms/NaCl/LLVMBuild.txt
new file mode 100644
index 0000000000..2f1522b3e5
--- /dev/null
+++ b/lib/Transforms/NaCl/LLVMBuild.txt
@@ -0,0 +1,23 @@
+;===- ./lib/Transforms/NaCl/LLVMBuild.txt ----------------------*- Conf -*--===;
+;
+;                     The LLVM Compiler Infrastructure
+;
+; This file is distributed under the University of Illinois Open Source
+; License. See LICENSE.TXT for details.
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+;   http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Library
+name = NaCl
+parent = Transforms
+library_name = NaCl
+required_libraries = Core
diff --git a/lib/Transforms/NaCl/Makefile b/lib/Transforms/NaCl/Makefile
new file mode 100644
index 0000000000..ecf8db6eae
--- /dev/null
+++ b/lib/Transforms/NaCl/Makefile
@@ -0,0 +1,15 @@
+##===- lib/Transforms/NaCl/Makefile-------------------------*- Makefile -*-===##
+#
+#                     The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../../..
+LIBRARYNAME = LLVMTransformsNaCl
+BUILD_ARCHIVE = 1
+
+include $(LEVEL)/Makefile.common
+
diff --git a/test/Transforms/NaCl/expand-ctors-empty.ll b/test/Transforms/NaCl/expand-ctors-empty.ll
new file mode 100644
index 0000000000..4368270765
--- /dev/null
+++ b/test/Transforms/NaCl/expand-ctors-empty.ll
@@ -0,0 +1,11 @@
+; Currently we do not define __{init,fini}_array_end as named aliases.
+; RUN: opt < %s -nacl-expand-ctors -S | not grep __init_array_end
+; RUN: opt < %s -nacl-expand-ctors -S | not grep __fini_array_end
+
+; RUN: opt < %s -nacl-expand-ctors -S | FileCheck %s
+
+; If llvm.global_ctors is not present, it is treated as if it is an
+; empty array, and __{init,fini}_array_start are defined anyway.
+
+; CHECK: @__init_array_start = internal constant [0 x void ()*] zeroinitializer
+; CHECK: @__fini_array_start = internal constant [0 x void ()*] zeroinitializer
diff --git a/test/Transforms/NaCl/expand-ctors.ll b/test/Transforms/NaCl/expand-ctors.ll
new file mode 100644
index 0000000000..7f202618e7
--- /dev/null
+++ b/test/Transforms/NaCl/expand-ctors.ll
@@ -0,0 +1,36 @@
+; We expect these symbol names to be removed:
+; RUN: opt < %s -nacl-expand-ctors -S | not grep llvm.global_ctors
+; RUN: opt < %s -nacl-expand-ctors -S | not grep __init_array_end
+; RUN: opt < %s -nacl-expand-ctors -S | not grep __fini_array_end
+
+; RUN: opt < %s -nacl-expand-ctors -S | FileCheck %s
+
+@llvm.global_ctors = appending global [3 x { i32, void ()* }]
+  [{ i32, void ()* } { i32 300, void ()* @init_func_A },
+   { i32, void ()* } { i32 100, void ()* @init_func_B },
+   { i32, void ()* } { i32 200, void ()* @init_func_C }]
+
+@__init_array_start = extern_weak global [0 x void ()*]
+@__init_array_end = extern_weak global [0 x void ()*]
+
+; CHECK: @__init_array_start = internal constant [3 x void ()*] [void ()* @init_func_B, void ()* @init_func_C, void ()* @init_func_A]
+; CHECK: @__fini_array_start = internal constant [0 x void ()*] zeroinitializer
+
+define void @init_func_A() { ret void }
+define void @init_func_B() { ret void }
+define void @init_func_C() { ret void }
+
+define [0 x void ()*]* @get_array_start() {
+  ret [0 x void ()*]* @__init_array_start;
+}
+; CHECK: @get_array_start()
+; CHECK: ret {{.*}} @__init_array_start
+
+define [0 x void ()*]* @get_array_end() {
+  ret [0 x void ()*]* @__init_array_end;
+}
+
+; @get_array_end() is converted to use a GetElementPtr that returns
+; the end of the generated array:
+; CHECK: @get_array_end()
+; CHECK: ret {{.*}} bitcast ([3 x void ()*]* getelementptr inbounds ([3 x void ()*]* @__init_array_start, i32 1)
diff --git a/tools/opt/opt.cpp b/tools/opt/opt.cpp
index 7ecd25c6b7..4a8041d2a0 100644
--- a/tools/opt/opt.cpp
+++ b/tools/opt/opt.cpp
@@ -504,6 +504,7 @@ int main(int argc, char **argv) {
   initializeInstCombine(Registry);
   initializeInstrumentation(Registry);
   initializeTarget(Registry);
+  initializeExpandCtorsPass(Registry);
 
   cl::ParseCommandLineOptions(argc, argv,
     "llvm .bc -> .bc modular optimizer and analysis printer\n");