cfg_optimization.py 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521
  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. import modelverse_jit.cfg_ssa_construction as cfg_ssa_construction
  6. import modelverse_jit.cfg_data_structures as cfg_data_structures
  7. import modelverse_kernel.primitives as primitive_functions
  8. def is_empty_block(block):
  9. """Tests if the given block contains no parameters or definitions."""
  10. return len(block.parameters) == 0 and len(block.definitions) == 0
  11. def optimize_flow(block):
  12. """Optimizes the given block's flow instruction."""
  13. changed = True
  14. while changed:
  15. changed = False
  16. # Select flow with a literal condition can be optimized to a direct jump.
  17. if (isinstance(block.flow, cfg_ir.SelectFlow)
  18. and cfg_ir.is_literal_def(block.flow.condition)):
  19. literal = cfg_ir.get_literal_def_value(block.flow.condition)
  20. block.flow = cfg_ir.JumpFlow(
  21. block.flow.if_branch if literal else block.flow.else_branch)
  22. changed = True
  23. # Jumps to blocks which contain no parameters or definitions can be replaced
  24. # by the target block's flow.
  25. if (isinstance(block.flow, cfg_ir.JumpFlow)
  26. and is_empty_block(block.flow.branch.block)
  27. and block.flow.branch.block is not block):
  28. block.flow = block.flow.branch.block.flow
  29. changed = True
  30. # Branches to blocks which contain nothing but a jump can be replaced by branches
  31. # to the jump's target.
  32. for branch in block.flow.branches():
  33. if (is_empty_block(branch.block)
  34. and branch.block is not block
  35. and isinstance(branch.block.flow, cfg_ir.JumpFlow)):
  36. new_branch = branch.block.flow.branch
  37. branch.block = new_branch.block
  38. branch.arguments = new_branch.arguments
  39. changed = True
  40. def optimize_graph_flow(entry_point):
  41. """Optimizes all flow instructions in the graph defined by the given entry point."""
  42. for block in cfg_ir.get_all_blocks(entry_point):
  43. optimize_flow(block)
  44. def merge_blocks(entry_point):
  45. """Merges blocks which have exactly one predecessor with said predecessor, if the
  46. predecessor has a jump flow instruction."""
  47. predecessor_map = cfg_ir.get_all_predecessor_blocks(entry_point)
  48. queue = set(predecessor_map.keys())
  49. queue.add(entry_point)
  50. def __do_merge(source, target):
  51. target_params = list(target.parameters)
  52. branch_args = list(source.flow.branch.arguments)
  53. for target_param, branch_arg in zip(target_params, branch_args):
  54. target.remove_parameter(target_param)
  55. target_param.redefine(branch_arg)
  56. source.append_definition(target_param)
  57. target_defs = list(target.definitions)
  58. for target_def in target_defs:
  59. target.remove_definition(target_def)
  60. source.append_definition(target_def)
  61. source.flow = target.flow
  62. for pred_set in predecessor_map.values():
  63. if target in pred_set:
  64. pred_set.remove(target)
  65. pred_set.add(source)
  66. while len(queue) > 0:
  67. block = queue.pop()
  68. if isinstance(block.flow, cfg_ir.JumpFlow):
  69. next_block = block.flow.branch.block
  70. preds = predecessor_map[next_block]
  71. if (len(preds) == 1
  72. and next(iter(preds)) == block
  73. and block != next_block
  74. and next_block != entry_point):
  75. __do_merge(block, next_block)
  76. del predecessor_map[next_block]
  77. queue.add(block)
  78. if next_block in queue:
  79. queue.remove(next_block)
  80. def elide_local_checks(entry_point):
  81. """Tries to elide redundant checks on local variables."""
  82. # The plan here is to replace all check-local-exists defs by literals if
  83. # they are either dominated by an appropriate declare-local or not reachable
  84. # from a declare-local.
  85. local_checks = defaultdict(set)
  86. local_defs = defaultdict(set)
  87. for block in cfg_ir.get_all_blocks(entry_point):
  88. for definition in block.definitions:
  89. if cfg_ir.is_value_def(definition, cfg_ir.CheckLocalExists):
  90. local_checks[cfg_ir.get_def_variable(definition).node_id].add(definition)
  91. elif cfg_ir.is_value_def(definition, cfg_ir.DeclareLocal):
  92. local_defs[cfg_ir.get_def_variable(definition).node_id].add(definition)
  93. dominator_tree = cfg_dominators.get_dominator_tree(entry_point)
  94. reachable_blocks = cfg_ir.get_all_reachable_blocks(entry_point)
  95. for (variable, all_checks) in local_checks.items():
  96. for check in all_checks:
  97. is_reachable = False
  98. for local_def in local_defs[variable]:
  99. if dominator_tree.dominates_instruction(local_def, check):
  100. # Check is dominated by a definition. Replace it by a 'True' literal.
  101. check.redefine(cfg_ir.Literal(True))
  102. is_reachable = True
  103. break
  104. elif check.block in reachable_blocks[local_def.block]:
  105. is_reachable = True
  106. if not is_reachable:
  107. # Check cannot be reached from any definition. Replace it by a 'False' literal.
  108. check.redefine(cfg_ir.Literal(False))
  109. def eliminate_unused_definitions(entry_point):
  110. """Tries to eliminate unused definitions in the control-flow graphb defined by the
  111. given entry point."""
  112. def_dependencies = defaultdict(set)
  113. root_defs = set()
  114. # Gather dependencies.
  115. for block in cfg_ir.get_all_blocks(entry_point):
  116. for definition in block.parameters + block.definitions:
  117. all_dependencies = list(definition.get_all_dependencies())
  118. def_dependencies[definition].update(
  119. [dep for dep in all_dependencies
  120. if isinstance(dep, cfg_ir.Definition)])
  121. if len(all_dependencies) > 0 and definition.has_bidirectional_dependencies():
  122. for dep in all_dependencies:
  123. def_dependencies[dep].add(definition)
  124. if definition.has_side_effects():
  125. root_defs.add(definition)
  126. for dep in block.flow.get_dependencies():
  127. if isinstance(dep, cfg_ir.Definition):
  128. root_defs.add(dep)
  129. else:
  130. assert isinstance(dep, cfg_ir.Branch)
  131. for param, arg in zip(dep.block.parameters, dep.arguments):
  132. def_dependencies[param].add(arg)
  133. # Figure out which definitions are live.
  134. live_defs = set()
  135. def __mark_live(definition):
  136. if definition in live_defs:
  137. return
  138. live_defs.add(definition)
  139. if definition in def_dependencies:
  140. for dep in def_dependencies[definition]:
  141. __mark_live(dep)
  142. for root in root_defs:
  143. __mark_live(root)
  144. # Remove all dead definitions.
  145. dead_defs = set.difference(set(def_dependencies.keys()), live_defs)
  146. dead_phis = set()
  147. for dead_def in dead_defs:
  148. if isinstance(dead_def.value, cfg_ir.BlockParameter):
  149. dead_phis.add(dead_def)
  150. else:
  151. dead_def.block.remove_definition(dead_def)
  152. erase_parameters(entry_point, dead_phis)
  153. def eliminate_trivial_phis(entry_point):
  154. """Eliminates trivial block parameters, i.e., block parameters which are really
  155. aliases."""
  156. phi_values = defaultdict(set)
  157. all_blocks = list(cfg_ir.get_all_blocks(entry_point))
  158. for block in all_blocks:
  159. for branch in block.flow.branches():
  160. for phi, arg in zip(branch.block.parameters, branch.arguments):
  161. phi_values[phi].add(arg)
  162. replacements = []
  163. for block in all_blocks:
  164. block_parameters = list(block.parameters)
  165. for parameter_def in block_parameters:
  166. trivial_phi_val = cfg_ir.get_trivial_phi_value(
  167. parameter_def, phi_values[parameter_def])
  168. if trivial_phi_val is not None:
  169. replacements.append((parameter_def, trivial_phi_val))
  170. erase_parameters(entry_point, set([parameter_def for parameter_def, _ in replacements]))
  171. for parameter_def, trivial_phi_val in replacements:
  172. block = parameter_def.block
  173. parameter_def.redefine(trivial_phi_val)
  174. block.prepend_definition(parameter_def)
  175. def erase_parameters(entry_point, parameters_to_erase):
  176. """Erases all arguments for the given set of parameters, and then takes out the
  177. parameters themselves."""
  178. for block in cfg_ir.get_all_blocks(entry_point):
  179. for branch in block.flow.branches():
  180. new_arg_list = []
  181. for parameter, arg in zip(branch.block.parameters, branch.arguments):
  182. if parameter not in parameters_to_erase:
  183. new_arg_list.append(arg)
  184. branch.arguments = new_arg_list
  185. for parameter_def in parameters_to_erase:
  186. parameter_def.block.remove_parameter(parameter_def)
  187. def apply_cfg_intrinsic(intrinsic_function, original_definition, named_args):
  188. """Applies the given intrinsic to the given sequence of named arguments."""
  189. kwargs = dict(named_args)
  190. kwargs['original_def'] = original_definition
  191. return intrinsic_function(**kwargs)
  192. def try_redefine_as_direct_call(definition, jit, called_globals):
  193. """Tries to redefine the given indirect call definition as a direct call."""
  194. call = cfg_ir.get_def_value(definition)
  195. if not isinstance(call, cfg_ir.IndirectFunctionCall):
  196. return
  197. target = cfg_ir.get_def_value(call.target)
  198. if isinstance(target, cfg_ir.LoadPointer):
  199. loaded_ptr = cfg_ir.get_def_value(target.pointer)
  200. if isinstance(loaded_ptr, cfg_ir.ResolveGlobal):
  201. resolved_var_name = loaded_ptr.variable.name
  202. called_globals.add(loaded_ptr)
  203. # Try to resolve the callee as an intrinsic.
  204. intrinsic = jit.get_cfg_intrinsic(resolved_var_name)
  205. if intrinsic is not None:
  206. apply_cfg_intrinsic(intrinsic, definition, call.argument_list)
  207. else:
  208. # Otherwise, build a thunk.
  209. thunk_name = jit.jit_thunk_global(resolved_var_name)
  210. calling_convention = (
  211. cfg_ir.JIT_NO_GC_CALLING_CONVENTION
  212. if jit.get_intrinsic(thunk_name) is not None
  213. else cfg_ir.JIT_CALLING_CONVENTION)
  214. definition.redefine(
  215. cfg_ir.DirectFunctionCall(
  216. thunk_name, call.argument_list, calling_convention))
  217. called_globals.add(loaded_ptr)
  218. elif isinstance(target, cfg_ir.Literal):
  219. node_id = target.literal
  220. thunk_name = jit.jit_thunk_constant(node_id)
  221. definition.redefine(
  222. cfg_ir.DirectFunctionCall(
  223. thunk_name, call.argument_list, cfg_ir.JIT_CALLING_CONVENTION))
  224. def get_checked_global(definition):
  225. """If the definition is a check that tests if a global does not exist, then
  226. the instruction that resolves the global is returned; otherwise None."""
  227. def_value = cfg_ir.get_def_value(definition)
  228. if not isinstance(def_value, cfg_ir.Binary):
  229. return None
  230. if def_value.operator != 'is':
  231. return None
  232. def __get_checked_global_single_dir(lhs, rhs):
  233. if (isinstance(lhs, cfg_ir.ResolveGlobal)
  234. and isinstance(rhs, cfg_ir.Literal)
  235. and rhs.literal is None):
  236. return lhs
  237. else:
  238. return None
  239. bin_lhs = cfg_ir.get_def_value(def_value.lhs)
  240. bin_rhs = cfg_ir.get_def_value(def_value.rhs)
  241. result = __get_checked_global_single_dir(bin_lhs, bin_rhs)
  242. if result is None:
  243. result = __get_checked_global_single_dir(bin_rhs, bin_lhs)
  244. return result
  245. def optimize_calls(entry_point, jit):
  246. """Converts indirect calls to direct calls in the control-flow graph defined by the
  247. given entry point."""
  248. called_globals = set()
  249. global_exists_defs = defaultdict(list)
  250. all_blocks = list(cfg_ir.get_all_blocks(entry_point))
  251. for block in all_blocks:
  252. for definition in block.definitions:
  253. checked_global = get_checked_global(definition)
  254. if checked_global is not None:
  255. global_exists_defs[checked_global].append(definition)
  256. else:
  257. try_redefine_as_direct_call(definition, jit, called_globals)
  258. for resolve_global in called_globals:
  259. for exists_def in global_exists_defs[resolve_global]:
  260. exists_def.redefine(cfg_ir.Literal(False))
  261. def simplify_values(entry_point):
  262. """Simplifies values in the control-flow graph defined by the given entry point."""
  263. for block in cfg_ir.get_all_blocks(entry_point):
  264. for definition in block.definitions:
  265. def_val = cfg_ir.get_def_value(definition)
  266. if isinstance(def_val, cfg_ir.Read):
  267. read_node = cfg_ir.get_def_value(def_val.node)
  268. if isinstance(read_node, cfg_ir.CreateNode):
  269. definition.redefine(read_node.value)
  270. elif isinstance(def_val, cfg_ir.Binary):
  271. lhs = cfg_ir.get_def_value(def_val.lhs)
  272. rhs = cfg_ir.get_def_value(def_val.rhs)
  273. if isinstance(lhs, cfg_ir.Literal) and isinstance(rhs, cfg_ir.Literal):
  274. definition.redefine(
  275. cfg_ir.Literal(
  276. eval('%r %s %r' % (lhs.literal, def_val.operator, rhs.literal))))
  277. def inline_constants(entry_point):
  278. """Replaces reads of constant nodes by the literals they contain."""
  279. for block in cfg_ir.get_all_blocks(entry_point):
  280. for definition in block.definitions:
  281. def_val = cfg_ir.get_def_value(definition)
  282. if isinstance(def_val, cfg_ir.Read):
  283. read_node = cfg_ir.get_def_value(def_val.node)
  284. if isinstance(read_node, cfg_ir.Literal):
  285. val, = yield [("RV", [read_node.literal])]
  286. definition.redefine(cfg_ir.Literal(val))
  287. def expand_indirect_definitions(entry_point):
  288. """Replaces indirect definitions by the values referred to by those definitions."""
  289. def __expand_indirect_defs(value):
  290. dependencies = value.get_dependencies()
  291. if len(dependencies) == 0:
  292. return value
  293. else:
  294. new_dependencies = []
  295. for dep in dependencies:
  296. new_dep = dep
  297. if isinstance(new_dep, cfg_ir.Definition):
  298. while isinstance(new_dep.value, cfg_ir.Definition):
  299. new_dep = new_dep.value
  300. else:
  301. new_dep = __expand_indirect_defs(new_dep)
  302. new_dependencies.append(new_dep)
  303. return value.create(new_dependencies)
  304. for block in cfg_ir.get_all_blocks(entry_point):
  305. block_definitions = list(block.definitions)
  306. for definition in block_definitions:
  307. if isinstance(definition.value, cfg_ir.Definition):
  308. block.remove_definition(definition)
  309. else:
  310. definition.redefine(
  311. __expand_indirect_defs(definition.value))
  312. block.flow = __expand_indirect_defs(block.flow)
  313. def optimize_reads(entry_point):
  314. """Tries to replace repeated reads by a single read."""
  315. cfg_ir.match_and_rewrite(
  316. entry_point,
  317. lambda _: True,
  318. lambda use_def, _: cfg_ir.is_value_def(use_def, cfg_ir.Read),
  319. lambda def_def:
  320. def_def.redefine(
  321. cfg_ir.Read(def_def.insert_before(def_def.value))),
  322. lambda use_def, def_def: use_def.redefine(def_def))
  323. def protect_from_gc(entry_point):
  324. """Protects locals in the control-flow graph defined by the given
  325. entry point from the GC."""
  326. root_node = entry_point.prepend_definition(cfg_ir.AllocateRootNode())
  327. def protect_def_from_gc(definition):
  328. """Protects the given definition from the GC."""
  329. definition.insert_after(cfg_ir.create_gc_protect(definition, root_node))
  330. def maybe_protect_def_from_gc(definition):
  331. """Protects the given definition from the GC, if its result is not None."""
  332. definition.insert_after(cfg_ir.create_conditional_gc_protect(definition, root_node))
  333. for block in cfg_ir.get_all_blocks(entry_point):
  334. for definition in block.definitions:
  335. def_value = cfg_ir.get_def_value(definition)
  336. if isinstance(def_value, cfg_ir.CreateNode):
  337. protect_def_from_gc(definition)
  338. elif (isinstance(def_value, cfg_ir.IndirectFunctionCall)
  339. or (isinstance(def_value, cfg_ir.DirectFunctionCall)
  340. and (def_value.calling_convention == cfg_ir.JIT_CALLING_CONVENTION
  341. or def_value.calling_convention == cfg_ir.JIT_NO_GC_CALLING_CONVENTION
  342. or def_value.calling_convention == cfg_ir.MACRO_IO_CALLING_CONVENTION)
  343. and def_value.has_value())):
  344. maybe_protect_def_from_gc(definition)
  345. if isinstance(block.flow, (cfg_ir.ReturnFlow, cfg_ir.ThrowFlow)):
  346. block.append_definition(cfg_ir.DeallocateRootNode(root_node))
  347. def elide_gc_protects(entry_point):
  348. """Tries to elide GC protection values."""
  349. # We don't need to protect a value from the GC if it is used for the
  350. # last time _before_ the GC has an opportunity to kick in. To simplify
  351. # things, we'll do a quick block-based analysis.
  352. def __may_cause_gc(definition):
  353. def_value = cfg_ir.get_def_value(definition)
  354. if isinstance(def_value, cfg_ir.IndirectFunctionCall):
  355. return True
  356. elif (isinstance(def_value, cfg_ir.DirectFunctionCall)
  357. and (def_value.calling_convention == cfg_ir.JIT_CALLING_CONVENTION
  358. or def_value.calling_convention == cfg_ir.MACRO_IO_CALLING_CONVENTION)):
  359. return True
  360. else:
  361. return False
  362. def __get_protected_def(def_or_value):
  363. value = cfg_ir.get_def_value(def_or_value)
  364. if cfg_ir.is_call(
  365. value, target_name=cfg_ir.GC_PROTECT_MACRO_NAME,
  366. calling_convention=cfg_ir.MACRO_POSITIONAL_CALLING_CONVENTION):
  367. _, protected_def = value.argument_list[0]
  368. return protected_def
  369. elif cfg_ir.is_call(
  370. value, target_name=cfg_ir.MAYBE_GC_PROTECT_MACRO_NAME,
  371. calling_convention=cfg_ir.MACRO_POSITIONAL_CALLING_CONVENTION):
  372. _, protected_def = value.argument_list[1]
  373. return protected_def
  374. else:
  375. return None
  376. def_blocks = {}
  377. def __register_def_or_use(definition, block):
  378. if definition in def_blocks and def_blocks[definition] != block:
  379. # Definition seems to be used across basic blocks.
  380. ineligible_defs.add(definition)
  381. def_blocks[definition] = block
  382. ineligible_defs = set()
  383. def_protections = defaultdict(list)
  384. for block in cfg_ir.get_all_blocks(entry_point):
  385. no_gc_defs = set()
  386. block_defs = set()
  387. first_gc = {}
  388. last_def_uses = {}
  389. for i, definition in enumerate(block.definitions):
  390. if isinstance(definition.value, cfg_ir.Definition):
  391. # Handling definitions of definitions is complicated and they should already have
  392. # been expanded at this point. Just mark them as ineligible.
  393. ineligible_defs.add(definition)
  394. ineligible_defs.add(definition.value)
  395. continue
  396. protected_def = __get_protected_def(definition)
  397. if protected_def is not None:
  398. # We just ran into a gc_protect/maybe_gc_protect.
  399. def_protections[protected_def].append(definition)
  400. continue
  401. block_defs.add(definition)
  402. __register_def_or_use(definition, block)
  403. for dependency in definition.get_all_dependencies():
  404. __register_def_or_use(dependency, block)
  405. last_def_uses[dependency] = i
  406. if __may_cause_gc(definition):
  407. for gc_def in no_gc_defs:
  408. first_gc[gc_def] = i
  409. no_gc_defs = set()
  410. no_gc_defs.add(definition)
  411. # Mark all branch arguments as ineligible.
  412. for branch in block.flow.branches():
  413. ineligible_defs.update(branch.arguments)
  414. for dependency in block.flow.get_dependencies():
  415. last_def_uses[dependency] = None
  416. for definition in block_defs:
  417. if definition in ineligible_defs:
  418. # Definition was already ineligible.
  419. continue
  420. # Mark `definition` as ineligible if there is a GC definition in the range of
  421. # definitions (definition, last_def_uses[definition]].
  422. if definition in first_gc:
  423. if definition in last_def_uses:
  424. last_use = last_def_uses[definition]
  425. if last_use is None or first_gc[definition] <= last_use:
  426. ineligible_defs.add(definition)
  427. # Elide all GC protections for definitions which are not in the `ineligible_defs` set.
  428. for protected, protections in def_protections.items():
  429. if protected not in ineligible_defs:
  430. for protect_def in protections:
  431. protect_def.redefine(cfg_ir.Literal(None))
  432. def optimize(entry_point, jit):
  433. """Optimizes the control-flow graph defined by the given entry point.
  434. A potentially altered entry point is returned."""
  435. optimize_graph_flow(entry_point)
  436. elide_local_checks(entry_point)
  437. optimize_graph_flow(entry_point)
  438. eliminate_trivial_phis(entry_point)
  439. entry_point = cfg_ssa_construction.construct_ssa_form(entry_point)
  440. optimize_calls(entry_point, jit)
  441. cfg_data_structures.optimize_data_structures(entry_point)
  442. yield [("CALL_ARGS", [inline_constants, (entry_point,)])]
  443. optimize_reads(entry_point)
  444. simplify_values(entry_point)
  445. eliminate_unused_definitions(entry_point)
  446. optimize_graph_flow(entry_point)
  447. expand_indirect_definitions(entry_point)
  448. eliminate_unused_definitions(entry_point)
  449. merge_blocks(entry_point)
  450. protect_from_gc(entry_point)
  451. elide_gc_protects(entry_point)
  452. eliminate_unused_definitions(entry_point)
  453. raise primitive_functions.PrimitiveFinished(entry_point)