Module: Laser::Analysis::ControlFlow::UnreachabilityAnalysis

Included in:
ControlFlowGraph
Defined in:
lib/laser/analysis/control_flow/unreachability_analysis.rb

Constant Summary

IGNORED_DEAD_CODE_NODES =

Dead Code Discovery: O(|V| + |E|)!

[:@ident, :@op, :void_stmt]

Instance Method Summary (collapse)

Instance Method Details

- (Object) dfs_for_dead_code(node)

Performs a simple DFS, adding errors to any nodes that are still marked unreachable.



43
44
45
46
47
48
49
50
51
52
53
# File 'lib/laser/analysis/control_flow/unreachability_analysis.rb', line 43

def dfs_for_dead_code(node)
  if node.reachable
    node.children.select { |x| Sexp === x }.reject do |child|
      child == [] || child[0].is_a?(::Fixnum) || IGNORED_DEAD_CODE_NODES.include?(child.type)
    end.each do |child|
      dfs_for_dead_code(child)
    end
  else
    node.add_error DeadCodeWarning.new('Dead code', node)
  end
end

- (Object) perform_dead_code_discovery(delete_dead = false)



11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# File 'lib/laser/analysis/control_flow/unreachability_analysis.rb', line 11

def perform_dead_code_discovery(delete_dead=false)
  dfst = depth_first_spanning_tree(self.enter)

  dead_verts = unreachable_vertices(dfst)

  # then, go over all code in dead blocks, and mark potentially dead
  # ast nodes.
  # O(V)
  dead_verts.each do |blk|
    blk.instructions.each { |ins| ins.node.reachable = false if ins.node  }
  end

  # run through all reachable statements and mark those nodes, and their
  # parents, as partially executing.
  #
  # at most |V| nodes will have cur.reachable = true set.
  # at most O(V) instructions will be visited total.
  dfst.each_vertex do |blk|
    blk.instructions.each do |ins|
      cur = ins.node
      while cur
        cur.reachable = true
        cur = cur.parent
      end
    end
  end
  dfs_for_dead_code self.root
  dead_verts.each { |block| remove_vertex block } if delete_dead
end

- (Object) unreachable_vertices(dfst = depth_first_spanning_tree(self.enter))



7
8
9
# File 'lib/laser/analysis/control_flow/unreachability_analysis.rb', line 7

def unreachable_vertices(dfst = depth_first_spanning_tree(self.enter))
  vertices - dfst.vertices
end