Changeset 298


Ignore:
Timestamp:
Sep 10, 2009, 3:41:52 PM (10 years ago)
Author:
eamiri
Message:

Transformation to SSA added, plus
minor modification to some other classes.
Class simple_op is added that abstracts RHS of an assignment.
An incomplete copy propagation is written.

Location:
proto/parabix2/Compiler
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • proto/parabix2/Compiler/bitexpr.py

    r297 r298  
    8383        self.LHS = var
    8484        self.RHS = expr
    85     def show(self): return 'Assign(%s, %s)' % (self.LHS.show(), self.RHS.show())
     85    def show(self): return '%s = %s' % (self.LHS, self.RHS.show())
    8686
    8787#
  • proto/parabix2/Compiler/bitstream_compiler.py

    r297 r298  
    66#  Code Generation
    77#
     8
     9Nop = 'nop'
     10Andc = 'simd_andc'
     11And = 'simd_and'
     12Or = 'simd_or'
     13Xor = 'simd_xor'
     14Not = 'not'
     15Add = 'simd_add'
     16Sub = 'simd_sub'
     17
     18AllOne = 'allone'
     19AllZero = 'allzero'
     20
     21class simple_op:
     22        def __init__(self, *arg):
     23                self.op = arg[0]
     24                self.first = arg[1]
     25                if len(arg) > 2:
     26                        self.second = arg[2]
     27                else:
     28                        assert(self.op==Nop)
     29                        self.second = None
     30
     31        def show(self):
     32                if self.op == Nop:
     33                        return "%s\n"%self.first
     34                else:
     35                        return "%s(%s, %s)\n"%(self.op, self.first, self.second)
     36        def update_var(self, old, new):
     37                if self.first == old:
     38                        self.first = new
     39                if self.second == old:
     40                        self.second = new
     41
    842class CodeGenObject:
    943    def __init__(self, predeclared):
     
    1347        self.common_expression_map = {}
    1448        for sym in predeclared: self.common_expression_map[sym] = sym
    15     def add_assignment(self, varname, expr):
    16         self.common_expression_map[expr] = varname
    17         self.generated_code.append('  %s = %s;\n' % (varname, expr))
     49    def add_stmt(self, varname, expr):
     50        self.common_expression_map[expr.show()] = varname
     51        self.generated_code.append(bitexpr.BitAssign(varname, expr))
    1852    def expr_string_to_variable(self, expr_string):
    19         if self.common_expression_map.has_key(expr_string):
    20             return self.common_expression_map[expr_string]
     53        if self.common_expression_map.has_key(expr_string.show()):
     54            return self.common_expression_map[expr_string.show()]
    2155        else:
    2256            self.gensym_counter += 1
    2357            sym = self.gensym_template % self.gensym_counter
    24             self.add_assignment(sym, expr_string)
     58            self.add_stmt(sym, expr_string)
    2559            return sym
    26     def showcode(self):
     60    def showcode(self, line_no = False):
    2761        s = ''
    28         for stmt in self.generated_code: s += stmt
     62        for index, stmt in enumerate(self.generated_code):
     63                if line_no:
     64                        s+= "%i %s"%(index, stmt.show())
     65                else:
     66                        s += stmt.show()
    2967        return s
    3068
    31 
     69    def get_code(self):
     70        return self.generated_code
    3271
    3372def expr2simd(genobj, expr):
     
    3574       using code generator object genobj.
    3675    """
    37     if isinstance(expr, bitexpr.TrueLiteral): return 'simd_const_1(1)'
    38     elif isinstance(expr, bitexpr.FalseLiteral): return 'simd_const_1(0)'
    39     elif isinstance(expr, bitexpr.Var): return expr.varname
     76    if isinstance(expr, bitexpr.TrueLiteral): return simple_op(Nop, AllOne)
     77    elif isinstance(expr, bitexpr.FalseLiteral): return simple_op(Nop, AllZero)
     78    elif isinstance(expr, bitexpr.Var): return simple_op(Nop, expr.varname)
    4079    elif isinstance(expr, bitexpr.Not):
    4180       e = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand))
    42        return 'simd_andc(simd_const_1(1), %s)' % (e)
     81       return simple_op(Andc, AllOne, e)
    4382    elif isinstance(expr, bitexpr.Or):
    4483       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
    4584       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
    46        return 'simd_or(%s, %s)' % (e1, e2)
     85       return simple_op(Or, e1, e2)
    4786    elif isinstance(expr, bitexpr.Xor):
    4887       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
    4988       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
    50        return 'simd_xor(%s, %s)' % (e1, e2)
     89       return simple_op(Xor, e1, e2)
    5190    elif isinstance(expr, bitexpr.And):
    5291       if isinstance(expr.operand1, bitexpr.Not):
    5392           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1.operand))
    5493           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
    55            return 'simd_andc(%s, %s)' % (e2, e1)
     94           return simple_op(Andc, e2, e1)
    5695       elif isinstance(expr.operand2, bitexpr.Not):
    5796           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
    5897           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2.operand))
    59            return 'simd_andc(%s, %s)' % (e1, e2)
     98           return simple_op(Andc, e1, e2)
    6099       else:
    61100           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
    62101           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
    63            return 'simd_and(%s, %s)' % (e1, e2)
     102           return simple_op(And, e1, e2)
    64103    elif isinstance(expr, bitexpr.Sel):
    65104       sel = genobj.expr_string_to_variable(expr2simd(genobj, expr.sel))
    66105       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.true_branch))
    67106       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.false_branch))
    68        return 'simd_if(%s, %s, %s)' %(sel, e1, e2)
     107       return None
     108       #return 'simd_if(%s, %s, %s)' %(sel, e1, e2)
     109       ## TODO; Do something for this. It should be removed
    69110    elif isinstance(expr, bitexpr.Add):
    70111       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
    71112       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
    72        return 'adc(%s, %s)' % (e1, e2)
     113       return simple_op(Add, e1, e2)
    73114    elif isinstance(expr, bitexpr.Sub):
    74115       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
    75116       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
    76        return 'sbb(%s, %s)' % (e1, e2)
    77 
     117       return simple_op(Sub, e1, e2)
    78118
    79119def pybit_codegen(cgo, stmts):
    80120        for s in stmts:
    81121                e = expr2simd(cgo, s.RHS)
    82                 cgo.add_assignment(s.LHS, e)
     122                cgo.add_stmt(s.LHS, e)
     123
     124def gen_sym_table(code):
     125        """Generate a simple symbol table for a three address code
     126           each entry is of this form: var_name:[[defs][uses]]
     127        """
     128        table = {}
     129        for index, stmt in enumerate(code):
     130                if stmt.LHS in table:
     131                        table[stmt.LHS][0].append(index)
     132                else:
     133                        table[stmt.LHS] = [[index],[]]
     134               
     135                if stmt.RHS.first in table:
     136                        table[stmt.RHS.first][1].append(index)
     137                else:
     138                        table[stmt.RHS.first] = [[], [index]]
     139               
     140                if stmt.RHS.second is None or stmt.RHS.second==stmt.RHS.first:
     141                        continue
     142               
     143                if stmt.RHS.second in table:
     144                        table[stmt.RHS.second][1].append(index)
     145                else:
     146                        table[stmt.RHS.second] = [[], [index]]
     147
     148        return table
     149
     150
     151def pairs(lst):
     152        if lst == []:
     153                return []
     154        return zip(lst,lst[1:]+[lst[0]])
     155
     156
     157def make_SSA(code, st):
     158        total_lines = len(code)
     159        for var in st:
     160                st[var][0].append(total_lines)
     161                st[var][1].append(total_lines)
     162       
     163        for var in st:
     164                use_index = 0
     165                def_index = 1
     166                for current, next in pairs(st[var][0])[1:-1]:
     167                        code[current].LHS = "%s_%i"%(var, current)
     168                        uline = st[var][1][use_index]
     169                        while uline <= next and uline < total_lines:
     170                                if uline > current:
     171                                        code[uline].RHS.update_var(var, "%s_%i"%(var, current))
     172                                use_index += 1
     173                                uline = st[var][1][use_index]
     174
     175
     176
     177
     178def copy_propagation(code, st):
     179        """Assumes the code is in SSA form"""
     180        """TODO: THIS IS NOT COMPLETE"""
     181        dic = {}
     182        for stmt in code:
     183                if stmt.RHS.op == Nop:
     184                        dic[stmt.LHS] = stmt.RHS.first
     185       
     186        for i in dic:
     187                if not dic[i] in dic:
     188                        continue
     189                while dic[i] in dic:
     190                        i = dic[i]
     191                dic[i] = i
     192
     193        return dic
     194
     195
     196
    83197
    84198if __name__ == '__main__':
     
    86200        Ref2 = bitutil.Advance(lex.RefStart &~ CtCDPI_mask)
    87201        NumRef2 = Ref2 & lex.Hash
    88         GenRef2 = Ref2 &~ lex.Hash
     202        GenRef2 = Ref2 & ~lex.Hash
    89203        NumRef3 = bitutil.Advance(NumRef2)
    90204        HexRef3 = NumRef3 & lex.x
     
    110224""")
    111225        s=s.body[0].body
     226
    112227        c=CodeGenObject([])
     228
    113229        pybit_codegen(c, py2bitexpr.translate_stmts(s))
    114         print c.showcode()
     230        #print c.showcode(True)
     231        code = c.generated_code
     232        make_SSA(code, gen_sym_table(code))
     233        print c.showcode(True)
Note: See TracChangeset for help on using the changeset viewer.