annotate python/codegen/canon.py @ 300:158068af716c

yafm
author Windel Bouwman
date Tue, 03 Dec 2013 18:00:22 +0100
parents 9417caea2eb3
children
rev   line source
275
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
1 import ir
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
2 from itertools import chain
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
3
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
4 def make(function, frame):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
5 """
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
6 Create canonicalized version of the IR-code. This means:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
7 - Calls out of expressions.
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
8 - Other things?
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
9 """
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
10 # Change the tree. This modifies the IR-tree!
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
11 # Move all parameters into registers
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
12 parmoves = []
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
13 for p in function.arguments:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
14 pt = newTemp()
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
15 frame.parMap[p] = pt
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
16 parmoves.append(ir.Move(pt, frame.argLoc(p.num)))
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
17 function.entry.instructions = parmoves + function.entry.instructions
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
18
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
19 for block in function.Blocks:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
20 for stmt in block.instructions:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
21 rewriteStmt(stmt, frame)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
22 linearize(block)
280
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
23 # TODO: schedule here?
275
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
24
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
25 # Visit all nodes with some function:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
26 # TODO: rewrite into visitor.
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
27
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
28 # Rewrite rewrites call instructions into Eseq instructions.
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
29
300
Windel Bouwman
parents: 296
diff changeset
30
275
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
31 def rewriteStmt(stmt, frame):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
32 if isinstance(stmt, ir.Jump):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
33 pass
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
34 elif isinstance(stmt, ir.CJump):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
35 stmt.a = rewriteExp(stmt.a, frame)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
36 stmt.b = rewriteExp(stmt.b, frame)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
37 elif isinstance(stmt, ir.Move):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
38 stmt.src = rewriteExp(stmt.src, frame)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
39 stmt.dst = rewriteExp(stmt.dst, frame)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
40 elif isinstance(stmt, ir.Terminator):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
41 pass
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
42 elif isinstance(stmt, ir.Exp):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
43 stmt.e = rewriteExp(stmt.e, frame)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
44 else:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
45 raise NotImplementedError('STMT NI: {}'.format(stmt))
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
46
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
47 newTemp = ir.NamedClassGenerator('canon_reg', ir.Temp).gen
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
48
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
49 def rewriteExp(exp, frame):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
50 if isinstance(exp, ir.Binop):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
51 exp.a = rewriteExp(exp.a, frame)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
52 exp.b = rewriteExp(exp.b, frame)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
53 return exp
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
54 elif isinstance(exp, ir.Const):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
55 return exp
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
56 elif isinstance(exp, ir.Temp):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
57 return exp
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
58 elif isinstance(exp, ir.Parameter):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
59 return frame.parMap[exp]
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
60 elif isinstance(exp, ir.LocalVariable):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
61 offset = frame.allocVar(exp)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 275
diff changeset
62 return ir.Add(frame.fp, ir.Const(offset))
275
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
63 elif isinstance(exp, ir.Mem):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
64 exp.e = rewriteExp(exp.e, frame)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
65 return exp
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
66 elif isinstance(exp, ir.Call):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
67 exp.arguments = [rewriteExp(p, frame) for p in exp.arguments]
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
68 # Rewrite call into eseq:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
69 t = newTemp()
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
70 return ir.Eseq(ir.Move(t, exp), t)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
71 else:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
72 raise NotImplementedError('NI: {}'.format(exp))
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
73
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
74 # The flatten functions pull out seq instructions to the sequence list.
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
75
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
76 def flattenExp(exp):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
77 if isinstance(exp, ir.Binop):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
78 exp.a, sa = flattenExp(exp.a)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
79 exp.b, sb = flattenExp(exp.b)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
80 return exp, sa + sb
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
81 elif isinstance(exp, ir.Temp):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
82 return exp, []
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
83 elif isinstance(exp, ir.Const):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
84 return exp, []
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
85 elif isinstance(exp, ir.Mem):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
86 exp.e, s = flattenExp(exp.e)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
87 return exp, s
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
88 elif isinstance(exp, ir.Eseq):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
89 s = flattenStmt(exp.stmt)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
90 exp.e, se = flattenExp(exp.e)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
91 return exp.e, s + se
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
92 elif isinstance(exp, ir.Call):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
93 sp = []
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
94 p = []
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
95 for p_, sp_ in (flattenExp(p) for p in exp.arguments):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
96 p.append(p_)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
97 sp.extend(sp_)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
98 exp.arguments = p
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
99 return exp, sp
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
100 else:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
101 raise NotImplementedError('NI: {}'.format(exp))
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
102
300
Windel Bouwman
parents: 296
diff changeset
103
275
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
104 def flattenStmt(stmt):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
105 if isinstance(stmt, ir.Jump):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
106 return [stmt]
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
107 elif isinstance(stmt, ir.CJump):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
108 stmt.a, sa = flattenExp(stmt.a)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
109 stmt.b, sb = flattenExp(stmt.b)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
110 return sa + sb + [stmt]
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
111 elif isinstance(stmt, ir.Move):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
112 stmt.dst, sd = flattenExp(stmt.dst)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
113 stmt.src, ss = flattenExp(stmt.src)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
114 return sd + ss + [stmt]
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
115 elif isinstance(stmt, ir.Terminator):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
116 return [stmt]
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
117 elif isinstance(stmt, ir.Exp):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
118 stmt.e, se = flattenExp(stmt.e)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
119 return se + [stmt]
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
120 else:
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
121 raise NotImplementedError('STMT NI: {}'.format(stmt))
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
122
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
123
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
124 def linearize(block):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
125 """
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
126 Move seq instructions to top and flatten these in an instruction list
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
127 """
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
128 i = list(flattenStmt(s) for s in block.instructions)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents:
diff changeset
129 block.instructions = list(chain.from_iterable(i))