move lots of source files around to match their actual placement in the original treemain

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,
+                    &register_defs[(char) op->arg][op->data.reg.reg],
+                    &register_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;
+}