PNaCl: Handle nested structure types in -expand-struct-regs.

lib/Transforms/NaCl/ExpandStructRegs.cpp

Index: lib/Transforms/NaCl/ExpandStructRegs.cpp
diff --git a/lib/Transforms/NaCl/ExpandStructRegs.cpp b/lib/Transforms/NaCl/ExpandStructRegs.cpp
index dace46eacf8ecb29ff42e312440b6c0c66d8800f..d1749c2db306b046c2a772af54ba7c4414505ee4 100644
--- a/lib/Transforms/NaCl/ExpandStructRegs.cpp
+++ b/lib/Transforms/NaCl/ExpandStructRegs.cpp
@@ -21,7 +21,6 @@
 //
 // ExpandStructRegs does not handle:
 //
-//  * Nested struct types.
 //  * Array types.
 //  * Function types containing arguments or return values of struct
 //    type without the "byval" or "sret" attributes.  Since by-value
@@ -63,7 +62,10 @@ char ExpandStructRegs::ID = 0;
 INITIALIZE_PASS(ExpandStructRegs, "expand-struct-regs",
                 "Expand out variables with struct types", false, false)
 
-static void SplitUpPHINode(PHINode *Phi) {
+static bool DoAnotherPass(Type *Ty) { return isa<StructType>(Ty); }
+static bool DoAnotherPass(Value *V) { return DoAnotherPass(V->getType()); }
+
+static void SplitUpPHINode(PHINode *Phi, bool &NeedsAnotherPass) {

[JF, 2014/12/06 23:52:13]

I'd return a bool here instead, same with the other functions.

[Richard Diamond, 2014/12/09 04:33:15]

Done.

   StructType *STy = cast<StructType>(Phi->getType());
 
   Value *NewStruct = UndefValue::get(STy);
@@ -74,9 +76,11 @@ static void SplitUpPHINode(PHINode *Phi) {
     SmallVector<unsigned, 1> EVIndexes;
     EVIndexes.push_back(Index);
 
-    PHINode *NewPhi = PHINode::Create(
-        STy->getElementType(Index), Phi->getNumIncomingValues(),
-        Phi->getName() + ".index", Phi);
+    Type *ElemTy = STy->getElementType(Index);
+    NeedsAnotherPass = NeedsAnotherPass || DoAnotherPass(ElemTy);
+
+    PHINode *NewPhi = PHINode::Create(ElemTy, Phi->getNumIncomingValues(),
+                                      Phi->getName() + ".index", Phi);
     CopyDebug(NewPhi, Phi);
     for (unsigned PhiIndex = 0; PhiIndex < Phi->getNumIncomingValues();
          ++PhiIndex) {
@@ -98,7 +102,7 @@ static void SplitUpPHINode(PHINode *Phi) {
   Phi->eraseFromParent();
 }
 
-static void SplitUpSelect(SelectInst *Select) {
+static void SplitUpSelect(SelectInst *Select, bool &NeedsAnotherPass) {
   StructType *STy = cast<StructType>(Select->getType());
   Value *NewStruct = UndefValue::get(STy);
 
@@ -119,6 +123,8 @@ static void SplitUpSelect(SelectInst *Select) {
         SelectInst::Create(Select->getCondition(), TrueVal, FalseVal,
                            Select->getName() + ".index", Select), Select);
 
+    NeedsAnotherPass = NeedsAnotherPass || DoAnotherPass(NewSelect);
+
     // Reconstruct the original struct value.
     NewStruct = CopyDebug(
         InsertValueInst::Create(NewStruct, NewSelect, EVIndexes,
@@ -144,8 +150,9 @@ static void ProcessLoadOrStoreAttrs(InstType *Dest, InstType *Src) {
   Dest->setAlignment(1);
 }
 
-static void SplitUpStore(StoreInst *Store) {
+static void SplitUpStore(StoreInst *Store, bool &NeedsAnotherPass) {
   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;
@@ -155,6 +162,9 @@ static void SplitUpStore(StoreInst *Store) {
                                Store->getPointerOperand(), Indexes,
                                Store->getPointerOperand()->getName() + ".index",
                                Store), Store);
+    NeedsAnotherPass =
+        NeedsAnotherPass || DoAnotherPass(GEP->getType()->getContainedType(0));
+
     SmallVector<unsigned, 1> EVIndexes;
     EVIndexes.push_back(Index);
     Value *Field = ExtractValueInst::Create(Store->getValueOperand(),
@@ -165,7 +175,7 @@ static void SplitUpStore(StoreInst *Store) {
   Store->eraseFromParent();
 }
 
-static void SplitUpLoad(LoadInst *Load) {
+static void SplitUpLoad(LoadInst *Load, bool &NeedsAnotherPass) {
   StructType *STy = cast<StructType>(Load->getType());
   Value *NewStruct = UndefValue::get(STy);
 
@@ -178,6 +188,8 @@ static void SplitUpLoad(LoadInst *Load) {
         GetElementPtrInst::Create(Load->getPointerOperand(), Indexes,
                                   Load->getName() + ".index", Load), Load);
     LoadInst *NewLoad = new LoadInst(GEP, Load->getName() + ".field", Load);
+
+    NeedsAnotherPass = NeedsAnotherPass || DoAnotherPass(NewLoad);
     ProcessLoadOrStoreAttrs(NewLoad, Load);
 
     // Reconstruct the struct value.
@@ -191,38 +203,111 @@ static void SplitUpLoad(LoadInst *Load) {
   Load->eraseFromParent();
 }
 
-static void ExpandExtractValue(ExtractValueInst *EV) {
+static void ExpandExtractValue(ExtractValueInst *EV, bool &NeedsAnotherPass) {
   // Search for the insertvalue instruction that inserts the struct
   // field referenced by this extractvalue instruction.
   Value *StructVal = EV->getAggregateOperand();
-  Value *ResultField;
+  Value *ResultField = NULL;

[JF, 2014/12/06 23:52:13]

nullptr

[Richard Diamond, 2014/12/09 04:33:13]

Done.

+  size_t I = 0;
   for (;;) {
     if (InsertValueInst *IV = dyn_cast<InsertValueInst>(StructVal)) {
-      if (EV->getNumIndices() != 1 || IV->getNumIndices() != 1) {
-        errs() << "Value: " << *EV << "\n";
-        errs() << "Value: " << *IV << "\n";
-        report_fatal_error("ExpandStructRegs does not handle nested structs");
+      size_t J = 0;
+      for (; I < EV->getIndices().size() && J < IV->getIndices().size();
+           ++J, ++I) {
+        const bool Equal = (EV->getIndices()[I] == IV->getIndices()[J]);
+        if (J + 1 == IV->getIndices().size() && Equal) {
+          if (I + 1 == EV->getIndices().size()) {
+            // Match
+            ResultField = IV->getInsertedValueOperand();
+          } else {
+            StructVal = IV->getInsertedValueOperand();
+            ++I;
+          }
+          break;
+        } else if (!Equal) {
+          // No match.  Try the next struct value in the chain.
+          StructVal = IV->getAggregateOperand();
+          break;
+        }
       }
-      if (EV->getIndices()[0] == IV->getIndices()[0]) {
-        ResultField = IV->getInsertedValueOperand();
+      if (ResultField != NULL) {

[JF, 2014/12/06 23:52:13]

if (ResultField)

[Richard Diamond, 2014/12/09 04:33:16]

Done.

+        break;
+      } else if (I == EV->getIndices().size()) {
+        // We've found an insertvalue that inserts at one or more levels deeper
+        // than this extractvalue.
+        NeedsAnotherPass = true;
+        SmallVector<unsigned, 4> Indices(IV->getIndices().begin() + J,
+                                         IV->getIndices().end());
+
+        InsertValueInst *Insert = InsertValueInst::Create(
+            UndefValue::get(EV->getType()), IV->getInsertedValueOperand(),
+            Indices, "", EV);
+        ResultField = CopyDebug(Insert, EV);
         break;
       }
-      // No match.  Try the next struct value in the chain.
-      StructVal = IV->getAggregateOperand();
     } else if (Constant *C = dyn_cast<Constant>(StructVal)) {
-      ResultField = ConstantExpr::getExtractValue(C, EV->getIndices());
+      SmallVector<unsigned, 4> Indices(EV->getIndices().begin() + I,
+                                       EV->getIndices().end());
+      ResultField = ConstantExpr::getExtractValue(C, Indices);
+      break;
+    } else if (isa<LoadInst>(StructVal)) {
+      ResultField = StructVal;
       break;
     } else {
       errs() << "Value: " << *StructVal << "\n";
       report_fatal_error("Unrecognized struct value");
     }
   }
+
+  assert(ResultField != NULL);

[JF, 2014/12/06 23:52:13]

assert(ResultField);

[Richard Diamond, 2014/12/09 04:33:18]

Done.

   EV->replaceAllUsesWith(ResultField);
   EV->eraseFromParent();
 }
 
+static bool ExpandExtractValues(Function &Func) {
+  bool Changed = false;
+  bool NeedsAnotherPass = false;
+
+  // Expand out all the extractvalue instructions.  Also collect up
+  // the insertvalue instructions for later deletion so that we do not
+  // need to make extra passes across the whole function.
+  SmallVector<Instruction *, 10> ToErase;
+  for (Function::iterator BB = Func.begin(), E = Func.end(); BB != E; ++BB) {
+    for (BasicBlock::iterator Iter = BB->begin(), E = BB->end(); Iter != E;) {

[JF, 2014/12/06 23:52:13]

C++11 range-based for here.

[Richard Diamond, 2014/12/09 04:33:11]

The inner loop can't use a range-based for loop because we need to store the
next position before possibly deleting an extractvalue instruction.
The outer loop now uses a range-based for loop.

+      Instruction *Inst = Iter++;
+      if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Inst)) {
+        ExpandExtractValue(EV, NeedsAnotherPass);
+        Changed = true;
+      } else if (isa<InsertValueInst>(Inst)) {
+        ToErase.push_back(Inst);
+        Changed = true;
+      }
+    }
+  }
+
+  if (!NeedsAnotherPass) {
+    // Delete the insertvalue instructions.  These can reference each
+    // other, so we must do dropAllReferences() before doing
+    // eraseFromParent(), otherwise we will try to erase instructions
+    // that are still referenced.
+    for (SmallVectorImpl<Instruction *>::iterator I = ToErase.begin(),
+                                                  E = ToErase.end();
+         I != E; ++I) {

[JF, 2014/12/06 23:52:13]

Range-based.

[Richard Diamond, 2014/12/09 04:33:17]

Done.

+      (*I)->dropAllReferences();
+    }
+    for (SmallVectorImpl<Instruction *>::iterator I = ToErase.begin(),
+                                                  E = ToErase.end();
+         I != E; ++I) {

[JF, 2014/12/06 23:52:13]

Range-based.

[Richard Diamond, 2014/12/09 04:33:12]

Done.

+      (*I)->eraseFromParent();
+    }
+  }
+
+  return (NeedsAnotherPass && ExpandExtractValues(Func)) || Changed;
+}
+
 bool ExpandStructRegs::runOnFunction(Function &Func) {
   bool Changed = false;
+  bool NeedsAnotherPass = false;
 
   // Split up aggregate loads, stores and phi nodes into operations on
   // scalar types.  This inserts extractvalue and insertvalue
@@ -234,61 +319,33 @@ bool ExpandStructRegs::runOnFunction(Function &Func) {
       Instruction *Inst = Iter++;
       if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
         if (Store->getValueOperand()->getType()->isStructTy()) {
-          SplitUpStore(Store);
+          SplitUpStore(Store, NeedsAnotherPass);
           Changed = true;
         }
       } else if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
         if (Load->getType()->isStructTy()) {
-          SplitUpLoad(Load);
+          SplitUpLoad(Load, NeedsAnotherPass);
           Changed = true;
         }
       } else if (PHINode *Phi = dyn_cast<PHINode>(Inst)) {
         if (Phi->getType()->isStructTy()) {
-          SplitUpPHINode(Phi);
+          SplitUpPHINode(Phi, NeedsAnotherPass);
           Changed = true;
         }
       } else if (SelectInst *Select = dyn_cast<SelectInst>(Inst)) {
         if (Select->getType()->isStructTy()) {
-          SplitUpSelect(Select);
+          SplitUpSelect(Select, NeedsAnotherPass);
           Changed = true;
         }
       }
     }
   }
 
-  // Expand out all the extractvalue instructions.  Also collect up
-  // the insertvalue instructions for later deletion so that we do not
-  // need to make extra passes across the whole function.
-  SmallVector<Instruction *, 10> ToErase;
-  for (Function::iterator BB = Func.begin(), E = Func.end();
-       BB != E; ++BB) {
-    for (BasicBlock::iterator Iter = BB->begin(), E = BB->end();
-         Iter != E; ) {
-      Instruction *Inst = Iter++;
-      if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Inst)) {
-        ExpandExtractValue(EV);
-        Changed = true;
-      } else if (isa<InsertValueInst>(Inst)) {
-        ToErase.push_back(Inst);
-        Changed = true;
-      }
-    }
+  if (!NeedsAnotherPass) {
+    Changed = ExpandExtractValues(Func) || Changed;
   }
-  // Delete the insertvalue instructions.  These can reference each
-  // other, so we must do dropAllReferences() before doing
-  // eraseFromParent(), otherwise we will try to erase instructions
-  // that are still referenced.
-  for (SmallVectorImpl<Instruction *>::iterator I = ToErase.begin(),
-           E = ToErase.end();
-       I != E; ++I) {
-    (*I)->dropAllReferences();
-  }
-  for (SmallVectorImpl<Instruction *>::iterator I = ToErase.begin(),
-           E = ToErase.end();
-       I != E; ++I) {
-    (*I)->eraseFromParent();
-  }
-  return Changed;
+
+  return (NeedsAnotherPass && runOnFunction(Func)) || Changed;
 }
 
 FunctionPass *llvm::createExpandStructRegsPass() {