| 1 | |
|---|
| 2 | # bitstream_compiler.py - compile unbounded bitstreams code into |
|---|
| 3 | # equivalent block-by-block code in C. |
|---|
| 4 | # |
|---|
| 5 | # (c) 2009 Robert D. Cameron and Ehsan Amiri |
|---|
| 6 | # All rights reserved. |
|---|
| 7 | # Licensed to International Characters, Inc. under Academic Free License 3.0 |
|---|
| 8 | # |
|---|
| 9 | |
|---|
| 10 | import ast, py2bitexpr, string |
|---|
| 11 | |
|---|
| 12 | #import bitexpr |
|---|
| 13 | """ |
|---|
| 14 | Nop = 'nop' |
|---|
| 15 | Andc = 'simd_andc' |
|---|
| 16 | And = 'simd_and' |
|---|
| 17 | Or = 'simd_or' |
|---|
| 18 | Xor = 'simd_xor' |
|---|
| 19 | Not = 'not' |
|---|
| 20 | Sel = 'simd_if' |
|---|
| 21 | Add = 'adc128' |
|---|
| 22 | Sub = 'sbb128' |
|---|
| 23 | If = 'simd_has_bit' |
|---|
| 24 | |
|---|
| 25 | |
|---|
| 26 | """ |
|---|
| 27 | |
|---|
| 28 | class Program: |
|---|
| 29 | def __init__(self): |
|---|
| 30 | pass |
|---|
| 31 | self.templ_name = "template.c" |
|---|
| 32 | self.outfile_name = "code.c" |
|---|
| 33 | |
|---|
| 34 | def output(self, decl, stmts, templ): |
|---|
| 35 | templ = string.replace(templ, '@decl', decl) |
|---|
| 36 | templ = string.replace(templ, '@stmts', stmts) |
|---|
| 37 | return templ |
|---|
| 38 | |
|---|
| 39 | def read_template(self): |
|---|
| 40 | f=open(self.templ_name) |
|---|
| 41 | inp = "" |
|---|
| 42 | for line in f: |
|---|
| 43 | inp += line |
|---|
| 44 | f.close() |
|---|
| 45 | return inp |
|---|
| 46 | |
|---|
| 47 | def write_final_code(self, code): |
|---|
| 48 | f=open(self.outfile_name, 'w') |
|---|
| 49 | f.write(code) |
|---|
| 50 | f.close() |
|---|
| 51 | |
|---|
| 52 | def generate_code(self, s): |
|---|
| 53 | s = ast.parse(s) |
|---|
| 54 | s = s.body[0].body |
|---|
| 55 | |
|---|
| 56 | s = py2bitexpr.translate_stmts(s) |
|---|
| 57 | |
|---|
| 58 | st = py2bitexpr.gen_sym_table(s) |
|---|
| 59 | |
|---|
| 60 | s=py2bitexpr.make_SSA(s, st) |
|---|
| 61 | |
|---|
| 62 | s = py2bitexpr.partition2bb(s, ) |
|---|
| 63 | |
|---|
| 64 | s = py2bitexpr.apply_all_opt(s) |
|---|
| 65 | s = py2bitexpr.normalize(s) |
|---|
| 66 | py2bitexpr.simplify_tree(s) |
|---|
| 67 | |
|---|
| 68 | livelist = ['u16hi[0]', 'u16hi[1]', 'u16hi[2]', 'u16hi[3]', 'u16hi[4]', 'u16hi[5]', 'u16hi[6]', 'u16hi[7]'] |
|---|
| 69 | livelist += ['u16lo[0]','u16lo[1]','u16lo[2]','u16lo[3]','u16lo[4]','u16lo[5]','u16lo[6]','u16lo[7]', 'delmask', 'u8.error', 'error_mask', 'u8lastbyte', 'Cursor2',] |
|---|
| 70 | all_lives, s = py2bitexpr.eliminate_dead_code(s, set(livelist)) |
|---|
| 71 | |
|---|
| 72 | s=py2bitexpr.factor_out(s) |
|---|
| 73 | |
|---|
| 74 | s, livelist = py2bitexpr.process_while_loops(s) |
|---|
| 75 | declarations = py2bitexpr.gen_declarations(s) |
|---|
| 76 | |
|---|
| 77 | templ = self.read_template() |
|---|
| 78 | templ = self.output(declarations, py2bitexpr.print_prog(s), templ) |
|---|
| 79 | self.write_final_code(templ) |
|---|
| 80 | return s |
|---|
| 81 | |
|---|
| 82 | #livelist = ['u16hi[0]','u16hi[1]','u16hi[2]','u16hi[3]','u16hi[4]','u16hi[5]','u16hi[6]','u16hi[7]'] |
|---|
| 83 | #livelist += ['u16lo[0]','u16lo[1]','u16lo[2]','u16lo[3]','u16lo[4]','u16lo[5]','u16lo[6]','u16lo[7]', 'delmask', 'u8.error', 'error_mask', 'u8lastbyte'] |
|---|
| 84 | |
|---|
| 85 | |
|---|
| 86 | ############################################################### |
|---|
| 87 | |
|---|
| 88 | #if __name__ == '__main__': |
|---|
| 89 | #if __name__ == '__main__': |
|---|
| 90 | |
|---|
| 91 | if True: |
|---|
| 92 | s=r"""def u8u16(u8bit): |
|---|
| 93 | temp1 = (u8bit[0] | u8bit[1]); |
|---|
| 94 | temp2 = (u8bit[2] & u8bit[3]); |
|---|
| 95 | temp3 = (temp2 &~ temp1); |
|---|
| 96 | temp4 = (u8bit[4] & u8bit[5]); |
|---|
| 97 | temp5 = (u8bit[6] | u8bit[7]); |
|---|
| 98 | temp6 = (temp4 &~ temp5); |
|---|
| 99 | LAngle =(temp3 & temp6); |
|---|
| 100 | temp7 = (u8bit[6] &~ u8bit[7]); |
|---|
| 101 | temp8 = (temp4 & temp7); |
|---|
| 102 | RAngle =(temp3 & temp8); |
|---|
| 103 | temp9 = (u8bit[7] &~ u8bit[6]); |
|---|
| 104 | temp10 =(temp4 & temp9); |
|---|
| 105 | Equal =(temp3 & temp10); |
|---|
| 106 | temp11 =(u8bit[2] &~ u8bit[3]); |
|---|
| 107 | temp12 =(temp11 &~ temp1); |
|---|
| 108 | temp13 =(u8bit[5] &~ u8bit[4]); |
|---|
| 109 | temp14 =(u8bit[6] & u8bit[7]); |
|---|
| 110 | temp15 =(temp13 & temp14); |
|---|
| 111 | SQuote =(temp12 & temp15); |
|---|
| 112 | temp16 =(u8bit[4] | u8bit[5]); |
|---|
| 113 | temp17 =(temp7 &~ temp16); |
|---|
| 114 | DQuote =(temp12 & temp17); |
|---|
| 115 | temp18 =(temp4 & temp14); |
|---|
| 116 | Slash = (temp12 & temp18); |
|---|
| 117 | temp19 =(temp16 | temp5); |
|---|
| 118 | temp20 =(temp12 &~ temp19); |
|---|
| 119 | temp21 =(u8bit[2] | u8bit[3]); |
|---|
| 120 | temp22 =(temp1 | temp21); |
|---|
| 121 | temp23 =(temp10 &~ temp22); |
|---|
| 122 | temp24 =(temp20 | temp23); |
|---|
| 123 | temp25 =(u8bit[4] &~ u8bit[5]); |
|---|
| 124 | temp26 =(temp25 & temp9); |
|---|
| 125 | temp27 =(temp26 &~ temp22); |
|---|
| 126 | temp28 =(temp24 | temp27); |
|---|
| 127 | temp29 =(temp25 & temp7); |
|---|
| 128 | temp30 =(temp29 &~ temp22); |
|---|
| 129 | WS = (temp28 | temp30); |
|---|
| 130 | temp31 = (temp14 &~ temp16); |
|---|
| 131 | temp32 = (temp12 & temp31); |
|---|
| 132 | temp33 = (temp32 | Equal); |
|---|
| 133 | temp34 = (temp33 | Slash); |
|---|
| 134 | temp35 = (temp34 | RAngle); |
|---|
| 135 | temp36 = (temp35 | LAngle); |
|---|
| 136 | temp37 = (u8bit[1] &~ u8bit[0]); |
|---|
| 137 | temp38 = (u8bit[3] &~ u8bit[2]); |
|---|
| 138 | temp39 = (temp37 & temp38); |
|---|
| 139 | temp40 = (temp39 & temp6); |
|---|
| 140 | temp41 = (temp36 | temp40); |
|---|
| 141 | temp42 = (temp41 | DQuote); |
|---|
| 142 | temp43 = (temp42 | SQuote); |
|---|
| 143 | temp44 = (temp25 & temp14); |
|---|
| 144 | temp45 = (temp3 & temp44); |
|---|
| 145 | temp46 = (temp43 | temp45); |
|---|
| 146 | temp47 = (temp46 | temp20); |
|---|
| 147 | temp48 = (temp47 | temp27); |
|---|
| 148 | temp49 = (temp48 | temp30); |
|---|
| 149 | temp50 = (temp49 | temp23); |
|---|
| 150 | temp51 = (temp13 & temp7); |
|---|
| 151 | temp52 = (temp12 & temp51); |
|---|
| 152 | temp53 = (temp50 | temp52); |
|---|
| 153 | temp54 = (temp12 & temp6); |
|---|
| 154 | temp55 = (temp53 | temp54); |
|---|
| 155 | temp56 = (temp37 & temp2); |
|---|
| 156 | temp57 = (temp56 & temp6); |
|---|
| 157 | temp58 = (temp55 | temp57); |
|---|
| 158 | temp59 = (temp9 &~ temp16); |
|---|
| 159 | temp60 = (temp12 & temp59); |
|---|
| 160 | temp61 = (temp58 | temp60); |
|---|
| 161 | temp62 = (temp3 & temp18); |
|---|
| 162 | temp63 = (temp61 | temp62); |
|---|
| 163 | temp64 = (temp39 & temp10); |
|---|
| 164 | NameDelim = (temp63 | temp64); |
|---|
| 165 | |
|---|
| 166 | DQuoteDelim = DQuote | LAngle |
|---|
| 167 | SQuoteDelim = SQuote | LAngle |
|---|
| 168 | AttListDelim = Slash | RAngle |
|---|
| 169 | |
|---|
| 170 | LAngleFollow = bitutil.Advance(LAngle) |
|---|
| 171 | ElemNamePositions = LAngleFollow & ~Slash |
|---|
| 172 | EndTagSeconds = LAngleFollow & Slash |
|---|
| 173 | |
|---|
| 174 | ElemNameFollows = bitutil.ScanThru(ElemNamePositions, ~NameDelim) |
|---|
| 175 | #ElemNames = ElemNameFollows - ElemNamePositions |
|---|
| 176 | ParseError = ElemNamePositions & ElemNameFollows |
|---|
| 177 | |
|---|
| 178 | AttNameStarts = AllZero |
|---|
| 179 | AttNameFollows = AllZero |
|---|
| 180 | EqToCheck = AllZero |
|---|
| 181 | AttValStarts = AllZero |
|---|
| 182 | AttValEnds = AllZero |
|---|
| 183 | AttValFollows = AllZero |
|---|
| 184 | |
|---|
| 185 | AfterWS = bitutil.ScanThru(ElemNameFollows, WS) |
|---|
| 186 | AttListEnd = AfterWS & AttListDelim |
|---|
| 187 | AttNameStart = AfterWS & ~AttListDelim |
|---|
| 188 | ParseError |= ElemNameFollows & AttNameStart |
|---|
| 189 | |
|---|
| 190 | while AttNameStart > 0: |
|---|
| 191 | AttNameStarts |= AttNameStart |
|---|
| 192 | AttNameFollow = bitutil.ScanThru(AttNameStart, ~NameDelim) |
|---|
| 193 | AttNameFollows |= AttNameFollow |
|---|
| 194 | |
|---|
| 195 | # Scan through WS to the expected '=' delimiter. |
|---|
| 196 | EqExpected = bitutil.ScanThru(AttNameFollow, WS) |
|---|
| 197 | EqToCheck |= EqExpected |
|---|
| 198 | AttValPos = bitutil.ScanThru(bitutil.Advance(EqExpected), WS) |
|---|
| 199 | AttValStarts |= AttValPos |
|---|
| 200 | DQuoteAttVal = AttValPos & DQuote |
|---|
| 201 | SQuoteAttVal = AttValPos & SQuote |
|---|
| 202 | DQuoteAttEnd = bitutil.ScanThru(bitutil.Advance(DQuoteAttVal), ~DQuoteDelim) |
|---|
| 203 | SQuoteAttEnd = ScanThru(bitutil.Advance(SQuoteAttVal), ~SQuoteDelim) |
|---|
| 204 | AttValEnd = DQuoteAttEnd | SQuoteAttEnd |
|---|
| 205 | AttValEnds |= AttValEnd |
|---|
| 206 | AttValFollow = bitutil.Advance(AttValEnd) |
|---|
| 207 | AttValFollows |= AttValFollow |
|---|
| 208 | AfterWS = bitutil.ScanThru(AttValFollow, WS) |
|---|
| 209 | AttListEnd |= AfterWS & AttListDelim |
|---|
| 210 | AttNameStart = AfterWS & ~AttListDelim |
|---|
| 211 | |
|---|
| 212 | # No more attribute values to process when AttNameStart == 0. |
|---|
| 213 | |
|---|
| 214 | #AttNames = AttNameFollows - AttNameStarts |
|---|
| 215 | #AttVals = AttValFollows - AttValStarts |
|---|
| 216 | STagEnds = AttListEnd & RAngle |
|---|
| 217 | |
|---|
| 218 | # Mark any "/" characters found as the ends of empty element tags. |
|---|
| 219 | EmptyTagEnds = Advance(AttListEnd & Slash) |
|---|
| 220 | Tags = (STagEnds | EmptyTagEnds) - ElemNamePositions |
|---|
| 221 | |
|---|
| 222 | # Check for errors. |
|---|
| 223 | ParseError |= AttValFollows & AttNameStarts |
|---|
| 224 | ParseError |= AttNameStarts & AttNameFollows |
|---|
| 225 | ParseError |= EqToCheck & ~Equal |
|---|
| 226 | ParseError |= AttValStarts & ~ (DQuote | SQuote) |
|---|
| 227 | ParseError |= AttValEnds & ~ (DQuote | SQuote) |
|---|
| 228 | ParseError |= EmptyTagEnds & ~RAngle |
|---|
| 229 | |
|---|
| 230 | # End Tag Parsing |
|---|
| 231 | EndTagEnds = bitutil.ScanThru(bitutil.ScanThru(bitutil.Advance(EndTagSeconds), ~NameDelim), WS) |
|---|
| 232 | ParseError |= EndTagEnds &~ RAngle |
|---|
| 233 | error_mask=ParseError""" |
|---|
| 234 | s = Program().generate_code(s) |
|---|
| 235 | |
|---|
| 236 | #TODO: merge expr2simd() and a simplify_expr() |
|---|
| 237 | #TODO: there is some unnecesary code in output duplication that can be removed |
|---|
| 238 | #TODO: removing unreachable code is developed but is incomplete. Currently the code is not used. |
|---|
| 239 | #TODO: Support optimizing over subset of values |
|---|
| 240 | #TODO: A mechanism for programmer to let the compiler know about relations between bitstreams. Some relations might |
|---|
| 241 | # be possibly extracted automatically, but it might be expensive.Look at the optimize(maxtwo, allone) in the current example. |
|---|
| 242 | # it does not help at all, while it is an important case. This is because thecompiler can not extract all the information |
|---|
| 243 | # implied by the assumption maxtwo = allone. |
|---|
| 244 | #TODO: How variables redefined within a while loop should be dealt with for SSA generation? |
|---|
| 245 | #TODO: How variables redefined within a while loop should be dealt if there is an optimization on them? |
|---|
| 246 | #TODO: Numbering of temp variables generated by class BasicBlock |
|---|
| 247 | #TODO: Cross-BasicBlock use of common expressions in class BasicBlock |
|---|
| 248 | ####################################### |
|---|
| 249 | # Errors to consider and report to the programmer: |
|---|
| 250 | # 1- Optimizaing on a variable that does not exist |
|---|
| 251 | # 2- infinite while loop when the loop looks like this: while (AllOne>0) |
|---|
