Changeset 369


Ignore:
Timestamp:
Mar 4, 2010, 3:06:54 PM (9 years ago)
Author:
eamiri
Message:

major cleanup in parition2bb() pass
minor bug fixes

Location:
proto/Compiler
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • proto/Compiler/bitstream_compiler.py

    r368 r369  
    4949        py2bitexpr.simplify_tree(s)
    5050        all_lives, s = py2bitexpr.eliminate_dead_code(s, set(livelist))
     51        s = py2bitexpr.factor_out(s)
    5152        s, livelist = py2bitexpr.process_while_loops(s)
    52         s = py2bitexpr.factor_out(s)
    5353
    5454        # BACK END
  • proto/Compiler/py2bitexpr.py

    r368 r369  
    179179        pass
    180180    else:
    181         print exp
    182181        assert(1==0)
    183182    return exp
     
    186185    call_list = []
    187186    for index, loc in enumerate(main.body):
    188         #print loc.value
    189187        if isinstance(loc, ast.Assign) and isinstance(loc.value, ast.Call):
    190188                func_name = translate_var(loc.value.func)
     
    228226
    229227def modify_assignments_in_caller(main, line_no, return_list, prefix, callee):
    230     #print "*********", prefix, "************"
    231228    if isinstance(main.body[line_no].targets[0], ast.Tuple):
    232229        all_vars = main.body[line_no].targets[0].elts
     
    249246            second_index = [translate_var(x) for x in callee.args.args].index(temp_name)
    250247            final_name = translate_var(main.body[line_no].value.args[second_index])
    251             #print "1111"
    252248        else:
    253249            final_name = prefix+temp_name
    254             #print "2222", final_name
    255250
    256251        if return_list[temp_name][0] == "struct":
     
    263258        else:
    264259            for elem in return_list[temp_name][1]:
    265                 #print final_name, elem
    266260                new_code.append(ast.Assign([ast.Name(id=my_template%(item.id, elem))], ast.Name(id=prefix+my_template%(temp_name, elem))))
    267261    main.body = main.body[:line_no]+new_code+main.body[line_no+1:]
     
    482476        for s in ast_stmts:
    483477                if isinstance(s, ast.Expr):
    484                         print translate_var(s.value.func)
    485478                        if (translate_var(s.value.func)=='strct_bitutil__Optimize_'):
    486479                            target = translate_var(s.value.args[0])
     
    602595
    603596def update_def(code, var, line, suffix_num):
    604     #for i in code:
    605     #    print i
    606     #print "------------------------", len(code), line, var
    607597    loc = code[line]
    608598    if isinstance(loc, bitexpr.BitAssign):
     
    715705    breaks = [-1]+breaks+[len(s)]
    716706    for start, stop in pairs(breaks)[:-1]:
    717         #print start, stop
    718707        next = s[start+1:stop]
    719708        if len(next)>0:
     
    754743    return sorted_targets, lineno
    755744
    756 def get_boundary(def_line, lastuse_line):
    757     earliest = min(def_line)
    758 
    759     # The indices of all variables defined in the same line of code and earlier than all other variables
    760     # There is more than one such variable only if these variables are input variables
    761     all_early = []
    762     all_early_cnt = 0
    763     j = 0
    764 
    765     while earliest in def_line[j:]:
    766         m = def_line[j:].index(earliest)
    767         all_early_cnt += 1
    768         all_early.append(m+j)
    769         j += m+1
    770 
    771     #all_early contains the indices of the all earliest defined vars
    772     lasts = []
    773     map(lambda y: lasts.append(lastuse_line[y]), all_early)
    774 
    775     latest = max(lasts)
    776     return earliest, latest
    777 
    778 def adjust_latest(s, latest):
    779     line = 0
    780     for stmt in s:
    781         if isinstance(stmt, bitexpr.BitAssign):
    782             if latest == line:
    783                 return latest
    784             line += 1
    785         if isinstance(stmt, bitexpr.WhileLoop):
    786             end_of_loop = line+len(stmt.stmts)
    787             if latest <= end_of_loop:
    788                 return end_of_loop
    789             else:
    790                 line = end_of_loop+1
    791     return line
    792 
    793 #There is slight difference between the function below and adjust_latest (look at the second return)
    794 def adjust_earliest(s, earliest):
    795     line = 0
     745def defines(varname, stmts):
     746    is_defined = False
     747    for loc in stmts:
     748        if isinstance(loc, bitexpr.WhileLoop):
     749            is_defined |= defines(varname, loc.stmts)
     750        elif isinstance(loc, bitexpr.BitAssign):
     751            if loc.LHS.varname == varname:
     752                is_defined = True
     753
     754    return is_defined
     755
     756def adjust_earliest(s, earliest, varname):
    796757    if earliest == -1:
    797758        return -1
    798759
    799     for stmt in s:
    800         if isinstance(stmt, bitexpr.BitAssign):
    801             if earliest == line:
    802                 return earliest
    803             line += 1
     760    line = earliest+1
     761    for stmt in s[earliest+1:]:
    804762        if isinstance(stmt, bitexpr.WhileLoop):
    805             end_of_loop = line+len(stmt.stmts)
    806             if earliest <= end_of_loop:
    807                 return end_of_loop+1
    808             else:
    809                 line = end_of_loop+1
     763            if defines(varname, stmt.stmts):
     764               earliest = line+1
     765        line+=1
     766    return earliest
    810767
    811768def chop_code(s, start, stop):
     
    827784
    828785        if isinstance(stmt, bitexpr.WhileLoop):
    829             end_of_loop = line+len(stmt.stmts)
    830786            if line == start:
    831787                cut1 = index
    832             if end_of_loop == stop:
     788            if line == stop:
    833789                cut2 = index
    834             line = end_of_loop+1
     790            line+=1
    835791
    836792    return s[:cut1+1], s[cut1+1:cut2+1], s[cut2+1:]
     
    844800
    845801
    846 def gen_bb(s, opt_list, def_line, lastuse_line):
    847     assert (len(opt_list) == len(def_line) == len(lastuse_line))
     802def gen_cond_obj(opt_pragma):
     803    if opt_pragma[1] == 'AllZero' or opt_pragma[1] == 'allzero':
     804        cond_obj = bitexpr.isAllZero(opt_pragma[0])
     805    if opt_pragma[1] == 'AllOne' or opt_pragma[1] == 'allone':
     806        cond_obj = bitexpr.isAllOne(opt_pragma[0])
     807    return cond_obj
     808
     809def gen_bb(s, opt_list, def_line):
     810    assert (len(opt_list) == len(def_line))
    848811    if opt_list==[]:
    849812        return s
    850813
    851     earliest, latest = get_boundary(def_line, lastuse_line)
    852 
    853     indices = []
    854     for index, i in enumerate(def_line): #was enumerate(lastuse_line)
    855         if i <= latest:
    856             indices.append(index)
    857     #if latest or earliest are inside a while loop they are pushed to the end of while loop or beginning of the next block (respectively)
    858 
    859     e = earliest
    860     l = latest
    861 
    862     opt1 = {}
    863     def1 = {}
    864     use1 = {}
    865     for index, i in enumerate(opt_list):
    866         opt1.setdefault(index in indices, []).append(i)
    867     for index, i in enumerate(def_line):
    868         def1.setdefault(index in indices, []).append(i)
    869     for index, i in enumerate(lastuse_line):
    870         use1.setdefault(index in indices, []).append(i)
    871 
    872     latest = max(use1[True])
    873     latest = adjust_latest(s, latest)
    874     earliest = adjust_earliest(s, earliest)
    875 
    876     #use earliest to construct an initial block with no if-then-else
    877     #use use1[True], def1[True], opt1[True] to construct if then else and recurse on inner blocks
    878     #use use1[False], def1[False], opt1[False] to construct the block after if-then-else and recurse on that block
     814    earliest = min(def_line)
     815    latest = len(s)
     816    earliest_index = def_line.index(earliest)
     817    early_varname = opt_list[earliest_index][0]
     818   
     819    earliest = adjust_earliest(s, earliest, early_varname)
     820
    879821    first, second, third = chop_code(s, earliest, latest)
    880822
    881     the_opt = None
    882     the_index = None
    883     for index, value in enumerate(opt1[True]):
    884         if e==def1[True][index] and l==use1[True][index]:
    885             the_opt = value
    886             the_index = index
    887     del opt1[True][the_index]
    888     del use1[True][the_index]
    889     del def1[True][the_index]
    890 
    891     second = gen_bb(second, opt1[True], def1[True],use1[True])
    892 
    893     if the_opt[1] == 'AllZero' or the_opt[1] == 'allzero':
    894         cond_obj = bitexpr.isAllZero(the_opt[0])
    895     if the_opt[1] == 'AllOne' or the_opt[1] == 'allone':
    896         cond_obj = bitexpr.isAllOne(the_opt[0])
    897 
    898     change = count_lines(first) + count_lines(second)
    899     new_def = []
    900     new_use = []
    901 
    902     if (False in opt1):
    903         for i in def1[False]:
    904             new_def.append(max(i-change, -1))
    905         for i in use1[False]:
    906             new_use.append(i-change)
    907 
    908         third = gen_bb(third, opt1[False], new_def, new_use)
     823    cond_obj = gen_cond_obj(opt_list[earliest_index])
     824   
     825    del opt_list[earliest_index]
     826    del def_line[earliest_index]
     827    def_line = [x-earliest-1 for x in def_line]
     828   
     829    second = gen_bb(second, opt_list, def_line)
    909830
    910831    result = first + [bitexpr.If(cond_obj, second, copy.deepcopy(second))] + third
    911 
    912832    return result
    913833
     
    916836    lineno = []
    917837    def_line = []
    918     lastuse_line = []
    919838    opt_list = get_opt_list(s)
    920839
    921     st = gen_sym_table(s, True)
    922840    st2 = gen_sym_table(s)
    923     #total_lines = count_lines(s)
    924     total_lines = len(s)
    925841
    926842    for item in opt_list:
     
    930846            def_line.append(-1)
    931847
    932         lastuse_line.append(total_lines)
    933 
    934     return gen_bb(s, opt_list, def_line, lastuse_line)
     848
     849    return gen_bb(s, opt_list, def_line)
    935850
    936851#################################################################################################################
     
    1015930def merge_var_dic(first, second):
    1016931    res = {}
    1017     #print first
    1018     #print second
    1019932    res['int'] = first['int'].union(second['int'])
    1020933    res['bitblock'] = first['bitblock'].union(second['bitblock'])
     
    11101023#################################################################################################################
    11111024def replace_in_rhs(rhs, target, replace):
     1025    if isinstance(rhs, bitexpr.Const):
     1026        return rhs
    11121027    if isinstance(rhs, bitexpr.Var):
    11131028        if rhs.varname == target:
     
    11511066        if code[0].control_expr.var.varname == target:
    11521067            code[0].control_expr.var = replace
    1153         code[0].stmts = apply_single_opt(code[0].stmts, target, replace)
     1068        #code[0].stmts = apply_single_opt(code[0].stmts, target, replace)
    11541069
    11551070    return [code[0]]+apply_single_opt(code[1:], target, replace)
     
    12651180        try:
    12661181            ind = varname.index("__")
    1267            
    12681182            return varname[6:ind]
    1269            
    12701183        except:
    12711184            return varname
    1272    
    12731185    return varname
    1274    
    1275    
     1186
    12761187def check_loc(loc, must_liv):
    12771188
     
    13051216
    13061217def remove_dead(bb, must_live):
    1307     #eliminates dead code from a basic block
    1308     #bb = remove_copies(bb)
    13091218    my_alives = set([])
    13101219    dead = []
    13111220
    13121221    for line, loc in reversed(list(enumerate(bb))):
    1313         #print line, my_alives.union(must_live)
    1314         #print "---------------------------------------------------"
    13151222        new_lives, removable = check_loc(loc, my_alives.union(must_live))
    1316         #print "---------------------------------------------------"
    13171223
    13181224        if removable:
     
    13251231
    13261232    return my_alives, bb
    1327 
    13281233
    13291234def get_loop_variables(code):
     
    13721277
    13731278    all_alives = new_alives.union(must_live)
    1374     #if "Ct_starts" in all_alives:
    1375     #    print "IT IS ALIVE"
    13761279    dummy, new_tree = eliminate_dead_code(tree[:last], all_alives)
    13771280    tree = new_tree+bb
     
    14371340    if one.__class__ != two.__class__:
    14381341        return False
    1439 
     1342   
    14401343    if isinstance(one, bitexpr.BitAssign):
    14411344        if (one.LHS.varname != two.LHS.varname):
     
    14491352        if isinstance(one.RHS, bitexpr.Var):
    14501353            return (one.RHS.varname == two.RHS.varname)
    1451 
     1354        if isinstance(one.RHS, bitexpr.Const):
     1355            return one.RHS.n == two.RHS.n
    14521356        return (one.RHS.operand1.varname == two.RHS.operand1.varname)and(one.RHS.operand2.varname == two.RHS.operand2.varname)
    14531357
     
    14741378        if (one.carry_expr.__class__ != two.carry_expr.__class__):
    14751379            return False
    1476         if (one.carry_expr.var.varname != two.carry_expr.var.varname):
    1477             return False
     1380        #if (one.carry_expr.var.varname != two.carry_expr.var.varname):
     1381        #    return False
    14781382        if (len(one.stmts) != len(two.stmts)):
    14791383            return False
     
    14851389def get_factorable(cond):
    14861390    earliest = 0
    1487     #print cond.control_expr, cond.control_expr.var.varname
    14881391    l = min(len(cond.true_branch), len(cond.false_branch))
    14891392    for index in reversed(range(-l,0)):
     
    15431446        return "bitblock_has_bit(%s)"%(expr.var.varname)
    15441447    else:
    1545         #print expr
    15461448        assert (1==0)
    15471449
     
    15541456        return "\n%s(%s) {\n"%(" "*indent+cond_stmt+" ", generate_condition(expr))
    15551457    else:
    1556         #print expr
    15571458        assert (1==0)
    15581459
Note: See TracChangeset for help on using the changeset viewer.