Add DWARF verifiers to verify address ranges are correct and scoped correctly.

[clayborg]

Summary

This change adds:

• Verify all DIEs with address ranges have valid ranges
• If a CU has a low/high PC or has a DW_AT_ranges, then verify that and DW_TAG_subprogram is completely contained in the CU ranges
• Keep a list of all address ranges for any DW_TAG_subprogram DIEs and verify none overlap
• verify that all DW_TAG_lexical_block and DW_TAG_inlined_subroutine address ranges are completely contained in the parent address ranges

[dblaikie]

I haven't followed some of the design direction Adrian's been pointing this work in - so all of this is subject to discussion, etc:

1. I'd expect not to build an entire representation of all ranges up-front, then verify them (uses more memory, etc) - but rather verify during a traversal of the DIEs instead

2. for/for loops to check if one range is a subset of another's probably rather inefficient. Not sure if LLVM already has better tools for this, though I suspect not.

3. I'm not sure that function ranges need to be special/separate - I'd expect any nested ranges (eg: the range of two scopes in a function) to be distinct as well, so I'd expect a more general algorithm that walks nodes and their children looking for ranges and checking that children are subsets of parents, and children are distinct from each other.

[clayborg]

In D32821#745213, @dblaikie wrote:

I haven't followed some of the design direction Adrian's been pointing this work in - so all of this is subject to discussion, etc:

1. I'd expect not to build an entire representation of all ranges up-front, then verify them (uses more memory, etc) - but rather verify during a traversal of the DIEs instead

The whole reason we need this is to look for overlapping functions between all CUs. This helps us to identify exactly which DIEs overlap. It is also just a DIE (2 pointers) + vector<pair<uint64_t, uint64_t>. Not too costly.

2. for/for loops to check if one range is a subset of another's probably rather inefficient. Not sure if LLVM already has better tools for this, though I suspect not.

It currently works and I have seen many errors introduced by the compilers when they optimize debug info and they get it wrong. We only check blocks and inline functions against the containing ranges. We can make sure the ranges are coalesced when needed, but other than that, what is innefficient about what is there? 99% of the time it is one range seeing if one other range is contained.

3. I'm not sure that function ranges need to be special/separate - I'd expect any nested ranges (eg: the range of two scopes in a function) to be distinct as well, so I'd expect a more general algorithm that walks nodes and their children looking for ranges and checking that children are subsets of parents, and children are distinct from each other.

Again, not sure what is wrong with the way it is doing it. We just keep a stack >= depth of the current DIE with ranges filled in. If a block or inlined function is found, it verifies it is in the parent. The DWARF doesn't store this information in any useful way we can access, so I believe this approach work well.

[clayborg]

And lets just get something to start with and optimize when we actually find something is taking too much memory or an algorithm is not efficient?

[clayborg]

One thing to clarify:

std::vector<RangeInfoType> DieRangeInfos;

is a vector that only gets as deep as the DIE depth. It doesn't get every range for every function, block, or inlined function, it just has a stack of ranges for the _current_ DIE depth.

std::set<RangeInfoType> AllFunctionRangeInfos;

Contains one entry for each DW_TAG_subprogram.

[clayborg]

• Make DIE verification recursive
• Remove all Depth based code and just pass info from the parent
• add detection of overalap between DW_TAG_lexical_block or DW_TAG_inlined_subroutine DIEs at the same level
• rename RangeInfoType to DieRangeInfo
• create a new VerifyDieInfo to help with verification

[clayborg]

David: this approach uses your suggested recursive approach and should make things clearer. It also adds verification of overlapping DW_TAG_lexical_block and DW_TAG_inlined_subroutine that are siblings at any level.

[clayborg]

Fixed address ranges not being contained errors from incorrectly being reported.

[clayborg]

Would love to get this one in if anyone any time. I have only one more patch after this for .debug_aranges

[aprantl]

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

129

We usually use \param for consistency.

lib/DebugInfo/DWARF/DWARFVerifier.cpp

256

It doesn't look like this is tested? (as far as I can tell by searching for the error message).

285

test?

341

This entire function has really weird indentation. Please clang-format.

361

. at the end

399

.

409

remove extra {

[aprantl]

David, are all your concerns addressed?
Otherwise from my end this change LGTM (with all outstanding issues addressed).

[dblaikie]

In D32821#747269, @aprantl wrote:

David, are all your concerns addressed?

Nah - I'll go over it on Monday.

Otherwise from my end this change LGTM (with all outstanding issues addressed).

lib/DebugInfo/DWARF/DWARFVerifier.cpp

316–317

Else after return

[clayborg]

Fixes:

• addressed Adrian's issues
• added test for invalid DIE ranges where high pc is less than low pc

[clayborg]

lib/DebugInfo/DWARF/DWARFVerifier.cpp

256

I added a test.

285

There are two: TestDwarfVerifyOverlappingFunctionRanges and TestDwarfVerifyOverlappingLexicalBlockRanges

[clayborg]

Fixed else after return.

[clayborg]

Moved ranges comparisons over into header file so we can unit test. The unit tests will help in case we make AnyDWARFRangesIntersect or DWARFRangesContains changes that assume sorted lists and try to do things more efficiently.

[dblaikie]

lib/DebugInfo/DWARF/DWARFVerifier.cpp

272–283

This still looks like it only compares adjacent pairs:

{{1, 2}, {2, 3}, {3, 4}}

Is that not the case? If it does' what if {1,3} overlap, but neither overlaps with 2? Will that be diagnosed?

283

If this change is independent of the rest of this patch, please commit it separately (doesn't need to be sent for review if you're just constifying something that should've been const to begin with)

346–375

I /think/ a lot of this code could be simplified if there were (as I mention in another comment) a generalized representation of the "scope of non-overlapping things with a possible parent they should all be within" that could be used at the CU level, subprogram level, and inter-subprogram level.

Let me know if you'd like me to sketch out such a design in more detail.

351

Similarly, commit without pre-commit review spelling corrections like this - makes it easier to review the real changes without having them conflated with cleanup changes like this.

372–376

I'd expect to do the subprogram checking incrementally, the same as the lexical scopes are done incrementally when another lexical scope is visited? Is there a reason to do it differently?

(possibly even using the same machinery/abstraction - even if it needs to be special cased to handle the interesting nesting cases)

377

Probably do this with

getUnitDIE(/* ExtractUnitDIEOnly = */ false)

rather than a local constant. Or try the trick Adrian did in a recent patch - an enum with a single value as a constant:

enum { ExtractAllDIEs = false };

(& could include that in the header where getUnitDIE is declared)

391–392

Why not do this as elements are visited, rather than at the end in another pass?

I'd imagine a small class that would take DIEs verify their ranges, merge them, flag merge failures (between previous DIEs or parents) & by the end there'd be nothing left to do?

[clayborg]

• Made a new NonOverlappingRanges class.
• Use it to verify address ranges on the fly for
  • functions within all CUs
  • lexical block and inlined functions in DW_TAG_subprogram DIEs

[clayborg]

lib/DebugInfo/DWARF/DWARFVerifier.cpp

283

These are sorted ranges since the data is in a std::set. You can't have 1 overlap with 3 without 1 and 2 overlapping and 2 and 3 overlapping.

351

Sure thing.

375

That is exactly what ParentVRI is? The class DieRangeInfo maintains this info. I didn't use one for the CU, but I use it for everything else. What am I missing here?

376

It has now been inlined.

392

We now check for overlapping functions on the fly and overlapping lexical blocks and inlined subroutines on the fly.

[clayborg]

So now we have DIERangeInfo:

struct DieRangeInfo {
  DWARFDie Die;
  DWARFAddressRangesVector Ranges;
};

And a class to track ranges that can't overlap:

struct NonOverlappingRanges {
  std::set<DieRangeInfo> NonOverlappingRanges;
};

We store a DieRangeInfo for the compile unit name UnitRI and a NonOverlappingRanges instance named AllFunctionRanges in the Verify instance. Then we pass a "const DieRangeInfo &ParentRI" and a "NonOverlappingRanges &NRO" to verifyDIE. Since the parent range info and DIE can't change, they should be in 1 class (DieRangeInfo) and the non overlapping address ranges are in a modifiable in/out argument. This effectively implements what you asked for David. We also do checking on the fly in all cases.

[clayborg]

Fixed the core issues David was asking for. Main differences are:

• Now have SortedRanges class that guarantees ranges are sorted instead of relying on DWARFAddressRangesVector being sorted
• SortedRanges can report if there are invalid ranges in a DWARFAddressRangesVector and if there are overlaps during insert
• DieRangeInfo now uses SortedRanges instead of DWARFAddressRangesVector
• DieRangeInfo now reports errors which really cleans up the DWARFVerifier::verifyDie() function
• NonOverlappingRanges now can report errors when DIEs have overlapping address ranges which really cleans up the DWARFVerifier::verifyDie() function

[clayborg]

Remove unused DWARFVerifier::verifyNoRangesOverlap() function.

[clayborg]

ping

[dblaikie]

I can work up a prototype/example of what I'm suggesting, if you like - but here are some comments to give the basic idea. It still seems to me like there are more parts to this than necessary.

include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h

25–40 ↗

(On Diff #98310)

Might be tidier to make this a struct with a couple of functions:

struct DWARFRange {
  uint64_t Start;
  uint64_t End;
  bool intersects(const DWARFRange&);
  bool contains(const DWARFRange&);
}

That way the function names don't have to repeat the "DWARFRange" prefix.

43 ↗

(On Diff #98310)

I don't think this typedef adds a lot now - the original name is shorter & more descriptive (since it makes it clear it's just a plain old std::vector, not anything fancier)

46–63 ↗

(On Diff #98310)

Surprised to see these O(N^2) algorithms still here - if the ranges are always sorted first, the pairwise-style algorithm you implemented for overlap within a single range should be usable on these cases I would think. A bit trickier to walk the two lists together, but do-able.

I wonder if LLVM's IntervalMap would be usable here (maps an integer range to something - in this case to a DWARFDie). If it provides an error message or a failable insert - you could walk each element of a range, adding them to the IntervalMap - if they ever collide, error out. Otherwise you have a compact/efficient representation of the ranges you can quickly look up/insert into...

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

30–46

Does this class need to exist? I'm not sure it adds much of an improved abstraction boundary compared to being an implementation detail of DieRangeInfo?

48–74

I'm surprised there's a need for both DieRangeInfo and NonOverlappingRanges - it seems like DieRangeInfo should/could do all the non-overlapping testing too, no?

52

I think the "Die(), Ranges()" is redundant/unnecessary & probably best to write this as:

DieRangeInfo() = default;

lib/DebugInfo/DWARF/DWARFVerifier.cpp

76–104

Ah, here's the other version of "intersects" - it's an "insert and test intersection". I'd expect to only need this version - not the other one that does the O(N^2) set of comparisons. Is that practical? (to only have the one version)

I also wouldn't be terribly sad if ranges were sorted first - that way they'd be quick to compare with the parent range and with the sibling ranges (O(N Log(N)) to sort, then two O(N) walks - one for the parent and one for the siblings. Rather than two O(N log(N)) walks - I mean it's still O(N log(N)) in the end... I don't mind much either way)

115–118

This diagnostic won't include both the DIEs that overlap, which seems difficult for the user. (test case should test this - that both the DIEs are dumped for cases where an error is about two DIEs)

202–218

Why are there 3 different things a subprogram is being added to/processed by/errored by?

I'd have expected only one - the outer/current CU. It'd also need to initialize the current SP (which would have to be a stack of some kind, I guess (like the patch I provided last week), to handle the nested SP definition case) for lexical scopes to compare against/be added to.

208–209

I don't think the CU DIE needs a special case for the diagnostic, does it? I would've expected the diagnostics to be in the RangeInfo & not need to be customized per caller.

210–213

The non-empty check I would guess isn't needed here ("reportErrorIfNotContained" seems like it'd be trivially true if the range is empty - it couldn't possibly be not contained in anything)

215–216

Why would all functions need to be compared? I would expect that functions would be compared to their enclosing CU - if all CUs are not overlapping and all functions are contained within their CU's range then no function could be overlapping (in the same way that if all lexical scopes are contained within their parent, and their parents are non-overlapping (eg: different, non-overlapping functions) then such a pair of lexical scopes couldn't overlap)

223–239

Also here, I wouldn't expect 3 different cases (RI, ParentRI, and NOR) - I'd expect one, maybe two but hopefully abstracted into a single operation I think - "to the current relevant scope add this DIE - which will retrieve its range, check it for local validity, check it doesn't overlap with any siblings in the current scope and is contained in the parent".

[clayborg]

• Created a struct named DWARFRange and test it
• Move all contains and intersects logic into DWARFRange and DieRangeInfo
• Create a new DWARFVerify::DIEInfo that contains a DieRangeInfo and a NonOverlappingRanges.
• Simplify verifyDIE as requested to do everything in one place
• Modified DieRangeInfo::contains and DieRangeInfo::intersects to be faster
• Added tests for DieRangeInfo::contains and DieRangeInfo::intersects
• Removed the SortedRanges class and moved it into DieRangeInfo

[dblaikie]

Looking pretty good - thanks for all your patience!

A few places this could be further tidied up/streamlined - and if you can do anything to pare down the unit tests based on equivalence classes/partitions, that'd be great, it looks like more tests/cases than I'd expect, given the code under test.

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

48

Usually any operator overload that can be a non-member should be (it can be a friend, though in this instance even that's not necessary)

49–51

One quick way to implement this is:

return std::tie(Start, End) < std::tie(RHS.Start, RHS.End);

83

Does llvm's IntervalMap make sense here? Keeping an IntervalMap from the address range to the DIE that occupies that range seems good & less code (no need to write a custom op<, etc) I think... probably.

lib/DebugInfo/DWARF/DWARFVerifier.cpp

38–52

Wouldn't the presence of overlapping ranges in the Ranges list mess with the correctness of other algorithms (like intersection) - you might then have to search arbitrarily far back in the range list from the lower_bound because an earlier range might be longer and extend past the current one?

This seems unreliable and may be better to error on an invalid range and then not process it further? (not produce follow-on errors for intersections, etc)? (also may be better in general rather than producing a bunch of related errors about an invalid range - errors about it overlapping with many things, being outside the parent raneg, etc)

Not sure.

63–73

Seems like a job for erase/remove, maybe:

UnsortedRanges.erase(llvm:::remove_if(UnsortedRanges, [&](const std::pair<uint64_t, uint64_t> &R) { if (R.first < R.second) return false; if (R.first > R.second) HasErrors = true; return false; } , UnsortedRanges.end());

(appropriately indented, etc)

125–135

This and contains still seems more expensive (O(N log(N))) than I'd expect - it should be doable without too much complexity, linearly - by walking both sorted lists at the same time.

Ah, I see, by moving the starting point forward it's a smaller search space - but still not as efficient, I think, as searching linearly from the start of that range, so maybe replacing lower_bound with std::find with a comparator of some kind?

Similar idea for 'contains' above.

140–154

Can probably implement this with:

return std::tie(Ranges, Die.getOffset()) < std::tie(RHS.Ranges, RHS.Die.getOffset());

Also - does this need to support < comparison of two entities with exactly the same ranges but a different DIE? When/where does that come up/what behavior is desirable there?

159–166

Probably invert this to reduce indentation:

if (contains(RI))
  return false;
OS << Error;
...

172–174

Drop braces on single line ifs, and probably change this code to:

bool HasErrors = DieRI.extractRangesAndReportErrors(OS);

179–181

Why is the CU a special case here? (a subprogram can have ranges in a CU with no ranges, but a lexical scope can't have ranges in a subprogram without ranges - is that the condition? I'm not sure why that's the case - could you explain it?)

182–189

Why is there a special case for CU DIEs here? I'd expect the same error message and behavior regardless of whether it's a CU or not. The DIEs should be dumped and that'll make it clear to the user what kind of DIE it is without needing a different error message.

203

Invert to reduce indentation:

if (RangeSet.empty())
  return nullptr;

204–211

Might be worth a couple of comments explaining the conditions these two cases cover.

205–206

Could collapse these together:

if (Iter != RangeSet.end() && Iter->intersects(RI))

209–211

Could collapse these two together:

if (Iter != RangeSet.begin() && (--Iter)->intersects(RI))

Though maybe that doesn't help readability - not sure.

221–224

Probably makes sense for "GetOverlappingRangeInfo" to return just the DWARFDie (assuming it has a null/empty state that's boolean testable) rather than something more complicated - maybe simpler name too "GetOverlappingDIE" I guess.

& you can collapse the declaration:

if (DWARFDie Die = GetOverlappingDie(RI)) {
  ...

229

If you use an IntervalMap, might be worth seeing if you could do an insert+retrieve previous value (but that's probably too niche - since an insert into the IntervalMap could cover multiple previous values). This would avoid GetOverlappingRangeInfo doing similar/the same work as 'insert'.

242–246

Where does the cross-CU checking happen (ensuring no two CUs ranges overlap). I'd expect it to happen here, but don't see it?

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

2508

/might/ be able to simplify these lines by omitting the "DWARFVerifier::DIERangeInfo(" ")" part (& just leaving the {} init) - you might need to add an extra set of {} around it instead, I'm not sure.

[clayborg]

• Address all of David's previous issues

[dblaikie]

lib/DebugInfo/DWARF/DWARFVerifier.cpp

60

Perhaps this should go in 'insert' which is only called from this function anyway?

70

Guessing this should be 'return true;' - otherwise no elements will ever be removed?

Is that tested? (what happens if elements aren't removed here? what would that do to the rest of the code/validation?)

81–84

Only dumps one of the two DIEs that are relevant to this situation. It should probably dump both - and at least some test coverage for this to demonstrate the usability of dumping two DIEs, etc.

125–131

This idiom seems to have appeared in a few places (similar code in DieRangeInfo::insert & sort of similar stuff in 'contains') any chance of factoring that out?

125–135

Still wondering about this ^

140–154

Still curious about this: does this need to support < comparison of two entities with exactly the same ranges but a different DIE? When/where does that come up/what behavior is desirable there?

156–160

Why is a rangeless CU a special case/acceptable here, in comparison to say, a rangeless subprogram or lexical_block?

179

grammar/missing word "Iter <something here> might the address range that follows RI"?

206

Roll this into its one use:

switch (Die.getTag())

213–218

Where, if anywhere, does the case of overlapping CUs get handled? That should be an error, right?

215–216

If the RI is the only part of UnitDI that's used - maybe only have the RI in the first place here?

But maybe the NOR in UnitDI should be used - that would catch cases where two CUs overlap with each other, right? & then all 3 cases (compile_unit, subprogram, lexical_block) would look quite the same, I think, just operating on different DieInfo objects?

225–228

Inconsistent bracing (some blocks in this switch have braces, some don't, for essentially the same code)

[clayborg]

• Added an assert to catch if we don't remove overlapping or invalid ranges that catches the issue where the lambda was returning false instead of true and modified DieRangeInfo::insert() to assert as mentioned.
• fixed ::contains and ::intersects to use a more efficient traversal.
• fixed all other issues

[dblaikie]

lib/DebugInfo/DWARF/DWARFVerifier.cpp

60

Still curious about this

70

While adding an assert is useful - I'm still curious about what would go wrong if/when this wasn't removing the elements it's intended to? Is this purely a performance improvement (if so, it's fine as-is, with the assert). Does this change behavior at all, in a way that matters/is intentional? (eg: does it make follow-on error messages better?) If so, that behavior should be tested.

81–84

Still curious about this

125–131

Still curious about this - this code and DieRangeInfo::insert (& similar, though not identical code for 'contains' tests) were duplicate, and now this code is fixed but DieRangeInfo::insert is not. Please refactor so the code's written once, not twice to avoid this kind of divergence/duplication/repeated work.

131–133

I'd probably skip this - the algorithm's linear anyway & pretty tidy without it. I suppose it catches the common case where they don't overlap at all, but might be better done another way (range lists could keep their max/min bound & shortcircuit here, etc)

135–141

This looks more expensive than what I had in mind - I figured a linear search to find the item, then testing 'intersects', rather than testing intersects on every item along the way.

140–154

Still curious about this

156–160

Still curious about this

176–177

Probably "emit (or report, to match the function name) an error" ("make an error" sounds curious, like maybe it returns an llvm::Error (though even that I'd expect to be described as "returns an Error") that the caller is responsible for emitting to the user, etc)

183

DWARFDie is already boolean testable - does it need to be wrapped in Optional? Or could this return an invalid DWARFDie to signal the "no overlap" case?

213–218

Still wondering about this.

215–216

Still curious about this

[clayborg]

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

46

Yes this can be moved into DieRangeInfo

52

Will change it.

74

We need both. NonOverlappingRanges keeps a set of "DIE + ranges" so we can tell which DIE had ranges that don't overlap. DieRangeInfo is ranges for a specific Die. For all function address ranges (AllFunctionRanges below), we need to know which DIE the range came from.

83

I don't it does. Looking at the IntervalMap::insert() function headerdoc:

/// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
/// It is assumed that no key in the interval is mapped to another value, but
/// overlapping intervals already mapped to y will be coalesced.

So it is says it can have no keys mapped to different values, and we are watching for possible overlaps and possible DIEs that have the same range.

lib/DebugInfo/DWARF/DWARFVerifier.cpp

52

Longer ranges will appear at the end since the comparison does both the Start and End so this should work right?

60

DieRangeInfo::extractRangesAndReportErrors() is called from two places. This function calls DWARFVerifier::DieRangeInfo::insert() and also the DieRangeInfo constructor calls it for testing.

70

It didn't affect the tests because DWARFVerifier::DieRangeInfo::insert() was removing them when they were inserted. I have removed the check from insert and added an assert that will fire and catch the above error when the final "return false;" is in, but succeeds when it is true. The DWARFVerifier::DieRangeInfo::insert() is used for testing with the DieRangeInfo constructor and those ranges must to be valid (sorted and non overlapping) and the assert that was added enforces that.

84

Again, this is only checking if the ranges within 1 DIE overlap while it is adding these ranges. Only 1 die needs to be printed.

118

This is detecting ranges within a Die that overlap or are invalid and the one and only Die is dumped below. This isn't checking if multiple Dies overlap, that is elsewhere. I do need to add a test for this though

131

The logic is simpler now, let me know if it still needs to be broken out.

154

Yes, we need to find errors if two DIEs have the same low/high PC.

160

rangless subprograms are fine, but not rangeless subprograms with ranged lexical blocks. So:

1 - Ranged CU with ranged subprogram -> OK as long as contained
2 - Rangless CU with rangeless subprogram -> OK
3 - Ranged CU with rangeless subprogram -> OK

1 - Rangless subprogram/block/inlined with contained rangeless block/inlined -> OK
2 - Rangless subprogram/block/inlined with contained ranged block/inlined -> bad
3 - Ranged subprogram/block/inlined with contained ranged block/inlined -> OK as long as contained

#2 is where they differ

181

You got it right. A CU may or may not have ranges and if it doesn't we don't need to check if DW_TAG_subprogram DIEs are contained. Lexical blocks and inline functions must be contained in parent.

189

One error message will be fine, I'll change it.

209

DW_TAG_subprogram DIEs are always direct children of the CU DIE so this special case is needed. We are always passing a parent range info in ParentRI, but that might be a DW_TAG_class_type for a DW_TAG_subprogram. So for DW_TAG_subprogram we always check against the CU and only check against the CU if it has ranges. For blocks we always check if the block has ranges, then the parent must have the ranges. So this needs to stay.

213

It is ok for the CU to be empty, not when you have a DW_TAG_lexical_block. If it has address range(s), then the parent must contain it. Not true for compile units. So the empty check is saying "it is ok if you just have a DW_AT_low_pc". If the CU has a low/high PC or a DW_AT_ranges, then it must contain all functions.

216

NOR is used to detect any functions overlapping. So the UnitDI.RI is used to track the Unit DIE and its ranges so each subprogram in the CU can verify it is in the CU ranges if the CU has range(s), and the NOR is never cleared across all CUs so we can verify that no functions overlap within a CU. So this is already happening.

217

This is the easiest way to do it.

I would expect that functions would be compared to their enclosing CU - if all CUs are not overlapping and all functions are contained within their CU's range then no function could be overlapping (in the same way that if all lexical scopes are contained within their parent, and their parents are non-overlapping (eg: different, non-overlapping functions) then such a pair of lexical scopes couldn't overlap)

So what if a CU has no ranges? Then we need to actually make and keep a list of all CUs and then compare them at the end. And we would still need to tell which DIEs overlapped in the end. This is easier and cleaner IMHO.

218

It checks 3 things:
1 - if the DIE has bad ranges or ranges that overlap within itself
2 - if the CU has ranges, make sure its ranges are in them
3 - make sure that the function doesn't overlap globally with any other function's address range

This seems pretty simple.

219

overlapping CUs happens below. Each DW_TAG_subprogram will check if it is in the UnitDI.RI's ranges and also add itself to the UnitDI.NOR to verify no functions globally overlap.

225–226

The above two lines need to be removed.

239

Sounds good.

246

The "NOR" in the UnitDI never gets cleared, so it is doing the cross CU checking. UnitDI.RI gets updated with the current CU info, but UnitDI.NOR never gets cleared.

[clayborg]

Sorry I hadn't posted my reply comments, just did that. Will look at your new comments and answer as needed.

[clayborg]

lib/DebugInfo/DWARF/DWARFVerifier.cpp

60

This should be answered above, let me know if it isn't?

141

I don't follow.

[clayborg]

I believe this patch is close enough for an initial checkin. We can iterate on it once it is in? We seem to be down to how to best iterate over ranges in ranges for intersect and for contains. Let me know your thoughts. Or feel free to commandeer this and check it in as you want it...

include/llvm/DebugInfo/DWARF/DWARFDie.h

inline bool operator==(const DWARFDie &LHS, const DWARFDie &RHS) {
   return LHS.getDebugInfoEntry() == RHS.getDebugInfoEntry() &&
       LHS.getDwarfUnit() == RHS.getDwarfUnit();
 }
 
 inline bool operator!=(const DWARFDie &LHS, const DWARFDie &RHS) {
   return !(LHS == RHS);
 }
 
+inline bool operator<(const DWARFDie &LHS, const DWARFDie &RHS) {
+  return LHS.getOffset() < RHS.getOffset();
+}
+
 class DWARFDie::iterator : public iterator_facade_base<iterator,
                                                       std::forward_iterator_tag,
                                                       const DWARFDie> {
   DWARFDie Die;
   void skipNull() {
     if (Die && Die.isNULL())
       Die = DWARFDie();
   }

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

 //===- DWARFVerifier.h ----------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H
 #define LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H
 
+#include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
+#include "llvm/DebugInfo/DWARF/DWARFDie.h"
+
 #include <cstdint>
 #include <map>
 #include <set>
+#include <vector>
 
 namespace llvm {
 class raw_ostream;
 struct DWARFAttribute;
 class DWARFContext;
 class DWARFDie;
 class DWARFUnit;
 
 /// A class that verifies DWARF debug information given a DWARF Context.
 class DWARFVerifier {
+public:
+  struct DWARFRange {
+    uint64_t Start;
+    uint64_t End;
+    DWARFRange(uint64_t S, uint64_t E) : Start(S), End(E) {}
+    /// Returns true if [Start, End) intersects with [RHS.Start, RHS.End).
+    bool intersects(const DWARFRange &RHS) const {
+      // Empty ranges can't intersect.
+      if (Start == End || RHS.Start == RHS.End)
+        return false;
+      return (Start < RHS.End) && (End > RHS.Start);
+    }
+    /// Returns true if [Start, End) fully contains [RHS.Start, RHS.End).
+    bool contains(const DWARFRange &RHS) const {
+      if (Start <= RHS.Start && RHS.Start < End)
+        return Start < RHS.End && RHS.End <= End;
+      return false;
+    }
+  };
+
+  /// A class that keeps the address range information for a single DIE.
+  struct DieRangeInfo {
+    DWARFDie Die;
+    /// Sorted address ranges.
+    std::vector<DWARFRange> Ranges;
+    DieRangeInfo() = default;
+    /// Constructor used for unit testing.
+    DieRangeInfo(const DWARFAddressRangesVector &R) { insert(R); }
+    /// Return true if ranges in this object contains all ranges within RHS.
+    bool contains(const DieRangeInfo &RHS) const;
+    /// Return true if any ranges in RHS overlap with ranges in this object.
+    bool intersects(const DieRangeInfo &RHS) const;
+    void dump(raw_ostream &OS) const;
+    /// Extract address ranges from the Die in this object and return true if
+    /// there are errors in the ranges.
+    bool extractRangesAndReportErrors(raw_ostream &OS);
+    /// Return true if this object doesn't fully contain the ranges in RI
+    /// and report errors to the stream.
+    bool reportErrorIfNotContained(raw_ostream &OS, const DieRangeInfo &RI,
+                                   const char *Error) const;
+    /// Inserts the unsorted ranges and returns true if errors were found
+    /// during insertion
+    bool insert(const DWARFAddressRangesVector &UnsortedRanges);
+    
+    std::vector<DWARFRange>::const_iterator findRange(const DWARFRange &R) const {
+      auto Begin = Ranges.begin();
+      auto Iter = std::upper_bound(Begin, Ranges.end(), R);
+      if (Iter != Begin)
+        --Iter;
+      return Iter;
+    }
+  };
+
+  /// A class that ensures that no two DieRangeInfo's overlap.
+  struct NonOverlappingRanges {
+    std::set<DieRangeInfo> RangeSet;
+
+    /// Returns a valid DWARFDie object if a DIE overlaps with any ranges in
+    /// RI, or an invalid DWARFDie if no other DIEs overlap.
+    DWARFDie GetDieThatOverlapsWithAnyRange(const DieRangeInfo &RI) const;
+
+    bool insertAndReportErrors(raw_ostream &OS, const DieRangeInfo &RI);
+  };
+
+  /// A class the keeps information for a DIE that contains child DIEs whose
+  /// address ranges must be contained within its ranges and whose direct
+  /// children that have address ranges must not overlap.
+  struct DieInfo {
+    DieRangeInfo RI;
+    NonOverlappingRanges NOR;
+    /// Returns true if an error was found when inserting Die.
+    bool addContainedDieAndReportErrors(raw_ostream &OS, DieRangeInfo &DieRI);
+  };
+
+private:
   raw_ostream &OS;
   DWARFContext &DCtx;
+  DieInfo UnitDI;
   /// A map that tracks all references (converted absolute references) so we
   /// can verify each reference points to a valid DIE and not an offset that
   /// lies between to valid DIEs.
   std::map<uint64_t, std::set<uint32_t>> ReferenceToDIEOffsets;
+
   uint32_t NumDebugInfoErrors;
   uint32_t NumDebugLineErrors;
 
+  /// Verifies the a DIE's tag and gathers information about all DIEs.
+  ///
+  /// This function currently checks for:
+  /// - Checks DW_TAG_compile_unit address range(s)
+  /// - Checks DW_TAG_subprogram address range(s) and if the compile unit
+  ///   has ranges, verifies that its address range is fully contained in
+  ///   the compile unit ranges. Also adds the functions address range info
+  ///   to AllFunctionDieRangeInfos to look for functions with overlapping
+  ///   ranges after all DIEs have been processed.
+  /// - Checks that DW_TAG_lexical_block and DW_TAG_inlined_subroutine DIEs
+  ///   have address range(s) that are fully contained in their parent DIEs
+  ///   address range(s).
+  ///
+  /// \param Die          The DWARF DIE to check
+  /// \param ParantDI     The parent DIE's range and overlap information.
+  void verifyDie(const DWARFDie &Die, DieInfo &ParentDI);
+
   /// Verifies the attribute's DWARF attribute and its value.
   ///
   /// This function currently checks for:
   /// - DW_AT_ranges values is a valid .debug_ranges offset
   /// - DW_AT_stmt_list is a valid .debug_line offset
   ///
   /// @param Die          The DWARF DIE that owns the attribute value
   /// @param AttrValue    The DWARF attribute value to check
public:
   ///
   /// Any errors are reported to the stream that was this object was
   /// constructed with.
   ///
   /// @return True if the .debug_line verifies successfully, false otherwise.
   bool handleDebugLine();
 };
 
+static inline bool operator<(const DWARFVerifier::DWARFRange &LHS,
+                             const DWARFVerifier::DWARFRange &RHS) {
+  return std::tie(LHS.Start, LHS.End) < std::tie(RHS.Start, RHS.End);
+}
+
+static inline bool operator<(const DWARFVerifier::DieRangeInfo &LHS,
+                             const DWARFVerifier::DieRangeInfo &RHS) {
+  return std::tie(LHS.Ranges, LHS.Die) < std::tie(RHS.Ranges, RHS.Die);
+}
+
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARF_DWARFCONTEXT_H

lib/DebugInfo/DWARF/DWARFContext.cpp

 
 DWARFDie DWARFContext::getDIEForOffset(uint32_t Offset) {
   parseCompileUnits();
   if (auto *CU = CUs.getUnitForOffset(Offset))
     return CU->getDIEForOffset(Offset);
   return DWARFDie();
 }
 
-namespace {
-  
-class Verifier {
-  raw_ostream &OS;
-  DWARFContext &DCtx;
-public:
-  Verifier(raw_ostream &S, DWARFContext &D) : OS(S), DCtx(D) {}
-  
-  bool HandleDebugInfo() {
-    bool Success = true;
-    // A map that tracks all references (converted absolute references) so we
-    // can verify each reference points to a valid DIE and not an offset that
-    // lies between to valid DIEs.
-    std::map<uint64_t, std::set<uint32_t>> ReferenceToDIEOffsets;
-
-    OS << "Verifying .debug_info...\n";
-    for (const auto &CU : DCtx.compile_units()) {
-      unsigned NumDies = CU->getNumDIEs();
-      for (unsigned I = 0; I < NumDies; ++I) {
-        auto Die = CU->getDIEAtIndex(I);
-        const auto Tag = Die.getTag();
-        if (Tag == DW_TAG_null)
-          continue;
-        for (auto AttrValue : Die.attributes()) {
-          const auto Attr = AttrValue.Attr;
-          const auto Form = AttrValue.Value.getForm();
-          switch (Attr) {
-            case DW_AT_ranges:
-              // Make sure the offset in the DW_AT_ranges attribute is valid.
-              if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
-                if (*SectionOffset >= DCtx.getRangeSection().Data.size()) {
-                  Success = false;
-                  OS << "error: DW_AT_ranges offset is beyond .debug_ranges "
-                  "bounds:\n";
-                  Die.dump(OS, 0);
-                  OS << "\n";
-                }
-              } else {
-                Success = false;
-                OS << "error: DIE has invalid DW_AT_ranges encoding:\n";
-                Die.dump(OS, 0);
-                OS << "\n";
-              }
-              break;
-            case DW_AT_stmt_list:
-              // Make sure the offset in the DW_AT_stmt_list attribute is valid.
-              if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
-                if (*SectionOffset >= DCtx.getLineSection().Data.size()) {
-                  Success = false;
-                  OS << "error: DW_AT_stmt_list offset is beyond .debug_line "
-                  "bounds: "
-                  << format("0x%08" PRIx32, *SectionOffset) << "\n";
-                  CU->getUnitDIE().dump(OS, 0);
-                  OS << "\n";
-                }
-              } else {
-                Success = false;
-                OS << "error: DIE has invalid DW_AT_stmt_list encoding:\n";
-                Die.dump(OS, 0);
-                OS << "\n";
-              }
-              break;
-              
-            default:
-              break;
-          }
-          switch (Form) {
-            case DW_FORM_ref1:
-            case DW_FORM_ref2:
-            case DW_FORM_ref4:
-            case DW_FORM_ref8:
-            case DW_FORM_ref_udata: {
-              // Verify all CU relative references are valid CU offsets.
-              Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
-              assert(RefVal);
-              if (RefVal) {
-                auto DieCU = Die.getDwarfUnit();
-                auto CUSize = DieCU->getNextUnitOffset() - DieCU->getOffset();
-                auto CUOffset = AttrValue.Value.getRawUValue();
-                if (CUOffset >= CUSize) {
-                  Success = false;
-                  OS << "error: " << FormEncodingString(Form) << " CU offset "
-                  << format("0x%08" PRIx32, CUOffset)
-                  << " is invalid (must be less than CU size of "
-                  << format("0x%08" PRIx32, CUSize) << "):\n";
-                  Die.dump(OS, 0);
-                  OS << "\n";
-                } else {
-                  // Valid reference, but we will verify it points to an actual
-                  // DIE later.
-                  ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
-                }
-              }
-              break;
-            }
-            case DW_FORM_ref_addr: {
-              // Verify all absolute DIE references have valid offsets in the
-              // .debug_info section.
-              Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
-              assert(RefVal);
-              if (RefVal) {
-                if(*RefVal >= DCtx.getInfoSection().Data.size()) {
-                  Success = false;
-                  OS << "error: DW_FORM_ref_addr offset beyond .debug_info "
-                        "bounds:\n";
-                  Die.dump(OS, 0);
-                  OS << "\n";
-                } else {
-                  // Valid reference, but we will verify it points to an actual
-                  // DIE later.
-                  ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
-                }
-              }
-              break;
-            }
-            case DW_FORM_strp: {
-              auto SecOffset = AttrValue.Value.getAsSectionOffset();
-              assert(SecOffset); // DW_FORM_strp is a section offset.
-              if (SecOffset && *SecOffset >= DCtx.getStringSection().size()) {
-                Success = false;
-                OS << "error: DW_FORM_strp offset beyond .debug_str bounds:\n";
-                Die.dump(OS, 0);
-                OS << "\n";
-              }
-              break;
-            }
-            default:
-              break;
-          }
-        }
-      }
-    }
-
-    // Take all references and make sure they point to an actual DIE by
-    // getting the DIE by offset and emitting an error
-    OS << "Verifying .debug_info references...\n";
-    for (auto Pair: ReferenceToDIEOffsets) {
-      auto Die = DCtx.getDIEForOffset(Pair.first);
-      if (Die)
-        continue;
-      Success = false;
-      OS << "error: invalid DIE reference " << format("0x%08" PRIx64, Pair.first)
-         << ". Offset is in between DIEs:\n";
-      for (auto Offset: Pair.second) {
-        auto ReferencingDie = DCtx.getDIEForOffset(Offset);
-        ReferencingDie.dump(OS, 0);
-        OS << "\n";
-      }
-      OS << "\n";
-    }
-    return Success;
-  }
-
-  bool HandleDebugLine() {
-    std::map<uint64_t, DWARFDie> StmtListToDie;
-    bool Success = true;
-    OS << "Verifying .debug_line...\n";
-    for (const auto &CU : DCtx.compile_units()) {
-      uint32_t LineTableOffset = 0;
-      auto CUDie = CU->getUnitDIE();
-      auto StmtFormValue = CUDie.find(DW_AT_stmt_list);
-      if (!StmtFormValue) {
-        // No line table for this compile unit.
-        continue;
-      }
-      // Get the attribute value as a section offset. No need to produce an
-      // error here if the encoding isn't correct because we validate this in
-      // the .debug_info verifier.
-      if (auto StmtSectionOffset = toSectionOffset(StmtFormValue)) {
-        LineTableOffset = *StmtSectionOffset;
-        if (LineTableOffset >= DCtx.getLineSection().Data.size()) {
-          // Make sure we don't get a valid line table back if the offset
-          // is wrong.
-          assert(DCtx.getLineTableForUnit(CU.get()) == nullptr);
-          // Skip this line table as it isn't valid. No need to create an error
-          // here because we validate this in the .debug_info verifier.
-          continue;
-        } else {
-          auto Iter = StmtListToDie.find(LineTableOffset);
-          if (Iter != StmtListToDie.end()) {
-            Success = false;
-            OS << "error: two compile unit DIEs, "
-               << format("0x%08" PRIx32, Iter->second.getOffset()) << " and "
-               << format("0x%08" PRIx32, CUDie.getOffset())
-               << ", have the same DW_AT_stmt_list section offset:\n";
-            Iter->second.dump(OS, 0);
-            CUDie.dump(OS, 0);
-            OS << '\n';
-            // Already verified this line table before, no need to do it again.
-            continue;
-          }
-          StmtListToDie[LineTableOffset] = CUDie;
-        }
-      }
-      auto LineTable = DCtx.getLineTableForUnit(CU.get());
-      if (!LineTable) {
-        Success = false;
-        OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset)
-           << "] was not able to be parsed for CU:\n";
-        CUDie.dump(OS, 0);
-        OS << '\n';
-        continue;
-      }
-      uint32_t MaxFileIndex = LineTable->Prologue.FileNames.size();
-      uint64_t PrevAddress = 0;
-      uint32_t RowIndex = 0;
-      for (const auto &Row : LineTable->Rows) {
-        if (Row.Address < PrevAddress) {
-          Success = false;
-          OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset)
-             << "] row[" << RowIndex
-             << "] decreases in address from previous row:\n";
-
-          DWARFDebugLine::Row::dumpTableHeader(OS);
-          if (RowIndex > 0)
-            LineTable->Rows[RowIndex - 1].dump(OS);
-          Row.dump(OS);
-          OS << '\n';
-        }
-
-        if (Row.File > MaxFileIndex) {
-          Success = false;
-          OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset)
-             << "][" << RowIndex << "] has invalid file index " << Row.File
-             << " (valid values are [1," << MaxFileIndex << "]):\n";
-          DWARFDebugLine::Row::dumpTableHeader(OS);
-          Row.dump(OS);
-          OS << '\n';
-        }
-        if (Row.EndSequence)
-          PrevAddress = 0;
-        else
-          PrevAddress = Row.Address;
-        ++RowIndex;
-      }
-    }
-    return Success;
-  }
-};
-  
-} // anonymous namespace
-
 bool DWARFContext::verify(raw_ostream &OS, DIDumpType DumpType) {
   bool Success = true;
   DWARFVerifier verifier(OS, *this);
   if (DumpType == DIDT_All || DumpType == DIDT_Info) {
     if (!verifier.handleDebugInfo())
       Success = false;
   }
   if (DumpType == DIDT_All || DumpType == DIDT_Line) {

lib/DebugInfo/DWARF/DWARFVerifier.cpp

 //===- DWARFVerifier.cpp --------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/DWARF/DWARFVerifier.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
 #include "llvm/DebugInfo/DWARF/DWARFSection.h"
 #include "llvm/Support/raw_ostream.h"
 #include <map>
 #include <set>
 #include <vector>
 
 using namespace llvm;
 using namespace dwarf;
 using namespace object;
 
+bool DWARFVerifier::DieRangeInfo::insert(
+    const DWARFAddressRangesVector &UnsortedRanges) {
+  bool Error = false;
+  for (const auto &UR : UnsortedRanges) {
+    DWARFRange R(UR.first, UR.second);
+    assert(R.Start < R.End);
+    auto Begin = Ranges.begin();
+    auto End = Ranges.end();
+    auto InsertPos = std::lower_bound(Begin, End, R);
+    if (!Error) {
+      bool RangeOverlaps = false;
+      if (InsertPos != End) {
+        if (InsertPos->intersects(R))
+          RangeOverlaps = true;
+        else if (InsertPos != Begin) {
+          auto Iter = InsertPos - 1;
+          if (Iter->intersects(R))
+            RangeOverlaps = true;
+        }
+        if (RangeOverlaps) {
+          Error = true;
+        }
+      }
+      // Insert the range into our sorted list
+      Ranges.insert(InsertPos, R);
+    }
+  }
+  return Error;
+}
+
+bool DWARFVerifier::DieRangeInfo::extractRangesAndReportErrors(
+    raw_ostream &OS) {
+  Ranges.clear();
+  auto UnsortedRanges = Die.getAddressRanges();
+  bool HasErrors = false;
+
+  auto ErasePos =
+      remove_if(UnsortedRanges, [&](const std::pair<uint64_t, uint64_t> &R) {
+        if (R.first < R.second)
+          return false;
+        if (R.first > R.second)
+          HasErrors = true;
+        return true;
+      });
+  UnsortedRanges.erase(ErasePos, UnsortedRanges.end());
+
+  if (HasErrors)
+    OS << "error: invalid range in DIE:\n";
+
+  if (insert(UnsortedRanges)) {
+    OS << "error: ranges in DIE overlap:\n";
+    HasErrors = true;
+  }
+  if (HasErrors) {
+    Die.dump(OS, 0);
+    OS << "\n";
+  }
+  return HasErrors;
+}
+
+void DWARFVerifier::DieRangeInfo::dump(raw_ostream &OS) const {
+  OS << format("0x%08" PRIx32, Die.getOffset()) << ":";
+  for (const auto &R : Ranges)
+    OS << " [" << format("0x%" PRIx64, R.Start) << "-"
+       << format("0x%" PRIx64, R.End) << ")";
+  OS << "\n";
+}
+
+bool DWARFVerifier::DieRangeInfo::contains(const DieRangeInfo &RHS) const {
+  // Both list of ranges are sorted so we can make this fasts
+  if (Ranges.empty() || RHS.Ranges.empty())
+    return false;
+  // Since the ranges are sorted we can advance where we start searching with
+  // this object's ranges as we traverse RHS.Ranges.
+  
+  auto End = Ranges.end();
+  auto Iter = findRange(RHS.Ranges.front());
+  // Now lineary walk the ranges in this object and see if they contain each
+  // ranges from RHS.Ranges.
+  for (const auto &R : RHS.Ranges) {
+    while (Iter != End) {
+      if (Iter->contains(R))
+        break;
+      ++Iter;
+    }
+    if (Iter == End)
+      return false;
+  }
+  return true;
+}
+
+bool DWARFVerifier::DieRangeInfo::intersects(const DieRangeInfo &RHS) const {
+  if (Ranges.empty() || RHS.Ranges.empty())
+    return false;
+
+  auto End = Ranges.end();
+  auto Iter = findRange(RHS.Ranges.front());
+  for (const auto &R : RHS.Ranges) {
+    if (R.End <= Iter->Start)
+      continue;
+    while (Iter != End) {
+      if (Iter->intersects(R))
+        return true;
+      ++Iter;
+    }
+  }
+  return false;
+}
+
+bool DWARFVerifier::DieRangeInfo::reportErrorIfNotContained(
+    raw_ostream &OS, const DieRangeInfo &RI, const char *Error) const {
+  if (contains(RI))
+    return false;
+  OS << Error;
+  Die.dump(OS, 0);
+  RI.Die.dump(OS, 0);
+  OS << "\n";
+  return true;
+}
+
+bool DWARFVerifier::DieInfo::addContainedDieAndReportErrors(
+    raw_ostream &OS, DieRangeInfo &DieRI) {
+  bool HasErrors = DieRI.extractRangesAndReportErrors(OS);
+
+  // If this DIE has not valid ranges to check then we are done.
+  if (DieRI.Ranges.empty())
+    return HasErrors;
+
+  // Die has address ranges so we need to check that its address ranges are
+  // contained in this DieInfo's address ranges except if this is a compile
+  // unit that doesn't have address range(s).
+  bool IsCompileUnit = RI.Die.getTag() == DW_TAG_compile_unit;
+  bool CheckContains = !IsCompileUnit || !RI.Ranges.empty();
+
+  const char *Error = "error: DIE has a child DIE whose address ranges are not "
+                      "contained in its ranges:";
+  if (CheckContains && RI.reportErrorIfNotContained(OS, DieRI, Error))
+    HasErrors = true;
+
+  // Check if this range overlaps with any previous sibling ranges and emit an
+  // error if needed.
+  if (NOR.insertAndReportErrors(OS, DieRI))
+    HasErrors = true;
+  return HasErrors;
+}
+
+DWARFDie DWARFVerifier::NonOverlappingRanges::GetDieThatOverlapsWithAnyRange(
+    const DieRangeInfo &RI) const {
+  if (RangeSet.empty())
+    return DWARFDie();
+  auto Iter = RangeSet.lower_bound(RI);
+  // Since we are searching using lower_bound, Iter might contain the address
+  // range that follows RI, so we need to check it in case RI overlaps with the
+  // next range.
+  if (Iter != RangeSet.end() && Iter->intersects(RI))
+    return Iter->Die;
+  // We also need to check the previous range to ensure it doesn't overlap with
+  // this range.
+  if (Iter != RangeSet.begin() && (--Iter)->intersects(RI))
+    return Iter->Die;
+  return DWARFDie();
+}
+
+bool DWARFVerifier::NonOverlappingRanges::insertAndReportErrors(
+    raw_ostream &OS, const DieRangeInfo &RI) {
+  bool Error = false;
+  if (auto OverlappingDie = GetDieThatOverlapsWithAnyRange(RI)) {
+    OS << "error: DIEs have overlapping address ranges:\n";
+    OverlappingDie.dump(OS, 0);
+    RI.Die.dump(OS, 0);
+    OS << "\n";
+    Error = true;
+  }
+  RangeSet.insert(RI);
+  return Error;
+}
+
+void DWARFVerifier::verifyDie(const DWARFDie &Die, DieInfo &ParentDI) {
+  DieInfo DI;
+  DI.RI.Die = Die;
+  switch (Die.getTag()) {
+  case DW_TAG_null:
+    return;
+  case DW_TAG_compile_unit:
+    // Set the Unit DIE info.
+    UnitDI.RI.Die = Die;
+    if (UnitDI.RI.extractRangesAndReportErrors(OS))
+      ++NumDebugInfoErrors;
+    break;
+  case DW_TAG_subprogram:
+    //␐ Add the subprogram to the unit DIE and make it is contained.
+    if (UnitDI.addContainedDieAndReportErrors(OS, DI.RI))
+      ++NumDebugInfoErrors;
+    break;
+  case DW_TAG_lexical_block:
+  case DW_TAG_inlined_subroutine:
+    if (ParentDI.addContainedDieAndReportErrors(OS, DI.RI))
+      ++NumDebugInfoErrors;
+    break;
+  default:
+    break;
+  }
+  // Verify the attributes and forms.
+  for (auto AttrValue : Die.attributes()) {
+    verifyDebugInfoAttribute(Die, AttrValue);
+    verifyDebugInfoForm(Die, AttrValue);
+  }
+
+  for (DWARFDie Child : Die)
+    verifyDie(Child, DI);
+}
 void DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die,
                                              DWARFAttribute &AttrValue) {
   const auto Attr = AttrValue.Attr;
   switch (Attr) {
   case DW_AT_ranges:
     // Make sure the offset in the DW_AT_ranges attribute is valid.
     if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
       if (*SectionOffset >= DCtx.getRangeSection().Data.size()) {
         ++NumDebugInfoErrors;
         OS << "error: DW_AT_ranges offset is beyond .debug_ranges "
               "bounds:\n";
         Die.dump(OS, 0);
         OS << "\n";
       }
     } else {
       ++NumDebugInfoErrors;
       OS << "error: DIE has invalid DW_AT_ranges encoding:\n";
       Die.dump(OS, 0);
       OS << "\n";
     }
     break;
   case DW_AT_stmt_list:
     // Make sure the offset in the DW_AT_stmt_list attribute is valid.
     if (auto SectionOffset = AttrValue.Value.getAsSectionOffset()) {
       if (*SectionOffset >= DCtx.getLineSection().Data.size()) {
         ++NumDebugInfoErrors;
         OS << "error: DW_AT_stmt_list offset is beyond .debug_line "
               "bounds: "
            << format("0x%08" PRIx32, *SectionOffset) << "\n";
         Die.dump(OS, 0);
         OS << "\n";
       }
     } else {
       ++NumDebugInfoErrors;
       OS << "error: DIE has invalid DW_AT_stmt_list encoding:\n";
       Die.dump(OS, 0);
       OS << "\n";
     }
     break;
 
   default:
     break;
   }
 }
 
 void DWARFVerifier::verifyDebugInfoForm(const DWARFDie &Die,
                                         DWARFAttribute &AttrValue) {
   const auto Form = AttrValue.Value.getForm();
   switch (Form) {
   case DW_FORM_ref1:
   case DW_FORM_ref2:
   case DW_FORM_ref4:
   case DW_FORM_ref8:
   case DW_FORM_ref_udata: {
     // Verify all CU relative references are valid CU offsets.
     Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
if (RefVal) {
         // Valid reference, but we will verify it points to an actual
         // DIE later.
         ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
       }
     }
     break;
   }
   case DW_FORM_ref_addr: {
     // Verify all absolute DIE references have valid offsets in the
     // .debug_info section.
     Optional<uint64_t> RefVal = AttrValue.Value.getAsReference();
     assert(RefVal);
     if (RefVal) {
       if (*RefVal >= DCtx.getInfoSection().Data.size()) {
         ++NumDebugInfoErrors;
         OS << "error: DW_FORM_ref_addr offset beyond .debug_info "
               "bounds:\n";
         Die.dump(OS, 0);
         OS << "\n";
       } else {
         // Valid reference, but we will verify it points to an actual
         // DIE later.
         ReferenceToDIEOffsets[*RefVal].insert(Die.getOffset());
       }
     }
     break;
   }
   case DW_FORM_strp: {
     auto SecOffset = AttrValue.Value.getAsSectionOffset();
     assert(SecOffset); // DW_FORM_strp is a section offset.
     if (SecOffset && *SecOffset >= DCtx.getStringSection().size()) {
       ++NumDebugInfoErrors;
       OS << "error: DW_FORM_strp offset beyond .debug_str bounds:\n";
       Die.dump(OS, 0);
       OS << "\n";
     }
     break;
   }
   default:
     break;
   }
 }
 
 void DWARFVerifier::verifyDebugInfoReferences() {
   // Take all references and make sure they point to an actual DIE by
   // getting the DIE by offset and emitting an error
   OS << "Verifying .debug_info references...\n";
   for (auto Pair : ReferenceToDIEOffsets) {
     auto Die = DCtx.getDIEForOffset(Pair.first);
     if (Die)
       continue;
     ++NumDebugInfoErrors;
     OS << "error: invalid DIE reference " << format("0x%08" PRIx64, Pair.first)
        << ". Offset is in between DIEs:\n";
     for (auto Offset : Pair.second) {
       auto ReferencingDie = DCtx.getDIEForOffset(Offset);
       ReferencingDie.dump(OS, 0);
       OS << "\n";
     }
     OS << "\n";
   }
 }
 
 bool DWARFVerifier::handleDebugInfo() {
   NumDebugInfoErrors = 0;
   OS << "Verifying .debug_info...\n";
   for (const auto &CU : DCtx.compile_units()) {
-    unsigned NumDies = CU->getNumDIEs();
-    for (unsigned I = 0; I < NumDies; ++I) {
-      auto Die = CU->getDIEAtIndex(I);
-      const auto Tag = Die.getTag();
-      if (Tag == DW_TAG_null)
-        continue;
-      for (auto AttrValue : Die.attributes()) {
-        verifyDebugInfoAttribute(Die, AttrValue);
-        verifyDebugInfoForm(Die, AttrValue);
-      }
-    }
+    DieInfo DI;
+    DWARFDie Die = CU->getUnitDIE(/* ExtractUnitDIEOnly = */ false);
+    verifyDie(Die, DI);
   }
   verifyDebugInfoReferences();
   return NumDebugInfoErrors == 0;
 }
 
 void DWARFVerifier::verifyDebugLineStmtOffsets() {
   std::map<uint64_t, DWARFDie> StmtListToDie;
   for (const auto &CU : DCtx.compile_units()) {
     auto Die = CU->getUnitDIE();
     // Get the attribute value as a section offset. No need to produce an
     // error here if the encoding isn't correct because we validate this in
     // the .debug_info verifier.
     auto StmtSectionOffset = toSectionOffset(Die.find(DW_AT_stmt_list));
     if (!StmtSectionOffset)
       continue;
     const uint32_t LineTableOffset = *StmtSectionOffset;
     auto LineTable = DCtx.getLineTableForUnit(CU.get());
     if (LineTableOffset < DCtx.getLineSection().Data.size()) {
       if (!LineTable) {
         ++NumDebugLineErrors;
         OS << "error: .debug_line[" << format("0x%08" PRIx32, LineTableOffset)
            << "] was not able to be parsed for CU:\n";
         Die.dump(OS, 0);
         OS << '\n';
         continue;
       }
     } else {
       // Make sure we don't get a valid line table back if the offset is wrong.
       assert(LineTable == nullptr);
       // Skip this line table as it isn't valid. No need to create an error
       // here because we validate this in the .debug_info verifier.
       continue;
     }
     auto Iter = StmtListToDie.find(LineTableOffset);
     if (Iter != StmtListToDie.end()) {
       ++NumDebugLineErrors;
       OS << "error: two compile unit DIEs, "
          << format("0x%08" PRIx32, Iter->second.getOffset()) << " and "
          << format("0x%08" PRIx32, Die.getOffset())
          << ", have the same DW_AT_stmt_list section offset:\n";

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
+#include "llvm/DebugInfo/DWARF/DWARFVerifier.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/ObjectYAML/DWARFEmitter.h"
 #include "llvm/ObjectYAML/DWARFYAML.h"
 #include "llvm/Support/Dwarf.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/TargetSelect.h"
 #include "gtest/gtest.h"

 
 void VerifyError(DWARFContext &DwarfContext, StringRef Error) {
   SmallString<1024> Str;
   raw_svector_ostream Strm(Str);
   EXPECT_FALSE(DwarfContext.verify(Strm, DIDT_All));
   EXPECT_TRUE(Str.str().contains(Error));
 }
 
+void VerifySuccess(DWARFContext &DwarfContext) {
+  SmallString<1024> Str;
+  raw_svector_ostream Strm(Str);
+  EXPECT_TRUE(DwarfContext.verify(Strm, DIDT_All));
+}
+
 TEST(DWARFDebugInfo, TestDwarfVerifyInvalidCURef) {
   // Create a single compile unit with a single function that has a DW_AT_type
   // that is CU relative. The CU offset is not valid becuase it is larger than
   // the compile unit itself.
 
   const char *yamldata = R"(
     debug_str:
       - ''
TEST(DWARFDebugInfo, TestDwarfVerifyCUDontShareLineTable) {
   auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
   ASSERT_TRUE((bool)ErrOrSections);
   DWARFContextInMemory DwarfContext(*ErrOrSections, 8);
   VerifyError(DwarfContext, "error: two compile unit DIEs, 0x0000000b and "
                             "0x0000001f, have the same DW_AT_stmt_list section "
                             "offset:");
 }
 
+TEST(DWARFDebugInfo, TestDwarfVerifyCURangesIncomplete) {
+  // Create a single compile unit with a single function. The compile
+  // unit has a DW_AT_ranges attribute that doesn't fully contain the
+  // address range of the function. The verification should fail due to
+  // the CU ranges not containing all of the address ranges of all of the
+  // functions.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+    debug_abbrev:    
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:      
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_no
+        Attributes:      
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:      
+      - Length:          
+          TotalLength:     46
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:         
+          - AbbrCode:        0x00000001
+            Values:          
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000001500
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:          
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000000
+            Values:          
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  DWARFContextInMemory DwarfContext(*ErrOrSections, 8);
+  VerifyError(DwarfContext, "error: DIE has a child DIE whose address ranges "
+                            "are not contained in its ranges:");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyLexicalBlockRanges) {
+  // Create a single compile unit with a single function that has a lexical
+  // block whose address range is not contained in the function address range.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+      - Code:            0x00000003
+        Tag:             DW_TAG_lexical_block
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:
+      - Length:
+          TotalLength:     52
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000003
+            Values:
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002001
+          - AbbrCode:        0x00000000
+            Values:
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  DWARFContextInMemory DwarfContext(*ErrOrSections, 8);
+  VerifyError(DwarfContext, "error: DIE has a child DIE whose address ranges "
+                            "are not contained in its ranges:");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyOverlappingFunctionRanges) {
+  // Create a single compile unit with a two functions that have overlapping
+  // address ranges.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+      - foo
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:
+      - Length:
+          TotalLength:     55
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x0000000000000012
+              - Value:           0x0000000000001FFF
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  DWARFContextInMemory DwarfContext(*ErrOrSections, 8);
+  VerifyError(DwarfContext, "error: DIEs have overlapping address ranges:");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyOverlappingLexicalBlockRanges) {
+  // Create a single compile unit with a one function that has two lexical
+  // blocks with overlapping address ranges.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+    debug_abbrev:    
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:      
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_yes
+        Attributes:      
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+      - Code:            0x00000003
+        Tag:             DW_TAG_lexical_block
+        Children:        DW_CHILDREN_no
+        Attributes:      
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:      
+      - Length:          
+          TotalLength:     85
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:         
+          - AbbrCode:        0x00000001
+            Values:          
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:          
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000003
+            Values:          
+              - Value:           0x0000000000001100
+              - Value:           0x0000000000001300
+          - AbbrCode:        0x00000003
+            Values:          
+              - Value:           0x00000000000012FF
+              - Value:           0x0000000000001300
+          - AbbrCode:        0x00000000
+            Values:          
+          - AbbrCode:        0x00000000
+            Values:          
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  DWARFContextInMemory DwarfContext(*ErrOrSections, 8);
+  VerifyError(DwarfContext, "error: DIEs have overlapping address ranges:");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyInvalidDIERange) {
+  // Create a single compile unit with a single function that has an invalid
+  // address range where the high PC is smaller than the low PC.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+    debug_abbrev:    
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:      
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_no
+        Attributes:      
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:      
+      - Length:          
+          TotalLength:     34
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:         
+          - AbbrCode:        0x00000001
+            Values:          
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:          
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000000900
+          - AbbrCode:        0x00000000
+            Values:          
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  DWARFContextInMemory DwarfContext(*ErrOrSections, 8);
+  VerifyError(DwarfContext, "error: invalid range in DIE:");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyElidedDoesntFail) {
+  // Create a single compile unit with two functions: one that has a valid range
+  // and one whose low and high PC are the same. When the low and high PC are
+  // the same, this indicates the function was dead code stripped. We want to
+  // ensure that verification succeeds.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+      - elided
+    debug_abbrev:    
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:      
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_no
+        Attributes:      
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:      
+      - Length:          
+          TotalLength:     71
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:         
+          - AbbrCode:        0x00000001
+            Values:          
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:          
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000002
+            Values:          
+              - Value:           0x0000000000000012
+              - Value:           0x0000000000002000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000000
+            Values:          
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  DWARFContextInMemory DwarfContext(*ErrOrSections, 8);
+  VerifySuccess(DwarfContext);
+}
+  
+TEST(DWARFDebugInfo, TestDwarfRangesContains) {
+  DWARFVerifier::DWARFRange R(0x10, 0x20);
+
+  //----------------------------------------------------------------------
+  // Test ranges that start before R...
+  //----------------------------------------------------------------------
+  // Other range ends before start of R
+  ASSERT_FALSE(R.contains({0x0f, 0x10}));
+  // Other range end address is start of a R
+  ASSERT_FALSE(R.contains({0x0f, 0x11}));
+  // Other range end address is at and of R
+  ASSERT_FALSE(R.contains({0x0f, 0x20}));
+  // Other range end address is past end of R
+  ASSERT_FALSE(R.contains({0x0f, 0x40}));
+
+  //----------------------------------------------------------------------
+  // Test ranges that start at R's start address
+  //----------------------------------------------------------------------
+  // Ensure empty ranges doesn't match
+  ASSERT_FALSE(R.contains({0x10, 0x10}));
+  // 1 byte of Range
+  ASSERT_TRUE(R.contains({0x10, 0x11}));
+  // same as Range
+  ASSERT_TRUE(R.contains({0x10, 0x20}));
+  // 1 byte past Range
+  ASSERT_FALSE(R.contains({0x10, 0x21}));
+
+  //----------------------------------------------------------------------
+  // Test ranges that start inside Range
+  //----------------------------------------------------------------------
+  // empty in range
+  ASSERT_TRUE(R.contains({0x11, 0x11}));
+  // all in Range
+  ASSERT_TRUE(R.contains({0x11, 0x1f}));
+  // ends at end of Range
+  ASSERT_TRUE(R.contains({0x11, 0x20}));
+  // ends past Range
+  ASSERT_FALSE(R.contains({0x11, 0x21}));
+
+  //----------------------------------------------------------------------
+  // Test ranges that start at last bytes of Range
+  //----------------------------------------------------------------------
+  // ends at end of Range
+  ASSERT_TRUE(R.contains({0x1f, 0x20}));
+  // ends past Range
+  ASSERT_FALSE(R.contains({0x1f, 0x21}));
+
+  //----------------------------------------------------------------------
+  // Test ranges that start after Range
+  //----------------------------------------------------------------------
+  // empty just past in Range
+  ASSERT_FALSE(R.contains({0x20, 0x20}));
+  // valid past Range
+  ASSERT_FALSE(R.contains({0x20, 0x21}));
+}
+
+TEST(DWARFDebugInfo, TestDWARFDieRangeInfoContains) {
+  DWARFVerifier::DieRangeInfo Ranges({{0x10, 0x20}, {0x30, 0x40}});
+
+  ASSERT_FALSE(Ranges.contains({{{0x0f, 0x10}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x20, 0x30}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x40, 0x41}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x10, 0x20}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x1f, 0x20}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x30, 0x40}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x31, 0x32}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x3f, 0x40}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x10, 0x20}, {0x30, 0x40}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}, {0x31, 0x32}}}));
+  ASSERT_TRUE(Ranges.contains(
+      {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x33}}}));
+  ASSERT_FALSE(Ranges.contains(
+      {{{0x11, 0x12}, {0x12, 0x13}, {0x20, 0x21}, {0x31, 0x32}, {0x32, 0x33}}}));
+  ASSERT_FALSE(Ranges.contains(
+      {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x41}}}));
+}
+
+namespace {
+
+void AssertRangesIntersect(const DWARFVerifier::DWARFRange &LHS,
+                           const DWARFVerifier::DWARFRange &RHS) {
+  ASSERT_TRUE(LHS.intersects(RHS));
+  ASSERT_TRUE(RHS.intersects(LHS));
+}
+void AssertRangesDontIntersect(const DWARFVerifier::DWARFRange &LHS,
+                               const DWARFVerifier::DWARFRange &RHS) {
+  ASSERT_FALSE(LHS.intersects(RHS));
+  ASSERT_FALSE(RHS.intersects(LHS));
+}
+
+void AssertRangesIntersect(const DWARFVerifier::DieRangeInfo &LHS,
+                           const DWARFAddressRangesVector &Ranges) {
+  DWARFVerifier::DieRangeInfo RHS(Ranges);
+  ASSERT_TRUE(LHS.intersects(RHS));
+  ASSERT_TRUE(RHS.intersects(LHS));
+}
+
+void AssertRangesDontIntersect(const DWARFVerifier::DieRangeInfo &LHS,
+                               const DWARFAddressRangesVector &Ranges) {
+  DWARFVerifier::DieRangeInfo RHS(Ranges);
+  ASSERT_FALSE(LHS.intersects(RHS));
+  ASSERT_FALSE(RHS.intersects(LHS));
+}
+
+} // namespace
+TEST(DWARFDebugInfo, TestDwarfRangesIntersect) {
+  DWARFVerifier::DWARFRange R(0x10, 0x20);
+
+  //----------------------------------------------------------------------
+  // Test ranges that start before R...
+  //----------------------------------------------------------------------
+  // Other range ends before start of R
+  AssertRangesDontIntersect(R, {0x00, 0x10});
+  // Other range end address is start of a R
+  AssertRangesIntersect(R, {0x00, 0x11});
+  // Other range end address is in R
+  AssertRangesIntersect(R, {0x00, 0x15});
+  // Other range end address is at and of R
+  AssertRangesIntersect(R, {0x00, 0x20});
+  // Other range end address is past end of R
+  AssertRangesIntersect(R, {0x00, 0x40});
+
+  //----------------------------------------------------------------------
+  // Test ranges that start at R's start address
+  //----------------------------------------------------------------------
+  // Ensure empty ranges doesn't match
+  AssertRangesDontIntersect(R, {0x10, 0x10});
+  // 1 byte of Range
+  AssertRangesIntersect(R, {0x10, 0x11});
+  // same as Range
+  AssertRangesIntersect(R, {0x10, 0x20});
+  // 1 byte past Range
+  AssertRangesIntersect(R, {0x10, 0x21});
+
+  //----------------------------------------------------------------------
+  // Test ranges that start inside Range
+  //----------------------------------------------------------------------
+  // empty in range
+  AssertRangesDontIntersect(R, {0x11, 0x11});
+  // all in Range
+  AssertRangesIntersect(R, {0x11, 0x1f});
+  // ends at end of Range
+  AssertRangesIntersect(R, {0x11, 0x20});
+  // ends past Range
+  AssertRangesIntersect(R, {0x11, 0x21});
+
+  //----------------------------------------------------------------------
+  // Test ranges that start at last bytes of Range
+  //----------------------------------------------------------------------
+  // ends at end of Range
+  AssertRangesIntersect(R, {0x1f, 0x20});
+  // ends past Range
+  AssertRangesIntersect(R, {0x1f, 0x21});
+
+  //----------------------------------------------------------------------
+  // Test ranges that start after Range
+  //----------------------------------------------------------------------
+  // empty just past in Range
+  AssertRangesDontIntersect(R, {0x20, 0x20});
+  // valid past Range
+  AssertRangesDontIntersect(R, {0x20, 0x21});
+}
+
+TEST(DWARFDebugInfo, TestDWARFDieRangeInfoIntersects) {
+
+  DWARFVerifier::DieRangeInfo Ranges({{0x10, 0x20}, {0x30, 0x40}});
+
+  // Test empty range
+  AssertRangesDontIntersect(Ranges, {});
+  // Test range that appears before all ranges in Ranges
+  AssertRangesDontIntersect(Ranges, {{0x00, 0x10}});
+  // Test range that appears between ranges in Ranges
+  AssertRangesDontIntersect(Ranges, {{0x20, 0x30}});
+  // Test range that appears after ranges in Ranges
+  AssertRangesDontIntersect(Ranges, {{0x40, 0x50}});
+
+  // Test range that start before first range
+  AssertRangesIntersect(Ranges, {{0x00, 0x11}});
+  // Test range that start at first range
+  AssertRangesIntersect(Ranges, {{0x10, 0x11}});
+  // Test range that start in first range
+  AssertRangesIntersect(Ranges, {{0x11, 0x12}});
+  // Test range that start at end of first range
+  AssertRangesIntersect(Ranges, {{0x1f, 0x20}});
+  // Test range that starts at end of first range
+  AssertRangesDontIntersect(Ranges, {{0x20, 0x21}});
+  // Test range that starts at end of first range
+  AssertRangesIntersect(Ranges, {{0x20, 0x31}});
+
+  // Test range that start before second range and ends before second
+  AssertRangesDontIntersect(Ranges, {{0x2f, 0x30}});
+  // Test range that start before second range and ends in second
+  AssertRangesIntersect(Ranges, {{0x2f, 0x31}});
+  // Test range that start at second range
+  AssertRangesIntersect(Ranges, {{0x30, 0x31}});
+  // Test range that start in second range
+  AssertRangesIntersect(Ranges, {{0x31, 0x32}});
+  // Test range that start at end of second range
+  AssertRangesIntersect(Ranges, {{0x3f, 0x40}});
+  // Test range that starts at end of second range
+  AssertRangesDontIntersect(Ranges, {{0x40, 0x41}});
+}
+  
 } // end anonymous namespace