Class: SyntaxTree::YARV::ControlFlowGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/syntax_tree/yarv/control_flow_graph.rb

Overview

This class represents a control flow graph of a YARV instruction sequence. It constructs a graph of basic blocks that hold subsets of the list of instructions from the instruction sequence.

You can use this class by calling the ::compile method and passing it a YARV instruction sequence. It will return a control flow graph object.

iseq = RubyVM::InstructionSequence.compile("1 + 2")
iseq = SyntaxTree::YARV::InstructionSequence.from(iseq.to_a)
cfg = SyntaxTree::YARV::ControlFlowGraph.compile(iseq)

Defined Under Namespace

Classes: Compiler

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(iseq, insns, blocks) ⇒ ControlFlowGraph

Returns a new instance of ControlFlowGraph.



173
174
175
176
177
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 173

def initialize(iseq, insns, blocks)
  @iseq = iseq
  @insns = insns
  @blocks = blocks
end

Instance Attribute Details

#blocks ⇒ Object (readonly)

This is the set of basic blocks that this control-flow graph contains.



171
172
173
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 171

def blocks
  @blocks
end

#insns ⇒ Object (readonly)

This is the list of instructions that this control flow graph contains. It is effectively the same as the list of instructions in the instruction sequence but with line numbers and events filtered out.



168
169
170
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 168

def insns
  @insns
end

#iseq ⇒ Object (readonly)

This is the instruction sequence that this control flow graph corresponds to.



163
164
165
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 163

def iseq
  @iseq
end

Class Method Details

.compile(iseq) ⇒ Object 



252
253
254
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 252

def self.compile(iseq)
  Compiler.new(iseq).compile
end

Instance Method Details

#disasm ⇒ Object 



179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 179

def disasm
  fmt = Disassembler.new(iseq)
  fmt.puts("== cfg: #{iseq.inspect}")

  blocks.each do |block|
    fmt.puts(block.id)
    fmt.with_prefix("    ") do |prefix|
      unless block.incoming_blocks.empty?
        from = block.incoming_blocks.map(&:id)
        fmt.puts("#{prefix}== from: #{from.join(", ")}")
      end

      fmt.format_insns!(block.insns, block.block_start)

      to = block.outgoing_blocks.map(&:id)
      to << "leaves" if block.insns.last.leaves?
      fmt.puts("#{prefix}== to: #{to.join(", ")}")
    end
  end

  fmt.string
end

#to_dfg ⇒ Object 



202
203
204
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 202

def to_dfg
  DataFlowGraph.compile(self)
end

#to_mermaid ⇒ Object 



210
211
212
213
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
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 210

def to_mermaid
  Mermaid.flowchart do |flowchart|
    disasm = Disassembler::Squished.new

    blocks.each do |block|
      flowchart.subgraph(block.id) do
        previous = nil

        block.each_with_length do |insn, length|
          node =
            flowchart.node(
              "node_#{length}",
              "%04d %s" % [length, insn.disasm(disasm)]
            )

          flowchart.link(previous, node) if previous
          previous = node
        end
      end
    end

    blocks.each do |block|
      block.outgoing_blocks.each do |outgoing|
        offset =
          block.block_start + block.insns.sum(&:length) -
            block.insns.last.length

        from = flowchart.fetch("node_#{offset}")
        to = flowchart.fetch("node_#{outgoing.block_start}")
        flowchart.link(from, to)
      end
    end
  end
end

#to_son ⇒ Object 



206
207
208
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 206

def to_son
  to_dfg.to_son
end

#verify ⇒ Object

This method is used to verify that the control flow graph is well formed. It does this by checking that each basic block is itself well formed.



248
249
250
 
# File 'lib/syntax_tree/yarv/control_flow_graph.rb', line 248

def verify
  blocks.each(&:verify)
end