cfg_optimization.py 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341
  1. """Optimizes and analyzes CFG-IR."""
  2. from collections import defaultdict
  3. import modelverse_jit.cfg_ir as cfg_ir
  4. import modelverse_jit.cfg_dominators as cfg_dominators
  5. def get_directly_reachable_blocks(block):
  6. """Gets the set of all blocks that can be reached by taking a single branch from the
  7. given block."""
  8. return [branch.block for branch in block.flow.branches()]
  9. def get_reachable_blocks(entry_point):
  10. """Constructs the set of all reachable vertices from the given block."""
  11. # This is a simple O(n^2) algorithm. Maybe a faster algorithm is more appropriate here.
  12. def __add_block_children(block, results):
  13. for child in get_directly_reachable_blocks(block):
  14. if child not in results:
  15. results.add(child)
  16. __add_block_children(child, results)
  17. return results
  18. return __add_block_children(entry_point, set())
  19. def get_all_reachable_blocks(entry_point):
  20. """Constructs the set of all reachable vertices, for every block that is
  21. reachable from the given entry point."""
  22. # This is a simple O(n^3) algorithm. Maybe a faster algorithm is more appropriate here.
  23. results = {}
  24. all_blocks = get_reachable_blocks(entry_point)
  25. results[entry_point] = all_blocks
  26. for block in all_blocks:
  27. if block not in results:
  28. results[block] = get_reachable_blocks(block)
  29. return results
  30. def is_empty_block(block):
  31. """Tests if the given block contains no parameters or definitions."""
  32. return len(block.parameters) == 0 and len(block.definitions) == 0
  33. def optimize_flow(block):
  34. """Optimizes the given block's flow instruction."""
  35. changed = True
  36. while changed:
  37. changed = False
  38. # Select flow with a literal condition can be optimized to a direct jump.
  39. if (isinstance(block.flow, cfg_ir.SelectFlow)
  40. and cfg_ir.is_literal_def(block.flow.condition)):
  41. literal = cfg_ir.get_literal_def_value(block.flow.condition)
  42. block.flow = cfg_ir.JumpFlow(
  43. block.flow.if_branch if literal else block.flow.else_branch)
  44. changed = True
  45. # Jumps to blocks which contain no parameters or definitions can be replaced
  46. # by the target block's flow.
  47. if (isinstance(block.flow, cfg_ir.JumpFlow)
  48. and is_empty_block(block.flow.branch.block)
  49. and block.flow.branch.block is not block):
  50. block.flow = block.flow.branch.block.flow
  51. changed = True
  52. # Branches to blocks which contain nothing but a jump can be replaced by branches
  53. # to the jump's target.
  54. for branch in block.flow.branches():
  55. if (is_empty_block(branch.block)
  56. and branch.block is not block
  57. and isinstance(branch.block.flow, cfg_ir.JumpFlow)):
  58. new_branch = branch.block.flow.branch
  59. branch.block = new_branch.block
  60. branch.arguments = new_branch.arguments
  61. changed = True
  62. def get_all_blocks(entry_point):
  63. """Gets all basic blocks in the control-flow graph defined by the given entry point."""
  64. yield entry_point
  65. for block in get_reachable_blocks(entry_point):
  66. yield block
  67. def optimize_graph_flow(entry_point):
  68. """Optimizes all flow instructions in the graph defined by the given entry point."""
  69. for block in get_all_blocks(entry_point):
  70. optimize_flow(block)
  71. def merge_blocks(entry_point):
  72. """Merges blocks which have exactly one predecessor with said predecessor, if the
  73. predecessor has a jump flow instruction."""
  74. predecessor_map = cfg_dominators.get_all_predecessor_blocks(entry_point)
  75. queue = list(predecessor_map.keys())
  76. def __do_merge(source, target):
  77. for target_param, branch_arg in zip(target.parameters, source.flow.branch.arguments):
  78. source.append_definition(target_param)
  79. target_param.redefine(branch_arg)
  80. for target_def in target.definitions:
  81. source.append_definition(target_def)
  82. source.flow = target.flow
  83. for pred_set in predecessor_map.values():
  84. if target in pred_set:
  85. pred_set.remove(target)
  86. pred_set.add(source)
  87. while len(queue) > 0:
  88. block = queue.pop()
  89. preds = predecessor_map[block]
  90. if len(preds) == 1:
  91. single_pred = next(iter(preds))
  92. if isinstance(single_pred.flow, cfg_ir.JumpFlow):
  93. __do_merge(single_pred, block)
  94. def elide_local_checks(entry_point):
  95. """Tries to elide redundant checks on local variables."""
  96. # The plan here is to replace all check-local-exists defs by literals if
  97. # they are either dominated by an appropriate declare-local or not reachable
  98. # from a declare-local.
  99. local_checks = defaultdict(set)
  100. local_defs = defaultdict(set)
  101. for block in get_all_blocks(entry_point):
  102. for definition in block.definitions:
  103. if cfg_ir.is_value_def(definition, cfg_ir.CheckLocalExists):
  104. local_checks[cfg_ir.get_def_variable(definition).node_id].add(definition)
  105. elif cfg_ir.is_value_def(definition, cfg_ir.DeclareLocal):
  106. local_defs[cfg_ir.get_def_variable(definition).node_id].add(definition)
  107. dominator_tree = cfg_dominators.get_dominator_tree(entry_point)
  108. reachable_blocks = get_all_reachable_blocks(entry_point)
  109. for (variable, all_checks) in local_checks.items():
  110. for check in all_checks:
  111. is_reachable = False
  112. for local_def in local_defs[variable]:
  113. if dominator_tree.dominates_instruction(local_def, check):
  114. # Check is dominated by a definition. Replace it by a 'True' literal.
  115. check.redefine(cfg_ir.Literal(True))
  116. is_reachable = True
  117. break
  118. elif check.block in reachable_blocks[local_def.block]:
  119. is_reachable = True
  120. if not is_reachable:
  121. # Check cannot be reached from any definition. Replace it by a 'False' literal.
  122. check.redefine(cfg_ir.Literal(False))
  123. def eliminate_unused_definitions(entry_point):
  124. """Tries to eliminate unused definitions in the control-flow graphb defined by the
  125. given entry point."""
  126. def_dependencies = {}
  127. root_defs = set()
  128. for block in get_all_blocks(entry_point):
  129. for definition in block.definitions:
  130. def_dependencies[definition] = set(
  131. [dep for dep in definition.get_all_dependencies()
  132. if isinstance(dep, cfg_ir.Definition)])
  133. if definition.has_side_effects():
  134. root_defs.add(definition)
  135. for dep in block.flow.get_all_dependencies():
  136. if isinstance(dep, cfg_ir.Definition):
  137. root_defs.add(dep)
  138. live_defs = set()
  139. def __mark_live(definition):
  140. if definition in live_defs:
  141. return
  142. live_defs.add(definition)
  143. if definition in def_dependencies:
  144. for dep in def_dependencies[definition]:
  145. __mark_live(dep)
  146. for root in root_defs:
  147. __mark_live(root)
  148. dead_defs = set.difference(set(def_dependencies.keys()), live_defs)
  149. for dead_def in dead_defs:
  150. dead_def.block.remove_definition(dead_def)
  151. def get_trivial_phi_value(parameter_def, values):
  152. """Tests if the given parameter definition is an alias for another definition.
  153. If so, then the other definition is returned; otherwise, None."""
  154. result = None
  155. for elem in values:
  156. if elem is not parameter_def:
  157. if result is None:
  158. result = elem
  159. else:
  160. return None
  161. return result
  162. def eliminate_trivial_phis(entry_point):
  163. """Eliminates trivial block parameters, i.e., block parameters which are really
  164. aliases."""
  165. phi_values = defaultdict(set)
  166. all_blocks = list(get_all_blocks(entry_point))
  167. for block in all_blocks:
  168. for branch in block.flow.branches():
  169. for phi, arg in zip(branch.block.parameters, branch.arguments):
  170. phi_values[phi].add(arg)
  171. replacements = []
  172. for block in all_blocks:
  173. block_parameters = list(block.parameters)
  174. for parameter_def in block_parameters:
  175. trivial_phi_val = get_trivial_phi_value(
  176. parameter_def, phi_values[parameter_def])
  177. if trivial_phi_val is not None:
  178. replacements.append((parameter_def, trivial_phi_val))
  179. erase_parameters(entry_point, set([parameter_def for parameter_def, _ in replacements]))
  180. for parameter_def, trivial_phi_val in replacements:
  181. block = parameter_def.block
  182. parameter_def.redefine(trivial_phi_val)
  183. block.prepend_definition(parameter_def)
  184. def erase_parameters(entry_point, parameters_to_erase):
  185. """Erases all arguments for the given set of parameters, and then takes out the
  186. parameters themselves."""
  187. for block in get_all_blocks(entry_point):
  188. for branch in block.flow.branches():
  189. new_arg_list = []
  190. for parameter, arg in zip(branch.block.parameters, branch.arguments):
  191. if parameter not in parameters_to_erase:
  192. new_arg_list.append(arg)
  193. branch.arguments = new_arg_list
  194. for parameter_def in parameters_to_erase:
  195. parameter_def.block.remove_parameter(parameter_def)
  196. def apply_cfg_intrinsic(intrinsic_function, original_definition, named_args):
  197. """Applies the given intrinsic to the given sequence of named arguments."""
  198. kwargs = dict(named_args)
  199. kwargs['original_def'] = original_definition
  200. return intrinsic_function(**kwargs)
  201. def try_redefine_as_direct_call(definition, jit, called_globals):
  202. """Tries to redefine the given indirect call definition as a direct call."""
  203. call = cfg_ir.get_def_value(definition)
  204. if not isinstance(call, cfg_ir.IndirectFunctionCall):
  205. return
  206. target = cfg_ir.get_def_value(call.target)
  207. if isinstance(target, cfg_ir.LoadPointer):
  208. loaded_ptr = cfg_ir.get_def_value(target.pointer)
  209. if isinstance(loaded_ptr, cfg_ir.ResolveGlobal):
  210. resolved_var_name = loaded_ptr.variable.name
  211. called_globals.add(loaded_ptr)
  212. # Try to resolve the callee as an intrinsic.
  213. intrinsic = jit.get_cfg_intrinsic(resolved_var_name)
  214. if intrinsic is not None:
  215. apply_cfg_intrinsic(intrinsic, definition, call.argument_list)
  216. else:
  217. # Otherwise, build a thunk.
  218. thunk_name = jit.jit_thunk_global(resolved_var_name)
  219. definition.redefine(
  220. cfg_ir.DirectFunctionCall(
  221. thunk_name, call.argument_list, cfg_ir.JIT_CALLING_CONVENTION))
  222. called_globals.add(loaded_ptr)
  223. elif isinstance(target, cfg_ir.Literal):
  224. node_id = target.literal
  225. thunk_name = jit.jit_thunk_constant(node_id)
  226. definition.redefine(
  227. cfg_ir.DirectFunctionCall(
  228. thunk_name, call.argument_list, cfg_ir.JIT_CALLING_CONVENTION))
  229. def get_checked_global(definition):
  230. """If the definition is a check that tests if a global does not exist, then
  231. the instruction that resolves the global is returned; otherwise None."""
  232. def_value = cfg_ir.get_def_value(definition)
  233. if not isinstance(def_value, cfg_ir.Binary):
  234. return None
  235. if def_value.operator != 'is':
  236. return None
  237. def __get_checked_global_single_dir(lhs, rhs):
  238. if (isinstance(lhs, cfg_ir.ResolveGlobal)
  239. and isinstance(rhs, cfg_ir.Literal)
  240. and rhs.literal is None):
  241. return lhs
  242. else:
  243. return None
  244. bin_lhs = cfg_ir.get_def_value(def_value.lhs)
  245. bin_rhs = cfg_ir.get_def_value(def_value.rhs)
  246. result = __get_checked_global_single_dir(bin_lhs, bin_rhs)
  247. if result is None:
  248. result = __get_checked_global_single_dir(bin_rhs, bin_lhs)
  249. return result
  250. def optimize_calls(entry_point, jit):
  251. """Converts indirect calls to direct calls in the control-flow graph defined by the
  252. given entry point."""
  253. called_globals = set()
  254. global_exists_defs = defaultdict(list)
  255. all_blocks = list(get_all_blocks(entry_point))
  256. for block in all_blocks:
  257. for definition in block.definitions:
  258. checked_global = get_checked_global(definition)
  259. if checked_global is not None:
  260. global_exists_defs[checked_global].append(definition)
  261. else:
  262. try_redefine_as_direct_call(definition, jit, called_globals)
  263. for resolve_global in called_globals:
  264. for exists_def in global_exists_defs[resolve_global]:
  265. exists_def.redefine(cfg_ir.Literal(False))
  266. def simplify_values(entry_point):
  267. """Simplifies values in the control-flow graph defined by the given entry point."""
  268. for block in get_all_blocks(entry_point):
  269. for definition in block.definitions:
  270. def_val = cfg_ir.get_def_value(definition)
  271. if isinstance(def_val, cfg_ir.Read):
  272. read_node = cfg_ir.get_def_value(def_val.node)
  273. if isinstance(read_node, cfg_ir.CreateNode):
  274. definition.redefine(read_node.value)
  275. elif isinstance(def_val, cfg_ir.Binary):
  276. lhs = cfg_ir.get_def_value(def_val.lhs)
  277. rhs = cfg_ir.get_def_value(def_val.rhs)
  278. if isinstance(lhs, cfg_ir.Literal) and isinstance(rhs, cfg_ir.Literal):
  279. definition.redefine(
  280. cfg_ir.Literal(
  281. eval('%r %s %r' % (lhs.literal, def_val.operator, rhs.literal))))
  282. def optimize(entry_point, jit):
  283. """Optimizes the control-flow graph defined by the given entry point."""
  284. optimize_graph_flow(entry_point)
  285. elide_local_checks(entry_point)
  286. optimize_graph_flow(entry_point)
  287. eliminate_trivial_phis(entry_point)
  288. optimize_calls(entry_point, jit)
  289. simplify_values(entry_point)
  290. eliminate_unused_definitions(entry_point)
  291. optimize_graph_flow(entry_point)
  292. merge_blocks(entry_point)
  293. eliminate_unused_definitions(entry_point)