Class: Optimize::IR::CFG

Inherits:
Object
  • Object
show all
Defined in:
lib/optimize/ir/cfg.rb

Overview

Control-flow graph of a function. Blocks are computed once from the function’s instruction list; successors/predecessors are queried via edge lookups.

Branch OFFSET operands are instruction indices (normalized by the codec at decode time), so CFG construction works directly on instruction indices.

Constant Summary collapse

BRANCH_OPCODES = 
%i[branchif branchunless branchnil].freeze
JUMP_OPCODES = 
%i[jump].freeze
TERMINATOR_OPCODES = 
(BRANCH_OPCODES + JUMP_OPCODES + %i[leave throw]).freeze

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(blocks, edges) ⇒ CFG

Returns a new instance of CFG.



26
27
28
29
 
# File 'lib/optimize/ir/cfg.rb', line 26

def initialize(blocks, edges)
  @blocks = blocks
  @edges = edges # { from_block_id => [to_block, ...] }
end

Instance Attribute Details

#blocks ⇒ Object (readonly)

Returns the value of attribute blocks.



17
18
19
 
# File 'lib/optimize/ir/cfg.rb', line 17

def blocks
  @blocks
end

Class Method Details

.build(instructions) ⇒ Object 



19
20
21
22
23
24
 
# File 'lib/optimize/ir/cfg.rb', line 19

def self.build(instructions)
  leaders = compute_leaders(instructions)
  blocks = slice_into_blocks(instructions, leaders)
  edges = compute_edges(instructions, blocks)
  new(blocks, edges)
end

.compute_edges(instructions, blocks) ⇒ Object 



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
 
# File 'lib/optimize/ir/cfg.rb', line 65

def self.compute_edges(instructions, blocks)
  # Map instruction index -> block (via identity comparison on first instruction).
  insn_to_block = {}
  blocks.each do |b|
    offset = instructions.index { |ins| ins.equal?(b.instructions.first) }
    next unless offset
    b.instructions.each_with_index do |_, j|
      insn_to_block[offset + j] = b
    end
  end

  edges = Hash.new { |h, k| h[k] = [] }
  blocks.each do |b|
    term = b.terminator
    next unless term
    case term.opcode
    when *BRANCH_OPCODES
      # OFFSET operand is an instruction index (normalized at decode time).
      target = term.operands[0]
      fallthrough_idx = instructions.index { |i| i.equal?(term) } + 1
      if (tblock = insn_to_block[target])
        edges[b.id] << tblock
      end
      if (fblock = insn_to_block[fallthrough_idx])
        edges[b.id] << fblock
      end
    when *JUMP_OPCODES
      target = term.operands[0]
      if (tblock = insn_to_block[target])
        edges[b.id] << tblock
      end
    when :leave, :throw
      # no successors
    else
      # Non-terminator tail (shouldn't happen if leaders are right,
      # but fall through to the next block just in case).
      fallthrough_idx = instructions.index { |i| i.equal?(term) } + 1
      if (fblock = insn_to_block[fallthrough_idx])
        edges[b.id] << fblock
      end
    end
  end
  edges
end

.compute_leaders(instructions) ⇒ Object 



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/optimize/ir/cfg.rb', line 39

def self.compute_leaders(instructions)
  return [] if instructions.empty?
  leaders = [0]
  instructions.each_with_index do |ins, i|
    next unless TERMINATOR_OPCODES.include?(ins.opcode)
    # The instruction after a terminator is a leader (if it exists).
    leaders << (i + 1) if i + 1 < instructions.size
    # Branch targets are leaders (OFFSET operand is an instruction index).
    if (BRANCH_OPCODES + JUMP_OPCODES).include?(ins.opcode)
      target = ins.operands[0]
      leaders << target if target.is_a?(Integer) && target >= 0 && target < instructions.size
    end
  end
  leaders.uniq.sort
end

.slice_into_blocks(instructions, leaders) ⇒ Object 



55
56
57
58
59
60
61
62
63
 
# File 'lib/optimize/ir/cfg.rb', line 55

def self.slice_into_blocks(instructions, leaders)
  return [] if instructions.empty?
  blocks = []
  leaders.each_with_index do |start, idx|
    stop = leaders[idx + 1] || instructions.size
    blocks << BasicBlock.new(id: idx, instructions: instructions[start...stop])
  end
  blocks
end

Instance Method Details

#predecessors(block) ⇒ Object 



35
36
37
 
# File 'lib/optimize/ir/cfg.rb', line 35

def predecessors(block)
  @blocks.select { |b| successors(b).include?(block) }
end

#successors(block) ⇒ Object 



31
32
33
 
# File 'lib/optimize/ir/cfg.rb', line 31

def successors(block)
  @edges[block.id] || []
end