bytecode_to_cfg.py 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304
  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. self.root_node = None
  14. self.__write_prolog()
  15. def __write_prolog(self):
  16. # Write a prolog in CFG IR.
  17. # We want to create the following definition:
  18. #
  19. # !entry_point():
  20. # $jit_locals = alloc-root-node
  21. #
  22. # We also want to store '$jit_locals' in an attribute, so we can
  23. # use it to shield locals from the GC.
  24. self.root_node = self.current_block.append_definition(cfg_ir.AllocateRootNode())
  25. def analyze(self, instruction):
  26. """Analyzes the given instruction as a basic block."""
  27. if instruction in self.analyzed_instructions:
  28. raise jit_runtime.JitCompilationFailedException(
  29. 'Cannot jit non-tree instruction graph.')
  30. self.analyzed_instructions.add(instruction)
  31. # Find an analyzer.
  32. instruction_type = type(instruction)
  33. if instruction_type in self.instruction_analyzers:
  34. # Analyze the instruction.
  35. result = self.instruction_analyzers[instruction_type](self, instruction)
  36. # Check if the instruction has a 'next' instruction. If so, analyze it!
  37. if instruction.next_instruction is not None:
  38. next_result = self.analyze(instruction.next_instruction)
  39. if next_result.value.has_value() or (not result.value.has_value()):
  40. result = next_result
  41. return result
  42. else:
  43. raise jit_runtime.JitCompilationFailedException(
  44. "Unknown instruction type: '%s'" % type(instruction))
  45. def emit_select(self, create_condition, create_if_body, create_else_body):
  46. """Emits a 'select' instruction."""
  47. # Create blocks that look like this:
  48. #
  49. # !current_block(...):
  50. # ...
  51. # $cond = <condition>
  52. # select $cond, !if_block(), !else_block()
  53. #
  54. # !if_block():
  55. # $if_result = <if-body>
  56. # jump !phi_block($if_result)
  57. #
  58. # !else_block():
  59. # $else_result = <else-body>
  60. # jump !phi_block($else_result)
  61. #
  62. # !phi_block($result = block-parameter):
  63. # ...
  64. #
  65. if_block = cfg_ir.BasicBlock(self.counter)
  66. else_block = cfg_ir.BasicBlock(self.counter)
  67. phi_block = cfg_ir.BasicBlock(self.counter)
  68. param_def = phi_block.append_parameter(cfg_ir.BlockParameter())
  69. condition = create_condition()
  70. self.current_block.flow = cfg_ir.SelectFlow(
  71. condition, cfg_ir.Branch(if_block), cfg_ir.Branch(else_block))
  72. self.current_block = if_block
  73. if_result = create_if_body()
  74. self.current_block.flow = cfg_ir.create_jump(phi_block, [if_result])
  75. self.current_block = else_block
  76. else_result = create_else_body()
  77. self.current_block.flow = cfg_ir.create_jump(phi_block, [else_result])
  78. self.current_block = phi_block
  79. return param_def
  80. def analyze_if(self, instruction):
  81. """Analyzes an 'if' instruction."""
  82. def __analyze_condition():
  83. condition_node = self.analyze(instruction.condition)
  84. return self.current_block.append_definition(cfg_ir.Read(condition_node))
  85. return self.emit_select(
  86. __analyze_condition,
  87. lambda: self.analyze(instruction.if_clause),
  88. lambda:
  89. self.current_block.append_definition(cfg_ir.Literal(None))
  90. if instruction.else_clause is None
  91. else self.analyze(instruction.else_clause))
  92. def analyze_while(self, instruction):
  93. """Analyzes a 'while' instruction."""
  94. # Create blocks that look like this:
  95. #
  96. # !current_block(...):
  97. # ...
  98. # jump !loop_condition()
  99. #
  100. # !loop_condition():
  101. # $condition_node = <condition>
  102. # $condition = read condition_node
  103. # select $condition, !loop_body(), !loop_exit()
  104. #
  105. # !loop_body():
  106. # $result = <body>
  107. # jump !loop_condition()
  108. #
  109. # !loop_exit():
  110. # $nothing = literal None
  111. # ...
  112. loop_condition_block = cfg_ir.BasicBlock(self.counter)
  113. loop_body_block = cfg_ir.BasicBlock(self.counter)
  114. loop_exit_block = cfg_ir.BasicBlock(self.counter)
  115. self.loop_instructions[instruction] = (loop_condition_block, loop_exit_block)
  116. self.current_block.flow = cfg_ir.create_jump(loop_condition_block)
  117. self.current_block = loop_condition_block
  118. condition_node = self.analyze(instruction.condition)
  119. condition = self.current_block.append_definition(cfg_ir.Read(condition_node))
  120. self.current_block.flow = cfg_ir.SelectFlow(
  121. condition, cfg_ir.Branch(loop_body_block), cfg_ir.Branch(loop_exit_block))
  122. self.current_block = loop_body_block
  123. self.analyze(instruction.body)
  124. self.current_block.flow = cfg_ir.create_jump(loop_condition_block)
  125. self.current_block = loop_exit_block
  126. return loop_exit_block.append_definition(cfg_ir.Literal(None))
  127. def analyze_return(self, instruction):
  128. """Analyzes a 'return' instruction."""
  129. if instruction.value is None:
  130. return_value = self.current_block.append_definition(cfg_ir.Literal(None))
  131. else:
  132. return_value = self.analyze(instruction.value)
  133. # Don't forget to deallocate the root node.
  134. self.current_block.append_definition(cfg_ir.DeallocateRootNode(self.root_node))
  135. self.current_block.flow = cfg_ir.ReturnFlow(return_value)
  136. self.current_block = cfg_ir.BasicBlock(self.counter)
  137. return self.current_block.append_definition(cfg_ir.Literal(None))
  138. def analyze_constant(self, instruction):
  139. """Analyzes a 'constant' instruction."""
  140. return self.current_block.append_definition(cfg_ir.Literal(instruction.constant_id))
  141. def analyze_resolve(self, instruction):
  142. """Analyzes a 'resolve' instruction."""
  143. def __resolve_global_carefully():
  144. # We might be resolving a global that does not exist. In that case, we
  145. # need to throw. We want to create the following blocks:
  146. #
  147. # !current_block(...):
  148. # ...
  149. # $resolved_global = resolve-global global
  150. # $nothing = literal None
  151. # $condition = binary $resolved_global, 'is', $nothing
  152. # select $condition, !no_global_block(), !global_exists_block()
  153. #
  154. # !no_global_block():
  155. # $message = literal <GLOBAL_NOT_FOUND_MESSAGE_FORMAT % instruction.variable.name>
  156. # $exception = direct-call "simple-positional" Exception(message=$message)
  157. # throw $exception
  158. #
  159. # !global_exists_block():
  160. # ...
  161. #
  162. no_global_block = cfg_ir.BasicBlock(self.counter)
  163. global_exists_block = cfg_ir.BasicBlock(self.counter)
  164. resolved_global = self.current_block.append_definition(
  165. cfg_ir.ResolveGlobal(instruction.variable))
  166. nothing = self.current_block.append_definition(cfg_ir.Literal(None))
  167. condition = self.current_block.append_definition(
  168. cfg_ir.Binary(resolved_global, 'is', nothing))
  169. self.current_block.flow = cfg_ir.SelectFlow(
  170. condition, cfg_ir.Branch(no_global_block), cfg_ir.Branch(global_exists_block))
  171. message = no_global_block.append_definition(
  172. cfg_ir.Literal(
  173. jit_runtime.GLOBAL_NOT_FOUND_MESSAGE_FORMAT % instruction.variable.name))
  174. exception = no_global_block.append_definition(
  175. cfg_ir.DirectFunctionCall(
  176. 'Exception',
  177. [('message', message)],
  178. cfg_ir.SIMPLE_POSITIONAL_CALLING_CONVENTION))
  179. no_global_block.flow = cfg_ir.ThrowFlow(exception)
  180. self.current_block = global_exists_block
  181. return resolved_global
  182. return self.emit_select(
  183. lambda:
  184. self.current_block.append_definition(
  185. cfg_ir.CheckLocalExists(instruction.variable)),
  186. lambda:
  187. self.current_block.append_definition(
  188. cfg_ir.ResolveLocal(instruction.variable)),
  189. __resolve_global_carefully)
  190. def analyze_declare(self, instruction):
  191. """Analyzes a 'declare' instruction."""
  192. return self.current_block.append_definition(
  193. cfg_ir.DeclareLocal(instruction.variable, self.root_node))
  194. def analyze_global(self, instruction):
  195. """Analyzes a 'global' instruction."""
  196. resolved_global = self.current_block.append_definition(
  197. cfg_ir.ResolveGlobal(instruction.variable))
  198. nothing = self.current_block.append_definition(cfg_ir.Literal(None))
  199. return self.emit_select(
  200. lambda:
  201. self.current_block.append_definition(
  202. cfg_ir.Binary(resolved_global, 'is', nothing)),
  203. lambda:
  204. self.current_block.append_definition(
  205. cfg_ir.DeclareGlobal(instruction.variable)),
  206. lambda: resolved_global)
  207. def analyze_assign(self, instruction):
  208. """Analyzes an 'assign' instruction."""
  209. pointer_result = self.analyze(instruction.pointer)
  210. value_result = self.analyze(instruction.value)
  211. return self.current_block.append_definition(
  212. cfg_ir.StoreAtPointer(pointer_result, value_result))
  213. def analyze_access(self, instruction):
  214. """Analyzes an 'access' instruction."""
  215. pointer_result = self.analyze(instruction.pointer)
  216. return self.current_block.append_definition(cfg_ir.LoadPointer(pointer_result))
  217. def analyze_output(self, instruction):
  218. """Analyzes an 'output' instruction."""
  219. value_result = self.analyze(instruction.value)
  220. return self.current_block.append_definition(cfg_ir.Output(value_result))
  221. def analyze_input(self, _):
  222. """Analyzes an 'input' instruction."""
  223. return self.current_block.append_definition(cfg_ir.Input())
  224. def analyze_break(self, instruction):
  225. """Analyzes a 'break' instruction."""
  226. if instruction.loop not in self.loop_instructions:
  227. raise jit_runtime.JitCompilationFailedException(
  228. "'break' instruction targets a 'while' loop that has not been defined yet.")
  229. _, exit_block = self.loop_instructions[instruction.loop]
  230. self.current_block.flow = cfg_ir.create_jump(exit_block)
  231. self.current_block = cfg_ir.BasicBlock(self.counter)
  232. return self.current_block.append_definition(cfg_ir.Literal(None))
  233. def analyze_continue(self, instruction):
  234. """Analyzes a 'continue' instruction."""
  235. if instruction.loop not in self.loop_instructions:
  236. raise jit_runtime.JitCompilationFailedException(
  237. "'continue' instruction targets a 'while' loop that has not been defined yet.")
  238. cond_block, _ = self.loop_instructions[instruction.loop]
  239. self.current_block.flow = cfg_ir.create_jump(cond_block)
  240. self.current_block = cfg_ir.BasicBlock(self.counter)
  241. return self.current_block.append_definition(cfg_ir.Literal(None))
  242. def analyze_call(self, instruction):
  243. """Analyzes the given 'call' instruction."""
  244. target = self.analyze(instruction.target)
  245. arg_list = []
  246. for key, arg_instruction in instruction.argument_list:
  247. arg_list.append((key, self.analyze(arg_instruction)))
  248. return self.current_block.append_definition(cfg_ir.IndirectFunctionCall(target, arg_list))
  249. instruction_analyzers = {
  250. bytecode_ir.SelectInstruction : analyze_if,
  251. bytecode_ir.WhileInstruction : analyze_while,
  252. bytecode_ir.ReturnInstruction : analyze_return,
  253. bytecode_ir.ConstantInstruction : analyze_constant,
  254. bytecode_ir.ResolveInstruction : analyze_resolve,
  255. bytecode_ir.DeclareInstruction : analyze_declare,
  256. bytecode_ir.GlobalInstruction : analyze_global,
  257. bytecode_ir.AssignInstruction : analyze_assign,
  258. bytecode_ir.AccessInstruction : analyze_access,
  259. bytecode_ir.OutputInstruction : analyze_output,
  260. bytecode_ir.InputInstruction : analyze_input,
  261. bytecode_ir.CallInstruction : analyze_call,
  262. bytecode_ir.BreakInstruction : analyze_break,
  263. bytecode_ir.ContinueInstruction : analyze_continue
  264. }