[llvm-dwarfdump] Fix unsigned overflow when calculating stats

[djtodoro]

Summary

This fixes https://bugs.llvm.org/show_bug.cgi?id=51652.

The idea is to bump all the stat fields to 64-bit wide unsigned integers. I've confirmed this resolves the use case for chromium.

[Orlando]

llvm/tools/llvm-dwarfdump/Statistics.cpp

421–422

I think this assert should come before the assignment and be something like this to catch a value that would "overflow" by wrapping:
assert(GlobalStats.ScopeBytesCovered + ScopeBytesCovered >= GlobalStats.ScopeBytesCovered && "ScopeBytesCovered - overflow");
Otherwise I don't think this assertion will ever catch anything, since all uint64_t values are <= UINT64_MAX.

[dblaikie]

Seems like a generally reasonabel direction forward.

llvm/tools/llvm-dwarfdump/Statistics.cpp

421–422

Yep! I think the more general assert probably looks like this:

assert(x <= max - y)
x += y;

423–424

When would this assert fire? If ScopeEntryValueBytesCovered is a uint64_t, it can't ever be > than the max uint64_t value.

Checking for overflow would usually be done, I tihnk, with a check before the overflow:

assert(x <= max - y)
x += y;

[akhuang]

no other comments, thanks for the fix!

[djtodoro]

llvm/tools/llvm-dwarfdump/Statistics.cpp

421–422

Oh yes, thanks

[tschuett]

Could something ala:
https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
help?

[dblaikie]

In D109217#2984816, @tschuett wrote:

Could something ala:
https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
help?

Probably enough to write the portable code (so it works on MSVC too, etc) and let the compiler optimize it. At least for this saturation code, Clang produces the same with or without the intrinsic (& GCC produces something else entirely - to itself and to clang): https://godbolt.org/z/jb3nnaKvT

[tschuett]

In D109217#2985644, @dblaikie wrote:

In D109217#2984816, @tschuett wrote:

Could something ala:
https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
help?

Probably enough to write the portable code (so it works on MSVC too, etc) and let the compiler optimize it. At least for this saturation code, Clang produces the same with or without the intrinsic (& GCC produces something else entirely - to itself and to clang): https://godbolt.org/z/jb3nnaKvT

Maybe LLVM should learn saturating integers that assert in debug mode?

[dblaikie]

In D109217#2985647, @tschuett wrote:

In D109217#2985644, @dblaikie wrote:

In D109217#2984816, @tschuett wrote:

Could something ala:
https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
help?

Probably enough to write the portable code (so it works on MSVC too, etc) and let the compiler optimize it. At least for this saturation code, Clang produces the same with or without the intrinsic (& GCC produces something else entirely - to itself and to clang): https://godbolt.org/z/jb3nnaKvT

Maybe LLVM should learn saturating integers that assert in debug mode?

Perhaps. (though anything that asserts in debug mode should basically be UB in non-debug mode, in my opinion - if you aren't testing/using the functionality, it shouldn't be defined)

For ints we've got UBSan, but unsigned ints are defined on wrap. There's no unsigned type that's UB on overflow - certainly might be nice to have them to clarify the difference between a think you want to do weird bitfiddling with and expect all the overflow, etc, and a thing that's meant to do maths and where sanitizers could diagnose overflow, etc.

But I think a couple of manual overflow checks here is probably OK - might be worth putting it in a generic function and applying it to all the statistics to make things more robust/generic.

[xbolva00]

For ints we've got UBSan, but unsigned ints are defined on wrap. There's no unsigned type that's UB on overflow - certainly might be nice to have them to clarify the difference between a think you want to do weird bitfiddling with and expect all the overflow, etc, and a thing that's meant to do maths and where sanitizers could diagnose overflow, etc.

-fsanitize=unsigned-integer-overflow ?

[dblaikie]

In D109217#2985680, @xbolva00 wrote:

For ints we've got UBSan, but unsigned ints are defined on wrap. There's no unsigned type that's UB on overflow - certainly might be nice to have them to clarify the difference between a think you want to do weird bitfiddling with and expect all the overflow, etc, and a thing that's meant to do maths and where sanitizers could diagnose overflow, etc.

-fsanitize=unsigned-integer-overflow ?

Oh, right, we do have that :) (but no doubt LLVM isn't remotely clean of failures for it)

[djtodoro]

• add a test
• bump the stats version
• address the comments (I think that these few asserts are enough for this)
• split JSON part into a separate patch

[Orlando]

Just one more inline question from me, but I will defer to the other reviewers for the rest & approval. Thanks for fixing this.

llvm/tools/llvm-dwarfdump/Statistics.cpp

794–809

I'm not sure how much this matters but looking at the comment above I don't think a version bump is necessary for this patch? Any input that didn't trip the assertions previously will still have the same output with the patch applied.

[djtodoro]

llvm/tools/llvm-dwarfdump/Statistics.cpp

794–809

I think since this is a bug fix we should bump it -- e.g., a stat number could have been 0 (as a consequence of the bug), and now it will be 2^32 for example, right? I think that this is the purpose behind the stats version.

[tschuett]

Let me revisit the saturating integer without asserts. If you print 5 for an uint32_t, you will never know whether it overflowed never or 10 times (in release mode).

A saturating integer will print 5 or max int (saturated).

Even an SaturatingUint<uint64_t> shouldn't yield too much overhead.

[djtodoro]

In D109217#2987177, @tschuett wrote:

Let me revisit the saturating integer without asserts. If you print 5 for an uint32_t, you will never know whether it overflowed never or 10 times (in release mode).

A saturating integer will print 5 or max int (saturated).

Even an SaturatingUint<uint64_t> shouldn't yield too much overhead.

Hmm, is there an implementation of the SaturatingUint, or do we need to implement such type?

[tschuett]

Not at the moment. I just wanted to pitch the idea of having a saturating integer in LLVM.

[djtodoro]

I think we can implement it here, and it will be useful/safe.
The question is if that should be implemented as a general thing in LLVM.

[Orlando]

It seems like the down side of using asserts to detect the "overflow" (the patch's current approach) is that release-config users may still get misleading stats due to wrapping. Implementing a saturating int in and of itself doesn't seem like a full solution, since a user may not notice that the stat is the saturated value, or even know that it's special, especially if the stats are consumed by another tool.

IMO when the stat cannot be computed properly - however the detection is implemented, either with saturating ints, checks like the ones in the asserts, or something else - a good solution for users would be to print a message, and either skip printing the "bad" stats or all of them. That would be consistent for all build configurations and avoid hiding the issue. What do you think? Sorry if I'm just stating the obvious!

llvm/tools/llvm-dwarfdump/Statistics.cpp

794–809

Sounds reasonable (I wasn't thinking about release mode when I made that comment).

[tschuett]

You will always know whether it is max int or max int because of saturating behaviour.

class SatUint32 {
  uint32_t value;
  bool overflowed;
}

[tschuett]

The saturating integer class would use the builtins I mentioned above to perform arithmetic operations on value and detect overflow and set overflow to true.

[dblaikie]

I'd just saturate to max int, and use the max int value to indicate overflow. Shaving one value off to represent the overflow state seems fine to me.

[tschuett]

That is fine be me. I guess the point is a save way to collect statistics and give guidance to users when the results could be bad, in release and debug mode. I would argue that saturating integers are different and maybe more precise solution than going from uint32_t to uint64_t ...

[dblaikie]

In D109217#2992699, @tschuett wrote:

That is fine be me. I guess the point is a save way to collect statistics and give guidance to users when the results could be bad, in release and debug mode. I would argue that saturating integers are different and maybe more precise solution than going from uint32_t to uint64_t ...

Well, both, probably - support use cases that weren't supported before (binaries that were too large to fit in the existing stats) and, separately/additionally, some way of reporting overflow rather than reporting bogus values.

[djtodoro]

• Introduce the SaturatingUINT64

[xbolva00]

In D109217#2992694, @dblaikie wrote:

I'd just saturate to max int, and use the max int value to indicate overflow. Shaving one value off to represent the overflow state seems fine to me.

+1, do not need Overflow flag.

[djtodoro]

-remove the isOverflow field

[dblaikie]

llvm/tools/llvm-dwarfdump/Statistics.cpp

71

Personally, I think once we've defined the behavior on overflow, we shouldn't assert that overflow doesn't happen - this undermines the concept of having defined behavior on overflow (& makes it somewhat harder to test - since that behavior can now only be tested in a non-asserts build (well, I guess since assert isn't UB-if-false, and the assert is after the warning, that's not the case, but it's a bit subtle)).

Also, might it make more sense to do the warning/etc on the final use/printing out of the statistic instead? (I guess that's difficult because some statistics are derived from others? - so catching it the moment it overflows means it'll always be diagnosed only once, rather than multiple times due to multiple uses?)

[djtodoro]

llvm/tools/llvm-dwarfdump/Statistics.cpp

71

Thanks for the suggestions. I totally agree.

I guess that it makes sense to report the warning when printing the overflowed value, since we can point to the specific field.

[djtodoro]

• addressing comments
  • now the warning looks as follows:

"#call site DIEs": N (llvm-dwarfdump: warning: this field overflows),

[dblaikie]

In D109217#3009505, @djtodoro wrote:

• addressing comments
  • now the warning looks as follows:

"#call site DIEs": N (llvm-dwarfdump: warning: this field overflows),

Maybe we could render it symbolically and just say:

"#call site DIEs": >= 9223372036854775807

But yeah, maybe the warning is more suitable, not sure - I'll leave it up to you folks to decide what's best.

[dblaikie]

@cmtice @rdhindsa - might be handy if you folks are aware of this in terms of quirks when encoding the stats from our internal analysis pipelines, in case the format chosen here needs to be taken into account for how to render out of range data.

[djtodoro]

In D109217#3011103, @dblaikie wrote:

In D109217#3009505, @djtodoro wrote:

• addressing comments
  • now the warning looks as follows:

"#call site DIEs": N (llvm-dwarfdump: warning: this field overflows),

Maybe we could render it symbolically and just say:

"#call site DIEs": >= 9223372036854775807

But yeah, maybe the warning is more suitable, not sure - I'll leave it up to you folks to decide what's best.

I'd prefer the warning since it will be easier when parsing the JSON data from utilities such as llvm-locstats.

[djtodoro]

ping :)

[dblaikie]

llvm/test/tools/llvm-dwarfdump/X86/locstats-bytes-overflow.yaml

25

I think it'd be worth CHECKing the specific/full syntax, rather than just "this warning text appears somewhere in the output" - since we're specifically putting it in the output in a particular place.

Hmm, that raises a question: is this warning going to stderr, but the actual stats output is to stdout? If so then I think that's a different problem. Maybe that answers one of my other questions though when I suggested printing the output as "> max int" - https://reviews.llvm.org/D109217#3012175 - is that what you meant in this comment? That the value in the JSON data doesn't have any mention of the warning/overflow, and only has the saturated integer value?

I worry that's error-prone though, since the value is incorrect and a tool might not be aware of that. So I think it may be valuable to ensure we don't encode a valid value/something that could be mistaken for a valid value in the field when it's overflowed?

JSON supports the value being a string, I assume - so perhaps a string representation of ">= max int" or "overflowed" or something would be suitable?

llvm/tools/llvm-dwarfdump/Statistics.cpp

51–56

Maybe just implement this in terms of the other:

[djtodoro]

llvm/test/tools/llvm-dwarfdump/X86/locstats-bytes-overflow.yaml

25

Yep, that was my concern. It was going to stderr, but the JSON data goes to stdout.

JSON supports the value being a string, I assume - so perhaps a string representation of ">= max int" or "overflowed" or something would be suitable?

Hmm, I agree... using some special value will make this output ready for the tools from outside. I'll update that.

llvm/tools/llvm-dwarfdump/Statistics.cpp

51–56

yes, thanks

[djtodoro]

• introduce "overflow" special stats value for the fields that overflow

[dblaikie]

This looks alright to me - though I'll leave it to toher folks with more statistics interest to provide final approval.

(@cmtice @rdhindsa - something to be aware of that might crop-up in google uses of the statistics infrastructure, I'd expect)

[djtodoro]

In D109217#3048505, @dblaikie wrote:

This looks alright to me - though I'll leave it to toher folks with more statistics interest to provide final approval.

(@cmtice @rdhindsa - something to be aware of that might crop-up in google uses of the statistics infrastructure, I'd expect)

Sure, thanks for your comments!

[aprantl]

I think this is reasonable, out of curiosity, would there be a benefit to using APInt? Probably not because 64 bits is already huge...

[djtodoro]

In D109217#3049369, @aprantl wrote:

I think this is reasonable, out of curiosity, would there be a benefit to using APInt? Probably not because 64 bits is already huge...

I guess we can use APInt as well, but the 64 bits seem enough for now. A challenge would be to teach all the front-ends how to parse the big numbers (>64bits), but it is achievable.

[aprantl]

Ok. Works for me.

llvm/tools/llvm-dwarfdump/Statistics.cpp

53

https://en.cppreference.com/w/cpp/types/numeric_limits/max ?

[djtodoro]

Thanks!

[djtodoro]

-use the std::numeric_limits<uint64_t>::max()

llvm/test/tools/llvm-dwarfdump/X86/locstats-big-number-of-bytes.yaml

+# RUN: yaml2obj %s | llvm-dwarfdump --statistics - | FileCheck %s
+
+## Check that we are covering the situation when
+## sum of bytes in scope is a huge (uint64_t) number.
+##
+## The yaml represents this DWARF:
+##
+## DW_TAG_compile_unit
+##   DW_AT_low_pc (0x0000000000000000)
+##   DW_AT_high_pc  (0x000000000000000b)
+##
+##   DW_TAG_subprogram
+##     DW_AT_low_pc (0x0000000000000000)
+##     DW_AT_high_pc  (0x00000000ffffffff)
+##       DW_TAG_variable
+##         DW_AT_location (0x00000023:
+##            [0x0000000000000003, 0x0000000000000005): DW_OP_reg2 RCX)
+##   DW_TAG_subprogram
+##     DW_AT_low_pc    (0x0000000000000000)
+##     DW_AT_high_pc   (0x00000000ffffffff)
+##     DW_TAG_variable
+##       DW_AT_location        (0x00000023:
+##             [0x0000000000000003, 0x0000000000000005): DW_OP_reg2 RCX)
+
+# CHECK: "version": 9,
+# CHECK: "sum_all_variables(#bytes in parent scope)": 8589934590
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_EXEC
+  Machine: EM_X86_64
+Sections:
+  - Name:         .debug_loc
+    Type:         SHT_PROGBITS
+    AddressAlign: 0x01
+    Content:      '00000000000000000600000000000000010055000000000000000000000000000000000300000000000000050000000000000001005200000000000000000000000000000000'
+  - Name:         .debug_ranges
+    Type:         SHT_PROGBITS
+    AddressAlign: 0x01
+    Content:      '000000000000000003000000000000000500000000000000080000000000000000000000000000000000000000000000'
+DWARF:
+  debug_abbrev:
+    - Table:
+      - Code:     1
+        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_data4
+      - Code:     2
+        Tag:      DW_TAG_subprogram
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_low_pc
+            Form:      DW_FORM_addr
+          - Attribute: DW_AT_high_pc
+            Form:      DW_FORM_data4
+      - Code:     3
+        Tag:      DW_TAG_variable
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_location
+            Form:      DW_FORM_sec_offset
+  debug_info:
+    - Version:    4
+      AbbrOffset: 0x00
+      Entries:
+        - AbbrCode: 1 ## DW_TAG_compile_unit
+          Values:
+            - Value: 0x00 ## DW_AT_low_pc
+            - Value: 0x0b ## DW_AT_high_pc
+        - AbbrCode: 2 ## DW_TAG_subprogram
+          Values:
+            - Value: 0x00 ## DW_AT_low_pc
+            - Value: 0xFFFFFFFF ## DW_AT_high_pc
+        - AbbrCode: 3 ## DW_TAG_variable
+          Values:
+            - Value: 0x23 ## DW_AT_sec_offset
+        - AbbrCode: 0 ## NULL
+        - AbbrCode: 2 ## DW_TAG_subprogram
+          Values:
+            - Value: 0x00 ## DW_AT_low_pc
+            - Value: 0xFFFFFFFF ## DW_AT_high_pc
+        - AbbrCode: 3 ## DW_TAG_variable
+          Values:
+            - Value: 0x23 ## DW_AT_sec_offset
+        - AbbrCode: 0 ## NULL
+        - AbbrCode: 0 ## NULL

llvm/test/tools/llvm-dwarfdump/X86/locstats-bytes-overflow.yaml

+# REQUIRES: asserts
+# RUN: yaml2obj %s | not --crash llvm-dwarfdump --statistics - -o /dev/null %s 2>&1 | FileCheck %s
+
+## Check that we are covering the situation when a stat field overflows.
+##
+## The yaml represents this DWARF:
+##
+## DW_TAG_compile_unit
+##   DW_AT_low_pc (0x0000000000000000)
+##   DW_AT_high_pc  (0x000000000000000b)
+##
+##   DW_TAG_subprogram
+##     DW_AT_low_pc (0x0000000000000000)
+##     DW_AT_high_pc  (0xffffffffffffffff)
+##       DW_TAG_variable
+##         DW_AT_location (0x00000023:
+##            [0x0000000000000003, 0x0000000000000005): DW_OP_reg2 RCX)
+##   DW_TAG_subprogram
+##     DW_AT_low_pc    (0x0000000000000000)
+##     DW_AT_high_pc   (0xffffffffffffffff)
+##     DW_TAG_variable
+##       DW_AT_location        (0x00000023:
+##             [0x0000000000000003, 0x0000000000000005): DW_OP_reg2 RCX)
+
+# CHECK: Stat field overflow
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS[[BITS=64]]
+  Data:    ELFDATA2LSB
+  Type:    ET_EXEC
+  Machine: EM_X86_64
+Sections:
+  - Name:         .debug_loc
+    Type:         SHT_PROGBITS
+    AddressAlign: 0x01
+    Content:      '00000000000000000600000000000000010055000000000000000000000000000000000300000000000000050000000000000001005200000000000000000000000000000000'
+  - Name:         .debug_ranges
+    Type:         SHT_PROGBITS
+    AddressAlign: 0x01
+    Content:      '000000000000000003000000000000000500000000000000080000000000000000000000000000000000000000000000'
+DWARF:
+  debug_abbrev:
+    - Table:
+      - Code:     1
+        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_data8
+      - Code:     2
+        Tag:      DW_TAG_subprogram
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_low_pc
+            Form:      DW_FORM_addr
+          - Attribute: DW_AT_high_pc
+            Form:      DW_FORM_data8
+      - Code:     3
+        Tag:      DW_TAG_variable
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_location
+            Form:      DW_FORM_sec_offset
+  debug_info:
+    - Version:    4
+      AbbrOffset: 0x00
+      Entries:
+        - AbbrCode: 1 ## DW_TAG_compile_unit
+          Values:
+            - Value: 0x00 ## DW_AT_low_pc
+            - Value: 0x0b ## DW_AT_high_pc
+        - AbbrCode: 2 ## DW_TAG_subprogram
+          Values:
+            - Value: 0x00 ## DW_AT_low_pc
+            - Value: 0xFFFFFFFFFFFFFFFF ## DW_AT_high_pc
+        - AbbrCode: 3 ## DW_TAG_variable
+          Values:
+            - Value: 0x23 ## DW_AT_sec_offset
+        - AbbrCode: 0 ## NULL
+        - AbbrCode: 2 ## DW_TAG_subprogram
+          Values:
+            - Value: 0x00 ## DW_AT_low_pc
+            - Value: 0xFFFFFFFFFFFFFFFF ## DW_AT_high_pc
+        - AbbrCode: 3 ## DW_TAG_variable
+          Values:
+            - Value: 0x23 ## DW_AT_sec_offset
+        - AbbrCode: 0 ## NULL
+        - AbbrCode: 0 ## NULL

llvm/test/tools/llvm-dwarfdump/X86/locstats-for-absctract-origin-vars.yaml

 ##         DW_AT_decl_line       (1)
 ##       DW_TAG_lexical_block
 ##         DW_TAG_variable <--(0x000000f8)
 ##           DW_AT_decl_file     (0x01)
 ##           DW_AT_decl_line     (1)
 ##    DW_TAG_subprogram
 ##        DW_AT_abstract_origin (0x000000f0)
 
-# CHECK: "version": 8,
+# CHECK: "version": 9,
 # CHECK: "#variables processed by location statistics": 17,
 # CHECK: "#variables with 0% of parent scope covered by DW_AT_location": 13,
 # CHECK: "#variables with 100% of parent scope covered by DW_AT_location": 4,
 
 --- !ELF
 FileHeader:
   Class:   ELFCLASS64
   Data:    ELFDATA2LSB

llvm/test/tools/llvm-dwarfdump/X86/statistics-dwo.test

 #   printf ("fibonacci(9) = %d\n", result);
 #   result = fib(10);
 #   printf ("fibonacci(10) = %d\n", result);
 # 
 #   return 0;
 # }
 #
 
-CHECK:      "version": 8,
+CHECK:      "version": 9,
 CHECK:      "#functions": 3,
 CHECK:      "#functions with location": 3,
 CHECK:      "#inlined functions": 7,
 CHECK:      "#inlined functions with abstract origins": 7,
 CHECK:      "#unique source variables": 9,
 CHECK:      "#source variables": 30,
 
 # Ideally the value below would be 33 but currently it's not.

llvm/test/tools/llvm-dwarfdump/X86/statistics-v3.test

 #   printf ("fibonacci(9) = %d\n", result);
 #   result = fib(10);
 #   printf ("fibonacci(10) = %d\n", result);
 # 
 #   return 0;
 # }
 #
 
-CHECK:      "version": 8,
+CHECK:      "version": 9,
 CHECK:      "#functions": 3,
 CHECK:      "#functions with location": 3,
 CHECK:      "#inlined functions": 8,
 CHECK:      "#inlined functions with abstract origins": 8,
 CHECK:      "#unique source variables": 9,
 CHECK:      "#source variables": 33,
 
 # Ideally the value below would be 33 but currently it's not.

llvm/test/tools/llvm-dwarfdump/X86/statistics.ll

 ; RUN: llc -O0 %s -o - -filetype=obj \
 ; RUN:   | llvm-dwarfdump -statistics - | FileCheck %s
-; CHECK: "version": 8,
+; CHECK: "version": 9,
 
 ; namespace test {
 ;  extern int a;
 ; }
 ; using test::a;
 ;
 ; int GlobalConst = 42;
 ; int Global;

llvm/test/tools/llvm-dwarfdump/X86/stats-scope-bytes-covered.yaml

 ##
 ##       // #bytes in parent scope: 6
 ##       // #bytes in any scope covered by DW_AT_location: 2
 ##       // #bytes in parent scope covered by DW_AT_location: 0
 ##       DW_TAG_variable
 ##         DW_AT_location (0x00000023:
 ##            [0x0000000000000003, 0x0000000000000005): DW_OP_reg2 RCX)
 
-# CHECK: "version": 8,
+# CHECK: "version": 9,
 # CHECK: "sum_all_variables(#bytes in parent scope)": 12,
 # CHECK: "sum_all_variables(#bytes in any scope covered by DW_AT_location)": 8
 # CHECK: "sum_all_variables(#bytes in parent scope covered by DW_AT_location)": 4
 
 --- !ELF
 FileHeader:
   Class:   ELFCLASS64
   Data:    ELFDATA2LSB

llvm/tools/llvm-dwarfdump/Statistics.cpp

 
 /// This represents variables DIE offsets.
 using AbstractOriginVarsTy = llvm::SmallVector<uint64_t>;
 /// This maps function DIE offset to its variables.
 using AbstractOriginVarsTyMap = llvm::DenseMap<uint64_t, AbstractOriginVarsTy>;
 /// This represents function DIE offsets containing an abstract_origin.
 using FunctionsWithAbstractOriginTy = llvm::SmallVector<uint64_t>;
 
+/// This represents a data type for the stats and it helps us to
+/// detect an overflow.
+/// NOTE: This can be implemented as a template if there is an another type
+/// needing this.
+struct SaturatingUINT64 {
+  /// Number that represents the stats.
+  uint64_t Value;
+
+  SaturatingUINT64(uint64_t Value_) : Value(Value_) {}
+
+  void operator++(int) {
+    if (!IsOverflow) {
+      if (Value <= UINT64_MAX - 1) {
+        ++Value;
+      } else {
+        WithColor::warning(errs(), "llvm-dwarfdump --statistics")
+            << "A stat field overflow.\n";
+        Value = UINT64_MAX;
+        IsOverflow = true;
+      }
+    }
+    assert(!IsOverflow && "Stat field overflow");
+  }
+  void operator+=(uint64_t Value_) {
+    if (!IsOverflow) {
+      if (Value <= UINT64_MAX - Value_)
+        Value += Value_;
+      else {
+        WithColor::warning(errs(), "llvm-dwarfdump --statistics")
+            << "A stat field overflow.\n";
+        Value = UINT64_MAX;
+        IsOverflow = true;
+      }
+    }
+    assert(!IsOverflow && "Stat field overflow");
+  }
+
+  /// Indicate if there is an overflow.
+  bool IsOverflow = false;
+};
+
 /// Holds statistics for one function (or other entity that has a PC range and
 /// contains variables, such as a compile unit).
 struct PerFunctionStats {
   /// Number of inlined instances of this function.
-  unsigned NumFnInlined = 0;
+  uint64_t NumFnInlined = 0;
   /// Number of out-of-line instances of this function.
-  unsigned NumFnOutOfLine = 0;
+  uint64_t NumFnOutOfLine = 0;
   /// Number of inlined instances that have abstract origins.
-  unsigned NumAbstractOrigins = 0;
+  uint64_t NumAbstractOrigins = 0;
   /// Number of variables and parameters with location across all inlined
   /// instances.
-  unsigned TotalVarWithLoc = 0;
+  uint64_t TotalVarWithLoc = 0;
   /// Number of constants with location across all inlined instances.
-  unsigned ConstantMembers = 0;
+  uint64_t ConstantMembers = 0;
   /// Number of arificial variables, parameters or members across all instances.
-  unsigned NumArtificial = 0;
+  uint64_t NumArtificial = 0;
   /// List of all Variables and parameters in this function.
   StringSet<> VarsInFunction;
   /// Compile units also cover a PC range, but have this flag set to false.
   bool IsFunction = false;
   /// Function has source location information.
   bool HasSourceLocation = false;
   /// Number of function parameters.
-  unsigned NumParams = 0;
+  uint64_t NumParams = 0;
   /// Number of function parameters with source location.
-  unsigned NumParamSourceLocations = 0;
+  uint64_t NumParamSourceLocations = 0;
   /// Number of function parameters with type.
-  unsigned NumParamTypes = 0;
+  uint64_t NumParamTypes = 0;
   /// Number of function parameters with a DW_AT_location.
-  unsigned NumParamLocations = 0;
+  uint64_t NumParamLocations = 0;
   /// Number of local variables.
-  unsigned NumLocalVars = 0;
+  uint64_t NumLocalVars = 0;
   /// Number of local variables with source location.
-  unsigned NumLocalVarSourceLocations = 0;
+  uint64_t NumLocalVarSourceLocations = 0;
   /// Number of local variables with type.
-  unsigned NumLocalVarTypes = 0;
+  uint64_t NumLocalVarTypes = 0;
   /// Number of local variables with DW_AT_location.
-  unsigned NumLocalVarLocations = 0;
+  uint64_t NumLocalVarLocations = 0;
 };
 
 /// Holds accumulated global statistics about DIEs.
 struct GlobalStats {
   /// Total number of PC range bytes covered by DW_AT_locations.
-  unsigned TotalBytesCovered = 0;
+  SaturatingUINT64 TotalBytesCovered = 0;
   /// Total number of parent DIE PC range bytes covered by DW_AT_Locations.
-  unsigned ScopeBytesCovered = 0;
+  SaturatingUINT64 ScopeBytesCovered = 0;
   /// Total number of PC range bytes in each variable's enclosing scope.
-  unsigned ScopeBytes = 0;
+  SaturatingUINT64 ScopeBytes = 0;
   /// Total number of PC range bytes covered by DW_AT_locations with
   /// the debug entry values (DW_OP_entry_value).
-  unsigned ScopeEntryValueBytesCovered = 0;
+  SaturatingUINT64 ScopeEntryValueBytesCovered = 0;
   /// Total number of PC range bytes covered by DW_AT_locations of
   /// formal parameters.
-  unsigned ParamScopeBytesCovered = 0;
+  SaturatingUINT64 ParamScopeBytesCovered = 0;
   /// Total number of PC range bytes in each parameter's enclosing scope.
-  unsigned ParamScopeBytes = 0;
+  SaturatingUINT64 ParamScopeBytes = 0;
   /// Total number of PC range bytes covered by DW_AT_locations with
   /// the debug entry values (DW_OP_entry_value) (only for parameters).
-  unsigned ParamScopeEntryValueBytesCovered = 0;
+  SaturatingUINT64 ParamScopeEntryValueBytesCovered = 0;
   /// Total number of PC range bytes covered by DW_AT_locations (only for local
   /// variables).
-  unsigned LocalVarScopeBytesCovered = 0;
+  SaturatingUINT64 LocalVarScopeBytesCovered = 0;
   /// Total number of PC range bytes in each local variable's enclosing scope.
-  unsigned LocalVarScopeBytes = 0;
+  SaturatingUINT64 LocalVarScopeBytes = 0;
   /// Total number of PC range bytes covered by DW_AT_locations with
   /// the debug entry values (DW_OP_entry_value) (only for local variables).
-  unsigned LocalVarScopeEntryValueBytesCovered = 0;
+  SaturatingUINT64 LocalVarScopeEntryValueBytesCovered = 0;
   /// Total number of call site entries (DW_AT_call_file & DW_AT_call_line).
-  unsigned CallSiteEntries = 0;
+  SaturatingUINT64 CallSiteEntries = 0;
   /// Total number of call site DIEs (DW_TAG_call_site).
-  unsigned CallSiteDIEs = 0;
+  SaturatingUINT64 CallSiteDIEs = 0;
   /// Total number of call site parameter DIEs (DW_TAG_call_site_parameter).
-  unsigned CallSiteParamDIEs = 0;
+  SaturatingUINT64 CallSiteParamDIEs = 0;
   /// Total byte size of concrete functions. This byte size includes
   /// inline functions contained in the concrete functions.
-  unsigned FunctionSize = 0;
+  SaturatingUINT64 FunctionSize = 0;
   /// Total byte size of inlined functions. This is the total number of bytes
   /// for the top inline functions within concrete functions. This can help
   /// tune the inline settings when compiling to match user expectations.
-  unsigned InlineFunctionSize = 0;
+  SaturatingUINT64 InlineFunctionSize = 0;
 };
 
 /// Holds accumulated debug location statistics about local variables and
 /// formal parameters.
 struct LocationStats {
   /// Map the scope coverage decile to the number of variables in the decile.
   /// The first element of the array (at the index zero) represents the number
   /// of variables with the no debug location at all, but the last element
   /// in the vector represents the number of fully covered variables within
   /// its scope.
-  std::vector<unsigned> VarParamLocStats{
-      std::vector<unsigned>(NumOfCoverageCategories, 0)};
+  std::vector<uint64_t> VarParamLocStats{
+      std::vector<uint64_t>(NumOfCoverageCategories, 0)};
   /// Map non debug entry values coverage.
-  std::vector<unsigned> VarParamNonEntryValLocStats{
-      std::vector<unsigned>(NumOfCoverageCategories, 0)};
+  std::vector<uint64_t> VarParamNonEntryValLocStats{
+      std::vector<uint64_t>(NumOfCoverageCategories, 0)};
   /// The debug location statistics for formal parameters.
-  std::vector<unsigned> ParamLocStats{
-      std::vector<unsigned>(NumOfCoverageCategories, 0)};
+  std::vector<uint64_t> ParamLocStats{
+      std::vector<uint64_t>(NumOfCoverageCategories, 0)};
   /// Map non debug entry values coverage for formal parameters.
-  std::vector<unsigned> ParamNonEntryValLocStats{
-      std::vector<unsigned>(NumOfCoverageCategories, 0)};
+  std::vector<uint64_t> ParamNonEntryValLocStats{
+      std::vector<uint64_t>(NumOfCoverageCategories, 0)};
   /// The debug location statistics for local variables.
-  std::vector<unsigned> LocalVarLocStats{
-      std::vector<unsigned>(NumOfCoverageCategories, 0)};
+  std::vector<uint64_t> LocalVarLocStats{
+      std::vector<uint64_t>(NumOfCoverageCategories, 0)};
   /// Map non debug entry values coverage for local variables.
-  std::vector<unsigned> LocalVarNonEntryValLocStats{
-      std::vector<unsigned>(NumOfCoverageCategories, 0)};
+  std::vector<uint64_t> LocalVarNonEntryValLocStats{
+      std::vector<uint64_t>(NumOfCoverageCategories, 0)};
   /// Total number of local variables and function parameters processed.
-  unsigned NumVarParam = 0;
+  uint64_t NumVarParam = 0;
   /// Total number of formal parameters processed.
-  unsigned NumParam = 0;
+  uint64_t NumParam = 0;
   /// Total number of local variables processed.
-  unsigned NumVar = 0;
+  uint64_t NumVar = 0;
 };
 } // namespace
 
 /// Collect debug location statistics for one DIE.
 static void collectLocStats(uint64_t ScopeBytesCovered, uint64_t BytesInScope,
-                            std::vector<unsigned> &VarParamLocStats,
-                            std::vector<unsigned> &ParamLocStats,
-                            std::vector<unsigned> &LocalVarLocStats,
+                            std::vector<uint64_t> &VarParamLocStats,
+                            std::vector<uint64_t> &ParamLocStats,
+                            std::vector<uint64_t> &LocalVarLocStats,
                             bool IsParam, bool IsLocalVar) {
   auto getCoverageBucket = [ScopeBytesCovered, BytesInScope]() -> unsigned {
     // No debug location at all for the variable.
     if (ScopeBytesCovered == 0)
       return 0;
     // Fully covered variable within its scope.
     if (ScopeBytesCovered >= BytesInScope)
       return NumOfCoverageCategories - 1;
if (DWARFDie D =
     Die = D;
 
   std::string VarID = constructDieID(Die, VarPrefix);
   FnStats.VarsInFunction.insert(VarID);
 
   GlobalStats.TotalBytesCovered += TotalBytesCovered;
   if (BytesInScope) {
     GlobalStats.ScopeBytesCovered += ScopeBytesCovered;
     GlobalStats.ScopeBytes += BytesInScope;
     GlobalStats.ScopeEntryValueBytesCovered += BytesEntryValuesCovered;
     if (IsParam) {
       GlobalStats.ParamScopeBytesCovered += ScopeBytesCovered;
       GlobalStats.ParamScopeBytes += BytesInScope;
       GlobalStats.ParamScopeEntryValueBytesCovered += BytesEntryValuesCovered;
     } else if (IsLocalVar) {
       GlobalStats.LocalVarScopeBytesCovered += ScopeBytesCovered;
       GlobalStats.LocalVarScopeBytes += BytesInScope;
       GlobalStats.LocalVarScopeEntryValueBytesCovered +=
           BytesEntryValuesCovered;
     }
-    assert(GlobalStats.ScopeBytesCovered <= GlobalStats.ScopeBytes);
+    assert(GlobalStats.ScopeBytesCovered.Value <= GlobalStats.ScopeBytes.Value);
   }
 
   if (IsConstantMember) {
     FnStats.ConstantMembers++;
     return;
   }
 
   FnStats.TotalVarWithLoc += (unsigned)HasLoc;

 /// Print human-readable output.
 /// \{
 static void printDatum(json::OStream &J, const char *Key, json::Value Value) {
   J.attribute(Key, Value);
   LLVM_DEBUG(llvm::dbgs() << Key << ": " << Value << '\n');
 }
 
 static void printLocationStats(json::OStream &J, const char *Key,
-                               std::vector<unsigned> &LocationStats) {
+                               std::vector<uint64_t> &LocationStats) {
   J.attribute(
       (Twine(Key) + " with 0% of parent scope covered by DW_AT_location").str(),
       LocationStats[0]);
   LLVM_DEBUG(
       llvm::dbgs() << Key
                    << " with 0% of parent scope covered by DW_AT_location: \\"
                    << LocationStats[0] << '\n');
   J.attribute(
bool dwarfdump::collectStatsForObjectFile(ObjectFile &Obj, DWARFContext &DICtx,
 
   /// Collect the sizes of debug sections.
   SectionSizes Sizes;
   calculateSectionSizes(Obj, Sizes, Filename);
 
   /// The version number should be increased every time the algorithm is changed
   /// (including bug fixes). New metrics may be added without increasing the
   /// version.
-  unsigned Version = 8;
-  unsigned VarParamTotal = 0;
-  unsigned VarParamUnique = 0;
-  unsigned VarParamWithLoc = 0;
-  unsigned NumFunctions = 0;
-  unsigned NumInlinedFunctions = 0;
-  unsigned NumFuncsWithSrcLoc = 0;
-  unsigned NumAbstractOrigins = 0;
-  unsigned ParamTotal = 0;
-  unsigned ParamWithType = 0;
-  unsigned ParamWithLoc = 0;
-  unsigned ParamWithSrcLoc = 0;
-  unsigned LocalVarTotal = 0;
-  unsigned LocalVarWithType = 0;
-  unsigned LocalVarWithSrcLoc = 0;
-  unsigned LocalVarWithLoc = 0;
+  unsigned Version = 9;
+  uint64_t VarParamTotal = 0;
+  uint64_t VarParamUnique = 0;
+  uint64_t VarParamWithLoc = 0;
+  uint64_t NumFunctions = 0;
+  uint64_t NumInlinedFunctions = 0;
+  uint64_t NumFuncsWithSrcLoc = 0;
+  uint64_t NumAbstractOrigins = 0;
+  uint64_t ParamTotal = 0;
+  uint64_t ParamWithType = 0;
+  uint64_t ParamWithLoc = 0;
+  uint64_t ParamWithSrcLoc = 0;
+  uint64_t LocalVarTotal = 0;
+  uint64_t LocalVarWithType = 0;
+  uint64_t LocalVarWithSrcLoc = 0;
+  uint64_t LocalVarWithLoc = 0;
   for (auto &Entry : Statistics) {
     PerFunctionStats &Stats = Entry.getValue();
-    unsigned TotalVars = Stats.VarsInFunction.size() *
+    uint64_t TotalVars = Stats.VarsInFunction.size() *
                          (Stats.NumFnInlined + Stats.NumFnOutOfLine);
     // Count variables in global scope.
     if (!Stats.IsFunction)
       TotalVars =
           Stats.NumLocalVars + Stats.ConstantMembers + Stats.NumArtificial;
-    unsigned Constants = Stats.ConstantMembers;
+    uint64_t Constants = Stats.ConstantMembers;
     VarParamWithLoc += Stats.TotalVarWithLoc + Constants;
     VarParamTotal += TotalVars;
     VarParamUnique += Stats.VarsInFunction.size();
     LLVM_DEBUG(for (auto &V
                     : Stats.VarsInFunction) llvm::dbgs()
                << Entry.getKey() << ": " << V.getKey() << "\n");
     NumFunctions += Stats.IsFunction;
     NumFuncsWithSrcLoc += Stats.HasSourceLocation;
bool dwarfdump::collectStatsForObjectFile(ObjectFile &Obj, DWARFContext &DICtx,
   printDatum(J, "#inlined functions", NumInlinedFunctions);
   printDatum(J, "#inlined functions with abstract origins", NumAbstractOrigins);
 
   // This includes local variables and formal parameters.
   printDatum(J, "#unique source variables", VarParamUnique);
   printDatum(J, "#source variables", VarParamTotal);
   printDatum(J, "#source variables with location", VarParamWithLoc);
 
-  printDatum(J, "#call site entries", GlobalStats.CallSiteEntries);
-  printDatum(J, "#call site DIEs", GlobalStats.CallSiteDIEs);
-  printDatum(J, "#call site parameter DIEs", GlobalStats.CallSiteParamDIEs);
+  printDatum(J, "#call site entries", GlobalStats.CallSiteEntries.Value);
+  printDatum(J, "#call site DIEs", GlobalStats.CallSiteDIEs.Value);
+  printDatum(J, "#call site parameter DIEs",
+             GlobalStats.CallSiteParamDIEs.Value);
 
   printDatum(J, "sum_all_variables(#bytes in parent scope)",
-             GlobalStats.ScopeBytes);
+             GlobalStats.ScopeBytes.Value);
   printDatum(J,
              "sum_all_variables(#bytes in any scope covered by DW_AT_location)",
-             GlobalStats.TotalBytesCovered);
+             GlobalStats.TotalBytesCovered.Value);
   printDatum(J,
              "sum_all_variables(#bytes in parent scope covered by "
              "DW_AT_location)",
-             GlobalStats.ScopeBytesCovered);
+             GlobalStats.ScopeBytesCovered.Value);
   printDatum(J,
              "sum_all_variables(#bytes in parent scope covered by "
              "DW_OP_entry_value)",
-             GlobalStats.ScopeEntryValueBytesCovered);
+             GlobalStats.ScopeEntryValueBytesCovered.Value);
 
   printDatum(J, "sum_all_params(#bytes in parent scope)",
-             GlobalStats.ParamScopeBytes);
+             GlobalStats.ParamScopeBytes.Value);
   printDatum(J,
              "sum_all_params(#bytes in parent scope covered by DW_AT_location)",
-             GlobalStats.ParamScopeBytesCovered);
+             GlobalStats.ParamScopeBytesCovered.Value);
   printDatum(J,
              "sum_all_params(#bytes in parent scope covered by "
              "DW_OP_entry_value)",
-             GlobalStats.ParamScopeEntryValueBytesCovered);
+             GlobalStats.ParamScopeEntryValueBytesCovered.Value);
 
   printDatum(J, "sum_all_local_vars(#bytes in parent scope)",
-             GlobalStats.LocalVarScopeBytes);
+             GlobalStats.LocalVarScopeBytes.Value);
   printDatum(J,
              "sum_all_local_vars(#bytes in parent scope covered by "
              "DW_AT_location)",
-             GlobalStats.LocalVarScopeBytesCovered);
+             GlobalStats.LocalVarScopeBytesCovered.Value);
   printDatum(J,
              "sum_all_local_vars(#bytes in parent scope covered by "
              "DW_OP_entry_value)",
-             GlobalStats.LocalVarScopeEntryValueBytesCovered);
+             GlobalStats.LocalVarScopeEntryValueBytesCovered.Value);
 
-  printDatum(J, "#bytes within functions", GlobalStats.FunctionSize);
+  printDatum(J, "#bytes within functions", GlobalStats.FunctionSize.Value);
   printDatum(J, "#bytes within inlined functions",
-             GlobalStats.InlineFunctionSize);
+             GlobalStats.InlineFunctionSize.Value);
 
   // Print the summary for formal parameters.
   printDatum(J, "#params", ParamTotal);
   printDatum(J, "#params with source location", ParamWithSrcLoc);
   printDatum(J, "#params with type", ParamWithType);
   printDatum(J, "#params with binary location", ParamWithLoc);
 
   // Print the summary for local variables.
printLocationStats(J, "#local vars - entry values",
                      LocStats.LocalVarNonEntryValLocStats);
   J.objectEnd();
   OS << '\n';
   LLVM_DEBUG(
       llvm::dbgs() << "Total Availability: "
                    << (int)std::round((VarParamWithLoc * 100.0) / VarParamTotal)
                    << "%\n";
       llvm::dbgs() << "PC Ranges covered: "
-                   << (int)std::round((GlobalStats.ScopeBytesCovered * 100.0) /
-                                      GlobalStats.ScopeBytes)
+                   << (int)std::round((GlobalStats.ScopeBytesCovered.Value * 100.0) /
+                                      GlobalStats.ScopeBytes.Value)
                    << "%\n");
   return true;
 }