Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Improve performance of parseModuleBlockEntry.unnamedGlobalsCount #178

Closed
Ptival opened this issue Oct 28, 2021 · 0 comments
Closed

Improve performance of parseModuleBlockEntry.unnamedGlobalsCount #178

Ptival opened this issue Oct 28, 2021 · 0 comments
Assignees
@Ptival

Comments

@Ptival
Copy link
Contributor

Ptival commented Oct 28, 2021

As part of my exploration of #176 , I have found that an enormous amount of time is spent computing:

llvm-pretty-bc-parser/src/Data/LLVM/BitCode/IR/Module.hs

Line 138 in daffc92

let unnamedGlobalsCount = length (partialUnnamedMd pm)

image
(Notice the somewhat large block on the right)

On my example, we repeatedly compute the length of this list while it is holding about 300k elements!

While I will need to investigate a little more to make sure that we indeed need to compute this length that frequently, I have also attempted a successful replacement of that list with a Data.Sequence, a more strict data type that has constant access to its length.

image
(It's hard to notice, but that huge block is now a tiny dark red block, all other blocks are expanded as a result to fit the same width)

On my example benchmark, the fix makes the total run go from 196 seconds down to 143 seconds.
@Ptival Ptival self-assigned this Oct 28, 2021
Ptival added a commit that referenced this issue Oct 28, 2021
@Ptival
use Seq over list in PartialModule (fixes #178)
14775cd
@Ptival Ptival closed this as completed in 062dc02 Oct 28, 2021
RyanGlScott added a commit to GaloisInc/crucible that referenced this issue Dec 5, 2021
@RyanGlScott
Bump llvm-pretty{-bc-parser} submodules, adapt to ValPoison
bad01d0 
This bumps the `llvm-pretty` submodule to bring in the following PRs:

* GaloisInc/llvm-pretty#86 (support LLVM 11 `IsDefault` fields in metadata)
* GaloisInc/llvm-pretty#87 (Relax the Symbol requirement to `ConstBlockAddr`)
* GaloisInc/llvm-pretty#88 (add LLVM12 poison value)

This also bumps the `llvm-pretty-bc-parser` submodule to bring in the
following PRs:

* GaloisInc/llvm-pretty-bc-parser#171 (don't consume fast math flag entry)
* GaloisInc/llvm-pretty-bc-parser#169 (make `getBitString` assumptions explicit)
* GaloisInc/llvm-pretty-bc-parser#168 (support for LLVM 11 `IsDefault` fields in metadata)
* GaloisInc/llvm-pretty-bc-parser#170 (remove `Aligned` from `SubWord`)
* GaloisInc/llvm-pretty-bc-parser#172 (fix BLOCKADDRESS parsing)
* GaloisInc/llvm-pretty-bc-parser#173 (parse LLVM12 poison value)
* GaloisInc/llvm-pretty-bc-parser#178 (use Seq over list in PartialModule)

Of these, the only PR that requires code changes in Crucible is
GaloisInc/llvm-pretty#88 (add LLVM12 poison value), as this adds a new
`ValPoison` constructor to `Value'`. Properly handling LLVM poison is a large
task that I do not wish to tackle here (see #366 for discussion of how one
might do this). For now, this PR does the bare minimum:

* In `Lang.Crucible.LLVM.Translation.BlockInfo.useVal`, treat `ValPoison`
  as not referencing any identifiers.
* The other two potential sites where `ValPoison` could be matched on are in
  `Lang.Crucible.LLVM.Translation.Constant.transConstant'` and
  `Lang.Crucible.LLVM.Translation.Expr.transValue`. Since we are not handling
  `ValPoison` for now, both of these functions will simply error if they
  encounter `ValPoison`.
* I have added a section to `crucible-llvm`'s `limitations.md` document which
  describes the above limitations of poison handling.
RyanGlScott added a commit to GaloisInc/crucible that referenced this issue Dec 6, 2021
@RyanGlScott
Bump llvm-pretty{-bc-parser} submodules, adapt to ValPoison
1796854 
This bumps the `llvm-pretty` submodule to bring in the following PRs:

* GaloisInc/llvm-pretty#86 (support LLVM 11 `IsDefault` fields in metadata)
* GaloisInc/llvm-pretty#87 (Relax the Symbol requirement to `ConstBlockAddr`)
* GaloisInc/llvm-pretty#88 (add LLVM12 poison value)
* GaloisInc/llvm-pretty#90 (Support structs with bitfields in `Text.LLVM.DebugUtils`)

This also bumps the `llvm-pretty-bc-parser` submodule to bring in the
following PRs:

* GaloisInc/llvm-pretty-bc-parser#171 (don't consume fast math flag entry)
* GaloisInc/llvm-pretty-bc-parser#169 (make `getBitString` assumptions explicit)
* GaloisInc/llvm-pretty-bc-parser#168 (support for LLVM 11 `IsDefault` fields in metadata)
* GaloisInc/llvm-pretty-bc-parser#170 (remove `Aligned` from `SubWord`)
* GaloisInc/llvm-pretty-bc-parser#172 (fix BLOCKADDRESS parsing)
* GaloisInc/llvm-pretty-bc-parser#173 (parse LLVM12 poison value)
* GaloisInc/llvm-pretty-bc-parser#178 (use Seq over list in PartialModule)

Of these, the only PR that requires code changes in Crucible is
GaloisInc/llvm-pretty#88 (add LLVM12 poison value), as this adds a new
`ValPoison` constructor to `Value'`. Properly handling LLVM poison is a large
task that I do not wish to tackle here (see #366 for discussion of how one
might do this). For now, this PR does the bare minimum:

* In `Lang.Crucible.LLVM.Translation.BlockInfo.useVal`, treat `ValPoison`
  as not referencing any identifiers.
* The other two potential sites where `ValPoison` could be matched on are in
  `Lang.Crucible.LLVM.Translation.Constant.transConstant'` and
  `Lang.Crucible.LLVM.Translation.Expr.transValue`. Since we are not handling
  `ValPoison` for now, both of these functions will simply error if they
  encounter `ValPoison`.
* I have added a section to `crucible-llvm`'s `limitations.md` document which
  describes the above limitations of poison handling.
@RyanGlScott RyanGlScott mentioned this issue Dec 6, 2021
Merged
RyanGlScott added a commit to GaloisInc/crucible that referenced this issue Dec 6, 2021
@RyanGlScott
Bump llvm-pretty{-bc-parser} submodules, adapt to ValPoison (#936)
acd37d5 
This bumps the `llvm-pretty` submodule to bring in the following PRs:

* GaloisInc/llvm-pretty#86 (support LLVM 11 `IsDefault` fields in metadata)
* GaloisInc/llvm-pretty#87 (Relax the Symbol requirement to `ConstBlockAddr`)
* GaloisInc/llvm-pretty#88 (add LLVM12 poison value)
* GaloisInc/llvm-pretty#90 (Support structs with bitfields in `Text.LLVM.DebugUtils`)

This also bumps the `llvm-pretty-bc-parser` submodule to bring in the
following PRs:

* GaloisInc/llvm-pretty-bc-parser#171 (don't consume fast math flag entry)
* GaloisInc/llvm-pretty-bc-parser#169 (make `getBitString` assumptions explicit)
* GaloisInc/llvm-pretty-bc-parser#168 (support for LLVM 11 `IsDefault` fields in metadata)
* GaloisInc/llvm-pretty-bc-parser#170 (remove `Aligned` from `SubWord`)
* GaloisInc/llvm-pretty-bc-parser#172 (fix BLOCKADDRESS parsing)
* GaloisInc/llvm-pretty-bc-parser#173 (parse LLVM12 poison value)
* GaloisInc/llvm-pretty-bc-parser#178 (use Seq over list in PartialModule)

Of these, the only PR that requires code changes in Crucible is
GaloisInc/llvm-pretty#88 (add LLVM12 poison value), as this adds a new
`ValPoison` constructor to `Value'`. Properly handling LLVM poison is a large
task that I do not wish to tackle here (see #366 for discussion of how one
might do this). For now, this PR does the bare minimum:

* In `Lang.Crucible.LLVM.Translation.BlockInfo.useVal`, treat `ValPoison`
  as not referencing any identifiers.
* The other two potential sites where `ValPoison` could be matched on are in
  `Lang.Crucible.LLVM.Translation.Constant.transConstant'` and
  `Lang.Crucible.LLVM.Translation.Expr.transValue`. Since we are not handling
  `ValPoison` for now, both of these functions will simply error if they
  encounter `ValPoison`.
* I have added a section to `crucible-llvm`'s `limitations.md` document which
  describes the above limitations of poison handling.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@Ptival Ptival

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@Ptival