#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 & (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; 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 & (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; 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) { 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++; } } } 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 & (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 && (RegClass) 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: 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); }