1typedef unsigned long int unsigned_word; 2typedef signed long int signed_word; 3typedef unsigned_word word; 4 5typedef enum { ADD, ADD_CI, ADD_CO, ADD_CIO, SUB, SUB_CI, SUB_CO, 6SUB_CIO, ADC_CI, ADC_CO, ADC_CIO, AND, IOR, XOR, ANDC, IORC, EQV, 7NAND, NOR, AND_RC, IOR_RC, XOR_RC, ANDC_RC, IORC_RC, EQV_RC, NAND_RC, 8NOR_RC, AND_CC, IOR_CC, XOR_CC, ANDC_CC, IORC_CC, EQV_CC, NAND_CC, 9NOR_CC, LSHIFTR, ASHIFTR, SHIFTL, LSHIFTR_CO, ASHIFTR_CO, SHIFTL_CO, 10ROTATEL, ROTATEL_CO, ROTATEXL_CIO, ASHIFTR_CON, EXTS1, EXTS2, EXTU1, 11EXTU2, CLZ, CTZ, FF1, FF0, ABSVAL, NABSVAL, CMP, CPEQ, CPGE, CPGEU, 12CPGT, CPGTU, CPLE, CPLEU, CPLT, CPLTU, CPNEQ, CMPPAR, DOZ, COPY, 13EXCHANGE, COMCY, } opcode_t; 14 15typedef struct 16{ 17 opcode_t opcode:8; 18 unsigned int s1:8; 19 unsigned int s2:8; 20 unsigned int d:8; 21} insn_t; 22 23enum prune_flags 24{ 25 NO_PRUNE = 0, 26 CY_0 = 1, 27 CY_1 = 2, 28 CY_JUST_SET = 4, 29}; 30 31int flag_use_carry = 1; 32 33inline 34recurse(opcode_t opcode, 35 int d, 36 int s1, 37 int s2, 38 word v, 39 int cost, 40 insn_t *sequence, 41 int n_insns, 42 word *values, 43 int n_values, 44 const word goal_value, 45 int allowed_cost, 46 int cy, 47 int prune_flags) 48{ 49 insn_t insn; 50 51 allowed_cost -= cost; 52 53 if (allowed_cost > 0) 54 { 55 word old_d; 56 57 old_d = values[d]; 58 values[d] = v; 59 60 insn.opcode = opcode; 61 insn.s1 = s1; 62 insn.s2 = s2; 63 insn.d = d; 64 sequence[n_insns] = insn; 65 66 synth(sequence, n_insns + 1, values, n_values, 67 goal_value, allowed_cost, cy, prune_flags); 68 69 values[d] = old_d; 70 } 71 else if (goal_value == v) 72 { 73 insn.opcode = opcode; 74 insn.s1 = s1; 75 insn.s2 = s2; 76 insn.d = d; 77 sequence[n_insns] = insn; 78 test_sequence(sequence, n_insns + 1); 79 } 80} 81 82synth(insn_t *sequence, 83 int n_insns, 84 word *values, 85 int n_values, 86 word goal_value, 87 int allowed_cost, 88 int ci, 89 int prune_hint) 90{ 91 int s1, s2; 92 word v, r1, r2; 93 int co; 94 int last_dest; 95 96 if (n_insns > 0) 97 last_dest = sequence[n_insns - 1].d; 98 else 99 last_dest = -1; 100 if (ci >= 0 && flag_use_carry) 101 { 102 for (s1 = n_values - 1; s1 >= 0; s1--) 103 { 104 r1 = values[s1]; 105 for (s2 = s1 - 1; s2 >= 0; s2--) 106 { 107 r2 = values[s2]; 108 109 if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0) 110 { 111 if (last_dest >= 0 && s1 != last_dest && s2 != last_dest) 112 continue; 113 } 114 do { word __d = ( r1) + ( r2) + (( ci)); ( co) = ( ci) ? __d <= ( r1) : __d < ( r1); (v) = __d; } while (0); 115 recurse(ADD_CIO, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 116 do { word __d = ( r1) + ( r2) + (( ci)); ( co) = ( ci); (v) = __d; } while (0); 117 recurse(ADD_CI, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 118 119 do { word __d = ( r1) - ( r2) - (( ci)); ( co) = ( ci) ? __d >= ( r1) : __d > ( r1); (v) = __d; } while (0); 120 recurse(SUB_CIO, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 121 do { word __d = ( r2) - ( r1) - (( ci)); ( co) = ( ci) ? __d >= ( r2) : __d > ( r2); (v) = __d; } while (0); 122 recurse(SUB_CIO, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 123 124 do { word __d = ( r1) - ( r2) - (( ci)); ( co) = ( ci); (v) = __d; } while (0); 125 recurse(SUB_CI, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 126 do { word __d = ( r2) - ( r1) - (( ci)); ( co) = ( ci); (v) = __d; } while (0); 127 recurse(SUB_CI, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 128 129 } 130 } 131 } 132 for (s1 = n_values - 1; s1 >= 0; s1--) 133 { 134 r1 = values[s1]; 135 for (s2 = s1 - 1; s2 >= 0; s2--) 136 { 137 r2 = values[s2]; 138 139 if (allowed_cost <= 1) 140 { 141 if (last_dest >= 0 && s1 != last_dest && s2 != last_dest) 142 continue; 143 } 144 145 do { word __d = ( r1) + ( r2); ( co) = __d < ( r1); (v) = __d; } while (0); 146 recurse(ADD_CO, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 147 148 ((v) = ( r1) + ( r2), ( co) = ( ci)); 149 recurse(ADD, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 150 151 do { word __d = ( r1) - ( r2); ( co) = __d > ( r1); (v) = __d; } while (0); 152 recurse(SUB_CO, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 153 do { word __d = ( r2) - ( r1); ( co) = __d > ( r2); (v) = __d; } while (0); 154 recurse(SUB_CO, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 155 ((v) = ( r1) - ( r2), ( co) = ( ci)); 156 recurse(SUB, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 157 ((v) = ( r2) - ( r1), ( co) = ( ci)); 158 recurse(SUB, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 159 160 ((v) = ( r1) & ( r2), ( co) = ( ci)); 161 recurse(AND, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 162 163 ((v) = ( r1) | ( r2), ( co) = ( ci)); 164 recurse(IOR, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 165 166 ((v) = ( r1) ^ ( r2), ( co) = ( ci)); 167 recurse(XOR, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 168 169 ((v) = ( r1) & ~( r2), ( co) = ( ci)); 170 recurse(ANDC, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 171 ((v) = ( r2) & ~( r1), ( co) = ( ci)); 172 recurse(ANDC, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 173 ((v) = ( r1) | ~( r2), ( co) = ( ci)); 174 recurse(IORC, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 175 ((v) = ( r2) | ~( r1), ( co) = ( ci)); 176 recurse(IORC, n_values, s2, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 177 ((v) = ( r1) ^ ~( r2), ( co) = ( ci)); 178 recurse(EQV, n_values, s1, s2, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 179 180 } 181 } 182 if (ci >= 0 && flag_use_carry) 183 { 184 for (s1 = n_values - 1; s1 >= 0; s1--) 185 { 186 r1 = values[s1]; 187 188 if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0) 189 { 190 191 if (last_dest >= 0 && s1 != last_dest) 192 continue; 193 } 194 195 do { word __d = ( r1) + ( r1) + (( ci)); ( co) = ( ci) ? __d <= ( r1) : __d < ( r1); (v) = __d; } while (0); 196 recurse(ADD_CIO, n_values, s1, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 197 198 do { word __d = ( r1) + ( r1) + (( ci)); ( co) = ( ci); (v) = __d; } while (0); 199 recurse(ADD_CI, n_values, s1, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 200 201 do { word __d = ( r1) + ( -1 ) + (( ci)); ( co) = ( ci) ? __d <= ( r1) : __d < ( r1); (v) = __d; } while (0); 202 recurse(ADD_CIO, n_values, s1, (0x20 + -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 203 204 do { word __d = ( r1) + ( 0 ) + (( ci)); ( co) = ( ci) ? __d <= ( r1) : __d < ( r1); (v) = __d; } while (0); 205 recurse(ADD_CIO, n_values, s1, (0x20 + 0) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 206 do { word __d = ( 0 ) - ( r1) - (( ci)); ( co) = ( ci) ? __d >= ( 0 ) : __d > ( 0 ); (v) = __d; } while (0); 207 recurse(SUB_CIO, n_values, (0x20 + 0) , s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 208 209 } 210 } 211 for (s1 = n_values - 1; s1 >= 0; s1--) 212 { 213 r1 = values[s1]; 214 215 if (allowed_cost <= 1) 216 { 217 if (last_dest >= 0 && s1 != last_dest) 218 continue; 219 } 220 do { word __d = ( r1) + ( r1); ( co) = __d < ( r1); (v) = __d; } while (0); 221 recurse(ADD_CO, n_values, s1, s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 222 223 ((v) = ( r1) & ( 1 ), ( co) = ( ci)); 224 recurse(AND, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 225 226 ((v) = ( r1) ^ ( 1 ), ( co) = ( ci)); 227 recurse(XOR, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 228 229 ((v) = ( -1 ) - ( r1), ( co) = ( ci)); 230 recurse(SUB, n_values, (0x20 + -1) , s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 231 do { word __d = ( r1) + ( 1 ); ( co) = __d < ( r1); (v) = __d; } while (0); 232 recurse(ADD_CO, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 233 ((v) = ( r1) + ( 1 ), ( co) = ( ci)); 234 recurse(ADD, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 235 do { word __d = ( r1) + ( -1 ); ( co) = __d < ( r1); (v) = __d; } while (0); 236 recurse(ADD_CO, n_values, s1, (0x20 + -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 237 do { word __d = ( r1) - ( 1 ); ( co) = __d > ( r1); (v) = __d; } while (0); 238 recurse(SUB_CO, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 239 do { word __d = ( 0 ) - ( r1); ( co) = __d > ( 0 ); (v) = __d; } while (0); 240 recurse(SUB_CO, n_values, (0x20 + 0) , s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET); 241 ((v) = ( 0 ) - ( r1), ( co) = ( ci)); 242 recurse(SUB, n_values, (0x20 + 0) , s1, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 243 ((v) = ((unsigned_word) ( r1) >> (( 1 ) & (32 - 1)) ), ( co) = ( ci)); 244 recurse(LSHIFTR, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 245 ((v) = ((signed_word) ( r1) >> (( 1 ) & (32 - 1)) ), ( co) = ( ci)); 246 recurse(ASHIFTR, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 247 ((v) = ((signed_word) ( r1) << (( 1 ) & (32 - 1)) ), ( co) = ( ci)); 248 recurse(SHIFTL, n_values, s1, (0x20 + 1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 249 ((v) = ((unsigned_word) ( r1) >> (( 32 -1 ) & (32 - 1)) ), ( co) = ( ci)); 250 recurse(LSHIFTR, n_values, s1, (0x20 + 32 -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 251 ((v) = ((signed_word) ( r1) >> (( 32 -1 ) & (32 - 1)) ), ( co) = ( ci)); 252 recurse(ASHIFTR, n_values, s1, (0x20 + 32 -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 253 } 254 if (ci >= 0 && flag_use_carry 255 && (allowed_cost <= 1 ? ((prune_hint & CY_JUST_SET) != 0) : 1)) 256 { 257 do { word __d = ( 0 ) + ( 0 ) + (( ci)); ( co) = ( ci) ? __d <= ( 0 ) : __d < ( 0 ); (v) = __d; } while (0); 258 recurse(ADD_CIO, n_values, (0x20 + 0) , (0x20 + 0) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET | CY_0); 259 do { word __d = ( 0 ) - ( 0 ) - (( ci)); ( co) = ( ci) ? __d >= ( 0 ) : __d > ( 0 ); (v) = __d; } while (0); 260 recurse(SUB_CIO, n_values, (0x20 + 0) , (0x20 + 0) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 261 do { word __d = ( 0 ) - ( -1 ) - (( ci)); ( co) = ( ci) ? __d >= ( 0 ) : __d > ( 0 ); (v) = __d; } while (0); 262 recurse(SUB_CIO, n_values, (0x20 + 0) , (0x20 + -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, CY_JUST_SET | CY_1); 263 do { word __d = ( 0 ) + ( -1 ) + (( ci)); ( co) = ( ci) ? __d <= ( 0 ) : __d < ( 0 ); (v) = __d; } while (0); 264 recurse(ADD_CIO, n_values, (0x20 + 0) , (0x20 + -1) , v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 265 266 } 267 268 if (allowed_cost > 1) 269 { 270 ((v) = ( 0x80000000 ), ( co) = ( ci)); 271 recurse(COPY, n_values, (0x20 - 2) , 0, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 272 273 ((v) = ( -1 ), ( co) = ( ci)); 274 recurse(COPY, n_values, (0x20 + -1) , 0, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 275 276 ((v) = ( 1 ), ( co) = ( ci)); 277 recurse(COPY, n_values, (0x20 + 1) , 0, v, 1, sequence, n_insns, values, n_values + 1, goal_value, allowed_cost, co, prune_hint & ~CY_JUST_SET); 278 } 279} 280