Skip to contentSkip to conversation

tcg: Use bitmaps for free temporaries

PATCH In review Richard Henderson 3 participants 7 messages Sep 19, 2013 – Dec 10, 2013

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 tcg: Use bitmaps for free temporaries

We previously allocated 32-bits per temp for the next_free_temp entry. We now allocate 4 bits per temp across the 4 bitmaps.

Using a linked list meant that if a translator is tweeked, resulting in temps being freed in a different order, that would have follow-on effects throughout the TB. Always allocating the lowest free temp means that follow-on effects are minimized, which can make it easier to diff output when debugging the translators.

---
 tcg/tcg.c | 32 +++++++++++++++-----------------
 tcg/tcg.h | 11 ++++++-----
 2 files changed, 21 insertions(+), 22 deletions(-)
tcg/tcg.c +15 -17
index fd7fb6b..41ed8b0 100644
@@ -316,11 +316,12 @@ void tcg_set_frame(TCGContext *s, int reg, intptr_t start, intptr_t size)
 
 void tcg_func_start(TCGContext *s)
 {
-    int i;
     tcg_pool_reset(s);
     s->nb_temps = s->nb_globals;
-    for(i = 0; i < (TCG_TYPE_COUNT * 2); i++)
-        s->first_free_temp[i] = -1;
+
+    /* No temps have been previously allocated for size or locality.  */
+    memset(s->free_temps, 0, sizeof(s->free_temps));
+
     s->labels = tcg_malloc(sizeof(TCGLabel) * TCG_MAX_LABELS);
     s->nb_labels = 0;
     s->current_frame_offset = s->frame_start;
@@ -468,16 +469,15 @@ static inline int tcg_temp_new_internal(TCGType type, int temp_local)
     TCGTemp *ts;
     int idx, k;
 
-    k = type;
-    if (temp_local)
-        k += TCG_TYPE_COUNT;
-    idx = s->first_free_temp[k];
-    if (idx != -1) {
-        /* There is already an available temp with the
-           right type */
+    k = type + (temp_local ? TCG_TYPE_COUNT : 0);
+    idx = find_first_bit(s->free_temps[k].l, TCG_MAX_TEMPS);
+    if (idx < TCG_MAX_TEMPS) {
+        /* There is already an available temp with the right type.  */
+        clear_bit(idx, s->free_temps[k].l);
+
         ts = &s->temps[idx];
-        s->first_free_temp[k] = ts->next_free_temp;
         ts->temp_allocated = 1;
+        assert(ts->base_type == type);
         assert(ts->temp_local == temp_local);
     } else {
         idx = s->nb_temps;
@@ -533,7 +533,7 @@ TCGv_i64 tcg_temp_new_internal_i64(int temp_local)
     return MAKE_TCGV_I64(idx);
 }
 
-static inline void tcg_temp_free_internal(int idx)
+static void tcg_temp_free_internal(int idx)
 {
     TCGContext *s = &tcg_ctx;
     TCGTemp *ts;
@@ -550,11 +550,9 @@ static inline void tcg_temp_free_internal(int idx)
     ts = &s->temps[idx];
     assert(ts->temp_allocated != 0);
     ts->temp_allocated = 0;
-    k = ts->base_type;
-    if (ts->temp_local)
-        k += TCG_TYPE_COUNT;
-    ts->next_free_temp = s->first_free_temp[k];
-    s->first_free_temp[k] = idx;
+
+    k = ts->type + (ts->temp_local ? TCG_TYPE_COUNT : 0);
+    set_bit(idx, s->free_temps[k].l);
 }
 
 void tcg_temp_free_i32(TCGv_i32 arg)
tcg/tcg.h +6 -5
index 902c751..c45e41b 100644
@@ -26,7 +26,7 @@
 #define TCG_H
 
 #include "qemu-common.h"
-
+#include "qemu/bitops.h"
 #include "tcg-target.h"
 
 /* Default target word size to pointer size.  */
@@ -400,8 +400,6 @@ typedef struct TCGTemp {
                                   basic blocks. Otherwise, it is not
                                   preserved across basic blocks. */
     unsigned int temp_allocated:1; /* never used for code gen */
-    /* index of next free temp of same base type, -1 if end */
-    int next_free_temp;
     const char *name;
 } TCGTemp;
 
@@ -412,6 +410,10 @@ typedef struct TCGHelperInfo {
 
 typedef struct TCGContext TCGContext;
 
+typedef struct TCGTempSet {
+    unsigned long l[BITS_TO_LONGS(TCG_MAX_TEMPS)];
+} TCGTempSet;
+
 struct TCGContext {
     uint8_t *pool_cur, *pool_end;
     TCGPool *pool_first, *pool_current, *pool_first_large;
@@ -419,8 +421,6 @@ struct TCGContext {
     int nb_labels;
     int nb_globals;
     int nb_temps;
-    /* index of free temps, -1 if none */
-    int first_free_temp[TCG_TYPE_COUNT * 2]; 
 
     /* goto_tb support */
     uint8_t *code_buf;
@@ -446,6 +446,7 @@ struct TCGContext {
 
     uint8_t *code_ptr;
     TCGTemp temps[TCG_MAX_TEMPS]; /* globals first, temps after */
+    TCGTempSet free_temps[TCG_TYPE_COUNT * 2];
 
     TCGHelperInfo *helpers;
     int nb_helpers;
Signature · 1 line
1.8.1.4
#1 lore raw

Ping?

r~

Quoted 134 lines · Richard Henderson

We previously allocated 32-bits per temp for the next_free_temp entry. We now allocate 4 bits per temp across the 4 bitmaps.

Using a linked list meant that if a translator is tweeked, resulting in temps being freed in a different order, that would have follow-on effects throughout the TB. Always allocating the lowest free temp means that follow-on effects are minimized, which can make it easier to diff output when debugging the translators.

---
 tcg/tcg.c | 32 +++++++++++++++-----------------
 tcg/tcg.h | 11 ++++++-----
 2 files changed, 21 insertions(+), 22 deletions(-)
tcg/tcg.c +15 -17
index fd7fb6b..41ed8b0 100644
@@ -316,11 +316,12 @@ void tcg_set_frame(TCGContext *s, int reg, intptr_t start, intptr_t size)
 
 void tcg_func_start(TCGContext *s)
 {
-    int i;
     tcg_pool_reset(s);
     s->nb_temps = s->nb_globals;
-    for(i = 0; i < (TCG_TYPE_COUNT * 2); i++)
-        s->first_free_temp[i] = -1;
+
+    /* No temps have been previously allocated for size or locality.  */
+    memset(s->free_temps, 0, sizeof(s->free_temps));
+
     s->labels = tcg_malloc(sizeof(TCGLabel) * TCG_MAX_LABELS);
     s->nb_labels = 0;
     s->current_frame_offset = s->frame_start;
@@ -468,16 +469,15 @@ static inline int tcg_temp_new_internal(TCGType type, int temp_local)
     TCGTemp *ts;
     int idx, k;
 
-    k = type;
-    if (temp_local)
-        k += TCG_TYPE_COUNT;
-    idx = s->first_free_temp[k];
-    if (idx != -1) {
-        /* There is already an available temp with the
-           right type */
+    k = type + (temp_local ? TCG_TYPE_COUNT : 0);
+    idx = find_first_bit(s->free_temps[k].l, TCG_MAX_TEMPS);
+    if (idx < TCG_MAX_TEMPS) {
+        /* There is already an available temp with the right type.  */
+        clear_bit(idx, s->free_temps[k].l);
+
         ts = &s->temps[idx];
-        s->first_free_temp[k] = ts->next_free_temp;
         ts->temp_allocated = 1;
+        assert(ts->base_type == type);
         assert(ts->temp_local == temp_local);
     } else {
         idx = s->nb_temps;
@@ -533,7 +533,7 @@ TCGv_i64 tcg_temp_new_internal_i64(int temp_local)
     return MAKE_TCGV_I64(idx);
 }
 
-static inline void tcg_temp_free_internal(int idx)
+static void tcg_temp_free_internal(int idx)
 {
     TCGContext *s = &tcg_ctx;
     TCGTemp *ts;
@@ -550,11 +550,9 @@ static inline void tcg_temp_free_internal(int idx)
     ts = &s->temps[idx];
     assert(ts->temp_allocated != 0);
     ts->temp_allocated = 0;
-    k = ts->base_type;
-    if (ts->temp_local)
-        k += TCG_TYPE_COUNT;
-    ts->next_free_temp = s->first_free_temp[k];
-    s->first_free_temp[k] = idx;
+
+    k = ts->type + (ts->temp_local ? TCG_TYPE_COUNT : 0);
+    set_bit(idx, s->free_temps[k].l);
 }
 
 void tcg_temp_free_i32(TCGv_i32 arg)
tcg/tcg.h +6 -5
index 902c751..c45e41b 100644
@@ -26,7 +26,7 @@
 #define TCG_H
 
 #include "qemu-common.h"
-
+#include "qemu/bitops.h"
 #include "tcg-target.h"
 
 /* Default target word size to pointer size.  */
@@ -400,8 +400,6 @@ typedef struct TCGTemp {
                                   basic blocks. Otherwise, it is not
                                   preserved across basic blocks. */
     unsigned int temp_allocated:1; /* never used for code gen */
-    /* index of next free temp of same base type, -1 if end */
-    int next_free_temp;
     const char *name;
 } TCGTemp;
 
@@ -412,6 +410,10 @@ typedef struct TCGHelperInfo {
 
 typedef struct TCGContext TCGContext;
 
+typedef struct TCGTempSet {
+    unsigned long l[BITS_TO_LONGS(TCG_MAX_TEMPS)];
+} TCGTempSet;
+
 struct TCGContext {
     uint8_t *pool_cur, *pool_end;
     TCGPool *pool_first, *pool_current, *pool_first_large;
@@ -419,8 +421,6 @@ struct TCGContext {
     int nb_labels;
     int nb_globals;
     int nb_temps;
-    /* index of free temps, -1 if none */
-    int first_free_temp[TCG_TYPE_COUNT * 2]; 
 
     /* goto_tb support */
     uint8_t *code_buf;
@@ -446,6 +446,7 @@ struct TCGContext {
 
     uint8_t *code_ptr;
     TCGTemp temps[TCG_MAX_TEMPS]; /* globals first, temps after */
+    TCGTempSet free_temps[TCG_TYPE_COUNT * 2];
 
     TCGHelperInfo *helpers;
     int nb_helpers;
#2 lore raw

Ping.

r~

Quoted 140 lines · Richard Henderson

Ping?

r~

Quoted 134 lines · Richard Henderson

We previously allocated 32-bits per temp for the next_free_temp entry. We now allocate 4 bits per temp across the 4 bitmaps.

Using a linked list meant that if a translator is tweeked, resulting in temps being freed in a different order, that would have follow-on effects throughout the TB. Always allocating the lowest free temp means that follow-on effects are minimized, which can make it easier to diff output when debugging the translators.

---
 tcg/tcg.c | 32 +++++++++++++++-----------------
 tcg/tcg.h | 11 ++++++-----
 2 files changed, 21 insertions(+), 22 deletions(-)
tcg/tcg.c +15 -17
index fd7fb6b..41ed8b0 100644
@@ -316,11 +316,12 @@ void tcg_set_frame(TCGContext *s, int reg, intptr_t start, intptr_t size)
 
 void tcg_func_start(TCGContext *s)
 {
-    int i;
     tcg_pool_reset(s);
     s->nb_temps = s->nb_globals;
-    for(i = 0; i < (TCG_TYPE_COUNT * 2); i++)
-        s->first_free_temp[i] = -1;
+
+    /* No temps have been previously allocated for size or locality.  */
+    memset(s->free_temps, 0, sizeof(s->free_temps));
+
     s->labels = tcg_malloc(sizeof(TCGLabel) * TCG_MAX_LABELS);
     s->nb_labels = 0;
     s->current_frame_offset = s->frame_start;
@@ -468,16 +469,15 @@ static inline int tcg_temp_new_internal(TCGType type, int temp_local)
     TCGTemp *ts;
     int idx, k;
 
-    k = type;
-    if (temp_local)
-        k += TCG_TYPE_COUNT;
-    idx = s->first_free_temp[k];
-    if (idx != -1) {
-        /* There is already an available temp with the
-           right type */
+    k = type + (temp_local ? TCG_TYPE_COUNT : 0);
+    idx = find_first_bit(s->free_temps[k].l, TCG_MAX_TEMPS);
+    if (idx < TCG_MAX_TEMPS) {
+        /* There is already an available temp with the right type.  */
+        clear_bit(idx, s->free_temps[k].l);
+
         ts = &s->temps[idx];
-        s->first_free_temp[k] = ts->next_free_temp;
         ts->temp_allocated = 1;
+        assert(ts->base_type == type);
         assert(ts->temp_local == temp_local);
     } else {
         idx = s->nb_temps;
@@ -533,7 +533,7 @@ TCGv_i64 tcg_temp_new_internal_i64(int temp_local)
     return MAKE_TCGV_I64(idx);
 }
 
-static inline void tcg_temp_free_internal(int idx)
+static void tcg_temp_free_internal(int idx)
 {
     TCGContext *s = &tcg_ctx;
     TCGTemp *ts;
@@ -550,11 +550,9 @@ static inline void tcg_temp_free_internal(int idx)
     ts = &s->temps[idx];
     assert(ts->temp_allocated != 0);
     ts->temp_allocated = 0;
-    k = ts->base_type;
-    if (ts->temp_local)
-        k += TCG_TYPE_COUNT;
-    ts->next_free_temp = s->first_free_temp[k];
-    s->first_free_temp[k] = idx;
+
+    k = ts->type + (ts->temp_local ? TCG_TYPE_COUNT : 0);
+    set_bit(idx, s->free_temps[k].l);
 }
 
 void tcg_temp_free_i32(TCGv_i32 arg)
tcg/tcg.h +6 -5
index 902c751..c45e41b 100644
@@ -26,7 +26,7 @@
 #define TCG_H
 
 #include "qemu-common.h"
-
+#include "qemu/bitops.h"
 #include "tcg-target.h"
 
 /* Default target word size to pointer size.  */
@@ -400,8 +400,6 @@ typedef struct TCGTemp {
                                   basic blocks. Otherwise, it is not
                                   preserved across basic blocks. */
     unsigned int temp_allocated:1; /* never used for code gen */
-    /* index of next free temp of same base type, -1 if end */
-    int next_free_temp;
     const char *name;
 } TCGTemp;
 
@@ -412,6 +410,10 @@ typedef struct TCGHelperInfo {
 
 typedef struct TCGContext TCGContext;
 
+typedef struct TCGTempSet {
+    unsigned long l[BITS_TO_LONGS(TCG_MAX_TEMPS)];
+} TCGTempSet;
+
 struct TCGContext {
     uint8_t *pool_cur, *pool_end;
     TCGPool *pool_first, *pool_current, *pool_first_large;
@@ -419,8 +421,6 @@ struct TCGContext {
     int nb_labels;
     int nb_globals;
     int nb_temps;
-    /* index of free temps, -1 if none */
-    int first_free_temp[TCG_TYPE_COUNT * 2]; 
 
     /* goto_tb support */
     uint8_t *code_buf;
@@ -446,6 +446,7 @@ struct TCGContext {
 
     uint8_t *code_ptr;
     TCGTemp temps[TCG_MAX_TEMPS]; /* globals first, temps after */
+    TCGTempSet free_temps[TCG_TYPE_COUNT * 2];
 
     TCGHelperInfo *helpers;
     int nb_helpers;
Reviewed-by on v1 1/1
#3 lore raw
In reply to Richard Henderson
Quoted 10 lines · Richard Henderson

We previously allocated 32-bits per temp for the next_free_temp entry. We now allocate 4 bits per temp across the 4 bitmaps.

Using a linked list meant that if a translator is tweeked, resulting in temps being freed in a different order, that would have follow-on effects throughout the TB. Always allocating the lowest free temp means that follow-on effects are minimized, which can make it easier to diff output when debugging the translators.

-- PMM

Reviewed-by on v1 1/1
#4 lore raw
In reply to Richard Henderson
Quoted 126 lines · Richard Henderson

We previously allocated 32-bits per temp for the next_free_temp entry. We now allocate 4 bits per temp across the 4 bitmaps.

Using a linked list meant that if a translator is tweeked, resulting in temps being freed in a different order, that would have follow-on effects throughout the TB. Always allocating the lowest free temp means that follow-on effects are minimized, which can make it easier to diff output when debugging the translators.

---
 tcg/tcg.c | 32 +++++++++++++++-----------------
 tcg/tcg.h | 11 ++++++-----
 2 files changed, 21 insertions(+), 22 deletions(-)
tcg/tcg.c +15 -17
index fd7fb6b..41ed8b0 100644
@@ -316,11 +316,12 @@ void tcg_set_frame(TCGContext *s, int reg, intptr_t start, intptr_t size)
 
 void tcg_func_start(TCGContext *s)
 {
-    int i;
     tcg_pool_reset(s);
     s->nb_temps = s->nb_globals;
-    for(i = 0; i < (TCG_TYPE_COUNT * 2); i++)
-        s->first_free_temp[i] = -1;
+
+    /* No temps have been previously allocated for size or locality.  */
+    memset(s->free_temps, 0, sizeof(s->free_temps));
+
     s->labels = tcg_malloc(sizeof(TCGLabel) * TCG_MAX_LABELS);
     s->nb_labels = 0;
     s->current_frame_offset = s->frame_start;
@@ -468,16 +469,15 @@ static inline int tcg_temp_new_internal(TCGType type, int temp_local)
     TCGTemp *ts;
     int idx, k;
 
-    k = type;
-    if (temp_local)
-        k += TCG_TYPE_COUNT;
-    idx = s->first_free_temp[k];
-    if (idx != -1) {
-        /* There is already an available temp with the
-           right type */
+    k = type + (temp_local ? TCG_TYPE_COUNT : 0);
+    idx = find_first_bit(s->free_temps[k].l, TCG_MAX_TEMPS);
+    if (idx < TCG_MAX_TEMPS) {
+        /* There is already an available temp with the right type.  */
+        clear_bit(idx, s->free_temps[k].l);
+
         ts = &s->temps[idx];
-        s->first_free_temp[k] = ts->next_free_temp;
         ts->temp_allocated = 1;
+        assert(ts->base_type == type);
         assert(ts->temp_local == temp_local);
     } else {
         idx = s->nb_temps;
@@ -533,7 +533,7 @@ TCGv_i64 tcg_temp_new_internal_i64(int temp_local)
     return MAKE_TCGV_I64(idx);
 }
 
-static inline void tcg_temp_free_internal(int idx)
+static void tcg_temp_free_internal(int idx)
 {
     TCGContext *s = &tcg_ctx;
     TCGTemp *ts;
@@ -550,11 +550,9 @@ static inline void tcg_temp_free_internal(int idx)
     ts = &s->temps[idx];
     assert(ts->temp_allocated != 0);
     ts->temp_allocated = 0;
-    k = ts->base_type;
-    if (ts->temp_local)
-        k += TCG_TYPE_COUNT;
-    ts->next_free_temp = s->first_free_temp[k];
-    s->first_free_temp[k] = idx;
+
+    k = ts->type + (ts->temp_local ? TCG_TYPE_COUNT : 0);
+    set_bit(idx, s->free_temps[k].l);
 }
 
 void tcg_temp_free_i32(TCGv_i32 arg)
tcg/tcg.h +5 -5
index 902c751..c45e41b 100644
@@ -26,7 +26,7 @@
 #define TCG_H
 
 #include "qemu-common.h"
-
+#include "qemu/bitops.h"
 #include "tcg-target.h"
 
 /* Default target word size to pointer size.  */
@@ -400,8 +400,6 @@ typedef struct TCGTemp {
                                   basic blocks. Otherwise, it is not
                                   preserved across basic blocks. */
     unsigned int temp_allocated:1; /* never used for code gen */
-    /* index of next free temp of same base type, -1 if end */
-    int next_free_temp;
     const char *name;
 } TCGTemp;
 
@@ -412,6 +410,10 @@ typedef struct TCGHelperInfo {
 
 typedef struct TCGContext TCGContext;
 
+typedef struct TCGTempSet {
+    unsigned long l[BITS_TO_LONGS(TCG_MAX_TEMPS)];
+} TCGTempSet;
+
 struct TCGContext {
     uint8_t *pool_cur, *pool_end;
     TCGPool *pool_first, *pool_current, *pool_first_large;
@@ -419,8 +421,6 @@ struct TCGContext {
     int nb_labels;
     int nb_globals;
     int nb_temps;
-    /* index of free temps, -1 if none */
-    int first_free_temp[TCG_TYPE_COUNT * 2]; 
 
     /* goto_tb support */
     uint8_t *code_buf;

tcg/tcg.h struct TCGContext { · line 452

Quoted 7 lines
tcg/tcg.h +1 -0
@@ -446,6 +446,7 @@ struct TCGContext {
 
     uint8_t *code_ptr;
     TCGTemp temps[TCG_MAX_TEMPS]; /* globals first, temps after */
+    TCGTempSet free_temps[TCG_TYPE_COUNT * 2];
 
     TCGHelperInfo *helpers;
     int nb_helpers;

It looks fine to me, though I don't know if it has any impact on the performances. find_first_bit() is calling find_next_bit() which is 87 instructions longs on x86_64. Maybe implementing find_first_bit() directly would help a bit there.

That said:

Signature · 2 lines
Aurelien Jarno	                        GPG: 1024D/F1BCDB73
[email protected]                 http://www.aurel32.net
#5 lore raw
Quoted 2 lines · Aurelien Jarno

It looks fine to me, though I don't know if it has any impact on the performances.

I couldn't measure any performance difference at all.

But for me, the improvement in debugging for the translators is important.

r~

#6 lore raw
Quoted 5 lines · Richard Henderson
Quoted 2 lines · Aurelien Jarno

It looks fine to me, though I don't know if it has any impact on the performances.

I couldn't measure any performance difference at all.

Ok great. Still in the long term we should provide a dedicated find_first_bit function that can be inlined, so that the compiler can do numerous optimizations in the case the size is known at compile time.

Quoted 2 lines

But for me, the improvement in debugging for the translators is important.

Yeah, I understand the point, that's why I gave a reviewed-by:

Aurelien

Signature · 2 lines
Aurelien Jarno                          GPG: 1024D/F1BCDB73
[email protected]                 http://www.aurel32.net