diff options
Diffstat (limited to 'compiler_and_linker/BackEnd/PowerPC/Scheduler/Scheduler.c')
| -rw-r--r-- | compiler_and_linker/BackEnd/PowerPC/Scheduler/Scheduler.c | 547 |
1 files changed, 547 insertions, 0 deletions
diff --git a/compiler_and_linker/BackEnd/PowerPC/Scheduler/Scheduler.c b/compiler_and_linker/BackEnd/PowerPC/Scheduler/Scheduler.c new file mode 100644 index 0000000..23b580f --- /dev/null +++ b/compiler_and_linker/BackEnd/PowerPC/Scheduler/Scheduler.c @@ -0,0 +1,547 @@ +#include "compiler/Scheduler.h" +#include "compiler/CError.h" +#include "compiler/CParser.h" +#include "compiler/Alias.h" +#include "compiler/CompilerTools.h" +#include "compiler/PCode.h" +#include "compiler/Registers.h" + +#ifdef __MWERKS__ +#pragma options align=mac68k +#endif +typedef struct DGNode { + struct DGNode *x0; + struct DGNode *x4; + struct DGSuccessor *successors; + PCode *instr; + UInt16 x10; + UInt16 x12; + UInt16 x14; + UInt16 x16; + short predCount; +} DGNode; + +typedef struct DGSuccessor { + struct DGSuccessor *next; + DGNode *node; + UInt16 x8; +} DGSuccessor; + +typedef struct DGNodeList { + struct DGNodeList *next; + DGNode *node; +} DGNodeList; +#ifdef __MWERKS__ +#pragma options align=reset +#endif + +static DGNodeList **register_uses[RegClassMax]; +static DGNodeList **register_defs[RegClassMax]; +static DGNodeList *memory_uses; +static DGNodeList *memory_defs; +static DGNodeList *side_effects; +static DGNodeList *volatile_refs; +static DGNode *defaultsuccessor; +static UInt16 criticalpath; +static MachineInfo *MI; + +static void initresources(void) { + int rclass; + int i; + + for (rclass = 0; (char) rclass < RegClassMax; rclass++) { + register_uses[(char) rclass] = oalloc(sizeof(DGNodeList *) * used_virtual_registers[(char) rclass]); + register_defs[(char) rclass] = oalloc(sizeof(DGNodeList *) * used_virtual_registers[(char) rclass]); + for (i = 0; i < used_virtual_registers[(char) rclass]; i++) { + register_uses[(char) rclass][i] = register_defs[(char) rclass][i] = NULL; + } + } + + memory_uses = memory_defs = NULL; + side_effects = NULL; + volatile_refs = NULL; + criticalpath = 0; +} + +static DGNode *makedgnode(PCode *instr) { + DGNode *node; + + node = oalloc(sizeof(DGNode)); + node->x0 = NULL; + node->x4 = NULL; + node->successors = NULL; + node->instr = instr; + node->x10 = node->x16 = MI->latency(instr); + node->x12 = 0; + node->x14 = 0; + node->predCount = 0; + return node; +} + +static DGNode *adddgnode(DGNode *head, DGNode *node) { + if (head) + head->x4 = node; + node->x0 = head; + return node; +} + +static DGNode *removedgnode(DGNode *head, DGNode *node) { + if (node->x4) + node->x4->x0 = node->x0; + else + head = node->x0; + + if (node->x0) + node->x0->x4 = node->x4; + + return head; +} + +static void addtolist(DGNodeList **list, DGNode *node) { + DGNodeList *entry = oalloc(sizeof(DGNodeList)); + entry->node = node; + entry->next = *list; + *list = entry; +} + +static DGNodeList *makedglistnode(DGNode *node) { + DGNodeList *list = oalloc(sizeof(DGNodeList)); + list->next = NULL; + list->node = node; + return list; +} + +int is_same_operand(PCodeArg *a, PCodeArg *b) { + if (a->kind != b->kind) + return 0; + + switch (a->kind) { + case PCOp_IMMEDIATE: + if (a->data.imm.value != b->data.imm.value) + return 0; + break; + case PCOp_REGISTER: + if ((char) a->arg != (char) b->arg) + return 0; + if (a->data.reg.reg != b->data.reg.reg) + return 0; + break; + case PCOp_MEMORY: + if (a->data.mem.offset != b->data.mem.offset) + return 0; + if (a->data.mem.obj != b->data.mem.obj) + return 0; + break; + case PCOp_LABEL: + if (a->data.label.label != b->data.label.label) + return 0; + break; + } + + return 1; +} + +static void addsuccessor(DGNode *a, DGNode *b, Boolean flag) { + int v6; + int r29; + DGSuccessor *succ; + + if (flag) + v6 = a->x10; + else + v6 = 0; + + if (a != b) { + r29 = (v6 > 0) ? v6 : 0; + for (succ = a->successors; succ; succ = succ->next) { + if (succ->node == b) { + if (succ->x8 < r29) { + succ->x8 = r29; + if (b->x16 + succ->x8 > a->x16) + a->x16 = b->x16 + succ->x8; + } + return; + } + } + + succ = oalloc(sizeof(DGSuccessor)); + succ->node = b; + succ->next = a->successors; + a->successors = succ; + succ->x8 = r29; + + if (flag && (succ->node->instr->flags & fIsBranch)) + succ->x8 += MI->x8; + + b->predCount++; + + if (b->x16 + succ->x8 > a->x16) + a->x16 = b->x16 + succ->x8; + } +} + +static void serializeall(DGNode *nodes, DGNode *node) { + DGNode *scan; + + for (scan = nodes; scan; scan = scan->x0) + addsuccessor(node, scan, 0); +} + +static void serializelist(DGNode *node, DGNodeList *list) { + while (list) { + if (list->node != node) + addsuccessor(node, list->node, 0); + list = list->next; + } +} + +static void serializeregister(int rclass, DGNode *node, DGNodeList **defs, DGNodeList **uses, int isWrite) { + DGNodeList *list; + + if (isWrite) { + for (list = *uses; list; list = list->next) { + if (list->node != node) + addsuccessor(node, list->node, 1); + } + for (list = *defs; list; list = list->next) { + if (list->node != node) + addsuccessor(node, list->node, ((char) rclass == RegClass_SPR) || (MI->x4 == 0)); + } + + list = makedglistnode(node); + list->next = *defs; + *defs = list; + } else { + for (list = *defs; list; list = list->next) { + if (list->node != node) + addsuccessor(node, list->node, ((char) rclass == RegClass_SPR) || (MI->x4 == 0)); + } + + list = makedglistnode(node); + list->next = *uses; + *uses = list; + } +} + +static void serialize_load(DGNode *node) { + DGNodeList *list; + + for (list = memory_defs; list; list = list->next) { + if (may_alias(node->instr, list->node->instr)) + addsuccessor(node, list->node, 1); + } + + addtolist(&memory_uses, node); +} + +static void serialize_store(DGNode *node) { + DGNodeList *list; + + for (list = memory_uses; list; list = list->next) { + if (may_alias(node->instr, list->node->instr)) + addsuccessor(node, list->node, 1); + } + for (list = memory_defs; list; list = list->next) { + if (may_alias(node->instr, list->node->instr)) + addsuccessor(node, list->node, 1); + } + + addtolist(&memory_defs, node); + if (node->instr->flags & fPCodeFlag40000) + addtolist(&memory_uses, node); +} + +static void findsuccessors(DGNode *nodes, DGNode *node) { + PCode *instr; + PCodeArg *op; + int i; + + instr = node->instr; + for (i = 0, op = instr->args; i < instr->argCount; i++, op++) { + switch (op->kind) { + case PCOp_IMMEDIATE: + case PCOp_MEMORY: + break; + case PCOp_REGISTER: + if ( + op->data.reg.reg < 0 || + op->data.reg.reg > used_virtual_registers[(char) op->arg] + ) + { + CError_FATAL(491); + } + + if (op->kind == PCOp_REGISTER && op->arg == RegClass_GPR) { + if (op->data.reg.reg == Register2) + break; + if (op->data.reg.reg == Register0 && !(op->data.reg.effect & (EffectRead | EffectWrite))) + break; + } + + serializeregister( + op->arg, + node, + ®ister_defs[(char) op->arg][op->data.reg.reg], + ®ister_uses[(char) op->arg][op->data.reg.reg], + op->data.reg.effect & EffectWrite + ); + + break; + } + } + + if (instr->flags & (fIsRead | fPCodeFlag20000)) + serialize_load(node); + else if (instr->flags & (fIsWrite | fPCodeFlag40000)) + serialize_store(node); + + if (instr->flags & fIsVolatile) { + serializelist(node, volatile_refs); + addtolist(&volatile_refs, node); + } + + if ( + ((instr->flags & fIsCall | fIsBranch) && (instr->flags & fLink)) || + (instr->flags & fSideEffects) || + MI->serializes(instr) + ) + { + serializeall(nodes, node); + addtolist(&side_effects, node); + } + + if (side_effects) + serializelist(node, side_effects); + + if (!node->successors && defaultsuccessor) + addsuccessor(node, defaultsuccessor, 0); + + if (node->x16 > criticalpath) + criticalpath = node->x16; +} + +static void computedeadlines(DGNode *nodes) { + while (nodes) { + nodes->x14 = criticalpath - nodes->x16; + nodes = nodes->x0; + } +} + +static int uncovering(DGNode *node) { + int counter; + DGSuccessor *succ; + + counter = 0; + for (succ = node->successors; succ; succ = succ->next) { + if (succ->node->predCount == 1) + counter++; + } + + return counter; +} + +static DGNode *selectinstruction(DGNode *nodes, UInt16 counter) { + DGNode *node; + DGNode *node2; + int a; + int b; + + node = nodes; + while (node) { + if (node->predCount == 0 && node->x12 <= counter && MI->can_issue(node->instr)) + break; + node = node->x0; + } + + if (!node) + return NULL; + + for (node2 = node->x0; node2; node2 = node2->x0) { + if ( + node2->predCount == 0 && + node2->x12 <= counter && + MI->can_issue(node2->instr) && + (node->x14 > counter || node2->x14 <= counter) + ) + { + if (node->x14 > counter && node2->x14 <= counter) { + node = node2; + continue; + } + + if ((a = uncovering(node)) > (b = uncovering(node2))) + continue; + + if (a < b) { + node = node2; + continue; + } + + if (node->x16 > node2->x16) + continue; + + if (node->x16 < node2->x16) { + node = node2; + continue; + } + + if (coloring) { + if (opcodeinfo[node->instr->op].x9 < opcodeinfo[node2->instr->op].x9) + continue; + + if (opcodeinfo[node->instr->op].x9 > opcodeinfo[node2->instr->op].x9) + node = node2; + } + } + } + + return node; +} + +static void holdoffsuccessors(DGNode *node, UInt16 counter) { + DGSuccessor *succ; + DGNode *n; + + for (succ = node->successors; succ; succ = succ->next) { + n = succ->node; + n->predCount--; + if (n->x12 < counter + succ->x8) + n->x12 = counter + succ->x8; + } +} + +static void scheduleblock(PCodeBlock *block) { + DGNode *node; + UInt16 counter; + PCode *instr; + UInt16 i; + DGNode *head; + + initresources(); + defaultsuccessor = NULL; + head = NULL; + + for (instr = block->lastPCode; instr; instr = instr->prevPCode) { + DGNode *n = makedgnode(instr); + findsuccessors(head, n); + if (instr->flags & fIsBranch) + defaultsuccessor = n; + head = adddgnode(head, n); + } + + computedeadlines(head); + block->firstPCode = block->lastPCode = NULL; + block->pcodeCount = 0; + + MI->initialize(); + counter = 0; + while (head != NULL) { + for (i = 0; i < MI->x0; i++) { + if (head == NULL) + break; + + node = selectinstruction(head, counter); + if (!node) + break; + + instr = node->instr; + if (node->successors) + holdoffsuccessors(node, counter); + + appendpcode(block, instr); + MI->issue(instr); + head = removedgnode(head, node); + } + + MI->advance_clock(); + counter++; + } + + freeoheap(); +} + +void scheduleinstructions(Boolean flag) { + PCodeBlock *block; + int cpu; + + cpu = copts.scheduling; + if (cpu == 10) { + MI = &machine7450; + } else if (copts.altivec_model != 0 || cpu == 7) { + MI = &machine7400; + } else if (cpu == 2) { + MI = &machine603; + } else if (cpu == 5) { + MI = &machine603e; + } else if (cpu == 3) { + MI = &machine604; + } else if (cpu == 6) { + MI = &machine604; + } else if (cpu == 4) { + MI = &machine750; + } else if (cpu == 1) { + MI = &machine601; + } else if (cpu == 9) { + MI = &machine821; + } else { + MI = &machine603; + } + + gather_alias_info(); + + for (block = pcbasicblocks; block; block = block->nextBlock) { + if ( + block->pcodeCount > 2 && + (flag || !(block->flags & (fIsProlog | fIsEpilogue))) && + !(block->flags & fScheduled) + ) + { + scheduleblock(block); + block->flags |= fScheduled; + } + } +} + +int is_dependent(PCode *a, PCode *b, char rclass) { + int i; + int reg; + PCodeArg *op; + + if ( + b && + b->argCount >= 1 && + b->args[0].kind == PCOp_REGISTER && + (char) b->args[0].arg == rclass && + (b->args[0].data.reg.effect & EffectWrite) + ) + { + reg = b->args[0].data.reg.reg; + for (i = 0; i < a->argCount; i++) { + op = &a->args[i]; + if ( + op->kind == PCOp_REGISTER && + (char) op->arg == rclass && + (op->data.reg.effect & (EffectRead | EffectWrite)) && + op->data.reg.reg == reg + ) + return 1; + } + } + + return 0; +} + +int uses_vpermute_unit(PCode *instr) { + int cpu; + + cpu = copts.scheduling; + if (cpu == 10) + return machine7450.uses_vpermute_unit(instr); + if (copts.altivec_model != 0 || cpu == 7) + return machine7400.uses_vpermute_unit(instr); + return 0; +} + +int default_uses_vpermute_unit(PCode *instr) { + return 0; +} |