Mercurial > lcfOS

comparison python/ppci/transform.py @ 300:158068af716c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
yafm
author Windel Bouwman
date Tue, 03 Dec 2013 18:00:22 +0100
parents python/transform.py@9417caea2eb3
children 6753763d3bec
comparison
equal deleted inserted replaced
299:674789d9ff37 300:158068af716c
1 """
2 Transformation to optimize IR-code
3 """
4
5 import logging
6 import ir
7 # Standard passes:
8
9 class FunctionPass:
10 def __init__(self):
11 self.logger = logging.getLogger('optimize')
12
13 def run(self, ir):
14 """ Main entry point for the pass """
15 self.logger.info('Running pass {}'.format(type(self)))
16 ir.check()
17 self.prepare()
18 for f in ir.Functions:
19 self.onFunction(f)
20 ir.check()
21
22 def onFunction(self, f):
23 """ Override this virtual method """
24 raise NotImplementedError()
25
26 def prepare(self):
27 pass
28
29
30 class BasicBlockPass(FunctionPass):
31 def onFunction(self, f):
32 for bb in f.Blocks:
33 self.onBasicBlock(bb)
34
35 def onBasicBlock(self, bb):
36 """ Override this virtual method """
37 raise NotImplementedError()
38
39
40 class InstructionPass(BasicBlockPass):
41 def onBasicBlock(self, bb):
42 for ins in iter(bb.Instructions):
43 self.onInstruction(ins)
44
45 def onInstruction(self, ins):
46 """ Override this virtual method """
47 raise NotImplementedError()
48
49
50 class BasePass(BasicBlockPass):
51 def onBasicBlock(self, bb):
52 pass
53
54
55 # Usefull transforms:
56 class ConstantFolder(BasePass):
57 def __init__(self):
58 super().__init__()
59 self.ops = {}
60 self.ops['+'] = lambda x, y: x + y
61 self.ops['-'] = lambda x, y: x - y
62 self.ops['*'] = lambda x, y: x * y
63 self.ops['<<'] = lambda x, y: x << y
64
65 def postExpr(self, expr):
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:
67 vr = self.ops[i.operation](i.a.value, i.b.value)
68 return Const(vr)
69 else:
70 return expr
71
72
73 class DeadCodeDeleter(BasicBlockPass):
74 def onBasicBlock(self, bb):
75 def instructionUsed(ins):
76 if not type(ins) in [ImmLoad, BinaryOperator]:
77 return True
78 if len(ins.defs) == 0:
79 # In case this instruction does not define any
80 # variables, assume it is usefull.
81 return True
82 return any(d.Used for d in ins.defs)
83
84 change = True
85 while change:
86 change = False
87 for i in bb.Instructions:
88 if instructionUsed(i):
89 continue
90 bb.removeInstruction(i)
91 change = True
92
93
94 class CommonSubexpressionElimination(BasicBlockPass):
95 def onBasicBlock(self, bb):
96 constMap = {}
97 to_remove = []
98 for i in bb.Instructions:
99 if isinstance(i, ImmLoad):
100 if i.value in constMap:
101 t_new = constMap[i.value]
102 t_old = i.target
103 logging.debug('Replacing {} with {}'.format(t_old, t_new))
104 t_old.replaceby(t_new)
105 to_remove.append(i)
106 else:
107 constMap[i.value] = i.target
108 elif isinstance(i, BinaryOperator):
109 k = (i.value1, i.operation, i.value2)
110 if k in constMap:
111 t_old = i.result
112 t_new = constMap[k]
113 logging.debug('Replacing {} with {}'.format(t_old, t_new))
114 t_old.replaceby(t_new)
115 to_remove.append(i)
116 else:
117 constMap[k] = i.result
118 for i in to_remove:
119 logging.debug('removing {}'.format(i))
120 bb.removeInstruction(i)
121
122
123 class CleanPass(FunctionPass):
124 def onFunction(self, f):
125 removeEmptyBasicBlocks(f)
126
127
128 def removeEmptyBlocks(f):
129 """ Remove empty basic blocks from function. """
130 # If a block only contains a branch, it can be removed:
131 empty = lambda b: type(b.FirstInstruction) is ir.Jump
132 empty_blocks = list(filter(empty, f.Blocks))
133 for b in empty_blocks:
134 # Update predecessors
135 preds = b.Predecessors
136 if b not in preds + [f.entry]:
137 # Do not remove if preceeded by itself
138 tgt = b.LastInstruction.target
139 for pred in preds:
140 pred.LastInstruction.changeTarget(b, tgt)
141 logging.debug('Removing empty block: {}'.format(b))
142 f.removeBlock(b)