cfg_ir.py 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668
  1. """Defines control flow graph IR data structures."""
  2. # Let's just agree to disagree on map vs list comprehensions, pylint.
  3. # pylint: disable=I0011,W0141
  4. class SharedCounter(object):
  5. """Defines a shared counter."""
  6. def __init__(self):
  7. self.index = 0
  8. def next_value(self):
  9. """Gets the next value for this counter."""
  10. result = self.index
  11. self.index += 1
  12. return result
  13. class BasicBlock(object):
  14. """Represents a basic block."""
  15. def __init__(self, counter):
  16. self.parameters = []
  17. self.definitions = []
  18. self.counter = counter
  19. self.index = counter.next_value()
  20. self.definition_counter = SharedCounter()
  21. self.flow = UnreachableFlow()
  22. def append_parameter(self, parameter):
  23. """Appends a parameter to this basic block."""
  24. result = self.create_definition(parameter)
  25. self.parameters.append(result)
  26. if len(self.definitions) > 0:
  27. self.renumber_definitions()
  28. return result
  29. def remove_parameter(self, parameter):
  30. """Removes the given parameter definition from this basic block."""
  31. return self.parameters.remove(parameter)
  32. def prepend_definition(self, value):
  33. """Defines the given value in this basic block."""
  34. result = self.create_definition(value)
  35. self.definitions.insert(0, result)
  36. self.renumber_definitions()
  37. return result
  38. def insert_definition_before(self, anchor, value):
  39. """Inserts the second definition or value before the first definition."""
  40. index = None
  41. for i, definition in enumerate(self.definitions):
  42. if definition.definition_index == anchor.definition_index:
  43. index = i
  44. if index is None:
  45. raise ValueError(
  46. 'Cannot insert a definition because the anchor '
  47. 'is not defined in this block.')
  48. result = self.create_definition(value)
  49. self.definitions.insert(index, result)
  50. self.renumber_definitions()
  51. return result
  52. def append_definition(self, value):
  53. """Defines the given value in this basic block."""
  54. result = self.create_definition(value)
  55. self.definitions.append(result)
  56. return result
  57. def create_definition(self, value=None):
  58. """Creates a definition, but does not assign it to this block yet."""
  59. if isinstance(value, Definition):
  60. value.block = self
  61. value.renumber(self.definition_counter.next_value())
  62. return value
  63. else:
  64. assert isinstance(value, Value) or value is None
  65. return Definition(
  66. self.counter.next_value(),
  67. self,
  68. self.definition_counter.next_value(),
  69. value)
  70. def remove_definition(self, definition):
  71. """Removes the given definition from this basic block."""
  72. return self.definitions.remove(definition)
  73. def renumber_definitions(self):
  74. """Re-numbers all definitions in this basic block."""
  75. self.definition_counter = SharedCounter()
  76. for definition in self.parameters:
  77. definition.renumber(self.definition_counter.next_value())
  78. for definition in self.definitions:
  79. definition.renumber(self.definition_counter.next_value())
  80. def __str__(self):
  81. prefix = '!%d(%s):' % (self.index, ', '.join(map(str, self.parameters)))
  82. return '\n'.join(
  83. [prefix] +
  84. [' ' * 4 + str(item) for item in self.definitions + [self.flow]])
  85. class Definition(object):
  86. """Maps a value to a variable."""
  87. def __init__(self, index, block, definition_index, value):
  88. self.index = index
  89. self.block = block
  90. self.definition_index = definition_index
  91. self.value = value
  92. if value is not None:
  93. assert isinstance(value, Value) or isinstance(value, Definition)
  94. def redefine(self, new_value):
  95. """Tweaks this definition to take on the given new value."""
  96. self.value = new_value
  97. if new_value is not None:
  98. assert isinstance(new_value, Value) or isinstance(new_value, Definition)
  99. def renumber(self, new_definition_index):
  100. """Updates this definition's index in the block that defines it."""
  101. self.definition_index = new_definition_index
  102. def get_all_dependencies(self):
  103. """Gets all definitions and instructions on which this definition depends,
  104. along with any dependencies of instruction dependencies."""
  105. if isinstance(self.value, Definition):
  106. return [self.value]
  107. else:
  108. return self.value.get_all_dependencies()
  109. def has_side_effects(self):
  110. """Tests if this definition produces any side-effects."""
  111. return self.value.has_side_effects()
  112. def has_value(self):
  113. """Tells if this definition produces a result that is not None."""
  114. return self.value.has_value()
  115. def insert_before(self, value):
  116. """Inserts the given value or definition before this definition."""
  117. return self.block.insert_definition_before(self, value)
  118. def ref_str(self):
  119. """Gets a string that represents a reference to this definition."""
  120. return '$%d' % self.index
  121. def __str__(self):
  122. return '$%d = %s' % (self.index, self.value.ref_str())
  123. class Instruction(object):
  124. """Represents an instruction."""
  125. def get_dependencies(self):
  126. """Gets all definitions and instructions on which this instruction depends."""
  127. raise NotImplementedError()
  128. def get_all_dependencies(self):
  129. """Gets all definitions and instructions on which this instruction depends,
  130. along with any dependencies of instruction dependencies."""
  131. results = list(self.get_dependencies())
  132. for item in results:
  133. if not isinstance(item, Definition):
  134. results.extend(item.get_all_dependencies())
  135. return results
  136. class Branch(Instruction):
  137. """Represents a branch from one basic block to another."""
  138. def __init__(self, block, arguments=None):
  139. self.block = block
  140. assert isinstance(block, BasicBlock)
  141. if arguments is None:
  142. arguments = []
  143. self.arguments = arguments
  144. assert all([isinstance(arg, Definition) for arg in arguments])
  145. def get_dependencies(self):
  146. """Gets all definitions and instructions on which this instruction depends."""
  147. return self.arguments
  148. def __str__(self):
  149. return '!%d(%s)' % (self.block.index, ', '.join([arg.ref_str() for arg in self.arguments]))
  150. class FlowInstruction(Instruction):
  151. """Represents a control flow instruction which terminates a basic block."""
  152. def branches(self):
  153. """Gets a list of basic blocks targeted by this flow instruction."""
  154. raise NotImplementedError()
  155. def has_side_effects(self):
  156. """Tells if this instruction has side-effects."""
  157. # All flow-instructions have side-effects!
  158. return True
  159. class JumpFlow(FlowInstruction):
  160. """Represents a control flow instruction which jumps directly to a basic block."""
  161. def __init__(self, branch):
  162. FlowInstruction.__init__(self)
  163. self.branch = branch
  164. assert isinstance(branch, Branch)
  165. def get_dependencies(self):
  166. """Gets all definitions and instructions on which this instruction depends."""
  167. return self.branches()
  168. def branches(self):
  169. """Gets a list of basic blocks targeted by this flow instruction."""
  170. return [self.branch]
  171. def __str__(self):
  172. return 'jump %s' % self.branch
  173. class SelectFlow(FlowInstruction):
  174. """Represents a control flow instruction which jumps to one of two basic blocks depending
  175. on whether a condition is truthy or not."""
  176. def __init__(self, condition, if_branch, else_branch):
  177. FlowInstruction.__init__(self)
  178. self.condition = condition
  179. assert isinstance(condition, Definition)
  180. self.if_branch = if_branch
  181. assert isinstance(if_branch, Branch)
  182. self.else_branch = else_branch
  183. assert isinstance(else_branch, Branch)
  184. def get_dependencies(self):
  185. """Gets all definitions and instructions on which this instruction depends."""
  186. return [self.condition] + self.branches()
  187. def branches(self):
  188. """Gets a list of basic blocks targeted by this flow instruction."""
  189. return [self.if_branch, self.else_branch]
  190. def __str__(self):
  191. return 'select %s, %s, %s' % (self.condition.ref_str(), self.if_branch, self.else_branch)
  192. class ReturnFlow(FlowInstruction):
  193. """Represents a control flow instruction which terminates the execution of the current
  194. function and returns a value."""
  195. def __init__(self, value):
  196. FlowInstruction.__init__(self)
  197. self.value = value
  198. assert isinstance(value, Definition)
  199. def get_dependencies(self):
  200. """Gets all definitions and instructions on which this instruction depends."""
  201. return [self.value]
  202. def branches(self):
  203. """Gets a list of basic blocks targeted by this flow instruction."""
  204. return []
  205. def __str__(self):
  206. return 'return %s' % self.value.ref_str()
  207. class ThrowFlow(FlowInstruction):
  208. """Represents a control flow instruction which throws an exception."""
  209. def __init__(self, exception):
  210. FlowInstruction.__init__(self)
  211. self.exception = exception
  212. assert isinstance(exception, Definition)
  213. def get_dependencies(self):
  214. """Gets all definitions and instructions on which this instruction depends."""
  215. return [self.exception]
  216. def branches(self):
  217. """Gets a list of basic blocks targeted by this flow instruction."""
  218. return []
  219. def __str__(self):
  220. return 'throw %s' % self.exception.ref_str()
  221. class UnreachableFlow(FlowInstruction):
  222. """Represents a control flow instruction which is unreachable."""
  223. def get_dependencies(self):
  224. """Gets all definitions and instructions on which this instruction depends."""
  225. return []
  226. def branches(self):
  227. """Gets a list of basic blocks targeted by this flow instruction."""
  228. return []
  229. def __str__(self):
  230. return 'unreachable'
  231. class Value(Instruction):
  232. """A value: an instruction that produces some result."""
  233. def get_dependencies(self):
  234. """Gets all definitions and instructions on which this instruction depends."""
  235. raise NotImplementedError()
  236. def has_value(self):
  237. """Tells if this value produces a result that is not None."""
  238. return True
  239. def has_side_effects(self):
  240. """Tells if this instruction has side-effects."""
  241. return False
  242. def ref_str(self):
  243. """Gets a string that represents this value."""
  244. return str(self)
  245. class BlockParameter(Value):
  246. """A basic block parameter."""
  247. def get_dependencies(self):
  248. """Gets all definitions and instructions on which this instruction depends."""
  249. return []
  250. def __str__(self):
  251. return 'block-parameter'
  252. class FunctionParameter(Value):
  253. """A function parameter."""
  254. def __init__(self, name):
  255. Value.__init__(self)
  256. self.name = name
  257. def get_dependencies(self):
  258. """Gets all definitions and instructions on which this instruction depends."""
  259. return []
  260. def __str__(self):
  261. return 'func-parameter %s' % self.name
  262. class Literal(Value):
  263. """A literal value."""
  264. def __init__(self, literal):
  265. Value.__init__(self)
  266. self.literal = literal
  267. def get_dependencies(self):
  268. """Gets all definitions and instructions on which this instruction depends."""
  269. return []
  270. def has_value(self):
  271. """Tells if this value produces a result that is not None."""
  272. return self.literal is not None
  273. def __str__(self):
  274. return 'literal %r' % self.literal
  275. class IndirectFunctionCall(Value):
  276. """A value that is the result of an indirect function call."""
  277. def __init__(self, target, argument_list):
  278. Value.__init__(self)
  279. assert isinstance(target, Definition)
  280. self.target = target
  281. assert all([isinstance(val, Definition) for _, val in argument_list])
  282. self.argument_list = argument_list
  283. def has_side_effects(self):
  284. """Tells if this instruction has side-effects."""
  285. return True
  286. def get_dependencies(self):
  287. """Gets all definitions and instructions on which this instruction depends."""
  288. return [self.target] + [val for _, val in self.argument_list]
  289. def __str__(self):
  290. return 'indirect-call %s(%s)' % (
  291. self.target.ref_str(),
  292. ', '.join(['%s=%s' % (key, val.ref_str()) for key, val in self.argument_list]))
  293. SIMPLE_POSITIONAL_CALLING_CONVENTION = 'simple-positional'
  294. """The calling convention for functions that use 'return' statements to return.
  295. Arguments are matched to parameters based on position."""
  296. JIT_CALLING_CONVENTION = 'jit'
  297. """The calling convention for jitted functions."""
  298. class DirectFunctionCall(Value):
  299. """A value that is the result of a direct function call."""
  300. def __init__(self, target_name, argument_list, calling_convention=JIT_CALLING_CONVENTION):
  301. Value.__init__(self)
  302. self.target_name = target_name
  303. assert all([isinstance(val, Definition) for _, val in argument_list])
  304. self.argument_list = argument_list
  305. self.calling_convention = calling_convention
  306. def has_side_effects(self):
  307. """Tells if this instruction has side-effects."""
  308. return True
  309. def get_dependencies(self):
  310. """Gets all definitions and instructions on which this instruction depends."""
  311. return [val for _, val in self.argument_list]
  312. def __str__(self):
  313. return 'direct-call %r %s(%s)' % (
  314. self.calling_convention,
  315. self.target_name,
  316. ', '.join(['%s=%s' % (key, val.ref_str()) for key, val in self.argument_list]))
  317. class AllocateRootNode(Value):
  318. """A value that produces a new root node. Typically used in function prologs."""
  319. def __init__(self):
  320. Value.__init__(self)
  321. def get_dependencies(self):
  322. """Gets all definitions and instructions on which this instruction depends."""
  323. return []
  324. def __str__(self):
  325. return 'alloc-root-node'
  326. class DeallocateRootNode(Value):
  327. """A value that deallocates a root node. Typically used in function epilogs."""
  328. def __init__(self, root_node):
  329. Value.__init__(self)
  330. assert isinstance(root_node, Definition)
  331. self.root_node = root_node
  332. def get_dependencies(self):
  333. """Gets all definitions and instructions on which this instruction depends."""
  334. return [self.root_node]
  335. def has_value(self):
  336. """Tells if this value produces a result that is not None."""
  337. return False
  338. def has_side_effects(self):
  339. """Tells if this instruction has side-effects."""
  340. return True
  341. def __str__(self):
  342. return 'free-root-node %s' % self.root_node.ref_str()
  343. class DeclareLocal(Value):
  344. """A value that declares a local variable."""
  345. def __init__(self, variable, root_node):
  346. Value.__init__(self)
  347. self.variable = variable
  348. self.root_node = root_node
  349. def get_dependencies(self):
  350. """Gets all definitions and instructions on which this instruction depends."""
  351. return [self.root_node]
  352. def has_value(self):
  353. """Tells if this value produces a result that is not None."""
  354. return False
  355. def has_side_effects(self):
  356. """Tells if this instruction has side-effects."""
  357. return True
  358. def __str__(self):
  359. return 'declare-local %s, %s' % (self.variable, self.root_node.ref_str())
  360. class DeclareGlobal(Value):
  361. """A value that declares a global variable."""
  362. def __init__(self, variable):
  363. Value.__init__(self)
  364. self.variable = variable
  365. def get_dependencies(self):
  366. """Gets all definitions and instructions on which this instruction depends."""
  367. return []
  368. def has_value(self):
  369. """Tells if this value produces a result that is not None."""
  370. return False
  371. def has_side_effects(self):
  372. """Tells if this instruction has side-effects."""
  373. return True
  374. def __str__(self):
  375. return 'declare-global %s' % self.variable.name
  376. class CheckLocalExists(Value):
  377. """A value that checks if a local value has been defined (yet)."""
  378. def __init__(self, variable):
  379. Value.__init__(self)
  380. self.variable = variable
  381. def get_dependencies(self):
  382. """Gets all definitions and instructions on which this instruction depends."""
  383. return []
  384. def __str__(self):
  385. return 'check-local-exists %s' % self.variable
  386. class ResolveLocal(Value):
  387. """A value that resolves a local as a pointer."""
  388. def __init__(self, variable):
  389. Value.__init__(self)
  390. self.variable = variable
  391. def get_dependencies(self):
  392. """Gets all definitions and instructions on which this instruction depends."""
  393. return []
  394. def __str__(self):
  395. return 'resolve-local %s' % self.variable
  396. class ResolveGlobal(Value):
  397. """A value that resolves a global as a pointer."""
  398. def __init__(self, variable):
  399. Value.__init__(self)
  400. self.variable = variable
  401. def get_dependencies(self):
  402. """Gets all definitions and instructions on which this instruction depends."""
  403. return []
  404. def __str__(self):
  405. return 'resolve-global %s' % self.variable.name
  406. class LoadPointer(Value):
  407. """A value that loads the value assigned to a pointer."""
  408. def __init__(self, pointer):
  409. Value.__init__(self)
  410. self.pointer = pointer
  411. assert isinstance(pointer, Definition)
  412. def get_dependencies(self):
  413. """Gets all definitions and instructions on which this instruction depends."""
  414. return [self.pointer]
  415. def __str__(self):
  416. return 'load %s' % self.pointer.ref_str()
  417. class StoreAtPointer(Value):
  418. """A value that assigns a value to a pointer."""
  419. def __init__(self, pointer, value):
  420. Value.__init__(self)
  421. self.pointer = pointer
  422. assert isinstance(pointer, Definition)
  423. self.value = value
  424. assert isinstance(value, Definition)
  425. def get_dependencies(self):
  426. """Gets all definitions and instructions on which this instruction depends."""
  427. return [self.pointer, self.value]
  428. def has_value(self):
  429. """Tells if this value produces a result that is not None."""
  430. return False
  431. def has_side_effects(self):
  432. """Tells if this instruction has side-effects."""
  433. return True
  434. def __str__(self):
  435. return 'store %s, %s' % (self.pointer.ref_str(), self.value.ref_str())
  436. class Read(Value):
  437. """A value that reads the value stored in a node."""
  438. def __init__(self, node):
  439. Value.__init__(self)
  440. self.node = node
  441. assert isinstance(node, Definition)
  442. def get_dependencies(self):
  443. """Gets all definitions and instructions on which this instruction depends."""
  444. return [self.node]
  445. def __str__(self):
  446. return 'read %s' % (self.node.ref_str())
  447. class CreateNode(Value):
  448. """A value that creates a new node."""
  449. def __init__(self, value):
  450. Value.__init__(self)
  451. self.value = value
  452. assert isinstance(value, Definition)
  453. def get_dependencies(self):
  454. """Gets all definitions and instructions on which this instruction depends."""
  455. return [self.value]
  456. def __str__(self):
  457. return 'create-node %s' % (self.value.ref_str())
  458. class Input(Value):
  459. """A value that pops a node from the input queue."""
  460. def get_dependencies(self):
  461. """Gets all definitions and instructions on which this instruction depends."""
  462. return []
  463. def has_side_effects(self):
  464. """Tells if this instruction has side-effects."""
  465. return True
  466. def __str__(self):
  467. return 'input'
  468. class Output(Value):
  469. """A value that pushes a node onto the output queue."""
  470. def __init__(self, value):
  471. Value.__init__(self)
  472. self.value = value
  473. assert isinstance(value, Definition)
  474. def get_dependencies(self):
  475. """Gets all definitions and instructions on which this instruction depends."""
  476. return [self.value]
  477. def has_value(self):
  478. """Tells if this value produces a result that is not None."""
  479. return False
  480. def has_side_effects(self):
  481. """Tells if this instruction has side-effects."""
  482. return True
  483. def __str__(self):
  484. return 'output %s' % self.value.ref_str()
  485. class Binary(Value):
  486. """A value that applies a binary operator to two other values."""
  487. def __init__(self, lhs, operator, rhs):
  488. Value.__init__(self)
  489. self.lhs = lhs
  490. assert isinstance(lhs, Definition)
  491. self.operator = operator
  492. self.rhs = rhs
  493. assert isinstance(rhs, Definition)
  494. def get_dependencies(self):
  495. """Gets all definitions and instructions on which this instruction depends."""
  496. return [self.lhs, self.rhs]
  497. def __str__(self):
  498. return 'binary %s, %r, %s' % (self.lhs.ref_str(), self.operator, self.rhs.ref_str())
  499. def create_jump(block, arguments=None):
  500. """Creates a jump to the given block with the given argument list."""
  501. return JumpFlow(Branch(block, arguments))
  502. def get_def_value(def_or_value):
  503. """Returns the given value, or the underlying value of the given definition, whichever is
  504. appropriate."""
  505. if isinstance(def_or_value, Definition):
  506. return get_def_value(def_or_value.value)
  507. else:
  508. return def_or_value
  509. def apply_to_value(function, def_or_value):
  510. """Applies the given function to the specified value, or the underlying value of the
  511. given definition."""
  512. return function(get_def_value(def_or_value))
  513. def is_literal(value):
  514. """Tests if the given value is a literal."""
  515. return isinstance(value, Literal)
  516. def is_literal_def(def_or_value):
  517. """Tests if the given value is a literal or a definition with an underlying literal."""
  518. return apply_to_value(is_literal, def_or_value)
  519. def is_value_def(def_or_value, class_or_type_or_tuple=Value):
  520. """Tests if the given definition or value is a value of the given type."""
  521. return isinstance(get_def_value(def_or_value), class_or_type_or_tuple)
  522. def get_def_variable(def_or_value):
  523. """Gets the 'variable' attribute of the given value, or the underlying value of the given
  524. definition, whichever is appropriate."""
  525. return get_def_value(def_or_value).variable
  526. def get_literal_value(value):
  527. """Gets the value of the given literal value."""
  528. return value.literal
  529. def get_literal_def_value(def_or_value):
  530. """Gets the value of the given literal value or definition with an underlying literal."""
  531. return apply_to_value(get_literal_value, def_or_value)