Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(176)

Side by Side Diff: src/PNaClTranslator.cpp

Issue 1297433002: Change tracking of basic blocks (within function) to use a vector. (Closed) Base URL: https://chromium.googlesource.com/native_client/pnacl-subzero.git@master
Patch Set: Fix nits. Created 5 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | tests_lit/parse_errs/Inputs/bad-bb-size.tbc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 //===- subzero/src/PNaClTranslator.cpp - ICE from bitcode -----------------===// 1 //===- subzero/src/PNaClTranslator.cpp - ICE from bitcode -----------------===//
2 // 2 //
3 // The Subzero Code Generator 3 // The Subzero Code Generator
4 // 4 //
5 // This file is distributed under the University of Illinois Open Source 5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details. 6 // License. See LICENSE.TXT for details.
7 // 7 //
8 //===----------------------------------------------------------------------===// 8 //===----------------------------------------------------------------------===//
9 /// 9 ///
10 /// \file 10 /// \file
(...skipping 1233 matching lines...) Expand 10 before | Expand all | Expand 10 after
1244 if (isIRGenerationDisabled()) { 1244 if (isIRGenerationDisabled()) {
1245 CurrentNode = nullptr; 1245 CurrentNode = nullptr;
1246 for (Ice::Type ArgType : Signature.getArgList()) { 1246 for (Ice::Type ArgType : Signature.getArgList()) {
1247 (void)ArgType; 1247 (void)ArgType;
1248 setNextLocalInstIndex(nullptr); 1248 setNextLocalInstIndex(nullptr);
1249 } 1249 }
1250 } else { 1250 } else {
1251 Func->setFunctionName(FuncDecl->getName()); 1251 Func->setFunctionName(FuncDecl->getName());
1252 Func->setReturnType(Signature.getReturnType()); 1252 Func->setReturnType(Signature.getReturnType());
1253 Func->setInternal(FuncDecl->getLinkage() == GlobalValue::InternalLinkage); 1253 Func->setInternal(FuncDecl->getLinkage() == GlobalValue::InternalLinkage);
1254 constexpr NaClBcIndexSize_t EntryBlock = 0; 1254 CurrentNode = installNextBasicBlock();
1255 CurrentNode = getBasicBlock(EntryBlock);
1256 Func->setEntryNode(CurrentNode); 1255 Func->setEntryNode(CurrentNode);
1257 for (Ice::Type ArgType : Signature.getArgList()) { 1256 for (Ice::Type ArgType : Signature.getArgList()) {
1258 Func->addArg(getNextInstVar(ArgType)); 1257 Func->addArg(getNextInstVar(ArgType));
1259 } 1258 }
1260 } 1259 }
1261 bool ParserResult = ParseThisBlock(); 1260 bool ParserResult = ParseThisBlock();
1262 1261
1263 // Temporarily end per-function timing, which will be resumed by 1262 // Temporarily end per-function timing, which will be resumed by
1264 // the translator function. This is because translation may be 1263 // the translator function. This is because translation may be
1265 // done asynchronously in a separate thread. 1264 // done asynchronously in a separate thread.
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after
1307 if (isIRGenerationDisabled()) 1306 if (isIRGenerationDisabled())
1308 return nullptr; 1307 return nullptr;
1309 std::string Buffer; 1308 std::string Buffer;
1310 raw_string_ostream StrBuf(Buffer); 1309 raw_string_ostream StrBuf(Buffer);
1311 StrBuf << "Value index " << Index << " not defined!"; 1310 StrBuf << "Value index " << Index << " not defined!";
1312 Fatal(StrBuf.str()); 1311 Fatal(StrBuf.str());
1313 } 1312 }
1314 return Op; 1313 return Op;
1315 } 1314 }
1316 1315
1317 // Returns the Index-th basic block in the list of basic blocks.
1318 Ice::CfgNode *getBasicBlock(NaClBcIndexSize_t Index) {
1319 assert(!isIRGenerationDisabled());
1320 Ice::CfgNode *&Node = BbMap[Index];
1321 if (Node == nullptr)
1322 Node = Func->makeNode();
1323 return Node;
1324 }
1325
1326 private: 1316 private:
1327 typedef std::unordered_map<NaClBcIndexSize_t, Ice::Operand *> OperandMap; 1317 typedef std::unordered_map<NaClBcIndexSize_t, Ice::Operand *> OperandMap;
1328 typedef std::unordered_map<NaClBcIndexSize_t, Ice::CfgNode *> CfgNodeMap;
1329 1318
1330 Ice::TimerMarker Timer; 1319 Ice::TimerMarker Timer;
1320 // The number of words in the bitstream defining the function block.
1321 uint64_t NumBytesDefiningFunction = 0;
1331 // The corresponding ICE function defined by the function block. 1322 // The corresponding ICE function defined by the function block.
1332 std::unique_ptr<Ice::Cfg> Func; 1323 std::unique_ptr<Ice::Cfg> Func;
1333 // The specified number of basic blocks in the bitcode file.
1334 NaClBcIndexSize_t SpecifiedNumBbs = 0;
1335 // The index to the current basic block being built. 1324 // The index to the current basic block being built.
1336 NaClBcIndexSize_t CurrentBbIndex = 0; 1325 NaClBcIndexSize_t CurrentBbIndex = 0;
1326 // The number of basic blocks declared for the function block.
1327 NaClBcIndexSize_t DeclaredNumberBbs = 0;
1337 // The basic block being built. 1328 // The basic block being built.
1338 Ice::CfgNode *CurrentNode = nullptr; 1329 Ice::CfgNode *CurrentNode = nullptr;
1339 // Map from basic block id (as defined in the bitcode file) to
1340 // the corresponding basic block that implements it.
1341 CfgNodeMap BbMap;
1342 // The ID for the function. 1330 // The ID for the function.
1343 NaClBcIndexSize_t FcnId; 1331 NaClBcIndexSize_t FcnId;
1344 // The corresponding function declaration. 1332 // The corresponding function declaration.
1345 Ice::FunctionDeclaration *FuncDecl; 1333 Ice::FunctionDeclaration *FuncDecl;
1346 // Holds the dividing point between local and global absolute value indices. 1334 // Holds the dividing point between local and global absolute value indices.
1347 size_t CachedNumGlobalValueIDs; 1335 size_t CachedNumGlobalValueIDs;
1348 // Holds operands local to the function block, based on indices 1336 // Holds operands local to the function block, based on indices
1349 // defined in the bitcode file. 1337 // defined in the bitcode file.
1350 OperandMap LocalOperands; 1338 OperandMap LocalOperands;
1351 // Holds the index within LocalOperands corresponding to the next 1339 // Holds the index within LocalOperands corresponding to the next
(...skipping 20 matching lines...) Expand all
1372 << ". Found: 2**" << (AlignPower - 1); 1360 << ". Found: 2**" << (AlignPower - 1);
1373 Error(StrBuf.str()); 1361 Error(StrBuf.str());
1374 // Error recover with value that is always acceptable. 1362 // Error recover with value that is always acceptable.
1375 Alignment = 1; 1363 Alignment = 1;
1376 } 1364 }
1377 1365
1378 bool ParseBlock(unsigned BlockID) override; 1366 bool ParseBlock(unsigned BlockID) override;
1379 1367
1380 void ProcessRecord() override; 1368 void ProcessRecord() override;
1381 1369
1370 void EnterBlock(unsigned NumWords) final {
1371 // Note: Bitstream defines words as 32-bit values.
1372 NumBytesDefiningFunction = NumWords * sizeof(uint32_t);
1373 }
1374
1382 void ExitBlock() override; 1375 void ExitBlock() override;
1383 1376
1384 bool verifyAndRenameBasicBlocks(); 1377 bool verifyAllForwardRefsDefined();
1385 1378
1386 bool verifyAllForwardRefsDefined(); 1379 // Creates and appends a new basic block to the list of basic blocks.
1380 Ice::CfgNode *installNextBasicBlock() {
1381 assert(!isIRGenerationDisabled());
1382 Ice::CfgNode *Node = Func->makeNode();
1383 return Node;
1384 }
1385
1386 // Returns the Index-th basic block in the list of basic blocks.
1387 Ice::CfgNode *getBasicBlock(NaClBcIndexSize_t Index) {
1388 assert(!isIRGenerationDisabled());
1389 if (Index >= Func->getNumNodes()) {
1390 std::string Buffer;
1391 raw_string_ostream StrBuf(Buffer);
1392 StrBuf << "Reference to basic block " << Index
1393 << " not found. Must be less than " << Func->getNumNodes();
1394 Error(StrBuf.str());
1395 Index = 0;
1396 }
1397 return Func->getNodes()[Index];
1398 }
1387 1399
1388 // Returns the Index-th basic block in the list of basic blocks. 1400 // Returns the Index-th basic block in the list of basic blocks.
1389 // Assumes Index corresponds to a branch instruction. Hence, if 1401 // Assumes Index corresponds to a branch instruction. Hence, if
1390 // the branch references the entry block, it also generates a 1402 // the branch references the entry block, it also generates a
1391 // corresponding error. 1403 // corresponding error.
1392 Ice::CfgNode *getBranchBasicBlock(NaClBcIndexSize_t Index) { 1404 Ice::CfgNode *getBranchBasicBlock(NaClBcIndexSize_t Index) {
1393 assert(!isIRGenerationDisabled()); 1405 assert(!isIRGenerationDisabled());
1394 if (Index == 0) { 1406 if (Index == 0) {
1395 Error("Branch to entry block not allowed"); 1407 Error("Branch to entry block not allowed");
1396 } 1408 }
(...skipping 592 matching lines...) Expand 10 before | Expand all | Expand 10 after
1989 std::sort(UndefinedFwdRefs.begin(), UndefinedFwdRefs.end()); 2001 std::sort(UndefinedFwdRefs.begin(), UndefinedFwdRefs.end());
1990 for (const NaClBcIndexSize_t Index : UndefinedFwdRefs) { 2002 for (const NaClBcIndexSize_t Index : UndefinedFwdRefs) {
1991 std::string Buffer; 2003 std::string Buffer;
1992 raw_string_ostream StrBuf(Buffer); 2004 raw_string_ostream StrBuf(Buffer);
1993 StrBuf << "Instruction forward reference not defined: " << Index; 2005 StrBuf << "Instruction forward reference not defined: " << Index;
1994 Error(StrBuf.str()); 2006 Error(StrBuf.str());
1995 } 2007 }
1996 return false; 2008 return false;
1997 } 2009 }
1998 2010
1999 bool FunctionParser::verifyAndRenameBasicBlocks() {
2000 const size_t NumFoundBbs = BbMap.size();
2001 // Verify number of basic blocks found match amount specified in function.
2002 if (NumFoundBbs != SpecifiedNumBbs) {
2003 std::string Buffer;
2004 raw_string_ostream StrBuf(Buffer);
2005 StrBuf << "Function specified " << SpecifiedNumBbs
2006 << "basic blocks. Found: " << NumFoundBbs;
2007 Error(StrBuf.str());
2008 return false;
2009 }
2010 // Verify size limit allowed for basic blocks.
2011 if (NumFoundBbs > NaClBcIndexSize_t_Max) {
2012 std::string Buffer;
2013 raw_string_ostream StrBuf(Buffer);
2014 StrBuf << "Functions can't define more than " << NaClBcIndexSize_t_Max
2015 << "basic blocks. Found: " << NumFoundBbs;
2016 Error(StrBuf.str());
2017 return false;
2018 }
2019 // Sort list of Bbs, verifying that no basic blocks are missing.
2020 Ice::NodeList SortedBbs;
2021 for (size_t i = 0; i < NumFoundBbs; ++i) {
2022 CfgNodeMap::iterator pos = BbMap.find(i);
2023 if (pos == BbMap.end()) {
2024 std::string Buffer;
2025 raw_string_ostream StrBuf(Buffer);
2026 StrBuf << "Can't find definition for basic block " << i << ".";
2027 Error(StrBuf.str());
2028 return false;
2029 }
2030 SortedBbs.push_back(pos->second);
2031 }
2032 // Install sorted basic blocks.
2033 Func->swapNodes(SortedBbs);
2034 return true;
2035 }
2036
2037 void FunctionParser::ExitBlock() { 2011 void FunctionParser::ExitBlock() {
2038 // Check if the last instruction in the function was terminating. 2012 // Check if the last instruction in the function was terminating.
2039 if (!InstIsTerminating) { 2013 if (!InstIsTerminating) {
2040 Error("Last instruction in function not terminator"); 2014 Error("Last instruction in function not terminator");
2041 if (isIRGenerationDisabled()) 2015 if (isIRGenerationDisabled())
2042 return; 2016 return;
2043 // Recover by inserting an unreachable instruction. 2017 // Recover by inserting an unreachable instruction.
2044 CurrentNode->appendInst(Ice::InstUnreachable::create(Func.get())); 2018 CurrentNode->appendInst(Ice::InstUnreachable::create(Func.get()));
2045 } 2019 }
2020 ++CurrentBbIndex;
2021 if (CurrentBbIndex != DeclaredNumberBbs) {
2022 std::string Buffer;
2023 raw_string_ostream StrBuf(Buffer);
2024 StrBuf << "Function declared " << DeclaredNumberBbs
2025 << " basic blocks, but defined " << CurrentBbIndex << ".";
2026 Error(StrBuf.str());
2027 }
2046 if (isIRGenerationDisabled()) 2028 if (isIRGenerationDisabled())
2047 return; 2029 return;
2048 if (!verifyAllForwardRefsDefined()) 2030 if (!verifyAllForwardRefsDefined())
2049 return; 2031 return;
2050 if (!verifyAndRenameBasicBlocks())
2051 return;
2052 // Before translating, check for blocks without instructions, and 2032 // Before translating, check for blocks without instructions, and
2053 // insert unreachable. This shouldn't happen, but be safe. 2033 // insert unreachable. This shouldn't happen, but be safe.
2054 size_t Index = 0; 2034 size_t Index = 0;
2055 for (Ice::CfgNode *Node : Func->getNodes()) { 2035 for (Ice::CfgNode *Node : Func->getNodes()) {
2056 if (Node->getInsts().empty()) { 2036 if (Node->getInsts().empty()) {
2057 std::string Buffer; 2037 std::string Buffer;
2058 raw_string_ostream StrBuf(Buffer); 2038 raw_string_ostream StrBuf(Buffer);
2059 StrBuf << "Basic block " << Index << " contains no instructions"; 2039 StrBuf << "Basic block " << Index << " contains no instructions";
2060 Error(StrBuf.str()); 2040 Error(StrBuf.str());
2061 Node->appendInst(Ice::InstUnreachable::create(Func.get())); 2041 Node->appendInst(Ice::InstUnreachable::create(Func.get()));
(...skipping 13 matching lines...) Expand all
2075 } 2055 }
2076 2056
2077 void FunctionParser::ProcessRecord() { 2057 void FunctionParser::ProcessRecord() {
2078 // Note: To better separate parse/IR generation times, when IR generation 2058 // Note: To better separate parse/IR generation times, when IR generation
2079 // is disabled we do the following: 2059 // is disabled we do the following:
2080 // 1) Delay exiting until after we extract operands. 2060 // 1) Delay exiting until after we extract operands.
2081 // 2) return before we access operands, since all operands will be a nullptr. 2061 // 2) return before we access operands, since all operands will be a nullptr.
2082 const NaClBitcodeRecord::RecordVector &Values = Record.GetValues(); 2062 const NaClBitcodeRecord::RecordVector &Values = Record.GetValues();
2083 if (InstIsTerminating) { 2063 if (InstIsTerminating) {
2084 InstIsTerminating = false; 2064 InstIsTerminating = false;
2065 ++CurrentBbIndex;
2085 if (!isIRGenerationDisabled()) 2066 if (!isIRGenerationDisabled())
2086 CurrentNode = getBasicBlock(++CurrentBbIndex); 2067 CurrentNode = getBasicBlock(CurrentBbIndex);
2087 } 2068 }
2088 // The base index for relative indexing. 2069 // The base index for relative indexing.
2089 NaClBcIndexSize_t BaseIndex = getNextInstIndex(); 2070 NaClBcIndexSize_t BaseIndex = getNextInstIndex();
2090 switch (Record.GetCode()) { 2071 switch (Record.GetCode()) {
2091 case naclbitc::FUNC_CODE_DECLAREBLOCKS: { 2072 case naclbitc::FUNC_CODE_DECLAREBLOCKS: {
2092 // DECLAREBLOCKS: [n] 2073 // DECLAREBLOCKS: [n]
2093 if (!isValidRecordSize(1, "count")) 2074 if (!isValidRecordSize(1, "count"))
2094 return; 2075 return;
2095 uint64_t NumBbsRaw = Values[0]; 2076 if (DeclaredNumberBbs > 0) {
2096 if (NumBbsRaw == 0) {
2097 Error("Functions must contain at least one basic block.");
2098 NumBbsRaw = 1;
2099 } else if (NumBbsRaw > NaClBcIndexSize_t_Max) {
2100 std::string Buffer;
2101 raw_string_ostream StrBuf(Buffer);
2102 StrBuf << "To many basic blocks specified: " << NumBbsRaw;
2103 Error(StrBuf.str());
2104 NumBbsRaw = NaClBcIndexSize_t_Max;
2105 }
2106 if (isIRGenerationDisabled())
2107 return;
2108 if (SpecifiedNumBbs != 0) {
2109 Error("Duplicate function block count record"); 2077 Error("Duplicate function block count record");
2110 return; 2078 return;
2111 } 2079 }
2112 SpecifiedNumBbs = NumBbsRaw; 2080
2081 uint64_t NumBbs = Values[0];
2082
2083 // Check for bad large sizes, since they can make ridiculous memory
2084 // requests and hang the user for large amounts of time. Note: We know
2085 // that each basic block must have a terminator instruction, and each
2086 // instruction is minimally defined by a two-bit abreviation.
2087 uint64_t MaxBbs = NumBytesDefiningFunction * (CHAR_BIT >> 1);
2088 if (NumBbs > MaxBbs) {
2089 std::string Buffer;
2090 raw_string_ostream StrBuf(Buffer);
2091 StrBuf << "Function defines " << NumBbs
2092 << " basic blocks, which is too big for a function containing "
2093 << NumBytesDefiningFunction << " bytes";
2094 Error(StrBuf.str());
2095 NumBbs = MaxBbs;
2096 }
2097
2098 if (NumBbs == 0) {
2099 Error("Functions must contain at least one basic block.");
2100 NumBbs = 1;
2101 }
2102
2103 DeclaredNumberBbs = NumBbs;
2104 if (isIRGenerationDisabled())
2105 return;
2106 // Install the basic blocks, skipping bb0 which was created in the
2107 // constructor.
2108 for (size_t i = 1; i < NumBbs; ++i)
2109 installNextBasicBlock();
2113 return; 2110 return;
2114 } 2111 }
2115 case naclbitc::FUNC_CODE_INST_BINOP: { 2112 case naclbitc::FUNC_CODE_INST_BINOP: {
2116 // BINOP: [opval, opval, opcode] 2113 // BINOP: [opval, opval, opcode]
2117 if (!isValidRecordSize(3, "binop")) 2114 if (!isValidRecordSize(3, "binop"))
2118 return; 2115 return;
2119 Ice::Operand *Op1 = getRelativeOperand(Values[0], BaseIndex); 2116 Ice::Operand *Op1 = getRelativeOperand(Values[0], BaseIndex);
2120 Ice::Operand *Op2 = getRelativeOperand(Values[1], BaseIndex); 2117 Ice::Operand *Op2 = getRelativeOperand(Values[1], BaseIndex);
2121 if (isIRGenerationDisabled()) { 2118 if (isIRGenerationDisabled()) {
2122 assert(Op1 == nullptr && Op2 == nullptr); 2119 assert(Op1 == nullptr && Op2 == nullptr);
(...skipping 803 matching lines...) Expand 10 before | Expand all | Expand 10 after
2926 reportUnableToAssign("variable", Index, Name); 2923 reportUnableToAssign("variable", Index, Name);
2927 } 2924 }
2928 } 2925 }
2929 2926
2930 void FunctionValuesymtabParser::setBbName(NaClBcIndexSize_t Index, 2927 void FunctionValuesymtabParser::setBbName(NaClBcIndexSize_t Index,
2931 StringType &Name) { 2928 StringType &Name) {
2932 if (!Ice::BuildDefs::dump()) 2929 if (!Ice::BuildDefs::dump())
2933 return; 2930 return;
2934 if (isIRGenerationDisabled()) 2931 if (isIRGenerationDisabled())
2935 return; 2932 return;
2936 Ice::CfgNode *Bb = getFunctionParser()->getBasicBlock(Index); 2933 if (Index >= getFunctionParser()->getFunc()->getNumNodes()) {
2934 reportUnableToAssign("block", Index, Name);
2935 return;
2936 }
2937 std::string Nm(Name.data(), Name.size()); 2937 std::string Nm(Name.data(), Name.size());
2938 Bb->setName(Nm); 2938 if (Ice::BuildDefs::dump())
2939 getFunctionParser()->getFunc()->getNodes()[Index]->setName(Nm);
2939 } 2940 }
2940 2941
2941 bool FunctionParser::ParseBlock(unsigned BlockID) { 2942 bool FunctionParser::ParseBlock(unsigned BlockID) {
2942 switch (BlockID) { 2943 switch (BlockID) {
2943 case naclbitc::CONSTANTS_BLOCK_ID: { 2944 case naclbitc::CONSTANTS_BLOCK_ID: {
2944 ConstantsParser Parser(BlockID, this); 2945 ConstantsParser Parser(BlockID, this);
2945 return Parser.ParseThisBlock(); 2946 return Parser.ParseThisBlock();
2946 } 2947 }
2947 case naclbitc::VALUE_SYMTAB_BLOCK_ID: { 2948 case naclbitc::VALUE_SYMTAB_BLOCK_ID: {
2948 if (PNaClAllowLocalSymbolTables) { 2949 if (PNaClAllowLocalSymbolTables) {
(...skipping 225 matching lines...) Expand 10 before | Expand all | Expand 10 after
3174 } 3175 }
3175 if (InputStreamFile.getBitcodeBytes().getExtent() % 4 != 0) { 3176 if (InputStreamFile.getBitcodeBytes().getExtent() % 4 != 0) {
3176 ErrStream 3177 ErrStream
3177 << IRFilename 3178 << IRFilename
3178 << ": Bitcode stream should be a multiple of 4 bytes in length.\n"; 3179 << ": Bitcode stream should be a multiple of 4 bytes in length.\n";
3179 llvm::report_fatal_error("Bitcode stream should be a multiple of 4 bytes"); 3180 llvm::report_fatal_error("Bitcode stream should be a multiple of 4 bytes");
3180 } 3181 }
3181 } 3182 }
3182 3183
3183 } // end of namespace Ice 3184 } // end of namespace Ice
OLDNEW
« no previous file with comments | « no previous file | tests_lit/parse_errs/Inputs/bad-bb-size.tbc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698