src/cpus/experiment_arm_multi.c

/*
 *  Copyright (C) 2005-2007  Anders Gavare.  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are met:
 *
 *  1. Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *  2. Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *  3. The name of the author may not be used to endorse or promote products
 *     derived from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 *  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 *  ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 *  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 *  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 *  OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 *  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 *  OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 *  SUCH DAMAGE.
 *
 *
 *  $Id: experiment_arm_multi.c,v 1.2 2006/12/30 13:30:55 debug Exp $
 *
 *  Given a list of common ARM load/store multiple opcodes, figure out (using 
 *  simple brute force), which n bits (where n is low, e.g. 7) that cause the
 *  best separation of the 24 bit opcode space into linear lists, where "best"
 *  means to optimize the length of the longest such linear list.
 *
 *  The result is a set of bits, such as this:
 *
 *        xxxx100P USWLnnnn llllllll llllllll
 *               ^ ^ ^^       ^^    (in this case, n = 6)
 *
 *  (it's a 24-bit space, because the s-bit isn't used).
 */

#include <stdio.h>
#include <stdlib.h>


int bit_count(unsigned int x)
{
        static const int c[16] = { 0,1,1,2, 1,2,2,3, 1,2,2,3, 2,3,3,4 };
        return c[x & 15] + c[(x>>4) & 15] +
            c[(x>>8) & 15] + c[(x>>12) & 15] +
            c[(x>>16) & 15] + c[(x>>20) & 15] +
            c[(x>>24) & 15] + c[(x>>28) & 15];
}


int cmpfunc(const void *a, const void *b)
{
        int *pa = (int *) a, *pb = (int *) b;
        if (*pa < *pb)
                return -1;
        if (*pa > *pb)
                return  1;
        return 0;
}


int calc_max_list_length(int *opcodes, int *tmp_table,
        int n_opcodes, int bit_mask)
{
        int i, maxlen, curlen;

        for (i=0; i<n_opcodes; i++)
                tmp_table[i] = opcodes[i] & bit_mask;

        qsort(tmp_table, n_opcodes, sizeof(int), cmpfunc);
        curlen = maxlen = 1;

        for (i=1; i<n_opcodes; i++)
                if (tmp_table[i] == tmp_table[i-1]) {
                        curlen ++;
                        if (curlen > maxlen)
                                maxlen = curlen;
                } else
                        curlen = 1;

        return maxlen;
}


int main(int argc, char *argv[])
{
        FILE *f = fopen("cpu_arm_multi.txt", "r");
        int n;
        const int max = 10000;
        int opcode[max];
        int tmp_table[max];
        int n_opcodes = 0;
        int *max_len;
        int bit_mask, best_bit_mask, best_bit_mask_len;

        if (argc < 2) {
                fprintf(stderr, "usage: %s n\n", argv[0]);
                fprintf(stderr, "where n=6 might be a good choice\n");
                exit(1);
        }

        n = atoi(argv[1]);

        if (f == NULL) {
                fprintf(stderr, "could not open cpu_arm_multi.txt\n");
                exit(1);
        }

        /*  Read the opcodes:  */
        while (!feof(f)) {
                char s[100];
                s[0] = s[sizeof(s)-1] = '\0';
                fgets(s, sizeof(s), f);
                if (s[0] == '0') {
                        if (n_opcodes > max) {
                                fprintf(stderr, "too many opcodes\n");
                                exit(1);
                        }
                        opcode[n_opcodes++] = strtol(s, NULL, 0);
                }
        }

        printf("nr of opcodes = %i\n", n_opcodes);

        max_len = malloc(sizeof(int) * (1 << 25));
        if (max_len == NULL) {
                fprintf(stderr, "out of memory\n");
                exit(1);
        }

        best_bit_mask_len = -1;

        for (bit_mask = 0; bit_mask <= 0x01ffffff; bit_mask ++) {
                /*  Skip the s-bit:  */
                if (bit_mask & 0x00400000)
                        continue;

                if (bit_count(bit_mask) != n)
                        continue;

                /*  Calculate the max list length for this bit_mask:  */
                max_len[bit_mask] = calc_max_list_length(opcode,
                    tmp_table, n_opcodes, bit_mask);

                if (best_bit_mask_len == -1 ||
                    max_len[bit_mask] < best_bit_mask_len) {
                        best_bit_mask_len = max_len[bit_mask];
                        best_bit_mask = bit_mask;
                        printf("best bit_mask so far: 0x%08x: %i\n",
                            best_bit_mask, best_bit_mask_len);
                }
        }

        return 0;
}

1	/*
2	* Copyright (C) 2005-2007 Anders Gavare. All rights reserved.
3	*
4	* Redistribution and use in source and binary forms, with or without
5	* modification, are permitted provided that the following conditions are met:
6	*
7	* 1. Redistributions of source code must retain the above copyright
8	* notice, this list of conditions and the following disclaimer.
9	* 2. Redistributions in binary form must reproduce the above copyright
10	* notice, this list of conditions and the following disclaimer in the
11	* documentation and/or other materials provided with the distribution.
12	* 3. The name of the author may not be used to endorse or promote products
13	* derived from this software without specific prior written permission.
14	*
15	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18	* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25	* SUCH DAMAGE.
26	*
27	*
28	* $Id: experiment_arm_multi.c,v 1.2 2006/12/30 13:30:55 debug Exp $
29	*
30	* Given a list of common ARM load/store multiple opcodes, figure out (using
31	* simple brute force), which n bits (where n is low, e.g. 7) that cause the
32	* best separation of the 24 bit opcode space into linear lists, where "best"
33	* means to optimize the length of the longest such linear list.
34	*
35	* The result is a set of bits, such as this:
36	*
37	* xxxx100P USWLnnnn llllllll llllllll
38	* ^ ^ ^^ ^^ (in this case, n = 6)
39	*
40	* (it's a 24-bit space, because the s-bit isn't used).
41	*/
42
43	#include <stdio.h>
44	#include <stdlib.h>
45
46
47	int bit_count(unsigned int x)
48	{
49	static const int c[16] = { 0,1,1,2, 1,2,2,3, 1,2,2,3, 2,3,3,4 };
50	return c[x & 15] + c[(x>>4) & 15] +
51	c[(x>>8) & 15] + c[(x>>12) & 15] +
52	c[(x>>16) & 15] + c[(x>>20) & 15] +
53	c[(x>>24) & 15] + c[(x>>28) & 15];
54	}
55
56
57	int cmpfunc(const void a, const void b)
58	{
59	int pa = (int ) a, pb = (int ) b;
60	if (pa < pb)
61	return -1;
62	if (pa > pb)
63	return 1;
64	return 0;
65	}
66
67
68	int calc_max_list_length(int opcodes, int tmp_table,
69	int n_opcodes, int bit_mask)
70	{
71	int i, maxlen, curlen;
72
73	for (i=0; i<n_opcodes; i++)
74	tmp_table[i] = opcodes[i] & bit_mask;
75
76	qsort(tmp_table, n_opcodes, sizeof(int), cmpfunc);
77	curlen = maxlen = 1;
78
79	for (i=1; i<n_opcodes; i++)
80	if (tmp_table[i] == tmp_table[i-1]) {
81	curlen ++;
82	if (curlen > maxlen)
83	maxlen = curlen;
84	} else
85	curlen = 1;
86
87	return maxlen;
88	}
89
90
91	int main(int argc, char *argv[])
92	{
93	FILE *f = fopen("cpu_arm_multi.txt", "r");
94	int n;
95	const int max = 10000;
96	int opcode[max];
97	int tmp_table[max];
98	int n_opcodes = 0;
99	int *max_len;
100	int bit_mask, best_bit_mask, best_bit_mask_len;
101
102	if (argc < 2) {
103	fprintf(stderr, "usage: %s n\n", argv[0]);
104	fprintf(stderr, "where n=6 might be a good choice\n");
105	exit(1);
106	}
107
108	n = atoi(argv[1]);
109
110	if (f == NULL) {
111	fprintf(stderr, "could not open cpu_arm_multi.txt\n");
112	exit(1);
113	}
114
115	/* Read the opcodes: */
116	while (!feof(f)) {
117	char s[100];
118	s[0] = s[sizeof(s)-1] = '\0';
119	fgets(s, sizeof(s), f);
120	if (s[0] == '0') {
121	if (n_opcodes > max) {
122	fprintf(stderr, "too many opcodes\n");
123	exit(1);
124	}
125	opcode[n_opcodes++] = strtol(s, NULL, 0);
126	}
127	}
128
129	printf("nr of opcodes = %i\n", n_opcodes);
130
131	max_len = malloc(sizeof(int) * (1 << 25));
132	if (max_len == NULL) {
133	fprintf(stderr, "out of memory\n");
134	exit(1);
135	}
136
137	best_bit_mask_len = -1;
138
139	for (bit_mask = 0; bit_mask <= 0x01ffffff; bit_mask ++) {
140	/* Skip the s-bit: */
141	if (bit_mask & 0x00400000)
142	continue;
143
144	if (bit_count(bit_mask) != n)
145	continue;
146
147	/* Calculate the max list length for this bit_mask: */
148	max_len[bit_mask] = calc_max_list_length(opcode,
149	tmp_table, n_opcodes, bit_mask);
150
151	if (best_bit_mask_len == -1 \|\|
152	max_len[bit_mask] < best_bit_mask_len) {
153	best_bit_mask_len = max_len[bit_mask];
154	best_bit_mask = bit_mask;
155	printf("best bit_mask so far: 0x%08x: %i\n",
156	best_bit_mask, best_bit_mask_len);
157	}
158	}
159
160	return 0;
161	}
162