tree_ir.py 47 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226
  1. # NOTE: NOP_LITERAL abuses a mechanic of the modelverse kernel. Specifically,
  2. # whenever the `ModelverseKernel.execute_yields` method returns `None`, then
  3. # the server built around it takes that as a hint that an instruction's phase
  4. # has been completed. The server interrupts the kernel's thread of execution
  5. # when it remarks that an instruction has completed a phase (i.e., when `None`
  6. # is returned by `ModelverseKernel.execute_yields`) and proceeds to check for
  7. # input and output.
  8. #
  9. # In assembly language, a nop is usually used as a point at which a thread of
  10. # execution can be terminated. It follows from the paragraph above that what
  11. # the interpreter does is more or less equivalent to placing nops after every
  12. # instruction. It is worthwhile to remark that JIT-compiled code cannot rely
  13. # on the kernel to interrupt the thread of execution automatically during a
  14. # jitted function's execution -- jitted functions are considered equivalent
  15. # to a single instruction as far as the kernel is concerned. A nop will be
  16. # inserted _after_ the function call (if it is called from interpreted code)
  17. # but that does not suffice for IO, which needs the input/output processing
  18. # to be performed during function execution.
  19. #
  20. # For this reason, the JIT must strategically interrupt the execution of the
  21. # functions it compiles. In other words, it must insert its own nops.
  22. # Here comes the interesting part: a nop is equivalent to `yield None`,
  23. # because that will persuade `ModelverseKernel.execute_yields` to relay the
  24. # `None` marker value to the server, without terminating the current
  25. # generator.
  26. NOP_LITERAL = None
  27. """A literal that results in a nop during which execution may be interrupted
  28. when yielded."""
  29. class Instruction(object):
  30. """A base class for instructions. An instruction is essentially a syntax
  31. node that must first be defined, and can only then be used."""
  32. def __init__(self):
  33. self.has_result_cache = None
  34. self.has_definition_cache = None
  35. def has_result(self):
  36. """Tells if this instruction computes a result."""
  37. if self.has_result_cache is None:
  38. self.has_result_cache = self.has_result_impl()
  39. return self.has_result_cache
  40. def has_definition(self):
  41. """Tells if this instruction requires a definition."""
  42. if self.has_definition_cache is None:
  43. self.has_definition_cache = self.has_definition_impl()
  44. return self.has_definition_cache
  45. def has_result_impl(self):
  46. """Tells if this instruction computes a result."""
  47. return True
  48. def has_definition_impl(self):
  49. """Tells if this instruction requires a definition."""
  50. return True
  51. def get_result_name_override(self, code_generator):
  52. """Gets a value that overrides the code generator's result name for this
  53. instruction if it is not None."""
  54. return None
  55. def generate_python_def(self, code_generator):
  56. """Generates a Python statement that executes this instruction.
  57. The statement is appended immediately to the code generator."""
  58. if self.has_definition():
  59. raise NotImplementedError()
  60. else:
  61. code_generator.append_line('pass')
  62. def generate_python_use(self, code_generator):
  63. """Generates a Python expression that retrieves this instruction's
  64. result. The expression is returned as a string."""
  65. if self.has_result():
  66. return code_generator.get_result_name(self)
  67. else:
  68. return 'None'
  69. def get_children(self):
  70. """Gets this instruction's sequence of child instructions."""
  71. raise NotImplementedError()
  72. def create(self, new_children):
  73. """Creates a new instruction of this type from the given sequence of child instructions."""
  74. raise NotImplementedError()
  75. def simplify_node(self):
  76. """Applies basic simplification to this instruction only."""
  77. return self
  78. def simplify(self):
  79. """Applies basic simplification to this instruction and all of its children."""
  80. # This fairly convoluted one-liner first simplifies all children, then creates
  81. # an instruction from the simplified children, and finally simplifies that top-level
  82. # instruction.
  83. return self.create([c.simplify() for c in self.get_children()]).simplify_node()
  84. def __str__(self):
  85. code_generator = PythonGenerator()
  86. self.generate_python_def(code_generator)
  87. return str(code_generator)
  88. class PythonGenerator(object):
  89. """Generates Python code from instructions."""
  90. def __init__(self, combine_state_definitions=True):
  91. self.code = []
  92. self.state_definitions = []
  93. self.state_definition_names = set()
  94. self.indentation_string = ' ' * 4
  95. self.indentation = 0
  96. self.result_name_dict = {}
  97. self.combine_state_definitions = combine_state_definitions
  98. def append(self, text):
  99. """Appends the given string to this code generator."""
  100. self.flush_state_definitions()
  101. self.code.append(text)
  102. def append_indentation(self):
  103. """Appends indentation to the code generator."""
  104. self.append(self.indentation_string * self.indentation)
  105. def append_line(self, line=None):
  106. """Appends the indentation string followed by the given string (if any)
  107. and a newline to the code generator."""
  108. self.append_indentation()
  109. if line is not None:
  110. self.append(line)
  111. self.append('\n')
  112. def increase_indentation(self):
  113. """Increases the code generator's indentation by one indent."""
  114. self.flush_state_definitions()
  115. self.indentation += 1
  116. def decrease_indentation(self):
  117. """Decreases the code generator's indentation by one indent."""
  118. self.flush_state_definitions()
  119. self.indentation -= 1
  120. def get_result_name(self, instruction, advised_name=None):
  121. """Gets the name of the given instruction's result variable."""
  122. if instruction not in self.result_name_dict:
  123. override_name = instruction.get_result_name_override(self)
  124. if override_name is not None:
  125. self.result_name_dict[instruction] = override_name
  126. elif advised_name is not None:
  127. self.result_name_dict[instruction] = advised_name
  128. else:
  129. self.result_name_dict[instruction] = \
  130. 'tmp' + str(len(self.result_name_dict))
  131. result = self.result_name_dict[instruction]
  132. if result in self.state_definition_names:
  133. # This might mean that we're trying to access a name that is
  134. # defined by the current block of state definitions. So we need
  135. # to flush the state definitions now.
  136. self.flush_state_definitions()
  137. return result
  138. def append_definition(self, lhs, rhs):
  139. """Defines the first instruction's result variable as the second
  140. instruction's result."""
  141. self.append_line(
  142. self.get_result_name(lhs) + ' = ' + rhs.generate_python_use(self))
  143. def append_move_definition(self, lhs, rhs):
  144. """First defines the second instruction, then defines the first
  145. instruction as the result of the second."""
  146. if rhs.has_definition():
  147. # Retrieve the result name for the lhs.
  148. lhs_result_name = self.get_result_name(lhs)
  149. # Encourage the rhs to take on the same result name as the lhs.
  150. rhs_result_name = self.get_result_name(rhs, lhs_result_name)
  151. # Generate the rhs' definition.
  152. rhs.generate_python_def(self)
  153. # Only perform an assignment if it's truly necessary.
  154. if lhs_result_name != rhs_result_name:
  155. self.append_definition(lhs, rhs)
  156. else:
  157. self.append_definition(lhs, rhs)
  158. def append_state_definition(self, lhs, opcode, args):
  159. """Appends a definition that queries the modelverse state."""
  160. result_name = self.get_result_name(lhs)
  161. request_tuple = '(%s, [%s])' % (
  162. repr(opcode),
  163. ', '.join([arg_i.generate_python_use(self) for arg_i in args]))
  164. self.state_definitions.append((result_name, request_tuple))
  165. self.state_definition_names.add(result_name)
  166. if not self.combine_state_definitions:
  167. self.flush_state_definitions()
  168. def flush_state_definitions(self):
  169. """Flushes the list of state-access definitions to the generated code."""
  170. state_defs = self.state_definitions
  171. if len(state_defs) > 0:
  172. # Clear state_definitions _before_ calling append_line, because append_line
  173. # will call flush_state_definitions. Clearing state_definitions afterward
  174. # will result in infinite recursion.
  175. self.state_definitions = []
  176. self.state_definition_names = set()
  177. if len(state_defs) == 1:
  178. self.append_line('%s, = yield [%s]' % state_defs[0])
  179. else:
  180. self.append_line(
  181. "%s = yield [%s]" % (
  182. ', '.join([name for name, _ in state_defs]),
  183. ', '.join([def_val for _, def_val in state_defs])))
  184. def __str__(self):
  185. self.flush_state_definitions()
  186. return ''.join(self.code)
  187. class VoidInstruction(Instruction):
  188. """A base class for instructions that do not return a value."""
  189. def has_result_impl(self):
  190. """Tells if this instruction computes a result."""
  191. return False
  192. def get_children(self):
  193. """Gets this instruction's sequence of child instructions."""
  194. return []
  195. def create(self, new_children):
  196. """Creates a new instruction of this type from the given sequence of child instructions."""
  197. return self
  198. class EmptyInstruction(VoidInstruction):
  199. """Represents the empty instruction, which does nothing."""
  200. def has_definition_impl(self):
  201. """Tells if this instruction requires a definition."""
  202. return False
  203. class SelectInstruction(Instruction):
  204. """Represents a select-instruction: an instruction that defines one of two
  205. child instructions, and sets its result to the defined child's result."""
  206. def __init__(self, condition, if_clause, else_clause):
  207. Instruction.__init__(self)
  208. self.condition = condition
  209. self.if_clause = if_clause
  210. self.else_clause = else_clause
  211. def has_result_impl(self):
  212. """Tells if this instruction computes a result."""
  213. return self.if_clause.has_result() or self.else_clause.has_result()
  214. def simplify_node(self):
  215. """Applies basic simplification to this instruction only."""
  216. if isinstance(self.condition, LiteralInstruction):
  217. return self.if_clause if self.condition.literal else self.else_clause
  218. else:
  219. return SelectInstruction(self.condition, self.if_clause, self.else_clause)
  220. def get_children(self):
  221. """Gets this instruction's sequence of child instructions."""
  222. return [self.condition, self.if_clause, self.else_clause]
  223. def create(self, new_children):
  224. """Creates a new instruction of this type from the given sequence of child instructions."""
  225. condition, if_clause, else_clause = new_children
  226. return SelectInstruction(condition, if_clause, else_clause)
  227. def generate_python_def(self, code_generator):
  228. """Generates Python code for this instruction."""
  229. if_has_result = self.has_result()
  230. if self.condition.has_definition():
  231. self.condition.generate_python_def(code_generator)
  232. code_generator.append_line(
  233. 'if ' + self.condition.generate_python_use(code_generator) + ':')
  234. code_generator.increase_indentation()
  235. if if_has_result:
  236. code_generator.append_move_definition(self, self.if_clause)
  237. else:
  238. self.if_clause.generate_python_def(code_generator)
  239. code_generator.decrease_indentation()
  240. else_has_def = self.else_clause.has_definition()
  241. if else_has_def or if_has_result:
  242. code_generator.append_line('else:')
  243. code_generator.increase_indentation()
  244. if if_has_result:
  245. code_generator.append_move_definition(self, self.else_clause)
  246. else:
  247. self.else_clause.generate_python_def(code_generator)
  248. code_generator.decrease_indentation()
  249. class ReturnInstruction(VoidInstruction):
  250. """Represents a return-instruction."""
  251. def __init__(self, value):
  252. VoidInstruction.__init__(self)
  253. self.value = value
  254. def get_children(self):
  255. """Gets this instruction's sequence of child instructions."""
  256. return [self.value]
  257. def create(self, new_children):
  258. """Creates a new instruction of this type from the given sequence of child instructions."""
  259. value, = new_children
  260. return ReturnInstruction(value)
  261. def generate_python_def(self, code_generator):
  262. """Generates Python code for this instruction."""
  263. if self.value.has_definition():
  264. self.value.generate_python_def(code_generator)
  265. code_generator.append_line(
  266. 'raise PrimitiveFinished(' +
  267. self.value.generate_python_use(code_generator) +
  268. ')')
  269. class RaiseInstruction(VoidInstruction):
  270. """An instruction that raises an error."""
  271. def __init__(self, value):
  272. VoidInstruction.__init__(self)
  273. self.value = value
  274. def get_children(self):
  275. """Gets this instruction's sequence of child instructions."""
  276. return [self.value]
  277. def create(self, new_children):
  278. """Creates a new instruction of this type from the given sequence of child instructions."""
  279. value, = new_children
  280. return RaiseInstruction(value)
  281. def generate_python_def(self, code_generator):
  282. """Generates Python code for this instruction."""
  283. self.value.generate_python_def(code_generator)
  284. code_generator.append_line(
  285. 'raise ' + self.value.generate_python_use(code_generator))
  286. class CallInstruction(Instruction):
  287. """An instruction that performs a simple call."""
  288. def __init__(self, target, argument_list):
  289. Instruction.__init__(self)
  290. self.target = target
  291. self.argument_list = argument_list
  292. def get_children(self):
  293. """Gets this instruction's sequence of child instructions."""
  294. return [self.target] + self.argument_list
  295. def create(self, new_children):
  296. """Creates a new instruction of this type from the given sequence of child instructions."""
  297. return CallInstruction(new_children[0], new_children[1:])
  298. def generate_python_def(self, code_generator):
  299. """Generates Python code for this instruction."""
  300. if self.target.has_definition():
  301. self.target.generate_python_def(code_generator)
  302. for arg in self.argument_list:
  303. if arg.has_definition():
  304. arg.generate_python_def(code_generator)
  305. code_generator.append_line(
  306. '%s = %s(%s)' % (
  307. code_generator.get_result_name(self),
  308. self.target.generate_python_use(code_generator),
  309. ', '.join([arg.generate_python_use(code_generator) for arg in self.argument_list])))
  310. class PrintInstruction(Instruction):
  311. """An instruction that prints a value."""
  312. def __init__(self, argument):
  313. Instruction.__init__(self)
  314. self.argument = argument
  315. def has_result_impl(self):
  316. """Tells if this instruction has a result."""
  317. return False
  318. def get_children(self):
  319. """Gets this instruction's sequence of child instructions."""
  320. return [self.argument]
  321. def create(self, new_children):
  322. """Creates a new instruction of this type from the given sequence of child instructions."""
  323. arg, = new_children
  324. return PrintInstruction(arg)
  325. def generate_python_def(self, code_generator):
  326. """Generates Python code for this instruction."""
  327. if self.argument.has_definition():
  328. self.argument.generate_python_def(code_generator)
  329. code_generator.append_line(
  330. 'print(%s)' % (
  331. self.argument.generate_python_use(code_generator)))
  332. class BinaryInstruction(Instruction):
  333. """An instruction that performs a binary operation."""
  334. def __init__(self, lhs, operator, rhs):
  335. Instruction.__init__(self)
  336. self.lhs = lhs
  337. self.operator = operator
  338. self.rhs = rhs
  339. def has_definition_impl(self):
  340. """Tells if this instruction requires a definition."""
  341. return self.lhs.has_definition() or self.rhs.has_definition()
  342. def get_children(self):
  343. """Gets this instruction's sequence of child instructions."""
  344. return [self.lhs, self.rhs]
  345. def create(self, new_children):
  346. """Creates a new instruction of this type from the given sequence of child instructions."""
  347. lhs, rhs, = new_children
  348. return BinaryInstruction(lhs, self.operator, rhs)
  349. def simplify_node(self):
  350. """Applies basic simplification to this instruction only."""
  351. if isinstance(self.lhs, LiteralInstruction) and isinstance(self.rhs, LiteralInstruction):
  352. # TODO: there's probably a better way to do this than with eval.
  353. return LiteralInstruction(
  354. eval('%s %s %s' % (repr(self.lhs.literal), self.operator, repr(self.rhs.literal))))
  355. else:
  356. return self
  357. def generate_python_use(self, code_generator):
  358. """Generates a Python expression that retrieves this instruction's
  359. result. The expression is returned as a string."""
  360. return '(%s %s %s)' % (
  361. self.lhs.generate_python_use(code_generator),
  362. self.operator,
  363. self.rhs.generate_python_use(code_generator))
  364. def generate_python_def(self, code_generator):
  365. """Generates a Python statement that executes this instruction.
  366. The statement is appended immediately to the code generator."""
  367. if self.lhs.has_definition():
  368. self.lhs.generate_python_def(code_generator)
  369. if self.rhs.has_definition():
  370. self.rhs.generate_python_def(code_generator)
  371. elif self.rhs.has_definition():
  372. self.rhs.generate_python_def(code_generator)
  373. else:
  374. code_generator.append_line('pass')
  375. class UnaryInstruction(Instruction):
  376. """An instruction that performs a unary operation."""
  377. def __init__(self, operator, operand):
  378. Instruction.__init__(self)
  379. self.operator = operator
  380. self.operand = operand
  381. def has_definition_impl(self):
  382. """Tells if this instruction requires a definition."""
  383. return self.operand.has_definition()
  384. def get_children(self):
  385. """Gets this instruction's sequence of child instructions."""
  386. return [self.operand]
  387. def create(self, new_children):
  388. """Creates a new instruction of this type from the given sequence of child instructions."""
  389. operand, = new_children
  390. return UnaryInstruction(self.operator, operand)
  391. def simplify_node(self):
  392. """Applies basic simplification to this instruction only."""
  393. if isinstance(self.operand, LiteralInstruction):
  394. # TODO: there's probably a better way to do this than with eval.
  395. return LiteralInstruction(
  396. eval('%s %s' % (self.operator, repr(self.operand.literal))))
  397. else:
  398. return self
  399. def generate_python_use(self, code_generator):
  400. """Generates a Python expression that retrieves this instruction's
  401. result. The expression is returned as a string."""
  402. return '(%s %s)' % (
  403. self.operator,
  404. self.operand.generate_python_use(code_generator))
  405. def generate_python_def(self, code_generator):
  406. """Generates a Python statement that executes this instruction.
  407. The statement is appended immediately to the code generator."""
  408. if self.operand.has_definition():
  409. self.operand.generate_python_def(code_generator)
  410. else:
  411. code_generator.append_line('pass')
  412. class LoopInstruction(VoidInstruction):
  413. """Represents a loop-instruction, which loops until broken."""
  414. def __init__(self, body):
  415. VoidInstruction.__init__(self)
  416. self.body = body
  417. def get_children(self):
  418. """Gets this instruction's sequence of child instructions."""
  419. return [self.body]
  420. def create(self, new_children):
  421. """Creates a new instruction of this type from the given sequence of child instructions."""
  422. body, = new_children
  423. return LoopInstruction(body)
  424. def generate_python_def(self, code_generator):
  425. """Generates Python code for this instruction."""
  426. code_generator.append_line('while 1:')
  427. code_generator.increase_indentation()
  428. self.body.generate_python_def(code_generator)
  429. code_generator.decrease_indentation()
  430. class BreakInstruction(VoidInstruction):
  431. """Represents a break-instruction."""
  432. def generate_python_def(self, code_generator):
  433. """Generates Python code for this instruction."""
  434. code_generator.append_line('break')
  435. class ContinueInstruction(VoidInstruction):
  436. """Represents a continue-instruction."""
  437. def generate_python_def(self, code_generator):
  438. """Generates Python code for this instruction."""
  439. code_generator.append_line('continue')
  440. class CompoundInstruction(Instruction):
  441. """Represents an instruction that evaluates two other instructions
  442. in order, and returns the second instruction's result."""
  443. def __init__(self, first, second):
  444. Instruction.__init__(self)
  445. self.first = first
  446. self.second = second
  447. def has_result_impl(self):
  448. """Tells if this instruction has a result."""
  449. return self.second.has_result() or self.first.has_result()
  450. def get_children(self):
  451. """Gets this instruction's sequence of child instructions."""
  452. return [self.first, self.second]
  453. def create(self, new_children):
  454. """Creates a new instruction of this type from the given sequence of child instructions."""
  455. first, second = new_children
  456. return CompoundInstruction(first, second)
  457. def simplify_node(self):
  458. """Applies basic simplification to this instruction and its children."""
  459. if not self.first.has_definition() and (
  460. not self.first.has_result() or self.second.has_result()):
  461. return self.second
  462. elif (not self.second.has_definition()) and (not self.second.has_result()):
  463. return self.first
  464. else:
  465. return self
  466. def generate_python_def(self, code_generator):
  467. """Generates Python code for this instruction."""
  468. if self.second.has_result():
  469. self.first.generate_python_def(code_generator)
  470. code_generator.append_move_definition(self, self.second)
  471. elif self.first.has_result():
  472. code_generator.append_move_definition(self, self.first)
  473. self.second.generate_python_def(code_generator)
  474. else:
  475. self.first.generate_python_def(code_generator)
  476. self.second.generate_python_def(code_generator)
  477. class LiteralInstruction(Instruction):
  478. """Represents an integer, floating-point, string or Boolean literal."""
  479. def __init__(self, literal):
  480. Instruction.__init__(self)
  481. self.literal = literal
  482. def has_definition_impl(self):
  483. """Tells if this instruction requires a definition."""
  484. return False
  485. def get_children(self):
  486. """Gets this instruction's sequence of child instructions."""
  487. return []
  488. def create(self, new_children):
  489. """Creates a new instruction of this type from the given sequence of child instructions."""
  490. return self
  491. def generate_python_use(self, code_generator):
  492. """Generates a Python expression that retrieves this instruction's
  493. result. The expression is returned as a string."""
  494. return repr(self.literal)
  495. class DictionaryLiteralInstruction(Instruction):
  496. """Constructs a dictionary literal."""
  497. def __init__(self, key_value_pairs):
  498. Instruction.__init__(self)
  499. self.key_value_pairs = key_value_pairs
  500. def get_children(self):
  501. """Gets this instruction's sequence of child instructions."""
  502. return [val for _, val in self.key_value_pairs]
  503. def create(self, new_children):
  504. """Creates a new instruction of this type from the given sequence of child instructions."""
  505. keys = [k for k, _ in self.key_value_pairs]
  506. return DictionaryLiteralInstruction(zip(keys, new_children))
  507. def has_definition_impl(self):
  508. """Tells if this instruction requires a definition."""
  509. return any(
  510. [key.has_definition() or val.has_definition()
  511. for key, val in self.key_value_pairs])
  512. def simplify(self):
  513. """Applies basic simplification to this instruction and its children."""
  514. return DictionaryLiteralInstruction(
  515. [(key.simplify(), val.simplify()) for key, val in self.key_value_pairs])
  516. def generate_dictionary_expr(self, code_generator):
  517. """Generates an expression that creates this dictionary."""
  518. return '{ %s }' % ', '.join(
  519. ['%s : %s' % (
  520. key.generate_python_use(code_generator),
  521. val.generate_python_use(code_generator))
  522. for key, val in self.key_value_pairs])
  523. def generate_python_def(self, code_generator):
  524. """Generates a Python statement that executes this instruction.
  525. The statement is appended immediately to the code generator."""
  526. if self.has_definition():
  527. for key, val in self.key_value_pairs:
  528. if key.has_definition():
  529. key.generate_python_def(code_generator)
  530. if val.has_definition():
  531. val.generate_python_def(code_generator)
  532. code_generator.append_line('%s = %s' % (
  533. code_generator.get_result_name(self),
  534. self.generate_dictionary_expr(code_generator)))
  535. else:
  536. code_generator.append_line('pass')
  537. def generate_python_use(self, code_generator):
  538. """Generates a Python expression that retrieves this instruction's
  539. result. The expression is returned as a string."""
  540. if self.has_definition():
  541. return code_generator.get_result_name(self)
  542. else:
  543. return self.generate_dictionary_expr(code_generator)
  544. class StateInstruction(Instruction):
  545. """An instruction that accesses the modelverse state."""
  546. def get_opcode(self):
  547. """Gets the opcode for this state instruction."""
  548. raise NotImplementedError()
  549. def get_arguments(self):
  550. """Gets this state instruction's argument list."""
  551. raise NotImplementedError()
  552. def get_children(self):
  553. """Gets this instruction's sequence of child instructions."""
  554. return self.get_arguments()
  555. def create(self, new_children):
  556. """Creates a new instruction of this type from the given sequence of child instructions."""
  557. return type(self)(*new_children)
  558. def generate_python_def(self, code_generator):
  559. """Generates a Python statement that executes this instruction.
  560. The statement is appended immediately to the code generator."""
  561. args = self.get_arguments()
  562. for arg_i in args:
  563. if arg_i.has_definition():
  564. arg_i.generate_python_def(code_generator)
  565. code_generator.append_state_definition(self, self.get_opcode(), args)
  566. class RunGeneratorFunctionInstruction(StateInstruction):
  567. """An instruction that runs a generator function."""
  568. def __init__(self, function, argument_dict):
  569. StateInstruction.__init__(self)
  570. self.function = function
  571. self.argument_dict = argument_dict
  572. def get_opcode(self):
  573. """Gets the opcode for this state instruction."""
  574. return "CALL_KWARGS"
  575. def get_arguments(self):
  576. """Gets this state instruction's argument list."""
  577. return [self.function, self.argument_dict]
  578. class VariableName(object):
  579. """A data structure that unifies names across instructions that access the
  580. same variable."""
  581. def __init__(self, name):
  582. self.name = name
  583. def get_result_name_override(self, _):
  584. """Gets a value that overrides the code generator's result name for this
  585. instruction if it is not None."""
  586. return self.name
  587. class VariableInstruction(Instruction):
  588. """A base class for instructions that access variables."""
  589. def __init__(self, name):
  590. Instruction.__init__(self)
  591. if isinstance(name, str) or isinstance(name, unicode) or name is None:
  592. self.name = VariableName(name)
  593. else:
  594. self.name = name
  595. def get_children(self):
  596. """Gets this instruction's sequence of child instructions."""
  597. raise NotImplementedError()
  598. def create(self, new_children):
  599. """Creates a new instruction of this type from the given sequence of child instructions."""
  600. raise NotImplementedError()
  601. def get_result_name_override(self, code_generator):
  602. """Gets a value that overrides the code generator's result name for this
  603. instruction if it is not None."""
  604. return code_generator.get_result_name(self.name)
  605. class LocalInstruction(VariableInstruction):
  606. """A base class for instructions that access local variables."""
  607. def get_children(self):
  608. """Gets this instruction's sequence of child instructions."""
  609. raise NotImplementedError()
  610. def create(self, new_children):
  611. """Creates a new instruction of this type from the given sequence of child instructions."""
  612. raise NotImplementedError()
  613. def create_load(self):
  614. """Creates an instruction that loads the variable referenced by this instruction."""
  615. return LoadLocalInstruction(self.name)
  616. def create_store(self, value):
  617. """Creates an instruction that stores the given value in the variable referenced
  618. by this instruction."""
  619. return StoreLocalInstruction(self.name, value)
  620. class StoreLocalInstruction(LocalInstruction):
  621. """An instruction that stores a value in a local variable."""
  622. def __init__(self, name, value):
  623. LocalInstruction.__init__(self, name)
  624. self.value = value
  625. def get_children(self):
  626. """Gets this instruction's sequence of child instructions."""
  627. return [self.value]
  628. def create(self, new_children):
  629. """Creates a new instruction of this type from the given sequence of child instructions."""
  630. val, = new_children
  631. return StoreLocalInstruction(self.name, val)
  632. def generate_python_def(self, code_generator):
  633. """Generates a Python statement that executes this instruction.
  634. The statement is appended immediately to the code generator."""
  635. code_generator.append_move_definition(self, self.value)
  636. class LoadLocalInstruction(LocalInstruction):
  637. """An instruction that loads a value from a local variable."""
  638. def has_definition_impl(self):
  639. """Tells if this instruction requires a definition."""
  640. return False
  641. def get_children(self):
  642. """Gets this instruction's sequence of child instructions."""
  643. return []
  644. def create(self, new_children):
  645. """Creates a new instruction of this type from the given sequence of child instructions."""
  646. return self
  647. class DefineFunctionInstruction(VariableInstruction):
  648. """An instruction that defines a function."""
  649. def __init__(self, name, parameter_list, body):
  650. VariableInstruction.__init__(self, name)
  651. self.parameter_list = parameter_list
  652. self.body = body
  653. def get_children(self):
  654. """Gets this instruction's sequence of child instructions."""
  655. return [self.body]
  656. def create(self, new_children):
  657. """Creates a new instruction of this type from the given sequence of child instructions."""
  658. body, = new_children
  659. return DefineFunctionInstruction(self.name, self.parameter_list, body)
  660. def generate_python_def(self, code_generator):
  661. """Generates a Python statement that executes this instruction.
  662. The statement is appended immediately to the code generator."""
  663. code_generator.append_line('def %s(%s):' % (
  664. code_generator.get_result_name(self), ', '.join(self.parameter_list)))
  665. code_generator.increase_indentation()
  666. self.body.generate_python_def(code_generator)
  667. code_generator.decrease_indentation()
  668. class LocalExistsInstruction(LocalInstruction):
  669. """An instruction that checks if a local variable exists."""
  670. def has_definition_impl(self):
  671. """Tells if this instruction requires a definition."""
  672. return False
  673. def get_children(self):
  674. """Gets this instruction's sequence of child instructions."""
  675. return []
  676. def create(self, new_children):
  677. """Creates a new instruction of this type from the given sequence of child instructions."""
  678. return self
  679. def generate_python_use(self, code_generator):
  680. """Generates a Python expression that retrieves this instruction's
  681. result. The expression is returned as a string."""
  682. return "'%s' in locals()" % self.get_result_name_override(code_generator)
  683. class LoadGlobalInstruction(VariableInstruction):
  684. """An instruction that loads a value from a global variable."""
  685. def has_definition_impl(self):
  686. """Tells if this instruction requires a definition."""
  687. return False
  688. def get_children(self):
  689. """Gets this instruction's sequence of child instructions."""
  690. return []
  691. def create(self, new_children):
  692. """Creates a new instruction of this type from the given sequence of child instructions."""
  693. return self
  694. class LoadIndexInstruction(Instruction):
  695. """An instruction that produces a value by indexing a specified expression with
  696. a given key."""
  697. def __init__(self, indexed, key):
  698. Instruction.__init__(self)
  699. self.indexed = indexed
  700. self.key = key
  701. def has_definition_impl(self):
  702. """Tells if this instruction requires a definition."""
  703. return False
  704. def get_children(self):
  705. """Gets this instruction's sequence of child instructions."""
  706. return [self.indexed, self.key]
  707. def create(self, new_children):
  708. """Creates a new instruction of this type from the given sequence of child instructions."""
  709. indexed, key = new_children
  710. return LoadIndexInstruction(indexed, key)
  711. def generate_python_use(self, code_generator):
  712. """Generates a Python expression that retrieves this instruction's
  713. result. The expression is returned as a string."""
  714. if self.indexed.has_definition():
  715. self.indexed.generate_python_def(code_generator)
  716. if self.key.has_definition():
  717. self.key.generate_python_def(code_generator)
  718. return "%s[%s]" % (
  719. self.indexed.generate_python_use(code_generator),
  720. self.key.generate_python_use(code_generator))
  721. class LoadMemberInstruction(Instruction):
  722. """An instruction that produces a value by loading a member from a container."""
  723. def __init__(self, container, member_name):
  724. Instruction.__init__(self)
  725. self.container = container
  726. self.member_name = member_name
  727. def has_definition_impl(self):
  728. """Tells if this instruction requires a definition."""
  729. return self.container.has_definition()
  730. def get_children(self):
  731. """Gets this instruction's sequence of child instructions."""
  732. return [self.container]
  733. def create(self, new_children):
  734. """Creates a new instruction of this type from the given sequence of child instructions."""
  735. container, = new_children
  736. return LoadMemberInstruction(container, self.member_name)
  737. def generate_python_def(self, code_generator):
  738. """Generates a Python statement that executes this instruction.
  739. The statement is appended immediately to the code generator."""
  740. self.container.generate_python_def(code_generator)
  741. def generate_python_use(self, code_generator):
  742. """Generates a Python expression that retrieves this instruction's
  743. result. The expression is returned as a string."""
  744. return "%s.%s" % (
  745. self.container.generate_python_use(code_generator),
  746. self.member_name)
  747. class StoreMemberInstruction(Instruction):
  748. """An instruction that stores a value in a container member."""
  749. def __init__(self, container, member_name, value):
  750. Instruction.__init__(self)
  751. self.container = container
  752. self.member_name = member_name
  753. self.value = value
  754. def has_definition_impl(self):
  755. """Tells if this instruction requires a definition."""
  756. return True
  757. def has_result_impl(self):
  758. """Tells if this instruction computes a result."""
  759. return False
  760. def get_children(self):
  761. """Gets this instruction's sequence of child instructions."""
  762. return [self.container, self.value]
  763. def create(self, new_children):
  764. """Creates a new instruction of this type from the given sequence of child instructions."""
  765. container, value = new_children
  766. return StoreMemberInstruction(container, self.member_name, value)
  767. def generate_python_def(self, code_generator):
  768. """Generates a Python statement that executes this instruction.
  769. The statement is appended immediately to the code generator."""
  770. if self.container.has_definition():
  771. self.container.generate_python_def(code_generator)
  772. code_generator.append_line('%s.%s = %s' % (
  773. self.container.generate_python_use(code_generator),
  774. self.member_name,
  775. self.value.generate_python_use(code_generator)))
  776. class NopInstruction(Instruction):
  777. """A nop instruction, which allows for the kernel's thread of execution to be interrupted."""
  778. def has_result_impl(self):
  779. """Tells if this instruction computes a result."""
  780. return False
  781. def get_children(self):
  782. """Gets this instruction's sequence of child instructions."""
  783. return []
  784. def create(self, new_children):
  785. """Creates a new instruction of this type from the given sequence of child instructions."""
  786. return self
  787. def generate_python_def(self, code_generator):
  788. """Generates a Python statement that executes this instruction.
  789. The statement is appended immediately to the code generator."""
  790. code_generator.append_line('yield %s' % repr(NOP_LITERAL))
  791. class ReadValueInstruction(StateInstruction):
  792. """An instruction that reads a value from a node."""
  793. def __init__(self, node_id):
  794. StateInstruction.__init__(self)
  795. self.node_id = node_id
  796. def simplify_node(self):
  797. """Applies basic simplification to this instruction only."""
  798. if isinstance(self.node_id, CreateNodeWithValueInstruction):
  799. return self.node_id.value
  800. else:
  801. return self
  802. def get_opcode(self):
  803. """Gets the opcode for this state instruction."""
  804. return "RV"
  805. def get_arguments(self):
  806. """Gets this state instruction's argument list."""
  807. return [self.node_id]
  808. class ReadDictionaryValueInstruction(StateInstruction):
  809. """An instruction that reads a dictionary value."""
  810. def __init__(self, node_id, key):
  811. StateInstruction.__init__(self)
  812. self.node_id = node_id
  813. self.key = key
  814. def get_opcode(self):
  815. """Gets the opcode for this state instruction."""
  816. return "RD"
  817. def get_arguments(self):
  818. """Gets this state instruction's argument list."""
  819. return [self.node_id, self.key]
  820. class ReadDictionaryEdgeInstruction(StateInstruction):
  821. """An instruction that reads a dictionary edge."""
  822. def __init__(self, node_id, key):
  823. StateInstruction.__init__(self)
  824. self.node_id = node_id
  825. self.key = key
  826. def get_opcode(self):
  827. """Gets the opcode for this state instruction."""
  828. return "RDE"
  829. def get_arguments(self):
  830. """Gets this state instruction's argument list."""
  831. return [self.node_id, self.key]
  832. class ReadEdgeInstruction(StateInstruction):
  833. """An instruction that reads an edge."""
  834. def __init__(self, node_id):
  835. StateInstruction.__init__(self)
  836. self.node_id = node_id
  837. def get_opcode(self):
  838. """Gets the opcode for this state instruction."""
  839. return "RE"
  840. def get_arguments(self):
  841. """Gets this state instruction's argument list."""
  842. return [self.node_id]
  843. class ReadOutgoingEdgesInstruction(StateInstruction):
  844. """An instruction that reads all outgoing edges for a node."""
  845. def __init__(self, node_id):
  846. StateInstruction.__init__(self)
  847. self.node_id = node_id
  848. def get_opcode(self):
  849. """Gets the opcode for this state instruction."""
  850. return "RO"
  851. def get_arguments(self):
  852. """Gets this state instruction's argument list."""
  853. return [self.node_id]
  854. class ReadIncomingEdgesInstruction(StateInstruction):
  855. """An instruction that reads all incoming edges for a node."""
  856. def __init__(self, node_id):
  857. StateInstruction.__init__(self)
  858. self.node_id = node_id
  859. def get_opcode(self):
  860. """Gets the opcode for this state instruction."""
  861. return "RI"
  862. def get_arguments(self):
  863. """Gets this state instruction's argument list."""
  864. return [self.node_id]
  865. class CreateNodeInstruction(StateInstruction):
  866. """An instruction that creates an empty node."""
  867. def get_opcode(self):
  868. """Gets the opcode for this state instruction."""
  869. return "CN"
  870. def get_arguments(self):
  871. """Gets this state instruction's argument list."""
  872. return []
  873. class CreateNodeWithValueInstruction(StateInstruction):
  874. """An instruction that creates a node with a given value."""
  875. def __init__(self, value):
  876. StateInstruction.__init__(self)
  877. self.value = value
  878. def get_opcode(self):
  879. """Gets the opcode for this state instruction."""
  880. return "CNV"
  881. def get_arguments(self):
  882. """Gets this state instruction's argument list."""
  883. return [self.value]
  884. class CreateEdgeInstruction(StateInstruction):
  885. """An instruction that creates an edge."""
  886. def __init__(self, source_id, target_id):
  887. StateInstruction.__init__(self)
  888. self.source_id = source_id
  889. self.target_id = target_id
  890. def get_opcode(self):
  891. """Gets the opcode for this state instruction."""
  892. return "CE"
  893. def get_arguments(self):
  894. """Gets this state instruction's argument list."""
  895. return [self.source_id, self.target_id]
  896. class CreateDictionaryEdgeInstruction(StateInstruction):
  897. """An instruction that creates a dictionary edge."""
  898. def __init__(self, source_id, key, target_id):
  899. StateInstruction.__init__(self)
  900. self.source_id = source_id
  901. self.key = key
  902. self.target_id = target_id
  903. def get_opcode(self):
  904. """Gets the opcode for this state instruction."""
  905. return "CD"
  906. def get_arguments(self):
  907. """Gets this state instruction's argument list."""
  908. return [self.source_id, self.key, self.target_id]
  909. class DeleteNodeInstruction(StateInstruction):
  910. """An instruction that deletes a node."""
  911. def __init__(self, node_id):
  912. StateInstruction.__init__(self)
  913. self.node_id = node_id
  914. def has_result(self):
  915. """Tells if this instruction computes a result."""
  916. return False
  917. def get_opcode(self):
  918. """Gets the opcode for this state instruction."""
  919. return "DN"
  920. def get_arguments(self):
  921. """Gets this state instruction's argument list."""
  922. return [self.node_id]
  923. class DeleteEdgeInstruction(StateInstruction):
  924. """An instruction that deletes an edge."""
  925. def __init__(self, edge_id):
  926. StateInstruction.__init__(self)
  927. self.edge_id = edge_id
  928. def has_result(self):
  929. """Tells if this instruction computes a result."""
  930. return False
  931. def get_opcode(self):
  932. """Gets the opcode for this state instruction."""
  933. return "DE"
  934. def get_arguments(self):
  935. """Gets this state instruction's argument list."""
  936. return [self.edge_id]
  937. def create_block(*statements):
  938. """Creates a block-statement from the given list of statements."""
  939. length = len(statements)
  940. if length == 0:
  941. return EmptyInstruction()
  942. elif length == 1:
  943. return statements[0]
  944. else:
  945. return CompoundInstruction(
  946. statements[0],
  947. create_block(*statements[1:]))
  948. def create_jit_call(target, named_arguments, kwargs):
  949. """Creates a call that abides by the JIT's calling convention."""
  950. # A JIT call looks like this:
  951. #
  952. # target = ...
  953. # arg_dict = { ... }
  954. # arg_dict.update(kwargs)
  955. # result, = yield [("CALL_KWARGS", [target, arg_dict])]
  956. results = []
  957. if target.has_definition():
  958. target_tmp = StoreLocalInstruction(None, target)
  959. results.append(target_tmp)
  960. target = target_tmp.create_load()
  961. arg_dict = StoreLocalInstruction(
  962. None,
  963. DictionaryLiteralInstruction(
  964. [(LiteralInstruction(key), val) for key, val in named_arguments]))
  965. results.append(arg_dict)
  966. results.append(
  967. CallInstruction(
  968. LoadMemberInstruction(arg_dict.create_load(), 'update'),
  969. [kwargs]))
  970. return CompoundInstruction(
  971. create_block(*results),
  972. RunGeneratorFunctionInstruction(
  973. target, arg_dict.create_load()))
  974. def with_debug_info_trace(instruction, debug_info, function_name):
  975. """Prepends the given instruction with a tracing instruction that prints
  976. the given debug information and function name."""
  977. if debug_info is None and function_name is None:
  978. return instruction
  979. else:
  980. if debug_info is None:
  981. debug_info = 'unknown location '
  982. if function_name is None:
  983. function_name = 'unknown function'
  984. return create_block(
  985. PrintInstruction(
  986. LiteralInstruction('TRACE: %s(%s, JIT)' % (debug_info, function_name))),
  987. instruction)
  988. def map_and_simplify(function, instruction):
  989. """Applies the given mapping function to every instruction in the tree
  990. that has the given instruction as root, and simplifies it on-the-fly.
  991. This is at least as powerful as first mapping and then simplifying, as
  992. maps and simplifications are interspersed."""
  993. # Let's just agree to disagree on map vs list comprehensions, pylint.
  994. # pylint: disable=I0011,W0141
  995. return function(
  996. instruction.create(
  997. map(map_and_simplify, instruction.get_children()))).simplify_node()
  998. if __name__ == "__main__":
  999. example_tree = SelectInstruction(
  1000. LiteralInstruction(True),
  1001. LoopInstruction(
  1002. CompoundInstruction(
  1003. BreakInstruction(),
  1004. CompoundInstruction(
  1005. EmptyInstruction(),
  1006. ContinueInstruction()
  1007. )
  1008. )
  1009. ),
  1010. ReturnInstruction(
  1011. EmptyInstruction()))
  1012. print(example_tree.simplify())