-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathaha.h
executable file
·195 lines (171 loc) · 8.21 KB
/
aha.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
// 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, int) {return -x;}
int _not(int x, int, int) {return ~x;}
int pop(int xx, int, int) {
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, int) {
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, int) {
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) {return x + y;}
int sub (int x, int y, int) {return x - y;}
int mul (int x, int y, int) {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 div (int x, int y, int) {
if (y == 0 || (y == -1 && x == (int)0x80000000))
{unacceptable = 1; return 0;}
else return x/y;}
int divu(int x, int y, int) {
if (y == 0) {unacceptable = 1; return 0;}
else return (unsigned)x/(unsigned)y;}
int _and(int x, int y, int) {return x & y;}
int _or (int x, int y, int) {return x | y;}
int _xor(int x, int y, int) {return x ^ y;}
int rotl(int x, int y, int) {int s = y & NBSM;
return x << s | (unsigned)x >> (32 - s);}
int shl (int x, int y, int) {int s = y & NBSM;
if (s >= 32) return 0; else return x << s;}
int shr(int x, int y, int) {int s = y & NBSM;
if (s >= 32) return 0; else return (unsigned)x >> s;}
int shrs(int x, int y, int) {int s = y & NBSM;
if (s >= 32) return x >> 31; else return x >> s;}
int cmpeq(int x, int y, int) {return x == y;}
int cmplt(int x, int y, int) {return x < y;}
int cmpltu(int x, int y, int) {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.
{div, 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.