cfg_to_tree.py 36 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865
  1. """Lowers CFG-IR to tree-IR."""
  2. from collections import defaultdict
  3. import modelverse_jit.cfg_ir as cfg_ir
  4. import modelverse_jit.cfg_optimization as cfg_optimization
  5. import modelverse_jit.tree_ir as tree_ir
  6. import modelverse_jit.runtime as jit_runtime
  7. import modelverse_jit.bytecode_to_tree as bytecode_to_tree
  8. # The CFG deconstruction code here is based on the relooper algorithm
  9. # as detailed in https://github.com/kripken/Relooper/blob/master/paper.pdf
  10. class FlowGraphComponent(object):
  11. """Represents a control-flow graph component."""
  12. def __init__(self, entry_blocks, blocks, reachable):
  13. self.entry_blocks = entry_blocks
  14. self.blocks = blocks
  15. self.reachable = reachable
  16. def get_entry_reachable_blocks(self):
  17. """Gets the set of all blocks that are reachable from the entry points."""
  18. return set.union(*[self.get_reachable_blocks(block) for block in self.entry_blocks])
  19. def get_reachable_blocks(self, block):
  20. """Gets all blocks in this component that are reachable from the given block."""
  21. return set.intersection(self.reachable[block], self.blocks)
  22. def get_directly_reachable_blocks(self, block):
  23. """Gets all blocks in this component that are reachable from the given block by taking
  24. exactly one branch."""
  25. return set.intersection(cfg_optimization.get_directly_reachable_blocks(block), self.blocks)
  26. def can_reach(self, source_block, target_block):
  27. """Tests if the first block can reach the second."""
  28. return target_block in self.reachable[source_block] and target_block in self.blocks
  29. def sub_component(self, new_entry_points):
  30. """Creates a sub-component of this component, with the given new entry points."""
  31. result = FlowGraphComponent(new_entry_points, self.blocks, self.reachable)
  32. result.blocks = result.get_entry_reachable_blocks()
  33. return result
  34. def create_graph_component(entry_point):
  35. """Creates a flow graph component from the given entry point."""
  36. reachable = cfg_optimization.get_all_reachable_blocks(entry_point)
  37. all_blocks = set(reachable[entry_point])
  38. all_blocks.add(entry_point)
  39. return FlowGraphComponent([entry_point], all_blocks, reachable)
  40. class SimpleBlock(object):
  41. """A 'simple' block in the relooper algorithm."""
  42. def __init__(self, body, next_block):
  43. self.body = body
  44. self.next_block = next_block
  45. def lower(self, state):
  46. """Lowers this 'simple' block to a tree."""
  47. return tree_ir.create_block(
  48. state.lower_block(self.body),
  49. self.next_block.lower(state))
  50. class EmptyBlock(object):
  51. """An empty relooper block."""
  52. def lower(self, _):
  53. """Lowers this empty block to a tree."""
  54. return tree_ir.EmptyInstruction()
  55. class LoopBlock(object):
  56. """A 'loop' block in the relooper algorithm."""
  57. def __init__(self, inner, next_block):
  58. self.inner = inner
  59. self.next_block = next_block
  60. def lower(self, state):
  61. """Lowers this 'loop' block to a tree."""
  62. return tree_ir.create_block(
  63. tree_ir.LoopInstruction(self.inner.lower(state)),
  64. self.next_block.lower(state))
  65. class MultipleBlock(object):
  66. """A 'multiple' block in the relooper algorithm that does _not_ require a loop."""
  67. def __init__(self, handled_blocks, next_block):
  68. self.handled_blocks = handled_blocks
  69. self.next_block = next_block
  70. def lower_handled_blocks(self, state):
  71. """Lowers the handled blocks of this 'multiple' block to a tree."""
  72. result = tree_ir.EmptyInstruction()
  73. for entry, block in self.handled_blocks:
  74. result = tree_ir.SelectInstruction(
  75. tree_ir.BinaryInstruction(
  76. tree_ir.LoadLocalInstruction(state.label_variable),
  77. '==',
  78. tree_ir.LiteralInstruction(entry.index)),
  79. block.lower(state),
  80. result)
  81. return result
  82. def lower(self, state):
  83. """Lowers this 'multiple' block to a tree."""
  84. return tree_ir.create_block(
  85. self.lower_handled_blocks(state),
  86. self.next_block.lower(state))
  87. class MultipleLoopBlock(MultipleBlock):
  88. """A 'multiple' block in the relooper algorithm."""
  89. def __init__(self, handled_blocks, next_block):
  90. MultipleBlock.__init__(self, handled_blocks, next_block)
  91. def lower(self, state):
  92. """Lowers this 'multiple' block to a tree."""
  93. return tree_ir.create_block(
  94. tree_ir.LoopInstruction(self.lower_handled_blocks(state)),
  95. self.next_block.lower(state))
  96. class ContinueFlow(cfg_ir.FlowInstruction):
  97. """Represents a control flow instruction which continues to the next loop iteration."""
  98. def __init__(self, loop):
  99. cfg_ir.FlowInstruction.__init__(self)
  100. self.loop = loop
  101. def get_dependencies(self):
  102. """Gets all definitions and instructions on which this instruction depends."""
  103. return []
  104. def branches(self):
  105. """Gets a list of basic blocks targeted by this flow instruction."""
  106. return []
  107. def __str__(self):
  108. return 'continue'
  109. class BreakFlow(cfg_ir.FlowInstruction):
  110. """Represents a control flow instruction which breaks out of a loop."""
  111. def __init__(self, loop):
  112. cfg_ir.FlowInstruction.__init__(self)
  113. self.loop = loop
  114. def get_dependencies(self):
  115. """Gets all definitions and instructions on which this instruction depends."""
  116. return []
  117. def branches(self):
  118. """Gets a list of basic blocks targeted by this flow instruction."""
  119. return []
  120. def __str__(self):
  121. return 'break'
  122. def solipsize(graph_component, loop, entry_blocks, next_blocks):
  123. """Replaces branches to entry blocks and next blocks by jumps to 'continue' and 'break'
  124. blocks, respectively."""
  125. all_blocks = set()
  126. reachable_from_inner = set()
  127. for block in graph_component.blocks:
  128. if block in next_blocks:
  129. continue
  130. all_blocks.add(block)
  131. for branch in block.flow.branches():
  132. if branch.block in entry_blocks:
  133. # Create a 'continue' block, and point to that.
  134. continue_block = cfg_ir.BasicBlock(block.counter)
  135. for param in branch.block.parameters:
  136. continue_block.append_parameter(param)
  137. continue_block.flow = ContinueFlow(loop)
  138. branch.block = continue_block
  139. all_blocks.add(continue_block)
  140. elif branch.block in next_blocks:
  141. # Create a 'break' block, and point to that.
  142. break_block = cfg_ir.BasicBlock(block.counter)
  143. for param in branch.block.parameters:
  144. break_block.append_parameter(param)
  145. break_block.flow = BreakFlow(loop)
  146. branch.block = break_block
  147. all_blocks.add(break_block)
  148. reachable_from_inner.add(branch.block)
  149. return reachable_from_inner, FlowGraphComponent(
  150. graph_component.entry_blocks,
  151. all_blocks,
  152. {
  153. block : cfg_optimization.get_reachable_blocks(block)
  154. for block in all_blocks
  155. })
  156. def to_relooper_loop(graph_component):
  157. """Converts the given graph component to a relooper 'loop'."""
  158. entry_blocks = graph_component.entry_blocks
  159. result = LoopBlock(None, None)
  160. inner_blocks = []
  161. next_blocks = []
  162. for block in graph_component.blocks:
  163. if any([graph_component.can_reach(block, ep) for ep in entry_blocks]):
  164. inner_blocks.append(block)
  165. else:
  166. next_blocks.append(block)
  167. reachable_from_inner, inner_component = solipsize(
  168. graph_component, result, entry_blocks, next_blocks)
  169. result.inner = reloop(inner_component)
  170. next_component = FlowGraphComponent(
  171. reachable_from_inner, next_blocks, graph_component.reachable)
  172. result.next_block = reloop(next_component)
  173. return result
  174. def to_relooper_multiple_or_loop(graph_component):
  175. """Converts the given graph component to a relooper 'multiple' or 'loop'."""
  176. # From the Emscripten paper:
  177. #
  178. # If we have more than one entry, try to create a Multiple block:
  179. # For each entry, find all the labels it reaches that
  180. # cannot be reached by any other entry. If at least one entry
  181. # has such labels, return a Multiple block, whose Handled
  182. # blocks are blocks for those labels (and whose entries are
  183. # those labels), and whose Next block is all the rest. Entries
  184. # for the next block are entries that did not become part of
  185. # the Handled blocks, and also labels that can be reached
  186. # from the Handled blocks.
  187. entry_blocks = graph_component.entry_blocks
  188. if len(entry_blocks) <= 1:
  189. return to_relooper_loop(graph_component)
  190. entry_reachables = {ep : graph_component.get_reachable_blocks(ep) for ep in entry_blocks}
  191. exclusive_entries = {}
  192. for entry in entry_blocks:
  193. exclusive_blocks = set(entry_reachables[entry])
  194. for other_entry in entry_blocks:
  195. if other_entry != entry:
  196. exclusive_blocks.difference_update(entry_reachables[other_entry])
  197. if len(exclusive_blocks) > 0:
  198. exclusive_entries[entry] = exclusive_blocks
  199. if len(exclusive_entries) == 0:
  200. return to_relooper_loop(graph_component)
  201. next_entries = set(graph_component.entry_blocks)
  202. for block_set in exclusive_entries.values():
  203. for elem in block_set:
  204. directly_reachable = graph_component.get_directly_reachable_blocks(elem)
  205. directly_reachable.remove(elem)
  206. next_entries.update(directly_reachable)
  207. next_entries.difference_update(exclusive_entries.keys())
  208. result = MultipleLoopBlock({}, None)
  209. for entry, exclusive_blocks in exclusive_entries.items():
  210. other_blocks = set(graph_component.blocks)
  211. other_blocks.difference_update(exclusive_blocks)
  212. result.handled_blocks[entry] = reloop(
  213. solipsize(graph_component, result, set([entry]), other_blocks))
  214. result.next_block = reloop(graph_component.sub_component(next_entries))
  215. return result
  216. def reloop(graph_component):
  217. """Applies the relooper algorithm to the given graph component."""
  218. entry_blocks = graph_component.entry_blocks
  219. if len(entry_blocks) == 0:
  220. return EmptyBlock()
  221. reachable_set = graph_component.get_entry_reachable_blocks()
  222. if len(entry_blocks) == 1 and entry_blocks[0] not in reachable_set:
  223. graph_component.blocks.remove(entry_blocks[0])
  224. return SimpleBlock(
  225. entry_blocks[0],
  226. reloop(
  227. FlowGraphComponent(
  228. graph_component.get_directly_reachable_blocks(entry_blocks[0]),
  229. graph_component.blocks,
  230. graph_component.reachable)))
  231. elif all([block in reachable_set for block in entry_blocks]):
  232. return to_relooper_loop(graph_component)
  233. else:
  234. return to_relooper_multiple_or_loop(graph_component)
  235. def reloop_trivial(graph_component):
  236. """Converts the given control-flow graph to a 'multiple' block that contains only 'simple'
  237. blocks."""
  238. return MultipleLoopBlock(
  239. [(block, SimpleBlock(block, EmptyBlock())) for block in graph_component.blocks],
  240. EmptyBlock())
  241. def reloop_function_body(entry_point):
  242. """Reloops the control-flow graph defined by the given entry point."""
  243. return reloop_trivial(create_graph_component(entry_point))
  244. def find_inlinable_definitions(entry_point):
  245. """Computes a set of definitions which are eligible for inlining, i.e., they
  246. are used only once and are consumed in the same basic block in which they
  247. are defined."""
  248. all_blocks = list(cfg_optimization.get_all_blocks(entry_point))
  249. # Find all definition users for each definition.
  250. def_users = defaultdict(set)
  251. def_blocks = {}
  252. for block in all_blocks:
  253. for parameter_def in block.parameters:
  254. def_blocks[parameter_def] = block
  255. for definition in block.definitions + [block.flow]:
  256. def_blocks[definition] = block
  257. for dependency in definition.get_all_dependencies():
  258. if not isinstance(dependency, cfg_ir.Branch):
  259. def_users[dependency].add(definition)
  260. # Find all definitions which are eligible for inlining.
  261. eligible_defs = set()
  262. for definition, users in def_users.items():
  263. if len(users) == 1:
  264. single_user = next(iter(users))
  265. if def_blocks[single_user] == def_blocks[definition]:
  266. eligible_defs.add(definition)
  267. return eligible_defs
  268. class DefinitionScheduler(object):
  269. """Schedules definitions within a basic block."""
  270. # We now have the opportunity to schedule definitions in a somewhat intelligent way.
  271. # We ought to make sure that we don't reorder operations in an observable way, though.
  272. # Specifically:
  273. #
  274. # We are allowed to reorder operations which have no side-effects,
  275. # as long as they do not depend on each other. So this is fine:
  276. #
  277. # $a = load $x
  278. # $b = load $y
  279. # $c = call-indirect 'jit' f($b, $a)
  280. #
  281. # ==>
  282. #
  283. # $c = call-indirect 'jit' f(load $y, load $x)
  284. #
  285. # But we are not allowed to reorder operations which do have side-effects.
  286. # This is _not_ okay:
  287. #
  288. # $a = load $x
  289. # $b = call-indirect 'jit' g()
  290. # $c = store $x, $a
  291. #
  292. # ==>
  293. #
  294. # $b = call-indirect 'jit' g()
  295. # $c = store $x, load $x
  296. #
  297. # We can combine the concepts of depending on the results of other instructions
  298. # and depending on the potential side-effects of instructions by extending the notion
  299. # of what a dependency is: every instruction depends on its explicit dependencies,
  300. # and has an implicit dependency on all effectful instructions that precede it.
  301. # Additionally, every instruction with side-effects also depends on every instruction
  302. # that precedes it, regardless of whether those instructions have side-effects or not.
  303. #
  304. # The advantage of this way of looking at things is that we can now construct a dependency
  305. # graph. For example, this is the dependency graph for the second example.
  306. #
  307. # $c = store $x, $a
  308. # / \
  309. # / \
  310. # v v
  311. # $a = load $x <------------- $b = call-indirect 'jit' g()
  312. #
  313. # Any topological sort of the dependency graph is a valid instruction scheduling, but we
  314. # specifically want to grow a tree that uses few temporaries.
  315. #
  316. # We can accomplish this by growing the tree in reverse: we pick a definition on which no other
  317. # definition depends, and remove it from the dependency graph. We then iterate over the
  318. # definition's dependencies in reverse. If a dependency is encountered that is eligible for
  319. # inlining, i.e., it is used only once and is defined in the basic block where it is used,
  320. # then we really want to schedule it inline -- doing so allows us to avoid defining a temporary.
  321. # Here's the algorithm that we'll use to schedule dependencies.
  322. #
  323. # while (dependency has not been scheduled) and (another definition depends on the dependency):
  324. # pick a definition that depends on the dependency and schedule it
  325. # store the scheduled definition's value in a temporary
  326. #
  327. # if (dependency has not been scheduled) and (dependency is eligible for inlining):
  328. # schedule the dependency inline
  329. # else if (dependency has not been scheduled):
  330. # schedule the dependency, and store it in a temporary
  331. # else:
  332. # load the (already scheduled) dependency's value from a temporary
  333. #
  334. # Note that it is possible for another definition to also depend on a dependency, despite having
  335. # the dependency used only once. This merely means that at least one dependency is based on an
  336. # instruction's side-effects.
  337. #
  338. # Okay, so that's the theory. In this class, we will use the following data structure to
  339. # improve performance:
  340. #
  341. # * We will implement our graph as a map of definitions to a
  342. # (outgoing edges, incoming edges) tuple. This will allow us to quickly test if a
  343. # definition is a dependency of some other definition, and will also allow us to
  344. # erase definitions from the graph efficiently.
  345. #
  346. # * We will not create implicit (side-effect--based) dependencies beyond the last
  347. # definition with side-effects. Said definition already depends on every definition
  348. # that precedes it, so those edges are simply redundant.
  349. #
  350. def __init__(self, lowering_state, definitions, flow):
  351. self.lowering_state = lowering_state
  352. self.dependency_graph = {}
  353. self.construct_dependency_graph(definitions + [flow])
  354. def add_dependency(self, definition, dependency):
  355. """Makes the given definition dependent on the given dependency in the
  356. dependency graph."""
  357. def_outgoing_edges, _ = self.dependency_graph[definition]
  358. _, dep_incoming_edges = self.dependency_graph[dependency]
  359. def_outgoing_edges.add(dependency)
  360. dep_incoming_edges.add(definition)
  361. def construct_dependency_graph(self, definitions):
  362. """Construct the dependency graph for the given set of definitions."""
  363. def_set = set(definitions)
  364. # Initialize the dependency graph for every definition in the basic block.
  365. for definition in definitions:
  366. self.dependency_graph[definition] = (set(), set())
  367. # Construct the dependency graph.
  368. last_def_batch = []
  369. last_effectful_def = None
  370. for definition in definitions:
  371. # Explicit dependencies.
  372. for dep in definition.get_all_dependencies():
  373. if dep in def_set:
  374. self.add_dependency(definition, dep)
  375. # Implicit dependency on the previous definition with side-effects.
  376. if last_effectful_def is not None:
  377. self.add_dependency(definition, last_effectful_def)
  378. # Implicit dependency of definitions with side-effects on all definitions
  379. # that precede them. Implementation detail: we don't actually make
  380. # definitions dependent on _all_ definitions that precede them. It suffices
  381. # to insert a dependency on every definition between the current definition
  382. # and the previous definition with side-effects.
  383. if definition.has_side_effects():
  384. for implicit_dependency in last_def_batch:
  385. self.add_dependency(definition, implicit_dependency)
  386. last_def_batch = []
  387. last_effectful_def = definition
  388. else:
  389. last_def_batch.append(definition)
  390. def remove_definition(self, definition):
  391. """Removes the given definition from the graph."""
  392. assert not self.has_dependents(definition)
  393. # Remove the definition from the graph.
  394. outgoing_edges, _ = self.dependency_graph[definition]
  395. del self.dependency_graph[definition]
  396. # Remove the definition's outgoing edges from the graph.
  397. for dependency in outgoing_edges:
  398. _, incoming_edges = self.dependency_graph[dependency]
  399. incoming_edges.remove(definition)
  400. def has_scheduled(self, definition):
  401. """Tests if the given definition has already been scheduled."""
  402. return definition not in self.dependency_graph
  403. def get_schedulable_definition(self):
  404. """Finds a schedulable definition. Returns None if the dependency graph is empty."""
  405. if len(self.dependency_graph) == 0:
  406. return None
  407. for node in self.dependency_graph.keys():
  408. if not self.has_dependents(node):
  409. return node
  410. raise ValueError(
  411. 'Could not find an instruction to schedule. Dependency graph: %s' %
  412. self.dependency_graph)
  413. def has_dependents(self, definition):
  414. """Tests if there is at least one definition in the dependency graph that
  415. depends on the given definition."""
  416. return len(self.get_dependents(definition)) > 0
  417. def get_dependents(self, definition):
  418. """Gets the set of definitions that depend on the given definition."""
  419. _, incoming_edges = self.dependency_graph[definition]
  420. return incoming_edges
  421. def use(self, definition):
  422. """Creates a tree that produces the given definition's value."""
  423. def_value = cfg_ir.get_def_value(definition)
  424. if isinstance(def_value, LoweringState.inline_value_types):
  425. return self.lowering_state.lower_value(def_value)
  426. elif isinstance(def_value, cfg_ir.AllocateRootNode):
  427. return tree_ir.LoadLocalInstruction(
  428. self.lowering_state.get_root_node_name(def_value))
  429. elif not self.has_scheduled(definition):
  430. return self.schedule(definition)
  431. elif definition.has_value():
  432. return self.lowering_state.create_definition_load(definition)
  433. else:
  434. return tree_ir.EmptyInstruction()
  435. def __schedule_definition(self, definition, store_and_forget=False):
  436. """Schedules the given definition, excluding definitions that are dependent on it.
  437. A list of trees is returned."""
  438. statements = []
  439. if not self.has_scheduled(definition):
  440. self.remove_definition(definition)
  441. if isinstance(definition, cfg_ir.FlowInstruction):
  442. statements.append(self.lowering_state.lower_value(definition))
  443. else:
  444. # We're sure that we're dealing with a bona fide cfg_ir.Definition now.
  445. definition_value = definition.value
  446. if cfg_ir.is_value_def(definition_value, LoweringState.inline_value_types):
  447. pass
  448. elif isinstance(definition_value, cfg_ir.Definition):
  449. value_use = self.use(definition_value)
  450. if definition_value.has_value():
  451. if store_and_forget:
  452. def_load = self.lowering_state.create_definition_load(definition)
  453. statements.append(
  454. tree_ir.IgnoreInstruction(def_load.create_store(value_use)))
  455. else:
  456. statements.append(value_use)
  457. elif (not store_and_forget
  458. and definition in self.lowering_state.inlinable_definitions):
  459. statements.append(self.lowering_state.lower_value(definition_value))
  460. else:
  461. lowered_value = self.lowering_state.lower_value(definition_value)
  462. if definition.has_value():
  463. def_load = self.lowering_state.create_definition_load(definition)
  464. statements.append(
  465. tree_ir.IgnoreInstruction(def_load.create_store(lowered_value)))
  466. if not store_and_forget:
  467. statements.append(def_load)
  468. else:
  469. statements.append(lowered_value)
  470. elif (not store_and_forget
  471. and definition.has_value()
  472. and not cfg_ir.is_value_def(definition, LoweringState.inline_value_types)):
  473. statements.append(self.lowering_state.create_definition_load(definition))
  474. return statements
  475. def schedule(self, definition, store_and_forget=False):
  476. """Schedules the given definition. The resulting tree is returned."""
  477. assert not self.has_scheduled(definition)
  478. statements = []
  479. dependents = self.get_dependents(definition)
  480. while not self.has_scheduled(definition) and len(dependents) > 0:
  481. dependent = next(iter(dependents))
  482. dependent_tree = self.schedule(dependent, True)
  483. statements.append(dependent_tree)
  484. statements.reverse()
  485. statements = self.__schedule_definition(definition, store_and_forget) + statements
  486. result = tree_ir.create_block(*statements)
  487. return result
  488. class LoweringState(object):
  489. """Stores information related to the relooper->tree conversion."""
  490. def __init__(self, jit, inlinable_definitions):
  491. self.jit = jit
  492. self.label_variable = tree_ir.VariableName('__label')
  493. self.definition_loads = {}
  494. self.local_name_map = bytecode_to_tree.LocalNameMap()
  495. self.root_edge_names = {}
  496. self.inlinable_definitions = inlinable_definitions
  497. self.scheduler = None
  498. def __get_root_edge_name(self, root_node):
  499. """Gets the name of the given root edge's variable."""
  500. return self.get_root_node_name(root_node) + '_edge'
  501. def get_root_node_name(self, root_node):
  502. """Gets the name of the given root node's variable."""
  503. if isinstance(root_node, cfg_ir.Definition):
  504. return self.get_root_node_name(root_node.value)
  505. if root_node in self.root_edge_names:
  506. return self.root_edge_names[root_node]
  507. result = 'jit_locals%d' % len(self.root_edge_names)
  508. self.root_edge_names[root_node] = result
  509. return result
  510. def create_definition_load(self, definition):
  511. """Loads the given definition's variable."""
  512. if definition in self.definition_loads:
  513. return self.definition_loads[definition]
  514. result = tree_ir.LoadLocalInstruction(None)
  515. self.definition_loads[definition] = result
  516. return result
  517. def use_definition(self, definition):
  518. """Loads the given definition's value."""
  519. return self.scheduler.use(definition)
  520. def lower_block(self, block):
  521. """Lowers the given (relooped) block to a tree."""
  522. statements = []
  523. self.scheduler = DefinitionScheduler(self, block.definitions, block.flow)
  524. while 1:
  525. schedulable_def = self.scheduler.get_schedulable_definition()
  526. if schedulable_def is None:
  527. break
  528. statements.append(self.scheduler.schedule(schedulable_def))
  529. self.scheduler = None
  530. statements.reverse()
  531. return tree_ir.create_block(*statements)
  532. def lower_value(self, value):
  533. """Lowers the given instruction to a tree."""
  534. value_type = type(value)
  535. if value_type in LoweringState.instruction_lowerings:
  536. return LoweringState.instruction_lowerings[value_type](self, value)
  537. else:
  538. raise jit_runtime.JitCompilationFailedException(
  539. "Unknown CFG instruction: '%s'" % value)
  540. def lower_literal(self, value):
  541. """Lowers the given literal value."""
  542. return tree_ir.LiteralInstruction(value.literal)
  543. def lower_check_local_exists(self, value):
  544. """Lowers a 'check-value-exists' value."""
  545. return tree_ir.LocalExistsInstruction(
  546. self.local_name_map.get_local_name(value.variable.node_id))
  547. def lower_declare_local(self, value):
  548. """Lowers a 'declare-local' value."""
  549. local_name = self.local_name_map.get_local_name(value.variable.node_id)
  550. return tree_ir.create_block(
  551. tree_ir.create_new_local_node(
  552. local_name,
  553. self.use_definition(value.root_node)),
  554. tree_ir.LoadLocalInstruction(local_name))
  555. def lower_resolve_local(self, value):
  556. """Lowers a 'resolve-local' value."""
  557. return tree_ir.LoadLocalInstruction(
  558. self.local_name_map.get_local_name(value.variable.node_id))
  559. def lower_declare_global(self, value):
  560. """Lowers a 'declare-global' value."""
  561. #
  562. # global_var, = yield [("CN", [])]
  563. # _globals, = yield [("RD", [task_root, "globals"])]
  564. # yield [("CD", [_globals, var_name, global_var])]
  565. #
  566. global_var = tree_ir.StoreLocalInstruction(None, tree_ir.CreateNodeInstruction())
  567. return tree_ir.create_block(
  568. global_var.create_store(
  569. tree_ir.CreateNodeInstruction()),
  570. tree_ir.CreateDictionaryEdgeInstruction(
  571. tree_ir.ReadDictionaryValueInstruction(
  572. bytecode_to_tree.load_task_root(),
  573. tree_ir.LiteralInstruction('globals')),
  574. tree_ir.LiteralInstruction(
  575. value.variable.name),
  576. global_var.create_load()),
  577. global_var.create_load())
  578. def lower_resolve_global(self, value):
  579. """Lowers a 'resolve-global' value."""
  580. #
  581. # _globals, = yield [("RD", [task_root, "globals"])]
  582. # global_var, = yield [("RD", [_globals, var_name])]
  583. #
  584. return tree_ir.ReadDictionaryValueInstruction(
  585. tree_ir.ReadDictionaryValueInstruction(
  586. bytecode_to_tree.load_task_root(),
  587. tree_ir.LiteralInstruction('globals')),
  588. tree_ir.LiteralInstruction(value.variable.name))
  589. def lower_function_parameter(self, value):
  590. """Lowers a 'function-parameter' value."""
  591. return tree_ir.LoadLocalInstruction(value.name)
  592. def lower_alloc_root_node(self, value):
  593. """Lowers an 'alloc-root-node' value."""
  594. local_name = tree_ir.VariableName(self.get_root_node_name(value))
  595. return tree_ir.create_block(
  596. tree_ir.create_new_local_node(
  597. local_name,
  598. tree_ir.LoadIndexInstruction(
  599. tree_ir.LoadLocalInstruction(jit_runtime.KWARGS_PARAMETER_NAME),
  600. tree_ir.LiteralInstruction('task_root')),
  601. self.__get_root_edge_name(value)),
  602. tree_ir.LoadLocalInstruction(local_name))
  603. def lower_free_root_node(self, value):
  604. """Lowers a 'free-root-node' value."""
  605. return tree_ir.DeleteEdgeInstruction(
  606. tree_ir.LoadLocalInstruction(self.__get_root_edge_name(value.root_node)))
  607. def lower_load_pointer(self, value):
  608. """Lowers a 'load' value."""
  609. return bytecode_to_tree.create_access(self.use_definition(value.pointer))
  610. def lower_store_pointer(self, value):
  611. """Lowers a 'store' value."""
  612. ptr, val = self.use_definition(value.pointer), self.use_definition(value.value)
  613. return bytecode_to_tree.create_assign(ptr, val)
  614. def lower_read(self, value):
  615. """Lowers a 'read' value."""
  616. return tree_ir.ReadValueInstruction(
  617. self.use_definition(value.node))
  618. def lower_create_node(self, value):
  619. """Lowers a 'create-node' value."""
  620. if value.value.has_value():
  621. return tree_ir.CreateNodeWithValueInstruction(
  622. self.use_definition(value.value))
  623. else:
  624. return tree_ir.CreateNodeInstruction()
  625. def lower_binary(self, value):
  626. """Lowers a 'binary' value."""
  627. lhs, rhs = self.use_definition(value.lhs), self.use_definition(value.rhs)
  628. return tree_ir.BinaryInstruction(lhs, value.operator, rhs)
  629. def lower_input(self, _):
  630. """Lowers an 'input' value."""
  631. return bytecode_to_tree.create_input(self.jit.use_input_function)
  632. def lower_output(self, value):
  633. """Lowers an 'output' value."""
  634. return bytecode_to_tree.create_output(self.use_definition(value.value))
  635. def lower_direct_call(self, value):
  636. """Lowers a direct function call."""
  637. calling_convention = value.calling_convention
  638. if calling_convention in LoweringState.call_lowerings:
  639. return LoweringState.call_lowerings[calling_convention](self, value)
  640. else:
  641. raise jit_runtime.JitCompilationFailedException(
  642. "Unknown calling convention: '%s' in instruction '%s'" %
  643. (calling_convention, value))
  644. def lower_indirect_call(self, value):
  645. """Lowers an indirect function call."""
  646. target = self.use_definition(value.target)
  647. args = [(name, self.use_definition(arg))
  648. for name, arg in value.argument_list]
  649. return bytecode_to_tree.create_indirect_call(target, args)
  650. def lower_simple_positional_call(self, value):
  651. """Lowers a direct call that uses the 'simple-positional' calling convention."""
  652. return tree_ir.CallInstruction(
  653. tree_ir.LoadGlobalInstruction(value.target_name),
  654. [self.use_definition(arg) for _, arg in value.argument_list])
  655. def lower_jit_call(self, value):
  656. """Lowers a direct call that uses the 'jit' calling convention."""
  657. arg_list = [(name, self.use_definition(arg))
  658. for name, arg in value.argument_list]
  659. intrinsic = self.jit.get_intrinsic(value.target_name)
  660. if intrinsic is not None:
  661. return bytecode_to_tree.apply_intrinsic(intrinsic, arg_list)
  662. else:
  663. return tree_ir.create_jit_call(
  664. tree_ir.LoadGlobalInstruction(value.target_name),
  665. arg_list,
  666. tree_ir.LoadLocalInstruction(jit_runtime.KWARGS_PARAMETER_NAME))
  667. def lower_jump(self, flow):
  668. """Lowers the given 'jump' flow instruction to a tree."""
  669. return self.lower_branch(flow.branch)
  670. def lower_select(self, flow):
  671. """Lowers the given 'select' flow instruction to a tree."""
  672. return tree_ir.SelectInstruction(
  673. self.use_definition(flow.condition),
  674. self.lower_branch(flow.if_branch),
  675. self.lower_branch(flow.else_branch))
  676. def lower_return(self, flow):
  677. """Lowers the given 'return' flow instruction to a tree."""
  678. return tree_ir.ReturnInstruction(self.use_definition(flow.value))
  679. def lower_throw(self, flow):
  680. """Lowers the given 'throw' flow instruction to a tree."""
  681. return tree_ir.RaiseInstruction(self.use_definition(flow.exception))
  682. def lower_unreachable(self, _):
  683. """Lowers the given 'unreachable' flow instruction to a tree."""
  684. return tree_ir.EmptyInstruction()
  685. def lower_break(self, _):
  686. """Lowers the given 'break' flow instruction to a tree."""
  687. return tree_ir.BreakInstruction()
  688. def lower_continue(self, _):
  689. """Lowers the given 'continue' flow instruction to a tree."""
  690. return tree_ir.ContinueInstruction()
  691. def lower_branch(self, branch):
  692. """Lowers the given (relooped) branch to a tree."""
  693. instructions = []
  694. for param, arg in zip(branch.block.parameters, branch.arguments):
  695. instructions.append(
  696. tree_ir.IgnoreInstruction(
  697. self.create_definition_load(param).create_store(self.use_definition(arg))))
  698. instructions.append(
  699. tree_ir.IgnoreInstruction(
  700. tree_ir.StoreLocalInstruction(
  701. self.label_variable,
  702. tree_ir.LiteralInstruction(branch.block.index))))
  703. return tree_ir.create_block(*instructions)
  704. inline_value_types = (cfg_ir.Literal, cfg_ir.ResolveLocal, cfg_ir.FunctionParameter)
  705. instruction_lowerings = {
  706. cfg_ir.Literal : lower_literal,
  707. cfg_ir.CheckLocalExists : lower_check_local_exists,
  708. cfg_ir.DeclareLocal : lower_declare_local,
  709. cfg_ir.ResolveLocal : lower_resolve_local,
  710. cfg_ir.DeclareGlobal : lower_declare_global,
  711. cfg_ir.ResolveGlobal : lower_resolve_global,
  712. cfg_ir.FunctionParameter : lower_function_parameter,
  713. cfg_ir.AllocateRootNode : lower_alloc_root_node,
  714. cfg_ir.DeallocateRootNode : lower_free_root_node,
  715. cfg_ir.LoadPointer : lower_load_pointer,
  716. cfg_ir.StoreAtPointer : lower_store_pointer,
  717. cfg_ir.Read : lower_read,
  718. cfg_ir.CreateNode : lower_create_node,
  719. cfg_ir.Binary : lower_binary,
  720. cfg_ir.Input : lower_input,
  721. cfg_ir.Output : lower_output,
  722. cfg_ir.DirectFunctionCall : lower_direct_call,
  723. cfg_ir.IndirectFunctionCall : lower_indirect_call,
  724. cfg_ir.JumpFlow : lower_jump,
  725. cfg_ir.SelectFlow : lower_select,
  726. cfg_ir.ReturnFlow : lower_return,
  727. cfg_ir.ThrowFlow : lower_throw,
  728. cfg_ir.UnreachableFlow : lower_unreachable,
  729. BreakFlow : lower_break,
  730. ContinueFlow : lower_continue
  731. }
  732. call_lowerings = {
  733. cfg_ir.SIMPLE_POSITIONAL_CALLING_CONVENTION : lower_simple_positional_call,
  734. cfg_ir.JIT_CALLING_CONVENTION : lower_jit_call
  735. }
  736. def lower_flow_graph(entry_point, jit):
  737. """Lowers the control-flow graph defined by the given entry point to tree IR."""
  738. cfg_lowerer = LoweringState(jit, find_inlinable_definitions(entry_point))
  739. lowered_body = reloop_function_body(entry_point).lower(cfg_lowerer)
  740. lowered_body = tree_ir.CompoundInstruction(
  741. cfg_lowerer.lower_jump(cfg_ir.create_jump(entry_point)), lowered_body)
  742. return tree_ir.map_and_simplify(lambda x: x, lowered_body)