Fix translator handling of basic block indices.

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 18 matching lines @@
 #pragma clang diagnostic ignored "-Wunused-parameter"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Bitcode/NaCl/NaClBitcodeDecoders.h"
 #include "llvm/Bitcode/NaCl/NaClBitcodeDefs.h"
 #include "llvm/Bitcode/NaCl/NaClBitcodeHeader.h"
 #include "llvm/Bitcode/NaCl/NaClBitcodeParser.h"
 #include "llvm/Bitcode/NaCl/NaClReaderWriter.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
+#include <unordered_map>

[Jim Stichnoth, 2015/08/06 19:41:21]

Could you move this include into IceDefs.h, and remove it from the other two
places that #include it?

[Karl, 2015/08/06 19:55:41]

Done.

 #pragma clang diagnostic pop
 
 namespace {
 using namespace llvm;
 
 // Models elements in the list of types defined in the types block.
 // These elements can be undefined, a (simple) type, or a function type
 // signature. Note that an extended type is undefined on construction.
 // Use methods setAsSimpleType and setAsFuncSigType to define
 // the extended type.
@@ skipping 1159 matching lines @@
     if (isIRGenerationDisabled()) {
       CurrentNode = nullptr;
       for (Ice::Type ArgType : Signature.getArgList()) {
         (void)ArgType;
         setNextLocalInstIndex(nullptr);
       }
     } else {
       Func->setFunctionName(FuncDecl->getName());
       Func->setReturnType(Signature.getReturnType());
       Func->setInternal(FuncDecl->getLinkage() == GlobalValue::InternalLinkage);
-      CurrentNode = installNextBasicBlock();
+      constexpr NaClBcIndexSize_t EntryBlock = 0;
+      CurrentNode = getBasicBlock(EntryBlock);
       Func->setEntryNode(CurrentNode);
       for (Ice::Type ArgType : Signature.getArgList()) {
         Func->addArg(getNextInstVar(ArgType));
       }
     }
     bool ParserResult = ParseThisBlock();
 
     // Temporarily end per-function timing, which will be resumed by
     // the translator function.  This is because translation may be
     // done asynchronously in a separate thread.
@@ skipping 47 matching lines @@
       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::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;
   // Holds the index within LocalOperands corresponding to the next
@@ skipping 22 matching lines @@
     // Error recover with value that is always acceptable.
     Alignment = 1;
   }
 
   bool ParseBlock(unsigned BlockID) override;
 
   void ProcessRecord() override;
 
   void ExitBlock() override;
 
-  // Creates and appends a new basic block to the list of basic blocks.
-  Ice::CfgNode *installNextBasicBlock() {
-    assert(!isIRGenerationDisabled());
-    return Func->makeNode();
-  }
-
-  // Returns the Index-th basic block in the list of basic blocks.
-  Ice::CfgNode *getBasicBlock(NaClBcIndexSize_t Index) {
-    assert(!isIRGenerationDisabled());
-    const Ice::NodeList &Nodes = Func->getNodes();
-    if (Index >= Nodes.size()) {
-      std::string Buffer;
-      raw_string_ostream StrBuf(Buffer);
-      StrBuf << "Reference to basic block " << Index
-             << " not found. Must be less than " << Nodes.size();
-      Error(StrBuf.str());
-      // TODO(kschimpf) Remove error recovery once implementation complete.
-      Index = 0;
-    }
-    return Nodes[Index];
-  }
+  bool verifyAndRenameBasicBlocks();
 
   // 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 587 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::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;
+  }
+  // Verify size limit allowed for basic blocks.
+  if (NumFoundBbs > NaClBcIndexSize_t_Max) {
+    std::string Buffer;
+    raw_string_ostream StrBuf(Buffer);
+    StrBuf << "Functions can't define more than " << NaClBcIndexSize_t_Max
+           << "basic blocks. Found: " << NumFoundBbs;
+    Error(StrBuf.str());
+    return false;
+  }
+  // Sort list of Bbs, verifying that no basic blocks are missing.
+  Ice::NodeList SortedBbs;
+  for (size_t i = 0; i < NumFoundBbs; ++i) {
+    CfgNodeMap::iterator pos = BbMap.find(i);
+    if (pos == BbMap.end()) {
+      std::string Buffer;
+      raw_string_ostream StrBuf(Buffer);
+      StrBuf << "Can't find definition for basic block " << i << ".";
+      Error(StrBuf.str());
+      return false;
+    }
+    SortedBbs.push_back(pos->second);
+  }
+  // Install sorted basic blocks.
+  Func->swapNodes(SortedBbs);
+  return true;
+}
+
 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()));
   }
   if (isIRGenerationDisabled())
     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";
       Error(StrBuf.str());
       // TODO(kschimpf) Remove error recovery once implementation complete.
@@ skipping 38 matching lines @@
       NumBbsRaw = 1;
     } else if (NumBbsRaw > NaClBcIndexSize_t_Max) {
       std::string Buffer;
       raw_string_ostream StrBuf(Buffer);
       StrBuf << "To many basic blocks specified: " << NumBbsRaw;
       Error(StrBuf.str());
       NumBbsRaw = NaClBcIndexSize_t_Max;
     }
     if (isIRGenerationDisabled())
       return;
-    if (Func->getNodes().size() != 1) {
+    if (SpecifiedNumBbs != 0) {
       Error("Duplicate function block count record");
       return;
     }
-    // Install the basic blocks, skipping bb0 which was created in the
-    // constructor.
-    for (size_t i = 1, NumBbs = NumBbsRaw; i < NumBbs; ++i)
-      installNextBasicBlock();
+    SpecifiedNumBbs = NumBbsRaw;
     return;
   }
   case naclbitc::FUNC_CODE_INST_BINOP: {
     // BINOP: [opval, opval, opcode]
     if (!isValidRecordSize(3, "binop"))
       return;
     Ice::Operand *Op1 = getRelativeOperand(Values[0], BaseIndex);
     Ice::Operand *Op2 = getRelativeOperand(Values[1], BaseIndex);
     if (isIRGenerationDisabled()) {
       assert(Op1 == nullptr && Op2 == nullptr);
@@ skipping 803 matching lines @@
       std::string Nm(Name.data(), Name.size());
       V->setName(getFunctionParser()->getFunc(), Nm);
     }
   } else {
     reportUnableToAssign("variable", Index, Name);
   }
 }
 
 void FunctionValuesymtabParser::setBbName(NaClBcIndexSize_t Index,
                                           StringType &Name) {
-  if (isIRGenerationDisabled())
+  if (isIRGenerationDisabled() || !Ice::BuildDefs::dump())

[Jim Stichnoth, 2015/08/06 19:41:21]

Test for BuildDefs::dump() very first, even before isIRGenerationDisabled(), so
that the function is *completely* empty if dump is not defined.  E.g., swap the
|| operand order.

[Karl, 2015/08/06 19:55:41]

Done.

     return;
-  if (Index >= getFunctionParser()->getFunc()->getNumNodes()) {
-    reportUnableToAssign("block", Index, Name);
-    return;
-  }
+  Ice::CfgNode *Bb = getFunctionParser()->getBasicBlock(Index);
   std::string Nm(Name.data(), Name.size());
-  if (Ice::BuildDefs::dump())
-    getFunctionParser()->getFunc()->getNodes()[Index]->setName(Nm);
+  Bb->setName(Nm);
 }
 
 bool FunctionParser::ParseBlock(unsigned BlockID) {
   switch (BlockID) {
   case naclbitc::CONSTANTS_BLOCK_ID: {
     ConstantsParser Parser(BlockID, this);
     return Parser.ParseThisBlock();
   }
   case naclbitc::VALUE_SYMTAB_BLOCK_ID: {
     if (PNaClAllowLocalSymbolTables) {
@@ skipping 225 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