Restore function-local variables to use a vector.

src/PNaClTranslator.cpp

 //===- subzero/src/PNaClTranslator.cpp - ICE from bitcode -----------------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 1296 matching lines @@
         return nullptr;
       std::string Buffer;
       raw_string_ostream StrBuf(Buffer);
       StrBuf << "Value index " << Index << " not defined!";
       Fatal(StrBuf.str());
     }
     return Op;
   }
 
 private:
-  typedef std::unordered_map<NaClBcIndexSize_t, Ice::Operand *> OperandMap;
-
   Ice::TimerMarker Timer;
   // The number of words in the bitstream defining the function block.
   uint64_t NumBytesDefiningFunction = 0;
+  // Maximum number of records that can appear in the function block, based on
+  // the number of bytes defining the function block.
+  uint64_t MaxRecordsInBlock = 0;
   // The corresponding ICE function defined by the function block.
   std::unique_ptr<Ice::Cfg> Func;
   // The index to the current basic block being built.
   NaClBcIndexSize_t CurrentBbIndex = 0;
   // The number of basic blocks declared for the function block.
   NaClBcIndexSize_t DeclaredNumberBbs = 0;
   // The basic block being built.
   Ice::CfgNode *CurrentNode = nullptr;
   // The ID for the function.
   NaClBcIndexSize_t FcnId;
   // The corresponding function declaration.
   Ice::FunctionDeclaration *FuncDecl;
   // Holds the dividing point between local and global absolute value indices.
   size_t CachedNumGlobalValueIDs;
   // Holds operands local to the function block, based on indices
   // defined in the bitcode file.
-  OperandMap LocalOperands;
+  std::vector<Ice::Operand *> LocalOperands;

[Jim Stichnoth, 2015/08/17 19:41:03]

It occurs to me that using STL containers with the default allocator may be
partially responsible for Subzero's scalability problems (along with similar
uses outside the parser code).

If containers are local to a Cfg, then a simple change is e.g. from:
  std::vector<Foo>
to:
  std::vector<Foo, CfgLocalAllocator<Foo>>
The same holds for list<>, unordered_map<>, etc.

It would be good to try these changes in a separate CL.  I would look at
-threads=0 and -threads=1 performance, before and after the change.

The same would be done later to the non-parser code as well.

[Karl, 2015/08/17 19:47:34]

Acknowledged.

   // Holds the index within LocalOperands corresponding to the next
   // instruction that generates a value.
   NaClBcIndexSize_t NextLocalInstIndex;
   // True if the last processed instruction was a terminating
   // instruction.
   bool InstIsTerminating = false;
   // Upper limit of alignment power allowed by LLVM
   static const uint32_t AlignPowerLimit = 29;
 
   // Extracts the corresponding Alignment to use, given the AlignPower
@@ skipping 14 matching lines @@
     Alignment = 1;
   }
 
   bool ParseBlock(unsigned BlockID) override;
 
   void ProcessRecord() override;
 
   void EnterBlock(unsigned NumWords) final {
     // Note: Bitstream defines words as 32-bit values.
     NumBytesDefiningFunction = NumWords * sizeof(uint32_t);
+    // We know that all records are minimally defined by a two-bit abreviation.
+    MaxRecordsInBlock = NumBytesDefiningFunction * (CHAR_BIT >> 1);
   }
 
   void ExitBlock() override;
 
-  bool verifyAllForwardRefsDefined();
-
   // Creates and appends a new basic block to the list of basic blocks.
   Ice::CfgNode *installNextBasicBlock() {
     assert(!isIRGenerationDisabled());
     Ice::CfgNode *Node = Func->makeNode();
     return Node;
   }
 
   // Returns the Index-th basic block in the list of basic blocks.
   Ice::CfgNode *getBasicBlock(NaClBcIndexSize_t Index) {
     assert(!isIRGenerationDisabled());
@@ skipping 73 matching lines @@
       return 0;
     }
     return BaseIndex - Id;
   }
 
   // Sets element Index (in the local operands list) to Op.
   void setOperand(NaClBcIndexSize_t Index, Ice::Operand *Op) {
     assert(Op || isIRGenerationDisabled());
     // Check if simple push works.
     NaClBcIndexSize_t LocalIndex = Index - CachedNumGlobalValueIDs;
-
-    // If element not defined, set it.
-    Ice::Operand *&IndexedOp = LocalOperands[LocalIndex];
-    if (IndexedOp == nullptr) {
-      IndexedOp = Op;
+    if (LocalIndex == LocalOperands.size()) {
+      LocalOperands.push_back(Op);
       return;
     }
 
-    // See if forward reference matchers.
-    if (IndexedOp == Op)
+    // Must be forward reference, expand vector to accommodate.
+    if (LocalIndex >= LocalOperands.size()) {
+      if (LocalIndex > MaxRecordsInBlock) {
+        std::string Buffer;
+        raw_string_ostream StrBuf(Buffer);
+        StrBuf << "Forward reference @" << Index << " too big. Have "
+               << CachedNumGlobalValueIDs << " globals and function contains "
+               << NumBytesDefiningFunction << " bytes";
+        Fatal(StrBuf.str());
+        // Recover by using index one beyond the maximal allowed.
+        LocalIndex = MaxRecordsInBlock;
+      }
+      LocalOperands.resize(LocalIndex + 1);
+    }
+
+    // If element not defined, set it.
+    Ice::Operand *OldOp = LocalOperands[LocalIndex];
+    if (OldOp == nullptr) {
+      LocalOperands[LocalIndex] = Op;
+      return;
+    }
+
+    // See if forward reference matches.
+    if (OldOp == Op)
       return;
 
     // Error has occurred.
     std::string Buffer;
     raw_string_ostream StrBuf(Buffer);
     StrBuf << "Multiple definitions for index " << Index << ": " << *Op
-           << " and " << *IndexedOp;
+           << " and " << *OldOp;
     Error(StrBuf.str());
-    IndexedOp = Op;
+    LocalOperands[LocalIndex] = Op;
   }
 
   // Returns the relative operand (wrt to BaseIndex) referenced by
   // the given value Index.
   Ice::Operand *getRelativeOperand(NaClBcIndexSize_t Index,
                                    NaClBcIndexSize_t BaseIndex) {
     return getOperand(convertRelativeToAbsIndex(Index, BaseIndex));
   }
 
   // Returns the absolute index of the next value generating instruction.
@@ skipping 480 matching lines @@
   void appendErrorInstruction(Ice::Type Ty) {
     // Note: we don't worry about downstream translation errors because
     // the function will not be translated if any errors occur.
     if (Ty == Ice::IceType_void)
       return;
     Ice::Variable *Var = getNextInstVar(Ty);
     CurrentNode->appendInst(Ice::InstAssign::create(Func.get(), Var, Var));
   }
 };
 
-bool FunctionParser::verifyAllForwardRefsDefined() {
-  NaClBcIndexSize_t NumInstructions =
-      NextLocalInstIndex - CachedNumGlobalValueIDs;
-  if (NumInstructions == LocalOperands.size())
-    return true;
-  // Find undefined forward references and report.
-  std::vector<NaClBcIndexSize_t> UndefinedFwdRefs;
-  for (const OperandMap::value_type &Elmt : LocalOperands)
-    if (Elmt.first >= NextLocalInstIndex)
-      UndefinedFwdRefs.push_back(Elmt.first);
-  std::sort(UndefinedFwdRefs.begin(), UndefinedFwdRefs.end());
-  for (const NaClBcIndexSize_t Index : UndefinedFwdRefs) {
-    std::string Buffer;
-    raw_string_ostream StrBuf(Buffer);
-    StrBuf << "Instruction forward reference not defined: " << Index;
-    Error(StrBuf.str());
-  }
-  return false;
-}
-
 void FunctionParser::ExitBlock() {
   // Check if the last instruction in the function was terminating.
   if (!InstIsTerminating) {
     Error("Last instruction in function not terminator");
     if (isIRGenerationDisabled())
       return;
     // Recover by inserting an unreachable instruction.
     CurrentNode->appendInst(Ice::InstUnreachable::create(Func.get()));
   }
   ++CurrentBbIndex;
   if (CurrentBbIndex != DeclaredNumberBbs) {
     std::string Buffer;
     raw_string_ostream StrBuf(Buffer);
     StrBuf << "Function declared " << DeclaredNumberBbs
            << " basic blocks, but defined " << CurrentBbIndex << ".";
     Error(StrBuf.str());
   }
   if (isIRGenerationDisabled())
     return;
-  if (!verifyAllForwardRefsDefined())
-    return;
   // Before translating, check for blocks without instructions, and
   // insert unreachable. This shouldn't happen, but be safe.
   size_t Index = 0;
   for (Ice::CfgNode *Node : Func->getNodes()) {
     if (Node->getInsts().empty()) {
       std::string Buffer;
       raw_string_ostream StrBuf(Buffer);
       StrBuf << "Basic block " << Index << " contains no instructions";
       Error(StrBuf.str());
       Node->appendInst(Ice::InstUnreachable::create(Func.get()));
@@ skipping 29 matching lines @@
   switch (Record.GetCode()) {
   case naclbitc::FUNC_CODE_DECLAREBLOCKS: {
     // DECLAREBLOCKS: [n]
     if (!isValidRecordSize(1, "count"))
       return;
     if (DeclaredNumberBbs > 0) {
       Error("Duplicate function block count record");
       return;
     }
 
+    // Check for bad large sizes, since they can make ridiculous memory
+    // requests and hang the user for large amounts of time.
     uint64_t NumBbs = Values[0];
-
-    // Check for bad large sizes, since they can make ridiculous memory
-    // requests and hang the user for large amounts of time.  Note: We know
-    // that each basic block must have a terminator instruction, and each
-    // instruction is minimally defined by a two-bit abreviation.
-    uint64_t MaxBbs = NumBytesDefiningFunction * (CHAR_BIT >> 1);
-    if (NumBbs > MaxBbs) {
+    if (NumBbs > MaxRecordsInBlock) {
       std::string Buffer;
       raw_string_ostream StrBuf(Buffer);
       StrBuf << "Function defines " << NumBbs
              << " basic blocks, which is too big for a function containing "
              << NumBytesDefiningFunction << " bytes";
       Error(StrBuf.str());
-      NumBbs = MaxBbs;
+      NumBbs = MaxRecordsInBlock;
     }
 
     if (NumBbs == 0) {
       Error("Functions must contain at least one basic block.");
       NumBbs = 1;
     }
 
     DeclaredNumberBbs = NumBbs;
     if (isIRGenerationDisabled())
       return;
@@ skipping 1069 matching lines @@
   }
   if (InputStreamFile.getBitcodeBytes().getExtent() % 4 != 0) {
     ErrStream
         << IRFilename
         << ": Bitcode stream should be a multiple of 4 bytes in length.\n";
     llvm::report_fatal_error("Bitcode stream should be a multiple of 4 bytes");
   }
 }
 
 } // end of namespace Ice