Elide pointer to int casts on phi nodes.

Handles the eliding of pointer to integer casts operands of the phi node.

Also caches unelided casts generated in the reader (removing
duplicates within the same block). This reduces the size of
thawed pnacl-llc.pexe by about 2%.

BUG=  https://code.google.com/p/nativeclient/issues/detailid=3544
R=mseaborn@chromium.org

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

2 files changed, 157 insertions, 53 deletions

diff --git a/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.cpp b/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.cpp
index a38b18afa1..fbe1fc0165 100644
--- a/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.cpp
+++ b/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.cpp
@@ -36,7 +36,6 @@ void NaClBitcodeReader::FreeState() {
   std::vector<Type*>().swap(TypeList);
   ValueList.clear();
 
-  std::vector<BasicBlock*>().swap(FunctionBBs);
   std::vector<Function*>().swap(FunctionsWithBodies);
   DeferredFunctionInfo.clear();
 }
@@ -1284,40 +1283,56 @@ bool NaClBitcodeReader::InstallInstruction(
   return false;
 }
 
-Value *NaClBitcodeReader::ConvertOpToScalar(Value *Op, BasicBlock *BB) {
+CastInst *
+NaClBitcodeReader::CreateCast(unsigned BBIndex, Instruction::CastOps Op,
+                              Type *CT, Value *V, bool DeferInsertion) {
+  if (BBIndex >= FunctionBBs.size())
+    report_fatal_error("CreateCast on unknown basic block");
+  BasicBlockInfo &BBInfo = FunctionBBs[BBIndex];
+  NaClBitcodeReaderCast ModeledCast(Op, CT, V);
+  CastInst *Cast = BBInfo.CastMap[ModeledCast];
+  if (Cast == NULL) {
+    Cast = CastInst::Create(Op, V, CT);
+    BBInfo.CastMap[ModeledCast] = Cast;
+    if (DeferInsertion) {
+      BBInfo.PhiCasts.push_back(Cast);
+    }
+  }
+  if (!DeferInsertion && Cast->getParent() == 0) {
+    InstallInstruction(BBInfo.BB, Cast);
+  }
+  return Cast;
+}
+
+Value *NaClBitcodeReader::ConvertOpToScalar(Value *Op, unsigned BBIndex,
+                                            bool DeferInsertion) {
   if (Op->getType()->isPointerTy()) {
-    Instruction *Conversion = new PtrToIntInst(Op, IntPtrType);
-    InstallInstruction(BB, Conversion);
-    return Conversion;
+    return CreateCast(BBIndex, Instruction::PtrToInt, IntPtrType, Op,
+                      DeferInsertion);
   }
   return Op;
 }
 
-Value *NaClBitcodeReader::ConvertOpToType(Value *Op, Type *T, BasicBlock *BB) {
+Value *NaClBitcodeReader::ConvertOpToType(Value *Op, Type *T,
+                                          unsigned BBIndex) {
   // Note: Currently only knows how to add inttoptr and bitcast type
   // conversions for non-phi nodes, since these are the only elided
   // instructions in the bitcode writer.
   //
   // TODO(kschimpf): Generalize this as we expand elided conversions.
-  Instruction *Conversion = 0;
   Type *OpTy = Op->getType();
   if (OpTy == T) return Op;
 
   if (OpTy->isPointerTy()) {
-    Conversion = new BitCastInst(Op, T);
+    return CreateCast(BBIndex, Instruction::BitCast, T, Op);
   } else if (OpTy == IntPtrType) {
-    Conversion = new IntToPtrInst(Op, T);
+    return CreateCast(BBIndex, Instruction::IntToPtr, T, Op);
   }
 
-  if (Conversion == 0) {
-    std::string Message;
-    raw_string_ostream StrM(Message);
-    StrM << "Can't convert " << *Op << " to type " << *T << "\n";
-    Error(StrM.str());
-  } else {
-    InstallInstruction(BB, Conversion);
-  }
-  return Conversion;
+  std::string Message;
+  raw_string_ostream StrM(Message);
+  StrM << "Can't convert " << *Op << " to type " << *T << "\n";
+  report_fatal_error(StrM.str());
 }
 
 Type *NaClBitcodeReader::ConvertTypeToScalarType(Type *T) {
@@ -1396,9 +1411,11 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
         return Error("Invalid DECLAREBLOCKS record");
       // Create all the basic blocks for the function.
       FunctionBBs.resize(Record[0]);
-      for (unsigned i = 0, e = FunctionBBs.size(); i != e; ++i)
-        FunctionBBs[i] = BasicBlock::Create(Context, "", F);
-      CurBB = FunctionBBs[0];
+      for (unsigned i = 0, e = FunctionBBs.size(); i != e; ++i) {
+        BasicBlockInfo &BBInfo = FunctionBBs[i];
+        BBInfo.BB = BasicBlock::Create(Context, "", F);
+      }
+      CurBB = FunctionBBs.at(0).BB;
       continue;
 
     case naclbitc::FUNC_CODE_INST_BINOP: {
@@ -1410,8 +1427,8 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
           OpNum+1 > Record.size())
         return Error("Invalid BINOP record");
 
-      LHS = ConvertOpToScalar(LHS, CurBB);
-      RHS = ConvertOpToScalar(RHS, CurBB);
+      LHS = ConvertOpToScalar(LHS, CurBBNo);
+      RHS = ConvertOpToScalar(RHS, CurBBNo);
 
       int Opc = GetDecodedBinaryOpcode(Record[OpNum++], LHS->getType());
       if (Opc == -1) return Error("Invalid BINOP record");
@@ -1472,7 +1489,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
         case Instruction::SExt:
         case Instruction::UIToFP:
         case Instruction::SIToFP:
-          Op = ConvertOpToScalar(Op, CurBB);
+          Op = ConvertOpToScalar(Op, CurBBNo);
           break;
         default:
           break;
@@ -1493,8 +1510,8 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
           popValue(Record, &OpNum, NextValueNo, &Cond))
         return Error("Invalid SELECT record");
 
-      TrueVal = ConvertOpToScalar(TrueVal, CurBB);
-      FalseVal = ConvertOpToScalar(FalseVal, CurBB);
+      TrueVal = ConvertOpToScalar(TrueVal, CurBBNo);
+      FalseVal = ConvertOpToScalar(FalseVal, CurBBNo);
 
       // expect i1
       if (Cond->getType() != Type::getInt1Ty(Context))
@@ -1514,8 +1531,8 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
           OpNum+1 != Record.size())
         return Error("Invalid CMP record");
 
-      LHS = ConvertOpToScalar(LHS, CurBB);
-      RHS = ConvertOpToScalar(RHS, CurBB);
+      LHS = ConvertOpToScalar(LHS, CurBBNo);
+      RHS = ConvertOpToScalar(RHS, CurBBNo);
 
       if (LHS->getType()->isFPOrFPVectorTy())
         I = new FCmpInst((FCmpInst::Predicate)Record[OpNum], LHS, RHS);
@@ -1622,9 +1639,6 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       Type *Ty = getTypeByID(Record[0]);
       if (!Ty) return Error("Invalid PHI record");
 
-      // TODO(kschimpf): Fix handling of converting types for values,
-      // to handle elided casts, once the bitcode writer knows how.
-
       PHINode *PN = PHINode::Create(Ty, (Record.size()-1)/2);
 
       for (unsigned i = 0, e = Record.size()-1; i != e; i += 2) {
@@ -1636,8 +1650,16 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
           V = getValueSigned(Record, 1+i, NextValueNo);
         else
           V = getValue(Record, 1+i, NextValueNo);
-        BasicBlock *BB = getBasicBlock(Record[2+i]);
+        unsigned BBIndex = Record[2+i];
+        BasicBlock *BB = getBasicBlock(BBIndex);
         if (!V || !BB) return Error("Invalid PHI record");
+        if (GetPNaClVersion() == 2 && Ty == IntPtrType) {
+          // Delay installing scalar casts until all instructions of
+          // the function are rendered. This guarantees that we insert
+          // the conversion just before the incoming edge (or use an
+          // existing conversion if already installed).
+          V = ConvertOpToScalar(V, BBIndex, /* DeferInsertion = */ true);
+        }
         PN->addIncoming(V, BB);
       }
       I = PN;
@@ -1672,7 +1694,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
           Type *T = getTypeByID(Record[2]);
           if (T == 0)
             return Error("Invalid type for load instruction");
-          Op = ConvertOpToType(Op, T->getPointerTo(), CurBB);
+          Op = ConvertOpToType(Op, T->getPointerTo(), CurBBNo);
           if (Op == 0) return true;
 	  I = new LoadInst(Op, "", false, (1 << Record[OpNum]) >> 1);
 	  break;
@@ -1697,8 +1719,8 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       case 2:
 	if (OpNum+1 != Record.size())
 	  return Error("Invalid STORE record");
-	Val = ConvertOpToScalar(Val, CurBB);
-	Ptr = ConvertOpToType(Ptr, Val->getType()->getPointerTo(), CurBB);
+        Val = ConvertOpToScalar(Val, CurBBNo);
+        Ptr = ConvertOpToType(Ptr, Val->getType()->getPointerTo(), CurBBNo);
 	I = new StoreInst(Val, Ptr, false, (1 << Record[OpNum]) >> 1);
 	break;
       }
@@ -1767,7 +1789,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
     // If this was a terminator instruction, move to the next block.
     if (isa<TerminatorInst>(I)) {
       ++CurBBNo;
-      CurBB = CurBBNo < FunctionBBs.size() ? FunctionBBs[CurBBNo] : 0;
+      CurBB = getBasicBlock(CurBBNo);
     }
 
     // Non-void values get registered in the value table for future use.
@@ -1777,6 +1799,24 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
 
 OutOfRecordLoop:
 
+  // Add PHI conversions to corresponding incoming block, if not
+  // already in the block. Also clear all conversions after fixing
+  // PHI conversions.
+  for (unsigned I = 0, NumBBs = FunctionBBs.size(); I < NumBBs; ++I) {
+    BasicBlockInfo &BBInfo = FunctionBBs[I];
+    std::vector<CastInst*> &PhiCasts = BBInfo.PhiCasts;
+    for (std::vector<CastInst*>::iterator Iter = PhiCasts.begin(),
+           IterEnd = PhiCasts.end(); Iter != IterEnd; ++Iter) {
+      CastInst *Cast = *Iter;
+      if (Cast->getParent() == 0) {
+        BasicBlock *BB = BBInfo.BB;
+        BB->getInstList().insert(BB->getTerminator(), Cast);
+      }
+    }
+    PhiCasts.clear();
+    BBInfo.CastMap.clear();
+  }
+
   // Check the function list for unresolved values.
   if (Argument *A = dyn_cast<Argument>(ValueList.back())) {
     if (A->getParent() == 0) {
@@ -1793,7 +1833,7 @@ OutOfRecordLoop:
 
   // Trim the value list down to the size it was before we parsed this function.
   ValueList.shrinkTo(ModuleValueListSize);
-  std::vector<BasicBlock*>().swap(FunctionBBs);
+  FunctionBBs.clear();
   DEBUG(dbgs() << "-> ParseFunctionBody\n");
   return false;
 }
diff --git a/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.h b/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.h
index 814ef44efb..762088887f 100644
--- a/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.h
+++ b/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.h
@@ -21,6 +21,7 @@
 #include "llvm/Bitcode/NaCl/NaClLLVMBitCodes.h"
 #include "llvm/GVMaterializer.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Instruction.h"
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/ValueHandle.h"
@@ -29,6 +30,46 @@
 namespace llvm {
   class MemoryBuffer;
   class LLVMContext;
+  class CastInst;
+
+// Models a Cast.  Used to cache casts created in a basic block by the
+// PNaCl bitcode reader.
+struct NaClBitcodeReaderCast {
+  // Fields of the conversion.
+  Instruction::CastOps Op;
+  Type *Ty;
+  Value *Val;
+
+  NaClBitcodeReaderCast(Instruction::CastOps Op, Type *Ty, Value *Val)
+    : Op(Op), Ty(Ty), Val(Val) {}
+};
+
+// Models the data structure used to hash/compare Casts in a DenseMap.
+template<>
+struct DenseMapInfo<NaClBitcodeReaderCast> {
+public:
+  static NaClBitcodeReaderCast getEmptyKey() {
+    return NaClBitcodeReaderCast(Instruction::CastOpsEnd,
+                                 DenseMapInfo<Type*>::getEmptyKey(),
+                                 DenseMapInfo<Value*>::getEmptyKey());
+  }
+  static NaClBitcodeReaderCast getTombstoneKey() {
+    return NaClBitcodeReaderCast(Instruction::CastOpsEnd,
+                                 DenseMapInfo<Type*>::getTombstoneKey(),
+                                 DenseMapInfo<Value*>::getTombstoneKey());
+  }
+  static unsigned getHashValue(const NaClBitcodeReaderCast &C) {
+    std::pair<int, std::pair<Type*, Value*> > Tuple;
+    Tuple.first = C.Op;
+    Tuple.second.first = C.Ty;
+    Tuple.second.second = C.Val;
+    return DenseMapInfo<std::pair<int, std::pair<Type*, Value*> > >::getHashValue(Tuple);
+  }
+  static bool isEqual(const NaClBitcodeReaderCast &LHS,
+                      const NaClBitcodeReaderCast &RHS) {
+    return LHS.Op == RHS.Op && LHS.Ty == RHS.Ty && LHS.Val == RHS.Val;
+  }
+};
 
 //===----------------------------------------------------------------------===//
 //                          NaClBitcodeReaderValueList Class
@@ -83,8 +124,8 @@ public:
   // already been declared.
   bool createValueFwdRef(unsigned Idx, Type *Ty);
 
-  // Declares the type of the forward-referenced constant Idx. Returns
-  // 0 if an error occurred.
+  // Declares the type of the forward-referenced constant Idx.
+  // Returns 0 if an error occurred.
   // TODO(kschimpf) Convert these to be like createValueFwdRef and
   // getValueFwdRef.
   Constant *getConstantFwdRef(unsigned Idx, Type *Ty);
@@ -103,7 +144,7 @@ public:
   // was forward referenced).
   void AssignValue(Value *V, unsigned Idx);
 
-  // Assigns Idx to the given global variable. If the Idx currently has
+  // Assigns Idx to the given global variable.  If the Idx currently has
   // a forward reference (built by createGlobalVarFwdRef(unsigned Idx)),
   // replaces uses of the global variable forward reference with the
   // value GV.
@@ -133,9 +174,20 @@ class NaClBitcodeReader : public GVMaterializer {
   NaClBitcodeReaderValueList ValueList;
   SmallVector<SmallVector<uint64_t, 64>, 64> UseListRecords;
 
+  // Holds information about each BasicBlock in the function being read.
+  struct BasicBlockInfo {
+    // A basic block within the function being modeled.
+    BasicBlock *BB;
+    // The set of generated conversions.
+    DenseMap<NaClBitcodeReaderCast, CastInst*> CastMap;
+    // The set of generated conversions that were added for phi nodes,
+    // and may need thier parent basic block defined.
+    std::vector<CastInst*> PhiCasts;
+  };
+
   /// FunctionBBs - While parsing a function body, this is a list of the basic
   /// blocks for the function.
-  std::vector<BasicBlock*> FunctionBBs;
+  std::vector<BasicBlockInfo> FunctionBBs;
 
   // When reading the module header, this list is populated with functions that
   // have bodies later in the file.
@@ -147,7 +199,7 @@ class NaClBitcodeReader : public GVMaterializer {
   UpgradedIntrinsicMap UpgradedIntrinsics;
 
   // Several operations happen after the module header has been read, but
-  // before function bodies are processed. This keeps track of whether
+  // before function bodies are processed.  This keeps track of whether
   // we've done this yet.
   bool SeenFirstFunctionBody;
 
@@ -226,14 +278,14 @@ private:
     return Header.GetPNaClVersion();
   }
   Type *getTypeByID(unsigned ID);
-  // Returns the value associated with ID. The value must already exist,
+  // Returns the value associated with ID.  The value must already exist,
   // or a forward referenced value created by getOrCreateFnVaueByID.
   Value *getFnValueByID(unsigned ID) {
     return ValueList.getValueFwdRef(ID);
   }
   BasicBlock *getBasicBlock(unsigned ID) const {
     if (ID >= FunctionBBs.size()) return 0; // Invalid ID
-    return FunctionBBs[ID];
+    return FunctionBBs[ID].BB;
   }
 
   /// \brief Read a value out of the specified record from slot '*Slot'.
@@ -273,18 +325,30 @@ private:
     return getFnValueByID(ValNo);
   }
 
-  /// \brief Add instructions to cast Op to the given type T into block BB.
-  /// Follows rules for pointer conversion as defined in
-  /// llvm/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp.
+  /// \brief Create an (elided) cast instruction for basic block
+  /// BBIndex.  Op is the type of cast.  V is the value to cast.  CT
+  /// is the type to convert V to.  DeferInsertion defines whether the
+  /// generated conversion should also be installed into basic block
+  /// BBIndex.  Note: For PHI nodes, we don't insert when created
+  /// (i.e. DeferInsertion=true), since they must be inserted at the end
+  /// of the corresponding incoming basic block.
+  CastInst *CreateCast(unsigned BBIndex, Instruction::CastOps Op,
+                       Type *CT, Value *V, bool DeferInsertion = false);
+
+  /// \brief Add instructions to cast Op to the given type T into
+  /// block BBIndex.  Follows rules for pointer conversion as defined
+  /// in llvm/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp.
   ///
   /// Returns 0 if unable to generate conversion value (also generates
   /// an appropriate error message and calls Error).
-  Value *ConvertOpToType(Value *Op, Type *T, BasicBlock *BB);
-
-  /// \brief If Op is a scalar value, this is a nop. If Op is a
-  /// pointer value, a PtrToInt instruction is inserted (in BB) to
-  /// convert Op to an integer.
-  Value *ConvertOpToScalar(Value *Op, BasicBlock *BB);
+  Value *ConvertOpToType(Value *Op, Type *T, unsigned BBIndex);
+
+  /// \brief If Op is a scalar value, this is a nop.  If Op is a
+  /// pointer value, a PtrToInt instruction is inserted (in BBIndex)
+  /// to convert Op to an integer.  For defaults on DeferInsertion,
+  /// see comments for method CreateCast.
+  Value *ConvertOpToScalar(Value *Op, unsigned BBIndex,
+                           bool DeferInsertion = false);
 
   /// \brief Returns the corresponding, PNaCl non-pointer equivalent
   /// for the given type.