Class: RGL::ControlFlowGraph

Inherits:
Object
  • Object
show all
Includes:
Enumerable, MutableGraph
Defined in:
lib/laser/third_party/rgl/control_flow.rb

Overview

This is an implementation of a more efficient graph customized for control-flow purposes. Lots of operations on RGL's base library, while re-using a lot of code, are needlessly algorithmically insufficient. (#empty is O(|V|)!)

Direct Known Subclasses

Laser::Analysis::ControlFlow::ControlFlowGraph

Constant Summary

EDGE_NORMAL =
1 << 0
EDGE_ABNORMAL =
1 << 1
EDGE_FAKE =
1 << 2
EDGE_EXECUTABLE =
1 << 3
EDGE_BLOCK_TAKEN =
1 << 4

Instance Attribute Summary (collapse)

Instance Method Summary (collapse)

Methods included from MutableGraph

#add_edges, #add_graph, #add_graphs, #add_vertices, #cycles, #cycles_with_vertex, #from_graphxml, #remove_vertices

Methods included from 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, #dominance_frontier, #dominator_tree, #dotty, #each_connected_component, #edge_class, #edges_filtered_by, #eql?, #implicit_graph, #iterated_dominance_frontier, #print_dotted_on, #reverse, #strongly_connected_components, #to_adjacency, #to_dot_graph, #to_s, #to_undirected, #topsort_iterator, #transitive_closure, #transitive_reduction, #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_set, #zip

Constructor Details

- (ControlFlowGraph) initialize



21
22
23
24
25
26
# File 'lib/laser/third_party/rgl/control_flow.rb', line 21

def initialize
  @enter = Laser::Analysis::ControlFlow::TerminalBasicBlock.new('Enter')
  @exit = Laser::Analysis::ControlFlow::TerminalBasicBlock.new('Exit')
  @vertices = Set[@enter, @exit]
  @vertex_lookup = {'Enter' => @enter, 'Exit' => @exit}
end

Instance Attribute Details

- (Object) enter (readonly)

Returns the value of attribute enter



18
19
20
# File 'lib/laser/third_party/rgl/control_flow.rb', line 18

def enter
  @enter
end

- (Object) exit (readonly)

Returns the value of attribute exit



18
19
20
# File 'lib/laser/third_party/rgl/control_flow.rb', line 18

def exit
  @exit
end

- (Object) vertex_lookup (readonly)

Returns the value of attribute vertex_lookup



19
20
21
# File 'lib/laser/third_party/rgl/control_flow.rb', line 19

def vertex_lookup
  @vertex_lookup
end

- (Object) vertices (readonly)

Returns the value of attribute vertices



19
20
21
# File 'lib/laser/third_party/rgl/control_flow.rb', line 19

def vertices
  @vertices
end

Instance Method Details

- (Object) [](key)



28
29
30
# File 'lib/laser/third_party/rgl/control_flow.rb', line 28

def [](key)
  vertex_with_name(key.name)
end

- (Object) add_edge(u, v, flags = EDGE_NORMAL)

Adds the edge to the graph. O(1) amortized.



66
67
68
69
# File 'lib/laser/third_party/rgl/control_flow.rb', line 66

def add_edge(u, v, flags = EDGE_NORMAL)
  u.join(v)
  u.set_flag(v, flags)
end

- (Object) add_flag(src, dest, flag)



87
88
89
# File 'lib/laser/third_party/rgl/control_flow.rb', line 87

def add_flag(src, dest, flag)
  src.add_flag(dest, flag)
end

- (Object) add_vertex(u)

Adds the vertex to the set of vertices. O(1) amortized.



60
61
62
63
# File 'lib/laser/third_party/rgl/control_flow.rb', line 60

def add_vertex(u)
  @vertex_lookup[u.name] = u
  vertices << u
end

- (Object) degree(u)

Computes the total degree of the vertex. O(1).



151
152
153
# File 'lib/laser/third_party/rgl/control_flow.rb', line 151

def degree(u)
  in_degree(u) + out_degree(u)
end

- (Boolean) directed?

Is the graph directed? Yes, always.



146
147
148
# File 'lib/laser/third_party/rgl/control_flow.rb', line 146

def directed?
  true
end

- (Object) each_adjacent(u, &b)

Enumerates every vertex adjacent to u. O(V).



48
49
50
# File 'lib/laser/third_party/rgl/control_flow.rb', line 48

def each_adjacent(u, &b)
  self[u].successors.each(&b)
end

- (Object) each_edge

Jacked from RGL. O(E).



53
54
55
56
57
# File 'lib/laser/third_party/rgl/control_flow.rb', line 53

def each_edge
  each_vertex { |u|
    each_adjacent(u) { |v| yield u,v }
  }
end

- (Object) each_vertex(&b) Also known as: each

Enumerates the vertices. O(V).



42
43
44
# File 'lib/laser/third_party/rgl/control_flow.rb', line 42

def each_vertex(&b)
  vertices.each(&b)
end

- (Object) edges

Gets all the edges. O(E).



37
38
39
# File 'lib/laser/third_party/rgl/control_flow.rb', line 37

def edges
  vertices.map { |vert| vert.successors.map { |succ| [vert, succ] }}.flatten 1
end

- (Boolean) empty?

Does the graph have no vertices? O(1).



127
128
129
# File 'lib/laser/third_party/rgl/control_flow.rb', line 127

def empty?
  vertices.empty?
end

- (Boolean) has_edge?(u, v)



136
137
138
# File 'lib/laser/third_party/rgl/control_flow.rb', line 136

def has_edge?(u, v)
  self[u].successors.include?(v)
end

- (Boolean) has_vertex?(u)

Does the graph contain this vertex? O(1).



132
133
134
# File 'lib/laser/third_party/rgl/control_flow.rb', line 132

def has_vertex?(u)
  vertices.include?(u)
end

- (Object) in_degree(u)

What is the in-degree of the vertex u? O(1).



156
157
158
# File 'lib/laser/third_party/rgl/control_flow.rb', line 156

def in_degree(u)
  self[u].predecessors.size
end

- (Boolean) is_abnormal?(src, dest)



75
76
77
# File 'lib/laser/third_party/rgl/control_flow.rb', line 75

def is_abnormal?(src, dest)
  src.has_flag?(dest, EDGE_ABNORMAL)
end

- (Boolean) is_block_taken?(src, dest)



71
72
73
# File 'lib/laser/third_party/rgl/control_flow.rb', line 71

def is_block_taken?(src, dest)
  src.has_flag?(dest, EDGE_BLOCK_TAKEN)
end

- (Boolean) is_executable?(src, dest)



83
84
85
# File 'lib/laser/third_party/rgl/control_flow.rb', line 83

def is_executable?(src, dest)
  src.has_flag?(dest, EDGE_EXECUTABLE)
end

- (Boolean) is_fake?(src, dest)



79
80
81
# File 'lib/laser/third_party/rgl/control_flow.rb', line 79

def is_fake?(src, dest)
  src.has_flag?(dest, EDGE_FAKE)
end

- (Object) num_edges

How many edges are in the graph? O(V).



166
167
168
# File 'lib/laser/third_party/rgl/control_flow.rb', line 166

def num_edges
  vertices.map { vertices.successors.size }.inject(:+)
end

- (Object) num_vertices Also known as: size

Counts the number of vertices. O(1).



121
122
123
# File 'lib/laser/third_party/rgl/control_flow.rb', line 121

def num_vertices
  vertices.size
end

- (Object) out_degree(u)

What is the out-degree of the vertex u? O(1).



161
162
163
# File 'lib/laser/third_party/rgl/control_flow.rb', line 161

def out_degree(u)
  self[u].successors.size
end

- (Object) remove_edge(u, v)

Removes the edge from the graph. O(1) amortized.



112
113
114
115
116
117
118
# File 'lib/laser/third_party/rgl/control_flow.rb', line 112

def remove_edge(u, v)
  
  looked_up_u, looked_up_v = self[u], self[v]
  looked_up_u.disconnect(looked_up_v)
  # looked_up_u.remove_successor looked_up_v
  # looked_up_v.remove_predecessor looked_up_u
end

- (Object) remove_flag(src, dest, flag)



91
92
93
# File 'lib/laser/third_party/rgl/control_flow.rb', line 91

def remove_flag(src, dest, flag)
  src.remove_flag(dest, flag)
end

- (Object) remove_vertex(u)

Removes the vertex from the graph. O(E) amortized.



96
97
98
99
100
101
102
103
104
105
106
107
108
109
# File 'lib/laser/third_party/rgl/control_flow.rb', line 96

def remove_vertex(u)
  u.clear_edges
  looked_up = self[u]
  # looked_up.successors.each do |succ|
  #   self[succ].remove_predecessor looked_up
  #   self[looked_up].delete_all_flags succ
  # end
  # looked_up.predecessors.each do |pred|
  #   self[pred].remove_successor looked_up
  #   self[pred].delete_all_flags looked_up
  # end
  @vertex_lookup.delete looked_up.name
  vertices.delete looked_up
end

- (Object) to_a

Returns an array of vertices in this graph. O(V).



141
142
143
# File 'lib/laser/third_party/rgl/control_flow.rb', line 141

def to_a
  vertices.to_a
end

- (Object) vertex_with_name(key)



32
33
34
# File 'lib/laser/third_party/rgl/control_flow.rb', line 32

def vertex_with_name(key)
  @vertex_lookup[key]
end