cfg_ir.py 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426
  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.flow = UnreachableFlow()
  21. def append_parameter(self, parameter):
  22. """Appends a parameter to this basic block."""
  23. result = self.create_definition(parameter)
  24. self.parameters.append(result)
  25. return result
  26. def prepend_definition(self, value):
  27. """Defines the given value in this basic block."""
  28. result = self.create_definition(value)
  29. self.definitions.insert(0, result)
  30. return result
  31. def append_definition(self, value):
  32. """Defines the given value in this basic block."""
  33. result = self.create_definition(value)
  34. self.definitions.append(result)
  35. return result
  36. def create_definition(self, value=None):
  37. """Creates a definition, but does not assign it to this block yet."""
  38. if isinstance(value, Definition):
  39. return value
  40. else:
  41. assert isinstance(value, Value) or value is None
  42. return Definition(self.counter.next_value(), value)
  43. def remove_definition(self, definition):
  44. """Removes the given definition from this basic block."""
  45. return self.definitions.remove(definition)
  46. def __str__(self):
  47. prefix = '!%d(%s):' % (self.index, ', '.join(map(str, self.parameters)))
  48. return '\n'.join(
  49. [prefix] +
  50. [' ' * 4 + str(item) for item in self.definitions + [self.flow]])
  51. class Definition(object):
  52. """Maps a value to a variable."""
  53. def __init__(self, index, value):
  54. self.index = index
  55. self.value = value
  56. if value is not None:
  57. assert isinstance(value, Value)
  58. def redefine(self, new_value):
  59. """Tweaks this definition to take on the given new value."""
  60. self.value = new_value
  61. if new_value is not None:
  62. assert isinstance(new_value, Value)
  63. def ref_str(self):
  64. """Gets a string that represents a reference to this definition."""
  65. return '$%d' % self.index
  66. def __str__(self):
  67. return '$%d = %s' % (self.index, str(self.value))
  68. class Instruction(object):
  69. """Represents an instruction."""
  70. def get_dependencies(self):
  71. """Gets all definitions and instructions on which this instruction depends."""
  72. raise NotImplementedError()
  73. def get_all_dependencies(self):
  74. """Gets all definitions and instructions on which this instruction depends,
  75. along with any dependencies of dependencies."""
  76. results = list(self.get_dependencies())
  77. for item in results:
  78. results.extend(item.get_all_dependencies())
  79. return results
  80. class Branch(Instruction):
  81. """Represents a branch from one basic block to another."""
  82. def __init__(self, block, arguments=None):
  83. self.block = block
  84. assert isinstance(block, BasicBlock)
  85. if arguments is None:
  86. arguments = []
  87. self.arguments = arguments
  88. assert all([isinstance(arg, Definition) for arg in arguments])
  89. def get_dependencies(self):
  90. """Gets all definitions and instructions on which this instruction depends."""
  91. return self.arguments
  92. def __str__(self):
  93. return '!%d(%s)' % (self.block.index, ', '.join(map(str, self.arguments)))
  94. class FlowInstruction(Instruction):
  95. """Represents a control flow instruction which terminates a basic block."""
  96. def branches(self):
  97. """Gets a list of basic blocks targeted by this flow instruction."""
  98. raise NotImplementedError()
  99. class JumpFlow(FlowInstruction):
  100. """Represents a control flow instruction which jumps directly to a basic block."""
  101. def __init__(self, branch):
  102. FlowInstruction.__init__(self)
  103. self.branch = branch
  104. assert isinstance(branch, Branch)
  105. def get_dependencies(self):
  106. """Gets all definitions and instructions on which this instruction depends."""
  107. return self.branches()
  108. def branches(self):
  109. """Gets a list of basic blocks targeted by this flow instruction."""
  110. return [self.branch]
  111. def __str__(self):
  112. return 'jump %s' % self.branch
  113. class SelectFlow(FlowInstruction):
  114. """Represents a control flow instruction which jumps to one of two basic blocks depending
  115. on whether a condition is truthy or not."""
  116. def __init__(self, condition, if_branch, else_branch):
  117. FlowInstruction.__init__(self)
  118. self.condition = condition
  119. assert isinstance(condition, Definition)
  120. self.if_branch = if_branch
  121. assert isinstance(if_branch, Branch)
  122. self.else_branch = else_branch
  123. assert isinstance(else_branch, Branch)
  124. def get_dependencies(self):
  125. """Gets all definitions and instructions on which this instruction depends."""
  126. return [self.condition] + self.branches()
  127. def branches(self):
  128. """Gets a list of basic blocks targeted by this flow instruction."""
  129. return [self.if_branch, self.else_branch]
  130. def __str__(self):
  131. return 'select %s, %s, %s' % (self.condition.ref_str(), self.if_branch, self.else_branch)
  132. class ReturnFlow(FlowInstruction):
  133. """Represents a control flow instruction which terminates the execution of the current
  134. function and returns a value."""
  135. def __init__(self, value):
  136. FlowInstruction.__init__(self)
  137. self.value = value
  138. assert isinstance(value, Value)
  139. def get_dependencies(self):
  140. """Gets all definitions and instructions on which this instruction depends."""
  141. return [self.value]
  142. def branches(self):
  143. """Gets a list of basic blocks targeted by this flow instruction."""
  144. return []
  145. def __str__(self):
  146. return 'return %s' % self.value.ref_str()
  147. class UnreachableFlow(FlowInstruction):
  148. """Represents a control flow instruction which is unreachable."""
  149. def get_dependencies(self):
  150. """Gets all definitions and instructions on which this instruction depends."""
  151. return []
  152. def branches(self):
  153. """Gets a list of basic blocks targeted by this flow instruction."""
  154. return []
  155. def __str__(self):
  156. return 'unreachable'
  157. class Value(Instruction):
  158. """A value: an instruction that produces some result."""
  159. def get_dependencies(self):
  160. """Gets all definitions and instructions on which this instruction depends."""
  161. raise NotImplementedError()
  162. def has_value(self):
  163. """Tells if this value produces a result that is not None."""
  164. return True
  165. def has_side_effects(self):
  166. """Tells if this instruction has side-effects."""
  167. return False
  168. class BlockParameter(Value):
  169. """A basic block parameter."""
  170. def get_dependencies(self):
  171. """Gets all definitions and instructions on which this instruction depends."""
  172. return []
  173. def __str__(self):
  174. return 'block-parameter'
  175. class FunctionParameter(Value):
  176. """A function parameter."""
  177. def __init__(self, name):
  178. Value.__init__(self)
  179. self.name = name
  180. def get_dependencies(self):
  181. """Gets all definitions and instructions on which this instruction depends."""
  182. return []
  183. def __str__(self):
  184. return 'func-parameter %s' % self.name
  185. class Literal(Value):
  186. """A literal value."""
  187. def __init__(self, literal):
  188. Value.__init__(self)
  189. self.literal = literal
  190. def get_dependencies(self):
  191. """Gets all definitions and instructions on which this instruction depends."""
  192. return []
  193. def has_value(self):
  194. """Tells if this value produces a result that is not None."""
  195. return self.literal is not None
  196. def __str__(self):
  197. return 'literal %r' % self.literal
  198. class JitFunctionCall(Value):
  199. """A value that is the result of a function call."""
  200. def __init__(self, target, argument_list):
  201. Value.__init__(self)
  202. assert isinstance(target, Definition)
  203. self.target = target
  204. assert all([isinstance(val, Definition) for val in argument_list])
  205. self.argument_list = argument_list
  206. def has_side_effects(self):
  207. """Tells if this instruction has side-effects."""
  208. return True
  209. def get_dependencies(self):
  210. """Gets all definitions and instructions on which this instruction depends."""
  211. return [self.target] + [val for _, val in self.argument_list]
  212. def __str__(self):
  213. return 'call %s(%s)' % (
  214. self.target.ref_str(),
  215. ', '.join(['%s=%s' % (key, val.ref_str()) for key, val in self.argument_list]))
  216. class DeclareLocal(Value):
  217. """A value that declares a local variable."""
  218. def __init__(self, variable):
  219. Value.__init__(self)
  220. self.variable = variable
  221. def get_dependencies(self):
  222. """Gets all definitions and instructions on which this instruction depends."""
  223. return []
  224. def has_value(self):
  225. """Tells if this value produces a result that is not None."""
  226. return False
  227. def has_side_effects(self):
  228. """Tells if this instruction has side-effects."""
  229. return True
  230. def __str__(self):
  231. return 'declare-local %d' % self.variable.node_id
  232. class DeclareGlobal(Value):
  233. """A value that declares a global variable."""
  234. def __init__(self, variable):
  235. Value.__init__(self)
  236. self.variable = variable
  237. def get_dependencies(self):
  238. """Gets all definitions and instructions on which this instruction depends."""
  239. return []
  240. def has_value(self):
  241. """Tells if this value produces a result that is not None."""
  242. return False
  243. def has_side_effects(self):
  244. """Tells if this instruction has side-effects."""
  245. return True
  246. def __str__(self):
  247. return 'declare-global %s' % self.variable.name
  248. class CheckLocalExists(Value):
  249. """A value that checks if a local value has been defined (yet)."""
  250. def __init__(self, variable):
  251. Value.__init__(self)
  252. self.variable = variable
  253. def get_dependencies(self):
  254. """Gets all definitions and instructions on which this instruction depends."""
  255. return []
  256. def __str__(self):
  257. return 'check-local-exists %d' % self.variable.node_id
  258. class ResolveLocal(Value):
  259. """A value that resolves a local as a pointer."""
  260. def __init__(self, variable):
  261. Value.__init__(self)
  262. self.variable = variable
  263. def get_dependencies(self):
  264. """Gets all definitions and instructions on which this instruction depends."""
  265. return []
  266. def __str__(self):
  267. return 'resolve-local %d' % self.variable.node_id
  268. class ResolveGlobal(Value):
  269. """A value that resolves a global as a pointer."""
  270. def __init__(self, variable):
  271. Value.__init__(self)
  272. self.variable = variable
  273. def get_dependencies(self):
  274. """Gets all definitions and instructions on which this instruction depends."""
  275. return []
  276. def __str__(self):
  277. return 'resolve-global %s' % self.variable.name
  278. class LoadPointer(Value):
  279. """A value that loads the value assigned to a pointer."""
  280. def __init__(self, pointer):
  281. Value.__init__(self)
  282. self.pointer = pointer
  283. assert isinstance(pointer, Definition)
  284. def get_dependencies(self):
  285. """Gets all definitions and instructions on which this instruction depends."""
  286. return [self.pointer]
  287. def __str__(self):
  288. return 'load %s' % self.pointer.ref_str()
  289. class StoreAtPointer(Value):
  290. """A value that assigns a value to a pointer."""
  291. def __init__(self, pointer, value):
  292. Value.__init__(self)
  293. self.pointer = pointer
  294. assert isinstance(pointer, Definition)
  295. self.value = value
  296. assert isinstance(value, Definition)
  297. def get_dependencies(self):
  298. """Gets all definitions and instructions on which this instruction depends."""
  299. return [self.pointer, self.value]
  300. def has_value(self):
  301. """Tells if this value produces a result that is not None."""
  302. return False
  303. def has_side_effects(self):
  304. """Tells if this instruction has side-effects."""
  305. return True
  306. def __str__(self):
  307. return 'store %s, %s' % (self.pointer.ref_str(), self.value.ref_str())
  308. class Input(Value):
  309. """A value that pops a node from the input queue."""
  310. def get_dependencies(self):
  311. """Gets all definitions and instructions on which this instruction depends."""
  312. return []
  313. def has_side_effects(self):
  314. """Tells if this instruction has side-effects."""
  315. return True
  316. def __str__(self):
  317. return 'input'
  318. class Output(Value):
  319. """A value that pushes a node onto the output queue."""
  320. def __init__(self, value):
  321. Value.__init__(self)
  322. self.value = value
  323. assert isinstance(value, Definition)
  324. def get_dependencies(self):
  325. """Gets all definitions and instructions on which this instruction depends."""
  326. return [self.value]
  327. def has_value(self):
  328. """Tells if this value produces a result that is not None."""
  329. return False
  330. def has_side_effects(self):
  331. """Tells if this instruction has side-effects."""
  332. return True
  333. def __str__(self):
  334. return 'output %s' % self.value.ref_str()
  335. def create_jump(block, arguments=None):
  336. """Creates a jump to the given block with the given argument list."""
  337. return JumpFlow(Branch(block, arguments))