Hi,

This patch optimises the execution history tracking. With this patch and
execution history enabled, my linux is booting ~40 seconds faster (~10%).

ChangeLog:
* Optimise execution history tracking

nog.
-------------- next part --------------
--- cpu/or32/execute.c 2005-01-31 09:51:41.000000000 +0100
+++ ../or1ksim-ac/cpu/or32/execute.c 2005-01-31 09:21:00.000000000 +0100
@@ -104,6 +104,9 @@
* only used to get dump_exe_log correct */
static oraddr_t insn_ea;

+/* History of execution */
+struct hist_exec *hist_exec_tail = NULL;
+
/* Implementation specific.
Get an actual value of a specific register. */

@@ -377,12 +381,9 @@
memcpy (&icomplet[0], current, sizeof (struct iqueue_entry));

if (config.sim.history) {
- int i;
-
/* History of execution */
- for (i = HISTEXEC_LEN - 1; i; i--)
- histexec = histexec[i - 1];
- histexec[0] = icomplet[0].insn_addr; /* add last insn */
+ hist_exec_tail = hist_exec_tail->next;
+ hist_exec_tail->addr = icomplet[0].insn_addr;
}

if (config.sim.exe_log) dump_exe_log();
@@ -603,6 +604,9 @@
void cpu_reset()
{
int i;
+ struct hist_exec *hist_exec_head = NULL;
+ struct hist_exec *hist_exec_new;
+
runtime.sim.cycles = 0;
runtime.sim.loadcycles = 0;
runtime.sim.storecycles = 0;
@@ -619,6 +623,25 @@
sbuf_count = 0;
sbuf_prev_cycles = 0;

+ /* Initialise execution history circular buffer */
+ for (i = 0; i + hist_exec_new = malloc(sizeof(struct hist_exec));
+ if(!hist_exec_new) {
+ fprintf(stderr, "Out-of-memory\n");
+ exit(1);
+ }
+ if(!hist_exec_head)
+ hist_exec_head = hist_exec_new;
+ else
+ hist_exec_tail->next = hist_exec_new;
+
+ hist_exec_new->prev = hist_exec_tail;
+ hist_exec_tail = hist_exec_new;
+ }
+ /* Make hist_exec_tail->next point to hist_exec_head */
+ hist_exec_tail->next = hist_exec_head;
+ hist_exec_head->prev = hist_exec_tail;
+
/* Cpu configuration */
mtspr(SPR_UPR, config.cpu.upr);
setsprbits(SPR_VR, SPR_VR_VER, config.cpu.ver);
--- cpu/common/abstract.h 2005-01-31 09:51:36.000000000 +0100
+++ ../or1ksim-ac/cpu/common/abstract.h 2005-01-31 09:24:39.000000000 +0100
@@ -166,5 +166,10 @@

/* History of execution */
#define HISTEXEC_LEN 200
-extern int histexec[HISTEXEC_LEN];
+struct hist_exec {
+ oraddr_t addr;
+ struct hist_exec *prev;
+ struct hist_exec *next;
+};

+extern struct hist_exec *hist_exec_tail;
--- toplevel.c 2005-01-31 09:51:42.000000000 +0100
+++ ../or1ksim-ac/toplevel.c 2005-01-31 09:56:55.000000000 +0100
@@ -84,9 +84,6 @@
/* CVS revision number. */
const char rcsrev[] = "$Revision: 1.100 $";

-/* History of execution */
-int histexec[HISTEXEC_LEN];
-
char *sim_commands [] = {
"q", "t", "help", "de", "dm", "run", "pr", "pm", "pc",
"reset", "break", "breaks", "hist", "stats", "stall" "info",
@@ -706,8 +704,9 @@
#endif
if (strcmp(item1, "hist") == 0) { /* dump history */
int i;
- for(i = HISTEXEC_LEN; i; i--)
- dumpmemory(histexec[i - 1], histexec[i - 1] + 4, 1, 1);
+ struct hist_exec *cur;
+ for(i = HISTEXEC_LEN, cur = hist_exec_tail->prev; i; i--, cur = cur->prev)
+ dumpmemory(cur->addr, cur->addr + 4, 1, 1);
PRINTF("\n");
} else
if (strcmp(item1, "run") == 0) { /* run */

* György 'nog' Jeney (nog@sdf.lonestar.org) wrote:

I agree with the circular buffer approach (defenetly better than than
'shift all'), but if you're doing the
change for performance reasons i think that the pointer-less
approach would be faster. I'm thinking about an array
with beginning and end indeces... I you feel like doing that great, but i
do not mind the implemented approach either... so after the new #7 goes in
this one should too...

best regards,
p.

I was aiming at having a condition-less implementation, tho I have no evidence
that this is any faster, so I'll implement an array-style circular buffer, and
see which is faster.

nog.

Here's an implementation useing an array-style circular buffer. I have done
some benchmarks on the two implementations, running linux until the ramdisk was
loaded:

With linked-list style circular buffer: 9m54.875s
With array style circular buffer: 10m14.355s

Not much between them, so take your pick...

nog.
-------------- next part --------------
--- cpu/common/abstract.h 2005-02-01 16:15:38.000000000 +0100
+++ ../or1ksim-ac/cpu/common/abstract.h 2005-02-01 16:16:50.000000000 +0100
@@ -166,5 +166,9 @@

/* History of execution */
#define HISTEXEC_LEN 200
-extern int histexec[HISTEXEC_LEN];
+struct hist_exec {
+ oraddr_t addr[HISTEXEC_LEN];
+ unsigned int last;
+};

+extern struct hist_exec hist_exec;
--- cpu/or32/execute.c 2005-02-01 16:15:45.000000000 +0100
+++ ../or1ksim-ac/cpu/or32/execute.c 2005-02-01 16:17:28.000000000 +0100
@@ -104,6 +104,9 @@
* only used to get dump_exe_log correct */
static oraddr_t insn_ea;

+/* History of execution */
+struct hist_exec hist_exec;
+
/* Implementation specific.
Get an actual value of a specific register. */

@@ -377,12 +381,10 @@
memcpy (&icomplet[0], current, sizeof (struct iqueue_entry));

if (config.sim.history) {
- int i;
-
/* History of execution */
- for (i = HISTEXEC_LEN - 1; i; i--)
- histexec = histexec[i - 1];
- histexec[0] = icomplet[0].insn_addr; /* add last insn */
+ if(++hist_exec.last == HISTEXEC_LEN)
+ hist_exec.last = 0;
+ hist_exec.addr[hist_exec.last] = icomplet[0].insn_addr;
}

if (config.sim.exe_log) dump_exe_log();
@@ -619,6 +624,10 @@
sbuf_count = 0;
sbuf_prev_cycles = 0;

+ /* Initialise execution history circular buffer */
+ memset(hist_exec.addr, 0, sizeof(oraddr_t) * HISTEXEC_LEN);
+ hist_exec.last = 0;
+
/* Cpu configuration */
mtspr(SPR_UPR, config.cpu.upr);
setsprbits(SPR_VR, SPR_VR_VER, config.cpu.ver);
--- toplevel.c 2005-01-27 14:51:51.000000000 +0100
+++ /home/nog/or1ksim-test/toplevel.c 2005-02-01 16:19:49.000000000 +0100
@@ -78,9 +84,6 @@
/* CVS revision number. */
const char rcsrev[] = "$Revision: 1.100 $";

-/* History of execution */
-int histexec[HISTEXEC_LEN];
-
char *sim_commands [] = {
"q", "t", "help", "de", "dm", "run", "pr", "pm", "pc",
"reset", "break", "breaks", "hist", "stats", "stall" "info",
@@ -700,8 +703,12 @@
#endif
if (strcmp(item1, "hist") == 0) { /* dump history */
int i;
- for(i = HISTEXEC_LEN; i; i--)
- dumpmemory(histexec[i - 1], histexec[i - 1] + 4, 1, 1);
+ i = hist_exec.last;
+ do {
+ if(++i == HISTEXEC_LEN)
+ i = 0;
+ dumpmemory(hist_exec.addr, hist_exec.addr + 1, 1, 1);
+ } while(i != hist_exec.last);
PRINTF("\n");
} else
if (strcmp(item1, "run") == 0) { /* run */

* György 'nog' Jeney (nog@sdf.lonestar.org) wrote:

Here's an implementation useing an array-style circular buffer. I have done
some benchmarks on the two implementations, running linux until the ramdisk was
loaded:

With linked-list style circular buffer: 9m54.875s
With array style circular buffer: 10m14.355s