Skip to content

Merging: Treat inlines as if they were static when mergeInlines is off#86

Merged
michael-schwarz merged 9 commits intodevelopfrom
merge_inline_invariant
Mar 28, 2022
Merged

Merging: Treat inlines as if they were static when mergeInlines is off#86
michael-schwarz merged 9 commits intodevelopfrom
merge_inline_invariant

Conversation

@michael-schwarz
Copy link
Copy Markdown
Member

@michael-schwarz michael-schwarz commented Mar 27, 2022

This should hopefully fix all issues with merging of inlines. The logic now is as follows:

If merge_inlines is off (default), inline functions are handled as if they were static, meaning they will always be renamed. This should fix any unintended instances of multiple fundecs for one given varinfo.

@michael-schwarz michael-schwarz requested a review from sim642 March 27, 2022 12:17
@michael-schwarz michael-schwarz changed the title Merging of inlines Merging: Treat inlines as if they were static when mergeInlines is off Mar 27, 2022
@michael-schwarz michael-schwarz linked an issue Mar 27, 2022 that may be closed by this pull request
Not merging inlines breaks fundec invariant #84
Closed
@michael-schwarz
Copy link
Copy Markdown
Member Author

michael-schwarz commented Mar 27, 2022

It seems that this does indeed fix the issues. On e7121bf4c936e9790ad0644b72df1dba2a2a8459 with mergeInlines off on FFmpeg, I ran out of patience after ~600s

TOTAL                          103.047 s
  parse                          46.625 s
  convert to CIL                 56.422 s
  analysis                        0.000 s
    createCFG                      516.978 s
      handle                          1.650 s
      iter_connect                   473.773 s
        computeSCCs                    233.188 s

with this fix, createCFG terminates after ~80s.

TOTAL                          102.306 s
  parse                          46.239 s
  convert to CIL                 56.068 s
  analysis                        0.000 s
    createCFG                      77.478 s
      handle                         10.272 s
      iter_connect                   63.263 s
        computeSCCs                     5.309 s

with
cfgF (bindings=2681395 buckets=2097152 max_length=9 histo=566502,761686,488614,200968,61356,14658,2790,510,59,9 load=1.278589), cfgB (bindings=2670407 buckets=2097152 max_length=9 histo=569323,763227,486315,200119,60610,14216,2819,440,68,15 load=1.273350)

This interestingly is still an order of magnitude slower than with mergeInlines on,

TOTAL                          103.190 s
  parse                          46.476 s
  convert to CIL                 56.714 s
  analysis                        0.000 s
    createCFG                       7.516 s
      handle                          2.453 s
      iter_connect                    4.487 s
        computeSCCs                     1.484 s

with

cfgF (bindings=829707 buckets=524288 max_length=9 histo=107465,170628,135133,71058,28129,8921,2283,562,95,14 load=1.582541), cfgB (bindings=829631 buckets=524288 max_length=9 histo=107450,170648,135211,71016,28104,8843,2360,545,92,19 load=1.582396).

Aside: I might also try to script some walltime comparison, to see how much of a difference it makes overall (the CIL times reported above do not seem accurate, I think it accounts only for parts of process), as the merging of inlines is supposed to make CIL an order of magnitude slower.

Regardless, I am pretty sure, we have now fixed the broken invariant.

@michael-schwarz
Copy link
Copy Markdown
Member Author

michael-schwarz commented Mar 27, 2022

Actually, all that was needed to get better number is wrapping the merging into a call to Stas.time inside Goblint.

@michael-schwarz
Copy link
Copy Markdown
Member Author

michael-schwarz commented Mar 27, 2022

With merging of inlines:

  mergeCIL                       285.114 s
  analysis                        0.000 s
    createCFG                      14.989 s
      handle                          4.853 s
      iter_connect                    8.983 s
        computeSCCs                     4.394 s

Without it:

  mergeCIL                       66.626 s
  analysis                        0.000 s
    createCFG                      71.905 s
      handle                          9.731 s
      iter_connect                   57.776 s
        computeSCCs                     7.778 s

So it looks like it buys us 2x speedup to not merge inlines (at least until the start of analysis).

@michael-schwarz michael-schwarz mentioned this pull request Mar 28, 2022
Merged
sim642
sim642 reviewed Mar 28, 2022
View reviewed changes
michael-schwarz and others added 2 commits March 28, 2022 09:33
@michael-schwarz @sim642
Clarify condition
78fbc13 
Co-authored-by: Simmo Saan <simmo.saan@gmail.com>
@michael-schwarz
Fix indentation
bc9a707
@michael-schwarz michael-schwarz merged commit 6998436 into develop Mar 28, 2022
@sim642 sim642 deleted the merge_inline_invariant branch May 30, 2022 07:12
@sim642 sim642 added this to the 2.0.0 milestone Aug 12, 2022
sim642 added a commit to sim642/opam-repository that referenced this pull request Aug 12, 2022
@sim642
[new release] goblint-cil (2.0.0)
a9c997a 
CHANGES:

* Wrap library into `GoblintCil` module (goblint/cil#107).
* Remove all MSVC support (goblint/cil#52, goblint/cil#88).
* Port entire build process from configure/make to dune (goblint/cil#104).
* Add C11 `_Generic` support (goblint/cil#48).
* Add C11 `_Noreturn` support (goblint/cil#58).
* Add C11 `_Static_assert` support (goblint/cil#62).
* Add C11 `_Alignof` support (goblint/cil#66).
* Add C11 `_Alignas` support (goblint/cil#93, goblint/cil#108).
* Add partial C11 `_Atomic` support (goblint/cil#61).
* Add `_Float32`, `_Float64`, `_Float32x` and `_Float64x` type support (goblint/cil#8, goblint/cil#60).
* Add Universal Character Names, `char16_t` and `char32_t` type support (goblint/cil#80).
* Change locations to location spans and add additional expression locations (goblint/cil#51).
* Add synthetic marking for CIL-inserted statement locations (goblint/cil#98).
* Expose list of files from line control directives (goblint/cil#73).
* Add parsed location transformation hook (goblint/cil#89).
* Use Zarith for integer constants (goblint/cil#47, goblint/cil#53).
* Fix constant folding overflows (goblint/cil#59).
* Add option to disable constant branch removal (goblint/cil#103).
* Add standalone expression parsing and checking (goblint/cil#97, goblint/cil#96).
* Improve inline function merging (goblint/cil#72, goblint/cil#85, goblint/cil#84, goblint/cil#86).
* Fix some attribute parsing cases (goblint/cil#71, goblint/cil#75, goblint/cil#76, goblint/cil#77).
* Fix global NaN initializers (goblint/cil#78, goblint/cil#79).
* Fix `cilly` binary installation (goblint/cil#99, goblint/cil#100, goblint/cil#102).
* Remove batteries dependency to support OCaml 5 (goblint/cil#106).
@sim642 sim642 mentioned this pull request Aug 12, 2022
Merged
sim642 added a commit to sim642/opam-repository that referenced this pull request Aug 12, 2022
@sim642
[new release] goblint-cil (2.0.0)
fb70853 
CHANGES:

* Wrap library into `GoblintCil` module (goblint/cil#107).
* Remove all MSVC support (goblint/cil#52, goblint/cil#88).
* Port entire build process from configure/make to dune (goblint/cil#104).
* Add C11 `_Generic` support (goblint/cil#48).
* Add C11 `_Noreturn` support (goblint/cil#58).
* Add C11 `_Static_assert` support (goblint/cil#62).
* Add C11 `_Alignof` support (goblint/cil#66).
* Add C11 `_Alignas` support (goblint/cil#93, goblint/cil#108).
* Add partial C11 `_Atomic` support (goblint/cil#61).
* Add `_Float32`, `_Float64`, `_Float32x` and `_Float64x` type support (goblint/cil#8, goblint/cil#60).
* Add Universal Character Names, `char16_t` and `char32_t` type support (goblint/cil#80).
* Change locations to location spans and add additional expression locations (goblint/cil#51).
* Add synthetic marking for CIL-inserted statement locations (goblint/cil#98).
* Expose list of files from line control directives (goblint/cil#73).
* Add parsed location transformation hook (goblint/cil#89).
* Use Zarith for integer constants (goblint/cil#47, goblint/cil#53).
* Fix constant folding overflows (goblint/cil#59).
* Add option to disable constant branch removal (goblint/cil#103).
* Add standalone expression parsing and checking (goblint/cil#97, goblint/cil#96).
* Improve inline function merging (goblint/cil#72, goblint/cil#85, goblint/cil#84, goblint/cil#86).
* Fix some attribute parsing cases (goblint/cil#71, goblint/cil#75, goblint/cil#76, goblint/cil#77).
* Fix global NaN initializers (goblint/cil#78, goblint/cil#79).
* Fix `cilly` binary installation (goblint/cil#99, goblint/cil#100, goblint/cil#102).
* Remove batteries dependency to support OCaml 5 (goblint/cil#106).
@sim642 sim642 mentioned this pull request May 18, 2023
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@sim642 sim642 sim642 approved these changes

@stilscher stilscher Awaiting requested review from stilscher

Assignees

No one assigned

Labels

bug

Projects

None yet

Milestone

2.0.0

Development

Successfully merging this pull request may close these issues.

Not merging inlines breaks fundec invariant

2 participants

@michael-schwarz @sim642