Changeset 323 for proto/parabix2


Ignore:
Timestamp:
Oct 26, 2009, 3:35:17 PM (10 years ago)
Author:
eamiri
Message:

dead code elimination introduced.
backward propagation of values of optimized(reduced) variables is added.

Location:
proto/parabix2/Compiler
Files:
3 edited

Legend:

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

    r322 r323  
    130130    def show(self):
    131131            if self.LHS is None:
    132                 return "%s"%self.RHS.show()
     132                return "%s"%self.RHS.show_C()
    133133            else:
    134                 return '%s = %s' % (self.LHS.show(), self.RHS.show())
     134                return '%s = %s' % (self.LHS.show_C(), self.RHS.show_C())
    135135
    136136class StmtList(BitStmt):
  • proto/parabix2/Compiler/bitstream_compiler.py

    r322 r323  
    172172            return expr
    173173    elif isinstance(expr, bitexpr.Add):
    174         return expr
     174        if isinstance(expr.operand1, bitexpr.FalseLiteral) and isinstance(expr.operand1, bitexpr.FalseLiteral):
     175            return bitexpr.FalseLiteral()
     176        else:
     177            return expr
    175178    elif isinstance(expr, bitexpr.Sub):
    176179        return expr
     
    202205                                table[var] = [[], [index]]
    203206        return table
    204 
    205 
    206207
    207208
     
    306307                        s+= "%i %s%s;\n"%(index, " "*indent,stmt.show())
    307308                else:
    308                         if not isinstance(stmt, bitexpr.BitAssign):
    309                             print "~~~~", index, stmt
     309                        #if not isinstance(stmt, bitexpr.BitAssign):
     310                        #   print "~~~~", index, stmt
    310311                        s += " "*indent + stmt.show() + ";\n"
    311312        return s
     
    314315        return self.code
    315316
     317    def calc_implications(self, assumptions):
     318        changed = False
     319        notchecked = [x for x in assumptions]
     320        lhs = [x.LHS.varname for x in self.code]
     321        while True:
     322            if len(notchecked) == 0:
     323                break
     324            var = notchecked.pop(0)
     325            if var in lhs:
     326                index = lhs.index(var)
     327                s = self.code[index]
     328            else:
     329                continue
     330            if var in assumptions:
     331                if isinstance(assumptions[s.LHS.varname], bitexpr.FalseLiteral):
     332                    if isinstance(s.RHS, bitexpr.Not):
     333                        assumptions[s.RHS.operand.varname] = bitexpr.TrueLiteral()
     334                        notchecked.append(s.RHS.operand.varname)
     335                    elif isinstance(s.RHS, bitexpr.Var):
     336                        assumptions[s.RHS.varname] = bitexpr.FalseLiteral()
     337                        notchecked.append(s.RHS.operand.varname)
     338                    elif isinstance(s.RHS, bitexpr.Or):
     339                        assumptions[s.RHS.operand1.varname] = bitexpr.FalseLiteral()
     340                        assumptions[s.RHS.operand2.varname] = bitexpr.FalseLiteral()
     341                        notchecked.append(s.RHS.operand1.varname)
     342                        notchecked.append(s.RHS.operand2.varname)
     343                    elif isinstance(s.RHS, bitexpr.Xor):
     344                        pass
     345                if isinstance(assumptions[s.LHS.varname], bitexpr.TrueLiteral):
     346                    if isinstance(s.RHS, bitexpr.Not):
     347                        assumptions[s.RHS.operand.varname] = bitexpr.FalseLiteral()
     348                        notchecked.append(s.RHS.operand.varname)
     349                    elif isinstance(s.RHS, bitexpr.Var):
     350                        assumptions[s.RHS.varname] = bitexpr.TrueLiteral()
     351                        notchecked.append(s.RHS.operand.varname)
     352                    elif isinstance(s.RHS, bitexpr.And):
     353                        assumptions[s.RHS.operand1.varname] = bitexpr.TrueLiteral()
     354                        assumptions[s.RHS.operand2.varname] = bitexpr.TrueLiteral()
     355                        notchecked.append(s.RHS.operand1.varname)
     356                        notchecked.append(s.RHS.operand2.varname)
     357                    elif isinstance(s.RHS, bitexpr.Andc):
     358                        if isinstance(s.RHS.operand1, bitexpr.TrueLiteral):
     359                            assumptions[s.RHS.operand2.varname] = bitexpr.FalseLiteral()
     360                            notchecked.append(s.RHS.operand2.varname)
     361                        else:
     362                            assumptions[s.RHS.operand1.varname] = bitexpr.TrueLiteral()
     363                            assumptions[s.RHS.operand2.varname] = bitexpr.FalseLiteral()
     364                            notchecked.append(s.RHS.operand1.varname)
     365                            notchecked.append(s.RHS.operand2.varname)
     366        return assumptions
    316367    def propagate_constant(self, previous):
    317368        changed = False
    318369        fixed = previous
     370        #print fixed
    319371        for s in self.code:
    320             #print s.RHS.__class__
     372            #if len(self.code)==1: print s, s.LHS.varname, s.RHS
     373
    321374            if isinstance(s.RHS, bitexpr.FalseLiteral):
    322375                fixed[s.LHS.varname] = bitexpr.FalseLiteral()
     
    342395                changed = True
    343396
    344         #for i in fixed:
    345         #   print i, fixed[i]
    346397        return fixed, changed
    347398
     
    390441    py2bitexpr.simplify_tree(tree)
    391442
     443   
     444    livelist = ['u16hi[0]','u16hi[1]','u16hi[2]','u16hi[3]','u16hi[4]','u16hi[5]','u16hi[6]','u16hi[7]']
     445    livelist += ['u16lo[0]','u16lo[1]','u16lo[2]','u16lo[3]','u16lo[4]','u16lo[5]','u16lo[6]','u16lo[7]', 'delmask', 'u8.error', 'error_mask']
     446    py2bitexpr.eliminate_dead_code(tree, set(livelist))
     447   
    392448    #Pass 9
    393449    s = py2bitexpr.unwind(tree)
     
    399455        s=r"""def u8u16(u8, u8bit):
    400456        u8.unibyte = (~u8bit[0]);
    401         while x:
    402                 x = bitutil.Advance(x)
    403                 y |= x
    404         optimize(u8bit[0], allzero)
     457        optimize(u8.unibyte, allone)
    405458        u8.prefix = (u8bit[0] & u8bit[1]);
    406459        u8.prefix2 = (u8.prefix &~ u8bit[2]);
    407460        temp1 = (u8bit[2] &~ u8bit[3]);
    408461        u8.prefix3 = (u8.prefix & temp1);
    409         #optimize(u8.prefix3, allzero)
    410462        temp2 = (u8bit[2] & u8bit[3]);
    411463        u8.prefix4 = (u8.prefix & temp2);
    412         #optimize(u8.prefix4, allzero)
    413         u8.suffix = (u8bit[0] &~ u8bit[1]);
     464        u8.suffix = (u8bit[0] &~ u8bit[1]);
     465        maxtwo = u8.prefix2 | u8.unibyte | u8.suffix
     466        optimize(maxtwo, allone)
    414467        temp3 = (u8bit[2] | u8bit[3]);
    415468        temp4 = (u8.prefix &~ temp3);
     
    436489        u8.x90_xBF = (u8.suffix & temp3);
    437490        u8.x80_x8F = (u8.suffix &~ temp3);
    438 
     491       
    439492        u8.scope22 = bitutil.Advance(u8.prefix2)
    440493        u8.scope32 = bitutil.Advance(u8.prefix3)
     
    442495        u8.scope42 = bitutil.Advance(u8.prefix4)
    443496        u8.scope43 = bitutil.Advance(u8.scope42)
    444         #optimize(u8.scope43, allzero)
    445497        u8.scope44 = bitutil.Advance(u8.scope43)
    446498        u8lastscope = u8.scope22 | u8.scope33 | u8.scope44
    447499        u8anyscope = u8lastscope | u8.scope32 | u8.scope42 | u8.scope43
    448 
     500       
    449501        # C0-C1 and F5-FF are illegal
    450502        error_mask = u8.badprefix
    451 
     503       
    452504        error_mask |= bitutil.Advance(u8.xE0) & u8.x80_x9F
    453505        error_mask |= bitutil.Advance(u8.xED) & u8.xA0_xBF
    454506        error_mask |= bitutil.Advance(u8.xF0) & u8.x80_x8F
    455507        error_mask |= bitutil.Advance(u8.xF4) & u8.x90_xBF
    456 
     508       
    457509        error_mask |= u8anyscope ^ u8.suffix
    458510        u8.error = error_mask
    459 
     511       
    460512        u8lastscope = u8.scope22 | u8.scope33 | u8.scope44
    461513        u8lastbyte = u8.unibyte | u8lastscope
    462         #optimize(u8lastbyte, allzero)
    463514        u16lo[2] = u8lastbyte & u8bit[2]
    464515        u16lo[3] = u8lastbyte & u8bit[3]
     
    469520        u16lo[1] = (u8.unibyte & u8bit[1]) | (u8lastscope & bitutil.Advance(u8bit[7]))
    470521        u16lo[0] = u8lastscope & bitutil.Advance(u8bit[6])
    471 
     522       
    472523        u16hi[5] = u8lastscope & bitutil.Advance(u8bit[3])
    473524        u16hi[6] = u8lastscope & bitutil.Advance(u8bit[4])
     
    480531
    481532        u8surrogate = u8.scope43 | u8.scope44
    482         #optimize(u8surrogate, allzero)
    483533        u16hi[0] = u16hi[0] | u8surrogate       
    484534        u16hi[1] = u16hi[1] | u8surrogate       
     
    506556        u16lo[7] = u16lo[7] | (u8.scope43 & u8bit[3])
    507557
    508         delmask = u8.prefix | u8.scope32 | u8.scope42
    509 """
     558        delmask = u8.prefix | u8.scope32 | u8.scope42"""
    510559        print generate_code(s)
    511560
  • proto/parabix2/Compiler/py2bitexpr.py

    r322 r323  
    1919
    2020#############################################################################################
    21 ## Translation to bitExpr classes
     21## Translation to bitExpr classes --- Pass 2
    2222#############################################################################################
    2323
     
    124124               
    125125#############################################################################################
    126 ## Conversion to SSA form
     126## Conversion to SSA form --- Pass 3
    127127#############################################################################################
    128128
     
    231231
    232232#################################################################################################################
    233 ## Breaking the code into basic blocks depending on where optimize pragma appears
     233## Breaking the code into basic blocks depending on where optimize pragma appears --- Pass 4
    234234#################################################################################################################
    235235def break_to_segs(s, breaks):
     
    241241            segs.append(next)
    242242    return segs
    243    
     243
    244244def partition2bb(s):
    245245    basicblocks = []
    246246    exprs = []
    247247    lineno = []
    248    
     248
    249249    for line, loc in enumerate(s):
    250250        if isinstance(loc, bitexpr.Reduce):
     
    263263
    264264#################################################################################################################
    265 ## Generating declarations for variables. This pass is based on the syntax of C programming language
     265## Generating declarations for variables. This pass is based on the syntax of C programming language --- Pass 5
    266266#################################################################################################################
    267267def get_vars(code):
     
    313313    res['array'].update(temp['array'])
    314314
    315    
     315
    316316    res['struct'] = first['struct']
    317317    temp = dict({'struct':copy.copy(second['struct'])})
     
    357357
    358358#################################################################################################################
    359 ## Converting to condition-tree form
     359## Converting to condition-tree form --- Pass 6
    360360#################################################################################################################
    361361def construct_tree(all_code, exprs):
     
    409409
    410410#################################################################################################################
    411 ## This class replaces all occurences of a reduced variable to its value
     411## This class replaces all occurences of a reduced variable to its value --- Pass 7
    412412#################################################################################################################
    413413class Reducer:
     
    466466        return [first_cond, head, self.apply_all_opt(optimized_code, copy.copy(exp)), self.apply_all_opt(all_code, exp)]
    467467#################################################################################################################
    468 ## Simplifying conditions-tree by applying various optimizations like: constant and copy propagation.
    469 ## method prune is supposed to remove unreachable branches but it is incomplete
     468## Simplifying conditions-tree by applying various optimizations like: constant and copy propagation. --- Pass 8
     469## method prune is supposed to remove unreachable branches but it is incomplete 
    470470#################################################################################################################
    471471def prune(fixed, tree):
     
    512512
    513513def simplify_tree(tree, fixed = {}):
     514    assumptions = {}
    514515    fixed.update(tree[1].simplify(fixed))
     516   
    515517    if tree[0] is None:
    516518        return
    517519    else:
    518520        #self.prune(fixed, tree)
     521        if tree[0].replace == 'allzero':
     522            assumptions[tree[0].target] = bitexpr.FalseLiteral()
     523        else:
     524            assumptions[tree[0].target] = bitexpr.TrueLiteral()
     525
     526        assumptions = tree[1].calc_implications(assumptions)
     527        #print "~~~~~~", assumptions
     528        fixed_a = copy.copy(fixed)
     529        fixed_a.update(assumptions)
     530        #print "~~~~~~", fixed_a
     531
     532        simplify_tree(tree[2], fixed_a)
    519533        for branch in tree[2:]:
    520534            simplify_tree(branch, copy.copy(fixed))
    521535
    522 
    523 #################################################################################################################
    524 ## Generates C code given conditions-tree, by a recursive traversal of the tree
     536#################################################################################################################
     537## Dead Code Elimination
     538#################################################################################################################
     539
     540def check_loc(loc, must_liv):
     541    if loc.LHS.varname in must_liv:
     542        if isinstance(loc.RHS, bitexpr.Not):
     543            return set([loc.RHS.operand.varname]), False
     544        elif isinstance(loc.RHS, bitexpr.Var):
     545            return set([loc.RHS.varname]), False
     546        elif isinstance(loc.RHS, bitexpr.FalseLiteral):
     547            return set([]), False
     548        elif isinstance(loc.RHS, bitexpr.TrueLiteral):
     549            return set([]), False
     550        else:
     551            return set([loc.RHS.operand1.varname, loc.RHS.operand2.varname]), False
     552    else:
     553        return set([]), True
     554
     555
     556def remove_copies(bb):
     557    """removes all copy statements e.g. var1 = var2"""
     558    lhs = [x.LHS.varname for x in bb.code]
     559    rhs = [(line, loc.RHS.varname) for line, loc in enumerate(bb.code) if isinstance(loc.RHS, bitexpr.Var)]
     560    for i in rhs:
     561        if i[1] in lhs:
     562            line = lhs.index(i[1])
     563            bb.code[i[0]].RHS = bb.code[line].RHS
     564
     565
     566def remove_dead(bb, must_live):
     567    remove_copies(bb)
     568    my_alives = set([])
     569    dead = []
     570    for line, loc in reversed(list(enumerate(bb.code))):
     571        new_lives, removable = check_loc(loc, my_alives.union(must_live))
     572        if removable:
     573            dead.append(line)
     574        else:
     575            my_alives = my_alives.union(new_lives)
     576
     577    for i in dead:
     578        del bb.code[i]
     579
     580    return my_alives
     581
     582
     583def eliminate_dead_code(tree, must_live):
     584    if not tree[0] is None:
     585        new_alives = set([tree[0].target])
     586        for branch in tree[2:]:
     587            new_alives = new_alives.union(eliminate_dead_code(branch, must_live))
     588        must_live = must_live.union(new_alives)
     589       
     590    #print len(tree[1].code), must_live
     591   
     592    return remove_dead(tree[1], must_live)
     593    #print len(tree[1].code)
     594    #print "~~~~~~~~~~~~~~~~~"
     595    #print his_alives
     596    #print
     597    #print
     598
     599
     600#################################################################################################################
     601## Generates C code given conditions-tree, by a recursive traversal of the tree --- Pass 9
    525602#################################################################################################################
    526603def generate_if_stmt(expr, indent):
     
    528605    replace = expr.replace
    529606    if replace == "allzero":
    530         return "\n%sif (bitblock_has_bit(%s))  {\n"%(" "*indent, target)
     607        return "\n%sif (!bitblock_has_bit(%s))  {\n"%(" "*indent, target)
    531608    elif replace == "allone":
    532         return "\n%sif (bitblock_has_bit(simd_not(%s))) {\n"%(" "*indent, target)
     609        return "\n%sif (!bitblock_has_bit(simd_not(%s))) {\n"%(" "*indent, target)
    533610    else:
    534611        assert (1==0)
     
    563640            s+=unwind(tree[4], tree[1], indent)
    564641            return s
     642
Note: See TracChangeset for help on using the changeset viewer.