[DWARF] Simplify DWARFAddressRange::contains

[MaskRay]

Summary

This transform is valid because the ranges have been validated (LowPC <= HighPC).

[jhenderson]

Also, mostly as an FYI, I didn't write this code, I just moved it. I've added @JDevlieghere as a reviewer, since he was the one that wrote it!

This transform is valid because the ranges have been validated (LowPC <= HighPC).

Given that this is in library code, I don't think we can make this statement. It might be valid in the current use-case(s), but technically, it's not guaranteed to be. I think it would would be reasonable to mandate it though, by explicitly adding asserts in intersects() and contains().

This code has some unit-tests in DWARFDebugInfoTest.cpp, and I'd expect to see any changes in behaviour reflected in the tests (specifically the changes in intersects()). Possibly, a new unit test file might be appropriate though.

include/llvm/DebugInfo/DWARF/DWARFAddressRange.h

39 ↗

(On Diff #139419)

There's a change in behaviour here, which I actually agree with, although I wonder whether it could have a negative impact on the clients. Given a range [N, N+2), I would expect an empty range of [N+1, N+1) to be classified as intersecting with it. Empty ranges at either end of the non-empty range are less clear-cut though, and I don't think should count as intersecting.

[JDevlieghere]

In D44772#1045398, @jhenderson wrote:

Also, mostly as an FYI, I didn't write this code, I just moved it. I've added @JDevlieghere as a reviewer, since he was the one that wrote it!

Thanks James!

This transform is valid because the ranges have been validated (LowPC <= HighPC).

Given that this is in library code, I don't think we can make this statement. It might be valid in the current use-case(s), but technically, it's not guaranteed to be. I think it would would be reasonable to mandate it though, by explicitly adding asserts in intersects() and contains().

An assertion sounds like the right trade-off.

This code has some unit-tests in DWARFDebugInfoTest.cpp, and I'd expect to see any changes in behaviour reflected in the tests (specifically the changes in intersects()). Possibly, a new unit test file might be appropriate though.

Correct, the current test that checks the scenario you described in your inline comment, now fails. Overlap of empty ranges at the begin and end of the interval still considered as non intersecting.

I ran the verifier over a freshly built clang and I didn't see any verification errors. That said, I'm not convinced we should consider fully-enclosed empty intervals as intersecting; the DWARF standard says that empty ranges can be ignored and therefore the verifier should not complain about this.

[jhenderson]

In D44772#1045463, @JDevlieghere wrote:

That said, I'm not convinced we should consider fully-enclosed empty intervals as intersecting; the DWARF standard says that empty ranges can be ignored and therefore the verifier should not complain about this.

Okay, I'm convinced by that comment (I just checked, and it applies for .debug_ranges as well as .debug_rnglists). In more general terms, empty ranges probably should be considered for intersection, in my opinion, but not for these sort of ranges.

[JDevlieghere]

In D44772#1045471, @jhenderson wrote:

In D44772#1045463, @JDevlieghere wrote:

That said, I'm not convinced we should consider fully-enclosed empty intervals as intersecting; the DWARF standard says that empty ranges can be ignored and therefore the verifier should not complain about this.

Okay, I'm convinced by that comment (I just checked, and it applies for .debug_ranges as well as .debug_rnglists). In more general terms, empty ranges probably should be considered for intersection, in my opinion, but not for these sort of ranges.

In mathematics, the intersection of two intervals is always an interval. The intersection of the any empty interval with any other interval would be the empty interval. The intersection of two disjoin intervals would also be the empty interval. So I don't think the empty interval should ever be considered as intersecting with anything.

[MaskRay]

Add assert().

Callers of
intersects
└⏷insert (DWARFVerifier.cpp:37)
└⏵verifyDieRanges (DWARFVerifier.cpp:340)
└⏷insert (DWARFVerifier.cpp:41)
└⏵verifyDieRanges (DWARFVerifier.cpp:340)
└⏷intersects (DWARFVerifier.cpp:100)
└⏵insert (DWARFVerifier.cpp:55)

[MaskRay]

include/llvm/DebugInfo/DWARF/DWARFAddressRange.h

39 ↗

(On Diff #139419)

Added an assert as the call site has checked the validity.

[jhenderson]

include/llvm/DebugInfo/DWARF/DWARFAddressRange.h

39 ↗

(On Diff #139419)

I might have missed something, but won't this assert() fire on some of the unit tests? If we think they're not really valid, please could you delete the relevant ones.

[MaskRay]

Make debug/unittests/DebugInfo/DWARF/DebugInfoDWARFTests pass

[MaskRay]

Update only contains

[jhenderson]

LGTM. Any reason you decided not to change intersects()?

@JDevlieghere - any more comments from you?

[JDevlieghere]

In D44772#1048988, @jhenderson wrote:

LGTM. Any reason you decided not to change intersects()?

Because we concluded that would not conform to the dwarf standard, right?

@JDevlieghere - any more comments from you?

The current diff LGTM.

[jhenderson]

In D44772#1049012, @JDevlieghere wrote:

In D44772#1048988, @jhenderson wrote:

LGTM. Any reason you decided not to change intersects()?

Because we concluded that would not conform to the dwarf standard, right?

Right. I was just wondering whether the assert is needed in intersects (after the if, obviously), as well as contains. I think it's fine without it though.

[JDevlieghere]

In D44772#1049017, @jhenderson wrote:

In D44772#1049012, @JDevlieghere wrote:

In D44772#1048988, @jhenderson wrote:

LGTM. Any reason you decided not to change intersects()?

Because we concluded that would not conform to the dwarf standard, right?

Right. I was just wondering whether the assert is needed in intersects (after the if, obviously), as well as contains. I think it's fine without it though.

Ah, yes, we should have checked validity before calling intersect. Please add the assertion there as well. Thanks!

[MaskRay]

Add validity assert

llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h

DWARFAddressRange(uint64_t LowPC, uint64_t HighPC, uint64_t SectionIndex = 0)
       : LowPC(LowPC), HighPC(HighPC), SectionIndex(SectionIndex) {}
 
   /// Returns true if LowPC is smaller or equal to HighPC. This accounts for
   /// dead-stripped ranges.
   bool valid() const { return LowPC <= HighPC; }
 
   /// Returns true if [LowPC, HighPC) intersects with [RHS.LowPC, RHS.HighPC).
   bool intersects(const DWARFAddressRange &RHS) const {
+    assert(valid() && RHS.valid());
     // Empty ranges can't intersect.
     if (LowPC == HighPC || RHS.LowPC == RHS.HighPC)
       return false;
-    return (LowPC < RHS.HighPC) && (HighPC > RHS.LowPC);
+    return LowPC < RHS.HighPC && RHS.LowPC < HighPC;
   }
 
   /// Returns true if [LowPC, HighPC) fully contains [RHS.LowPC, RHS.HighPC).
   bool contains(const DWARFAddressRange &RHS) const {
-    if (LowPC <= RHS.LowPC && RHS.LowPC <= HighPC)
-      return LowPC <= RHS.HighPC && RHS.HighPC <= HighPC;
-    return false;
+    assert(valid() && RHS.valid());
+    return LowPC <= RHS.LowPC && RHS.HighPC <= HighPC;
   }
 
   void dump(raw_ostream &OS, uint32_t AddressSize,
             DIDumpOptions DumpOpts = {}) const;
 };
 
 static inline bool operator<(const DWARFAddressRange &LHS,
                              const DWARFAddressRange &RHS) {