diff options
Diffstat (limited to 'compiler_and_linker/FrontEnd/Optimizer/IroCSE.c')
| -rw-r--r-- | compiler_and_linker/FrontEnd/Optimizer/IroCSE.c | 1038 |
1 files changed, 1038 insertions, 0 deletions
diff --git a/compiler_and_linker/FrontEnd/Optimizer/IroCSE.c b/compiler_and_linker/FrontEnd/Optimizer/IroCSE.c new file mode 100644 index 0000000..7bc4866 --- /dev/null +++ b/compiler_and_linker/FrontEnd/Optimizer/IroCSE.c @@ -0,0 +1,1038 @@ +#include "IroCSE.h" +#include "IroDump.h" +#include "IroFlowgraph.h" +#include "IroLinearForm.h" +#include "IroMalloc.h" +#include "IroPointerAnalysis.h" +#include "IroSubable.h" +#include "IROUseDef.h" +#include "IroUtil.h" +#include "IroVars.h" +#include "compiler/CError.h" +#include "compiler/CExpr.h" +#include "compiler/CInt64.h" +#include "compiler/CParser.h" +#include "compiler/CompilerTools.h" +#include "compiler/objects.h" + +BitVector *IRO_Depends; +Boolean IRO_NotSubable; +Boolean IRO_IsVolatile; +Boolean IRO_CouldError; +IROExpr *IRO_FirstExpr; +IROExpr *IRO_LastExpr; +SInt32 IRO_NumExprs; +static Boolean HasVectorOperand; + +// forward decls +static void IRO_DependsOnForDataFlow(IROLinear *linear, Boolean flag); + +static void GetDependsOfIndirect(IROLinear *nd) { + IROListNode *resultList; + IROListNode *next; + IROListNode *list; + IROListNode *scan; + IROLinear *scannd; + Object *obj; + VarRecord *var; + int index; + Boolean result; + Boolean foundObjRef; + + result = 0; + + if (nd && copts.opt_pointer_analysis && nd->pointsToFunction && FunctionName) { + resultList = NULL; + PointerAnalysis_LookupLinearNodePointerExpr(FunctionName, nd, &resultList); + if ((list = resultList)) { + for (scan = list; scan; scan = scan->nextList) { + if (!scan->list.head || !scan->list.tail) { + result = 1; + break; + } + + foundObjRef = 0; + for (scannd = scan->list.head; scannd != scan->list.tail->next; scannd = scannd->next) { + if (scannd->type == IROLinearOperand && scannd->u.node->type == EOBJREF) { + foundObjRef = 1; + break; + } + } + + if (!foundObjRef) { + result = 1; + break; + } + } + + if (!result) { + while (list) { + for (scannd = list->list.head; scannd != list->list.tail->next; scannd = scannd->next) { + if (scannd->type == IROLinearOperand && scannd->u.node->type == EOBJREF) { + obj = scannd->u.node->data.objref; + CError_ASSERT(119, obj != NULL); + var = IRO_FindVar(obj, 1, 1); + CError_ASSERT(121, var != NULL); + index = var->index; + CError_ASSERT(123, index != 0); + + if (is_volatile_object(obj)) { + IRO_IsVolatile = 1; + IRO_NotSubable = 1; + } + Bv_SetBit(index, IRO_Depends); + } + } + list = list->nextList; + } + } + + while (resultList) { + next = resultList->nextList; + IRO_free(resultList); + resultList = next; + } + } else { + result = 1; + } + } else { + result = 1; + } + + if (result) { + nd = nd->u.monadic; + if (nd->type == IROLinearOp1Arg && nd->nodetype == EBITFIELD) + nd = nd->u.monadic; + + if (nd->type == IROLinearOp2Arg && nd->nodetype == EADD) { + IRO_BaseTerms = 0; + IRO_VarTerms = 0; + IRO_DecomposeAddressExpression_Cheap(nd); + if (IRO_BaseTerms != 1) { + IRO_CouldError = 1; + Bv_SetBit(0, IRO_Depends); + Bv_Or(IRO_FuncKills, IRO_Depends); + } + if (IRO_VarTerms) + IRO_CouldError = 1; + } else { + IRO_CouldError = 1; + Bv_SetBit(0, IRO_Depends); + Bv_Or(IRO_FuncKills, IRO_Depends); + } + } +} + +static void GetDependsOfFunctionCallForDataFlow(IROLinear *nd) { + IROLinear *innernd; + IROListNode *resultList; + IROListNode *next; + IROListNode *list; + IROListNode *scan; + IROLinear *scannd; + Object *obj; + VarRecord *var; + int index; + Boolean result; + Boolean foundObjRef; + ObjectList *olist; + ObjectList *depsList; + + result = 0; + innernd = nd->u.funccall.linear8; + + if (innernd && copts.opt_pointer_analysis && innernd->pointsToFunction && FunctionName) { + resultList = NULL; + PointerAnalysis_LookupLinearNodePointerExpr(FunctionName, innernd, &resultList); + if ((list = resultList)) { + for (scan = list; scan; scan = scan->nextList) { + if (!scan->list.head || !scan->list.tail) { + result = 1; + break; + } + + foundObjRef = 0; + for (scannd = scan->list.head; scannd != scan->list.tail->next; scannd = scannd->next) { + if (scannd->type == IROLinearOperand && scannd->u.node->type == EOBJREF) { + foundObjRef = 1; + obj = scannd->u.node->data.objref; + CError_ASSERT(234, obj != NULL); + + depsList = NULL; + PointerAnalysis_GetFunctionDependencies(obj, nd, &depsList); + + for (olist = depsList; olist; olist = olist->next) { + if (!olist->object) { + result = 1; + break; + } + } + + while (depsList) { + olist = depsList->next; + IRO_free(depsList); + depsList = olist; + } + + if (result) + break; + } + } + + if (!foundObjRef) + result = 1; + if (result) + break; + } + + if (!result) { + for (list = resultList; list; list = list->nextList) { + for (scannd = list->list.head; scannd != list->list.tail->next; scannd = scannd->next) { + if (scannd->type == IROLinearOperand && scannd->u.node->type == EOBJREF) { + obj = scannd->u.node->data.objref; + + depsList = NULL; + PointerAnalysis_GetFunctionDependencies(obj, nd, &depsList); + + for (olist = depsList; olist; olist = olist->next) { + var = IRO_FindVar(olist->object, 1, 1); + CError_ASSERT(285, var != NULL); + index = var->index; + CError_ASSERT(287, index != 0); + + if (is_volatile_object(olist->object)) { + IRO_IsVolatile = 1; + IRO_NotSubable = 1; + } + Bv_SetBit(index, IRO_Depends); + } + + while (depsList) { + olist = depsList->next; + IRO_free(depsList); + depsList = olist; + } + } + } + } + } + + while (resultList) { + next = resultList->nextList; + IRO_free(resultList); + resultList = next; + } + } else { + result = 1; + } + } else { + result = 1; + } + + if (result) { + IRO_DependsOnForDataFlow(nd->u.funccall.linear8, 0); + Bv_Or(IRO_FuncKills, IRO_Depends); + + for (index = nd->u.funccall.argCount - 1; index >= 0; index--) + IRO_DependsOnForDataFlow(nd->u.funccall.args[index], 0); + } +} + +static void IRO_DependsOn(IROLinear *linear, Boolean flag) { + VarRecord *var; + IROLinear *inner; + + if (linear->rtype && CParser_IsVolatile(linear->rtype, linear->nodeflags & ENODE_FLAG_QUALS)) { + IRO_IsVolatile = 1; + IRO_NotSubable = 1; + } + + if (!IRO_NotSubable) { + switch (linear->type) { + case IROLinearOperand: + if (flag && linear->u.node->type == EOBJREF) { + if ((var = IRO_FindVar(linear->u.node->data.objref, 0, 1))) { + if (is_volatile_object(var->object)) { + IRO_IsVolatile = 1; + IRO_NotSubable = 1; + } + Bv_SetBit(var->index, IRO_Depends); + } else { + IRO_NotSubable = 1; + } + } + break; + case IROLinearOp1Arg: + if (IRO_IsAssignOp[linear->nodetype]) { + IRO_NotSubable = 1; + } else { + inner = linear->u.monadic; + if (linear->nodetype == EINDIRECT) { + if (inner->type == IROLinearOp1Arg && inner->nodetype == EBITFIELD) + inner = inner->u.monadic; + if (inner->type != IROLinearOperand || inner->u.node->type != EOBJREF) + GetDependsOfIndirect(linear); + } + + IRO_DependsOn(inner, linear->nodetype == EINDIRECT); + } + break; + case IROLinearOp2Arg: + if (IRO_IsAssignOp[linear->nodetype]) { + IRO_NotSubable = 1; + } else { + if (linear->nodetype == EDIV || linear->nodetype == EMODULO) { + if (IRO_IsIntConstant(linear->u.diadic.right)) { + if (CInt64_Equal(linear->u.diadic.right->u.node->data.intval, cint64_zero)) + IRO_CouldError = 1; + } else { + IRO_CouldError = 1; + } + } + + IRO_DependsOn(linear->u.diadic.left, flag); + IRO_DependsOn(linear->u.diadic.right, flag); + } + break; + case IROLinearOp3Arg: + if (IRO_IsAssignOp[linear->nodetype]) { + IRO_NotSubable = 1; + } else { + IRO_DependsOn(linear->u.args3.a, flag); + IRO_DependsOn(linear->u.args3.b, flag); + IRO_DependsOn(linear->u.args3.c, flag); + } + break; + case IROLinearFunccall: + IRO_NotSubable = 1; + break; + default: + CError_FATAL(479); + } + } +} + +static void IRO_DependsOnForDataFlow(IROLinear *linear, Boolean flag) { + VarRecord *var; + IROLinear *inner; + + if (linear->rtype && CParser_IsVolatile(linear->rtype, linear->nodeflags & ENODE_FLAG_QUALS)) { + IRO_IsVolatile = 1; + IRO_NotSubable = 1; + } + + switch (linear->type) { + case IROLinearOperand: + if (flag && linear->u.node->type == EOBJREF) { + if ((var = IRO_FindVar(linear->u.node->data.objref, 0, 1))) { + if (is_volatile_object(var->object)) { + IRO_IsVolatile = 1; + IRO_NotSubable = 1; + } + Bv_SetBit(var->index, IRO_Depends); + } else { + IRO_NotSubable = 1; + } + } + break; + case IROLinearOp1Arg: + if (IRO_IsAssignOp[linear->nodetype]) + IRO_NotSubable = 1; + + inner = linear->u.monadic; + if (linear->nodetype == EINDIRECT) { + if (inner->type == IROLinearOp1Arg && inner->nodetype == EBITFIELD) + inner = inner->u.monadic; + if (inner->type != IROLinearOperand || inner->u.node->type != EOBJREF) + GetDependsOfIndirect(linear); + } + + IRO_DependsOnForDataFlow(inner, linear->nodetype == EINDIRECT); + break; + case IROLinearOp2Arg: + if (IRO_IsAssignOp[linear->nodetype]) + IRO_NotSubable = 1; + + if (linear->nodetype == EDIV || linear->nodetype == EMODULO) { + if (IRO_IsIntConstant(linear->u.diadic.right)) { + if (CInt64_Equal(linear->u.diadic.right->u.node->data.intval, cint64_zero)) + IRO_CouldError = 1; + } else { + IRO_CouldError = 1; + } + } + + IRO_DependsOnForDataFlow(linear->u.diadic.left, flag); + IRO_DependsOnForDataFlow(linear->u.diadic.right, flag); + break; + case IROLinearOp3Arg: + if (IRO_IsAssignOp[linear->nodetype]) + IRO_NotSubable = 1; + + IRO_DependsOnForDataFlow(linear->u.args3.a, flag); + IRO_DependsOnForDataFlow(linear->u.args3.b, flag); + IRO_DependsOnForDataFlow(linear->u.args3.c, flag); + break; + case IROLinearFunccall: + IRO_NotSubable = 1; + GetDependsOfFunctionCallForDataFlow(linear); + break; + default: + CError_FATAL(650); + } +} + +void IRO_FindDepends_NoAlloc(IROLinear *linear) { + Bv_Clear(IRO_Depends); + IRO_CouldError = 0; + IRO_NotSubable = 0; + IRO_IsVolatile = 0; + IRO_DependsOnForDataFlow(linear, 0); +} + +void IRO_FindDepends(IROLinear *linear) { + Bv_AllocVector(&IRO_Depends, IRO_NumVars + 1); + IRO_CouldError = 0; + IRO_NotSubable = 0; + IRO_DependsOn(linear, 0); +} + +static void VecAct(IROLinear *linear, Boolean isFirst) { + if (!isFirst && (linear->flags & IROLF_VecOpBase)) + HasVectorOperand = 1; +} + +static Boolean IRO_DoesNotHaveVectorOperand(IROLinear *linear) { + HasVectorOperand = 0; + IRO_WalkTree(linear, VecAct); + return HasVectorOperand == 0; +} + +static void IRO_AddExpression(IROLinear *linear, IRONode *node, Boolean flag) { + IROExpr *expr; + + if ((linear->flags & IROLF_Reffed) && IRO_IsSubableExpression(linear) && IRO_DoesNotHaveVectorOperand(linear)) { + expr = oalloc(sizeof(IROExpr)); + expr->x0 = 0; + expr->index = ++IRO_NumExprs; + expr->linear = linear; + expr->x8 = NULL; + expr->node = node; + IRO_FindDepends(linear); + expr->depends = IRO_Depends; + expr->notSubable = IRO_NotSubable; + expr->couldError = IRO_CouldError; + expr->next = NULL; + expr->x14 = NULL; + if (IRO_FirstExpr) + IRO_LastExpr->next = expr; + else + IRO_FirstExpr = expr; + IRO_LastExpr = expr; + linear->expr = expr; + } +} + +void IRO_FindExpressions(BitVector *bv, Boolean flag) { + IROLinear *nd; + IRONode *fnode; + + IRO_FirstExpr = IRO_LastExpr = NULL; + IRO_NumExprs = 0; + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + if (!bv || Bv_IsBitSet(fnode->index, bv)) { + for (nd = fnode->first; nd; nd = nd->next) { + nd->expr = NULL; + IRO_AddExpression(nd, fnode, flag); + if (nd == fnode->last) + break; + } + } else { + for (nd = fnode->first; nd; nd = nd->next) { + nd->expr = NULL; + if (nd == fnode->last) + break; + } + } + } + + IRO_CheckForUserBreak(); +} + +void IRO_RemoveExpr(IROExpr *expr) { + IROExpr *prev; + IROExpr *scan; + + scan = IRO_FirstExpr; + prev = NULL; + while (scan != expr) { + prev = scan; + scan = scan->next; + CError_ASSERT(809, scan); + } + + expr->linear->expr = NULL; + if (prev) + prev->next = expr->next; + else + IRO_FirstExpr = expr->next; +} + +static void GetExprKillsByIndirectAssignment(IROLinear *linear) { + IROLinear *inner; + IROListNode *resultList; + IROListNode *next; + IROListNode *list; + IROListNode *scan; + IROLinear *scannd; + Object *obj; + VarRecord *var; + int index; + Boolean result; + Boolean foundObjRef; + IROExpr *expr; + + result = 0; + if (linear->type == IROLinearOp2Arg) + linear = linear->u.diadic.left; + else + linear = linear->u.monadic; + + if ( + linear && + linear->type == IROLinearOp1Arg && + linear->nodetype == EINDIRECT && + (inner = linear->u.monadic) && + copts.opt_pointer_analysis && + inner->pointsToFunction && + FunctionName + ) { + resultList = NULL; + PointerAnalysis_LookupLinearNodePointerExpr(FunctionName, inner, &resultList); + if ((list = resultList)) { + for (scan = list; scan; scan = scan->nextList) { + if (!scan->list.head || !scan->list.tail) { + result = 1; + break; + } + + foundObjRef = 0; + for (scannd = scan->list.head; scannd != scan->list.tail->next; scannd = scannd->next) { + if (scannd->type == IROLinearOperand && scannd->u.node->type == EOBJREF) { + foundObjRef = 1; + break; + } + } + + if (!foundObjRef) { + result = 1; + break; + } + } + + if (!result) { + while (list) { + for (scannd = list->list.head; scannd != list->list.tail->next; scannd = scannd->next) { + if (scannd->type == IROLinearOperand && scannd->u.node->type == EOBJREF) { + obj = scannd->u.node->data.objref; + CError_ASSERT(893, obj != NULL); + var = IRO_FindVar(obj, 1, 1); + CError_ASSERT(895, var != NULL); + index = var->index; + + for (expr = IRO_FirstExpr; expr; expr = expr->next) { + if (Bv_IsBitSet(index, expr->depends)) + Bv_SetBit(expr->index, IRO_ExprKills); + } + } + } + list = list->nextList; + } + } + + while (resultList) { + next = resultList->nextList; + IRO_free(resultList); + resultList = next; + } + } else { + result = 1; + } + } else { + result = 1; + } + + if (result) { + for (expr = IRO_FirstExpr; expr; expr = expr->next) { + if (Bv_BitsInCommon(expr->depends, IRO_FuncKills)) + Bv_SetBit(expr->index, IRO_ExprKills); + } + } +} + +static void GetExprKillsByFunctionCall(IROLinear *funccall) { + IROLinear *innernd; + IROListNode *resultList; + IROListNode *next; + IROListNode *list; + IROListNode *scan; + IROLinear *scannd; + Object *obj; + VarRecord *var; + int index; + Boolean result; + Boolean foundObjRef; + ObjectList *olist; + ObjectList *depsList; + IROExpr *expr; + + result = 0; + innernd = funccall->u.funccall.linear8; + + if (innernd && copts.opt_pointer_analysis && innernd->pointsToFunction && FunctionName) { + resultList = NULL; + PointerAnalysis_LookupLinearNodePointerExpr(FunctionName, innernd, &resultList); + if ((list = resultList)) { + for (scan = list; scan; scan = scan->nextList) { + if (!scan->list.head || !scan->list.tail) { + result = 1; + break; + } + + foundObjRef = 0; + for (scannd = scan->list.head; scannd != scan->list.tail->next; scannd = scannd->next) { + if (scannd->type == IROLinearOperand && scannd->u.node->type == EOBJREF) { + foundObjRef = 1; + obj = scannd->u.node->data.objref; + CError_ASSERT(991, obj != NULL); + + depsList = NULL; + PointerAnalysis_GetFunctionKills(obj, funccall, &depsList); + + for (olist = depsList; olist; olist = olist->next) { + if (!olist->object) { + result = 1; + break; + } + } + + while (depsList) { + olist = depsList->next; + IRO_free(depsList); + depsList = olist; + } + + if (result) + break; + } + } + + if (!foundObjRef) + result = 1; + if (result) + break; + } + + if (!result) { + for (list = resultList; list; list = list->nextList) { + for (scannd = list->list.head; scannd != list->list.tail->next; scannd = scannd->next) { + if (scannd->type == IROLinearOperand && scannd->u.node->type == EOBJREF) { + obj = scannd->u.node->data.objref; + + depsList = NULL; + PointerAnalysis_GetFunctionKills(obj, funccall, &depsList); + + for (olist = depsList; olist; olist = olist->next) { + var = IRO_FindVar(olist->object, 1, 1); + CError_ASSERT(1042, var != NULL); + index = var->index; + CError_ASSERT(1044, index != 0); + + for (expr = IRO_FirstExpr; expr; expr = expr->next) { + if (Bv_IsBitSet(index, expr->depends)) + Bv_SetBit(expr->index, IRO_ExprKills); + } + } + + while (depsList) { + olist = depsList->next; + IRO_free(depsList); + depsList = olist; + } + } + } + } + } + + while (resultList) { + next = resultList->nextList; + IRO_free(resultList); + resultList = next; + } + } else { + result = 1; + } + } else { + result = 1; + } + + if (result) { + for (expr = IRO_FirstExpr; expr; expr = expr->next) { + if (Bv_BitsInCommon(expr->depends, IRO_FuncKills)) + Bv_SetBit(expr->index, IRO_ExprKills); + } + } +} + +static void IRO_GetExprKills(IROLinear *linear) { + Bv_Clear(IRO_ExprKills); + switch (linear->type) { + case IROLinearOp1Arg: + case IROLinearOp2Arg: + if (IRO_IsAssignOp[linear->nodetype]) { + VarRecord *var; + int index; + + var = IRO_FindAssigned(linear); + index = 0; + if (var) + index = var->index; + if (!index) { + GetExprKillsByIndirectAssignment(linear); + } else { + IROExpr *expr; + for (expr = IRO_FirstExpr; expr; expr = expr->next) { + if (Bv_IsBitSet(index, expr->depends)) + Bv_SetBit(expr->index, IRO_ExprKills); + } + } + } + break; + case IROLinearAsm: { + IROExpr *expr; + IRO_GetKills(linear); + for (expr = IRO_FirstExpr; expr; expr = expr->next) { + if (Bv_BitsInCommon(expr->depends, IRO_VarKills)) + Bv_SetBit(expr->index, IRO_ExprKills); + } + break; + } + case IROLinearFunccall: + GetExprKillsByFunctionCall(linear); + break; + } +} + +void IRO_ComputeAvail(void) { + IRONode *node; + IROLinear *linear; + SInt32 counter; + BitVector *bv; + Boolean flag; + + counter = 0; + node = IRO_FirstNode; + Bv_AllocVector(&IRO_VarKills, IRO_NumVars + 1); + Bv_AllocVector(&IRO_ExprKills, IRO_NumExprs + 1); + + while (node) { + Bv_AllocVector(&node->x16, IRO_NumExprs); + if (node->numpred) + Bv_Set(node->x16); + Bv_AllocVector(&node->x22, IRO_NumExprs); + Bv_AllocVector(&node->x1E, IRO_NumExprs); + Bv_AllocVector(&node->x1A, IRO_NumExprs); + + for (linear = node->first; linear; linear = linear->next) { + if (linear->expr) + Bv_SetBit(linear->expr->index, node->x1E); + IRO_GetExprKills(linear); + Bv_Or(IRO_ExprKills, node->x22); + Bv_Minus(IRO_ExprKills, node->x1E); + if (linear == node->last) + break; + + if (counter > 250) { + IRO_CheckForUserBreak(); + counter = 0; + } else { + counter++; + } + } + + Bv_Copy(node->x16, node->x1A); + Bv_Minus(node->x22, node->x1A); + Bv_Or(node->x1E, node->x1A); + node = node->nextnode; + } + + IRO_CheckForUserBreak(); + + Bv_AllocVector(&bv, IRO_NumExprs); + do { + flag = 0; + for (node = IRO_FirstNode; node; node = node->nextnode) { + if (!node->numpred) { + Bv_Clear(bv); + } else { + UInt16 i; + Bv_Set(bv); + for (i = 0; i < node->numpred; i++) + Bv_And(IRO_NodeTable[node->pred[i]]->x1A, bv); + } + + if (!Bv_Compare(bv, node->x16)) { + flag = 1; + Bv_Copy(bv, node->x16); + } + + Bv_Copy(node->x16, node->x1A); + Bv_Minus(node->x22, node->x1A); + Bv_Or(node->x1E, node->x1A); + } + IRO_CheckForUserBreak(); + } while (flag); +} + +static void IRO_MakeReplacementEmbedded(IROExpr *expr) { + IROLinear *opnd; + IROLinear *ind; + IROLinear *ass; + + IRO_GetTemp(expr); + + opnd = IRO_NewLinear(IROLinearOperand); + opnd->u.node = create_objectrefnode(expr->x8); + opnd->rtype = opnd->u.node->data.objref->type; + opnd->index = ++IRO_NumLinear; + opnd->flags |= IROLF_Reffed | IROLF_Assigned | IROLF_Ind; + + ind = IRO_NewLinear(IROLinearOp1Arg); + ind->nodetype = EINDIRECT; + ind->rtype = expr->linear->rtype; + ind->u.monadic = opnd; + ind->index = ++IRO_NumLinear; + ind->flags |= IROLF_Reffed | IROLF_Assigned; + + ass = IRO_NewLinear(IROLinearOp2Arg); + ass->nodetype = EASS; + ass->u.diadic.left = ind; + ass->u.diadic.right = expr->linear; + ass->rtype = expr->linear->rtype; + ass->index = ++IRO_NumLinear; + + opnd->next = ind; + ind->next = ass; + IRO_ReplaceReferenceWithNode(expr->linear, ass); + IRO_PasteAfter(opnd, ass, expr->linear); +} + +static void IRO_ActUnmarkSubExpressions(IROLinear *linear, Boolean isFirst) { + if (isFirst) + linear->flags &= ~IROLF_8; +} + +static void CheckCommonSub(IROLinear *linear) { + IROExpr *expr; + + for (expr = IRO_FirstExpr; expr; expr = expr->next) { + if (expr->linear != linear && !expr->x14) { + if (Bv_IsBitSet(expr->index, IRO_Avail) && !expr->notSubable && IRO_ExprsSame(linear, expr->linear)) { + IRO_WalkTree(linear, IRO_ActUnmarkSubExpressions); + linear->flags |= IROLF_8; + linear->expr->x14 = expr; + break; + } + } + } +} + +static void MoveCommonSub(IROExpr *expr) { + SInt32 best; + SInt32 sz1; + SInt32 sz2; + SInt32 i1; + SInt32 i2; + IROLinear *scan; + IROLinear *array1[64]; + IROLinear *array2[64]; + IROExpr *scanexpr; + + sz1 = 0; + scan = expr->linear; + do { + scan = IRO_LocateFather(scan); + if (scan) { + if (sz1 == 64) + return; + array1[sz1++] = scan; + } + } while (scan); + + best = -1; + for (scanexpr = IRO_FirstExpr; scanexpr; scanexpr = scanexpr->next) { + if (scanexpr->x14 == expr) { + sz2 = 0; + scan = scanexpr->linear; + do { + scan = IRO_LocateFather(scan); + if (scan) { + if (sz2 == 64) + return; + array2[sz2++] = scan; + } + } while (scan); + + i1 = sz1; + i2 = sz2; + while (i1 && i2 && array1[i1 - 1] == array2[i2 - 1]) { + i1--; + i2--; + } + + if (i1 != sz1 && i1 > best) + best = i1; + } + } + + if (best < 0) { + IRO_MakeReplacementEmbedded(expr); + } else { + IROLinear *start; + IROLinear *comma; + IRO_Dump("Moving common sub from node %d to %d\n", expr->linear->index, array1[best]->index); + start = IRO_FindStart(array1[best]); + IRO_GetTemp(expr); + IRO_ReplaceReference(expr->linear, expr->x8, expr->linear); + IRO_MoveExpression(expr, start); + + comma = IRO_NewLinear(IROLinearOp2Arg); + comma->nodetype = ECOMMA; + comma->rtype = array1[best]->rtype; + comma->u.diadic.left = IRO_AssignToTemp(expr); + comma->u.diadic.right = array1[best]; + comma->stmt = array1[best]->stmt; + IRO_ReplaceReferenceWithNode(array1[best], comma); + IRO_PasteAfter(comma, comma, array1[best]); + } +} + +static void ReplaceCommonSub(IROLinear *linear) { + IROExpr *expr = linear->expr->x14; + if (!expr->x8) { + MoveCommonSub(expr); + if (!expr->x8) + return; + } + + IRO_Dump("Replacing common sub at %d with %d\n", linear->index, expr->linear->index); + IRO_ReplaceReference(linear, expr->x8, linear); + IRO_RemoveExpr(linear->expr); + IRO_NopOut(linear); +} + +void IRO_CommonSubs(void) { + IRONode *node; + IROLinear *linear; + SInt32 counter; + + counter = 0; + for (node = IRO_FirstNode; node; node = node->nextnode) { + IRO_Avail = node->x16; + linear = node->first; + while (1) { + if (!linear) + break; + if (linear->expr && !linear->expr->notSubable) + CheckCommonSub(linear); + if (linear->expr) + Bv_SetBit(linear->expr->index, IRO_Avail); + IRO_GetExprKills(linear); + Bv_Minus(IRO_ExprKills, IRO_Avail); + if (linear == node->last) + break; + if (counter > 250) { + IRO_CheckForUserBreak(); + counter = 0; + } else { + counter++; + } + linear = linear->next; + } + } + + for (node = IRO_FirstNode; node; node = node->nextnode) { + for (linear = node->first; linear; linear = linear->next) { + if (linear->expr && (linear->flags & IROLF_8) && !IRO_HasSideEffect(linear)) + ReplaceCommonSub(linear); + if (linear == node->last) + break; + if (counter > 250) { + IRO_CheckForUserBreak(); + counter = 0; + } else { + counter++; + } + } + } + + IRO_CheckForUserBreak(); +} + +static Boolean CountThisSubableOperandUse(IROUse *use) { + return use->x1C != 0; +} + +static int GetSubableOperandUseCount(VarRecord *var) { + int count = 0; + IROUse *use; + + if (var->uses) { + for (use = var->uses; use; use = use->varnext) { + if (CountThisSubableOperandUse(use)) + count++; + } + } + + return count; +} + +static void IRO_MakeTopLevelExprForSubableOperand(IROLinear *linear) { + IROLinear *copy = IRO_NewLinear(IROLinearOperand); + memcpy(copy, linear, sizeof(IROLinear)); + copy->index = ++IRO_NumLinear; + + if (IRO_FirstLinear && IRO_FirstLinear->type == IROLinearNop) + IRO_PasteAfter(copy, copy, IRO_FirstLinear); + else + IRO_Paste(copy, copy, IRO_FirstLinear); +} + +void IRO_GenerateTopLevelExprsForSubableOperands(void) { + IROLinear *nd; + IRONode *fnode; + VarRecord *var; + BitVector *bv; + + Bv_AllocVector(&bv, IRO_NumVars + 1); + + for (fnode = IRO_FirstNode; fnode; fnode = fnode->nextnode) { + for (nd = fnode->first; nd; nd = nd->next) { + nd->expr = NULL; + if ((nd->flags & IROLF_Reffed) && IRO_IsSubableExpression(nd) && IRO_DoesNotHaveVectorOperand(nd)) { + if (nd->type == IROLinearOperand && nd->u.node && nd->u.node->type == EOBJREF) { + if ((var = IRO_FindVar(nd->u.node->data.objref, 0, 1))) { + if (!Bv_IsBitSet(var->index, bv)) { + IRO_MakeTopLevelExprForSubableOperand(nd); + Bv_SetBit(var->index, bv); + } + } + } + } + + if (nd == fnode->last) + break; + } + } +} |