|
From: <sv...@va...> - 2015-04-03 20:47:47
|
Author: sewardj
Date: Fri Apr 3 21:47:38 2015
New Revision: 3117
Log:
amd64 ncode generation: switch from using temporary HRegSet to the
new bitmap-based real-regs-only RRegSet. Remove HRegSet entirely.
Modified:
branches/NCODE/priv/host_amd64_defs.c
branches/NCODE/priv/host_amd64_defs.h
branches/NCODE/priv/host_generic_reg_alloc2.c
branches/NCODE/priv/host_generic_regs.c
branches/NCODE/priv/host_generic_regs.h
Modified: branches/NCODE/priv/host_amd64_defs.c
==============================================================================
--- branches/NCODE/priv/host_amd64_defs.c (original)
+++ branches/NCODE/priv/host_amd64_defs.c Fri Apr 3 21:47:38 2015
@@ -217,7 +217,7 @@
return am;
}
AMD64AMode* AMD64AMode_IRS ( UInt imm32, HReg reg, Int shift ) {
- AMD64AMode* am = LibVEX_Alloc(sizeof(AMD64AMode));
+ AMD64AMode* am = LibVEX_Alloc_inline(sizeof(AMD64AMode));
am->tag = Aam_IRS;
am->Aam.IRS.imm = imm32;
am->Aam.IRS.reg = reg;
@@ -803,7 +803,7 @@
return i;
}
AMD64Instr* AMD64Instr_MovxWQ ( Bool syned, HReg src, HReg dst ) {
- AMD64Instr* i = LibVEX_Alloc(sizeof(AMD64Instr));
+ AMD64Instr* i = LibVEX_Alloc_inline(sizeof(AMD64Instr));
i->tag = Ain_MovxWQ;
i->Ain.MovxWQ.syned = syned;
i->Ain.MovxWQ.src = src;
@@ -1068,30 +1068,30 @@
}
AMD64Instr* AMD64Instr_NCode ( NCodeTemplate* tmpl, HReg* regsR,
HReg* regsA, HReg* regsS ) {
- AMD64InstrNCode* details = LibVEX_Alloc(sizeof(AMD64InstrNCode));
- details->tmpl = tmpl;
- details->regsR = regsR;
- details->regsA = regsA;
- details->regsS = regsS;
- details->liveAfter = NULL;
- AMD64Instr* i = LibVEX_Alloc(sizeof(AMD64Instr));
+ AMD64InstrNCode* details = LibVEX_Alloc_inline(sizeof(AMD64InstrNCode));
+ details->tmpl = tmpl;
+ details->regsR = regsR;
+ details->regsA = regsA;
+ details->regsS = regsS;
+ details->rrLiveAfter = NULL;
+ AMD64Instr* i = LibVEX_Alloc_inline(sizeof(AMD64Instr));
i->tag = Ain_NCode;
i->Ain.NCode.details = details;
return i;
}
AMD64Instr* AMD64Instr_NC_Jmp32 ( AMD64CondCode cc ) {
- AMD64Instr* i = LibVEX_Alloc(sizeof(AMD64Instr));
+ AMD64Instr* i = LibVEX_Alloc_inline(sizeof(AMD64Instr));
i->tag = Ain_NC_Jmp32;
i->Ain.NC_Jmp32.cc = cc;
return i;
}
AMD64Instr* AMD64Instr_NC_CallR11 ( void ) {
- AMD64Instr* i = LibVEX_Alloc(sizeof(AMD64Instr));
+ AMD64Instr* i = LibVEX_Alloc_inline(sizeof(AMD64Instr));
i->tag = Ain_NC_CallR11;
return i;
}
AMD64Instr* AMD64Instr_NC_TestQ ( HReg src, HReg dst ) {
- AMD64Instr* i = LibVEX_Alloc(sizeof(AMD64Instr));
+ AMD64Instr* i = LibVEX_Alloc_inline(sizeof(AMD64Instr));
i->tag = Ain_NC_TestQ;
i->Ain.NC_TestQ.src = src;
i->Ain.NC_TestQ.dst = dst;
@@ -3998,7 +3998,7 @@
/*MOD*/RelocationBuffer* rb,
const NInstr* ni,
const NRegMap* nregMap,
- const HRegSet* hregsLiveAfter,
+ const RRegSet* rrLiveAfter,
/* for debug printing only */
Bool verbose, NLabel niLabel );
@@ -4029,7 +4029,8 @@
const AMD64InstrNCode* hi_details = hi->Ain.NCode.details;
const NCodeTemplate* tmpl = hi_details->tmpl;
- const HRegSet* hregsLiveAfter = hi_details->liveAfter;
+ const RRegSet* rregsLiveAfter = hi_details->rrLiveAfter;
+ const RRegUniverse* univ = RRegSet__getUniverse(rregsLiveAfter);
NRegMap nregMap;
nregMap.regsR = hi_details->regsR;
@@ -4078,7 +4079,7 @@
offsetsHot[i] = AssemblyBuffer__getNext(ab_hot);
NLabel lbl = mkNLabel(Nlz_Hot, i);
emit_AMD64NInstr(ab_hot, rb, tmpl->hot[i], &nregMap,
- hregsLiveAfter, verbose, lbl);
+ rregsLiveAfter, verbose, lbl);
}
/* And the cold code */
@@ -4086,7 +4087,7 @@
offsetsCold[i] = AssemblyBuffer__getNext(ab_cold);
NLabel lbl = mkNLabel(Nlz_Cold, i);
emit_AMD64NInstr(ab_cold, rb, tmpl->cold[i], &nregMap,
- hregsLiveAfter, verbose, lbl);
+ rregsLiveAfter, verbose, lbl);
}
/* Now visit the new relocation entries. */
@@ -4132,69 +4133,69 @@
HReg rcx = hregAMD64_RCX();
HReg rdx = hregAMD64_RDX();
- HRegSet* rs = HRegSet__new();
+ RRegSet* rs = RRegSet__new(univ);
vex_printf("\n__new\n");
- vex_printf("1: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ vex_printf("1: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
vex_printf("\n__add\n");
- HRegSet__add(rs, rbx);
- vex_printf("2: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__add(rs, rbx);
+ vex_printf("2: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__add(rs, rdx);
- vex_printf("3: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__add(rs, rdx);
+ vex_printf("3: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__add(rs, rcx);
- vex_printf("4: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__add(rs, rcx);
+ vex_printf("4: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__add(rs, rcx);
- vex_printf("5: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__add(rs, rcx);
+ vex_printf("5: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__add(rs, r10);
- vex_printf("6: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__add(rs, r10);
+ vex_printf("6: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__add(rs, rax);
- vex_printf("7: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__add(rs, rax);
+ vex_printf("7: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
vex_printf("\n__fromVec\n");
const HReg vec[4] = { rdx, rcx, rbx, rax };
- HRegSet__fromVec(rs, vec, 0);
- vex_printf("8: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__fromVec(rs, vec, 0);
+ vex_printf("8: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__fromVec(rs, vec, 4);
- vex_printf("9: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__fromVec(rs, vec, 4);
+ vex_printf("9: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
vex_printf("\n__del\n");
- HRegSet__del(rs, rcx);
- vex_printf("10: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__del(rs, rcx);
+ vex_printf("10: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__del(rs, rcx);
- vex_printf("11: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__del(rs, rcx);
+ vex_printf("11: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__del(rs, rbx);
- vex_printf("12: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__del(rs, rbx);
+ vex_printf("12: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__del(rs, rax);
- vex_printf("13: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__del(rs, rax);
+ vex_printf("13: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__del(rs, rdx);
- vex_printf("14: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__del(rs, rdx);
+ vex_printf("14: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- HRegSet__del(rs, rdx);
- vex_printf("15: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__del(rs, rdx);
+ vex_printf("15: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
vex_printf("\n__plus\n");
- HRegSet* rs2 = HRegSet__new();
- HRegSet__add(rs, r10); HRegSet__add(rs, rax);
- HRegSet__add(rs2, rbx); HRegSet__add(rs2, rcx); HRegSet__add(rs2, rax);
-
- HRegSet__plus(rs2, rs);
- vex_printf("16a: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
- vex_printf("16b: "); HRegSet__pp(rs2, ppHRegAMD64); vex_printf("\n");
+ RRegSet* rs2 = RRegSet__new(univ);
+ RRegSet__add(rs, r10); RRegSet__add(rs, rax);
+ RRegSet__add(rs2, rbx); RRegSet__add(rs2, rcx); RRegSet__add(rs2, rax);
+
+ RRegSet__plus(rs2, rs);
+ vex_printf("16a: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ vex_printf("16b: "); RRegSet__pp(rs2, ppHRegAMD64); vex_printf("\n");
vex_printf("\n__minus\n");
- HRegSet__minus(rs, rs2);
- vex_printf("17: "); HRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
+ RRegSet__minus(rs, rs2);
+ vex_printf("17: "); RRegSet__pp(rs, ppHRegAMD64); vex_printf("\n");
}
@@ -4230,7 +4231,7 @@
/*MOD*/RelocationBuffer* rb,
const NInstr* ni,
const NRegMap* nregMap,
- const HRegSet* hregsLiveAfter,
+ const RRegSet* hregsLiveAfter,
/* the next 2 are for debug printing only */
Bool verbose, NLabel niLabel )
{
@@ -4320,80 +4321,81 @@
overestimate of (1) -- for example, all regs available to
reg-alloc -- and refine it later.
*/
- const HRegSet* set_1 = hregsLiveAfter; //HRegSet__new();
- //if (0) {
- // Int nregs; HReg* arr;
- // getAllocableRegs_AMD64(&nregs, &arr);
- // HRegSet__fromVec(set_1, arr, nregs);
- // }
+ const RRegUniverse* univ = RRegSet__getUniverse(hregsLiveAfter);
+ const RRegSet* set_1 = hregsLiveAfter;
- HRegSet* set_2 = HRegSet__new();
+ RRegSet* set_2 = RRegSet__new(univ);
{ UInt i;
for (i = 0; i < nregMap->nRegsR; i++)
- HRegSet__add(set_2, nregMap->regsR[i]);
+ RRegSet__add(set_2, nregMap->regsR[i]);
for (i = 0; i < nregMap->nRegsA; i++)
- HRegSet__add(set_2, nregMap->regsA[i]);
+ RRegSet__add(set_2, nregMap->regsA[i]);
for (i = 0; i < nregMap->nRegsS; i++)
- HRegSet__add(set_2, nregMap->regsS[i]);
+ RRegSet__add(set_2, nregMap->regsS[i]);
}
- HRegSet* set_3 = HRegSet__new();
+ RRegSet* set_3 = RRegSet__new(univ);
// callee-saves: rbx rbp r12 r13 r14 r15
{ HReg vec[6];
vec[0] = hregAMD64_RBX(); vec[1] = hregAMD64_RBP();
vec[2] = hregAMD64_R12(); vec[3] = hregAMD64_R13();
vec[4] = hregAMD64_R14(); vec[5] = hregAMD64_R15();
- HRegSet__fromVec(set_3, vec, sizeof(vec)/sizeof(vec[0]));
+ RRegSet__fromVec(set_3, vec, sizeof(vec)/sizeof(vec[0]));
}
- HRegSet* set_4 = HRegSet__new();
+ RRegSet* set_4 = RRegSet__new(univ);
if (!isNRegINVALID(ni->Nin.Call.resHi))
- HRegSet__add(set_4, mapNReg(nregMap, ni->Nin.Call.resHi));
+ RRegSet__add(set_4, mapNReg(nregMap, ni->Nin.Call.resHi));
if (!isNRegINVALID(ni->Nin.Call.resLo))
- HRegSet__add(set_4, mapNReg(nregMap, ni->Nin.Call.resLo));
+ RRegSet__add(set_4, mapNReg(nregMap, ni->Nin.Call.resLo));
- HRegSet* to_preserve = HRegSet__new();
- HRegSet__copy(to_preserve, set_1);
- HRegSet__plus(to_preserve, set_2);
- HRegSet__minus(to_preserve, set_3);
- HRegSet__minus(to_preserve, set_4);
+ RRegSet* to_preserve = RRegSet__new(univ);
+ RRegSet__copy(to_preserve, set_1);
+ RRegSet__plus(to_preserve, set_2);
+ RRegSet__minus(to_preserve, set_3);
+ RRegSet__minus(to_preserve, set_4);
if (verbose) {
vex_printf(" # set1: ");
- HRegSet__pp(set_1, ppHRegAMD64); vex_printf("\n");
+ RRegSet__pp(set_1, ppHRegAMD64); vex_printf("\n");
vex_printf(" # set2: ");
- HRegSet__pp(set_2, ppHRegAMD64); vex_printf("\n");
+ RRegSet__pp(set_2, ppHRegAMD64); vex_printf("\n");
vex_printf(" # set3: ");
- HRegSet__pp(set_3, ppHRegAMD64); vex_printf("\n");
+ RRegSet__pp(set_3, ppHRegAMD64); vex_printf("\n");
vex_printf(" # set4: ");
- HRegSet__pp(set_4, ppHRegAMD64); vex_printf("\n");
+ RRegSet__pp(set_4, ppHRegAMD64); vex_printf("\n");
vex_printf(" # pres: ");
- HRegSet__pp(to_preserve, ppHRegAMD64); vex_printf("\n");
+ RRegSet__pp(to_preserve, ppHRegAMD64); vex_printf("\n");
}
/* Save live regs */
- UInt n_to_preserve = HRegSet__size(to_preserve);
+ UInt n_to_preserve = RRegSet__card(to_preserve);
vassert(n_to_preserve < 25); /* stay sane */
/* Figure out how much to move the stack, ensuring any alignment up
to 32 is preserved. */
UInt stackMove = n_to_preserve * 16;
stackMove = (stackMove + 31) & ~31;
-
- UInt i;
if (stackMove > 0) {
HI( AMD64Instr_Alu64R(Aalu_SUB, AMD64RMI_Imm(stackMove),
hregAMD64_RSP()) );
}
- for (i = 0; i < n_to_preserve; i++) {
- HReg r = HRegSet__index(to_preserve, i);
+
+ RRegSetIterator* iter = RRegSetIterator__new();
+ RRegSetIterator__init(iter, to_preserve);
+ UInt slotNo = 0;
+ while (True) {
+ HReg r = RRegSetIterator__next(iter);
+ if (hregIsInvalid(r)) break;
AMD64Instr* i1 = NULL;
AMD64Instr* i2 = NULL;
genSpill_AMD64( (HInstr**)&i1, (HInstr**)&i2,
- r, True/*spRel*/, 16 * i, True/*mode64*/ );
+ r, True/*spRel*/, 16 * slotNo, True/*mode64*/ );
if (i1) HI(i1);
if (i2) HI(i2);
+ slotNo++;
}
+ vassert(slotNo == n_to_preserve);
/* Marshall args for the call, do the call, marshal the result */
/* Case: 1 arg reg, 1 result reg */
@@ -4424,15 +4426,20 @@
}
/* Restore live regs */
- for (i = 0; i < n_to_preserve; i++) {
- HReg r = HRegSet__index(to_preserve, i);
+ RRegSetIterator__init(iter, to_preserve);
+ slotNo = 0;
+ while (True) {
+ HReg r = RRegSetIterator__next(iter);
+ if (hregIsInvalid(r)) break;
AMD64Instr* i1 = NULL;
AMD64Instr* i2 = NULL;
genReload_AMD64( (HInstr**)&i1, (HInstr**)&i2,
- r, True/*spRel*/, 16 * i, True/*mode64*/ );
+ r, True/*spRel*/, 16 * slotNo, True/*mode64*/ );
if (i1) HI(i1);
if (i2) HI(i2);
+ slotNo++;
}
+ vassert(slotNo == n_to_preserve);
if (stackMove > 0) {
HI( AMD64Instr_Alu64R(Aalu_ADD, AMD64RMI_Imm(stackMove),
hregAMD64_RSP()) );
Modified: branches/NCODE/priv/host_amd64_defs.h
==============================================================================
--- branches/NCODE/priv/host_amd64_defs.h (original)
+++ branches/NCODE/priv/host_amd64_defs.h Fri Apr 3 21:47:38 2015
@@ -426,7 +426,7 @@
HReg* regsR; /* Result regs, INVALID_HREG terminated */
HReg* regsA; /* Arg regs, ditto */
HReg* regsS; /* Scratch regs, ditto */
- HRegSet* liveAfter; /* initially NULL, filled in by RA */
+ RRegSet* rrLiveAfter; /* initially NULL, filled in by RA */
}
AMD64InstrNCode;
Modified: branches/NCODE/priv/host_generic_reg_alloc2.c
==============================================================================
--- branches/NCODE/priv/host_generic_reg_alloc2.c (original)
+++ branches/NCODE/priv/host_generic_reg_alloc2.c Fri Apr 3 21:47:38 2015
@@ -1604,17 +1604,17 @@
if (ai->tag == Ain_NCode) {
AMD64InstrNCode* details = ai->Ain.NCode.details;
//vex_printf("RA: after NCode: ");
- vassert(details->liveAfter == NULL);
- HRegSet* live_after_NCode = HRegSet__new();
+ vassert(details->rrLiveAfter == NULL);
+ RRegSet* rrLive_after_NCode = RRegSet__new(univ);
for (Int k = 0; k < n_rregs; k++) {
if (rreg_state[k].disp == Free)
continue;
//ppHRegAMD64(rreg_state[k].rreg);
- HRegSet__add(live_after_NCode, univ->regs[k]);
+ RRegSet__add(rrLive_after_NCode, univ->regs[k]);
//vex_printf(" ");
}
//vex_printf("\n");
- details->liveAfter = live_after_NCode;
+ details->rrLiveAfter = rrLive_after_NCode;
}
}
Modified: branches/NCODE/priv/host_generic_regs.c
==============================================================================
--- branches/NCODE/priv/host_generic_regs.c (original)
+++ branches/NCODE/priv/host_generic_regs.c Fri Apr 3 21:47:38 2015
@@ -83,283 +83,206 @@
/*---------------------------------------------------------*/
-/*--- A simple implementation of register sets ---*/
+/*--- Real register Universes. ---*/
/*---------------------------------------------------------*/
-/* Helper function, to sort HReg values in an array. */
-static void sortHRegArray ( HReg* arr, Int nArr )
+void RRegUniverse__init ( /*OUT*/RRegUniverse* univ )
{
- Int incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
- 9841, 29524, 88573, 265720,
- 797161, 2391484 };
- Int lo = 0;
- Int hi = nArr-1;
- Int i, j, h, bigN, hp;
- HReg v;
-
- vassert(nArr >= 0);
- if (nArr == 0) return;
-
- bigN = hi - lo + 1; if (bigN < 2) return;
- hp = 0; while (hp < 14 && incs[hp] < bigN) hp++; hp--;
-
- for ( ; hp >= 0; hp--) {
- h = incs[hp];
- for (i = lo + h; i <= hi; i++) {
- v = arr[i];
- j = i;
- while (arr[j-h].u32 > v.u32) {
- arr[j] = arr[j-h];
- j = j - h;
- if (j <= (lo + h - 1)) break;
- }
- arr[j] = v;
- }
+ *univ = (RRegUniverse){};
+ univ->size = 0;
+ univ->allocable = 0;
+ for (UInt i = 0; i < N_RREGUNIVERSE_REGS; i++) {
+ univ->regs[i] = HReg_INVALID;
}
}
+void RRegUniverse__check_is_sane ( const RRegUniverse* univ )
+{
+ /* Check Real-Register-Universe invariants. All of these are
+ important. */
+ vassert(univ->size > 0);
+ vassert(univ->size <= N_RREGUNIVERSE_REGS);
+ vassert(univ->allocable <= univ->size);
+ for (UInt i = 0; i < univ->size; i++) {
+ HReg reg = univ->regs[i];
+ vassert(!hregIsInvalid(reg));
+ vassert(!hregIsVirtual(reg));
+ vassert(hregIndex(reg) == i);
+ }
+ for (UInt i = univ->size; i < N_RREGUNIVERSE_REGS; i++) {
+ HReg reg = univ->regs[i];
+ vassert(hregIsInvalid(reg));
+ }
+}
+
+
+/*---------------------------------------------------------*/
+/*--- Real register sets ---*/
+/*---------------------------------------------------------*/
+
+/* Represents sets of real registers. |bits| is interpreted in the
+ context of |univ|. That is, each bit index |i| in |bits|
+ corresponds to the register |univ->regs[i]|. This relies
+ entirely on the fact that N_RREGUNIVERSE_REGS <= 64.
+*/
+struct _RRegSet {
+ ULong bits;
+ const RRegUniverse* univ;
+};
+
+STATIC_ASSERT(N_RREGUNIVERSE_REGS <= 8 * sizeof(ULong));
+
/* Print a register set, using the arch-specific register printing
function |regPrinter| supplied. */
-void HRegSet__pp ( HRegSet* set, void (*regPrinter)(HReg) )
+void RRegSet__pp ( const RRegSet* set, void (*regPrinter)(HReg) )
{
- UInt i;
+ const RRegUniverse* univ = set->univ;
+ Bool first = True;
vex_printf("{");
- for (i = 0; i < set->regsUsed; i++) {
- regPrinter(set->regs[i]);
- if (i+1 != set->regsUsed)
+ for (UInt i = 0; i < 8 * sizeof(ULong); i++) {
+ if (0ULL == (set->bits & (1ULL << i)))
+ continue;
+ vassert(i < univ->size);
+ if (!first) {
vex_printf(",");
+ } else {
+ first = False;
+ }
+ regPrinter(univ->regs[i]);
}
vex_printf("}");
}
/* Create a new, empty, set. */
-HRegSet* HRegSet__new ( void )
+RRegSet* RRegSet__new ( const RRegUniverse* univ )
{
- HRegSet* set = LibVEX_Alloc(sizeof(HRegSet));
- set->regsUsed = 0;
+ vassert(univ);
+ RRegSet* set = LibVEX_Alloc_inline(sizeof(RRegSet));
+ set->bits = 0;
+ set->univ = univ;
return set;
}
+/* Return the RRegUniverse for a given RRegSet. */
+const RRegUniverse* RRegSet__getUniverse ( const RRegSet* set )
+{
+ return set->univ;
+}
+
/* Install elements from vec[0 .. nVec-1]. The previous contents of
|dst| are lost. vec[0 .. nVec-1] may not contain any
duplicates. */
-void HRegSet__fromVec ( /*MOD*/HRegSet* dst, const HReg* vec, UInt nVec )
+void RRegSet__fromVec ( /*MOD*/RRegSet* dst, const HReg* vec, UInt nVec )
{
- UInt i;
- vassert(nVec <= N_HREG_SET);
- for (i = 0; i < nVec; i++) {
- dst->regs[i] = vec[i];
- }
- dst->regsUsed = nVec;
- sortHRegArray(&dst->regs[0], dst->regsUsed);
- /* Assert no duplicates (and, as a side effect, in-order) */
- for (i = 1; i < dst->regsUsed; i++) {
- /* If this fails, your vec[] contains duplicates. */
- vassert(dst->regs[i-1].u32 < dst->regs[i].u32);
+ for (UInt i = 0; i < nVec; i++) {
+ HReg r = vec[i];
+ vassert(!hregIsInvalid(r) && !hregIsVirtual(r));
+ UInt ix = hregIndex(r);
+ vassert(ix < dst->univ->size);
+ dst->bits |= (1ULL << ix);
}
}
/* Copy the contents of |regs| into |dst|. The previous contents of
|dst| are lost. */
-void HRegSet__copy ( /*MOD*/HRegSet* dst, const HRegSet* regs )
+void RRegSet__copy ( /*MOD*/RRegSet* dst, const RRegSet* regs )
{
- UInt i;
- dst->regsUsed = regs->regsUsed;
- for (i = 0; i < regs->regsUsed; i++)
- dst->regs[i] = regs->regs[i];
+ vassert(dst->univ == regs->univ);
+ dst->bits = regs->bits;
}
/* Add |reg| to |dst|. */
-void HRegSet__add ( /*MOD*/HRegSet* dst, HReg reg )
+void RRegSet__add ( /*MOD*/RRegSet* dst, HReg reg )
{
- UInt i, j;
- for (i = 0; i < dst->regsUsed; i++) {
- if (reg.u32 <= dst->regs[i].u32)
- break;
- }
- /* Is it already present? */
- if (i < dst->regsUsed && reg.u32 == dst->regs[i].u32) {
- /* Yes. Do nothing more. */
- return;
- }
- /* No. Add it at position |i|. */
- vassert(dst->regsUsed < N_HREG_SET);
- dst->regsUsed++;
- for (j = dst->regsUsed-1; j > i; j--) {
- dst->regs[j] = dst->regs[j-1];
- }
- dst->regs[i] = reg;
+ vassert(!hregIsInvalid(reg) && !hregIsVirtual(reg));
+ UInt ix = hregIndex(reg);
+ vassert(ix < dst->univ->size);
+ dst->bits |= (1ULL << ix);
}
/* Remove |reg| from |dst|. */
-void HRegSet__del ( /*MOD*/HRegSet* dst, HReg reg )
+void RRegSet__del ( /*MOD*/RRegSet* dst, HReg reg )
{
- UInt i, j;
- for (i = 0; i < dst->regsUsed; i++) {
- if (reg.u32 <= dst->regs[i].u32)
- break;
- }
- /* Is it already present? */
- if (i < dst->regsUsed && reg.u32 == dst->regs[i].u32) {
- /* Yes, at position |i|. */;
- vassert(dst->regsUsed > 0);
- for (j = i+1; j < dst->regsUsed; j++) {
- dst->regs[j-1] = dst->regs[j];
- }
- dst->regsUsed--;
- }
+ vassert(!hregIsInvalid(reg) && !hregIsVirtual(reg));
+ UInt ix = hregIndex(reg);
+ vassert(ix < dst->univ->size);
+ dst->bits &= ~(1ULL << ix);
}
/* Add |regs| to |dst|. */
-void HRegSet__plus ( /*MOD*/HRegSet* dst, const HRegSet* regs )
+void RRegSet__plus ( /*MOD*/RRegSet* dst, const RRegSet* regs )
{
- /* We'll need to create the result into a temp vector,
- since |dst| is also one of the sources. */
- HReg tmp[N_HREG_SET];
- UInt iD, iR, iT;
- UInt usedD = dst->regsUsed;
- UInt usedR = regs->regsUsed;
- iD = iR = iT = 0;
-
- while (1) {
- vassert(iD <= usedD && iR <= usedR);
- if (iD == usedD && iR == usedR) {
- /* both empty -- done */
- break;
- }
- vassert(iT < N_HREG_SET);
- if (iD == usedD && iR != usedR) {
- /* D empty, use up R */
- tmp[iT++] = regs->regs[iR++];
- continue;
- }
- if (iD != usedD && iR == usedR) {
- /* R empty, use up D */
- tmp[iT++] = dst->regs[iD++];
- continue;
- }
- /* both not empty; use the lowest valued HReg */
- HReg candD = dst->regs[iD];
- HReg candR = regs->regs[iR];
- if (candD.u32 < candR.u32) {
- tmp[iT++] = candD;
- iD++;
- }
- else if (candD.u32 > candR.u32) {
- tmp[iT++] = candR;
- iR++;
- }
- else {
- tmp[iT++] = candD;
- iD++; iR++;
- }
- }
-
- /* Copy result back into place. */
- vassert((iT >= usedD || iT >= usedR) && iT <= N_HREG_SET);
- UInt i;
- for (i = 0; i < iT; i++) {
- dst->regs[i] = tmp[i];
- }
- dst->regsUsed = iT;
+ vassert(dst->univ == regs->univ);
+ dst->bits |= regs->bits;
}
/* Remove |regs| from |dst|. */
-void HRegSet__minus ( /*MOD*/HRegSet* dst, const HRegSet* regs )
+void RRegSet__minus ( /*MOD*/RRegSet* dst, const RRegSet* regs )
{
- /* We'll need to create the result into a temp vector,
- since |dst| is also one of the sources. */
- HReg tmp[N_HREG_SET];
- UInt iD, iR, iT;
- UInt usedD = dst->regsUsed;
- UInt usedR = regs->regsUsed;
- iD = iR = iT = 0;
-
- while (1) {
- vassert(iD <= usedD && iR <= usedR);
- if (iD == usedD) {
- /* D empty -- done */
- break;
- }
- vassert(iT < N_HREG_SET);
- if (iR == usedR) {
- /* R empty, use up D */
- tmp[iT++] = dst->regs[iD++];
- continue;
- }
- /* both not empty */
- HReg candD = dst->regs[iD];
- HReg candR = regs->regs[iR];
- if (candD.u32 < candR.u32) {
- /* candD can't possibly be in the part of R that we
- haven't yet visited, so keep it. */
- tmp[iT++] = candD;
- iD++;
- }
- else if (candD.u32 > candR.u32) {
- /* We don't know yet if we can retain candD, but for sure,
- candR won't be able to delete anything in the unvisited
- part of D. So skip over candR. */
- iR++;
- }
- else {
- /* The register appears in both lists, so skip it. */
- iR++; iD++;
- }
- }
-
- /* Copy result back into place. */
- vassert((iT <= usedD || iT <= usedR) && iT <= N_HREG_SET);
- UInt i;
- for (i = 0; i < iT; i++) {
- dst->regs[i] = tmp[i];
- }
- dst->regsUsed = iT;
+ vassert(dst->univ == regs->univ);
+ dst->bits &= (~regs->bits);
}
/* Returns the number of elements in |set|. */
-UInt HRegSet__size ( const HRegSet* set ) {
- return set->regsUsed;
+UInt RRegSet__card ( const RRegSet* set )
+{
+ return __builtin_popcountll(set->bits);
}
-/* Returns the |ix|th element of |set|, where |ix| is zero-based. */
-HReg HRegSet__index ( const HRegSet* set, UInt ix ) {
- vassert(ix < set->regsUsed);
- return set->regs[ix];
-}
+struct _RRegSetIterator {
+ const RRegSet* set;
+ UInt nextIx; /* The next |set->bits| index to try */
+};
-/*---------------------------------------------------------*/
-/*--- Real register Universes. ---*/
-/*---------------------------------------------------------*/
+/* Create a new iterator. It can't be used until it is first __init'd. */
+RRegSetIterator* RRegSetIterator__new ( void )
+{
+ RRegSetIterator* iter = LibVEX_Alloc_inline(sizeof(RRegSetIterator));
+ vex_bzero(iter, sizeof(*iter));
+ return iter;
+}
-void RRegUniverse__init ( /*OUT*/RRegUniverse* univ )
+/* Initialise an iterator. */
+void RRegSetIterator__init ( /*OUT*/RRegSetIterator* iter,
+ const RRegSet* set )
{
- *univ = (RRegUniverse){};
- univ->size = 0;
- univ->allocable = 0;
- for (UInt i = 0; i < N_RREGUNIVERSE_REGS; i++) {
- univ->regs[i] = HReg_INVALID;
+ iter->set = set;
+ iter->nextIx = 0;
+ /* We're going to iterate only up as far as the Universe size, so
+ check that there are no elements above that. RRegSet__add and
+ __fromVec should ensure that is never the case, and there are no
+ other ways to add elements to a set. */
+ const RRegUniverse* univ = set->univ;
+ if (LIKELY(univ->size < 64)) {
+ vassert((set->bits >> univ->size) == 0);
+ } else {
+ vassert(univ->size == 64);
}
}
-void RRegUniverse__check_is_sane ( const RRegUniverse* univ )
+/* Get the next element from the set, or HReg_INVALID if there is
+ none. */
+HReg RRegSetIterator__next ( /*MOD*/RRegSetIterator* iter )
{
- /* Check Real-Register-Universe invariants. All of these are
- important. */
- vassert(univ->size > 0);
- vassert(univ->size <= N_RREGUNIVERSE_REGS);
- vassert(univ->allocable <= univ->size);
- for (UInt i = 0; i < univ->size; i++) {
- HReg reg = univ->regs[i];
- vassert(!hregIsInvalid(reg));
- vassert(!hregIsVirtual(reg));
- vassert(hregIndex(reg) == i);
- }
- for (UInt i = univ->size; i < N_RREGUNIVERSE_REGS; i++) {
- HReg reg = univ->regs[i];
- vassert(hregIsInvalid(reg));
+ const RRegSet* set = iter->set;
+ /* If this fails, it's possibly a sign that the __init call for
+ |iter| was missed. */
+ vassert(iter->set);
+
+ const RRegUniverse* univ = set->univ;
+ const UInt maxIx = univ->size;
+ vassert(iter->nextIx <= maxIx);
+ while (1) {
+ if (UNLIKELY(iter->nextIx >= maxIx)) {
+ return HReg_INVALID;
+ }
+ if (UNLIKELY(0ULL != (set->bits & (1ULL << iter->nextIx)))) {
+ return univ->regs[iter->nextIx++];
+ }
+ iter->nextIx++;
}
+ /*NOTREACHED*/
}
Modified: branches/NCODE/priv/host_generic_regs.h
==============================================================================
--- branches/NCODE/priv/host_generic_regs.h (original)
+++ branches/NCODE/priv/host_generic_regs.h Fri Apr 3 21:47:38 2015
@@ -182,58 +182,7 @@
/*---------------------------------------------------------*/
-/*--- Representing register sets ---*/
-/*---------------------------------------------------------*/
-
-/* This is a very un-clever representation, but we need
- to start somewhere. */
-
-#define N_HREG_SET 20
-
-typedef
- struct {
- HReg regs[N_HREG_SET];
- UInt regsUsed; /* 0 .. N_HREG_SET inclusive */
- }
- HRegSet;
-
-/* Print a register set, using the arch-specific register printing
- function |regPrinter| supplied. */
-extern void HRegSet__pp ( HRegSet* set, void (*regPrinter)(HReg) );
-
-/* Create a new, empty, set. */
-extern HRegSet* HRegSet__new ( void );
-
-/* Install elements from vec[0 .. nVec-1]. The previous contents of
- |dst| are lost. */
-extern void HRegSet__fromVec ( /*MOD*/HRegSet* dst,
- const HReg* vec, UInt nVec );
-
-/* Copy the contents of |regs| into |dst|. The previous contents of
- |dst| are lost. */
-extern void HRegSet__copy ( /*MOD*/HRegSet* dst, const HRegSet* regs );
-
-/* Add |reg| to |dst|. */
-extern void HRegSet__add ( /*MOD*/HRegSet* dst, HReg reg );
-
-/* Remove |reg| from |dst|. */
-extern void HRegSet__del ( /*MOD*/HRegSet* dst, HReg reg );
-
-/* Add |regs| to |dst|. */
-extern void HRegSet__plus ( /*MOD*/HRegSet* dst, const HRegSet* regs );
-
-/* Remove |regs| from |dst|. */
-extern void HRegSet__minus ( /*MOD*/HRegSet* dst, const HRegSet* regs );
-
-/* Returns the number of elements in |set|. */
-extern UInt HRegSet__size ( const HRegSet* set );
-
-/* Returns the |ix|th element of |set|, where |ix| is zero-based. */
-extern HReg HRegSet__index ( const HRegSet* set, UInt ix );
-
-
-/*---------------------------------------------------------*/
-/*--- Real register Universes. ---*/
+/*--- Real Register Universes ---*/
/*---------------------------------------------------------*/
/* A "Real Register Universe" is a read-only structure that contains
@@ -282,23 +231,68 @@
void RRegUniverse__check_is_sane ( const RRegUniverse* );
/* Print an RRegUniverse, for debugging. */
-void RRegUniverse__show ( const RRegUniverse* );
+void RRegUniverse__pp ( const RRegUniverse* );
/*---------------------------------------------------------*/
-/*--- Real register sets. ---*/
+/*--- Real Register Sets ---*/
/*---------------------------------------------------------*/
-/* Represents sets of real registers. |bitset| is interpreted in the
- context of |univ|. That is, each bit index |i| in |bitset|
- corresponds to the register |univ->regs[i]|. This relies
- entirely on the fact that N_RREGUNIVERSE_REGS <= 64. */
-typedef
- struct {
- ULong bitset;
- RRegUniverse* univ;
- }
- RRegSet;
+/* ABSTYPE */
+typedef struct _RRegSet RRegSet;
+
+/* Print a register set, using the arch-specific register printing
+ function |regPrinter| supplied. */
+extern void RRegSet__pp ( const RRegSet* set, void (*regPrinter)(HReg) );
+
+/* Create a new, empty, set. */
+extern RRegSet* RRegSet__new ( const RRegUniverse* univ );
+
+/* Return the RRegUniverse for a given RRegSet. */
+extern const RRegUniverse* RRegSet__getUniverse ( const RRegSet* );
+
+/* Install elements from vec[0 .. nVec-1]. The previous contents of
+ |dst| are lost. */
+extern void RRegSet__fromVec ( /*MOD*/RRegSet* dst,
+ const HReg* vec, UInt nVec );
+
+/* Copy the contents of |regs| into |dst|. The previous contents of
+ |dst| are lost. */
+extern void RRegSet__copy ( /*MOD*/RRegSet* dst, const RRegSet* regs );
+
+/* Add |reg| to |dst|. */
+extern void RRegSet__add ( /*MOD*/RRegSet* dst, HReg reg );
+
+/* Remove |reg| from |dst|. */
+extern void RRegSet__del ( /*MOD*/RRegSet* dst, HReg reg );
+
+/* Add |regs| to |dst|. */
+extern void RRegSet__plus ( /*MOD*/RRegSet* dst, const RRegSet* regs );
+
+/* Remove |regs| from |dst|. */
+extern void RRegSet__minus ( /*MOD*/RRegSet* dst, const RRegSet* regs );
+
+/* Returns the number of elements in |set|. */
+extern UInt RRegSet__card ( const RRegSet* set );
+
+
+/* Iterating over RRegSets. */
+/* ABSTYPE */
+typedef struct _RRegSetIterator RRegSetIterator;
+
+/* Create a new iterator. It must be initialised with __init before
+ it can be used in __next calls. This is checked in __next. */
+extern RRegSetIterator* RRegSetIterator__new ( void );
+
+/* Initialise an iterator for iterating over the given set. */
+extern void RRegSetIterator__init ( /*OUT*/RRegSetIterator* iter,
+ const RRegSet* set );
+
+/* Get the next element out of an iterator. If there are no more
+ elements, HReg_INVALID is returned. This pretty much implies (and
+ is checked) that the set construction routines above cannot be used
+ to insert HReg_INVALID into a set. */
+extern HReg RRegSetIterator__next ( /*MOD*/RRegSetIterator* );
/*---------------------------------------------------------*/
|