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

102

We usually use \param for consistency.

lib/DebugInfo/DWARF/DWARFVerifier.cpp

290

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

319

test?

375

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

395

. at the end

433

.

443

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

350–351

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

290

I added a test.

319

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

306–317

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?

317

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)

380–409

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.

385

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.

406–410

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)

411

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)

425–426

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

317

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.

385

Sure thing.

409

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?

410

It has now been inlined.

426

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

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

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

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

75–103

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)

114–117

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)

201–217

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.

207–208

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.

209–212

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)

214–215

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)

222–238

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

37–51

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.

62–72

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)

124–134

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.

139–153

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?

158–165

Probably invert this to reduce indentation:

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

171–173

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

bool HasErrors = DieRI.extractRangesAndReportErrors(OS);

178–180

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?)

181–188

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.

202

Invert to reduce indentation:

if (RangeSet.empty())
  return nullptr;

203–210

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

204–205

Could collapse these together:

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

208–210

Could collapse these two together:

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

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

220–223

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)) {
  ...

228

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'.

241–245

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

2501

/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

59

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

69

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?)

80–83

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.

124–130

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?

124–134

Still wondering about this ^

139–153

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?

155–159

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

178

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

205

Roll this into its one use:

switch (Die.getTag())

212–217

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

214–215

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?

224–227

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

59

Still curious about this

69

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.

80–83

Still curious about this

124–130

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.

130–132

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)

134–140

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.

139–153

Still curious about this

155–159

Still curious about this

175–176

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)

182

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?

212–217

Still wondering about this.

214–215

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

51

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

59

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

69

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.

83

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.

117

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

130

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

153

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

159

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

180

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.

188

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

208

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.

212

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.

215

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.

216

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.

217

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.

218

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.

224–225

The above two lines need to be removed.

238

Sounds good.

245

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

59

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

140

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/DWARFDebugRangeList.h

 #include <cstdint>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
 class raw_ostream;
 
+typedef std::pair<uint64_t, uint64_t> DWARFRange;
+
+/// Returns true if [LHS.first, LHS.second) intersects with
+/// [RHS.first, RHS.second).
+inline bool DWARFRangesIntersect(const DWARFRange &LHS, const DWARFRange &RHS) {
+  if (LHS.first == LHS.second || RHS.first == RHS.second)
+    return false; // Empty ranges can't intersect.
+  return (LHS.first < RHS.second) && (LHS.second > RHS.first);
+}
+
+/// Returns true if [LHS.first, LHS.second) contains [RHS.first, RHS.second).
+inline bool DWARFRangeContains(const DWARFRange &LHS, const DWARFRange &RHS) {
+  if (LHS.first <= RHS.first && RHS.first < LHS.second)
+    return LHS.first < RHS.second && RHS.second <= LHS.second;
+  return false;
+}
+
 /// DWARFAddressRangesVector - represents a set of absolute address ranges.
-typedef std::vector<std::pair<uint64_t, uint64_t>> DWARFAddressRangesVector;
+typedef std::vector<DWARFRange> DWARFAddressRangesVector;
+
+/// Returns true if any ranges in LHS intersect with any ranges of RHS.
+inline bool AnyDWARFRangesIntersect(const DWARFAddressRangesVector &LHS,
+                                    const DWARFAddressRangesVector &RHS) {
+  for (const auto &R : LHS)
+    for (const auto &L : RHS)
+      if (DWARFRangesIntersect(R, L))
+        return true;
+  return false;
+}
+
+/// Returns true LHS contains all ranges in RHS.
+inline bool DWARFRangesContains(const DWARFAddressRangesVector &LHS,
+                                const DWARFAddressRangesVector &RHS) {
+  for (const auto &L : LHS)
+    for (const auto &R : RHS)
+      if (!DWARFRangeContains(L, R))
+        return false;
+  return true;
+}
 
 class DWARFDebugRangeList {
 public:
   struct RangeListEntry {
     // A beginning address offset. This address offset has the size of an
     // address and is relative to the applicable base address of the
     // compilation unit referencing this range list. It marks the beginning
     // of an address range.

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 {
+  class SortedRanges {
+    DWARFAddressRangesVector Ranges;
+
+  public:
+    bool contains(const SortedRanges &RHS) const;
+    bool doesIntersect(const SortedRanges &RHS) const;
+    void dump(raw_ostream &OS) const;
+    bool empty() const { return Ranges.empty(); }
+    bool operator<(const SortedRanges &RHS) const;
+
+    /// Remove any empty or invalid ranges and return the number if invalid
+    /// ranges that were removed (empty ranges are not invalid).
+    static uint32_t removeInvalidRanges(DWARFAddressRangesVector &Ranges);
+    /// Inserts the unsorted ranges and returns true if errors were found
+    /// during insertion
+    bool insert(const DWARFAddressRangesVector &UnsortedRanges);
+  };
+
+  struct DieRangeInfo {
+    DWARFDie Die;
+    SortedRanges Ranges;
+
+    DieRangeInfo() : Die(), Ranges() {}
+    DieRangeInfo(DWARFDie D, const DWARFAddressRangesVector &R);
+    /// Return true if this object contains all ranges within RHS.
+    bool contains(const DieRangeInfo &RHS) const;
+    bool doesIntersect(const DieRangeInfo &RHS) const;
+    void dump(raw_ostream &OS) const;
+    bool operator<(const DieRangeInfo &RHS) const;
+    /// Return true if there are errors in the ranges R.
+    bool setDieAndReportRangeErrors(raw_ostream &OS, DWARFDie Die);
+    /// 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;
+  };
+
+  struct NonOverlappingRanges {
+    std::set<DieRangeInfo> RangeSet;
+
+    /// Returns true if the sibling ranges
+    const DieRangeInfo *GetOverlappingRangeInfo(const DieRangeInfo &RI) const;
+
+    bool insertAndReportErrors(raw_ostream &OS, const DieRangeInfo &RI);
+  };
+
   raw_ostream &OS;
   DWARFContext &DCtx;
+  DieRangeInfo UnitRI;
+  NonOverlappingRanges AllFunctionRanges;
+
   /// 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 ParantRI     The parent DIE's range information
+  /// \param NOR          The parent DIE's list of ranges that can't overlap.
+  void verifyDie(const DWARFDie &Die, const DieRangeInfo &ParentRI,
+                 NonOverlappingRanges &NOR);
+
+  /// Verify that no DIE ranges overlap.
+  void verifyNoRangesOverlap(const std::set<DieRangeInfo> &DieRangeInfos);
+
   /// 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

lib/DebugInfo/DWARF/DWARFVerifier.cpp

 #include <map>
 #include <set>
 #include <vector>
 
 using namespace llvm;
 using namespace dwarf;
 using namespace object;
 
+bool DWARFVerifier::SortedRanges::contains(const SortedRanges &RHS) const {
+  return DWARFRangesContains(Ranges, RHS.Ranges);
+}
+
+bool DWARFVerifier::SortedRanges::doesIntersect(const SortedRanges &RHS) const {
+  return AnyDWARFRangesIntersect(Ranges, RHS.Ranges);
+}
+
+void DWARFVerifier::SortedRanges::dump(raw_ostream &OS) const {
+  for (const auto &R : Ranges)
+    OS << " [" << format("0x%" PRIx64, R.first) << "-"
+       << format("0x%" PRIx64, R.second) << ")";
+}
+
+bool DWARFVerifier::SortedRanges::operator<(const SortedRanges &RHS) const {
+  if (RHS.Ranges.empty())
+    return false;
+  if (Ranges.empty())
+    return true;
+  size_t LeftSize = Ranges.size();
+  size_t RightSize = RHS.Ranges.size();
+  for (size_t I = 0; I < LeftSize; ++I) {
+    if (I >= RightSize)
+      return false;
+    if (Ranges[I].first != RHS.Ranges[I].first)
+      return Ranges[I].first < RHS.Ranges[I].first;
+    if (Ranges[I].second != RHS.Ranges[I].second)
+      return Ranges[I].second < RHS.Ranges[I].second;
+  }
+  return false;
+}
+
+uint32_t DWARFVerifier::SortedRanges::removeInvalidRanges(
+    DWARFAddressRangesVector &Ranges) {
+  uint32_t NumInvalidRanges = 0;
+  size_t I = 0;
+  while (I < Ranges.size()) {
+    if (Ranges[I].first >= Ranges[I].second) {
+      if (Ranges[I].first > Ranges[I].second)
+        ++NumInvalidRanges;
+      // Remove empty or invalid ranges.
+      Ranges.erase(Ranges.begin() + I);
+    } else {
+      ++I; // Only increment if we didn't remove the range.
+    }
+  }
+  return NumInvalidRanges;
+}
+
+bool DWARFVerifier::SortedRanges::insert(
+    const DWARFAddressRangesVector &UnsortedRanges) {
+  bool Error = false;
+  for (const auto &R : UnsortedRanges) {
+    if (R.first >= R.second)
+      continue;
+    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 (DWARFRangesIntersect(*InsertPos, R))
+          RangeOverlaps = true;
+        else if (InsertPos != Begin) {
+          auto Iter = InsertPos - 1;
+          if (DWARFRangesIntersect(*Iter, R))
+            RangeOverlaps = true;
+        }
+        if (RangeOverlaps) {
+          Error = true;
+        }
+      }
+      // Insert the range into our sorted list
+      Ranges.insert(InsertPos, R);
+    }
+  }
+  return Error;
+}
+
+bool DWARFVerifier::DieRangeInfo::setDieAndReportRangeErrors(raw_ostream &OS,
+                                                             DWARFDie D) {
+  Die = D;
+  auto UnsortedRanges = Die.getAddressRanges();
+  bool HasErrors = false;
+  if (SortedRanges::removeInvalidRanges(UnsortedRanges)) {
+    HasErrors = true;
+    OS << "error: invalid range in DIE:\n";
+  }
+  if (Ranges.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()) << ":";
+  Ranges.dump(OS);
+  OS << "\n";
+}
+
+void DWARFVerifier::verifyNoRangesOverlap(
+    const std::set<DieRangeInfo> &DieRangeInfos) {
+  auto End = DieRangeInfos.end();
+  auto Prev = End;
+  for (auto Curr = DieRangeInfos.begin(); Curr != End; ++Curr) {
+    if (Prev != End) {
+      if (Prev->doesIntersect(*Curr)) {
+        ++NumDebugInfoErrors;
+        OS << "error: DIEs have overlapping address ranges:\n";
+        Prev->Die.dump(OS, 0);
+        Curr->Die.dump(OS, 0);
+        OS << "\n";
+      }
+    }
+    Prev = Curr;
+  }
+}
+
+bool DWARFVerifier::DieRangeInfo::contains(const DieRangeInfo &RHS) const {
+  return Ranges.contains(RHS.Ranges);
+}
+
+bool DWARFVerifier::DieRangeInfo::doesIntersect(const DieRangeInfo &RHS) const {
+  return Ranges.doesIntersect(RHS.Ranges);
+}
+
+bool DWARFVerifier::DieRangeInfo::operator<(const DieRangeInfo &RHS) const {
+  return Ranges < RHS.Ranges;
+}
+
+bool DWARFVerifier::DieRangeInfo::reportErrorIfNotContained(
+    raw_ostream &OS, const DieRangeInfo &RI, const char *Error) const {
+  if (!contains(RI)) {
+    OS << Error;
+    Die.dump(OS, 0);
+    RI.Die.dump(OS, 0);
+    OS << "\n";
+    return true;
+  }
+  return false;
+}
+
+const DWARFVerifier::DieRangeInfo *
+DWARFVerifier::NonOverlappingRanges::GetOverlappingRangeInfo(
+    const DieRangeInfo &RI) const {
+  if (!RangeSet.empty()) {
+    auto Iter = RangeSet.lower_bound(RI);
+    if (Iter != RangeSet.end()) {
+      if (Iter->doesIntersect(RI))
+        return &*Iter;
+    }
+    if (Iter != RangeSet.begin()) {
+      --Iter;
+      if (Iter->doesIntersect(RI))
+        return &*Iter;
+    }
+  }
+  return nullptr;
+}
+
+bool DWARFVerifier::NonOverlappingRanges::insertAndReportErrors(
+    raw_ostream &OS, const DieRangeInfo &RI) {
+  bool Error = false;
+  auto OverlappingRI = GetOverlappingRangeInfo(RI);
+  if (OverlappingRI) {
+    OS << "error: DIEs have overlapping address ranges:\n";
+    OverlappingRI->Die.dump(OS, 0);
+    RI.Die.dump(OS, 0);
+    OS << "\n";
+    Error = true;
+  }
+  RangeSet.insert(RI);
+  return Error;
+}
+
+void DWARFVerifier::verifyDie(const DWARFDie &Die, const DieRangeInfo &ParentRI,
+                              NonOverlappingRanges &NOR) {
+  const auto Tag = Die.getTag();
+
+  DieRangeInfo RI;
+  switch (Tag) {
+  case DW_TAG_null:
+    return;
+  case DW_TAG_compile_unit:
+    if (UnitRI.setDieAndReportRangeErrors(OS, Die))
+      ++NumDebugInfoErrors;
+    break;
+  case DW_TAG_subprogram: {
+    if (RI.setDieAndReportRangeErrors(OS, Die))
+      ++NumDebugInfoErrors;
+    if (RI.Ranges.empty())
+      break;
+
+    // If the compile unit has address range(s), it must contain DIE's ranges.
+    const char *Error = "error: CU DIE has child with address ranges that are "
+                        "not contained in its ranges:\n";
+    if (!UnitRI.Ranges.empty() &&
+        UnitRI.reportErrorIfNotContained(OS, RI, Error)) {
+      ++NumDebugInfoErrors;
+    }
+
+    // Check if this function's range overlaps with any previous function ranges
+    // from any compile unit and make an error if needed.
+    if (AllFunctionRanges.insertAndReportErrors(OS, RI))
+      ++NumDebugInfoErrors;
+
+  } break;
+  case DW_TAG_lexical_block:
+  case DW_TAG_inlined_subroutine: {
+    if (RI.setDieAndReportRangeErrors(OS, Die)) {
+      ++NumDebugInfoErrors;
+      Die.dump(OS, 0);
+      OS << "\n";
+    }
+    if (RI.Ranges.empty())
+      break;
+    // Check to make sure our parent contains all ranges for this Die.
+    const char *Error = "error: DIE has a child DIE whose address ranges are "
+                        "not contained in its ranges:\n";
+    if (ParentRI.reportErrorIfNotContained(OS, RI, Error))
+      ++NumDebugInfoErrors;
+
+    // Check if this range overlaps with any previous sibling ranges and make an
+    // error if needed.
+    if (NOR.insertAndReportErrors(OS, RI))
+      ++NumDebugInfoErrors;
+  } break;
+  default:
+    RI.Die = Die;
+    break;
+  }
+  // Verify the attributes and forms.
+  for (auto AttrValue : Die.attributes()) {
+    verifyDebugInfoAttribute(Die, AttrValue);
+    verifyDebugInfoForm(Die, AttrValue);
+  }
+
+  NonOverlappingRanges DieNRO;
+  for (DWARFDie Child : Die)
+    verifyDie(Child, RI, DieNRO);
+}
 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);
-      }
-    }
+    NonOverlappingRanges NRO;
+    verifyDie(CU->getUnitDIE(/* ExtractUnitDIEOnly = */ false), DieRangeInfo(),
+              NRO);
   }
   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

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: CU DIE has child with address ranges that "
+                            "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 two functions that have 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:");
+}
+
+namespace {
+
+void AssertRangesIntersect(const DWARFRange &LHS, const DWARFRange &RHS) {
+  ASSERT_TRUE(DWARFRangesIntersect(LHS, RHS));
+  ASSERT_TRUE(DWARFRangesIntersect(RHS, LHS));
+}
+void AssertRangesDontIntersect(const DWARFRange &LHS, const DWARFRange &RHS) {
+  ASSERT_FALSE(DWARFRangesIntersect(LHS, RHS));
+  ASSERT_FALSE(DWARFRangesIntersect(RHS, LHS));
+}
+
+void AssertRangesIntersect(const DWARFAddressRangesVector &LHS,
+                           const DWARFAddressRangesVector &RHS) {
+  ASSERT_TRUE(AnyDWARFRangesIntersect(LHS, RHS));
+  ASSERT_TRUE(AnyDWARFRangesIntersect(RHS, LHS));
+}
+
+void AssertRangesDontIntersect(const DWARFAddressRangesVector &LHS,
+                               const DWARFAddressRangesVector &RHS) {
+  ASSERT_FALSE(AnyDWARFRangesIntersect(LHS, RHS));
+  ASSERT_FALSE(AnyDWARFRangesIntersect(RHS, LHS));
+}
+
+} // namespace
+TEST(DWARFDebugInfo, TestDwarfRangesIntersect) {
+  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, TestDwarfRangeVectorsIntersect) {
+  DWARFAddressRangesVector 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