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

7 files changed, 189 insertions, 2 deletions

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
+