bytecode_to_cfg.py 15 KB

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