diff options
Diffstat (limited to 'compiler_and_linker/BackEnd/PowerPC/RegisterAllocator')
4 files changed, 1465 insertions, 0 deletions
diff --git a/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/Coloring.c b/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/Coloring.c new file mode 100644 index 0000000..8036435 --- /dev/null +++ b/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/Coloring.c @@ -0,0 +1,268 @@ +#include "compiler/Coloring.h" +#include "compiler/CFunc.h" +#include "compiler/CompilerTools.h" +#include "compiler/InterferenceGraph.h" +#include "compiler/PCode.h" +#include "compiler/PPCError.h" +#include "compiler/Registers.h" +#include "compiler/RegisterInfo.h" +#include "compiler/SpillCode.h" +#include "compiler/StackFrame.h" +#include "compiler/objects.h" + +RegClass coloring_class; +static short used_regs_before_coloring; + +static void markspecialregisters(RegClass rclass) { + ObjectList *list; + Object *object; + VarInfo *vi; + UInt32 i; + + for (i = 0; i < n_real_registers[rclass]; i++) + interferencegraph[i]->x14 = i; + + for (list = arguments; list; list = list->next) { + object = list->object; + vi = Registers_GetVarInfo(object); + if ((vi->flags & VarInfoFlag2) && vi->rclass == rclass) { + interferencegraph[vi->reg]->spillTemporary = object; + if (vi->flags & VarInfoFlag4) { + interferencegraph[vi->reg]->flags |= fPairLow; + interferencegraph[vi->regHi]->flags |= fPairHigh; + interferencegraph[vi->regHi]->spillTemporary = object; + } + } + } + + for (list = locals; list; list = list->next) { + object = list->object; + vi = Registers_GetVarInfo(object); + if ((vi->flags & VarInfoFlag2) && vi->rclass == rclass) { + interferencegraph[vi->reg]->spillTemporary = object; + if (vi->flags & VarInfoFlag4) { + interferencegraph[vi->reg]->flags |= fPairLow; + interferencegraph[vi->regHi]->flags |= fPairHigh; + interferencegraph[vi->regHi]->spillTemporary = object; + } + } + } +} + +static IGNode *simplifygraph(void) { + int availableRegs; + IGNode *spilledNodes; + IGNode *pushedNodes; + IGNode *best; + IGNode *node; + UInt32 i; + UInt32 j; + int flag; + float bestScore; + float score; + + availableRegs = available_registers(coloring_class); + pushedNodes = NULL; + + do { + spilledNodes = NULL; + flag = 0; + for (i = n_real_registers[coloring_class]; i < used_virtual_registers[coloring_class]; i++) { + node = interferencegraph[i]; + if (!(node->flags & (fPushed | fCoalesced))) { + if (node->x12 < availableRegs) { + for (j = 0; j < node->arraySize; j++) + interferencegraph[node->array[j]]->x12--; + node->flags |= fPushed; + node->next = pushedNodes; + pushedNodes = node; + flag = 1; + } else { + node->next = spilledNodes; + spilledNodes = node; + } + } + } + } while (flag); + + if (spilledNodes) + estimatespillcosts(); + + while (spilledNodes) { + best = spilledNodes; + bestScore = (spilledNodes->x10 >= used_regs_before_coloring) ? FLT_MAX : ((float) spilledNodes->spillCost / (float) spilledNodes->x12); + + for (node = spilledNodes->next; node; node = node->next) { + score = (node->x10 >= used_regs_before_coloring) ? FLT_MAX : ((float) node->spillCost / (float) node->x12); + if (score < bestScore) { + best = node; + bestScore = score; + } + } + + for (i = 0; i < best->arraySize; i++) + interferencegraph[best->array[i]]->x12--; + + best->flags |= fPushed; + best->next = pushedNodes; + pushedNodes = best; + + do { + spilledNodes = NULL; + flag = 0; + for (i = n_real_registers[coloring_class]; i < used_virtual_registers[coloring_class]; i++) { + node = interferencegraph[i]; + if (!(node->flags & (fPushed | fCoalesced))) { + if (node->x12 < availableRegs) { + for (j = 0; j < node->arraySize; j++) + interferencegraph[node->array[j]]->x12--; + node->flags |= fPushed; + node->next = pushedNodes; + pushedNodes = node; + flag = 1; + } else { + node->next = spilledNodes; + spilledNodes = node; + } + } + } + } while (flag); + } + + return pushedNodes; +} + +static int colorgraph(IGNode *node) { + UInt32 volatileRegs; + int result; + IGNode *otherNode; + int reg; + UInt32 workingMask; + int i; + short *array; + + result = 1; + + reset_nonvolatile_registers(coloring_class); + volatileRegs = volatile_registers(coloring_class); + + while (node) { + workingMask = volatileRegs; + for (array = node->array, i = 0; i < node->arraySize; i++) { + otherNode = interferencegraph[*(array++)]; + reg = otherNode->x14; + if (reg != -1 && reg < n_real_registers[coloring_class]) + workingMask &= ~(1 << reg); + } + + if (workingMask) { + for (i = 0; i < n_real_registers[coloring_class]; i++) { + if (workingMask & (1 << i)) { + node->x14 = i; + break; + } + } + } else { + reg = obtain_nonvolatile_register(coloring_class); + if (reg != -1) { + volatileRegs |= 1 << (node->x14 = reg); + } else { + node->flags |= fSpilled; + result = 0; + } + } + + node = node->next; + } + + return result; +} + +static void rewritepcode(void) { + PCodeBlock *block; + PCode *instr; + PCodeArg *op; + UInt32 i; + IGNode *node; + int reg; + + for (block = pcbasicblocks; block; block = block->nextBlock) { + for (instr = block->firstPCode; instr; instr = instr->nextPCode) { + op = instr->args; + i = instr->argCount; + while (i--) { + if (PC_OP_IS_ANY_REGISTER(op, coloring_class)) + op->data.reg.reg = interferencegraph[op->data.reg.reg]->x14; + op++; + } + + if ( + (instr->flags & fIsMove) && + (instr->args[1].arg == coloring_class) && + instr->args[1].data.reg.reg == instr->args[0].data.reg.reg + ) + deletepcode(instr); + } + } + + for (i = n_real_registers[coloring_class]; i < used_virtual_registers[coloring_class]; i++) { + node = interferencegraph[i]; + if (node->spillTemporary && !(node->flags & fSpilled)) { + if (node->flags & fCoalesced) { + reg = node->x14; + while (reg >= n_real_registers[coloring_class]) { + reg = interferencegraph[reg]->x14; + if (reg < 0) + break; + } + node->x14 = reg; + } + + if (node->flags & fPairHigh) { + reg = node->x14; + Registers_GetVarInfo(node->spillTemporary)->regHi = reg; + } else { + reg = node->x14; + Registers_GetVarInfo(node->spillTemporary)->reg = reg; + } + } + } +} + +void colorinstructions(Object *proc) { + RegClass rclass; + int flag; + + for (rclass = 0; rclass < RegClassMax; rclass++) { + coloring_class = rclass; + + if (rclass == RegClass_GPR) + check_dynamic_aligned_frame(); + + if (used_virtual_registers[rclass] > n_real_registers[rclass]) { + save_before_coloring_nonvolatile_registers(rclass); + used_regs_before_coloring = used_virtual_registers[rclass]; + if (!available_registers(rclass)) { + PPCError_Error(PPCErrorStr102, register_class_name[rclass]); + return; + } + + flag = 1; + while (flag && used_virtual_registers[rclass] > n_real_registers[rclass]) { + buildinterferencegraph(proc); + markspecialregisters(rclass); + flag = colorgraph(simplifygraph()) ? 0 : 1; + + if (flag) + insertspillcode(); + else + rewritepcode(); + freeoheap(); + } + } + + used_virtual_registers[rclass] = n_real_registers[rclass]; + } + + coloring = 0; +} diff --git a/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/InterferenceGraph.c b/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/InterferenceGraph.c new file mode 100644 index 0000000..d589502 --- /dev/null +++ b/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/InterferenceGraph.c @@ -0,0 +1,364 @@ +#include "compiler/InterferenceGraph.h" +#include "compiler/CError.h" +#include "compiler/CParser.h" +#include "compiler/BitVectors.h" +#include "compiler/Coloring.h" +#include "compiler/LiveInfo.h" +#include "compiler/PCode.h" +#include "compiler/PCodeListing.h" +#include "compiler/PCodeUtilities.h" +#include "compiler/Registers.h" +#include "compiler/RegisterInfo.h" +#include "compiler/CompilerTools.h" + +IGNode **interferencegraph; +static UInt32 *interferencematrix; +Boolean coalesced_nregisters; +static SInt16 *coalesced; + +static void makeinterfere(UInt32 a, UInt32 b) { + if (a < b) + bitvectorsetbit(((b * b) / 2) + a, interferencematrix); + else if (a > b) + bitvectorsetbit(((a * a) / 2) + b, interferencematrix); +} + +int interferes(UInt32 a, UInt32 b) { + if (a < b) + return bitvectorgetbit(((b * b) / 2) + a, interferencematrix) > 0; + else if (a > b) + return bitvectorgetbit(((a * a) / 2) + b, interferencematrix) > 0; + else + return 0; +} + +static void buildinterferencematrix(void) { + PCodeBlock *block; // r30 + PCode *instr; // r29 + PCodeArg *op; + UInt32 *vec; // r28 + UInt32 i; + UInt32 j; + + UInt32 regs = used_virtual_registers[coloring_class]; + interferencematrix = oalloc(4 * ((((regs * regs) / 2) + 31) >> 5)); + bitvectorinitialize(interferencematrix, (regs * regs) / 2, 0); + + for (i = 0; i < 32; i++) + for (j = 0; j < 32; j++) + if (i != j) + makeinterfere(i, j); + + vec = oalloc(4 * ((regs + 31) >> 5)); + for (block = pcbasicblocks; block; block = block->nextBlock) { + bitvectorcopy(vec, liveinfo[block->blockIndex].out, regs); + for (instr = block->lastPCode; instr; instr = instr->prevPCode) { + for (op = instr->args, i = instr->argCount; i--; op++) { + if (PC_OP_IS_WRITE_ANY_REGISTER(op, coloring_class)) { + int reg = op->data.reg.reg; + bitvectorclearbit(reg, vec); + for (j = 0; j < regs; j++) { + if (bitvectorgetbit(j, vec)) { + if ( + (instr->flags & fIsMove) && + PC_OP_IS_ANY_REGISTER(&instr->args[0], coloring_class) && + instr->args[1].data.reg.reg == j + ) + continue; + makeinterfere(reg, j); + } + } + } + } + + for (op = instr->args, i = instr->argCount; i--; op++) { + if (PC_OP_IS_READ_ANY_REGISTER(op, coloring_class)) { + int reg = op->data.reg.reg; + if (bitvectorgetbit(op->data.reg.reg, vec) == 0) + op->data.reg.effect |= Effect4; + bitvectorsetbit(reg, vec); + } + } + + if (coloring_class == RegClass_GPR) { + if (PCODE_FLAG_SET_F(instr) & (fIsRead | fIsWrite | fPCodeFlag400000)) { + if (instr->args[1].data.reg.reg >= n_real_registers[coloring_class]) + makeinterfere(0, instr->args[1].data.reg.reg); + if (PCODE_FLAG_SET_F(instr) & fUpdatesPtr) + makeinterfere(instr->args[0].data.reg.reg, instr->args[1].data.reg.reg); + } else { + switch (instr->op) { + case PC_DCBF: + case PC_DCBST: + case PC_DCBT: + case PC_DCBTST: + case PC_DCBZ: + case PC_DCBI: + case PC_ICBI: + case PC_DCCCI: + case PC_ICBT: + case PC_ICCCI: + case PC_ICREAD: + case PC_DCBA: + case PC_DST: + case PC_DSTT: + case PC_DSTST: + case PC_DSTSTT: + if (instr->args[0].data.reg.reg >= n_real_registers[coloring_class]) + makeinterfere(0, instr->args[0].data.reg.reg); + break; + } + } + } + + if (coloring_class == RegClass_GPR && (instr->flags & fIsCall)) { + i = branch_count_volatiles(); + op = instr->args; + CError_ASSERT(219, instr->argCount != 0); + + while (op->kind != PCOp_REGISTER || !(op->data.reg.effect & EffectWrite)) { + i++; + op++; + CError_ASSERT(226, i <= instr->argCount); + } + + for (op = instr->args + i; i < instr->argCount; i++, op++) { + if (op->kind == PCOp_REGISTER && op->arg == RegClass_GPR) { + for (j = 0; j < n_scratch_registers[coloring_class]; j++) + makeinterfere(op->data.reg.reg, scratch_registers[coloring_class][j]); + } + } + } + } + } +} + +static short coalesced_path(short id) { + while (id != coalesced[id]) + id = coalesced[id]; + return id; +} + +static void coalescenodes(void) { + PCodeArg *op; + UInt32 regs; + PCodeBlock *block; + PCode *instr; + UInt32 i; + short path1; + short path2; + short node1; + short node2; + + regs = used_virtual_registers[coloring_class]; + coalesced = oalloc(sizeof(SInt16) * regs); + + for (i = 0; i < regs; i++) + coalesced[i] = i; + + for (block = pcbasicblocks; block; block = block->nextBlock) { + for (instr = block->firstPCode; instr; instr = instr->nextPCode) { + if ((instr->flags & fIsMove) && !(instr->flags & fSideEffects)) { + if (PCODE_FLAG_SET_F(instr) & fRecordBit) { + CError_FATAL(309); + continue; + } + + if (instr->argCount > 2) { + if (instr->argCount != 3 || instr->args[2].kind != PCOp_PLACEHOLDEROPERAND) { + CError_FATAL(316); + continue; + } + } + + if (PC_OP_IS_ANY_REGISTER(&instr->args[0], coloring_class)) { + path1 = coalesced_path(instr->args[0].data.reg.reg); + path2 = coalesced_path(instr->args[1].data.reg.reg); + if (path1 == path2) { + deletepcode(instr); + continue; + } + + if (!interferes(path1, path2)) { + if (path1 >= n_real_registers[coloring_class] && path2 >= n_real_registers[coloring_class]) { + if (path1 < first_fe_temporary_register[coloring_class]) + continue; + if (path1 > last_temporary_register[coloring_class]) + continue; + if (path2 < first_fe_temporary_register[coloring_class]) + continue; + if (path2 > last_temporary_register[coloring_class]) + continue; + } + + node1 = (path2 < path1) ? path2 : path1; + node2 = (path2 > path1) ? path2 : path1; + + if (coloring_class == RegClass_GPR && node2 == _CALLER_SP_) + continue; + + coalesced[node2] = node1; + for (i = 0; i < regs; i++) { + if (interferes(node2, i)) + makeinterfere(node1, i); + } + + deletepcode(instr); + } + } + } + } + } + + for (block = pcbasicblocks; block; block = block->nextBlock) { + for (instr = block->firstPCode; instr; instr = instr->nextPCode) { + op = instr->args; + i = instr->argCount; + while (i--) { + if (PC_OP_IS_ANY_REGISTER(op, coloring_class) && op->data.reg.reg != coalesced[op->data.reg.reg]) + op->data.reg.reg = coalesced_path(op->data.reg.reg); + op++; + } + } + } +} + +static void buildadjacencyvectors(void) { + IGNode *node; + UInt32 regs; + UInt32 i; + UInt32 counter; + short *array; + short *dest; + short *src; + UInt32 j; + + regs = used_virtual_registers[coloring_class]; + interferencegraph = oalloc(sizeof(IGNode *) * regs); + array = oalloc(sizeof(short) * regs); + + for (i = 0; i < regs; i++) { + counter = 0; + for (j = 0; j < regs; j++) { + if (interferes(i, j)) + array[counter++] = j; + } + + node = interferencegraph[i] = oalloc(sizeof(IGNode) + sizeof(short) * (counter - 1)); + memclrw(node, sizeof(IGNode) + sizeof(short) * (counter - 1)); + + node->x10 = i; + node->x14 = -1; + node->arraySize = counter; + node->x12 = counter; + + dest = node->array; + src = array; + for (j = 0; j < counter; j++) + *(dest++) = *(src++); + + if (i != coalesced[i]) { + node->flags |= fCoalesced; + j = coalesced_path(i); + interferencegraph[j]->flags |= fCoalescedInto; + node->x14 = j; + } + } +} + +static void eliminatedeadcode(void) { + UInt32 regs; + PCodeBlock *block; + PCode *instr; + UInt32 *vec; + UInt32 i; + PCodeArg *op; + + regs = used_virtual_registers[coloring_class]; + vec = oalloc(4 * ((regs + 31) >> 5)); + + for (block = pcbasicblocks; block; block = block->nextBlock) { + bitvectorcopy(vec, liveinfo[block->blockIndex].out, regs); + for (instr = block->lastPCode; instr; instr = instr->prevPCode) { + if (dead(instr, coloring_class, vec)) { + deletepcode(instr); + continue; + } + + op = instr->args; + i = instr->argCount; + while (i--) { + if (PC_OP_IS_WRITE_ANY_REGISTER(op, coloring_class)) + bitvectorclearbit(op->data.reg.reg, vec); + op++; + } + + op = instr->args; + i = instr->argCount; + while (i--) { + if (PC_OP_IS_READ_ANY_REGISTER(op, coloring_class)) { + int reg = op->data.reg.reg; + if (!bitvectorgetbit(reg, vec)) + op->data.reg.effect |= Effect4; + bitvectorsetbit(reg, vec); + } + op++; + } + } + } +} + +static void findrematerializations(void) { + UInt32 regs; + UInt32 i; + PCodeBlock *block; + PCode *instr; + PCodeArg *op; + IGNode *node; + + regs = used_virtual_registers[coloring_class]; + + for (block = pcbasicblocks; block; block = block->nextBlock) { + for (instr = block->lastPCode; instr; instr = instr->prevPCode) { + op = instr->args; + i = instr->argCount; + while (i--) { + if ( + PC_OP_IS_WRITE_ANY_REGISTER(op, coloring_class) && + op->data.reg.reg >= n_real_registers[coloring_class] && + !(interferencegraph[op->data.reg.reg]->flags & (fPairLow | fPairHigh)) && + !(interferencegraph[op->data.reg.reg]->flags & fIGNode40) + ) + { + node = interferencegraph[op->data.reg.reg]; + if (!node->instr8) { + node->instr8 = instr; + } else { + node->instr8 = NULL; + node->flags |= fIGNode40; + } + } + op++; + } + } + } + + for (i = 0; i < regs; i++) { + node = interferencegraph[i]; + if (node->instr8 && !is_location_independent(node->instr8)) + node->instr8 = NULL; + } +} + +void buildinterferencegraph(Object *proc) { + int regs = used_virtual_registers[coloring_class]; + + computelivevariables(proc); + eliminatedeadcode(); + buildinterferencematrix(); + if (copts.debuglisting) + pclistinterferences(register_class_format[coloring_class], regs); + coalescenodes(); + buildadjacencyvectors(); + findrematerializations(); +} diff --git a/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/RegisterInfo.c b/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/RegisterInfo.c new file mode 100644 index 0000000..177c2e0 --- /dev/null +++ b/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/RegisterInfo.c @@ -0,0 +1,381 @@ +#include "compiler/RegisterInfo.h" +#include "compiler/CodeGen.h" +#include "compiler/CError.h" +#include "compiler/CParser.h" +#include "compiler/PCode.h" +#include "compiler/CompilerTools.h" +#include "compiler/objects.h" +#include "compiler/types.h" + +short last_exception_register[RegClassMax]; +short first_fe_temporary_register[RegClassMax]; +short last_argument_register[RegClassMax]; +short _FP_; +short _CALLER_SP_; +char *special_register_names[RegClassMax][RegisterMax]; +static short used_regs_before_coloring; +static UInt8 save_state[RegisterMax]; + +short spr_to_sysreg[4] = {1, 8, 9, 0x100}; + +void asm_used_register(RegClass rclass, short reg) { + int i; + + if ((reg < n_real_registers[rclass]) && (reg_state[rclass][reg] == RegState0)) { + if (reg == nonvolatile_registers[rclass][used_nonvolatile_registers[rclass]]) { + if (assignable_registers[rclass] > 0) + assignable_registers[rclass]--; + reg_state[rclass][reg] = RegState1; + used_nonvolatile_registers[rclass]++; + } else { + for (i = used_nonvolatile_registers[rclass]; i < n_nonvolatile_registers[rclass]; i++) { + if (reg == nonvolatile_registers[rclass][i]) { + reg_state[rclass][reg] = RegState1; + if (assignable_registers[rclass] > 0) + assignable_registers[rclass]--; + } + } + } + } +} + +void retain_register(Object *obj, RegClass rclass, short reg) { + VarInfo *vi; + + CError_ASSERT(95, (short) reg < RegisterMax); + + if (reg_state[rclass][reg] == RegState0) { + assignable_registers[rclass]--; + reg_state[rclass][reg] = RegState1; + if (reg == nonvolatile_registers[rclass][used_nonvolatile_registers[rclass]]) + used_nonvolatile_registers[rclass]++; + } + + if (obj) { + vi = Registers_GetVarInfo(obj); + vi->rclass = rclass; + vi->flags |= VarInfoFlag2; + vi->reg = reg; + } +} + +void retain_GPR_pair(Object *obj, short reg, short regHi) { + VarInfo *vi; + + retain_register(NULL, RegClass_GPR, reg); + retain_register(NULL, RegClass_GPR, regHi); + + if (obj) { + vi = Registers_GetVarInfo(obj); + vi->rclass = RegClass_GPR; + vi->flags |= VarInfoFlag2 | VarInfoFlag4; + vi->reg = reg; + vi->regHi = regHi; + } +} + +int is_register_object(Object *obj) { + return obj->sclass == TK_REGISTER; +} + +int GetABIFirstNonVolatile(RegClass rclass) { + switch (rclass) { + case RegClass_SPR: return 3; + case RegClass_CRFIELD: return 2; + case RegClass_VR: return 20; + case RegClass_GPR: return 13; + case RegClass_FPR: return 14; + default: return -1; + } +} + +char GetRegisterClassName(RegClass rclass) { + switch (rclass) { + case RegClass_VR: return 'v'; + case RegClass_GPR: return 'r'; + case RegClass_FPR: return 'f'; + default: + CError_FATAL(242); + return '?'; + } +} + +static int first_nonvolatile_reg(RegClass rclass) { + return GetABIFirstNonVolatile(rclass); +} + +void setup_diagnostic_reg_strings(void) { + register_class_name[RegClass_SPR] = "SPR"; + register_class_format[RegClass_SPR] = "spr%" PRId32; + register_class_name[RegClass_CRFIELD] = "CRFIELD"; + register_class_format[RegClass_CRFIELD] = "cr%" PRId32; + register_class_name[RegClass_VR] = "VR"; + register_class_format[RegClass_VR] = "vr%" PRId32; + register_class_name[RegClass_FPR] = "FPR"; + register_class_format[RegClass_FPR] = "f%" PRId32; + register_class_name[RegClass_GPR] = "GPR"; + register_class_format[RegClass_GPR] = "r%" PRId32; +} + +void init_target_registers(void) { + int reg; + int end; + RegClass rclass; + + static int last_nonvolatile_reg[] = {3, 5, 31, 31, 31}; + static int nonvol_reserve[] = {0, 0, 0, 4, 3}; + + for (rclass = 0; rclass < RegClassMax; rclass++) { + for (reg = 0; reg < RegisterMax; reg++) + special_register_names[rclass][reg] = NULL; + } + + special_register_names[RegClass_SPR][0] = "XER"; + special_register_names[RegClass_SPR][1] = "LR"; + special_register_names[RegClass_SPR][2] = "CTR"; + special_register_names[RegClass_SPR][3] = "VRSAVE"; + special_register_names[RegClass_GPR][1] = "SP"; + + setup_diagnostic_reg_strings(); + n_real_registers[RegClass_SPR] = 4; + n_real_registers[RegClass_CRFIELD] = 8; + n_real_registers[RegClass_VR] = 32; + n_real_registers[RegClass_FPR] = 32; + n_real_registers[RegClass_GPR] = 32; + reg_state[RegClass_GPR][1] = RegState2; + reg_state[RegClass_GPR][2] = RegState2; + reg_state[RegClass_CRFIELD][5] = RegState2; + + for (rclass = 0; rclass < RegClassMax; rclass++) { + n_nonvolatile_registers[rclass] = 0; + if (last_nonvolatile_reg[rclass] >= 0) { + end = first_nonvolatile_reg(rclass); + for (reg = last_nonvolatile_reg[rclass]; reg >= end; reg--) { + if (reg_state[rclass][reg] == RegState0) { + nonvolatile_registers[rclass][n_nonvolatile_registers[rclass]++] = reg; + } + } + } + + assignable_registers[rclass] = n_nonvolatile_registers[rclass] - nonvol_reserve[rclass]; + if (assignable_registers[rclass] < 0) + assignable_registers[rclass] = 0; + + n_scratch_registers[rclass] = 0; + for (reg = 0; reg < n_real_registers[rclass]; reg++) { + if (reg < GetABIFirstNonVolatile(rclass) || reg > last_nonvolatile_reg[rclass]) { + if (reg_state[rclass][reg] == RegState0) { + scratch_registers[rclass][n_scratch_registers[rclass]++] = reg; + } + } + } + } + + _FP_ = -1; + _CALLER_SP_ = -1; + optimizing = (copts.optimizationlevel > 0) && !disable_optimizer; +} + +void assign_register_by_type(Object *obj) { + VarInfo *vi; + Type *ty; + Boolean flag; + + ty = obj->type; + vi = Registers_GetVarInfo(obj); + flag = 0; + vi->rclass = RegClassMax; + vi->reg = 0; + vi->regHi = 0; + + if ((ty->type == TYPEINT) || (ty->type == TYPEENUM) || ((ty->type == TYPEPOINTER || ty->type == TYPEARRAY) && (ty->type != TYPEARRAY)) || ((ty->type == TYPEMEMBERPOINTER) && (ty->size == 4U))) { + if (((ty->type == TYPEINT) || (ty->type == TYPEENUM)) && (ty->size == 8)) + flag = 1; + vi->rclass = RegClass_GPR; + } else if (ty->type == TYPEFLOAT) { + vi->rclass = RegClass_FPR; + } else if ((ty->type == TYPESTRUCT) && (TYPE_STRUCT(ty)->stype >= STRUCT_VECTOR_UCHAR) && (TYPE_STRUCT(ty)->stype <= STRUCT_VECTOR_PIXEL)) { + vi->rclass = RegClass_VR; + } else { + return; + } + + if (vi->rclass < RegClassMax) { + if (flag) { + CError_ASSERT(520, vi->rclass == RegClass_GPR); + if (assignable_registers[vi->rclass] > 1) + assign_GPR_pair(obj); + } else { + if (assignable_registers[vi->rclass] > 0) + assign_register_to_variable(obj, vi->rclass); + } + } +} + +void assign_GPR_pair(Object *obj) { + VarInfo *vi; + short reg; + short regHi; + + vi = Registers_GetVarInfo(obj); + if (optimizing) { + reg = used_virtual_registers[RegClass_GPR]++; + regHi = used_virtual_registers[RegClass_GPR]++; + } else { + CError_ASSERT(554, assignable_registers[RegClass_GPR] >= 2); + reg = obtain_nonvolatile_register(RegClass_GPR); + regHi = obtain_nonvolatile_register(RegClass_GPR); + retain_GPR_pair(obj, reg, regHi); + } + + vi->rclass = RegClass_GPR; + if (reg > 0 && regHi > 0) { + vi->flags |= VarInfoFlag2 | VarInfoFlag4; + vi->reg = reg; + vi->regHi = regHi; + } else { + CError_FATAL(567); + } +} + +void open_fe_temp_registers(void) { + int r; + + r = used_virtual_registers[RegClass_GPR]; + first_fe_temporary_register[RegClass_GPR] = last_temporary_register[RegClass_GPR] = r; + r = used_virtual_registers[RegClass_FPR]; + first_fe_temporary_register[RegClass_FPR] = last_temporary_register[RegClass_FPR] = r; + r = used_virtual_registers[RegClass_VR]; + first_fe_temporary_register[RegClass_VR] = last_temporary_register[RegClass_VR] = r; +} + +void set_last_exception_registers(void) { + last_exception_register[RegClass_GPR] = used_virtual_registers[RegClass_GPR] - 1; + last_exception_register[RegClass_FPR] = used_virtual_registers[RegClass_FPR] - 1; + last_exception_register[RegClass_VR] = used_virtual_registers[RegClass_VR] - 1; +} + +static VarInfo *Registers_GetNewVarInfo(void) { + VarInfo *vi = galloc(sizeof(VarInfo)); + memclrw(vi, sizeof(VarInfo)); + return vi; +} + +VarInfo *Registers_GetVarInfo(Object *obj) { + switch (obj->datatype) { + case DDATA: + if (!obj->u.data.info) + obj->u.data.info = Registers_GetNewVarInfo(); + return obj->u.data.info; + case DNONLAZYPTR: + if (!obj->u.toc.info) { + CError_FATAL(639); + obj->u.toc.info = CodeGen_GetNewVarInfo(); + } + return obj->u.toc.info; + case DLOCAL: + if (!obj->u.var.info) + CError_FATAL(647); + return obj->u.var.info; + case DABSOLUTE: + // not sure if this is the right union + if (!obj->u.data.info) + obj->u.data.info = Registers_GetNewVarInfo(); + return obj->u.data.info; + default: + CError_FATAL(660); + return NULL; + } +} + +int used_vrstate_VRs(void) { + int count = 0; + int i; + for (i = 0; i < RegisterMax; i++) { + if (reg_state[RegClass_VR][i]) + count++; + } + return count; +} + +UInt32 colored_vrs_as_vrsave(PCodeBlock *block) { + PCode *pc; + UInt32 mask; + int i; + + mask = 0; + if (copts.altivec_vrsave == 2) + return 0xFFFFFFFF; + if (copts.altivec_vrsave == 0) + return 0; + + while (block) { + for (pc = block->firstPCode; pc; pc = pc->nextPCode) { + if (pc->flags & fOpTypeVR) { + for (i = 0; i < pc->argCount; i++) { + if (pc->args[i].kind == PCOp_REGISTER && pc->args[i].arg == RegClass_VR) + mask |= 1 << (31 - pc->args[i].data.reg.reg); + } + } + } + block = block->nextBlock; + } + + return mask; +} + +void save_before_coloring_nonvolatile_registers(RegClass rclass) { + used_regs_before_coloring = used_nonvolatile_registers[rclass]; + memcpy(save_state, reg_state[rclass], sizeof(save_state)); +} + +void reset_nonvolatile_registers(RegClass rclass) { + used_nonvolatile_registers[rclass] = used_regs_before_coloring; + memcpy(reg_state[rclass], save_state, sizeof(save_state)); +} + +int is_nonvolatile_register(RegClass rclass, int reg) { + int i; + + for (i = 0; i < n_nonvolatile_registers[rclass]; i++) { + if (reg == nonvolatile_registers[rclass][i]) + return 1; + } + + return 0; +} + +void init_endian(void) { + if (copts.littleendian) { + high_offset = 4; + low_offset = 0; + high_reg = 4; + low_reg = 3; + high_reg2 = 6; + low_reg2 = 5; + } else { + high_offset = 0; + low_offset = 4; + high_reg = 3; + low_reg = 4; + high_reg2 = 5; + low_reg2 = 6; + } +} + +void update_asm_nonvolatile_registers(void) { + RegClass rclass; + int i; + int reg; + + for (rclass = 0; rclass < RegClassMax; rclass++) { + reg = n_nonvolatile_registers[rclass]; + for (i = n_nonvolatile_registers[rclass] - 1; i >= 0; i--) { + if (reg_state[rclass][nonvolatile_registers[rclass][i]] == RegState1) + break; + reg--; + } + if (reg > used_nonvolatile_registers[rclass]) + used_nonvolatile_registers[rclass] = reg; + } +} diff --git a/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/SpillCode.c b/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/SpillCode.c new file mode 100644 index 0000000..69e7e43 --- /dev/null +++ b/compiler_and_linker/BackEnd/PowerPC/RegisterAllocator/SpillCode.c @@ -0,0 +1,452 @@ +#include "compiler/SpillCode.h" +#include "compiler/CError.h" +#include "compiler/CMachine.h" +#include "compiler/CParser.h" +#include "compiler/CodeGen.h" +#include "compiler/CompilerTools.h" +#include "compiler/Coloring.h" +#include "compiler/InterferenceGraph.h" +#include "compiler/Operands.h" +#include "compiler/PCode.h" +#include "compiler/PCodeUtilities.h" +#include "compiler/Registers.h" +#include "compiler/RegisterInfo.h" +#include "compiler/StackFrame.h" +#include "compiler/objects.h" + +static int last_unused_vreg_before_spilling; +static short rTEMP_for_VR_spill; + +void estimatespillcosts(void) { + PCodeBlock *block; + PCode *instr; + IGNode *node; + PCodeArg *op; + int i; + int weight; + + for (block = pcbasicblocks; block; block = block->nextBlock) { + if (copts.optimizesize) + weight = 1; + else + weight = block->loopWeight; + + for (instr = block->firstPCode; instr; instr = instr->nextPCode) { + op = instr->args; + i = instr->argCount; + while (i--) { + if (PC_OP_IS_READ_ANY_REGISTER(op, coloring_class)) { + node = interferencegraph[op->data.reg.reg]; + if (node->instr8 || copts.optimizesize) + node->spillCost += weight; + else + node->spillCost += weight * 2; + } + op++; + } + + op = instr->args; + i = instr->argCount; + while (i--) { + if (PC_OP_IS_WRITE_ANY_REGISTER(op, coloring_class)) { + node = interferencegraph[op->data.reg.reg]; + if (node->instr8 || (instr->flags & fIsArgInit)) + node->spillCost -= weight; + else + node->spillCost += weight; + } + op++; + } + } + } +} + +static Object *makespilltemporary(Type *type) { + Object *obj = lalloc(sizeof(Object)); + memclrw(obj, sizeof(Object)); + + obj->otype = OT_OBJECT; + obj->access = ACCESSPUBLIC; + obj->datatype = DLOCAL; + obj->type = type; + obj->name = CParser_GetUniqueName(); + obj->u.var.info = CodeGen_GetNewVarInfo(); + obj->u.var.uid = 0; + + return obj; +} + +static PCode *rematerialize_spilled_register(short reg, IGNode *node) { + PCode *instr = copypcode(node->instr8); + + CError_ASSERT(128, instr->args[0].kind == PCOp_REGISTER); + + instr->args[0].data.reg.reg = reg; + return instr; +} + +static void insert_load_spilled_register(PCode *instr, short reg, IGNode *node) { + Type *type; + Opcode opcode; + Object *object; + PCode *newInstr; + PCode *newInstr2; + SInt32 offset; + Operand operand; + + type = node->spillTemporary->type; + switch (coloring_class) { + case RegClass_CRFIELD: + case RegClass_GPR: + switch (type->size) { + case 1: + opcode = PC_LBZ; + break; + case 2: + opcode = is_unsigned(type) ? PC_LHZ : PC_LHA; + break; + case 4: + opcode = PC_LWZ; + break; + case 8: + opcode = PC_LWZ; + break; + default: + CError_FATAL(187); + } + + memclrw(&operand, sizeof(Operand)); + operand.optype = OpndType_Symbol; + operand.object = node->spillTemporary; + CError_ASSERT(222, node->spillTemporary->datatype == DLOCAL); + + coerce_to_addressable(&operand); + + CError_ASSERT(233, operand.optype == OpndType_GPR_ImmOffset); + + CError_ASSERT(237, node->spillTemporary->datatype == DLOCAL); + + if (node->flags & fPairLow) + offset = low_offset; + else if (node->flags & fPairHigh) + offset = high_offset; + else + offset = 0; + insertpcodebefore(instr, makepcode(opcode, reg, operand.reg, operand.object, operand.immOffset + offset)); + break; + + case RegClass_FPR: + CError_ASSERT(253, node->spillTemporary->datatype == DLOCAL); + + if (node->flags & fPairLow) + offset = low_offset; + else if (node->flags & fPairHigh) + offset = high_offset; + else + offset = 0; + + object = node->spillTemporary; + insertpcodebefore( + instr, + makepcode( + (type->size == 8) ? PC_LFD : PC_LFS, + reg, + local_base_register(object), + object, + offset + ) + ); + break; + + case RegClass_VR: + CError_ASSERT(320, node->spillTemporary->datatype == DLOCAL); + + object = node->spillTemporary; + newInstr = makepcode(PC_ADDI, rTEMP_for_VR_spill, local_base_register(object), object, 0); + newInstr2 = makepcode(PC_LVX, reg, 0, rTEMP_for_VR_spill); + insertpcodebefore(instr, newInstr); + insertpcodeafter(newInstr, newInstr2); + break; + + default: + CError_FATAL(333); + } +} + +static void insert_store_spilled_register(PCode *instr, Boolean flag, short reg, IGNode *node) { + Object *object; // r31 + Opcode opcode; // r30 + SInt32 offset; // r26 + PCode *newInstr2; // r26 + PCode *newInstr; // r25 + Type *type; // r25 + + object = node->spillTemporary; + type = object->type; + + switch (coloring_class) { + case RegClass_CRFIELD: + case RegClass_GPR: + switch (type->size) { + case 1: + opcode = PC_STB; + break; + case 2: + opcode = PC_STH; + break; + case 4: + opcode = PC_STW; + break; + case 8: + opcode = PC_STW; + break; + default: + CError_FATAL(391); + } + + if (node->flags & fPairLow) + offset = low_offset; + else if (node->flags & fPairHigh) + offset = high_offset; + else + offset = 0; + + newInstr = makepcode(opcode, reg, local_base_register(object), object, offset); + if (flag) + insertpcodebefore(instr, newInstr); + else + insertpcodeafter(instr, newInstr); + + break; + + case RegClass_FPR: + newInstr = makepcode((type->size == 8) ? PC_STFD : PC_STFS, reg, local_base_register(object), object, 0); + if (flag) + insertpcodebefore(instr, newInstr); + else + insertpcodeafter(instr, newInstr); + + break; + + case RegClass_VR: + newInstr = makepcode(PC_ADDI, rTEMP_for_VR_spill, local_base_register(object), object, 0); + newInstr2 = makepcode(PC_STVX, reg, 0, rTEMP_for_VR_spill); + if (flag) + insertpcodebefore(instr, newInstr); + else + insertpcodeafter(instr, newInstr); + insertpcodeafter(newInstr, newInstr2); + + break; + + default: + CError_FATAL(527); + } +} + +static void spillinstruction(PCodeBlock *block, PCode *instr) { + int reg; + int reg2; + int regs; + IGNode *node; + PCodeArg *op; + int i; + PCodeArg *op2; + int j; + int readCounter; + int writeCounter; + Boolean flag; + + regs = used_virtual_registers[coloring_class]; + flag = 0; + for (i = 0, op = instr->args; i < instr->argCount; i++, op++) { + CError_ASSERT(563, instr->block != NULL); + + if ( + PC_OP_IS_ANY_REGISTER(op, coloring_class) && + (reg = op->data.reg.reg) < regs && + ((node = interferencegraph[op->data.reg.reg])->flags & fSpilled) + ) + { + reg2 = used_virtual_registers[coloring_class]++; + readCounter = 0; + writeCounter = 0; + + for (j = i, op2 = op; j < instr->argCount; j++, op2++) { + if (PC_OP_IS_REGISTER(op2, coloring_class, reg)) { + if (op2->data.reg.effect & EffectRead) + readCounter++; + if (op2->data.reg.effect & EffectWrite) + writeCounter++; + op2->data.reg.reg = reg2; + op2->data.reg.effect |= Effect40; + } + } + + if (readCounter) { + if (node->instr8) + insertpcodebefore(instr, rematerialize_spilled_register(reg2, node)); + else + insert_load_spilled_register(instr, reg2, node); + } + + if (writeCounter) { + if (node->instr8 || (instr->flags & fIsArgInit)) + flag = 1; + else + insert_store_spilled_register(instr, 0, reg2, node); + } + } + } + + if (flag) + deletepcode(instr); +} + +static void spillcopy(PCodeBlock *block, PCode *instr) { + IGNode *node1; + IGNode *node2; + int reg; + + node1 = interferencegraph[instr->args[1].data.reg.reg]; + node2 = interferencegraph[instr->args[0].data.reg.reg]; + + if (node1->flags & fSpilled) { + if (node2->flags & fSpilled) { + reg = used_virtual_registers[coloring_class]++; + if (node1->instr8) + insertpcodebefore(instr, rematerialize_spilled_register(reg, node1)); + else + insert_load_spilled_register(instr, reg, node1); + insert_store_spilled_register(instr, 1, reg, node2); + } else { + if (node1->instr8) + insertpcodebefore(instr, rematerialize_spilled_register(instr->args[0].data.reg.reg, node1)); + else + insert_load_spilled_register(instr, instr->args[0].data.reg.reg, node1); + } + } else { + insert_store_spilled_register(instr, 1, instr->args[1].data.reg.reg, node2); + } + + deletepcode(instr); +} + +static void spillcall(PCodeBlock *block, PCode *instr) { + PCodeArg *opSrc; + PCodeArg *opDst; + int opCount; + int volatileCount; + int i; + + opCount = instr->argCount; + volatileCount = branch_count_volatiles(); + + opDst = instr->args + volatileCount; + opSrc = instr->args + volatileCount; + for (i = volatileCount; i < opCount; i++) { + if ( + PC_OP_IS_ANY_REGISTER(opSrc, coloring_class) && + opSrc->data.reg.reg >= n_real_registers[coloring_class] && + (interferencegraph[opSrc->data.reg.reg]->flags & fSpilled) + ) + { + instr->argCount--; + } else { + *opDst = *opSrc; + opDst++; + } + opSrc++; + } + + spillinstruction(block, instr); +} + +static void assign_spill_locations(void) { + UInt32 i; + IGNode *node; + Type *type; + + last_unused_vreg_before_spilling = used_virtual_registers[coloring_class]; + for (i = n_real_registers[coloring_class]; i < last_unused_vreg_before_spilling; i++) { + node = interferencegraph[i]; + if (node->flags & fCoalesced) + continue; + if (!(node->flags & fSpilled)) + continue; + + if (!node->spillTemporary) { + switch (coloring_class) { + case RegClass_GPR: + type = TYPE(&stunsignedlong); + break; + case RegClass_CRFIELD: + type = TYPE(&stunsignedlong); + break; + case RegClass_FPR: + type = TYPE(&stunsignedlong); + break; + case RegClass_VR: + type = TYPE(&stvectorunsignedchar); + break; + default: + CError_FATAL(771); + } + + node->spillTemporary = makespilltemporary(type); + } + + if (node->spillTemporary->datatype == DLOCAL && !(node->spillTemporary->u.var.info->flags & VarInfoFlag1)) + assign_local_memory(node->spillTemporary); + + if (node->flags & fPairHigh) + Registers_GetVarInfo(node->spillTemporary)->regHi = Register0; + else + Registers_GetVarInfo(node->spillTemporary)->reg = Register0; + } +} + +void insertspillcode(void) { + PCodeBlock *block; + PCode *instr; + PCode *nextInstr; + PCodeArg *op; + UInt32 i; + int flag; + + rTEMP_for_VR_spill = 0; + assign_spill_locations(); + + for (block = pcbasicblocks; block; block = block->nextBlock) { + for (instr = block->firstPCode; instr; instr = nextInstr) { + nextInstr = instr->nextPCode; + flag = 0; + op = instr->args; + i = instr->argCount; + while (i--) { + if ( + PC_OP_IS_ANY_REGISTER(op, coloring_class) && + op->data.reg.reg < last_unused_vreg_before_spilling && + (interferencegraph[op->data.reg.reg]->flags & fSpilled) + ) + { + flag = 1; + break; + } + op++; + } + + if (flag) { + if (coloring_class == RegClass_VR && rTEMP_for_VR_spill == 0) + rTEMP_for_VR_spill = used_virtual_registers[RegClass_GPR]++; + + if (instr->flags & fIsMove) + spillcopy(block, instr); + else if (instr->flags & fIsCall) + spillcall(block, instr); + else + spillinstruction(block, instr); + } + } + } +} |