PNaCl: Add a pass to expand out Clang's use of registers of struct type

Clang's implementation of C++ method pointers generates IR that uses
LLVM registers with struct type -- specifically, loads and stores of
struct values, and extractvalue instructions.  See
lib/CodeGen/ItaniumCXXABI.cpp in Clang.  Add a pass, ExpandStructRegs,
which expands out those uses.

Factor out a function from ExpandArithWithOverflow so that the two
passes can share some code.

BUG=https://code.google.com/p/nativeclient/issues/detail?id=3343
TEST=*.ll tests + trybots + GCC torture tests

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

5 files changed, 203 insertions, 27 deletions

diff --git a/lib/Transforms/NaCl/CMakeLists.txt b/lib/Transforms/NaCl/CMakeLists.txt
index 027bb46a14..1424f95026 100644
--- a/lib/Transforms/NaCl/CMakeLists.txt
+++ b/lib/Transforms/NaCl/CMakeLists.txt
@@ -6,6 +6,7 @@ add_llvm_library(LLVMNaClTransforms
   ExpandCtors.cpp
   ExpandGetElementPtr.cpp
   ExpandSmallArguments.cpp
+  ExpandStructRegs.cpp
   ExpandTls.cpp
   ExpandTlsConstantExpr.cpp
   ExpandUtils.cpp
diff --git a/lib/Transforms/NaCl/ExpandArithWithOverflow.cpp b/lib/Transforms/NaCl/ExpandArithWithOverflow.cpp
index e120b24293..1c879d524c 100644
--- a/lib/Transforms/NaCl/ExpandArithWithOverflow.cpp
+++ b/lib/Transforms/NaCl/ExpandArithWithOverflow.cpp
@@ -94,9 +94,10 @@ static bool ExpandOpForIntSize(Module *M, unsigned Bits, bool Mul) {
                          "*.with.overflow must be a constant");
     }
 
-    Value *ArithResult = BinaryOperator::Create(
+    SmallVector<Value *, 2> Fields;
+    Fields.push_back(BinaryOperator::Create(
         (Mul ? Instruction::Mul : Instruction::Add), VariableArg, ConstantArg,
-        Call->getName() + ".arith", Call);
+        Call->getName() + ".arith", Call));
 
     uint64_t ArgMax;
     if (Mul) {
@@ -104,32 +105,10 @@ static bool ExpandOpForIntSize(Module *M, unsigned Bits, bool Mul) {
     } else {
       ArgMax = UintTypeMax(Bits) - ConstantArg->getZExtValue();
     }
-    Value *Overflow = new ICmpInst(
+    Fields.push_back(new ICmpInst(
         Call, CmpInst::ICMP_UGT, VariableArg, ConstantInt::get(IntTy, ArgMax),
-        Call->getName() + ".overflow");
-
-    for (Value::use_iterator FieldIter = Call->use_begin(),
-           E = Call->use_end(); FieldIter != E; ) {
-      User *U = *FieldIter++;
-      ExtractValueInst *Field = dyn_cast<ExtractValueInst>(U);
-      if (!Field) {
-        errs() << "Use: " << *U << "\n";
-        report_fatal_error(
-            "ExpandArithWithOverflow: Use is not an extractvalue");
-      }
-      if (Field->getNumIndices() != 1) {
-        report_fatal_error("ExpandArithWithOverflow: Unexpected indices");
-      }
-      unsigned Index = Field->getIndices()[0];
-      if (Index == 0) {
-        Field->replaceAllUsesWith(ArithResult);
-      } else if (Index == 1) {
-        Field->replaceAllUsesWith(Overflow);
-      } else {
-        report_fatal_error("ExpandArithWithOverflow: Unexpected index");
-      }
-      Field->eraseFromParent();
-    }
+        Call->getName() + ".overflow"));
+    ReplaceUsesOfStructWithFields(Call, Fields);
     Call->eraseFromParent();
   }
   Intrinsic->eraseFromParent();
diff --git a/lib/Transforms/NaCl/ExpandStructRegs.cpp b/lib/Transforms/NaCl/ExpandStructRegs.cpp
new file mode 100644
index 0000000000..eacad1f7f4
--- /dev/null
+++ b/lib/Transforms/NaCl/ExpandStructRegs.cpp
@@ -0,0 +1,168 @@
+//===- ExpandStructRegs.cpp - Expand out variables with struct type--------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass expands out some uses of LLVM variables
+// (a.k.a. registers) of struct type.  It replaces loads and stores of
+// structs with separate loads and stores of the structs' fields.  The
+// motivation is to omit struct types from PNaCl's stable ABI.
+//
+// ExpandStructRegs does not handle all possible uses of struct
+// values.  It is only intended to handle the uses that Clang
+// generates.  Clang generates struct loads and stores, along with
+// extractvalue instructions, in its implementation of C++ method
+// pointers.
+//
+// ExpandStructRegs does not handle:
+//
+//  * The insertvalue instruction, which does not appear to be
+//    generated anywhere.
+//  * PHI nodes of struct type.
+//  * Function types containing arguments or return values of struct
+//    type without the "byval" or "sret" attributes.  Since by-value
+//    struct-passing generally uses "byval"/"sret", this does not
+//    matter.
+//
+// Other limitations:
+//
+//  * ExpandStructRegs does not attempt to use memcpy() where that
+//    might be more appropriate than copying fields individually.
+//  * ExpandStructRegs does not preserve the contents of padding
+//    between fields when copying structs.  However, the contents of
+//    padding fields are not defined anyway.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/NaCl.h"
+
+using namespace llvm;
+
+namespace {
+  struct ExpandStructRegs : public FunctionPass {
+    static char ID; // Pass identification, replacement for typeid
+    ExpandStructRegs() : FunctionPass(ID) {
+      initializeExpandStructRegsPass(*PassRegistry::getPassRegistry());
+    }
+
+    virtual bool runOnFunction(Function &F);
+  };
+}
+
+char ExpandStructRegs::ID = 0;
+INITIALIZE_PASS(ExpandStructRegs, "expand-struct-regs",
+                "Expand out variables with struct types", false, false)
+
+template <class InstType>
+static void ProcessLoadOrStoreAttrs(InstType *Dest, InstType *Src) {
+  CopyDebug(Dest, Src);
+  Dest->setVolatile(Src->isVolatile());
+  if (Src->isAtomic()) {
+    errs() << "Use: " << *Src << "\n";
+    report_fatal_error("Atomic struct loads/stores not supported");
+  }
+  // Make a pessimistic assumption about alignment.  Preserving
+  // alignment information here is tricky and is not really desirable
+  // for PNaCl because mistakes here could lead to non-portable
+  // behaviour.
+  Dest->setAlignment(1);
+}
+
+static void ExpandStore(StoreInst *Store) {
+  StructType *STy = cast<StructType>(Store->getValueOperand()->getType());
+  // Create a separate store instruction for each struct field.
+  for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) {
+    SmallVector<Value *, 2> Indexes;
+    Indexes.push_back(ConstantInt::get(Store->getContext(), APInt(32, 0)));
+    Indexes.push_back(ConstantInt::get(Store->getContext(), APInt(32, Index)));
+    Value *GEP = CopyDebug(GetElementPtrInst::Create(
+                               Store->getPointerOperand(), Indexes,
+                               Store->getPointerOperand()->getName() + ".index",
+                               Store), Store);
+    SmallVector<unsigned, 1> EVIndexes;
+    EVIndexes.push_back(Index);
+    Value *Field;
+    if (Constant *C = dyn_cast<Constant>(Store->getValueOperand())) {
+      Field = ConstantExpr::getExtractValue(C, EVIndexes);
+    } else {
+      Field = ExtractValueInst::Create(
+          Store->getValueOperand(), EVIndexes, "", Store);
+    }
+    StoreInst *NewStore = new StoreInst(Field, GEP, Store);
+    ProcessLoadOrStoreAttrs(NewStore, Store);
+  }
+  Store->eraseFromParent();
+}
+
+static void ExpandLoad(LoadInst *Load) {
+  StructType *STy = cast<StructType>(Load->getType());
+  // Create a separate load instruction for each struct field.
+  SmallVector<Value *, 5> Fields;
+  for (unsigned Index = 0; Index < STy->getNumElements(); ++Index) {
+    SmallVector<Value *, 2> Indexes;
+    Indexes.push_back(ConstantInt::get(Load->getContext(), APInt(32, 0)));
+    Indexes.push_back(ConstantInt::get(Load->getContext(), APInt(32, Index)));
+    Value *GEP = CopyDebug(
+        GetElementPtrInst::Create(Load->getPointerOperand(), Indexes,
+                                  Load->getName() + ".index", Load), Load);
+    LoadInst *NewLoad = new LoadInst(GEP, Load->getName() + ".field", Load);
+    ProcessLoadOrStoreAttrs(NewLoad, Load);
+    Fields.push_back(NewLoad);
+  }
+  ReplaceUsesOfStructWithFields(Load, Fields);
+  Load->eraseFromParent();
+}
+
+bool ExpandStructRegs::runOnFunction(Function &Func) {
+  bool Changed = false;
+
+  // It is not safe to iterate through the basic block while
+  // deleting extractvalue instructions, so make a copy of the
+  // instructions we will operate on first.
+  SmallVector<StoreInst *, 10> Stores;
+  SmallVector<LoadInst *, 10> Loads;
+  for (Function::iterator BB = Func.begin(), E = Func.end();
+       BB != E; ++BB) {
+    for (BasicBlock::iterator Inst = BB->begin(), E = BB->end();
+         Inst != E; ++Inst) {
+      if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
+        if (Store->getValueOperand()->getType()->isStructTy()) {
+          Stores.push_back(Store);
+        }
+      } else if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
+        if (Load->getType()->isStructTy()) {
+          Loads.push_back(Load);
+        }
+      }
+    }
+  }
+
+  // Expand stores first.  This will introduce extractvalue
+  // instructions.
+  for (SmallVectorImpl<StoreInst *>::iterator Inst = Stores.begin(),
+         E = Stores.end(); Inst != E; ++Inst) {
+    ExpandStore(*Inst);
+    Changed = true;
+  }
+  // Expanding loads will remove the extractvalue instructions we
+  // previously introduced.
+  for (SmallVectorImpl<LoadInst *>::iterator Inst = Loads.begin(),
+         E = Loads.end(); Inst != E; ++Inst) {
+    ExpandLoad(*Inst);
+    Changed = true;
+  }
+  return Changed;
+}
+
+FunctionPass *llvm::createExpandStructRegsPass() {
+  return new ExpandStructRegs();
+}
diff --git a/lib/Transforms/NaCl/ExpandUtils.cpp b/lib/Transforms/NaCl/ExpandUtils.cpp
index 913e0d6607..75f5dad114 100644
--- a/lib/Transforms/NaCl/ExpandUtils.cpp
+++ b/lib/Transforms/NaCl/ExpandUtils.cpp
@@ -11,6 +11,7 @@
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
+#include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/NaCl.h"
 
 using namespace llvm;
@@ -58,3 +59,27 @@ Function *llvm::RecreateFunction(Function *Func, FunctionType *NewType) {
                                Func->getFunctionType()->getPointerTo()));
   return NewFunc;
 }
+
+void llvm::ReplaceUsesOfStructWithFields(
+    Value *StructVal, const SmallVectorImpl<Value *> &Fields) {
+  while (!StructVal->use_empty()) {
+    User *U = StructVal->use_back();
+    ExtractValueInst *Field = dyn_cast<ExtractValueInst>(U);
+    if (!Field) {
+      errs() << "Use: " << *U << "\n";
+      report_fatal_error("ReplaceUsesOfStructWithFields: "
+                         "Struct use site is not an extractvalue");
+    }
+    if (Field->getNumIndices() != 1) {
+      // If we wanted to handle this case, we could split the
+      // extractvalue into two extractvalues and run ExpandLoad()
+      // multiple times.
+      errs() << "Use: " << *U << "\n";
+      report_fatal_error("ReplaceUsesOfStructWithFields: Unexpected indices");
+    }
+    unsigned Index = Field->getIndices()[0];
+    assert(Index < Fields.size());
+    Field->replaceAllUsesWith(Fields[Index]);
+    Field->eraseFromParent();
+  }
+}
diff --git a/lib/Transforms/NaCl/PNaClABISimplify.cpp b/lib/Transforms/NaCl/PNaClABISimplify.cpp
index 848d340e22..8c945800af 100644
--- a/lib/Transforms/NaCl/PNaClABISimplify.cpp
+++ b/lib/Transforms/NaCl/PNaClABISimplify.cpp
@@ -28,7 +28,10 @@ void llvm::PNaClABISimplifyAddPreOptPasses(PassManager &PM) {
   // Remove landingpad blocks made unreachable by LowerInvoke.
   PM.add(createCFGSimplificationPass());
 
+  // Expand out some uses of struct types.
   PM.add(createExpandArithWithOverflowPass());
+  PM.add(createExpandStructRegsPass());
+
   PM.add(createExpandVarArgsPass());
   PM.add(createExpandCtorsPass());
   PM.add(createResolveAliasesPass());