Class: Laser::Analysis::ControlFlow::ControlFlowGraph

Inherits:
RGL::ControlFlowGraph show all
Includes:
AliasAnalysis, ConstantPropagation, GuaranteedSuperDetection, LifetimeAnalysis, MethodCallSearch, RaiseProperties, Simulation, StaticSingleAssignment, UnreachabilityAnalysis, UnusedVariables, YieldProperties
Defined in:
lib/laser/analysis/control_flow/control_flow_graph.rb

Constant Summary

RETURN_POSTDOMINATOR_NAME = 
'Return'
YIELD_POSTDOMINATOR_NAME = 
'YieldWithoutBlock'
EXCEPTION_POSTDOMINATOR_NAME = 
'UncaughtException'
FAILURE_POSTDOMINATOR_NAME = 
'Failure'
DEFAULT_ANALYSIS_OPTS = 
{optimize: true, simulate: true}

Constants included from Simulation

Simulation::DEFAULT_SIMULATION_OPTS, Simulation::MAX_SIMULATION_BLOCKS

Constants included from UnreachabilityAnalysis

UnreachabilityAnalysis::IGNORED_DEAD_CODE_NODES

Constants included from UnusedVariables

UnusedVariables::IGNORED_VARS

Constants inherited from RGL::ControlFlowGraph

RGL::ControlFlowGraph::EDGE_ABNORMAL, RGL::ControlFlowGraph::EDGE_BLOCK_TAKEN, RGL::ControlFlowGraph::EDGE_EXECUTABLE, RGL::ControlFlowGraph::EDGE_FAKE, RGL::ControlFlowGraph::EDGE_NORMAL

Instance Attribute Summary (collapse)

Attributes inherited from RGL::ControlFlowGraph

#enter, #exit, #vertex_lookup, #vertices

Instance Method Summary (collapse)

Methods included from GuaranteedSuperDetection

#guaranteed_super_on_success?

Methods included from Simulation

#reset_simulation!, #should_simulate_call, #simulate, #simulate_args, #simulate_assignment, #simulate_block, #simulate_call, #simulate_call_dispatch, #simulate_call_instruction, #simulate_define_method, #simulate_deterministic_phi_node, #simulate_exit_instruction, #simulate_instruction, #simulate_method_missing, #simulate_module_eval, #simulate_require, #simulate_special_method, #simulate_take_step

Methods included from RaiseProperties

#find_raise_frequency, #find_raise_properties

Methods included from MethodCallSearch

#find_method_calls

Methods included from YieldProperties

#calculate_yield_arity, #compute_yield_type, #find_yield_properties, #initial_block_aliases, #potential_block_calls

Methods included from AliasAnalysis

#value_aliases, #weak_local_aliases_for

Methods included from UnreachabilityAnalysis

#dfs_for_dead_code, #perform_dead_code_discovery, #unreachable_vertices

Methods included from UnusedVariables

#add_unused_variable_warnings, #killable_with_unused_target?, #simple_unused, #unused_variables

Methods included from StaticSingleAssignment

#static_single_assignment_form

Methods included from LifetimeAnalysis

#calculate_live

Methods included from ConstantPropagation

#perform_constant_propagation

Methods inherited from RGL::ControlFlowGraph

#[], #add_edge, #add_flag, #add_vertex, #degree, #directed?, #each_adjacent, #each_edge, #each_vertex, #edges, #empty?, #has_edge?, #has_vertex?, #in_degree, #is_abnormal?, #is_block_taken?, #is_executable?, #is_fake?, #num_edges, #num_vertices, #out_degree, #remove_edge, #remove_flag, #remove_vertex, #to_a, #vertex_with_name

Methods included from RGL::MutableGraph

#add_edge, #add_edges, #add_graph, #add_graphs, #add_vertex, #add_vertices, #cycles, #cycles_with_vertex, #from_graphxml, #remove_edge, #remove_vertex, #remove_vertices

Methods included from RGL::Graph

#acyclic?, #adjacent_vertices, #bfs_iterator, #bfs_search_tree_from, #build_dfst, #condensation_graph, #depth_first_search, #depth_first_spanning_tree, #depth_first_visit, #dfs_iterator, #directed?, #dominance_frontier, #dominator_tree, #each, #each_adjacent, #each_connected_component, #each_edge, #each_vertex, #edge_class, #edges, #edges_filtered_by, #empty?, #eql?, #has_vertex?, #implicit_graph, #iterated_dominance_frontier, #num_edges, #out_degree, #print_dotted_on, #reverse, #size, #strongly_connected_components, #to_adjacency, #to_dot_graph, #to_s, #to_undirected, #topsort_iterator, #transitive_closure, #transitive_reduction, #vertices, #vertices_filtered_by, #write_to_graphic_file

Methods included from Enumerable

#all?, #any?, #chunk, #collect, #collect_concat, #count, #cycle, #detect, #drop, #drop_while, #each_cons, #each_entry, #each_slice, #each_with_index, #each_with_object, #entries, #find_index, #first, #flat_map, #grep, #group_by, #include?, #inject, #map, #max, #max_by, #min, #min_by, #minmax, #minmax_by, #none?, #one?, #partition, #reject, #reverse_each, #select, #slice_before, #sort, #sort_by, #take, #take_while, #to_a, #to_set, #zip

Constructor Details

- (ControlFlowGraph) initialize(formal_arguments = [])

Initializes the control flow graph, potentially with a list of argument bindings. Those bindings will almost always be extracted from parsing an argument list of a method or block.

formal_arguments: [ArgumentBinding]



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 38

def initialize(formal_arguments = [])
  @in_ssa = false
  @self_type = nil
  @formal_types = nil
  @block_type = nil
  @block_register = nil
  @all_cached_variables = Set.new
  @live = Hash.new { |hash, temp| hash[temp] = Set.new }
  @constants  = {}
  @globals = Set.new
  @name_stack = Hash.new { |hash, temp| hash[temp] = [] }
  @name_count = Hash.new { |hash, temp| hash[temp] = 0 }
  @formals = formal_arguments
  @yield_type = nil
  @yield_arity = nil
  @raise_frequency = Frequency::MAYBE
  @analyzed = false
  super()
end

Instance Attribute Details

- (Object) all_cached_variables (readonly)

Returns the value of attribute all_cached_variables



29
30
31
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 29

def all_cached_variables
  @all_cached_variables
end

- (Object) analyzed (readonly)

Returns the value of attribute analyzed



29
30
31
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 29

def analyzed
  @analyzed
end

- (Object) block_register

Returns the value of attribute block_register



25
26
27
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 25

def block_register
  @block_register
end

- (Object) block_type (readonly)

Returns the value of attribute block_type



28
29
30
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 28

def block_type
  @block_type
end

- (Object) constants (readonly)

Returns the value of attribute constants



26
27
28
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 26

def constants
  @constants
end

- (Object) definition (readonly)

Returns the value of attribute definition



26
27
28
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 26

def definition
  @definition
end

- (Object) final_exception

Returns the value of attribute final_exception



25
26
27
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 25

def final_exception
  @final_exception
end

- (Object) final_return

Returns the value of attribute final_return



25
26
27
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 25

def final_return
  @final_return
end

- (Object) formal_types (readonly)

Returns the value of attribute formal_types



28
29
30
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 28

def formal_types
  @formal_types
end

- (Object) formals (readonly)

Returns the value of attribute formals



26
27
28
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 26

def formals
  @formals
end

- (Object) globals (readonly)

Returns the value of attribute globals



26
27
28
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 26

def globals
  @globals
end

- (Object) in_ssa (readonly)

Returns the value of attribute in_ssa



27
28
29
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 27

def in_ssa
  @in_ssa
end

- (Object) live (readonly)

Returns the value of attribute live



26
27
28
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 26

def live
  @live
end

- (Object) raise_frequency (readonly)

Returns the value of attribute raise_frequency



27
28
29
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 27

def raise_frequency
  @raise_frequency
end

- (Object) root

Returns the value of attribute root



25
26
27
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 25

def root
  @root
end

- (Object) self_type (readonly)

Returns the value of attribute self_type



28
29
30
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 28

def self_type
  @self_type
end

- (Object) uses (readonly)

Returns the value of attribute uses



26
27
28
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 26

def uses
  @uses
end

- (Object) yield_arity (readonly)

Returns the value of attribute yield_arity



27
28
29
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 27

def yield_arity
  @yield_arity
end

- (Object) yield_type (readonly)

Returns the value of attribute yield_type



27
28
29
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 27

def yield_type
  @yield_type
end

Instance Method Details

- (Object) ==(other)

Compares the graphs for equality. Relies on the basic blocks having unique names to simplify isomorphism comparisons. Unfortunately this means tests will have to know block names. Oh well.



133
134
135
136
137
138
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 133

def ==(other)
  pairs = self.vertices.sort_by(&:name).zip(other.vertices.sort_by(&:name))
  (pairs.all? do |v1, v2|
    v1.name == v2.name && v1.instructions == v2.instructions
  end) && (self.edges.sort == other.edges.sort)
end

- (Object) all_errors 



268
269
270
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 268

def all_errors
  self.root.all_errors
end

- (Object) all_failure_postdominator 



301
302
303
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 301

def all_failure_postdominator
  vertex_with_name(FAILURE_POSTDOMINATOR_NAME)
end

- (Object) all_variables

Returns the names of all variables in the graph



273
274
275
276
277
278
279
280
281
282
283
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 273

def all_variables
  return @all_cached_variables unless @all_cached_variables.empty?
  return @all_variables if @all_variables
  result = Set.new
  vertices.each do |vert|
    vert.variables.each do |var|
      result << var
    end
  end
  @all_variables = result
end

- (Object) analyze(opts = {})

Runs full analysis on the CFG. Puts it in SSA then searches for warnings.



214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 214

def analyze(opts={})
  return if @analyzed
  @analyzed = true

  opts = DEFAULT_ANALYSIS_OPTS.merge(opts)
  # kill obvious dead code now.
  perform_dead_code_discovery(true)
  Laser.debug_puts('>>> Starting SSA Transformation <<<')
  static_single_assignment_form unless @in_ssa
  Laser.debug_puts('>>> Finished SSA Transformation <<<')
  if @root.type == :program
    Laser.debug_puts('>>> Starting Simulation <<<')
    begin
      simulate([], :mutation => true) if opts[:simulate]
    rescue Simulation::NonDeterminismHappened => err
      Laser.debug_puts('Note: Simulation was nondeterministic.')
    rescue Simulation::SimulationNonterminationError => err
      Laser.debug_puts('Note: Simulation was potentially nonterminating.')
    end
    Laser.debug_puts('>>> Finished Simulation <<<')
  else
    Laser.debug_puts('>>> Starting CP <<<')
    perform_constant_propagation(opts)
    Laser.debug_puts('>>> Finished CP <<<')
    if opts[:optimize]
      Laser.debug_puts('>>> Killing Unexecuted Edges <<<')
      kill_unexecuted_edges
      Laser.debug_puts('>>> Finished Killing Unexecuted Edges <<<')
      Laser.debug_puts('>>> Pruning Totally Useless Blocks <<<')
      prune_totally_useless_blocks
      Laser.debug_puts('>>> Finished Pruning Totally Useless Blocks <<<')
      Laser.debug_puts('>>> Dead Code Discovery <<<')
      perform_dead_code_discovery
      Laser.debug_puts('>>> Finished Dead Code Discovery <<<')
      Laser.debug_puts('>>> Adding Unused Variable Warnings <<<')
      add_unused_variable_warnings
      Laser.debug_puts('>>> Finished Adding Unused Variable Warnings <<<')

      if @root.type != :program
        Laser.debug_puts('>>> Determining Yield Properties <<<')
        find_yield_properties(opts)
        Laser.debug_puts('>>> Finished Determining Yield Properties <<<')
      end
      Laser.debug_puts('>>> Determining Raise Properties <<<')
      find_raise_properties
      Laser.debug_puts('>>> Finished Determining Raise Properties <<<')
    end
  end
end

- (Object) bind_block_type(new_block_type) 



208
209
210
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 208

def bind_block_type(new_block_type)
  @block_type = new_block_type
end

- (Object) bind_formal_types(new_formal_types) 



200
201
202
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 200

def bind_formal_types(new_formal_types)
  @formal_types = new_formal_types
end

- (Object) bind_self_type(new_self_type) 



184
185
186
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 184

def bind_self_type(new_self_type)
  @self_type = new_self_type
end

- (Boolean) bound_argument_types?

Returns:

  • (Boolean) 


188
189
190
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 188

def bound_argument_types?
  !!@formal_types
end

- (Object) bound_arity 



192
193
194
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 192

def bound_arity
  @formal_types.size
end

- (Object) clear_analyses 



144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 144

def clear_analyses
  all_variables.each do |temp|
    temp.bind! UNDEFINED
    temp.inferred_type = nil
  end
  vertices.each do |block|
    block.successors.each do |succ|
      block.remove_flag(succ, ControlFlowGraph::EDGE_EXECUTABLE)
    end
  end
end

- (Object) debug_dotty 



264
265
266
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 264

def debug_dotty
  Laser.debug_dotty(self)
end

- (Object) dotty(params = {'shape' => 'box'}) 



160
161
162
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 160

def dotty(params = {'shape' => 'box'})
  super
end

- (Object) dup 



58
59
60
61
62
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 58

def dup
  copy = self.class.new
  copy.initialize_dup(self)
  copy
end

- (Object) exception_postdominator 



297
298
299
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 297

def exception_postdominator
  vertex_with_name(EXCEPTION_POSTDOMINATOR_NAME)
end

- (Object) initialize_dup(source) 



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 64

def initialize_dup(source)
  @root = source.root
  @in_ssa = source.in_ssa
  @self_type = source.self_type
  @formal_types = source.formal_types
  @block_type = source.block_type
  # we'll be duplicating temporaries, and since we need to know how
  # our source data about temps (defs, uses, constants...) corresponds
  # the duplicated temps, we'll need a hash to look them up.
  temp_lookup = { Bootstrap::VISIBILITY_STACK => Bootstrap::VISIBILITY_STACK }
  block_lookup = { source.enter => @enter, source.exit => @exit }
  insn_lookup = Hash.new
  # copy all vars defined in the body
  source.all_cached_variables.each do |k|
    copy = k.deep_dup
    temp_lookup[k] = copy
    @all_cached_variables << copy
  end
  self.block_register = temp_lookup[source.block_register]
  self.final_exception = temp_lookup[source.final_exception]
  self.final_return = temp_lookup[source.final_return]
  # copy all formals and their mapping to initial bindings
  @formals = source.formals.map do |formal|
    temp_lookup[formal] = formal.deep_dup
  end

  new_blocks = source.vertices.reject { |v| TerminalBasicBlock === v }
  new_blocks.map! do |block|
    copy = block.duplicate_for_graph_copy(temp_lookup, insn_lookup)
    block_lookup[block] = copy
    copy
  end
  
  new_blocks.each do |new_block|
    add_vertex new_block
  end
  source.each_edge do |u, v|
    add_edge(block_lookup[u], block_lookup[v], u.get_flags(v))
  end
  
  # computed stuff we shouldn't lose:
  # @globals
  # @constants
  # @live
  # @formal_map
  temp_lookup.each do |old, new|
    new.definition = insn_lookup[old.definition]
    new.uses = Set.new(old.uses.map { |insn| insn_lookup[insn] })
  end
  source.globals.each do |global|
    @globals.add temp_lookup[global]
  end
  source.constants.each do |temp, value|
    # no need to dup value, as these constants *MUST NOT* be mutated.
    @constants[temp_lookup[temp]] = value
  end
  source.live.each do |temp, blocks|
    @live[temp_lookup[temp]] = Set.new(blocks.map { |block| block_lookup[block] })
  end
  # Tiny hope this speeds anything up
  temp_lookup.clear
  block_lookup.clear
  insn_lookup.clear
  self
end

- (Object) inspect 



140
141
142
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 140

def inspect
  "<ControlFlowGraph num_verts=#{vertices.size}>"
end

- (Object) kill_unexecuted_edges(remove = false)

Marks all edges that are not executable as fake edges. That way, the postdominance of Exit is preserved, but dead code analysis will ignore them.



356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 356

def kill_unexecuted_edges(remove=false)
  killable = Set.new
  each_edge do |u, v|
    if !(is_executable?(u, v) || is_fake?(u, v))
      killable << [u, v]
    end
  end
  killable.each do |u, v|
    if remove
      remove_edge(u, v)
    else
      u.add_flag(v, EDGE_FAKE)
    end
  end
end

- (Object) prune_totally_useless_blocks

Removes blocks that are not reachable and which go nowhere: they have no effect on the program.



334
335
336
337
338
339
340
341
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 334

def prune_totally_useless_blocks
  vertices = self.to_a
  vertices.each do |vertex|
    if degree(vertex).zero?
      remove_vertex(vertex)
    end
  end
end

- (Object) prune_unexecuted_blocks 



343
344
345
346
347
348
349
350
351
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 343

def prune_unexecuted_blocks
  kill_unexecuted_edges(true)  # be ruthless
  unreachable_vertices.each do |block|
    block.instructions.each do |insn|
      insn.operands.each { |op| op.uses -= ::Set[insn] }
    end
    remove_vertex block
  end
end

- (Object) raise_type 



164
165
166
167
168
169
170
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 164

def raise_type
  if !all_failure_postdominator || all_failure_postdominator.real_predecessors.empty?
    Types::EMPTY
  else
    @final_exception.expr_type
  end
end

- (Object) reachable_variables(block = @enter, visited = Set.new)

Computes the variables reachable by DFSing the start node. This excludes variables defined in dead code.



321
322
323
324
325
326
327
328
329
330
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 321

def reachable_variables(block = @enter, visited = Set.new)
  visited << block
  block.real_successors.inject(block.variables) do |cur, succ|
    if visited.include?(succ)
      cur
    else
      cur | reachable_variables(succ, visited)
    end
  end
end

- (Object) reachable_vertices

Yields reachable vertices via depth-first-search on real edges



306
307
308
309
310
311
312
313
314
315
316
317
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 306

def reachable_vertices
  vertices = Set[]
  worklist = Set[self.enter]
  while worklist.any?
    block = worklist.pop
    yield block if block_given?
    block.real_successors.each do |succ|
      worklist.add(succ) if vertices.add?(succ)
    end
  end
  vertices
end

- (Object) real_block_type 



204
205
206
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 204

def real_block_type
  @block_type || Types::BLOCK
end

- (Object) real_formal_type(idx) 



196
197
198
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 196

def real_formal_type(idx)
  (@formal_types && @formal_types[idx]) || Types::TOP
end

- (Object) real_self_type 



180
181
182
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 180

def real_self_type
  @self_type || Types::TOP
end

- (Object) return_postdominator 



289
290
291
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 289

def return_postdominator
  vertex_with_name(RETURN_POSTDOMINATOR_NAME)
end

- (Object) return_type 



172
173
174
175
176
177
178
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 172

def return_type
  if (@exit.normal_predecessors & @exit.real_predecessors).empty?
    Types::EMPTY
  else
    @final_return.expr_type
  end
end

- (Object) save_pretty_picture(fmt = 'png', dotfile = 'graph', params = {'shape' => 'box'}) 



156
157
158
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 156

def save_pretty_picture(fmt='png', dotfile='graph', params = {'shape' => 'box'})
  write_to_graphic_file(fmt, dotfile, params)
end

- (Object) var_named(name) 



285
286
287
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 285

def var_named(name)
  all_variables.find { |x| x.name.start_with?(name) }
end

- (Object) yield_fail_postdominator 



293
294
295
 
# File 'lib/laser/analysis/control_flow/control_flow_graph.rb', line 293

def yield_fail_postdominator
  vertex_with_name(YIELD_POSTDOMINATOR_NAME)
end