From 25bab8b1fb2fc851ea3f1f630b3de65ca6afdc22 Mon Sep 17 00:00:00 2001 From: Ash Wolf Date: Wed, 14 Dec 2022 00:16:59 +0000 Subject: haha it's been a while since i last committed, hasn't it --- compiler_and_linker/unsorted/Alias.c | 766 +++++++++++++++++++++++++++++++++++ 1 file changed, 766 insertions(+) (limited to 'compiler_and_linker/unsorted/Alias.c') diff --git a/compiler_and_linker/unsorted/Alias.c b/compiler_and_linker/unsorted/Alias.c index e69de29..4c0f064 100644 --- a/compiler_and_linker/unsorted/Alias.c +++ b/compiler_and_linker/unsorted/Alias.c @@ -0,0 +1,766 @@ +#include "compiler/Alias.h" +#include "compiler/CClass.h" +#include "compiler/CError.h" +#include "compiler/CParser.h" +#include "compiler/CMachine.h" +#include "compiler/CodeGen.h" +#include "compiler/CopyPropagation.h" +#include "compiler/PCode.h" +#include "compiler/PCodeInfo.h" +#include "compiler/RegisterInfo.h" +#include "compiler/UseDefChains.h" +#include "compiler/ValueNumbering.h" +#include "compiler/BitVectors.h" +#include "compiler/CompilerTools.h" +#include "compiler/objects.h" +#include "compiler/types.h" + +static Alias *aliases; +static int n_aliases; +static int n_gathered_aliases; +static Alias *alias_hash[997]; +Alias *worst_case; +Object worst_case_obj; + +static TypePointer worst_case_memory_type = { + TYPEARRAY, + 0xFFFFFF, + TYPE(&stchar) +}; + +static Boolean is_safe_const(Object *obj) { + Type *type; + + type = obj->type; + while (IS_TYPE_ARRAY(type)) + type = TPTR_TARGET(type); + + if (TYPE_FITS_IN_REGISTER(type) || IS_TYPE_VECTOR(type) || IS_TYPE_FLOAT(type) || IS_TYPE_STRUCT(type)) + return is_const_object(obj); + + if (IS_TYPE_CLASS(type)) + return is_const_object(obj) && CClass_IsPODClass(TYPE_CLASS(type)); + + return 0; +} + +void initialize_aliases(void) { + int i; + + memclrw(&worst_case_obj, sizeof(Object)); + worst_case_obj.otype = OT_OBJECT; + worst_case_obj.type = TYPE(&worst_case_memory_type); + worst_case_obj.datatype = DDATA; + worst_case_obj.name = GetHashNameNodeExport("@worst_case@"); + + aliases = NULL; + n_aliases = 0; + n_gathered_aliases = 0; + for (i = 0; i < 997; i++) + alias_hash[i] = NULL; + + worst_case = make_alias_set(); + add_alias_member(worst_case, make_alias(&worst_case_obj, 0, 0)); +} + +static UInt32 hash_alias(Object *object, SInt32 offset, SInt32 size) { + return (UInt32) (object->name->hashval * offset * size) % 997; +} + +static Alias *create_alias(AliasType type, Object *object, SInt32 offset, SInt32 size, Boolean addToHash) { + Alias *alias; + UInt32 hash; + + alias = lalloc(sizeof(Alias)); + memclrw(alias, sizeof(Alias)); + alias->type = type; + alias->index = n_aliases++; + alias->next = aliases; + aliases = alias; + alias->object = object; + alias->offset = offset; + alias->size = size; + + if (addToHash) { + hash = hash_alias(object, offset, size); + alias->hashNext = alias_hash[hash]; + alias_hash[hash] = alias; + } + + return alias; +} + +static Alias *lookup_alias(Object *object, SInt32 offset, SInt32 size) { + Alias *scan; + + for (scan = alias_hash[hash_alias(object, offset, size)]; scan; scan = scan->hashNext) { + if (scan->object == object && scan->offset == offset && scan->size == size) + return scan; + } + + return NULL; +} + +Alias *make_alias(Object *object, SInt32 offset, SInt32 size) { + Alias *alias; + Alias *alias2; + + if (!offset && !size) + size = object->type->size; + + alias = lookup_alias(object, offset, size); + if (!alias) { + if (offset > 0 || size != object->type->size) { + alias2 = make_alias(object, 0, object->type->size); + alias = create_alias(AliasType1, object, offset, size, 1); + add_alias_member(alias2, alias); + } else { + alias = create_alias(AliasType0, object, offset, size, 1); + } + + switch (object->datatype) { + case DLOCAL: + case DNONLAZYPTR: + break; + default: + if (!is_safe_const(object)) + add_alias_member(worst_case, make_alias(object, 0, 0)); + } + } + + if (offset > object->type->size) + return NULL; + else + return alias; +} + +Alias *make_alias_set(void) { + return create_alias(AliasType2, NULL, 0, 0, 0); +} + +void add_alias_member(Alias *parent, Alias *child) { + AliasMember *member; + + if (child->type == AliasType2) { + for (member = child->parents; member; member = member->nextParent) + add_alias_member(parent, member->child); + } else { + if (parent == worst_case && child->type == AliasType1) + child = make_alias(child->object, 0, 0); + + for (member = parent->parents; member; member = member->nextParent) { + if (member->child == child) + return; + } + + member = lalloc(sizeof(AliasMember)); + member->parent = parent; + member->child = child; + member->nextParent = parent->parents; + parent->parents = member; + member->nextChild = child->children; + child->children = member; + } +} + +Alias *make_alias_set_from_IR(void) { +#line 333 + CError_FATAL(); + return NULL; +} + +static Boolean aliases_overlap(Alias *a, Alias *b) { + return ( + a->offset == b->offset || + (a->offset > b->offset && a->offset < (b->offset + b->size)) || + (b->offset > a->offset && b->offset < (a->offset + a->size)) + ); +} + +static int is_address_load(PCode *pcode) { + Object *obj; + + switch (pcode->op) { + case PC_LWZ: + if (pcode->args[2].kind == PCOp_MEMORY && pcode->args[2].data.mem.obj->datatype == DNONLAZYPTR) + return 1; + break; + case PC_LBZU: + case PC_LBZUX: + case PC_LHZU: + case PC_LHZUX: + case PC_LHAU: + case PC_LHAUX: + case PC_LWZU: + case PC_LWZUX: + case PC_STBU: + case PC_STBUX: + case PC_STHU: + case PC_STHUX: + case PC_STWU: + case PC_STWUX: + return 1; + case PC_ADDI: + case PC_ADDIS: + if (pcode->args[0].data.reg.reg < n_real_registers[RegClass_GPR]) { + if (pcode->args[2].kind == PCOp_MEMORY) { + obj = pcode->args[2].data.mem.obj; + if (obj->datatype == DLOCAL && !is_safe_const(obj)) + add_alias_member(worst_case, make_alias(obj, 0, 0)); + return 0; + } + } else { + return 1; + } + break; + case PC_ADD: + return 1; + } + + return 0; +} + +static int addresspropagatestouse(int candidateID, int useID) { + PCode *candidate_pcode; // r30 + PCode *use_pcode; // r29 + int reg; // r28 + short reg2; + Object *object; // r27 + SInt32 offset; // r26 + Alias *alias; // r25 + Boolean flag24; // r24 + SInt32 size; // r23 + Alias *aliasSet; // r22 + int i; + PCode *scan; + PCodeArg *op; + + candidate_pcode = Candidates[candidateID].pcode; + use_pcode = Uses[useID].pcode; + flag24 = 0; + size = 1; + reg = candidate_pcode->args[0].data.reg.reg; + + if (candidate_pcode->alias && (candidate_pcode->alias->type == AliasType0 || candidate_pcode->alias->type == AliasType1)) { + object = candidate_pcode->alias->object; + offset = candidate_pcode->alias->offset; + if (offset == 0 && candidate_pcode->alias->size == object->type->size) + flag24 = 1; + } else if (candidate_pcode->args[2].kind == PCOp_MEMORY) { + object = candidate_pcode->args[2].data.mem.obj; + if (candidate_pcode->op == PC_ADDIS) + offset = candidate_pcode->args[2].data.mem.offset << 16; + else + offset = candidate_pcode->args[2].data.mem.offset; + } else { + return 0; + } + +#line 478 + CError_ASSERT(object->otype == OT_OBJECT); + + if ((candidate_pcode->flags & (fPCodeFlag2 | fPCodeFlag4)) && (candidate_pcode->flags & fPCodeFlag2000000)) { + reg = candidate_pcode->args[1].data.reg.reg; + offset = 0; + flag24 = 1; + } else if (candidate_pcode->op == PC_LWZ) { + if (object->datatype != DNONLAZYPTR) + return 0; + + object = object->u.var.realObj; +#line 495 + CError_ASSERT(object->otype == OT_OBJECT); + offset = 0; + } else if (candidate_pcode->op == PC_ADDI) { + if (!candidate_pcode->alias && object) + candidate_pcode->alias = make_alias(object, offset, 1); + } else if (candidate_pcode->op == PC_ADDIS) { + if (!candidate_pcode->alias && object) + candidate_pcode->alias = make_alias(object, offset, 1); + } else if (candidate_pcode->op == PC_ADD) { + offset = 0; + flag24 = 1; + } else { +#line 509 + CError_FATAL(); + } + + if ( + !(use_pcode->flags & (fPCodeFlag2 | fPCodeFlag4)) && + use_pcode->op != PC_ADDI && + use_pcode->op != PC_ADD && + use_pcode->op != PC_ADDIS + ) { + if (object->datatype == DLOCAL && !is_safe_const(object)) + add_alias_member(worst_case, make_alias(object, 0, 0)); + return 1; + } + + if ( + (use_pcode->flags & (fPCodeFlag4 | fPCodeFlag40000)) && + use_pcode->args[0].kind == PCOp_REGISTER && + use_pcode->args[0].arg == RegClass_GPR && + use_pcode->args[0].data.reg.reg == reg && + object->datatype == DLOCAL && + !is_safe_const(object) + ) + add_alias_member(worst_case, make_alias(object, 0, 0)); + + if (use_pcode->argCount < 3) + return 1; + +#line 543 + CError_ASSERT(use_pcode->args[1].kind == PCOp_REGISTER); + + if (candidate_pcode->block == use_pcode->block && precedes(candidate_pcode, use_pcode)) { + for (scan = candidate_pcode->nextPCode; scan && scan != use_pcode; scan = scan->nextPCode) { + op = scan->args; + i = scan->argCount; + while (i--) { + if (op->kind == PCOp_REGISTER && + op->arg == RegClass_GPR && + (op->data.reg.effect & EffectWrite) && + op->data.reg.reg == reg) + return 1; + op++; + } + } + } else { + if (!bitvectorgetbit(candidateID, propinfo[use_pcode->block->blockIndex].vec8)) { + if (bitvectorgetbit(candidate_pcode->defID, usedefinfo[use_pcode->block->blockIndex].defvec8)) { + for (scan = use_pcode->block->firstPCode; scan && scan != use_pcode; scan = scan->nextPCode) { + op = scan->args; + i = scan->argCount; + while (i--) { + if (op->kind == PCOp_REGISTER && + op->arg == RegClass_GPR && + (op->data.reg.effect & EffectWrite) && + op->data.reg.reg == reg) + return 1; + op++; + } + } + } else { + return 1; + } + } + + for (scan = use_pcode->block->firstPCode; scan; scan = scan->nextPCode) { + if (scan == use_pcode) + break; + op = scan->args; + i = scan->argCount; + while (i--) { + if (op->kind == PCOp_REGISTER && + op->arg == RegClass_GPR && + (op->data.reg.effect & EffectWrite) && + op->data.reg.reg == reg) + return 1; + op++; + } + } + } + +#line 598 + CError_ASSERT(object != NULL); + + if (use_pcode->op == PC_ADDI || use_pcode->op == PC_ADD || use_pcode->op == PC_ADDIS) { + if (use_pcode->args[0].data.reg.reg < n_real_registers[RegClass_GPR] && !is_safe_const(object)) + add_alias_member(worst_case, make_alias(object, 0, 0)); + } + + if (use_pcode->flags & (fPCodeFlag2 | fPCodeFlag4)) + size = nbytes_loaded_or_stored_by(use_pcode); + + if (use_pcode->args[2].kind == PCOp_REGISTER) { + if (use_pcode->args[1].data.reg.reg == 0) { + if (use_pcode->args[2].data.reg.reg == reg) + alias = make_alias(object, offset, size); + } else { + if (use_pcode->args[1].data.reg.reg == reg) + reg2 = use_pcode->args[2].data.reg.reg; + else if (use_pcode->args[2].data.reg.reg == reg) + reg2 = use_pcode->args[1].data.reg.reg; + else + return 1; + + for (scan = use_pcode->prevPCode; scan; scan = scan->prevPCode) { + if (scan->op == PC_LI && scan->args[0].data.reg.reg == reg2) + break; + + for (i = 0; i < scan->argCount; i++) { + if (scan->args[i].kind == PCOp_REGISTER && + scan->args[i].arg == RegClass_GPR && + scan->args[i].data.reg.reg == reg2 && + (scan->args[i].data.reg.effect & EffectWrite)) { + scan = NULL; + break; + } + } + + if (!scan) + break; + } + + if (scan) { + offset += scan->args[1].data.mem.offset; + alias = make_alias(object, offset, size); + } else { + alias = make_alias(object, 0, 0); + } + } + } else { + if (use_pcode->args[1].kind != PCOp_REGISTER || + use_pcode->args[1].arg != RegClass_GPR || + use_pcode->args[1].data.reg.reg != reg) + return 1; + + if (use_pcode->args[1].data.reg.effect & EffectWrite) { + alias = make_alias(object, 0, 0); + } else if (use_pcode->args[2].kind == PCOp_IMMEDIATE) { + if (use_pcode->op == PC_ADDIS) { + offset += use_pcode->args[2].data.imm.value << 16; + alias = make_alias(object, offset, 1); + } else { + offset += use_pcode->args[2].data.imm.value; + alias = make_alias(object, offset, size); + } + } else { + return 1; + } + } + + if (flag24) + alias = make_alias(object, 0, 0); + + if (!alias) + return 1; + + if (!use_pcode->alias) { + if ( + use_pcode->op == PC_ADDI || + use_pcode->op == PC_ADD || + use_pcode->op == PC_ADDIS || + ((candidate_pcode->flags & (fPCodeFlag2 | fPCodeFlag4)) && (candidate_pcode->flags & fPCodeFlag2000000)) + ) + recursive_propagation = 1; + } + + if (use_pcode->alias) { + if (use_pcode->alias == worst_case) { + add_alias_member(worst_case, make_alias(object, 0, 0)); + } else if (use_pcode->alias == alias) { + return 1; + } else if (use_pcode->alias->type == AliasType0 || use_pcode->alias->type == AliasType1) { + if (object == use_pcode->alias->object) { + use_pcode->alias = make_alias(object, 0, 0); + } else { + aliasSet = make_alias_set(); + if ( + use_pcode->op == PC_ADDI || + use_pcode->op == PC_ADD || + use_pcode->op == PC_ADDIS || + ((use_pcode->flags & (fPCodeFlag2 | fPCodeFlag4)) && (use_pcode->flags & fPCodeFlag2000000)) + ) { + if (alias->type == AliasType2) + add_alias_member(worst_case, alias); + else + add_alias_member(worst_case, make_alias(use_pcode->alias->object, 0, 0)); + } + add_alias_member(aliasSet, use_pcode->alias); + add_alias_member(aliasSet, alias); + use_pcode->alias = aliasSet; + } + } else { + add_alias_member(use_pcode->alias, alias); + } + } else { + use_pcode->alias = alias; + } + + propagated_instructions = 1; + return 1; +} + +static void finishpropagatealiases(int id) { + propagated_instructions = 1; +} + +static Propagation alias_prop = { + &is_address_load, + &addresspropagatestouse, + &finishpropagatealiases, + "ALIAS", + "ALIASES", + "A%ld", + 1 +}; + +static void propagatealiasinfo(Object *proc) { + propagateinstructions(proc, &alias_prop, (copts.optimizationlevel >= 4) ? 4 : 1, 1); +} + +void gather_alias_info(void) { + UInt32 *myvec; // r31 + Alias *alias; // r22 + AliasMember *member; + AliasMember *member2; + PCodeBlock *block; // r21 + PCode *pcode; // r20 + PCodeArg *op; // r19 + RegUseOrDef *list; // r18 + int i; // r17 + Alias *alias_choice; // r16 + int aliases_idx; // r15 (helper in r23) + PCode *defpcode; // r14 + Alias *alias_array[3]; + UseOrDef *def; + int defID; + + if (coloring) { + propagatealiasinfo(gFunction); + myvec = oalloc(4 * ((number_of_Defs + 31) >> 5)); + + for (block = pcbasicblocks; block; block = block->nextBlock) { + bitvectorcopy(myvec, usedefinfo[block->blockIndex].defvec8, number_of_Defs); + + for (pcode = block->firstPCode; pcode; pcode = pcode->nextPCode) { + if (pcode->flags & (fPCodeFlag2 | fPCodeFlag4 | fPCodeFlag20000 | fPCodeFlag40000)) { + if (!pcode->alias) { + pcode->alias = worst_case; + } else { + if ((pcode->alias->type == AliasType0 || pcode->alias->type == AliasType1) && + pcode->alias->size == nbytes_loaded_or_stored_by(pcode)) { + pcode->flags &= ~fPCodeFlag20; + } else { + pcode->flags |= fPCodeFlag20; + } + + if (pcode->alias != worst_case) { + aliases_idx = 0; + alias_choice = NULL; + op = pcode->args; + for (i = 0; i < pcode->argCount; i++, op++) { + if ( + (!(pcode->flags & (fPCodeFlag4 | fPCodeFlag40000)) || op != pcode->args) && + op->kind == PCOp_REGISTER && + op->arg == RegClass_GPR && + (op->data.reg.effect & EffectRead) + ) { + alias_array[aliases_idx] = NULL; + if (aliases_idx >= 2) { + alias_choice = worst_case; + break; + } + alias_array[aliases_idx] = pcode->alias; + + for (list = reg_Defs[RegClass_GPR][op->data.reg.reg]; list; list = list->next) { + if (bitvectorgetbit(list->id, myvec)) { + defpcode = Defs[list->id].pcode; + if (!defpcode->alias || !is_address_load(defpcode) || defpcode->alias == worst_case) { + alias_array[aliases_idx] = worst_case; + break; + } + } + } + + aliases_idx++; + } + } + + if (!alias_choice) { + if (aliases_idx > 0) { + alias_choice = alias_array[0]; + if (aliases_idx == 2) { + if (alias_array[0] != worst_case) { + if (alias_array[1] != worst_case) + alias_choice = worst_case; + } else if (alias_array[1] != worst_case) { + alias_choice = alias_array[1]; + } + } + } + + if (alias_choice == worst_case) { + pcode->flags |= fPCodeFlag20; + if (pcode->alias->type == AliasType2) + add_alias_member(worst_case, pcode->alias); + else + add_alias_member(worst_case, make_alias(pcode->alias->object, 0, 0)); + } + + if (alias_choice) + pcode->alias = alias_choice; + } + } + } + } else { + if ((pcode->flags & fPCodeFlag8) && !pcode->alias) + pcode->alias = worst_case; + } + + for (def = &Defs[defID = pcode->defID]; defID < number_of_Defs && def->pcode == pcode; defID++, def++) { + if (def->v.kind == PCOp_REGISTER && def->v.arg == RegClass_GPR) { + for (list = reg_Defs[RegClass_GPR][def->v.u.reg]; list; list = list->next) + bitvectorclearbit(list->id, myvec); + } + bitvectorsetbit(defID, myvec); + } + } + } + + freeoheap(); + } else { + for (block = pcbasicblocks; block; block = block->nextBlock) { + for (pcode = block->firstPCode; pcode; pcode = pcode->nextPCode) { + if ((pcode->flags & (fPCodeFlag2 | fPCodeFlag4 | fPCodeFlag8 | fPCodeFlag20000 | fPCodeFlag40000)) && !pcode->alias) + pcode->alias = worst_case; + } + } + } + + if (n_gathered_aliases != n_aliases) { + for (alias = aliases; alias; alias = alias->next) { + if (alias->type == AliasType2) { + alias->vec24 = lalloc(4 * ((n_aliases + 31) >> 35)); + bitvectorinitialize(alias->vec24, n_aliases, 0); + for (member = alias->parents; member; member = member->nextParent) { + bitvectorsetbit(member->child->index, alias->vec24); + for (member2 = member->child->parents; member2; member2 = member2->nextParent) + bitvectorsetbit(member2->child->index, alias->vec24); + } + } + } + n_gathered_aliases = n_aliases; + } +} + +static Boolean may_alias_alias(Alias *a, Alias *b) { + switch ((a->type * 3) + b->type) { + case (AliasType0 * 3) + AliasType0: + return a == b; + case (AliasType0 * 3) + AliasType1: + case (AliasType1 * 3) + AliasType0: + return a->object == b->object; + case (AliasType1 * 3) + AliasType1: + return (a->object == b->object) && aliases_overlap(a, b); + case (AliasType0 * 3) + AliasType2: + case (AliasType1 * 3) + AliasType2: + return bitvectorgetbit(a->index, b->vec24) != 0; + case (AliasType2 * 3) + AliasType0: + case (AliasType2 * 3) + AliasType1: + return bitvectorgetbit(b->index, a->vec24) != 0; + case (AliasType2 * 3) + AliasType2: + return (a == b) || !bitvectorintersectionisempty(a->vec24, b->vec24, n_aliases); + default: +#line 1054 + CError_FATAL(); + return 1; + } +} + +Boolean may_alias(PCode *a, PCode *b) { + return may_alias_alias(a->alias, b->alias); +} + +Boolean uniquely_aliases(PCode *a, PCode *b) { + if (may_alias_alias(a->alias, b->alias)) { + if ( + a->alias->type != AliasType2 && + b->alias->type != AliasType2 && + a->alias && + b->alias && + a->alias->size == nbytes_loaded_or_stored_by(a) && + b->alias->size == nbytes_loaded_or_stored_by(b) + ) + return 1; + } + + return 0; +} + +Boolean may_alias_worst_case(PCode *pcode) { + return may_alias_alias(pcode->alias, worst_case); +} + +Boolean may_alias_object(PCode *pcode, Object *object) { + return may_alias_alias(pcode->alias, make_alias(object, 0, 0)); +} + +void initialize_alias_values(void) { + Alias *alias; + + for (alias = aliases; alias; alias = alias->next) { + alias->valuenumber = nextvaluenumber++; + alias->valuepcode = NULL; + } +} + +void update_alias_value(Alias *alias, PCode *pcode) { + AliasMember *member; + AliasMember *member2; + AliasMember *member3; + + switch (alias->type) { + case AliasType0: + killmemory(alias, pcode); + for (member = alias->children; member; member = member->nextChild) { +#line 1152 + CError_ASSERT(member->parent->type == AliasType2); + killmemory(member->parent, NULL); + } + for (member = alias->parents; member; member = member->nextParent) { +#line 1157 + CError_ASSERT(member->child->type == AliasType1); + killmemory(member->child, NULL); + for (member2 = member->child->children; member2; member2 = member2->nextChild) { + if (member2->parent != alias) { +#line 1163 + CError_ASSERT(member2->parent->type == AliasType2); + killmemory(member2->parent, NULL); + } + } + } + break; + + case AliasType1: + killmemory(alias, pcode); + for (member = alias->children; member; member = member->nextChild) { + killmemory(member->parent, NULL); + if (member->parent->type == AliasType0) { + for (member2 = member->parent->parents; member2; member2 = member2->nextParent) { + if (member2->child != alias && aliases_overlap(alias, member2->child)) { + killmemory(member2->child, NULL); + } + } + } + } + break; + + case AliasType2: + killmemory(alias, NULL); + for (member = alias->parents; member; member = member->nextParent) { + killmemory(member->child, NULL); + for (member2 = member->child->children; member2; member2 = member2->nextChild) { + if (member2->parent != alias) + killmemory(member2->parent, NULL); + } + for (member3 = member->child->parents; member3; member3 = member3->nextParent) { + killmemory(member3->child, NULL); + for (member2 = member3->child->children; member2; member2 = member2->nextChild) { + if (member2->parent != member->child) + killmemory(member2->parent, NULL); + } + } + } + break; + } +} + +void update_all_alias_values(void) { + Alias *alias; + + for (alias = aliases; alias; alias = alias->next) + killmemory(alias, NULL); +} + -- cgit v1.2.3