cfg_ir.py 30 KB

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