diff options
Diffstat (limited to 'compiler_and_linker/unsorted/Alias.c')
| -rw-r--r-- | compiler_and_linker/unsorted/Alias.c | 747 |
1 files changed, 0 insertions, 747 deletions
diff --git a/compiler_and_linker/unsorted/Alias.c b/compiler_and_linker/unsorted/Alias.c deleted file mode 100644 index 8223bf4..0000000 --- a/compiler_and_linker/unsorted/Alias.c +++ /dev/null @@ -1,747 +0,0 @@ -#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) { - CError_FATAL(333); - 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; - } - - CError_ASSERT(478, object->otype == OT_OBJECT); - - if ((candidate_pcode->flags & (fIsRead | fIsWrite)) && (candidate_pcode->flags & fUpdatesPtr)) { - 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; - CError_ASSERT(495, 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 { - CError_FATAL(509); - } - - if ( - !(use_pcode->flags & (fIsRead | fIsWrite)) && - 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 & (fIsWrite | 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; - - CError_ASSERT(543, 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) { - for (op = scan->args, i = scan->argCount; i--; op++) { - if (op->kind == PCOp_REGISTER && - op->arg == RegClass_GPR && - (op->data.reg.effect & EffectWrite) && - op->data.reg.reg == reg) - return 1; - } - } - } 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) { - for (op = scan->args, i = scan->argCount; i--; op++) { - if (op->kind == PCOp_REGISTER && - op->arg == RegClass_GPR && - (op->data.reg.effect & EffectWrite) && - op->data.reg.reg == reg) - return 1; - } - } - } else { - return 1; - } - } - - for (scan = use_pcode->block->firstPCode; scan; scan = scan->nextPCode) { - if (scan == use_pcode) - break; - for (op = scan->args, i = scan->argCount; i--; op++) { - if (op->kind == PCOp_REGISTER && - op->arg == RegClass_GPR && - (op->data.reg.effect & EffectWrite) && - op->data.reg.reg == reg) - return 1; - } - } - } - - CError_ASSERT(598, 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 & (fIsRead | fIsWrite)) - 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 & (fIsRead | fIsWrite)) && (candidate_pcode->flags & fUpdatesPtr)) - ) - 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 & (fIsRead | fIsWrite)) && (use_pcode->flags & fUpdatesPtr)) - ) { - 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%" PRId32, - 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 & (fIsRead | fIsWrite | 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 &= ~fIsPtrOp; - } else { - pcode->flags |= fIsPtrOp; - } - - 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 & (fIsWrite | 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 |= fIsPtrOp; - 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 & fIsCall) && !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 & (fIsRead | fIsWrite | fIsCall | 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) >> 5)); - 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: - CError_FATAL(1054); - 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) { - CError_ASSERT(1152, member->parent->type == AliasType2); - killmemory(member->parent, NULL); - } - for (member = alias->parents; member; member = member->nextParent) { - CError_ASSERT(1157, member->child->type == AliasType1); - killmemory(member->child, NULL); - for (member2 = member->child->children; member2; member2 = member2->nextChild) { - if (member2->parent != alias) { - CError_ASSERT(1163, 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); -} - |