diff options
Diffstat (limited to 'compiler_and_linker/FrontEnd/Optimizer/IroPropagate.c')
| -rw-r--r-- | compiler_and_linker/FrontEnd/Optimizer/IroPropagate.c | 593 |
1 files changed, 593 insertions, 0 deletions
diff --git a/compiler_and_linker/FrontEnd/Optimizer/IroPropagate.c b/compiler_and_linker/FrontEnd/Optimizer/IroPropagate.c new file mode 100644 index 0000000..c5ad708 --- /dev/null +++ b/compiler_and_linker/FrontEnd/Optimizer/IroPropagate.c @@ -0,0 +1,593 @@ +#include "IroPropagate.h" +#include "IroCSE.h" +#include "IroDump.h" +#include "IroEval.h" +#include "IroFlowgraph.h" +#include "IroLinearForm.h" +#include "IROUseDef.h" +#include "IroUtil.h" +#include "IroVars.h" +#include "compiler/objects.h" +#include "compiler/CExpr.h" +#include "compiler/CompilerTools.h" +#include "compiler/CParser.h" +#include "compiler/InlineAsm.h" +#include "compiler/InlineAsmPPC.h" + +IROAssign *IRO_FirstAssign; +IROAssign *IRO_LastAssign; +SInt32 IRO_NumAssign; + +static Boolean VarIsUsedInOtherFNodes(VarRecord *var, IRONode *node) { + if (var->defs && var->uses) { + IROUse *use; + IRODef *def = NULL; + for (use = var->uses; use; use = use->varnext) { + if (!def && use->node == node && use->linear && !(use->linear->flags & IROLF_Assigned)) { + for (def = var->defs; def; def = def->varnext) { + if (Bv_IsBitSet(def->index, use->x18)) + break; + } + } + } + + if (def) { + for (use = var->uses; use; use = use->varnext) { + if (use->node != node && use->linear && !(use->linear->flags & IROLF_Assigned)) { + if (Bv_IsBitSet(def->index, use->x18)) + return 1; + } + } + } + } else { + IROLinear *linear; + IRONode *scan; + for (scan = IRO_FirstNode; scan; scan = scan->nextnode) { + if (scan != node) { + linear = scan->first; + while (1) { + if (!linear) + break; + + if (IRO_IsVariable(linear) && !(linear->flags & IROLF_Assigned)) { + if (IRO_FindVar(linear->u.diadic.left->u.node->data.objref, 0, 1) == var) + return 1; + } + + if (linear == scan->last) + break; + linear = linear->next; + } + } + } + IRO_CheckForUserBreak(); + } + + return 0; +} + +static void GetExprUses(IROLinear *linear, Boolean isFirst) { + if (isFirst && IS_LINEAR_ENODE(linear, EOBJREF)) { + Object *obj = linear->u.node->data.objref; + if ((linear->flags & IROLF_Ind) && (!(linear->flags & IROLF_Assigned) || (linear->flags & IROLF_Used))) { + VarRecord *var = IRO_FindVar(obj, 0, 1); + if (var) + Bv_SetBit(var->index, IRO_VarKills); + } + } +} + +static void GetExprKills(IROLinear *linear, Boolean isFirst) { + if (isFirst) + IRO_GetKills(linear); +} + +static void CheckUnorderedRegionForDefs(IROLinear *linear, BitVector *a, BitVector *b, Boolean *flag) { + Bv_Clear(a); + Bv_Clear(IRO_VarKills); + IRO_WalkTree(linear, GetExprKills); + Bv_Or(IRO_VarKills, a); + if (Bv_BitsInCommon(a, b)) + *flag = 1; +} + +static void CheckUnorderedRegionsForDefs(IROLinear *linear1, IROLinear *linear2, BitVector *a, BitVector *b, Boolean *flag) { + int i; + + switch (linear1->type) { + case IROLinearOp2Arg: + if (linear1->nodetype == ELAND) break; + if (linear1->nodetype == ELOR) break; + if (linear1->nodetype == ECOMMA) break; + if (linear1->u.diadic.left != linear2) + CheckUnorderedRegionForDefs(linear1->u.diadic.left, a, b, flag); + if (linear1->u.diadic.right != linear2) + CheckUnorderedRegionForDefs(linear1->u.diadic.right, a, b, flag); + break; + case IROLinearFunccall: + if (linear1->u.funccall.linear8 != linear2) + CheckUnorderedRegionForDefs(linear1->u.funccall.linear8, a, b, flag); + for (i = 0; !*flag && i < linear1->u.funccall.argCount; i++) { + if (linear1->u.funccall.args[i] != linear2) + CheckUnorderedRegionForDefs(linear1->u.funccall.args[i], a, b, flag); + } + break; + } +} + +static Boolean PropagationHasDefsInUnorderedRegions(IROLinear *a, IROLinear *b) { + Boolean flag; + IROLinear *father; + BitVector *bv1; + BitVector *bv2; + VarRecord *var; + + flag = 0; + if ((father = IRO_LocateFather(a))) { + Bv_AllocVector(&bv1, IRO_NumVars + 1); + Bv_AllocVector(&bv2, IRO_NumVars + 1); + Bv_AllocVector(&IRO_VarKills, IRO_NumVars + 1); + IRO_WalkTree(b, GetExprUses); + Bv_Or(IRO_VarKills, bv2); + var = IRO_FindVar(a->u.diadic.left->u.node->data.objref, 0, 1); + Bv_SetBit(var->index, bv2); + while (father && !flag) { + CheckUnorderedRegionsForDefs(father, a, bv1, bv2, &flag); + a = father; + father = IRO_LocateFather(father); + } + } + + return flag; +} + +int IRO_IsRegable(Object *obj) { + if (obj->datatype == DLOCAL && obj->u.var.info) + return obj->u.var.info->noregister == 0; + return 0; +} + +static Boolean IsPropagatable(IROLinear *linear) { + Object *obj; + Object *obj2; + + if (IS_LINEAR_DIADIC(linear, EASS) && (obj = IRO_IsVariable(linear->u.diadic.left)) && obj->type == linear->rtype && !is_volatile_object(obj)) { + if (linear->u.diadic.left->flags & IROLF_BitfieldIndirect) { + if (!IRO_IsConstant(linear->u.diadic.right)) + return 0; + else + return 1; + } + + if (IRO_IsConstant(linear->u.diadic.right)) + return 1; + + if ((obj2 = IRO_IsVariable(linear->u.diadic.right)) && !is_volatile_object(obj2) && IRO_TypesEqual(obj->type, linear->rtype)) { + if (!Inline_IsObjectData(linear->u.diadic.right->u.monadic->u.node->data.objref)) { + if (IRO_IsRegable(obj) && !IRO_IsRegable(obj2)) + return 0; + return 1; + } + } + } + + return 0; +} + +static Boolean IsIntGenKillCandidate(IROLinear *linear) { + if (linear->type == IROLinearFunccall) + return 1; + + if (IRO_IsAssignOp[linear->nodetype] && (linear->type == IROLinearOp1Arg || linear->type == IROLinearOp2Arg)) + return 1; + + if (linear->type == IROLinearAsm) + return 1; + + return 0; +} + +static Boolean IsPropagatableExpr(IROLinear *linear, IROList *list) { + Object *obj; + if (IS_LINEAR_DIADIC(linear, EASS) && !(linear->flags & IROLF_Reffed)) { + if ((obj = IRO_IsVariable(linear->u.diadic.left)) && !is_volatile_object(obj) && !(linear->u.diadic.left->flags & IROLF_BitfieldIndirect)) { + if (!IRO_IsRegable(obj)) + return 0; + if (IS_LINEAR_ENODE(linear->u.diadic.right, ESTRINGCONST)) + return 0; + + IRO_FindDepends(linear->u.diadic.right); + if (!IRO_NotSubable) + return 1; + } + } + + return 0; +} + +static void ClearAvailibilityOnNode(IRONode *node, UInt32 bit) { + IRONode *scan; + + for (scan = node->nextnode; scan; scan = scan->nextnode) + Bv_ClearBit(bit, scan->x16); +} + +Boolean IRO_CopyAndConstantPropagation(void) { + IROAssign *ass2; + IROAssign *ass; + IROLinear *linear; + IRONode *node; + VarRecord *var; + BitVector *bv; + Boolean flag; + Boolean result; + + IRO_FirstAssign = NULL; + IRO_NumAssign = 0; + result = 0; + + for (node = IRO_FirstNode; node; node = node->nextnode) { + linear = node->first; + while (1) { + if (!linear) + break; + + if (IsPropagatable(linear) && (var = IRO_FindAssigned(linear))) { + IROAssign *newass; + IRO_Dump("Found propagatable assignment at: %d\n", linear->index); + newass = oalloc(sizeof(IROAssign)); + newass->linear = linear; + newass->next = NULL; + newass->index = ++IRO_NumAssign; + newass->varIndex = var->index; + newass->linear2 = linear->u.diadic.right; + newass->var = NULL; + newass->varObj = IRO_IsVariable(linear->u.diadic.right); + newass->node = node; + if (newass->varObj) + newass->var = IRO_FindVar(newass->varObj, 0, 1); + if (!IRO_FirstAssign) + IRO_FirstAssign = newass; + else + IRO_LastAssign->next = newass; + IRO_LastAssign = newass; + } + + if (linear == node->last) + break; + linear = linear->next; + } + } + + IRO_CheckForUserBreak(); + + node = IRO_FirstNode; + ass = IRO_FirstAssign; + Bv_AllocVector(&IRO_VarKills, IRO_NumVars + 1); + while (node) { + Bv_AllocVector(&node->x16, IRO_NumAssign); + if (node != IRO_FirstNode) + Bv_Set(node->x16); + Bv_AllocVector(&node->x22, IRO_NumAssign); + Bv_AllocVector(&node->x1E, IRO_NumAssign); + Bv_AllocVector(&node->x2A, IRO_NumAssign); + node->x1A = NULL; + + linear = node->first; + while (1) { + if (!linear) + break; + + if (IsIntGenKillCandidate(linear)) { + //IROAssign *ass2; + Bv_Clear(IRO_VarKills); + IRO_GetKills(linear); + + for (ass2 = IRO_FirstAssign; ass2; ass2 = ass2->next) { + if (Bv_IsBitSet(ass2->varIndex, IRO_VarKills)) { + Bv_SetBit(ass2->index, node->x22); + Bv_ClearBit(ass2->index, node->x1E); + } + if (ass2->var && Bv_IsBitSet(ass2->var->index, IRO_VarKills)) { + Bv_SetBit(ass2->index, node->x22); + Bv_ClearBit(ass2->index, node->x1E); + } + } + } + + while (ass && ass->linear == linear) { + Bv_SetBit(ass->index, node->x1E); + ass = ass->next; + } + + if (linear == node->last) + break; + linear = linear->next; + } + + Bv_Copy(node->x16, node->x2A); + Bv_Minus(node->x22, node->x2A); + Bv_Or(node->x1E, node->x2A); + node = node->nextnode; + } + + IRO_CheckForUserBreak(); + + Bv_AllocVector(&bv, IRO_NumAssign); + do { + flag = 0; + for (node = IRO_FirstNode; node; node = node->nextnode) { + if (node == IRO_FirstNode) { + Bv_Clear(bv); + } else { + UInt16 i; + Bv_Set(bv); + for (i = 0; i < node->numpred; i++) + Bv_And(IRO_NodeTable[node->pred[i]]->x2A, bv); + } + + if (!Bv_Compare(bv, node->x16)) { + flag = 1; + Bv_Copy(bv, node->x16); + } + + Bv_Copy(node->x16, node->x2A); + Bv_Minus(node->x22, node->x2A); + Bv_Or(node->x1E, node->x2A); + } + } while (flag); + + IRO_CheckForUserBreak(); + + node = IRO_FirstNode; + ass = IRO_FirstAssign; + while (node) { + IRO_Avail = node->x16; + linear = node->first; + while (1) { + if (!linear) + break; + + if (IRO_IsVariable(linear) && !(linear->flags & IROLF_Assigned)) { + if ((var = IRO_FindVar(linear->u.diadic.left->u.node->data.objref, 0, 1))) { + //IROAssign *ass2; + for (ass2 = IRO_FirstAssign; ass2; ass2 = ass2->next) { + if ( + ass2->varIndex == var->index && + Bv_IsBitSet(ass2->index, IRO_Avail) && + (IRO_IsConstant(ass2->linear2) || node->loopdepth <= ass2->node->loopdepth) && + !PropagationHasDefsInUnorderedRegions(linear, ass2->linear2) + ) { + if (ass2->linear2->type == IROLinearOperand && IRO_is_CPtypeequal(linear->rtype, ass2->linear->u.diadic.left->rtype)) { + ENode *enode = IRO_NewENode(ass2->linear2->u.node->type); + *enode = *ass2->linear2->u.node; + if (enode->type == EINTCONST) { + if (linear->flags & IROLF_BitfieldIndirect) { + IRO_TruncateBitfieldValueToType(&enode->data.intval, linear->rtype, var->x1A); + enode->rtype = linear->rtype; + result = 1; + } else { + IRO_TruncateValueToType(&enode->data.intval, linear->rtype); + enode->rtype = linear->rtype; + } + } + linear->u.monadic->type = IROLinearNop; + linear->type = IROLinearOperand; + linear->u.node = enode; + } else if (ass2->varObj && IRO_is_CPtypeequal(linear->rtype, ass2->linear->rtype)) { + linear->u.diadic.left->u.node = create_objectrefnode(ass2->varObj); + if (ass2->linear2->flags & IROLF_BitfieldIndirect) + linear->flags |= IROLF_BitfieldIndirect; + } + IRO_Dump("Found propagation at %d from %d\n", linear->index, ass2->linear->index); + break; + } + } + } + } else if (linear->type == IROLinearAsm) { + IAEffects effects; + int i; + CodeGen_GetAsmEffects(linear->u.asm_stmt, &effects); + + for (i = 0; i < effects.numoperands; i++) { + if (effects.operands[i].type == IAEffect_0 && effects.operands[i].offset == 0 && effects.operands[i].object->type->size == effects.operands[i].size) { + if ((var = IRO_FindVar(effects.operands[i].object, 0, 1))) { + //IROAssign *ass2; + for (ass2 = IRO_FirstAssign; ass2; ass2 = ass2->next) { + if (ass2->varIndex == var->index && Bv_IsBitSet(ass2->index, IRO_Avail) && ass2->linear->rtype->size == effects.operands[i].size) { + ENode *enode; + if (ass2->varObj) + enode = create_objectrefnode(ass2->varObj); + else if (ass2->linear2->type == IROLinearOperand) + enode = ass2->linear2->u.node; + else + CError_FATAL(768); + CodeGen_PropagateIntoAsm(linear->u.asm_stmt, effects.operands[i].object, enode); + break; + } + } + } + } + } + } + + if (IsIntGenKillCandidate(linear)) { + //IROAssign *ass2; + Bv_Clear(IRO_VarKills); + IRO_GetKills(linear); + + for (ass2 = IRO_FirstAssign; ass2; ass2 = ass2->next) { + if (Bv_IsBitSet(ass2->varIndex, IRO_VarKills)) { + Bv_ClearBit(ass2->index, IRO_Avail); + } + if (ass2->var && Bv_IsBitSet(ass2->var->index, IRO_VarKills)) { + Bv_ClearBit(ass2->index, IRO_Avail); + } + } + + while (ass && ass->linear == linear) { + Bv_SetBit(ass->index, IRO_Avail); + ass = ass->next; + } + } + + if (linear == node->last) + break; + linear = linear->next; + } + node = node->nextnode; + } + + IRO_CheckForUserBreak(); + + return result; +} + +void IRO_ExpressionPropagation(void) { + IRONode *node; + IROLinear *linear; + Object *obj; + VarRecord *var; + IROAssign *ass; + + for (node = IRO_FirstNode; node; node = node->nextnode) { + IRO_FirstAssign = NULL; + IRO_LastAssign = NULL; + IRO_NumAssign = 0; + + linear = node->first; + while (1) { + IROList list; + if (!linear) + break; + + IRO_InitList(&list); + if (IsPropagatableExpr(linear, &list)) { + if ((var = IRO_FindAssigned(linear))) { + IRO_Dump("Found propagatable expression assignment at: %d\n", linear->index); + ass = oalloc(sizeof(IROAssign)); + ass->linear = linear; + ass->next = NULL; + ass->index = ++IRO_NumAssign; + ass->varIndex = var->index; + ass->linear2 = linear->u.diadic.right; + ass->x20 = 0; + ass->node = node; + IRO_FindDepends(linear->u.diadic.right); + ass->depends = IRO_Depends; + if (!IRO_FirstAssign) { + IRO_FirstAssign = ass; + ass->prev = NULL; + } else { + IRO_LastAssign->next = ass; + ass->prev = IRO_LastAssign; + } + IRO_LastAssign = ass; + } + } + + if (IRO_IsVariable(linear) && !(linear->flags & IROLF_Assigned)) { + if ((var = IRO_FindVar(linear->u.monadic->u.node->data.objref, 0, 1))) { + for (ass = IRO_LastAssign; ass; ass = ass->prev) { + if (ass->varIndex == var->index) + ass->x20++; + } + } + } + + if (linear == node->last) + break; + linear = linear->next; + } + + Bv_AllocVector(&IRO_Avail, IRO_NumAssign); + + linear = node->first; + while (1) { + if (!linear) + break; + + if (IRO_IsVariable(linear) && !(linear->flags & IROLF_Assigned)) { + if ((var = IRO_FindVar(linear->u.monadic->u.node->data.objref, 0, 1))) { + for (ass = IRO_FirstAssign; ass; ass = ass->next) { + if (ass->varIndex == var->index && Bv_IsBitSet(ass->index, IRO_Avail) && !PropagationHasDefsInUnorderedRegions(linear, ass->linear2)) { + if (ass->linear2->type == IROLinearOperand && IRO_is_CPtypeequal(linear->rtype, ass->linear->u.diadic.left->rtype)) { + ENode *enode = IRO_NewENode(ass->linear2->u.node->type); + *enode = *ass->linear2->u.node; + if (enode->type == EINTCONST) { + IRO_TruncateValueToType(&enode->data.intval, linear->rtype); + enode->rtype = linear->rtype; + } else if (enode->type == EOBJREF) { + IROLinear *tmp = IRO_LocateFather(linear); + if (tmp && (tmp->flags & IROLF_Assigned)) + linear->flags |= IROLF_Assigned; + } + linear->u.monadic->type = IROLinearNop; + linear->type = IROLinearOperand; + linear->u.node = enode; + } else if (IRO_IsVariable(ass->linear2) && IRO_is_CPtypeequal(linear->rtype, ass->linear->rtype)) { + linear->u.monadic->u.node = create_objectrefnode(ass->linear2->u.monadic->u.node->data.objref); + if (ass->linear2->flags & IROLF_BitfieldIndirect) + linear->flags |= IROLF_BitfieldIndirect; + } else if (IRO_is_CPtypeequal(linear->rtype, ass->linear->rtype) && ass->x20 == 1 && !VarIsUsedInOtherFNodes(var, node)) { + IROList list; + IRO_InitList(&list); + IRO_DuplicateExpr(ass->linear->u.diadic.right, &list); + if (IS_TYPE_FLOAT(ass->linear->rtype)) { + IROLinear *tmp = IRO_NewLinear(IROLinearOp1Arg); + tmp->index = ++IRO_NumLinear; + tmp->rtype = ass->linear->rtype; + tmp->nodetype = ETYPCON; + tmp->nodeflags = ENODE_FLAG_80; + tmp->u.monadic = list.tail; + IRO_AddToList(tmp, &list); + } + IRO_PasteAfter(list.head, list.tail, linear); + IRO_LocateFather_Cut_And_Paste(linear, list.tail); + linear = list.tail; + } + IRO_Dump("Found expression propagation at %d from %d\n", linear->index, ass->linear->index); + break; + } + } + } + } + + if (linear->type != IROLinearNop && IsIntGenKillCandidate(linear)) { + Bv_Clear(IRO_VarKills); + IRO_GetKills(linear); + for (ass = IRO_FirstAssign; ass; ass = ass->next) { + if (Bv_IsBitSet(ass->varIndex, IRO_VarKills)) + Bv_ClearBit(ass->index, IRO_Avail); + if ((obj = IRO_IsVariable(ass->linear->u.diadic.right))) { + if ((var = IRO_FindVar(obj, 0, 1))) { + if (Bv_IsBitSet(var->index, IRO_VarKills)) + Bv_ClearBit(ass->index, IRO_Avail); + } + } else { + IROList list; + IRO_InitList(&list); + IRO_Depends = ass->depends; + IRO_FindDepends_NoAlloc(ass->linear->u.diadic.right); + if (Bv_BitsInCommon(IRO_VarKills, ass->depends)) + Bv_ClearBit(ass->index, IRO_Avail); + } + } + + for (ass = IRO_FirstAssign; ass; ass = ass->next) { + IRO_Depends = ass->depends; + IRO_FindDepends_NoAlloc(ass->linear->u.diadic.right); + if (ass->linear == linear && !Bv_IsBitSet(ass->varIndex, ass->depends)) + Bv_SetBit(ass->index, IRO_Avail); + } + } + + if (linear == node->last) + break; + linear = linear->next; + } + } + + IRO_CheckForUserBreak(); +} + |