cfg_to_tree.py 38 KB

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