Changeset 429

Timestamp:

07/03/10 17:32:50 (3 years ago)

Author:

eamiri

Message:

-simd-carry option added

Location:

proto/Compiler

Files:

• bitexpr.py (modified) (2 diffs)
• bitstream_compiler.py (modified) (4 diffs)
• py2bitexpr.py (modified) (11 diffs)
• sse_simd.h (modified) (3 diffs)
• template.c (modified) (6 diffs)

proto/Compiler/bitexpr.py

@@ -101 +101 @@
         self.op_C = "adc128"
         self.carry = carry
+        self.op_advance_noint = "advance_with_carry"
+        self.op_add_noint = "adc128_simd"
         BitExpr.__init__(self, expr1, expr2, "Add")
     def show(self): return 'Add(%s, %s)' % (self.operand1.show(), self.operand2.show())
@@ -109 +111 @@
         self.op_C = "sbb128"
         self.brw = brw
+        self.op_sub_noint = "sbb128_simd"
         BitExpr.__init__(self, expr1, expr2, "Sub")
     def show(self): return 'Sub(%s, %s)' % (self.operand1.show(), self.operand2.show())

proto/Compiler/bitstream_compiler.py

@@ -7 +7 @@
 #
 
-import ast, py2bitexpr, string, sys
+import ast, py2bitexpr, string, sys, copy
 
 class Program:
@@ -15 +15 @@
         self.outfile_name = out_file
 
-    def output(self, decl, stmts, templ):
+    def output(self, decl, stream_stmts , block_stmts, templ):
         templ = string.replace(templ, '@decl', decl)
-        templ = string.replace(templ, '@stmts', stmts)
+        templ = string.replace(templ, '@stream_stmts', stream_stmts)
+        templ = string.replace(templ, '@block_stmts', block_stmts)
         return templ
 
@@ -33 +34 @@
         f.close()
 
-    def generate_code(self, s, file_path):
+    def generate_code(self, s, file_path, int_carry):
         # FRONT END
         s = ast.parse(s)
@@ -50 +51 @@
         all_lives, s = py2bitexpr.eliminate_dead_code(s, set(livelist))
         s = py2bitexpr.factor_out(s)
-        s, livelist = py2bitexpr.process_while_loops(s)
+        s, livelist = py2bitexpr.process_while_loops(s, int_carry)
+        
 
         # BACK END
-        declarations = py2bitexpr.gen_declarations(s)
+        declarations = py2bitexpr.gen_declarations(s, int_carry)
         templ = self.read_template(file_path)
 
-        templ = self.output(declarations, py2bitexpr.print_prog(s), templ)
+        templ = self.output(declarations, py2bitexpr.print_stream_stmts(copy.deepcopy(s)), py2bitexpr.print_block_stmts(s, int_carry), templ)
         self.write_final_code(templ)
         return s
 
+
+def read_flags (params):
+    flags = []
+    non_flags = []
+    l = len(params)
+    for i in range(l):
+        if params[i][0] == '-':
+            flags.append(params[i])
+        else:
+            non_flags.append(params[i])
+
+    return flags, non_flags
+
+def int_carry(flags):
+    l = len(flags)
+    for i in range(l):
+        if flags[i] == '-simd-carry':
+            return False
+        if flags[i] == '-int-carry':
+            return True
+    return True #default carry type is int
+
+def read_input(inp_file_name):
+    mycode = ""
+    inp_file = open(non_flags[1])
+    for line in inp_file:
+        mycode += line
+    inp_file.close()
+    return mycode
 ###############################################################
 
 if __name__ == '__main__':
-        mycode = ""
         if len(sys.argv) < 2:
-            print "Usage: python bitstream_compiler.py <input file> [output file]"
+            print "Usage: python bitstream_compiler.py <input file> [output file] options"
             #exit()
 
-        #inp_file = open("parabix2.py")
-        inp_file = open(sys.argv[1])
-        last_slash = sys.argv[1].rfind("/")
-        file_path = sys.argv[1][:last_slash+1]
+        flags, non_flags = read_flags(sys.argv)
+        last_slash = non_flags[1].rfind("/")
+        file_path = non_flags[1][:last_slash+1]
         
+        out_file = "code.c"
+        if len(non_flags) >= 3:
+            out_file = non_flags[2]
         
-        
-        for line in inp_file:
-            mycode += line
-        inp_file.close()
-
-        out_file = "code.c"
-        if len(sys.argv) >= 3:
-            out_file = sys.argv[2]
-        s = Program(out_file).generate_code(mycode, file_path)
+        s = Program(out_file).generate_code(read_input(non_flags[1]), file_path, int_carry(flags))

proto/Compiler/py2bitexpr.py

@@ -926 +926 @@
                 if var_type == "int":
                     ints.add(name)
+                        
         return {'int':ints, 'bitblock': bitblocks, 'array': arrays, 'struct': structs}
 
@@ -951 +952 @@
     return res
 
-def gen_output(var_dic):
+def gen_output(var_dic, int_carry):
         s = ''
-        for i in  var_dic['int']:
-                s+="int %s=0;\n"%i
-
         for i in var_dic['bitblock']:
                 if i == AllOne:
                         s += "BitBlock %s = simd_const_1(1);\n"%i
-                elif i== AllZero:
+                elif i == AllZero:
                         s+="BitBlock %s = simd_const_1(0);\n"%i
+                elif i == "EOF_mask":
+                        s+="BitBlock EOF_mask = simd_const_1(1);\n"
                 else:
                         s+="BitBlock %s;\n"%i
@@ -973 +973 @@
                 s+="};\n"
                 s+="struct __%s__ %s;\n"%(i,i)
+
+        for i in  var_dic['int']:
+                if int_carry:
+                        s+="int %s=0;\n"%i
+                else:
+                        s+="BitBlock %s=AllZero;\n"%i
+
+
 
         return s
@@ -1003 +1011 @@
         return vd
 
-    """for loc in s[1:]:
-        more = get_vars(loc)
-
-    vd = get_vars(bb[0].code)
-    for block in bb[1:]:
-        more = get_vars(block.code)
-        vd = merge_var_dic(vd, more)
-    declarations = gen_output(vd)
-    return declarations
-    """
-
-def gen_declarations(s):
+def gen_declarations(s, int_carry):
     vd = gen_var_dic(s)
-    return gen_output(vd)
-#################################################################################################################
-## This class replaces all occurences of a reduced variable to its value --- Pass 7
+    return gen_output(vd, int_carry)
+#################################################################################################################
+## This class replaces all occurrences of a reduced variable to its value --- Pass 7
 ## *** This pass should change so that instead of recursing on the tree structure used before, it recurses on ***
 ## *** the new AST notation                                                                                   ***
@@ -1286 +1283 @@
 carry_suffix = "_i"
 
-def fix_the_loop(loop):
+def fix_the_loop(loop, carry_type):
     carries = []
     for loc in loop.stmts:
@@ -1293 +1290 @@
     for item in carries:
         newvar = bitexpr.Var(item+carry_suffix)
-        loop.stmts.append(bitexpr.BitAssign(newvar, bitexpr.Or(newvar, bitexpr.Var(item), "int")))
+        loop.stmts.append(bitexpr.BitAssign(newvar, bitexpr.Or(newvar, bitexpr.Var(item), carry_type)))
     for item in carries:
-        loop.stmts.append(bitexpr.BitAssign( bitexpr.Var(item), bitexpr.FalseLiteral("int") ))
+        loop.stmts.append(bitexpr.BitAssign( bitexpr.Var(item), bitexpr.FalseLiteral(carry_type) ))
 
     return loop, carries
 
-def process_while_loops(code):
+def process_while_loops(code, int_carry):
     all = []
     update = {}
+    
+    if int_carry:
+        carry_type = "int"
+    else:
+        carry_type = "vector"
+    
     for index, loc in enumerate(code):
         if isinstance(loc, bitexpr.WhileLoop):
-            update[index] = fix_the_loop(loc)
+            update[index] = fix_the_loop(loc, carry_type)
             for i in update[index][1]:
                 all.append(i)
@@ -1318 +1321 @@
         code[key] = update[key][0]
         carry_variable = bitexpr.Var("CarryTemp"+str(key))
-        code[key].stmts.insert(0, bitexpr.BitAssign(carry_variable, bitexpr.FalseLiteral("int")))
+        code[key].stmts.insert(0, bitexpr.BitAssign(carry_variable, bitexpr.FalseLiteral(carry_type)))
         for item in update[key][1][2:]:
-            code.insert(key+1, bitexpr.BitAssign(carry_variable, bitexpr.Or(carry_variable, bitexpr.Var(item), "int")))
+            code.insert(key+1, bitexpr.BitAssign(carry_variable, bitexpr.Or(carry_variable, bitexpr.Var(item), carry_type)))
         if len(update[key][1]) == 1:
             code.insert(key+1, bitexpr.BitAssign(carry_variable, bitexpr.Var(update[key][1][0])))
         elif len(update[key][1]) > 1:
-            code.insert(key+1, bitexpr.BitAssign(carry_variable, bitexpr.Or(bitexpr.Var(update[key][1][0]), bitexpr.Var(update[key][1][1]), "int")))
+            code.insert(key+1, bitexpr.BitAssign(carry_variable, bitexpr.Or(bitexpr.Var(update[key][1][0]), bitexpr.Var(update[key][1][1]), carry_type)))
         for item in update[key][1]:
-            code.insert(key+1, bitexpr.BitAssign(bitexpr.Var(item+carry_suffix), bitexpr.FalseLiteral("int")))
+            code.insert(key+1, bitexpr.BitAssign(bitexpr.Var(item+carry_suffix), bitexpr.FalseLiteral(carry_type)))
         for item in update[key][1]:
             code.insert(key+1, bitexpr.BitAssign(bitexpr.Var(item), bitexpr.Var(item+carry_suffix)))
@@ -1458 +1461 @@
         assert (1==0)
 
-def print_prog(s, indent = 0):
+def print_block_stmts(s, int_carry, indent = 0):
     indent_unit = 4
     code = ""
@@ -1465 +1468 @@
     if isinstance(s[0], bitexpr.If):
         code = generate_statement(s[0].control_expr, indent, "if")
-        code += print_prog(s[0].true_branch, indent+indent_unit)
+        code += print_block_stmts(s[0].true_branch, int_carry, indent+indent_unit)
         code += " "*indent+"}\n"
         code += " "*indent+"else {\n"
-        code += print_prog(s[0].false_branch, indent+indent_unit)
+        code += print_block_stmts(s[0].false_branch, int_carry, indent+indent_unit)
         code += " "*indent+"}\n"
 
-    if isinstance(s[0], bitexpr.WhileLoop):
-        #code = generate_statement(s[0].control_expr, indent, "while")
-        code = "\n%s((%s)||((256&%s)%s)) {\n"%(" "*indent+"while"+" ", generate_condition(s[0].control_expr), s[0].carry_expr.var.varname, ">0")
-        code += print_prog(s[0].stmts, indent+indent_unit)
+    elif isinstance(s[0], bitexpr.WhileLoop):
+        if int_carry:
+                code = "\n%s((%s)||((256&%s)%s)) {\n"%(" "*indent+"while"+" ", generate_condition(s[0].control_expr), s[0].carry_expr.var.varname, ">0")
+        else:
+                        code = "\n%s((%s)||(bitblock_has_bit(%s))) {\n"%(" "*indent+"while"+" ", generate_condition(s[0].control_expr), s[0].carry_expr.var.varname)
+        code += print_block_stmts(s[0].stmts, int_carry, indent+indent_unit)
         code += " "*indent+"}\n"
-
-    if isinstance(s[0], bitexpr.BitAssign) and not (isinstance(s[0].RHS, bitexpr.Add) or isinstance(s[0].RHS, bitexpr.Sub)):
+    elif (isinstance(s[0].RHS, bitexpr.Const)):
+        pass
+ 
+    elif isinstance(s[0], bitexpr.BitAssign) and not (isinstance(s[0].RHS, bitexpr.Add) or isinstance(s[0].RHS, bitexpr.Sub)):
+
         code += " "*indent + s[0].LHS.varname
         code += " = "
@@ -1504 +1512 @@
                 code += s[0].RHS.operand2.varname
                 code += ";\n"
-            elif isinstance(s[0].RHS, bitexpr.Const):
-                code += "sisd_from_int(%i);"%s[0].RHS.n
-                code += "\n"
             elif isinstance(s[0].RHS, bitexpr.FalseLiteral):
                 code += "0;\n"
-    if isinstance(s[0], bitexpr.BitAssign) and (isinstance(s[0].RHS, bitexpr.Add) or isinstance(s[0].RHS, bitexpr.Sub)):
+    elif isinstance(s[0], bitexpr.BitAssign) and (isinstance(s[0].RHS, bitexpr.Add) or isinstance(s[0].RHS, bitexpr.Sub)) and int_carry:
             if isinstance(s[0].RHS, bitexpr.Add):
                 code += " "*indent + s[0].RHS.op_C + "("
@@ -1530 +1535 @@
                 code += s[0].LHS.varname
                 code += ");\n"
+    elif isinstance(s[0], bitexpr.BitAssign) and (isinstance(s[0].RHS, bitexpr.Add) or isinstance(s[0].RHS, bitexpr.Sub)) and (not int_carry):
+                        if isinstance(s[0].RHS, bitexpr.Add) and (s[0].RHS.operand1.varname == s[0].RHS.operand2.varname):
+                                code += " "*indent + s[0].RHS.op_advance_noint + "("
+                                code += s[0].RHS.operand1.varname
+                                code += ', '
+                                code += s[0].RHS.carry
+                                code += ", "
+                                code += s[0].LHS.varname
+                                code += ");\n"
+                        elif isinstance(s[0].RHS, bitexpr.Add):
+                                code += " "*indent + s[0].RHS.op_add_noint + "("
+                                code += s[0].RHS.operand1.varname
+                                code += ', '
+                                code += s[0].RHS.operand2.varname
+                                code += ', '
+                                code += s[0].RHS.carry
+                                code += ", "
+                                code += s[0].LHS.varname
+                                code += ");\n"
+                        elif isinstance(s[0].RHS, bitexpr.Sub):
+                                code += " "*indent + s[0].RHS.op_sub_noint + "("
+                                code += s[0].RHS.operand1.varname
+                                code += ', '
+                                code += s[0].RHS.operand2.varname
+                                code += ', '
+                                code += s[0].RHS.brw
+                                code += ", "
+                                code += s[0].LHS.varname
+                                code += ");\n"
     s.pop(0)
-    return code+print_prog(s, indent)
+    return code+print_block_stmts(s, int_carry, indent)
+
+
+def print_stream_stmts(s, indent = 0):
+    indent_unit = 4
+    code = ""
+    if len(s) == 0:
+        return ""
+    elif isinstance(s[0], bitexpr.BitAssign):
+        if (isinstance(s[0].RHS, bitexpr.Const)):
+            code += " "*indent + s[0].LHS.varname
+            code += " = "
+            code += "sisd_from_int(%i);"%s[0].RHS.n
+            code += "\n"
+
+    s.pop(0)
+    return code+print_stream_stmts(s, indent)
 
 #################################################################################################################

proto/Compiler/sse_simd.h

@@ -644 +644 @@
 
 
-void print_bit_block(char * var_name, SIMD_type v) {
+void print_bit_block(const char * var_name, SIMD_type v) {
   union {SIMD_type vec; unsigned char elems[8];} x;
-  x.vec = v;
+  x.vec = v;d
   unsigned char c, bit_reversed;
   int i;
@@ -652 +652 @@
   for (i = 0; i < sizeof(SIMD_type); i++) {
     c = x.elems[i];
-     printf("%02X ", c); 
+     printf("%02X ", c);
   }
   printf("\n");
@@ -703 +703 @@
 
 
-#endif
-
+#define double_int64_adc(x1, x2, y1, y2, rslt1, rslt2, carry) \
+  __asm__  ("sahf\n\t" \
+        "adc %[e1], %[z1]\n\t" \
+        "adc %[e2], %[z2]\n\t" \
+        "lahf\n\t" \
+     : [z1] "=r" (rslt1), [z2] "=r" (rslt2), [carryflag] "=a" (carry) \
+         : "[z1]" (x1), "[z2]" (x2), \
+           [e1] "r" (y1), [e2] "r" (y2), \
+           "[carryflag]" (carry) \
+         : "cc")
+
+#define adc128(first, second, carry, sum) \
+do\
+{\
+  union {__m128i bitblock;\
+         uint64_t int64[2];} rslt;\
+\
+  union {__m128i bitblock;\
+         uint64_t int64[2];} x;\
+\
+  union {__m128i bitblock;\
+         uint64_t int64[2];} y;\
+\
+  x.bitblock = first;\
+  y.bitblock = second;\
+\
+  double_int64_adc(x.int64[0], x.int64[1], y.int64[0], y.int64[1], rslt.int64[0], rslt.int64[1], carry);\
+  sum = rslt.bitblock;\
+}while(0)
+
+
+
+#define double_int64_sbb(x1, x2, y1, y2, rslt1, rslt2, carry) \
+  __asm__  ("sahf\n\t" \
+        "sbb %[e1], %[z1]\n\t" \
+        "sbb %[e2], %[z2]\n\t" \
+        "lahf\n\t" \
+     : [z1] "=r" (rslt1), [z2] "=r" (rslt2), [carryflag] "=a" (carry) \
+         : "[z1]" (x1), "[z2]" (x2), \
+           [e1] "r" (y1), [e2] "r" (y2), \
+           "[carryflag]" (carry) \
+         : "cc")
+
+#define sbb128(first, second, carry, sum) \
+do\
+{ union {__m128i bitblock;\
+         uint64_t int64[2];} rslt;\
+\
+  union {__m128i bitblock;\
+         uint64_t int64[2];} x;\
+\
+  union {__m128i bitblock;\
+         uint64_t int64[2];} y;\
+\
+  x.bitblock = first;\
+  y.bitblock = second;\
+\
+  double_int64_sbb(x.int64[0], x.int64[1], y.int64[0], y.int64[1], \
+                   rslt.int64[0], rslt.int64[1], carry);\
+  sum = rslt.bitblock;\
+}while(0)
+
+
+
+#define adc128_simd(x, y, carry,  sum) \
+do{ \
+  SIMD_type gen = simd_and(x, y); \
+  SIMD_type prop = simd_or(x, y); \
+  SIMD_type partial = simd_add_64(simd_add_64(x, y), *carry); \
+  SIMD_type c1 = sisd_slli(simd_srli_64(simd_or(gen, simd_andc(prop, partial)), 63), 64); \
+  *sum = simd_add_64(c1, partial); \
+  *carry = sisd_srli(simd_or(gen, simd_andc(prop, *sum)), 127); \
+} while(0)
+
+
+#define sbb128_simd(x, y, borrow, difference) \
+do {\
+  SIMD_type gen = simd_andc(y, x); \
+  SIMD_type prop = simd_not(simd_xor(x, y)); \
+  SIMD_type partial = simd_sub_64(simd_sub_64(x, y), *borrow); \
+  SIMD_type b1 = sisd_slli(simd_srli_64(simd_or(gen, simd_and(prop, partial)), 63), 64); \
+  *difference = simd_sub_64(partial, b1); \
+  *borrow = sisd_srli(simd_or(gen, simd_and(prop, *difference)), 127); \
+}while(0)
+
+
+#define advance_with_carry(cursor, carry, rslt)\
+do{\
+  SIMD_type shift_out = simd_srli_64(cursor, 63);\
+  SIMD_type low_bits = simd_mergel_64(shift_out, carry);\
+  carry = sisd_srli(shift_out, 64);\
+  rslt = simd_or(simd_add_64(cursor, cursor), low_bits);\
+}while(0)
+
+#endif
+

proto/Compiler/template.c

@@ -12 +12 @@
 
 
-#define BUFFER_PROFILING
-
+#include "perfsec.h"
+//#define BUFFER_PROFILING
 #ifdef BUFFER_PROFILING
-#include "perfsec.h"
 BOM_Table * parser_timer;
 #endif
@@ -77 +76 @@
 } \
 
-#define double_int64_adc(x1, x2, y1, y2, rslt1, rslt2, carry) \
-  __asm__  ("sahf\n\t" \
-        "adc %[e1], %[z1]\n\t" \
-        "adc %[e2], %[z2]\n\t" \
-        "lahf\n\t" \
-     : [z1] "=r" (rslt1), [z2] "=r" (rslt2), [carryflag] "=a" (carry) \
-         : "[z1]" (x1), "[z2]" (x2), \
-           [e1] "r" (y1), [e2] "r" (y2), \
-           "[carryflag]" (carry) \
-         : "cc")
-
-#define adc128(first, second, carry, sum) \
-do\
-{\
-  union {__m128i bitblock;\
-         uint64_t int64[2];} rslt;\
-\
-  union {__m128i bitblock;\
-         uint64_t int64[2];} x;\
-\
-  union {__m128i bitblock;\
-         uint64_t int64[2];} y;\
-\
-  x.bitblock = first;\
-  y.bitblock = second;\
-\
-  double_int64_adc(x.int64[0], x.int64[1], y.int64[0], y.int64[1], rslt.int64[0], rslt.int64[1], carry);\
-  sum = rslt.bitblock;\
-}while(0)
-
-
-
-#define double_int64_sbb(x1, x2, y1, y2, rslt1, rslt2, carry) \
-  __asm__  ("sahf\n\t" \
-        "sbb %[e1], %[z1]\n\t" \
-        "sbb %[e2], %[z2]\n\t" \
-        "lahf\n\t" \
-     : [z1] "=r" (rslt1), [z2] "=r" (rslt2), [carryflag] "=a" (carry) \
-         : "[z1]" (x1), "[z2]" (x2), \
-           [e1] "r" (y1), [e2] "r" (y2), \
-           "[carryflag]" (carry) \
-         : "cc")
-
-#define sbb128(first, second, carry, sum) \
-do\
-{ union {__m128i bitblock;\
-         uint64_t int64[2];} rslt;\
-\
-  union {__m128i bitblock;\
-         uint64_t int64[2];} x;\
-\
-  union {__m128i bitblock;\
-         uint64_t int64[2];} y;\
-\
-  x.bitblock = first;\
-  y.bitblock = second;\
-\
-  double_int64_sbb(x.int64[0], x.int64[1], y.int64[0], y.int64[1], \
-                   rslt.int64[0], rslt.int64[1], carry);\
-  sum = rslt.bitblock;\
-}while(0)
+      
 
         
@@ -145 +84 @@
 void do_process(FILE *infile, FILE *outfile) {
 
-  @decl
+@decl
 
   BytePack U8[8];
@@ -156 +95 @@
   char * srclimit;
 
+
   
   srcbuf = (char *) malloc(BUFFER_SIZE+BLOCK_SIZE);
@@ -163 +103 @@
   }
   
-  EOF_mask = simd_const_1(1);
   chars_read = fread((void *)srcbuf, 1, BUFFER_SIZE, infile);
   srclimit = srcbuf + chars_read;
+
+@stream_stmts
 
   while(chars_read>0){
@@ -199 +140 @@
       array_bit__7_ &= EOF_mask;
 
-      @stmts
-
+      @block_stmts
+
+      
       if (bitblock_has_bit(error_mask)) {
         errpos = block_pos + buf_pos + count_forward_zeroes(error_mask);