bytecode_to_cfg.py 9.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225
  1. """Converts bytecode IR to CFG IR."""
  2. import modelverse_jit.bytecode_ir as bytecode_ir
  3. import modelverse_jit.cfg_ir as cfg_ir
  4. import modelverse_jit.runtime as jit_runtime
  5. class AnalysisState(object):
  6. """State that is common to the bytecode->CFG transformation of a function."""
  7. def __init__(self):
  8. self.counter = cfg_ir.SharedCounter()
  9. self.analyzed_instructions = set()
  10. self.loop_instructions = {}
  11. self.entry_point = cfg_ir.BasicBlock(self.counter)
  12. self.current_block = self.entry_point
  13. def analyze(self, instruction):
  14. """Analyzes the given instruction as a basic block."""
  15. if instruction in self.analyzed_instructions:
  16. raise jit_runtime.JitCompilationFailedException(
  17. 'Cannot jit non-tree instruction graph.')
  18. self.analyzed_instructions.add(instruction)
  19. # Find an analyzer.
  20. instruction_type = type(instruction)
  21. if instruction_type in self.instruction_analyzers:
  22. # Analyze the instruction.
  23. result = self.instruction_analyzers[instruction_type](self, instruction)
  24. # Check if the instruction has a 'next' instruction. If so, analyze it!
  25. if instruction.next_instruction is not None:
  26. next_result = self.analyze(instruction.next_instruction)
  27. if next_result.has_result() or (not result.has_result()):
  28. result = next_result
  29. return result
  30. else:
  31. raise jit_runtime.JitCompilationFailedException(
  32. "Unknown instruction type: '%s'" % type(instruction))
  33. def emit_select(self, create_condition, create_if_body, create_else_body):
  34. """Emits a 'select' instruction."""
  35. # Create blocks that look like this:
  36. #
  37. # !current_block(...):
  38. # ...
  39. # $cond = <condition>
  40. # select $cond, !if_block(), !else_block()
  41. #
  42. # !if_block():
  43. # $if_result = <if-body>
  44. # jump !phi_block($if_result)
  45. #
  46. # !else_block():
  47. # $else_result = <else-body>
  48. # jump !phi_block($else_result)
  49. #
  50. # !phi_block($result = block-parameter):
  51. # ...
  52. #
  53. if_block = cfg_ir.BasicBlock(self.counter)
  54. else_block = cfg_ir.BasicBlock(self.counter)
  55. phi_block = cfg_ir.BasicBlock(self.counter)
  56. param_def = phi_block.append_parameter(cfg_ir.BlockParameter())
  57. condition = create_condition()
  58. self.current_block.flow = cfg_ir.SelectFlow(
  59. condition, cfg_ir.Branch(if_block), cfg_ir.Branch(else_block))
  60. self.current_block = if_block
  61. if_result = create_if_body()
  62. self.current_block.flow = cfg_ir.create_jump(phi_block, [if_result])
  63. self.current_block = else_block
  64. else_result = create_else_body()
  65. self.current_block.flow = cfg_ir.create_jump(phi_block, [else_result])
  66. self.current_block = phi_block
  67. return param_def
  68. def analyze_if(self, instruction):
  69. """Analyzes an 'if' instruction."""
  70. return self.emit_select(
  71. lambda: self.analyze(instruction.condition),
  72. lambda: self.analyze(instruction.if_clause),
  73. lambda: self.analyze(instruction.else_clause))
  74. def analyze_while(self, instruction):
  75. """Analyzes a 'while' instruction."""
  76. # Create blocks that look like this:
  77. #
  78. # !current_block(...):
  79. # ...
  80. # jump !loop_condition()
  81. #
  82. # !loop_condition():
  83. # $condition = <condition>
  84. # select $condition, !loop_body(), !loop_exit()
  85. #
  86. # !loop_body():
  87. # $result = <body>
  88. # jump !loop_condition()
  89. #
  90. # !loop_exit():
  91. # $nothing = literal None
  92. # ...
  93. loop_condition_block = cfg_ir.BasicBlock(self.counter)
  94. loop_body_block = cfg_ir.BasicBlock(self.counter)
  95. loop_exit_block = cfg_ir.BasicBlock(self.counter)
  96. self.loop_instructions[instruction] = (loop_condition_block, loop_exit_block)
  97. self.current_block.flow = cfg_ir.create_jump(loop_condition_block)
  98. self.current_block = loop_condition_block
  99. condition_value = self.analyze(instruction.condition)
  100. self.current_block.flow = cfg_ir.SelectFlow(
  101. condition_value, cfg_ir.Branch(loop_body_block), cfg_ir.Branch(loop_exit_block))
  102. self.current_block = loop_body_block
  103. self.analyze(instruction.body)
  104. self.current_block.flow = cfg_ir.create_jump(loop_condition_block)
  105. self.current_block = loop_exit_block
  106. return loop_exit_block.append_definition(cfg_ir.Literal(None))
  107. def analyze_return(self, instruction):
  108. """Analyzes a 'return' instruction."""
  109. if instruction.value is None:
  110. return_value = self.current_block.append_definition(cfg_ir.Literal(None))
  111. else:
  112. return_value = self.analyze(instruction.value)
  113. self.current_block.flow = cfg_ir.ReturnFlow(return_value)
  114. self.current_block = cfg_ir.BasicBlock(self.counter)
  115. def analyze_constant(self, instruction):
  116. """Analyzes a 'constant' instruction."""
  117. return self.current_block.append_definition(cfg_ir.Literal(instruction.node_id))
  118. def analyze_resolve(self, instruction):
  119. """Analyzes a 'resolve' instruction."""
  120. return self.emit_select(
  121. lambda:
  122. self.current_block.append_definition(
  123. cfg_ir.CheckLocalExists(instruction.variable)),
  124. lambda:
  125. self.current_block.append_definition(
  126. cfg_ir.ResolveLocal(instruction.variable)),
  127. lambda:
  128. self.current_block.append_definition(
  129. cfg_ir.ResolveGlobal(instruction.variable)))
  130. def analyze_declare(self, instruction):
  131. """Analyzes a 'declare' instruction."""
  132. return self.current_block.append_definition(cfg_ir.DeclareLocal(instruction.variable))
  133. def analyze_global(self, instruction):
  134. """Analyzes a 'global' instruction."""
  135. return self.current_block.append_definition(cfg_ir.DeclareGlobal(instruction.variable))
  136. def analyze_assign(self, instruction):
  137. """Analyzes an 'assign' instruction."""
  138. pointer_result = self.analyze(instruction.pointer)
  139. value_result = self.analyze(instruction.value)
  140. return self.current_block.append_definition(
  141. cfg_ir.StoreAtPointer(pointer_result, value_result))
  142. def analyze_access(self, instruction):
  143. """Analyzes an 'access' instruction."""
  144. pointer_result = self.analyze(instruction.pointer)
  145. return self.current_block.append_definition(cfg_ir.LoadPointer(pointer_result))
  146. def analyze_output(self, instruction):
  147. """Analyzes an 'output' instruction."""
  148. value_result = self.analyze(instruction.value)
  149. return self.current_block.append_definition(cfg_ir.Output(value_result))
  150. def analyze_input(self, _):
  151. """Analyzes an 'input' instruction."""
  152. return self.current_block.append_definition(cfg_ir.Input())
  153. def analyze_break(self, instruction):
  154. """Analyzes a 'break' instruction."""
  155. if instruction.loop not in self.loop_instructions:
  156. raise jit_runtime.JitCompilationFailedException(
  157. "'break' instruction targets a 'while' loop that has not been defined yet.")
  158. _, exit_block = self.loop_instructions[instruction.loop]
  159. self.current_block.flow = cfg_ir.create_jump(exit_block)
  160. def analyze_continue(self, instruction):
  161. """Analyzes a 'continue' instruction."""
  162. if instruction.loop not in self.loop_instructions:
  163. raise jit_runtime.JitCompilationFailedException(
  164. "'continue' instruction targets a 'while' loop that has not been defined yet.")
  165. cond_block, _ = self.loop_instructions[instruction.loop]
  166. self.current_block.flow = cfg_ir.create_jump(cond_block)
  167. def analyze_call(self, instruction):
  168. """Analyzes the given 'call' instruction."""
  169. target = self.analyze(instruction.target)
  170. arg_list = []
  171. for key, arg_instruction in instruction.argument_list:
  172. arg_list.append((key, self.analyze(arg_instruction)))
  173. return cfg_ir.JitFunctionCall(target, arg_list)
  174. instruction_analyzers = {
  175. bytecode_ir.SelectInstruction : analyze_if,
  176. bytecode_ir.WhileInstruction : analyze_while,
  177. bytecode_ir.ReturnInstruction : analyze_return,
  178. bytecode_ir.ConstantInstruction : analyze_constant,
  179. bytecode_ir.ResolveInstruction : analyze_resolve,
  180. bytecode_ir.DeclareInstruction : analyze_declare,
  181. bytecode_ir.GlobalInstruction : analyze_global,
  182. bytecode_ir.AssignInstruction : analyze_assign,
  183. bytecode_ir.AccessInstruction : analyze_access,
  184. bytecode_ir.OutputInstruction : analyze_output,
  185. bytecode_ir.InputInstruction : analyze_input,
  186. bytecode_ir.CallInstruction : analyze_call,
  187. bytecode_ir.BreakInstruction : analyze_break,
  188. bytecode_ir.ContinueInstruction : analyze_continue
  189. }