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

1 files changed, 661 insertions, 0 deletions

diff --git a/compiler_and_linker/BackEnd/PowerPC/GlobalOptimizer/ValueNumbering.c b/compiler_and_linker/BackEnd/PowerPC/GlobalOptimizer/ValueNumbering.c
new file mode 100644
index 0000000..0907fa1
--- /dev/null
+++ b/compiler_and_linker/BackEnd/PowerPC/GlobalOptimizer/ValueNumbering.c
@@ -0,0 +1,661 @@
+#include "compiler/ValueNumbering.h"
+#include "compiler/Alias.h"
+#include "compiler/PCode.h"
+#include "compiler/Registers.h"
+#include "compiler/RegisterInfo.h"
+#include "compiler/CompilerTools.h"
+#include "compiler/CError.h"
+
+typedef struct ValueLabel {
+    struct ValueLabel *next;
+    PCodeArg op;
+} ValueLabel;
+
+typedef struct AvailableValue {
+    struct AvailableValue *next;
+    ValueLabel *labelled;
+    PCode *pcode;
+    int killedregister;
+    int aliasnumber;
+    int opnumbers[0];
+} AvailableValue;
+
+typedef struct RegValue {
+    int number;
+    int x4;
+    AvailableValue *available;
+} RegValue;
+
+typedef struct State {
+    void *stackedvalues;
+    int valueceiling;
+} State;
+
+typedef struct StackedValue {
+    struct StackedValue *next;
+    PCodeArg op;
+    RegValue value;
+    Alias *alias;
+    PCode *valuepcode;
+} StackedValue;
+
+int removedcommonsubexpressions;
+int nextvaluenumber;
+static AvailableValue *opvalue[428];
+static RegValue *regvalue[RegClassMax];
+static StackedValue *stackedvalues;
+static int valueceiling;
+static int moreaggressiveoptimization;
+
+static void allocatecsedatastructures(void) {
+    char rclass;
+
+    for (rclass = 0; rclass < RegClassMax; rclass++)
+        regvalue[(char) rclass] = oalloc(sizeof(RegValue) * used_virtual_registers[(char) rclass]);
+}
+
+static void initializecsedatastructures(void) {
+    RegValue *rv;
+    char rclass;
+    int i;
+
+    nextvaluenumber = 0;
+
+    for (i = 0; i < 428; i++)
+        opvalue[i] = NULL;
+
+    for (rclass = 0; rclass < RegClassMax; rclass++) {
+        rv = regvalue[(char) rclass];
+        for (i = 0; i < used_virtual_registers[(char) rclass]; i++, rv++) {
+            rv->number = nextvaluenumber++;
+            rv->x4 = 0;
+            rv->available = NULL;
+        }
+    }
+
+    initialize_alias_values();
+    stackedvalues = NULL;
+    valueceiling = 0x7FFFFFFF;
+}
+
+static void labelvalue(AvailableValue *av, PCodeArg *op) {
+    ValueLabel *label = oalloc(sizeof(ValueLabel));
+    label->op = *op;
+    label->next = av->labelled;
+    av->labelled = label;
+}
+
+static void unlabelvalue(AvailableValue *av, PCodeArg *op) {
+    ValueLabel *labelled;
+    ValueLabel **ptr;
+
+    ptr = &av->labelled;
+    while ((labelled = *ptr)) {
+        if (labelled->op.data.reg.reg == op->data.reg.reg)
+            *ptr = labelled->next;
+        else
+            ptr = &labelled->next;
+    }
+}
+
+static void stackregistervalue(PCodeArg *op, RegValue *value) {
+    StackedValue *stacked = oalloc(sizeof(StackedValue));
+    stacked->next = stackedvalues;
+    stackedvalues = stacked;
+
+    stacked->op = *op;
+    stacked->value = *value;
+}
+
+static void stackmemoryvalue(Alias *alias) {
+    StackedValue *stacked = oalloc(sizeof(StackedValue));
+    stacked->next = stackedvalues;
+    stackedvalues = stacked;
+
+    stacked->op.kind = PCOp_MEMORY;
+    stacked->alias = alias;
+    stacked->value.number = alias->valuenumber;
+    stacked->valuepcode = alias->valuepcode;
+}
+
+static void unstackvalue(StackedValue *stacked) {
+    PCodeArg *op = &stacked->op;
+    RegValue *value;
+
+    if (stacked->op.kind == PCOp_MEMORY) {
+        stacked->alias->valuenumber = stacked->value.number;
+        stacked->alias->valuepcode = stacked->valuepcode;
+    } else {
+        value = &regvalue[op->arg][op->data.reg.reg];
+        if (value->available)
+            unlabelvalue(value->available, op);
+        value->number = stacked->value.number;
+        value->x4 = stacked->value.x4;
+        value->available = stacked->value.available;
+        if (value->available)
+            labelvalue(value->available, op);
+    }
+}
+
+static int samevalue(PCodeArg *op1, PCodeArg *op2) {
+    return regvalue[op1->arg][op1->data.reg.reg].number == regvalue[op2->arg][op2->data.reg.reg].number;
+}
+
+static int killregister(PCodeArg *op) {
+    RegValue *value;
+
+    value = &regvalue[op->arg][op->data.reg.reg];
+    if (value->number < valueceiling && nextvaluenumber >= valueceiling)
+        stackregistervalue(op, value);
+
+    if (value->available)
+        unlabelvalue(value->available, op);
+    value->available = NULL;
+    value->x4 = 0;
+    return value->number = nextvaluenumber++;
+}
+
+void killmemory(Alias *alias, PCode *newValue) {
+    if (alias->valuenumber < valueceiling && nextvaluenumber >= valueceiling)
+        stackmemoryvalue(alias);
+
+    if (newValue) {
+        alias->valuenumber = regvalue[newValue->args[0].arg][newValue->args[0].data.reg.reg].number;
+        alias->valuepcode = newValue;
+    } else {
+        alias->valuenumber = nextvaluenumber++;
+        alias->valuepcode = NULL;
+    }
+}
+
+static void killspecificCSEs(short op) {
+    AvailableValue *av;
+    ValueLabel *labelled;
+
+    for (av = opvalue[op]; av; av = av->next) {
+        for (labelled = av->labelled; labelled; labelled = labelled->next)
+            killregister(&labelled->op);
+    }
+}
+
+static void killallCSEs(void) {
+    AvailableValue *av;
+    ValueLabel *labelled;
+    int i;
+
+    for (i = 0; i < 428; i++) {
+        for (av = opvalue[i]; av; av = av->next) {
+            for (labelled = av->labelled; labelled; labelled = labelled->next)
+                killregister(&labelled->op);
+        }
+    }
+}
+
+static void killregisters(PCode *pcode) {
+    PCodeArg *op;
+    int i;
+
+    for (i = 0, op = pcode->args; i < pcode->argCount; i++, op++) {
+        if (op->kind == PCOp_REGISTER && (op->data.reg.effect & EffectWrite))
+            killregister(op);
+    }
+}
+
+static void copyregister(PCodeArg *src, PCodeArg *dest) {
+    RegValue *srcvalue;
+    RegValue *destvalue;
+
+    srcvalue = &regvalue[src->arg][src->data.reg.reg];
+    destvalue = &regvalue[dest->arg][dest->data.reg.reg];
+
+    if (destvalue->number < valueceiling && nextvaluenumber >= valueceiling)
+        stackregistervalue(dest, destvalue);
+
+    if (destvalue->available)
+        unlabelvalue(destvalue->available, dest);
+    destvalue->available = srcvalue->available;
+    if (destvalue->available)
+        labelvalue(destvalue->available, dest);
+
+    destvalue->number = srcvalue->number;
+
+    if (srcvalue->x4 && srcvalue->number == regvalue[src->arg][srcvalue->x4].number)
+        destvalue->x4 = srcvalue->x4;
+    else
+        destvalue->x4 = src->data.reg.reg;
+}
+
+static int matchvalues(AvailableValue *av, PCode *match) {
+    PCodeArg *avOp;
+    PCodeArg *matchOp;
+    int i;
+
+    for (avOp = &av->pcode->args[0], matchOp = &match->args[0], i = 0; i < match->argCount; i++, avOp++, matchOp++) {
+        if (i != 0) {
+            switch (avOp->kind) {
+                case PCOp_REGISTER:
+                    if (av->opnumbers[i] != regvalue[matchOp->arg][matchOp->data.reg.reg].number)
+                        return 0;
+                    break;
+                case PCOp_MEMORY:
+                    if (matchOp->kind != PCOp_MEMORY)
+                        return 0;
+                    if (matchOp->data.mem.obj != avOp->data.mem.obj)
+                        return 0;
+                    if (matchOp->data.mem.offset != avOp->data.mem.offset)
+                        return 0;
+                    if ((unsigned char) matchOp->arg != (unsigned char) avOp->arg)
+                        return 0;
+                    break;
+                case PCOp_IMMEDIATE:
+                    if (matchOp->kind != PCOp_IMMEDIATE)
+                        return 0;
+                    if (matchOp->data.imm.value != avOp->data.imm.value)
+                        return 0;
+                    break;
+                case PCOp_LABEL:
+                    if (matchOp->kind != PCOp_LABEL)
+                        return 0;
+                    if (matchOp->data.label.label != avOp->data.label.label)
+                        return 0;
+                    break;
+                case PCOp_SYSREG:
+                    CError_FATAL(572);
+            }
+        }
+    }
+
+    if ((match->flags & (fIsRead | fPCodeFlag20000)) && match->alias->valuenumber != av->aliasnumber)
+        return 0;
+
+    return 1;
+}
+
+static void chooselocation(AvailableValue *av, PCodeArg *op) {
+    ValueLabel *labelled;
+    PCodeArg *baseop;
+
+    baseop = &av->pcode->args[0];
+    labelled = av->labelled;
+    while (labelled) {
+        if (labelled->op.data.reg.reg == baseop->data.reg.reg) {
+            *op = labelled->op;
+            return;
+        }
+        labelled = labelled->next;
+    }
+
+    *op = av->labelled[0].op;
+}
+
+static int findavailablevalue(PCode *pcode, PCodeArg *op) {
+    AvailableValue *av;
+    PCodeArg tmp1;
+    PCodeArg tmp2;
+
+    for (av = opvalue[pcode->op]; av; av = av->next) {
+        if (av->labelled && av->pcode->flags == pcode->flags && av->pcode->argCount == pcode->argCount) {
+            if (!matchvalues(av, pcode)) {
+                if (!(pcode->flags & fCommutative))
+                    continue;
+
+                tmp1 = pcode->args[1];
+                pcode->args[1] = pcode->args[2];
+                pcode->args[2] = tmp1;
+
+                if (!matchvalues(av, pcode)) {
+                    tmp2 = pcode->args[1];
+                    pcode->args[1] = pcode->args[2];
+                    pcode->args[2] = tmp2;
+                    continue;
+                }
+            }
+            chooselocation(av, op);
+            return 1;
+        }
+    }
+
+    return 0;
+}
+
+static void addavailablevalue(PCode *pcode) {
+    AvailableValue *av;
+    PCodeArg *op;
+    int i;
+
+    av = oalloc(sizeof(AvailableValue) + sizeof(int) * pcode->argCount);
+    av->labelled = NULL;
+    av->pcode = pcode;
+    for (i = 0, op = &pcode->args[0]; i < pcode->argCount; i++, op++) {
+        if (op->kind == PCOp_REGISTER)
+            av->opnumbers[i] = regvalue[op->arg][op->data.reg.reg].number;
+    }
+
+    if (pcode->flags & (fIsRead | fPCodeFlag20000))
+        av->aliasnumber = pcode->alias->valuenumber;
+
+    op = &pcode->args[0];
+    av->killedregister = killregister(op);
+    labelvalue(av, op);
+    regvalue[op->arg][op->data.reg.reg].available = av;
+    av->next = opvalue[pcode->op];
+    opvalue[pcode->op] = av;
+}
+
+static int isCSEop(PCode *pcode) {
+    PCodeArg *baseOp;
+    PCodeArg *op;
+    int i;
+
+    baseOp = &pcode->args[0];
+
+    switch (pcode->op) {
+        case PC_CMPI:
+        case PC_CMP:
+        case PC_CMPLI:
+        case PC_CMPL:
+        case PC_FCMPU:
+        case PC_FCMPO:
+            if (!moreaggressiveoptimization)
+                return 0;
+            break;
+        case PC_LI:
+        case PC_LIS:
+            if (!moreaggressiveoptimization)
+                return 0;
+            if (pcode->args[0].data.reg.reg < first_fe_temporary_register[RegClass_GPR] || pcode->args[0].data.reg.reg > last_temporary_register[RegClass_GPR])
+                return 0;
+            break;
+    }
+
+    if (PCODE_FLAG_SET_F(pcode) & (fIsVolatile | fSideEffects | fOverflow | fSetsCarry | fRecordBit))
+        return 0;
+
+    for (i = 0, op = &pcode->args[0]; i < pcode->argCount; i++, op++) {
+        if (op != baseOp &&
+            op->kind == baseOp->kind &&
+            op->arg == baseOp->arg &&
+            op->data.reg.reg == baseOp->data.reg.reg)
+            return 0;
+    }
+
+    return 1;
+}
+
+static int isCSEload(PCode *pcode) {
+    PCodeArg *op;
+    int i;
+    int count;
+
+    count = 0;
+    for (i = 0, op = &pcode->args[0]; i < pcode->argCount; i++, op++) {
+        if (op->kind == PCOp_REGISTER && (op->data.reg.effect & EffectWrite))
+            count++;
+    }
+
+    return count == 1;
+}
+
+static void registercopy(PCode *pcode) {
+    PCodeArg *op1;
+    PCodeArg *op2;
+
+    op1 = &pcode->args[0];
+    op2 = &pcode->args[1];
+    if (samevalue(op2, op1))
+        deletepcode(pcode);
+    else
+        copyregister(op2, op1);
+}
+
+static PCode *recentlystored(Alias *alias, PCodeArg *op) {
+    PCode *pc;
+    if ((pc = alias->valuepcode) && alias->valuenumber == regvalue[pc->args[0].arg][pc->args[0].data.reg.reg].number) {
+        *op = pc->args[0];
+        return pc;
+    } else {
+        return NULL;
+    }
+}
+
+static void simpleload(PCode *pcode) {
+    PCodeArg *origOp;
+    PCodeArg op;
+    PCode *rs;
+
+    origOp = &pcode->args[0];
+    if ((pcode->flags & fIsVolatile) || !isCSEload(pcode)) {
+        killregisters(pcode);
+        return;
+    }
+
+    if (findavailablevalue(pcode, &op)) {
+        if (!samevalue(origOp, &op)) {
+            insertpcodebefore(pcode, makecopyinstruction(&op, origOp));
+            copyregister(&op, origOp);
+        }
+        deletepcode(pcode);
+        removedcommonsubexpressions = 1;
+    } else if ((rs = recentlystored(pcode->alias, &op)) && can_reuse_stored_value(rs, pcode)) {
+        if (!samevalue(origOp, &op)) {
+            insertpcodebefore(pcode, makecopyinstruction(&op, origOp));
+            copyregister(&op, origOp);
+        }
+        deletepcode(pcode);
+        removedcommonsubexpressions = 1;
+    } else {
+        addavailablevalue(pcode);
+    }
+}
+
+static void simplestore(PCode *pcode) {
+    update_alias_value(pcode->alias, pcode);
+    killregisters(pcode);
+}
+
+static void pointerload(PCode *pcode) {
+    PCodeArg *op;
+    PCodeArg buf;
+
+    op = &pcode->args[0];
+
+    if ((pcode->flags & fIsVolatile) || !isCSEload(pcode)) {
+        killregisters(pcode);
+        return;
+    }
+
+    if (findavailablevalue(pcode, &buf)) {
+        if (!samevalue(op, &buf)) {
+            insertpcodebefore(pcode, makecopyinstruction(&buf, op));
+            copyregister(&buf, op);
+        }
+        deletepcode(pcode);
+        removedcommonsubexpressions = 1;
+    } else {
+        addavailablevalue(pcode);
+    }
+}
+
+static void pointerstore(PCode *pcode) {
+    update_alias_value(pcode->alias, NULL);
+    killregisters(pcode);
+}
+
+static void arithmeticop(PCode *pcode) {
+    PCodeArg *op;
+    PCodeArg buf;
+
+    op = &pcode->args[0];
+
+    if (findavailablevalue(pcode, &buf)) {
+        if (!samevalue(op, &buf)) {
+            insertpcodebefore(pcode, makecopyinstruction(&buf, op));
+            copyregister(&buf, op);
+        }
+        deletepcode(pcode);
+        removedcommonsubexpressions = 1;
+    } else {
+        addavailablevalue(pcode);
+    }
+}
+
+static void functioncall(PCode *pcode) {
+    killregisters(pcode);
+    if (coloring) {
+        update_all_alias_values();
+        killallCSEs();
+    } else {
+        update_alias_value(pcode->alias, NULL);
+    }
+}
+
+static void operatefrommemory(PCode *pcode) {
+    CError_FATAL(980);
+}
+
+static void operatetomemory(PCode *pcode) {
+    CError_FATAL(1011);
+}
+
+static void propagatecopiesto(PCode *pcode) {
+    PCodeArg *op;
+    int i;
+
+    for (i = 0, op = &pcode->args[0]; i < pcode->argCount; i++, op++) {
+        if (
+            op->kind == PCOp_REGISTER &&
+            (op->data.reg.effect & (EffectRead | EffectWrite | Effect8)) == EffectRead &&
+            op->data.reg.reg >= n_real_registers[op->arg] &&
+            regvalue[op->arg][op->data.reg.reg].x4 &&
+            regvalue[op->arg][op->data.reg.reg].x4 >= n_real_registers[op->arg] &&
+            regvalue[op->arg][op->data.reg.reg].number == regvalue[op->arg][regvalue[op->arg][op->data.reg.reg].x4].number
+            ) {
+            op->data.reg.reg = regvalue[op->arg][op->data.reg.reg].x4;
+        }
+    }
+}
+
+static void removecsesfrombasicblock(PCodeBlock *block) {
+    PCode *pcode;
+    PCode *next;
+
+    for (pcode = block->firstPCode; pcode; pcode = next) {
+        next = pcode->nextPCode;
+        propagatecopiesto(pcode);
+        if (pcode->flags & fIsMove) {
+            registercopy(pcode);
+        } else if ((pcode->flags & fIsCall) && (pcode->flags & (fLink | fSideEffects))) {
+            functioncall(pcode);
+        } else if (pcode->flags & fIsRead) {
+            if (pcode->flags & fIsPtrOp)
+                pointerload(pcode);
+            else
+                simpleload(pcode);
+        } else if (pcode->flags & fIsWrite) {
+            if (pcode->flags & fIsPtrOp)
+                pointerstore(pcode);
+            else
+                simplestore(pcode);
+        } else if (pcode->flags & fPCodeFlag20000) {
+            operatefrommemory(pcode);
+        } else if (pcode->flags & fPCodeFlag40000) {
+            operatetomemory(pcode);
+        } else if ((pcode->flags & fIsCSE) && isCSEop(pcode)) {
+            arithmeticop(pcode);
+        } else {
+            killregisters(pcode);
+        }
+    }
+
+    block->flags |= fVisited;
+}
+
+static void getvaluestate(State *state) {
+    state->stackedvalues = stackedvalues;
+    state->valueceiling = valueceiling;
+}
+
+static void setvaluestate(State *state) {
+    stackedvalues = state->stackedvalues;
+    valueceiling = state->valueceiling;
+}
+
+static void forkvaluestate(int number) {
+    stackedvalues = NULL;
+    valueceiling = number;
+}
+
+static void regressvaluestate(void) {
+    AvailableValue *av;
+    AvailableValue **ptr;
+    int i;
+    StackedValue *stacked;
+
+    for (i = 0; i < 428; i++) {
+        ptr = &opvalue[i];
+        while ((av = *ptr)) {
+            if (av->killedregister >= valueceiling)
+                *ptr = av->next;
+            else
+                ptr = &av->next;
+        }
+    }
+
+    for (stacked = stackedvalues; stacked; stacked = stacked->next)
+        unstackvalue(stacked);
+}
+
+static void removecsesfromextendedbasicblock(PCodeBlock *block) {
+    PCLink *succ;
+    int counter;
+    State state;
+
+    removecsesfrombasicblock(block);
+    while (block->successors &&
+        !block->successors->nextLink &&
+        block->successors->block->predecessors &&
+        !block->successors->block->predecessors->nextLink) {
+        block = block->successors->block;
+        removecsesfrombasicblock(block);
+    }
+
+    counter = 0;
+    for (succ = block->successors; succ; succ = succ->nextLink) {
+        if (!(succ->block->flags & fVisited) && succ->block->predecessors && !succ->block->predecessors->nextLink)
+            counter++;
+    }
+
+    if (counter) {
+        getvaluestate(&state);
+        forkvaluestate(nextvaluenumber);
+        for (succ = block->successors; succ; succ = succ->nextLink) {
+            if (!(succ->block->flags & fVisited) && succ->block->predecessors && !succ->block->predecessors->nextLink) {
+                removecsesfromextendedbasicblock(succ->block);
+                regressvaluestate();
+            }
+        }
+        setvaluestate(&state);
+    }
+}
+
+void removecommonsubexpressions(Object *proc, int flag) {
+    PCodeBlock *block;
+
+    moreaggressiveoptimization = flag;
+    removedcommonsubexpressions = 0;
+    gather_alias_info();
+    allocatecsedatastructures();
+
+    for (block = pcbasicblocks; block; block = block->nextBlock)
+        block->flags &= ~fVisited;
+
+    for (block = pcbasicblocks; block; block = block->nextBlock) {
+        if (!(block->flags & fVisited)) {
+            initializecsedatastructures();
+            removecsesfromextendedbasicblock(block);
+        }
+    }
+
+    freeoheap();
+}
+