makes dead code elimination less conservative (#906)

* maked dead code elimination less conservative 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 * makes it sound 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. * removes a dead function note: this PR shall be merged after #907 is merged * drops debug info * drops a change that is irrelevant to the proposal to make it cleaner
BinaryAnalysisPlatform · Dec 11, 2018 · ed57d9a · ed57d9a
1 parent 6ac0793
commit ed57d9a
Showing 1 changed file with 11 additions and 7 deletions.
diff --git a/plugins/optimization/optimization_main.ml b/plugins/optimization/optimization_main.ml
@@ -42,13 +42,17 @@ let compute_dead can_touch protected sub =
   let defs,uses = computed_def_use sub in
   let dead = Set.diff defs uses in
   let live v = not (Set.mem dead v) in
-  (object inherit [Tid.Set.t] Term.visitor
-    method! enter_def t dead =
-      let v = Def.lhs t in
-      if not (can_touch v) || Set.mem protected (Var.base v) || live v
-      then dead
-      else Set.add dead (Term.tid t)
-  end)#visit_sub sub Tid.Set.empty
+  Term.enum blk_t sub |>
+  Seq.fold ~init:Tid.Set.empty ~f:(fun dead blk ->
+      Term.enum ~rev:true def_t blk |>
+      Seq.fold ~init:(protected,dead) ~f:(fun (protected,dead) def ->
+          let v = Def.lhs def in
+          if not (can_touch v) || live v
+          then (protected,dead)
+          else if Set.mem protected (Var.base v)
+          then Set.remove protected (Var.base v), dead
+          else protected, Set.add dead (Term.tid def)) |>
+      snd)
 
 let is_alive dead t = not (Set.mem dead (Term.tid t))
 let live_phi dead blk = Term.filter phi_t ~f:(is_alive dead) blk