| // Copyright (C) 2002 by Henry S. Warren, Jr. |
| const int debug = 0; // 0 or 1; debugging printouts if 1. |
| const int counters = 1; // 0 or 1; count number of evaluations. |
| #define NARGS 1 // Number of args in userfun, 1 or 2. |
| |
| /* A note about the registers: |
| |
| They are divided into four groups. The first group, starting with |
| register 0, holds ordinary immediate values. The second group, starting |
| with register NIM, holds the shift immediate values. The next 1 or 2 |
| regs are the arguments to the user-defined function. The last group |
| holds the results of computations done by the trial programs. |
| |
| 0 Start of ordinary immediate values (those given by IMMEDS) |
| NIM Start of shift immediate values (those given by SHIMMEDS) |
| RX First (or only) user function argument |
| RY Second user function argument |
| RI0 Result of instruction 0 goes here |
| RI0 + i Result of instruction i goes here |
| where: |
| NIM = number of ordinary immediate values |
| NSHIM = number of shift immediate values |
| */ |
| |
| #define MAXNEG 0x80000000 |
| #define MAXPOS 0x7FFFFFFF |
| #define NBSM 63 // Shift mask. Use 63 for mod 64 |
| // shifts, or 31 for mod 32. |
| |
| int trialx[] = {1, 0, -1, MAXNEG, MAXPOS, \ |
| MAXNEG + 1, MAXPOS - 1, 0x01234567, 0x89ABCDEF, -2, 2, -3, 3, \ |
| -64, 64, -5, -31415}; |
| #if NARGS == 2 |
| int trialy[] = {0}; |
| #endif |
| // First three values of IMMEDS must be 0, -1, and 1. |
| #define IMMEDS 0, -1, 1, MAXNEG, -2, 2, 3 |
| #define SHIMMEDS 1, 2, 30, 31 |
| |
| int dummy1[] = {IMMEDS}; // These get optimized out of existence. |
| int dummy2[] = {SHIMMEDS}; |
| |
| #define NIM (int)(sizeof(dummy1)/sizeof(dummy1[0])) |
| #define NSHIM (int)(sizeof(dummy2)/sizeof(dummy2[0])) |
| #define RX (NIM + NSHIM) // First (or only) user function argument |
| #define RY (RX + 1) // Second user function argument |
| #define RI0 (RX + NARGS) // Result of instruction 0 goes here |
| |
| int unacceptable; // Code below sets this to 1 for an |
| // unacceptable operation, such as |
| // divide by 0. It is initially 0. |
| |
| /* Collection of simulator routines for the instructions in the isa. */ |
| int neg(int x, int y, int z) {return -x;} |
| int Not(int x, int y, int z) {return ~x;} |
| int pop(int xx, int y, int z) { |
| unsigned x = xx; |
| x = x - ((x >> 1) & 0x55555555); |
| x = (x & 0x33333333) + ((x >> 2) & 0x33333333); |
| x = (x + (x >> 4)) & 0x0F0F0F0F; |
| x = x + (x << 8); |
| x = x + (x << 16); |
| return x >> 24; |
| } |
| |
| int nlz(int xx, int y, int z) { |
| unsigned x = xx; |
| int n; |
| |
| if (x == 0) return(32); |
| n = 0; |
| if (x <= 0x0000FFFF) {n = n +16; x = x <<16;} |
| if (x <= 0x00FFFFFF) {n = n + 8; x = x << 8;} |
| if (x <= 0x0FFFFFFF) {n = n + 4; x = x << 4;} |
| if (x <= 0x3FFFFFFF) {n = n + 2; x = x << 2;} |
| if (x <= 0x7FFFFFFF) {n = n + 1;} |
| return n; |
| } |
| |
| int rev(int xi, int y, int z) { |
| unsigned x = xi; |
| x = (x & 0x55555555) << 1 | ((x >> 1) & 0x55555555); |
| x = (x & 0x33333333) << 2 | ((x >> 2) & 0x33333333); |
| x = (x & 0x0F0F0F0F) << 4 | ((x >> 4) & 0x0F0F0F0F); |
| x = (x << 24) | ((x & 0xFF00) << 8) | |
| ((x >> 8) & 0xFF00) | (x >> 24); |
| return x; |
| } |
| |
| int add (int x, int y, int z) {return x + y;} |
| int sub (int x, int y, int z) {return x - y;} |
| int mul (int x, int y, int z) {return x * y;} |
| /* For division overflow we return arbitrary values, hoping they fail |
| to be part of a solution. (User must check solutions, in general.) */ |
| int divide (int x, int y, int z) { |
| if (y == 0 || (y == -1 && x == (int)0x80000000)) |
| {unacceptable = 1; return 0;} |
| else return x/y;} |
| int divu(int x, int y, int z) { |
| if (y == 0) {unacceptable = 1; return 0;} |
| else return (unsigned)x/(unsigned)y;} |
| int And(int x, int y, int z) {return x & y;} |
| int Or (int x, int y, int z) {return x | y;} |
| int Xor(int x, int y, int z) {return x ^ y;} |
| int rotl(int x, int y, int z) {int s = y & NBSM; |
| return x << s | (unsigned)x >> (32 - s);} |
| int shl (int x, int y, int z) {int s = y & NBSM; |
| if (s >= 32) return 0; else return x << s;} |
| int shr(int x, int y, int z) {int s = y & NBSM; |
| if (s >= 32) return 0; else return (unsigned)x >> s;} |
| int shrs(int x, int y, int z) {int s = y & NBSM; |
| if (s >= 32) return x >> 31; else return x >> s;} |
| int cmpeq(int x, int y, int z) {return x == y;} |
| int cmplt(int x, int y, int z) {return x < y;} |
| int cmpltu(int x, int y, int z) {return (unsigned)(x) < (unsigned)(y);} |
| int seleq(int x, int y, int z) {return x == 0 ? y : z;} |
| int sellt(int x, int y, int z) {return x < 0 ? y : z;} |
| int selle(int x, int y, int z) {return x <= 0 ? y : z;} |
| |
| // The machine's instruction set: |
| // Note: Commutative ops are commutative in operands 0 and 1. |
| struct { |
| int (*proc)(int, int, int); // Procedure for simulating the op. |
| int numopnds; // Number of operands, 1 to 3. |
| int commutative; // 1 if opnds 0 and 1 commutative. |
| int opndstart[3]; // Starting reg no. for each operand. |
| char *mnemonic; // Name of op, for printing. |
| char *fun_name; // Function name, for printing. |
| char *op_name; // Operator name, for printing. |
| } isa[] = { |
| {neg, 1, 0, {RX, 0, 0}, "neg", "-(", "" }, // Negate. |
| {Not, 1, 0, {RX, 0, 0}, "not", "~(", "" }, // One's-complement. |
| // {pop, 1, 0, {RX, 0, 0}, "pop", "pop(", "" }, // Population count. |
| // {nlz, 1, 0, {RX, 0, 0}, "nlz", "nlz(", "" }, // Num leading 0's. |
| // {rev, 1, 0, {RX, 0, 0}, "rev", "rev(", "" }, // Bit reversal. |
| {add, 2, 1, {RX, 2, 0}, "add", "(", " + " }, // Add. |
| {sub, 2, 0, { 2, 2, 0}, "sub", "(", " - " }, // Subtract. |
| {mul, 2, 1, {RX, 3, 0}, "mul", "(", "*" }, // Multiply. |
| {divide, 2, 0, { 1, 3, 0}, "div", "(", "/" }, // Divide signed. |
| {divu, 2, 0, { 1, 1, 0}, "divu", "(", " /u " }, // Divide unsigned. |
| {And, 2, 1, {RX, 2, 0}, "and", "(", " & " }, // AND. |
| {Or, 2, 1, {RX, 2, 0}, "or", "(", " | " }, // OR. |
| {Xor, 2, 1, {RX, 2, 0}, "xor", "(", " ^ " }, // XOR. |
| // {rotl, 2, 0, { 1,NIM, 0}, "rotl", "(", " <<r "}, // Rotate shift left. |
| {shl, 2, 0, { 1,NIM, 0}, "shl", "(", " << " }, // Shift left. |
| {shr, 2, 0, { 1,NIM, 0}, "shr", "(", " >>u "}, // Shift right. |
| {shrs, 2, 0, { 3,NIM, 0}, "shrs", "(", " >>s "}, // Shift right signed. |
| // {cmpeq, 2, 1, {RX, 0, 0}, "cmpeq", "(", " == " }, // Compare equal. |
| // {cmplt, 2, 0, { 0, 0, 0}, "cmplt", "(", " < " }, // Compare less than. |
| // {cmpltu, 2, 0, { 1, 1, 0}, "cmpltu","(", " <u " }, // Compare less than unsigned. |
| // {seleq, 3, 0, {RX, 0, 0}, "seleq", "seleq(", ", " }, // Select if = 0. |
| // {sellt, 3, 0, {RX, 0, 0}, "sellt", "sellt(", ", " }, // Select if < 0. |
| // {selle, 3, 0, {RX, 0, 0}, "selle", "selle(", ", " }, // Select if <= 0. |
| }; |
| |
| /* ------------------- End of user-setup Portion -------------------- */ |
| |
| #define MAXNUMI 5 // Max num of insns that can be tried. |
| #if NARGS == 1 |
| int userfun(int); |
| #else |
| int userfun(int, int); |
| #endif |
| |
| #define NTRIALX (int)(sizeof(trialx)/sizeof(trialx[0])) |
| #define NTRIALY (int)(sizeof(trialy)/sizeof(trialy[0])) |
| |
| #if NARGS == 1 |
| int correct_result[NTRIALX]; |
| #else |
| int correct_result[NTRIALX][NTRIALY]; |
| #endif |
| |
| int corr_result; // Correct result for current trial. |
| |
| #define NUM_INSNS_IN_ISA (int)(sizeof(isa)/sizeof(isa[0])) |
| |
| struct { // The current program. |
| int op; // Index into isa. |
| int opnd[3]; // Operands of op. Register numbers |
| // except if negative, it's the negative |
| // of a shift amount. |
| } pgm[MAXNUMI]; |
| |
| int numi; // Current size of the trial programs, |
| // must be from 1 to MAXNUMI. |
| |
| /* GPR array: First NIM slots hold ordinary immediate values (IMMEDS), |
| next NSHIM slots hold shift immediate values (SHIMMEDS), next NARGS |
| slots hold the arguments x and, optionally, y, and the last numi slots |
| hold the result of instructions 0 through numi - 1. */ |
| |
| int r[NIM + NSHIM + NARGS + MAXNUMI] = {IMMEDS, SHIMMEDS}; |
| unsigned counter[MAXNUMI]; // Count num times insn at level i is |
| // evaluated. |