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.

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

makes dead code elimination less conservative #906

Merged

Conversation

ivg
Copy link
Member

@ivg ivg commented Dec 11, 2018

As was noted in #905 the optimization passes sometimes misses an
opportunity to remove obvious assignments. The underlying reason
is that we compute a very conservative set of variables which are
used for interprocedural communication. And if a variable is a
member of this set then we do not delete it (under assumption, that
it could be used in other subroutines).

What was overconservative is that all versions of the same variable
were protected, while only the last definition one could be used for
interprocedural communication. The propsed change relaxes the
protected set, and removes only the last version of a variable from
the set of the dead variables.

Fixes #905

As was noted in BinaryAnalysisPlatform#905 the optimization passes sometimes misses an
opportunity to remove obvious assignments. The underlying reason
is that we compute a very conservative set of variables which are
used for interprocedural communication. And if a variable is a
member of this set then we do not delete it (under assumption, that
it could be used in other subroutines).

What was overconservative is that all versions of the same variable
were protected, while only the last definition one could be used for
interprocedural communication. The propsed change relaxes the
protected set, and removes only the last version of a variable from
the set of the dead variables.

Fixes BinaryAnalysisPlatform#905
ivg added 2 commits December 11, 2018 11:10
Unfortunately, the original proposal was unsound, as the assumption
that only the last definition should be preserved is implied by the
assumption that only the last definition is used for interprocedural
communication, which is totally wrong.

The liveness property is propagated from each call (and indirect jump)
to all members of the protected set. We're using the SSA form for
def-use analysis which is inherently intraprocedural, so to preserve
the liveness of the variables with the interprocedural scope we use
the protected set as an overapproximation.  A tighter approximation
would be to reinstantiate their liveness after each call or indirect
jump. However, this would require tampering with the ssa algorithm,
that we don't want to do right now.

The updated solution reinstantiates liveness of protected variables
at the end of each block, even the block is not a call or even jump.
The liveness is killed by the first use of protection, so it is
propagated only to the last (if any) definition.
note: this PR shall be merged after BinaryAnalysisPlatform#907 is merged
@@ -38,17 +38,30 @@ end
let computed_def_use sub =
def_use_collector#visit_sub sub (Var.Set.empty,Var.Set.empty)

let protect dead protected =
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

dead code elimination requested)

@gitoleg gitoleg merged commit ed57d9a into BinaryAnalysisPlatform:master Dec 11, 2018
@ivg ivg deleted the relax-dead-code-elimination branch December 1, 2021 19:12
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants