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

updates the Sub.compute_liveness function to handle SSA form #1445

Merged
merged 1 commit into from
Mar 11, 2022
Merged

updates the Sub.compute_liveness function to handle SSA form #1445

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
13 changes: 13 additions & 0 deletions lib/bap/bap.mli
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -8529,7 +8529,20 @@ module Std : sig
whole subroutine is the set of variables that are live at the
[Graphs.Tid.start] node.

When the subroutine is in the SSA form then the phi-nodes have
the following semantics. For a phi-node at block [b0],
[x0 := phi([b1,x1; b2,x2;...;bN,xN])], the defined variable
[x0] is considered to be at the entry of [b0], i.e., [x0] is
live-in of [b0], and the variable [xi] is live-out of basic
block [bi], for [i > 0].

Informally, a phi-node defines the values on the corresponding
edges of the predecessors.


@since 2.1
@since 2.5.0 supports SSA
@before 2.5.0 the subroutine must not be in the SSA form
*)
val compute_liveness : t -> (tid, Var.Set.t) Solution.t

Expand Down
21 changes: 17 additions & 4 deletions lib/bap_sema/bap_sema_free_vars.ml
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -30,13 +30,26 @@ let blk_defs blk =
Seq.fold ~init:Var.Set.empty ~f:(fun defs def ->
Set.add defs (Ir_def.lhs def))

let update blk defs uses trans = Map.update trans blk ~f:(function
| None -> {defs; uses}
| Some had -> {
defs = Set.union had.defs defs;
uses = Set.union had.uses uses
})

let block_transitions sub =
Term.enum blk_t sub |>
Seq.fold ~init:Tid.Map.empty ~f:(fun fs blk ->
Map.add_exn fs (Term.tid blk) {
defs = blk_defs blk;
uses = Ir_blk.free_vars blk;
})
let init = update
(Term.tid blk)
(blk_defs blk)
(Ir_blk.free_vars blk) fs in
Term.enum phi_t blk |>
Seq.fold ~init ~f:(fun init phi ->
let defs = Var.Set.singleton @@ Ir_phi.lhs phi in
Ir_phi.values phi |>
Seq.fold ~init ~f:(fun fs (src,exp) ->
update src defs (Exp.free_vars exp) fs)))

let compute_liveness sub =
let g = G.create sub in
Expand Down