From 094b96ca1df4a035b5f93c351f773306c0241f3f Mon Sep 17 00:00:00 2001 From: Ash Wolf Date: Thu, 26 Jan 2023 11:30:47 +0000 Subject: move lots of source files around to match their actual placement in the original tree --- .../PowerPC/GlobalOptimizer/ValueNumbering.c | 661 +++++++++++++++++++++ 1 file changed, 661 insertions(+) create mode 100644 compiler_and_linker/BackEnd/PowerPC/GlobalOptimizer/ValueNumbering.c (limited to 'compiler_and_linker/BackEnd/PowerPC/GlobalOptimizer/ValueNumbering.c') 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 = ®value[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 = ®value[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 = ®value[src->arg][src->data.reg.reg]; + destvalue = ®value[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(); +} + -- cgit v1.2.3