class Fisk::CFG
Public Class Methods
build(instructions)
click to toggle source
# File lib/fisk/basic_block.rb, line 22 def self.build instructions blocks = [] bb_index = 0 chunks = instructions.chunk { |insn| if insn.label? # start a new block here bb_index += 1 end ret_idx = bb_index if insn.jump? # end the block here bb_index += 1 end ret_idx }.to_a chunk_name = ->(chunk_id, insns) { if insns.first.label? insns.first.name else :"bb_#{chunk_id}" end } jump_targets = {} wants_target = [] insn_idx = 0 chunks.each_with_index do |(chunk_id, insns), idx| prev_block = blocks.last name = chunk_name.(chunk_id, insns) next_chunk_id, next_insns = chunks[idx + 1] outgoing = [] if next_chunk_id outgoing << chunk_name.(next_chunk_id, next_insns) end bb = BasicBlock.new(name, insns) bb.pred = [] bb.start_point = insn_idx insn_idx += insns.length bb.end_point = insn_idx - 1 if bb.jump? target_name = bb.jump_name # if we need to jump backwards, the label should already be filled in. # Otherwise we need to find the block later (we're jumping forward) if jump_targets[target_name] jt = jump_targets[target_name] bb.jump = jt jt.pred << bb else wants_target << bb end end jump_targets[bb.name] = bb if prev_block prev_block.fall = bb bb.pred << prev_block end blocks << bb end # fill in any forward jumps wants_target.each { |bb| jt = jump_targets[bb.jump_name] bb.jump = jt jt.pred << bb } variables = live_variables blocks CFG.new variables, blocks end
live_variables(blocks)
click to toggle source
# File lib/fisk/basic_block.rb, line 109 def self.live_variables blocks seen = Set.new blocks.each do |block| used = Set.new defd = Set.new block.insns.each do |insn| if insn.has_temp_registers? insn.temp_registers.each do |reg| defd << reg unless seen.include?(reg) used << reg unless defd.include?(reg) seen << reg end end end block.use = used.to_a block.def = defd.to_a block.in = [] block.out = [] end worklist = blocks.dup while block = worklist.pop block.out = block.succ.inject([]) { |out_registers, succ_block| out_registers | succ_block.in } ins = block.in | block.use | (block.out - block.def) if ins == block.in # Done with this block! block.live.each do |live_register| live_register.end_point ||= block.end_point if live_register.start_point > block.start_point live_register.start_point = block.start_point end if live_register.end_point < block.end_point live_register.end_point = block.end_point end end else block.in = ins worklist.concat(block.pred) end end seen end