Fix translator handling of basic block indices.
The code used to use a vector to hold basic blocks associated with
indices. This had two problem: 1) The "number of blocks" record would
generate a vector of the given size (even if very large); and 2)
Indices would expand the vector to define the index (even if very
large).
In most cases, such large values are incorrect. To fix this, this
patch uses a map from block index, to the corresponding basic block.
Only after all basic block indices have been processed, we check that
the size makes sense, and convert it to a vector.
BUG= https://code.google.com/p/nativeclient/issues/detail?id=4261
R=jpp@chromium.org, stichnot@chromium.org
Review URL: https://codereview.chromium.org/1275953002 .
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 58d7957..4288f6d 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -61,6 +61,12 @@
return Node;
}
+void Cfg::swapNodes(NodeList &NewNodes) {
+ Nodes.swap(NewNodes);
+ for (SizeT I = 0, NumNodes = getNumNodes(); I < NumNodes; ++I)
+ Nodes[I]->resetIndex(I);
+}
+
void Cfg::addArg(Variable *Arg) {
Arg->setIsArg();
Args.push_back(Arg);
@@ -358,14 +364,14 @@
}
// Reorder Nodes according to the built-up lists.
- SizeT OldSize = Nodes.size();
- (void)OldSize;
- Nodes.clear();
+ NodeList Reordered;
+ Reordered.reserve(Placed.size() + Unreachable.size());
for (CfgNode *Node : Placed)
- Nodes.push_back(Node);
+ Reordered.push_back(Node);
for (CfgNode *Node : Unreachable)
- Nodes.push_back(Node);
- assert(Nodes.size() == OldSize);
+ Reordered.push_back(Node);
+ assert(getNumNodes() == Reordered.size());
+ swapNodes(Reordered);
}
namespace {
@@ -400,15 +406,14 @@
if (ToVisit[Node->getIndex()])
Unreachable.push_back(Node);
// Copy the layout list to the Nodes.
- SizeT OldSize = Nodes.size();
- (void)OldSize;
- Nodes.clear();
+ NodeList Shuffled;
+ Shuffled.reserve(ReversedReachable.size() + Unreachable.size());
for (CfgNode *Node : reverse_range(ReversedReachable))
- Nodes.emplace_back(Node);
- for (CfgNode *Node : Unreachable) {
- Nodes.emplace_back(Node);
- }
- assert(Nodes.size() == OldSize);
+ Shuffled.push_back(Node);
+ for (CfgNode *Node : Unreachable)
+ Shuffled.push_back(Node);
+ assert(Nodes.size() == Shuffled.size());
+ swapNodes(Shuffled);
dump("After basic block shuffling");
}
diff --git a/src/IceCfg.h b/src/IceCfg.h
index cf572c1..b5ded6a 100644
--- a/src/IceCfg.h
+++ b/src/IceCfg.h
@@ -90,6 +90,8 @@
CfgNode *makeNode();
SizeT getNumNodes() const { return Nodes.size(); }
const NodeList &getNodes() const { return Nodes; }
+ /// Swap nodes of Cfg with given list of nodes.
+ void swapNodes(NodeList &NewNodes);
/// @}
typedef int32_t IdentifierIndexType;
diff --git a/src/IceDefs.h b/src/IceDefs.h
index 374b4b3..1908a03 100644
--- a/src/IceDefs.h
+++ b/src/IceDefs.h
@@ -43,6 +43,7 @@
#include <mutex>
#include <string>
#include <system_error>
+#include <unordered_map>
#include <vector>
namespace Ice {
diff --git a/src/IceGlobalContext.cpp b/src/IceGlobalContext.cpp
index 0a426c7..ffa6c15 100644
--- a/src/IceGlobalContext.cpp
+++ b/src/IceGlobalContext.cpp
@@ -34,7 +34,6 @@
#include <algorithm> // max()
#include <cctype> // isdigit(), isupper()
#include <locale> // locale
-#include <unordered_map>
namespace std {
template <> struct hash<Ice::RelocatableTuple> {
diff --git a/src/IceTargetLoweringX86Base.h b/src/IceTargetLoweringX86Base.h
index 40966a2..46b472f 100644
--- a/src/IceTargetLoweringX86Base.h
+++ b/src/IceTargetLoweringX86Base.h
@@ -23,7 +23,6 @@
#include "IceTargetLowering.h"
#include <type_traits>
-#include <unordered_map>
#include <utility>
namespace Ice {
diff --git a/src/PNaClTranslator.cpp b/src/PNaClTranslator.cpp
index 11e0b8e..6ff9d97 100644
--- a/src/PNaClTranslator.cpp
+++ b/src/PNaClTranslator.cpp
@@ -1215,7 +1215,8 @@
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));
@@ -1283,14 +1284,30 @@
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.
@@ -1333,27 +1350,7 @@
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
@@ -1961,6 +1958,44 @@
}
};
+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) {
@@ -1972,6 +2007,8 @@
}
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;
@@ -2030,14 +2067,11 @@
}
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: {
@@ -2861,15 +2895,13 @@
void FunctionValuesymtabParser::setBbName(NaClBcIndexSize_t Index,
StringType &Name) {
+ if (!Ice::BuildDefs::dump())
+ return;
if (isIRGenerationDisabled())
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) {
