Class: CastOff::Compiler::Translator::CFG

Inherits:
Object
  • Object
show all
Includes:
Instruction, SimpleIR, Util
Defined in:
lib/cast_off/compile/cfg.rb,
lib/cast_off/compile/stack.rb,
lib/cast_off/compile/basicblock.rb,
lib/cast_off/compile/information.rb

Defined Under Namespace

Classes: Alias, BasicBlock, Condition, Guards, Information

Constant Summary

Constants included from SimpleIR

SimpleIR::SPLATCALL_LIMIT, SimpleIR::SupportLoopInstruction

Constants included from Instruction

Instruction::BlockSeparator, Instruction::BranchInstruction, Instruction::IgnoreInstruction, Instruction::JumpOrReturnInstruction, Instruction::SupportInstruction, Instruction::TypeInfoUser, Instruction::VM_CALL_ARGS_BLOCKARG_BIT, Instruction::VM_CALL_ARGS_SPLAT_BIT, Instruction::VM_CALL_FCALL_BIT, Instruction::VM_CALL_OPT_SEND_BIT, Instruction::VM_CALL_SUPER_BIT, Instruction::VM_CALL_TAILCALL_BIT, Instruction::VM_CALL_TAILRECURSION_BIT, Instruction::VM_CALL_VCALL_BIT

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from SimpleIR

#block_argument_is_unsupported, #generate_ir

Methods included from Util

#bug, #dlog, #todo, #vlog

Constructor Details

#initialize(body) ⇒ CFG

Returns a new instance of CFG.



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/cast_off/compile/cfg.rb', line 25

def initialize(body)
  @translator = nil
  blocks = []
  basicblock = []
  body.each do |v|
    case v
    when InsnInfo
      basicblock << v
      if BlockSeparator.include?(v.op)
        blocks << basicblock
        basicblock = []
      end
    when Symbol
      if !basicblock.empty?
        blocks << basicblock
        basicblock = []
      end
      blocks << v
    else
      bug("v = #{v}")
    end
  end
  blocks << basicblock unless basicblock.empty?

  bbnum = -1
  blocks.map!{|b| b.instance_of?(Array) ? BasicBlock.new(self, b, bbnum += 1) : b}
  blocks.each{|b| b.set_prev_block(blocks) if b.instance_of?(BasicBlock)}
  blocks.each{|b| b.set_next_block(blocks) if b.instance_of?(BasicBlock)}
  @blocks = blocks.select{|b| b.instance_of?(BasicBlock)}
  @blocks.each{|b| bug() unless b.next && b.pre}

  eliminate_unreachable_blocks()
  validate_stack() # stack.rb
end

Instance Attribute Details

#blocks ⇒ Object (readonly)

Returns the value of attribute blocks.



10
11
12
 
# File 'lib/cast_off/compile/cfg.rb', line 10

def blocks
  @blocks
end

Instance Method Details

#calc_egen_ekill ⇒ Object

Condition



463
464
465
466
467
 
# File 'lib/cast_off/compile/information.rb', line 463

def calc_egen_ekill
  all = all_ir()
  @blocks.each { |b| b.calc_egen() }
  @blocks.each { |b| b.calc_ekill(all) }
end

#calc_undefined_variables ⇒ Object

BasicBlock



633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
 
# File 'lib/cast_off/compile/information.rb', line 633

def calc_undefined_variables()
  vars = all_variable()
  change = true
  entry = @blocks[0]
  bug() if @blocks.find{|b| b != entry && b.pre.empty? }
  bug() unless entry.pre.empty?
  entry.in_undefined = vars
  @blocks.each{|b| b.out_undefined = []}
  entry.out_undefined = entry.in_undefined - entry.egen.map{|ir| ir.result_variable}
  while change
    change = false
    @blocks.each do |b0|
      if b0 != entry
        b0.in_undefined = b0.pre.inject([]){|in_undefined, b1| in_undefined | b1.out_undefined }
        out_undefined = b0.in_undefined + b0.ekill.map{|ir| ir.result_variable} - b0.egen.map{|ir| ir.result_variable}
        if !(out_undefined - b0.out_undefined).empty?
          b0.out_undefined |= out_undefined
          change = true
        end
      end
    end
  end
  @blocks.each do |b|
    b.in_undefined.freeze()
    b.out_undefined.freeze()
  end
  # validation
  @blocks.each do |b|
    undefined = b.in_undefined.dup()
    b.irs.each do |ir|
      ir.variables_without_result.each do |var|
        var.has_undefined_path() if undefined.include?(var)
      end
      result_variable = ir.result_variable
      undefined -= [result_variable] if result_variable
    end
  end
end

#find_insn_stack_depth(insn) ⇒ Object 



36
37
38
39
 
# File 'lib/cast_off/compile/stack.rb', line 36

def find_insn_stack_depth(insn)
  b = @blocks.find{|b| b.insns.include?(insn)}
  b ? b.find_insn_stack_depth(insn) : nil
end

#find_variable(v0) ⇒ Object 



89
90
91
 
# File 'lib/cast_off/compile/cfg.rb', line 89

def find_variable(v0)
  all_variable.find{|v1| v0 == v1}
end

#gen_ir(t) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
# File 'lib/cast_off/compile/cfg.rb', line 60

def gen_ir(t)
  @translator = t
  @blocks.each{|b| b.gen_ir()}
  change = true
  while change
    change = false
    set_information() # information.rb
    type_propergation()
    propergate_exact_class()
    propergate_guard_usage()
    inject_guards()
    reject_redundant_guards()
    if transform_branch_instruction()
      eliminate_unreachable_blocks() # this method generates jump_guards
      change = true
    end
    reject_unused_ir() # should be call after guard generation
    change |= method_inlining()
    if change
      validate_stack() # stack.rb
      reject_guards()
      reset_ir()
    end
  end
  unboxing()
  attach_var_info()
  set_sampling()
end

#inject_guards ⇒ Object 



828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
 
# File 'lib/cast_off/compile/information.rb', line 828

def inject_guards()
  vars = all_variable()
  ptrs = all_pointer()
  vars.freeze()
  ptrs.freeze()
  @blocks.each do |b|
    b.irs.map! do |ir|
      g = ir.generate_guard(vars)
      g ? [g, ir] : ir
    end
    b.irs.flatten!
  end

  bug() if @blocks.find{|b| not b.information.frozen?}
  @blocks.each{|b| b.in_guards = Guards.new(b, b.information, [], ptrs)}
  change = true
  while change
    change = false
    @blocks.each do |b0|
      next if b0.entry_point?
      in_guards = b0.pre.inject(Guards.new(b0, b0.information, vars, ptrs)){|in_g, b1| in_g & b1.in_guards.final_state()}
      change = true if b0.in_guards != in_guards
      b0.in_guards = in_guards
    end
  end
  @blocks.each{|b| b.in_guards.freeze()}
end

#set_condition ⇒ Object 



672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
 
# File 'lib/cast_off/compile/information.rb', line 672

def set_condition
  @blocks.each{|b| b.information.initialize_condition()}
  change = true
  entry = @blocks.first
  while change
    change = false
    @blocks.each do |b0|
      next if b0 == entry
      info = b0.information
      cond = b0.pre.inject(info.condition.dup) do |c, b1|
        next c if b0 == b1
        c.union(b1.information.condition.final_state)
      end
      change = true if info.condition != cond
      info.condition = cond
    end
  end
end

#set_information ⇒ Object 



691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
 
# File 'lib/cast_off/compile/information.rb', line 691

def set_information
  ptr_defs = all_pointer_definition()
  ptrs = all_pointer()
  vars = all_variable()
  calc_egen_ekill()
  calc_undefined_variables()
  entry = @blocks[0]
  bug() if @blocks.find{|b| (not b.in_undefined) || (not b.out_undefined)}
  bug() if @blocks.find{|b| b != entry && b.pre.empty? }
  bug() unless entry.pre.empty?
  @blocks.each{|b| b.information = Information.new(b, vars, vars, nil, [], [], ptr_defs, ptrs)}
  entry.information = Information.new(entry, vars, vars, nil, [], vars, ptr_defs, ptrs)
  change = true
  while change
    change = false
    @blocks.each do |b0|
      next if b0 == entry
      info = b0.pre.inject(Information.new(b0, vars, nil, nil, [], [], ptr_defs, ptrs)) {|info, b1| info | b1.information.final_state()}
      change = true if b0.information != info
      b0.information = info
    end
  end
  change = true
  while change
    change = false
    @blocks.each do |b0|
      next if b0 == entry
      info = b0.information.dup
      b0.pre.each{|b1| info.kill_definition(b1.information.final_state())}
      change = true if b0.information != info
      b0.information = info
    end
  end
  set_condition()
  @blocks.each{|b| b.information.freeze()}
  # validation
  @blocks.each do |b|
    definition = b.information.dup()
    definition.validate()
    b.irs.each do |ir|
      ir.variables_without_result.each do |var|
        var.has_undefined_path() if definition.undefined_variables.include?(var)
      end
      definition.step(ir)
    end
    definition.validate_final()
  end
  @blocks.each do |b|
    u0 = b.in_undefined
    u1 = b.information.undefined_variables
    bug("u1 = #{u1}, u0 = #{u0}") unless (u0 - u1).empty? && (u1 - u0).empty?
    u0 = b.out_undefined
    u1 = b.information.final_state.undefined_variables
    bug("u1 = #{u1}, u0 = #{u0}") unless (u0 - u1).empty? && (u1 - u0).empty?
  end
end

#to_c ⇒ Object 



12
13
14
 
# File 'lib/cast_off/compile/cfg.rb', line 12

def to_c()
  @blocks.each{|b| b.iseq.append_c_function_body(b.to_c())}
end

#to_s ⇒ Object 



16
17
18
 
# File 'lib/cast_off/compile/cfg.rb', line 16

def to_s()
  @blocks.join("\n")
end

#translator ⇒ Object 



20
21
22
23
 
# File 'lib/cast_off/compile/cfg.rb', line 20

def translator
  bug() unless @translator
  @translator
end