cfg_ir.py 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542
  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([arg.ref_str() for arg in 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, Definition)
  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 ThrowFlow(FlowInstruction):
  148. """Represents a control flow instruction which throws an exception."""
  149. def __init__(self, exception):
  150. FlowInstruction.__init__(self)
  151. self.exception = exception
  152. assert isinstance(exception, Definition)
  153. def get_dependencies(self):
  154. """Gets all definitions and instructions on which this instruction depends."""
  155. return [self.exception]
  156. def branches(self):
  157. """Gets a list of basic blocks targeted by this flow instruction."""
  158. return []
  159. def __str__(self):
  160. return 'throw %s' % self.exception.ref_str()
  161. class UnreachableFlow(FlowInstruction):
  162. """Represents a control flow instruction which is unreachable."""
  163. def get_dependencies(self):
  164. """Gets all definitions and instructions on which this instruction depends."""
  165. return []
  166. def branches(self):
  167. """Gets a list of basic blocks targeted by this flow instruction."""
  168. return []
  169. def __str__(self):
  170. return 'unreachable'
  171. class Value(Instruction):
  172. """A value: an instruction that produces some result."""
  173. def get_dependencies(self):
  174. """Gets all definitions and instructions on which this instruction depends."""
  175. raise NotImplementedError()
  176. def has_value(self):
  177. """Tells if this value produces a result that is not None."""
  178. return True
  179. def has_side_effects(self):
  180. """Tells if this instruction has side-effects."""
  181. return False
  182. class BlockParameter(Value):
  183. """A basic block parameter."""
  184. def get_dependencies(self):
  185. """Gets all definitions and instructions on which this instruction depends."""
  186. return []
  187. def __str__(self):
  188. return 'block-parameter'
  189. class FunctionParameter(Value):
  190. """A function parameter."""
  191. def __init__(self, name):
  192. Value.__init__(self)
  193. self.name = name
  194. def get_dependencies(self):
  195. """Gets all definitions and instructions on which this instruction depends."""
  196. return []
  197. def __str__(self):
  198. return 'func-parameter %s' % self.name
  199. class Literal(Value):
  200. """A literal value."""
  201. def __init__(self, literal):
  202. Value.__init__(self)
  203. self.literal = literal
  204. def get_dependencies(self):
  205. """Gets all definitions and instructions on which this instruction depends."""
  206. return []
  207. def has_value(self):
  208. """Tells if this value produces a result that is not None."""
  209. return self.literal is not None
  210. def __str__(self):
  211. return 'literal %r' % self.literal
  212. class IndirectFunctionCall(Value):
  213. """A value that is the result of an indirect function call."""
  214. def __init__(self, target, argument_list):
  215. Value.__init__(self)
  216. assert isinstance(target, Definition)
  217. self.target = target
  218. assert all([isinstance(val, Definition) for _, val in argument_list])
  219. self.argument_list = argument_list
  220. def has_side_effects(self):
  221. """Tells if this instruction has side-effects."""
  222. return True
  223. def get_dependencies(self):
  224. """Gets all definitions and instructions on which this instruction depends."""
  225. return [self.target] + [val for _, val in self.argument_list]
  226. def __str__(self):
  227. return 'indirect-call %s(%s)' % (
  228. self.target.ref_str(),
  229. ', '.join(['%s=%s' % (key, val.ref_str()) for key, val in self.argument_list]))
  230. SIMPLE_POSITIONAL_CALLING_CONVENTION = 'simple-positional'
  231. """The calling convention for functions that use 'return' statements to return.
  232. Arguments are matched to parameters based on position."""
  233. JIT_CALLING_CONVENTION = 'jit'
  234. """The calling convention for jitted functions."""
  235. class DirectFunctionCall(Value):
  236. """A value that is the result of a direct function call."""
  237. def __init__(self, target_name, argument_list, calling_convention=JIT_CALLING_CONVENTION):
  238. Value.__init__(self)
  239. self.target_name = target_name
  240. assert all([isinstance(val, Definition) for _, val in argument_list])
  241. self.argument_list = argument_list
  242. self.calling_convention = calling_convention
  243. def has_side_effects(self):
  244. """Tells if this instruction has side-effects."""
  245. return True
  246. def get_dependencies(self):
  247. """Gets all definitions and instructions on which this instruction depends."""
  248. return [val for _, val in self.argument_list]
  249. def __str__(self):
  250. return 'direct-call %r %s(%s)' % (
  251. self.calling_convention,
  252. self.target_name,
  253. ', '.join(['%s=%s' % (key, val.ref_str()) for key, val in self.argument_list]))
  254. class AllocateRootNode(Value):
  255. """A value that produces a new root node. Typically used in function prologs."""
  256. def __init__(self):
  257. Value.__init__(self)
  258. def get_dependencies(self):
  259. """Gets all definitions and instructions on which this instruction depends."""
  260. return []
  261. def __str__(self):
  262. return 'alloc-root-node'
  263. class DeallocateRootNode(Value):
  264. """A value that deallocates a root node. Typically used in function epilogs."""
  265. def __init__(self, root_node):
  266. Value.__init__(self)
  267. assert isinstance(root_node, Definition)
  268. self.root_node = root_node
  269. def get_dependencies(self):
  270. """Gets all definitions and instructions on which this instruction depends."""
  271. return []
  272. def __str__(self):
  273. return 'free-root-node %s' % self.root_node.ref_str()
  274. class DeclareLocal(Value):
  275. """A value that declares a local variable."""
  276. def __init__(self, variable, root_node):
  277. Value.__init__(self)
  278. self.variable = variable
  279. self.root_node = root_node
  280. def get_dependencies(self):
  281. """Gets all definitions and instructions on which this instruction depends."""
  282. return []
  283. def has_value(self):
  284. """Tells if this value produces a result that is not None."""
  285. return False
  286. def has_side_effects(self):
  287. """Tells if this instruction has side-effects."""
  288. return True
  289. def __str__(self):
  290. return 'declare-local %s, %s' % (self.variable, self.root_node.ref_str())
  291. class DeclareGlobal(Value):
  292. """A value that declares a global variable."""
  293. def __init__(self, variable):
  294. Value.__init__(self)
  295. self.variable = variable
  296. def get_dependencies(self):
  297. """Gets all definitions and instructions on which this instruction depends."""
  298. return []
  299. def has_value(self):
  300. """Tells if this value produces a result that is not None."""
  301. return False
  302. def has_side_effects(self):
  303. """Tells if this instruction has side-effects."""
  304. return True
  305. def __str__(self):
  306. return 'declare-global %s' % self.variable.name
  307. class CheckLocalExists(Value):
  308. """A value that checks if a local value has been defined (yet)."""
  309. def __init__(self, variable):
  310. Value.__init__(self)
  311. self.variable = variable
  312. def get_dependencies(self):
  313. """Gets all definitions and instructions on which this instruction depends."""
  314. return []
  315. def __str__(self):
  316. return 'check-local-exists %s' % self.variable
  317. class ResolveLocal(Value):
  318. """A value that resolves a local as a pointer."""
  319. def __init__(self, variable):
  320. Value.__init__(self)
  321. self.variable = variable
  322. def get_dependencies(self):
  323. """Gets all definitions and instructions on which this instruction depends."""
  324. return []
  325. def __str__(self):
  326. return 'resolve-local %s' % self.variable
  327. class ResolveGlobal(Value):
  328. """A value that resolves a global as a pointer."""
  329. def __init__(self, variable):
  330. Value.__init__(self)
  331. self.variable = variable
  332. def get_dependencies(self):
  333. """Gets all definitions and instructions on which this instruction depends."""
  334. return []
  335. def __str__(self):
  336. return 'resolve-global %s' % self.variable.name
  337. class LoadPointer(Value):
  338. """A value that loads the value assigned to a pointer."""
  339. def __init__(self, pointer):
  340. Value.__init__(self)
  341. self.pointer = pointer
  342. assert isinstance(pointer, Definition)
  343. def get_dependencies(self):
  344. """Gets all definitions and instructions on which this instruction depends."""
  345. return [self.pointer]
  346. def __str__(self):
  347. return 'load %s' % self.pointer.ref_str()
  348. class StoreAtPointer(Value):
  349. """A value that assigns a value to a pointer."""
  350. def __init__(self, pointer, value):
  351. Value.__init__(self)
  352. self.pointer = pointer
  353. assert isinstance(pointer, Definition)
  354. self.value = value
  355. assert isinstance(value, Definition)
  356. def get_dependencies(self):
  357. """Gets all definitions and instructions on which this instruction depends."""
  358. return [self.pointer, self.value]
  359. def has_value(self):
  360. """Tells if this value produces a result that is not None."""
  361. return False
  362. def has_side_effects(self):
  363. """Tells if this instruction has side-effects."""
  364. return True
  365. def __str__(self):
  366. return 'store %s, %s' % (self.pointer.ref_str(), self.value.ref_str())
  367. class Input(Value):
  368. """A value that pops a node from the input queue."""
  369. def get_dependencies(self):
  370. """Gets all definitions and instructions on which this instruction depends."""
  371. return []
  372. def has_side_effects(self):
  373. """Tells if this instruction has side-effects."""
  374. return True
  375. def __str__(self):
  376. return 'input'
  377. class Output(Value):
  378. """A value that pushes a node onto the output queue."""
  379. def __init__(self, value):
  380. Value.__init__(self)
  381. self.value = value
  382. assert isinstance(value, Definition)
  383. def get_dependencies(self):
  384. """Gets all definitions and instructions on which this instruction depends."""
  385. return [self.value]
  386. def has_value(self):
  387. """Tells if this value produces a result that is not None."""
  388. return False
  389. def has_side_effects(self):
  390. """Tells if this instruction has side-effects."""
  391. return True
  392. def __str__(self):
  393. return 'output %s' % self.value.ref_str()
  394. class Binary(Value):
  395. """A value that applies a binary operator to two other values."""
  396. def __init__(self, lhs, operator, rhs):
  397. Value.__init__(self)
  398. self.lhs = lhs
  399. assert isinstance(lhs, Definition)
  400. self.operator = operator
  401. self.rhs = rhs
  402. assert isinstance(rhs, Definition)
  403. def get_dependencies(self):
  404. """Gets all definitions and instructions on which this instruction depends."""
  405. return [self.lhs, self.rhs]
  406. def __str__(self):
  407. return 'binary %s, %r, %s' % (self.lhs.ref_str(), self.operator, self.rhs.ref_str())
  408. def create_jump(block, arguments=None):
  409. """Creates a jump to the given block with the given argument list."""
  410. return JumpFlow(Branch(block, arguments))
  411. def apply_to_value(function, def_or_value):
  412. """Applies the given function to the specified value, or the underlying value of the
  413. given definition."""
  414. if isinstance(def_or_value, Definition):
  415. return apply_to_value(function, def_or_value.value)
  416. else:
  417. return function(def_or_value)
  418. def is_literal(value):
  419. """Tests if the given value is a literal."""
  420. return isinstance(value, Literal)
  421. def is_literal_def(def_or_value):
  422. """Tests if the given value is a literal or a definition with an underlying literal."""
  423. return apply_to_value(is_literal, def_or_value)
  424. def get_literal_value(value):
  425. """Gets the value of the given literal value."""
  426. return value.literal
  427. def get_literal_def_value(def_or_value):
  428. """Gets the value of the given literal value or definition with an underlying literal."""
  429. return apply_to_value(get_literal_value, def_or_value)