diff options
-rw-r--r-- | include/llvm/MC/MCCodeView.h | 48 | ||||
-rw-r--r-- | include/llvm/Support/GenericDomTreeConstruction.h | 28 | ||||
-rw-r--r-- | lib/MC/MCCodeView.cpp | 69 | ||||
-rw-r--r-- | test/MC/COFF/cv-inline-linetable.s | 26 | ||||
-rw-r--r-- | unittests/IR/DominatorTreeBatchUpdatesTest.cpp | 95 |
5 files changed, 211 insertions, 55 deletions
diff --git a/include/llvm/MC/MCCodeView.h b/include/llvm/MC/MCCodeView.h index e2249f49c86..c8f14515ed3 100644 --- a/include/llvm/MC/MCCodeView.h +++ b/include/llvm/MC/MCCodeView.h @@ -177,13 +177,7 @@ public: unsigned IACol); /// Retreive the function info if this is a valid function id, or nullptr. - MCCVFunctionInfo *getCVFunctionInfo(unsigned FuncId) { - if (FuncId >= Functions.size()) - return nullptr; - if (Functions[FuncId].isUnallocatedFunctionInfo()) - return nullptr; - return &Functions[FuncId]; - } + MCCVFunctionInfo *getCVFunctionInfo(unsigned FuncId); /// Saves the information from the currently parsed .cv_loc directive /// and sets CVLocSeen. When the next instruction is assembled an entry @@ -199,50 +193,22 @@ public: CurrentCVLoc.setIsStmt(IsStmt); CVLocSeen = true; } - void clearCVLocSeen() { CVLocSeen = false; } bool getCVLocSeen() { return CVLocSeen; } + void clearCVLocSeen() { CVLocSeen = false; } + const MCCVLoc &getCurrentCVLoc() { return CurrentCVLoc; } bool isValidCVFileNumber(unsigned FileNumber); /// \brief Add a line entry. - void addLineEntry(const MCCVLineEntry &LineEntry) { - size_t Offset = MCCVLines.size(); - auto I = MCCVLineStartStop.insert( - {LineEntry.getFunctionId(), {Offset, Offset + 1}}); - if (!I.second) - I.first->second.second = Offset + 1; - MCCVLines.push_back(LineEntry); - } + void addLineEntry(const MCCVLineEntry &LineEntry); - std::vector<MCCVLineEntry> getFunctionLineEntries(unsigned FuncId) { - std::vector<MCCVLineEntry> FilteredLines; + std::vector<MCCVLineEntry> getFunctionLineEntries(unsigned FuncId); - auto I = MCCVLineStartStop.find(FuncId); - if (I != MCCVLineStartStop.end()) - for (size_t Idx = I->second.first, End = I->second.second; Idx != End; - ++Idx) - if (MCCVLines[Idx].getFunctionId() == FuncId) - FilteredLines.push_back(MCCVLines[Idx]); - return FilteredLines; - } - - std::pair<size_t, size_t> getLineExtent(unsigned FuncId) { - auto I = MCCVLineStartStop.find(FuncId); - // Return an empty extent if there are no cv_locs for this function id. - if (I == MCCVLineStartStop.end()) - return {~0ULL, 0}; - return I->second; - } + std::pair<size_t, size_t> getLineExtent(unsigned FuncId); - ArrayRef<MCCVLineEntry> getLinesForExtent(size_t L, size_t R) { - if (R <= L) - return None; - if (L >= MCCVLines.size()) - return None; - return makeArrayRef(&MCCVLines[L], R - L); - } + ArrayRef<MCCVLineEntry> getLinesForExtent(size_t L, size_t R); /// Emits a line table substream. void emitLineTableForFunction(MCObjectStreamer &OS, unsigned FuncId, diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h index e85ac76c780..25175fe66aa 100644 --- a/include/llvm/Support/GenericDomTreeConstruction.h +++ b/include/llvm/Support/GenericDomTreeConstruction.h @@ -706,7 +706,7 @@ struct SemiNCAInfo { // algorithm does not really know or use the set of roots and can make a // different (implicit) decision about which nodes within an infinite loop // becomes a root. - if (DT.isVirtualRoot(TN->getIDom())) { + if (TN && !DT.isVirtualRoot(TN->getIDom())) { DEBUG(dbgs() << "Root " << BlockNamePrinter(R) << " is not virtual root's child\n" << "The entire tree needs to be rebuilt\n"); @@ -940,21 +940,21 @@ struct SemiNCAInfo { const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To); const TreeNodePtr NCD = DT.getNode(NCDBlock); - // To dominates From -- nothing to do. - if (ToTN == NCD) return; + // If To dominates From -- nothing to do. + if (ToTN != NCD) { + DT.DFSInfoValid = false; - DT.DFSInfoValid = false; - - const TreeNodePtr ToIDom = ToTN->getIDom(); - DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom " - << BlockNamePrinter(ToIDom) << "\n"); + const TreeNodePtr ToIDom = ToTN->getIDom(); + DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom " + << BlockNamePrinter(ToIDom) << "\n"); - // To remains reachable after deletion. - // (Based on the caption under Figure 4. from the second paper.) - if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN)) - DeleteReachable(DT, BUI, FromTN, ToTN); - else - DeleteUnreachable(DT, BUI, ToTN); + // To remains reachable after deletion. + // (Based on the caption under Figure 4. from the second paper.) + if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN)) + DeleteReachable(DT, BUI, FromTN, ToTN); + else + DeleteUnreachable(DT, BUI, ToTN); + } if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); } diff --git a/lib/MC/MCCodeView.cpp b/lib/MC/MCCodeView.cpp index 82b81ccc24d..5fd5bde9f1e 100644 --- a/lib/MC/MCCodeView.cpp +++ b/lib/MC/MCCodeView.cpp @@ -76,6 +76,14 @@ bool CodeViewContext::addFile(MCStreamer &OS, unsigned FileNumber, return true; } +MCCVFunctionInfo *CodeViewContext::getCVFunctionInfo(unsigned FuncId) { + if (FuncId >= Functions.size()) + return nullptr; + if (Functions[FuncId].isUnallocatedFunctionInfo()) + return nullptr; + return &Functions[FuncId]; +} + bool CodeViewContext::recordFunctionId(unsigned FuncId) { if (FuncId >= Functions.size()) Functions.resize(FuncId + 1); @@ -247,6 +255,67 @@ void CodeViewContext::emitFileChecksumOffset(MCObjectStreamer &OS, OS.EmitValueImpl(SRE, 4); } +void CodeViewContext::addLineEntry(const MCCVLineEntry &LineEntry) { + size_t Offset = MCCVLines.size(); + auto I = MCCVLineStartStop.insert( + {LineEntry.getFunctionId(), {Offset, Offset + 1}}); + if (!I.second) + I.first->second.second = Offset + 1; + MCCVLines.push_back(LineEntry); +} + +std::vector<MCCVLineEntry> +CodeViewContext::getFunctionLineEntries(unsigned FuncId) { + std::vector<MCCVLineEntry> FilteredLines; + auto I = MCCVLineStartStop.find(FuncId); + if (I != MCCVLineStartStop.end()) { + MCCVFunctionInfo *SiteInfo = getCVFunctionInfo(FuncId); + for (size_t Idx = I->second.first, End = I->second.second; Idx != End; + ++Idx) { + unsigned LocationFuncId = MCCVLines[Idx].getFunctionId(); + if (LocationFuncId == FuncId) { + // This was a .cv_loc directly for FuncId, so record it. + FilteredLines.push_back(MCCVLines[Idx]); + } else { + // Check if the current location is inlined in this function. If it is, + // synthesize a statement .cv_loc at the original inlined call site. + auto I = SiteInfo->InlinedAtMap.find(LocationFuncId); + if (I != SiteInfo->InlinedAtMap.end()) { + MCCVFunctionInfo::LineInfo &IA = I->second; + // Only add the location if it differs from the previous location. + // Large inlined calls will have many .cv_loc entries and we only need + // one line table entry in the parent function. + if (FilteredLines.empty() || + FilteredLines.back().getFileNum() != IA.File || + FilteredLines.back().getLine() != IA.Line || + FilteredLines.back().getColumn() != IA.Col) { + FilteredLines.push_back(MCCVLineEntry( + MCCVLines[Idx].getLabel(), + MCCVLoc(FuncId, IA.File, IA.Line, IA.Col, false, false))); + } + } + } + } + } + return FilteredLines; +} + +std::pair<size_t, size_t> CodeViewContext::getLineExtent(unsigned FuncId) { + auto I = MCCVLineStartStop.find(FuncId); + // Return an empty extent if there are no cv_locs for this function id. + if (I == MCCVLineStartStop.end()) + return {~0ULL, 0}; + return I->second; +} + +ArrayRef<MCCVLineEntry> CodeViewContext::getLinesForExtent(size_t L, size_t R) { + if (R <= L) + return None; + if (L >= MCCVLines.size()) + return None; + return makeArrayRef(&MCCVLines[L], R - L); +} + void CodeViewContext::emitLineTableForFunction(MCObjectStreamer &OS, unsigned FuncId, const MCSymbol *FuncBegin, diff --git a/test/MC/COFF/cv-inline-linetable.s b/test/MC/COFF/cv-inline-linetable.s index 61a42d92f40..c5e28c4d078 100644 --- a/test/MC/COFF/cv-inline-linetable.s +++ b/test/MC/COFF/cv-inline-linetable.s @@ -135,3 +135,29 @@ Ltmp1: .cv_filechecksums # File index to string table offset subsection .cv_stringtable # String table +# CHECK-LABEL: FunctionLineTable [ +# CHECK: LinkageName: ?baz@@YAXXZ +# CHECK: Flags: 0x1 +# CHECK: CodeSize: 0x3D +# CHECK: FilenameSegment [ +# CHECK: Filename: D:\src\llvm\build\t.cpp (0x0) +# CHECK: +0x0 [ +# CHECK: LineNumberStart: 13 +# CHECK: ] +# CHECK: +0x1 [ +# CHECK: LineNumberStart: 14 +# CHECK: ] +# CHECK: +0x8 [ +# CHECK: LineNumberStart: 15 +# CHECK: ] +# There shouldn't be any other line number entries because all the other +# .cv_locs are on line 15 where the top-level inline call site is. +# CHECK-NOT: LineNumberStart +# CHECK: +0x34 [ +# CHECK: LineNumberStart: 16 +# CHECK: ] +# CHECK: +0x3B [ +# CHECK: LineNumberStart: 17 +# CHECK: ] +# CHECK: ] +# CHECK: ] diff --git a/unittests/IR/DominatorTreeBatchUpdatesTest.cpp b/unittests/IR/DominatorTreeBatchUpdatesTest.cpp index 4ad1f69030c..e362afd8404 100644 --- a/unittests/IR/DominatorTreeBatchUpdatesTest.cpp +++ b/unittests/IR/DominatorTreeBatchUpdatesTest.cpp @@ -258,3 +258,98 @@ TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) { EXPECT_TRUE(PDT.verify()); } } + +// These are some odd flowgraphs, usually generated from csmith cases, +// which are difficult on post dom trees. +TEST(DominatorTreeBatchUpdates, InfiniteLoop) { + std::vector<CFGBuilder::Arc> Arcs = { + {"1", "2"}, + {"2", "3"}, + {"3", "6"}, {"3", "5"}, + {"4", "5"}, + {"5", "2"}, + {"6", "3"}, {"6", "4"}}; + + // SplitBlock on 3 -> 5 + std::vector<CFGBuilder::Update> Updates = { + {CFGInsert, {"N", "5"}}, {CFGInsert, {"3", "N"}}, {CFGDelete, {"3", "5"}}}; + + CFGHolder Holder; + CFGBuilder B(Holder.F, Arcs, Updates); + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + while (B.applyUpdate()) + ; + + auto DomUpdates = ToDomUpdates(B, Updates); + DT.applyUpdates(DomUpdates); + EXPECT_TRUE(DT.verify()); + PDT.applyUpdates(DomUpdates); + EXPECT_TRUE(PDT.verify()); +} + +TEST(DominatorTreeBatchUpdates, DeadBlocks) { + std::vector<CFGBuilder::Arc> Arcs = { + {"1", "2"}, + {"2", "3"}, + {"3", "4"}, {"3", "7"}, + {"4", "4"}, + {"5", "6"}, {"5", "7"}, + {"6", "7"}, + {"7", "2"}, {"7", "8"}}; + + // Remove dead 5 and 7, + // plus SplitBlock on 7 -> 8 + std::vector<CFGBuilder::Update> Updates = { + {CFGDelete, {"6", "7"}}, {CFGDelete, {"5", "7"}}, {CFGDelete, {"5", "6"}}, + {CFGInsert, {"N", "8"}}, {CFGInsert, {"7", "N"}}, {CFGDelete, {"7", "8"}}}; + + CFGHolder Holder; + CFGBuilder B(Holder.F, Arcs, Updates); + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + while (B.applyUpdate()) + ; + + auto DomUpdates = ToDomUpdates(B, Updates); + DT.applyUpdates(DomUpdates); + EXPECT_TRUE(DT.verify()); + PDT.applyUpdates(DomUpdates); + EXPECT_TRUE(PDT.verify()); +} + +TEST(DominatorTreeBatchUpdates, InfiniteLoop2) { + std::vector<CFGBuilder::Arc> Arcs = { + {"1", "2"}, + {"2", "6"}, {"2", "3"}, + {"3", "4"}, + {"4", "5"}, {"4", "6"}, + {"5", "4"}, + {"6", "2"}}; + + // SplitBlock on 4 -> 6 + std::vector<CFGBuilder::Update> Updates = { + {CFGInsert, {"N", "6"}}, {CFGInsert, {"4", "N"}}, {CFGDelete, {"4", "6"}}}; + + CFGHolder Holder; + CFGBuilder B(Holder.F, Arcs, Updates); + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + while (B.applyUpdate()) + ; + + auto DomUpdates = ToDomUpdates(B, Updates); + DT.applyUpdates(DomUpdates); + EXPECT_TRUE(DT.verify()); + PDT.applyUpdates(DomUpdates); + EXPECT_TRUE(PDT.verify()); +} |