Fix processing of local variable indices in fuction blocks.

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 1248 matching lines @@
 
   // Set the next constant ID to the given constant C.
   void setNextConstantID(Ice::Constant *C) { setNextLocalInstIndex(C); }
 
   // Returns the value referenced by the given value Index.
   Ice::Operand *getOperand(NaClBcIndexSize_t Index) {
     if (Index < CachedNumGlobalValueIDs) {
       return Context->getGlobalConstantByID(Index);
     }
     NaClBcIndexSize_t LocalIndex = Index - CachedNumGlobalValueIDs;
-    if (LocalIndex >= LocalOperands.size()) {
-      std::string Buffer;
-      raw_string_ostream StrBuf(Buffer);
-      StrBuf << "Value index " << Index << " not defined!";
-      Fatal(StrBuf.str());
-    }
     Ice::Operand *Op = LocalOperands[LocalIndex];
     if (Op == nullptr) {
       if (isIRGenerationDisabled())
         return nullptr;
       std::string Buffer;
       raw_string_ostream StrBuf(Buffer);
       StrBuf << "Value index " << Index << " not defined!";
       Fatal(StrBuf.str());
     }
     return Op;
   }
 
   // Returns the Index-th basic block in the list of basic blocks.
   Ice::CfgNode *getBasicBlock(NaClBcIndexSize_t Index) {
     assert(!isIRGenerationDisabled());
     Ice::CfgNode *&Node = BbMap[Index];
     if (Node == nullptr)
       Node = Func->makeNode();
     return Node;
   }
 
 private:
+  typedef std::unordered_map<NaClBcIndexSize_t, Ice::Operand *> OperandsMap;

[Jim Stichnoth, 2015/08/08 16:14:48]

For naming consistency, I would use "OperandMap" or "CfgNodesMap".  (I prefer
OperandMap/CfgNodeMap, fwiw.)

[Karl, 2015/08/10 18:13:09]

Done.

   typedef std::unordered_map<NaClBcIndexSize_t, Ice::CfgNode *> CfgNodeMap;
 
   Ice::TimerMarker Timer;
   // The corresponding ICE function defined by the function block.
   std::unique_ptr<Ice::Cfg> Func;
   // The specified number of basic blocks in the bitcode file.
   NaClBcIndexSize_t SpecifiedNumBbs = 0;
   // The index to the current basic block being built.
   NaClBcIndexSize_t CurrentBbIndex = 0;
   // The basic block being built.
   Ice::CfgNode *CurrentNode = nullptr;
   // Map from basic block id (as defined in the bitcode file) to
   // the corresponding basic block that implements it.
   CfgNodeMap BbMap;
   // 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.
-  std::vector<Ice::Operand *> LocalOperands;
+  OperandsMap LocalOperands;
   // 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 15 matching lines @@
   }
 
   bool ParseBlock(unsigned BlockID) override;
 
   void ProcessRecord() override;
 
   void ExitBlock() override;
 
   bool verifyAndRenameBasicBlocks();
 
+  bool verifyAllForwardRefsDefined();
+
   // Returns the Index-th basic block in the list of basic blocks.
   // Assumes Index corresponds to a branch instruction. Hence, if
   // the branch references the entry block, it also generates a
   // corresponding error.
   Ice::CfgNode *getBranchBasicBlock(NaClBcIndexSize_t Index) {
     assert(!isIRGenerationDisabled());
     if (Index == 0) {
       Error("Branch to entry block not allowed");
       // TODO(kschimpf) Remove error recovery once implementation complete.
     }
@@ skipping 55 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 (LocalIndex == LocalOperands.size()) {
-      LocalOperands.push_back(Op);
+
+    // If element not defined, set it.
+    Ice::Operand *&IndexedOp = LocalOperands[LocalIndex];
+    if (IndexedOp == nullptr) {
+      IndexedOp = Op;
       return;
     }
 
-    // Must be forward reference, expand vector to accommodate.
-    if (LocalIndex >= LocalOperands.size())
-      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)
+    // See if forward reference matchers.
+    if (IndexedOp == Op)
       return;
 
     // Error has occurred.
     std::string Buffer;
     raw_string_ostream StrBuf(Buffer);
     StrBuf << "Multiple definitions for index " << Index << ": " << *Op
-           << " and " << *OldOp;
+           << " and " << *IndexedOp;
     Error(StrBuf.str());
     // TODO(kschimpf) Remove error recovery once implementation complete.

[Jim Stichnoth, 2015/08/08 16:14:48]

Trying to remember the context of these TODOs...  Isn't implementation complete
by now?

[Karl, 2015/08/10 18:13:09]

This was back when someone wasn't sure we should keep error recovery, once we
get things working (i.e. consider it only for debugging). I think that keeping
error recovery around is good, and will fix in a separate CL>

-    LocalOperands[LocalIndex] = Op;
+    IndexedOp = 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 483 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 std::pair<NaClBcIndexSize_t, Ice::Operand *> Elmt : LocalOperands)

[Jim Stichnoth, 2015/08/08 16:14:48]

I think this calls for auto:

  for (auto &Elmt : LocalOperands)

Or if not:

  for (const OperandsMap::value_type &Elmt : LocalOperands)

[Karl, 2015/08/10 18:13:09]

Good point. I didn't put the auto in because I didn't think the type was clear
enough. However, Using the second form is clear and simpler.

+    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;
+}
+
 bool FunctionParser::verifyAndRenameBasicBlocks() {
   const size_t NumFoundBbs = BbMap.size();
   // Verify number of basic blocks found match amount specified in function.
   if (NumFoundBbs != SpecifiedNumBbs) {
     std::string Buffer;
     raw_string_ostream StrBuf(Buffer);
     StrBuf << "Function specified " << SpecifiedNumBbs
            << "basic blocks. Found: " << NumFoundBbs;
     Error(StrBuf.str());
     return false;
@@ skipping 29 matching lines @@
   // 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()));
   }
   if (isIRGenerationDisabled())
     return;
+  if (!verifyAllForwardRefsDefined())
+    return;
   if (!verifyAndRenameBasicBlocks())
     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";
@@ skipping 1120 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