annotate python/ppci/transform.py @ 306:b145f8e6050b

Start on c3 rewrite
author Windel Bouwman
date Mon, 09 Dec 2013 19:00:21 +0100
parents 6753763d3bec
children 56e6ff84f646
rev   line source
240
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
1 """
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
2 Transformation to optimize IR-code
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
3 """
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
4
253
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
5 import logging
301
6753763d3bec merge codegen into ppci package
Windel Bouwman
parents: 300
diff changeset
6 from . import ir
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
7 # Standard passes:
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
8
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
9 class FunctionPass:
255
7416c923a02a Added more logging
Windel Bouwman
parents: 253
diff changeset
10 def __init__(self):
7416c923a02a Added more logging
Windel Bouwman
parents: 253
diff changeset
11 self.logger = logging.getLogger('optimize')
7416c923a02a Added more logging
Windel Bouwman
parents: 253
diff changeset
12
253
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
13 def run(self, ir):
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
14 """ Main entry point for the pass """
255
7416c923a02a Added more logging
Windel Bouwman
parents: 253
diff changeset
15 self.logger.info('Running pass {}'.format(type(self)))
7416c923a02a Added more logging
Windel Bouwman
parents: 253
diff changeset
16 ir.check()
253
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
17 self.prepare()
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
18 for f in ir.Functions:
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
19 self.onFunction(f)
255
7416c923a02a Added more logging
Windel Bouwman
parents: 253
diff changeset
20 ir.check()
253
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
21
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
22 def onFunction(self, f):
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
23 """ Override this virtual method """
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
24 raise NotImplementedError()
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
25
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
26 def prepare(self):
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
27 pass
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
28
240
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
29
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
30 class BasicBlockPass(FunctionPass):
240
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
31 def onFunction(self, f):
274
ea93e0a7a31e Move docs
Windel Bouwman
parents: 261
diff changeset
32 for bb in f.Blocks:
240
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
33 self.onBasicBlock(bb)
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
34
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
35 def onBasicBlock(self, bb):
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
36 """ Override this virtual method """
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
37 raise NotImplementedError()
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
38
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
39
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
40 class InstructionPass(BasicBlockPass):
240
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
41 def onBasicBlock(self, bb):
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
42 for ins in iter(bb.Instructions):
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
43 self.onInstruction(ins)
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
44
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
45 def onInstruction(self, ins):
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
46 """ Override this virtual method """
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
47 raise NotImplementedError()
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
48
280
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
49
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
50 class BasePass(BasicBlockPass):
255
7416c923a02a Added more logging
Windel Bouwman
parents: 253
diff changeset
51 def onBasicBlock(self, bb):
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
52 pass
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
53
280
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
54
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
55 # Usefull transforms:
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
56 class ConstantFolder(BasePass):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
57 def __init__(self):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
58 super().__init__()
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
59 self.ops = {}
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
60 self.ops['+'] = lambda x, y: x + y
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
61 self.ops['-'] = lambda x, y: x - y
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
62 self.ops['*'] = lambda x, y: x * y
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
63 self.ops['<<'] = lambda x, y: x << y
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
64
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
65 def postExpr(self, expr):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
66 if type(i) is BinaryOperator and i.operation in self.ops.keys() and type(i.a) is Const and type(i.b) is Const:
280
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
67 vr = self.ops[i.operation](i.a.value, i.b.value)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
68 return Const(vr)
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
69 else:
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 274
diff changeset
70 return expr
237
81752b0f85a5 Added burn led test program
Windel Bouwman
parents: 235
diff changeset
71
81752b0f85a5 Added burn led test program
Windel Bouwman
parents: 235
diff changeset
72
174
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
73 class DeadCodeDeleter(BasicBlockPass):
252
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
74 def onBasicBlock(self, bb):
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
75 def instructionUsed(ins):
253
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
76 if not type(ins) in [ImmLoad, BinaryOperator]:
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
77 return True
252
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
78 if len(ins.defs) == 0:
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
79 # In case this instruction does not define any
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
80 # variables, assume it is usefull.
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
81 return True
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
82 return any(d.Used for d in ins.defs)
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
83
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
84 change = True
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
85 while change:
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
86 change = False
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
87 for i in bb.Instructions:
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
88 if instructionUsed(i):
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
89 continue
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
90 bb.removeInstruction(i)
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
91 change = True
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
92
239
63bb40758066 added check
Windel Bouwman
parents: 237
diff changeset
93
252
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
94 class CommonSubexpressionElimination(BasicBlockPass):
239
63bb40758066 added check
Windel Bouwman
parents: 237
diff changeset
95 def onBasicBlock(self, bb):
63bb40758066 added check
Windel Bouwman
parents: 237
diff changeset
96 constMap = {}
252
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
97 to_remove = []
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
98 for i in bb.Instructions:
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
99 if isinstance(i, ImmLoad):
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
100 if i.value in constMap:
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
101 t_new = constMap[i.value]
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
102 t_old = i.target
253
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
103 logging.debug('Replacing {} with {}'.format(t_old, t_new))
261
444b9df2ed99 try to split up code generation
Windel Bouwman
parents: 255
diff changeset
104 t_old.replaceby(t_new)
252
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
105 to_remove.append(i)
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
106 else:
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
107 constMap[i.value] = i.target
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
108 elif isinstance(i, BinaryOperator):
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
109 k = (i.value1, i.operation, i.value2)
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
110 if k in constMap:
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
111 t_old = i.result
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
112 t_new = constMap[k]
253
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
113 logging.debug('Replacing {} with {}'.format(t_old, t_new))
261
444b9df2ed99 try to split up code generation
Windel Bouwman
parents: 255
diff changeset
114 t_old.replaceby(t_new)
252
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
115 to_remove.append(i)
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
116 else:
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
117 constMap[k] = i.result
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
118 for i in to_remove:
253
74c6a20302d5 Added better logging
Windel Bouwman
parents: 252
diff changeset
119 logging.debug('removing {}'.format(i))
252
c4370696ccc7 added optimize function
Windel Bouwman
parents: 240
diff changeset
120 bb.removeInstruction(i)
240
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
121
6259856841a0 Remove project
Windel Bouwman
parents: 239
diff changeset
122
177
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
123 class CleanPass(FunctionPass):
219
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
124 def onFunction(self, f):
280
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
125 removeEmptyBasicBlocks(f)
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
126
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
127
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
128 def removeEmptyBlocks(f):
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
129 """ Remove empty basic blocks from function. """
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
130 # If a block only contains a branch, it can be removed:
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
131 empty = lambda b: type(b.FirstInstruction) is ir.Jump
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
132 empty_blocks = list(filter(empty, f.Blocks))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
133 for b in empty_blocks:
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
134 # Update predecessors
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
135 preds = b.Predecessors
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
136 if b not in preds + [f.entry]:
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
137 # Do not remove if preceeded by itself
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
138 tgt = b.LastInstruction.target
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
139 for pred in preds:
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
140 pred.LastInstruction.changeTarget(b, tgt)
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
141 logging.debug('Removing empty block: {}'.format(b))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
142 f.removeBlock(b)