| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| /** |
| * @author Intel, Pavel A. Ozhdikhin |
| * |
| */ |
| |
| #include <assert.h> |
| #include <iostream> |
| #include <algorithm> |
| #include "Stl.h" |
| #include "Log.h" |
| #include "open/types.h" |
| #include "Inst.h" |
| #include "irmanager.h" |
| #include "reassociate.h" |
| #include "CSEHash.h" |
| #include "Opcode.h" |
| #include "constantfolder.h" |
| #include "simplifier.h" |
| #include "FlowGraph.h" |
| |
| namespace Jitrino { |
| |
| DEFINE_SESSION_ACTION(ReassociationPass, reassoc, "Reassociation") |
| |
| void |
| ReassociationPass::_run(IRManager& irm) { |
| Reassociate pass(irm, irm.getNestedMemoryManager()); |
| pass.runPass(false); |
| } |
| |
| DEFINE_SESSION_ACTION(DepthReassociationPass, reassocdepth, "Reassociation with Minimum Depth") |
| |
| void |
| DepthReassociationPass::_run(IRManager& irm) { |
| Reassociate pass(irm, irm.getNestedMemoryManager()); |
| pass.runPass(true); |
| } |
| |
| DEFINE_SESSION_ACTION(LateDepthReassociationPass, latereassocdepth, "Reassociation with Minimum Depth + Constant Mul/Div Optimization") |
| |
| void |
| LateDepthReassociationPass::_run(IRManager& irm) { |
| Reassociate pass(irm, irm.getNestedMemoryManager()); |
| pass.runPass(true, true); |
| } |
| |
| inline U_32 computePriority(U_32 op_cost, U_32 priority0) { |
| if (priority0 == 0) return 0; |
| else return op_cost + priority0; |
| } |
| inline U_32 computePriority(U_32 op_cost, U_32 priority0, U_32 priority1) { |
| if (priority0 == 0) return 0; |
| else return op_cost + ::std::max(priority0, priority1); |
| } |
| inline U_32 computePriority(U_32 op_cost, U_32 priority0, U_32 priority1, U_32 priority2) { |
| if ((priority0 == 0) && (priority1 == 0) && (priority2 == 0)) return 0; |
| else return op_cost + ::std::max(::std::max(priority0, priority1), priority2); |
| } |
| |
| inline bool operator < (const OpndWithPriority &a, const OpndWithPriority &b) |
| { |
| if (a.priority < b.priority) return true; |
| if (a.priority == b.priority) { |
| if (b.negate && !a.negate) return true; |
| } |
| return false; |
| } |
| |
| Reassociate::Reassociate(IRManager &irManager0, |
| MemoryManager& memManager) |
| : irManager(irManager0), |
| mm(memManager), |
| cfgRpoNum(memManager), |
| priority(memManager), |
| minDepth(false), |
| maxReassocDepth(64) |
| { |
| } |
| |
| Reassociate::~Reassociate() |
| { |
| } |
| |
| |
| U_32 Reassociate::getPriority(Opnd *opnd) |
| { |
| if (priority.has(opnd)) return priority[opnd]; |
| Inst *inst = opnd->getInst(); |
| U_32 opriority = 0; |
| Operation operation = inst->getOperation(); |
| Opcode opc = operation.getOpcode(); |
| switch (opc) { |
| case Op_LdConstant: |
| opriority = 0; break; |
| case Op_Copy: |
| opriority = getPriority(inst->getSrc(0)); break; |
| case Op_LdVar: |
| { |
| Opnd *var = inst->getSrc(0); |
| SsaVarOpnd *ssaVarOpnd = var->asSsaVarOpnd(); |
| assert(ssaVarOpnd); |
| opriority = getPriority(ssaVarOpnd); |
| } |
| break; |
| case Op_Add: |
| opriority = computePriority(costOfAdd, getPriority(inst->getSrc(0)), |
| getPriority(inst->getSrc(1))); |
| break; |
| case Op_Sub: |
| opriority = computePriority(costOfSub, getPriority(inst->getSrc(0)), |
| getPriority(inst->getSrc(1))); |
| break; |
| case Op_Neg: |
| opriority = computePriority(costOfNeg, getPriority(inst->getSrc(0))); |
| break; |
| case Op_Mul: |
| opriority = computePriority(costOfMul, getPriority(inst->getSrc(0)), |
| getPriority(inst->getSrc(1))); |
| break; |
| case Op_Conv: |
| opriority = computePriority(costOfConv, getPriority(inst->getSrc(0))); |
| break; |
| case Op_And: |
| case Op_Or: |
| case Op_Xor: |
| opriority = computePriority(costOfBoolOp, getPriority(inst->getSrc(0)), |
| getPriority(inst->getSrc(1))); |
| break; |
| case Op_Not: |
| opriority = computePriority(costOfNot, getPriority(inst->getSrc(0))); |
| break; |
| case Op_Shladd: |
| opriority = computePriority(costOfShladd,getPriority(inst->getSrc(0)), |
| getPriority(inst->getSrc(1)), |
| getPriority(inst->getSrc(2))); |
| break; |
| case Op_Shr: |
| case Op_Shl: |
| opriority = computePriority(costOfShift, getPriority(inst->getSrc(0)), |
| getPriority(inst->getSrc(1))); |
| break; |
| default: |
| if (operation.isMovable()) { |
| U_32 numOpnds = inst->getNumSrcOperands(); |
| opriority = 0; |
| |
| for (U_32 i = 0; i<numOpnds; i++) { |
| Opnd *opndi = inst->getSrc(i); |
| U_32 argpriority = getPriority(opndi); |
| opriority = ::std::max(opriority, argpriority); |
| } |
| opriority = computePriority(costOfMisc, opriority); |
| } else { |
| Inst *previ = inst->getPrevInst(); |
| U_32 ipriority = 1; |
| while (!previ->isLabel()) { |
| ++ipriority; |
| previ = previ->getPrevInst(); |
| } |
| Node *block = previ->asLabelInst()->getNode(); |
| U_32 bpriority = cfgRpoNum[block]; |
| opriority = ((bpriority * priorityFactorOfBlock) |
| + ipriority)*priorityFactorOfPosition; |
| } |
| break; |
| } |
| if (Log::isEnabled()) { |
| Log::out() << "Priority of "; |
| opnd->print(Log::out()); |
| Log::out() << " computed is " << (int) opriority << ::std::endl; |
| } |
| priority[opnd] = opriority; |
| return opriority; |
| } |
| |
| void Reassociate::runPass(bool minimizeDepth, bool isLate) |
| { |
| minDepth = minimizeDepth; |
| if (minimizeDepth) { |
| costOfAdd = 1; |
| costOfSub = 1; |
| costOfNeg = 1; |
| costOfMul = 15; |
| costOfConv = 1; |
| costOfBoolOp = 1; |
| costOfNot = 1; |
| costOfShladd = 1; |
| costOfShift = 1; |
| costOfMisc = 1; |
| priorityFactorOfBlock = 64; |
| priorityFactorOfPosition = 2; |
| } else { |
| costOfAdd = 0; |
| costOfSub = 0; |
| costOfNeg = 0; |
| costOfMul = 0; |
| costOfConv = 0; |
| costOfBoolOp = 0; |
| costOfNot = 0; |
| costOfShladd = 0; |
| costOfShift = 0; |
| costOfMisc = 0; |
| priorityFactorOfBlock = 64; |
| priorityFactorOfPosition = 1; |
| } |
| |
| if (Log::isEnabled()) { |
| Log::out() << "IR before Reassociation pass" << ::std::endl; |
| FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); |
| FlowGraph::printDotFile(irManager.getFlowGraph(), irManager.getMethodDesc(), "beforereassoc"); |
| } |
| |
| // first, assign Reverse-PostOrder numbers to flowGraph nodes |
| StlVector<Node *> postOrderNodes(mm); |
| ControlFlowGraph &fg = irManager.getFlowGraph(); |
| fg.getNodesPostOrder(postOrderNodes); |
| StlVector<Node *>::reverse_iterator |
| riter = postOrderNodes.rbegin(), |
| rend = postOrderNodes.rend(); |
| U_32 i = 0; |
| while (riter != rend) { |
| Node *node = *riter; |
| if (Log::isEnabled()) { |
| Log::out() << "RPO["; |
| FlowGraph::printLabel(Log::out(), node); |
| Log::out() << "] = " << (int) i; |
| Log::out() << ::std::endl; |
| } |
| cfgRpoNum[node] = i++; |
| ++riter; |
| } |
| numBlocks = i; |
| |
| SimplifierWithInstFactory simplifier(irManager, isLate, this); |
| theSimp = &simplifier; |
| simplifier.simplifyControlFlowGraph(); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "IR after Reassociation pass" << ::std::endl; |
| FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); |
| FlowGraph::printDotFile(irManager.getFlowGraph(), irManager.getMethodDesc(), "afterreassoc"); |
| } |
| } |
| |
| void |
| Reassociate::addAddAssoc(StlDeque<OpndWithPriority> &opnds, |
| bool negated, |
| Type* type, Opnd* opnd) |
| { |
| Inst *inst = opnd->getInst(); |
| if (inst->getType() == type->tag && opnds.size() < maxReassocDepth) { |
| switch(inst->getOpcode()) { |
| case Op_Add: |
| if (inst->getOverflowModifier() != Overflow_None) break; |
| if (Log::isEnabled()) { |
| Log::out() << "addAddAssoc of operand "; |
| opnd->print(Log::out()); |
| Log::out() << " is Add("; |
| inst->getSrc(0)->print(Log::out()); |
| Log::out() << ", "; |
| inst->getSrc(1)->print(Log::out()); |
| Log::out() << "), checking opnds" << ::std::endl; |
| } |
| addAddAssoc(opnds, negated, type, inst->getSrc(0)); |
| addAddAssoc(opnds, negated, type, inst->getSrc(1)); |
| return; |
| case Op_Neg: |
| if (Log::isEnabled()) { |
| Log::out() << "addAddAssoc of operand "; |
| opnd->print(Log::out()); |
| Log::out() << " is Neg("; |
| inst->getSrc(0)->print(Log::out()); |
| Log::out() << "), checking opnd" << ::std::endl; |
| } |
| addAddAssoc(opnds, !negated, type, inst->getSrc(0)); |
| return; |
| case Op_Sub: |
| if (inst->getOverflowModifier() != Overflow_None) break; |
| if (Log::isEnabled()) { |
| Log::out() << "addAddAssoc of operand "; |
| opnd->print(Log::out()); |
| Log::out() << " is Sub("; |
| inst->getSrc(0)->print(Log::out()); |
| Log::out() << ", "; |
| inst->getSrc(1)->print(Log::out()); |
| Log::out() << "), checking opnds" << ::std::endl; |
| } |
| addAddAssoc(opnds, negated, type, inst->getSrc(0)); |
| addAddAssoc(opnds, !negated, type, inst->getSrc(1)); |
| return; |
| case Op_Copy: |
| if (Log::isEnabled()) { |
| Log::out() << "addAddAssoc of operand "; |
| opnd->print(Log::out()); |
| Log::out() << " is Copy("; |
| inst->getSrc(0)->print(Log::out()); |
| Log::out() << "), checking opnd" << ::std::endl; |
| } |
| addAddAssoc(opnds, negated, type, inst->getSrc(0)); |
| return; |
| default: |
| break; |
| } |
| } |
| if (Log::isEnabled()) { |
| Log::out() << "addAddAssoc of operand "; |
| opnd->print(Log::out()); |
| Log::out() << " is terminal, adding" << ::std::endl; |
| } |
| opnds.push_back(OpndWithPriority(opnd, getPriority(opnd), negated)); |
| } |
| |
| void |
| Reassociate::addMulAssoc(StlDeque<OpndWithPriority> &opnds, |
| bool negated, |
| Type* type, Opnd* opnd) |
| { |
| Inst *inst = opnd->getInst(); |
| if (inst->getType() == type->tag && opnds.size() < maxReassocDepth) { |
| switch(inst->getOpcode()) { |
| case Op_Mul: |
| if (inst->getOverflowModifier() != Overflow_None) break; |
| addMulAssoc(opnds, negated, type, inst->getSrc(0)); |
| addMulAssoc(opnds, negated, type, inst->getSrc(1)); |
| return; |
| case Op_Copy: |
| addAddAssoc(opnds, negated, type, inst->getSrc(0)); |
| return; |
| default: |
| break; |
| } |
| } |
| opnds.push_back(OpndWithPriority(opnd, getPriority(opnd), negated)); |
| } |
| |
| void |
| Reassociate::addAddOffsetAssoc(StlDeque<OpndWithPriority> &opnds, |
| bool compressed, |
| Type* type, Opnd* opnd) |
| { |
| Inst *inst = opnd->getInst(); |
| if (inst->getType() == type->tag && opnds.size() < maxReassocDepth) { |
| switch(inst->getOpcode()) { |
| case Op_AddOffset: |
| addAddOffsetAssoc(opnds, compressed, type, inst->getSrc(0)); |
| addAddOffsetAssoc(opnds, compressed, type, inst->getSrc(1)); |
| return; |
| case Op_AddOffsetPlusHeapbase: |
| addAddOffsetAssoc(opnds, compressed, type, inst->getSrc(0)); |
| addAddOffsetAssoc(opnds, compressed, type, inst->getSrc(1)); |
| return; |
| case Op_UncompressRef: |
| case Op_CompressRef: |
| case Op_Copy: |
| case Op_LdFieldOffset: |
| case Op_LdFieldOffsetPlusHeapbase: |
| case Op_LdArrayBaseOffsetPlusHeapbase: |
| case Op_LdArrayLenOffset: |
| case Op_LdArrayLenOffsetPlusHeapbase: |
| case Op_AddScaledIndex: |
| case Op_TauArrayLen: |
| default: |
| break; |
| } |
| } |
| opnds.push_back(OpndWithPriority(opnd, getPriority(opnd), compressed)); |
| } |
| |
| |
| // maybe this stuff should be in simplifier. |
| Opnd* |
| Reassociate::simplifyReassociatedAdd(Type *type, |
| StlDeque<OpndWithPriority> &opnds) |
| { |
| typedef StlDeque<OpndWithPriority> VectType; |
| |
| ::std::sort(opnds.begin(), opnds.end()); |
| |
| if (Log::isEnabled()) { |
| VectType::iterator |
| iter = opnds.begin(), |
| end = opnds.end(); |
| Log::out() << "BEGIN simplifyReassociatedAdd: "; |
| for ( ; iter != end ; iter++) { |
| OpndWithPriority &owd = *iter; |
| Log::out() << (owd.negate ? "-" : "+") << "("; |
| owd.opnd->print(Log::out()); |
| Log::out() << ", " << (int)owd.priority << ") "; |
| } |
| Log::out() << ::std::endl; |
| } |
| |
| // algorithm: |
| // first, if all opnds are negated, wantToNegate=true |
| // while (opnds.size > 1) |
| // if (opnds[0].negate != opnds[1].negate) { |
| // if (opnds[0].negate) |
| // newop = Op_Sub(opnds[1], opnds[0]); |
| // else |
| // newop = Op_Sub(opnds[0], opnds[1]); |
| // else |
| // if (wantToNegate && (computePriority(costofNeg, opnds[0].priority) < opnds[1].priority) |
| // newop = Op_Sub(Op_Neg(opnds[0]), opnds[1]) |
| // wantToNegate = false |
| // else |
| // newop = Op_Add(opnds[0], opnds[1]); |
| |
| VectType::size_type size = opnds.size(); |
| |
| if (size < 2) { return 0; } |
| |
| bool wantToNegate = true; |
| VectType::iterator |
| iter = opnds.begin(), |
| end = opnds.end(); |
| for ( ; iter != end; ++iter) { |
| if (!(*iter).negate) wantToNegate=false; |
| } |
| |
| if ((!wantToNegate) && (size < 3)) { return 0; } |
| |
| while (size > 1) { |
| OpndWithPriority owd0 = opnds[0]; |
| OpndWithPriority owd1 = opnds[1]; |
| opnds.pop_front(); |
| opnds.pop_front(); |
| size -= 2; |
| Opnd *opnd0 = owd0.opnd; |
| Opnd *opnd1 = owd1.opnd; |
| Opnd *newOpnd = 0; |
| bool newNegated = 0; |
| U_32 priority0 = owd0.priority; |
| U_32 priority1 = owd1.priority; |
| const char *debug_op = ""; |
| bool debug_swapped = false; |
| U_32 newPriority = 0; |
| if (owd0.negate != owd1.negate) { |
| if (owd0.negate) { |
| newOpnd = theSimp->genSub(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| opnd1, opnd0)->getDst(); |
| newPriority = computePriority(costOfSub, priority1, priority0); |
| newNegated = false; |
| debug_swapped = true; |
| } else { |
| newOpnd = theSimp->genSub(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| opnd0, opnd1)->getDst(); |
| newPriority = computePriority(costOfSub, priority0, priority1); |
| newNegated = false; |
| } |
| debug_op = "sub"; |
| } else { |
| if (wantToNegate && (computePriority(costOfNeg, priority0) < priority1)) { |
| // we can effort to negate here, negate deeper argument |
| Opnd *negated = theSimp->genNeg(type, opnd0)->getDst(); |
| newOpnd = theSimp->genSub(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| negated, opnd1)->getDst(); |
| newNegated = false; |
| wantToNegate = false; |
| newPriority = computePriority(costOfSub, computePriority(costOfNeg, priority0), priority1); |
| debug_op = "negsub"; |
| } else { |
| newNegated = owd0.negate; |
| newOpnd = theSimp->genAdd(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| opnd0, opnd1)->getDst(); |
| newPriority = computePriority(costOfAdd, priority0, priority1); |
| debug_op = "add"; |
| } |
| } |
| OpndWithPriority newelt(newOpnd, newPriority, newNegated); |
| opnds.push_front(newelt); |
| size += 1; |
| if (Log::isEnabled()) { |
| Log::out() << " new " << (newNegated ? "-" : "+") << "("; |
| newOpnd->print(Log::out()); |
| Log::out() << ", " << (int) newPriority << ") = " << debug_op << "("; |
| if (debug_swapped) { |
| opnd1->print(Log::out()); |
| } else { |
| opnd0->print(Log::out()); |
| } |
| Log::out() << ", "; |
| if (debug_swapped) { |
| opnd0->print(Log::out()); |
| } else { |
| opnd1->print(Log::out()); |
| } |
| Log::out() << ")" << ::std::endl; |
| } |
| } |
| |
| assert(size == 1); |
| Opnd *res = opnds[0].opnd; |
| if (wantToNegate) { |
| assert(opnds[0].negate); |
| // need to neg result |
| Opnd *newres = theSimp->genNeg(type, res)->getDst(); |
| if (Log::isEnabled()) { |
| Log::out() << " negated: "; |
| newres->print(Log::out()); |
| Log::out() << " = neg("; |
| res->print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| res = newres; |
| } else { |
| assert(!opnds[0].negate); |
| } |
| if (Log::isEnabled()) { |
| Log::out() << "FINISHED simplifyReassociatedAdd: "; |
| res->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| return res; |
| } |
| |
| Opnd* |
| Reassociate::simplifyReassociatedMul(Type *type, |
| StlDeque<OpndWithPriority> &opnds) |
| { |
| typedef StlDeque<OpndWithPriority> VectType; |
| if (Log::isEnabled()) { |
| VectType::iterator |
| iter = opnds.begin(), |
| end = opnds.end(); |
| Log::out() << "BEGIN simplifyReassociatedMul: "; |
| for ( ; iter != end ; iter++) { |
| OpndWithPriority &owd = *iter; |
| Log::out() << "("; |
| owd.opnd->print(Log::out()); |
| Log::out() << ", " << (int)owd.priority << ") "; |
| } |
| Log::out() << ::std::endl; |
| } |
| |
| ::std::sort(opnds.begin(), opnds.end()); |
| |
| // general algorithm: for priority reduction, we just repeatedly reduce |
| // 2 highest-priority operands |
| |
| VectType::size_type opndsize = opnds.size(); |
| while (opndsize > 1) { |
| OpndWithPriority owd0 = opnds[0]; |
| OpndWithPriority owd1 = opnds[1]; |
| Opnd *opnd0 = owd0.opnd; |
| U_32 priority0 = owd0.priority; |
| bool neg0 = owd0.negate; |
| Opnd *opnd1 = owd1.opnd; |
| U_32 priority1 = owd1.priority; |
| bool neg1 = owd1.negate; |
| |
| if ((opnd0 == opnd1) && (opndsize > 3) |
| && (opnds[2].opnd == opnds[3].opnd)) { |
| // we have (a * a * b * b) |
| // convert to (a*b)*(a*b) |
| |
| OpndWithPriority owd2 = opnds[2]; |
| OpndWithPriority owd3 = opnds[3]; |
| Opnd *opnd2 = owd2.opnd; |
| U_32 priority2 = owd2.priority; |
| |
| Opnd *newOpnd0 = theSimp->genMul(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| opnd0, opnd2)->getDst(); |
| Opnd *newOpnd1 = theSimp->genMul(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| newOpnd0, newOpnd0)->getDst(); |
| opnds.pop_front(); |
| opnds.pop_front(); |
| opnds.pop_front(); |
| U_32 priorityNew0 = computePriority(costOfMul, priority0, |
| priority2); |
| U_32 priorityNew1 = computePriority(costOfMul, |
| priorityNew0, |
| priorityNew0); |
| OpndWithPriority newelt(newOpnd1, priorityNew1, |
| false // negs negate each other |
| ); |
| |
| if (Log::isEnabled()) { |
| Log::out() << " new ("; |
| newOpnd1->print(Log::out()); |
| Log::out() << ", " << (int) priorityNew1 << ") = sqr(mul("; |
| opnd0->print(Log::out()); |
| Log::out() << ", " << (int) priority0 << "), ("; |
| opnd2->print(Log::out()); |
| Log::out() << ", " << (int) priority2 << "))" << ::std::endl; |
| } |
| |
| opnds[0] = newelt; |
| opndsize -= 3; |
| U_32 i = 1; |
| while (i < opndsize) { |
| if (opnds[i].priority < priorityNew1) { |
| opnds[i-1] = opnds[i]; |
| opnds[i] = newelt; |
| } else { |
| break; |
| } |
| } |
| } else { |
| |
| Opnd *newOpnd = theSimp->genMul(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| opnd0, opnd1)->getDst(); |
| opnds.pop_front(); |
| U_32 priority = computePriority(costOfMul, priority0, priority1); |
| OpndWithPriority newelt(newOpnd, priority, neg0 ^ neg1); |
| |
| if (Log::isEnabled()) { |
| Log::out() << " new ("; |
| newOpnd->print(Log::out()); |
| Log::out() << ", " << (int) priority << ") = mul(("; |
| opnd0->print(Log::out()); |
| Log::out() << ", " << (int) priority0 << "), ("; |
| opnd1->print(Log::out()); |
| Log::out() << ", " << (int) priority1 << "))" << ::std::endl; |
| } |
| |
| opnds[0] = newelt; |
| opndsize -= 1; |
| U_32 i = 1; |
| while (i < opndsize) { |
| if (opnds[i].priority < priority) { |
| opnds[i-1] = opnds[i]; |
| opnds[i] = newelt; |
| } else { |
| break; |
| } |
| } |
| } |
| } |
| if (Log::isEnabled()) { |
| VectType::iterator |
| iter = opnds.begin(), |
| end = opnds.end(); |
| Log::out() << "FINISHED simplifyReassociatedMul: "; |
| opnds[0].opnd->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| return opnds[0].opnd; |
| } |
| |
| Opnd* |
| Reassociate::simplifyReassociatedAddOffset(Type *type, |
| StlDeque<OpndWithPriority> &opnds) |
| { |
| typedef StlDeque<OpndWithPriority> VectType; |
| |
| ::std::sort(opnds.begin(), opnds.end()); |
| |
| if (Log::isEnabled()) { |
| VectType::iterator |
| iter = opnds.begin(), |
| end = opnds.end(); |
| Log::out() << "BEGIN simplifyReassociatedAddOffset: "; |
| for ( ; iter != end ; iter++) { |
| OpndWithPriority &owd = *iter; |
| Log::out() << (owd.negate ? "-" : "+") << "("; |
| owd.opnd->print(Log::out()); |
| Log::out() << ", " << (int)owd.priority << ") "; |
| } |
| Log::out() << ::std::endl; |
| } |
| |
| assert(0); |
| |
| // algorithm: |
| // first, if all opnds are negated, wantToNegate=true |
| // while (opnds.size > 1) |
| // if (opnds[0].negate != opnds[1].negate) { |
| // if (opnds[0].negate) |
| // newop = Op_Sub(opnds[1], opnds[0]); |
| // else |
| // newop = Op_Sub(opnds[0], opnds[1]); |
| // else |
| // if (wantToNegate && (computePriority(costofNeg, opnds[0].priority) < opnds[1].priority) |
| // newop = Op_Sub(Op_Neg(opnds[0]), opnds[1]) |
| // wantToNegate = false |
| // else |
| // newop = Op_Add(opnds[0], opnds[1]); |
| |
| VectType::size_type size = opnds.size(); |
| |
| if (size < 2) { return 0; } // don't rewrite, no point |
| |
| bool wantToNegate = true; |
| VectType::iterator |
| iter = opnds.begin(), |
| end = opnds.end(); |
| for ( ; iter != end; ++iter) { |
| if (!(*iter).negate) wantToNegate=false; |
| } |
| |
| if ((!wantToNegate) && (size < 3)) { return 0; } // don't bother |
| |
| while (size > 1) { |
| OpndWithPriority owd0 = opnds[0]; |
| OpndWithPriority owd1 = opnds[1]; |
| opnds.pop_front(); |
| opnds.pop_front(); |
| size -= 2; |
| Opnd *opnd0 = owd0.opnd; |
| Opnd *opnd1 = owd1.opnd; |
| Opnd *newOpnd = 0; |
| bool newNegated = 0; |
| U_32 priority0 = owd0.priority; |
| U_32 priority1 = owd1.priority; |
| const char *debug_op = ""; |
| bool debug_swapped = false; |
| U_32 newPriority = 0; |
| if (owd0.negate != owd1.negate) { |
| if (owd0.negate) { |
| newOpnd = theSimp->genSub(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| opnd1, opnd0)->getDst(); |
| newPriority = computePriority(costOfSub, priority1, priority0); |
| newNegated = false; |
| debug_swapped = true; |
| } else { |
| newOpnd = theSimp->genSub(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| opnd0, opnd1)->getDst(); |
| newPriority = computePriority(costOfSub, priority0, priority1); |
| newNegated = false; |
| } |
| debug_op = "sub"; |
| } else { |
| if (wantToNegate && (computePriority(costOfNeg, priority0) < priority1)) { |
| // we can effort to negate here, negate deeper arguments |
| Opnd *negated = theSimp->genNeg(type, opnd0)->getDst(); |
| newOpnd = theSimp->genSub(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| negated, opnd1)->getDst(); |
| newNegated = false; |
| wantToNegate = false; |
| newPriority = computePriority(costOfSub, computePriority(costOfNeg, priority0), priority1); |
| debug_op = "negsub"; |
| } else { |
| newNegated = owd0.negate; |
| newOpnd = theSimp->genAdd(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), |
| opnd0, opnd1)->getDst(); |
| newPriority = computePriority(costOfAdd, priority0, priority1); |
| debug_op = "add"; |
| } |
| } |
| OpndWithPriority newelt(newOpnd, newPriority, newNegated); |
| opnds.push_front(newelt); |
| size += 1; |
| if (Log::isEnabled()) { |
| Log::out() << " new " << (newNegated ? "-" : "+") << "("; |
| newOpnd->print(Log::out()); |
| Log::out() << ", " << (int) newPriority << ") = " << debug_op << "("; |
| if (debug_swapped) { |
| opnd1->print(Log::out()); |
| } else { |
| opnd0->print(Log::out()); |
| } |
| Log::out() << ", "; |
| if (debug_swapped) { |
| opnd0->print(Log::out()); |
| } else { |
| opnd1->print(Log::out()); |
| } |
| Log::out() << ")" << ::std::endl; |
| } |
| } |
| |
| assert(size == 1); |
| Opnd *res = opnds[0].opnd; |
| if (wantToNegate) { |
| assert(opnds[0].negate); |
| // need to neg result |
| Opnd *newres = theSimp->genNeg(type, res)->getDst(); |
| if (Log::isEnabled()) { |
| Log::out() << " negated: "; |
| newres->print(Log::out()); |
| Log::out() << " = neg("; |
| res->print(Log::out()); |
| Log::out() << ")" << ::std::endl; |
| } |
| res = newres; |
| } else { |
| assert(!opnds[0].negate); |
| } |
| if (Log::isEnabled()) { |
| Log::out() << "FINISHED simplifyReassociatedAdd: "; |
| res->print(Log::out()); |
| Log::out() << ::std::endl; |
| } |
| return res; |
| } |
| |
| |
| // checks for and performs possible re-associations of add |
| // makes no assumptions about types |
| Opnd* |
| Simplifier::simplifyAddViaReassociation2(Type* type, Opnd* src1, Opnd* src2) { |
| assert(theReassociate); |
| StlDeque<OpndWithPriority> opnds(theReassociate->mm); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "simplifyAddViaReassociation2 Add("; |
| src1->print(Log::out()); |
| Log::out() << ", "; |
| src2->print(Log::out()); |
| Log::out() << "): " << ::std::endl; |
| } |
| |
| theReassociate->addAddAssoc(opnds, false, type, src1); |
| theReassociate->addAddAssoc(opnds, false, type, src2); |
| return theReassociate->simplifyReassociatedAdd(type, opnds); |
| } |
| |
| // checks for and performs possible re-associations of neg |
| // makes no assumptions about types |
| Opnd* |
| Simplifier::simplifyNegViaReassociation2(Type* type, Opnd* src1) { |
| assert(theReassociate); |
| StlDeque<OpndWithPriority> opnds(theReassociate->mm); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "simplifyNegViaReassociation2 Neg("; |
| src1->print(Log::out()); |
| Log::out() << "): " << ::std::endl; |
| } |
| |
| theReassociate->addAddAssoc(opnds, true, type, src1); |
| return theReassociate->simplifyReassociatedAdd(type, opnds); |
| } |
| |
| // checks for and performs possible re-associations of neg |
| // makes no assumptions about types |
| Opnd* |
| Simplifier::simplifySubViaReassociation2(Type* type, Opnd* src1, Opnd *src2) { |
| assert(theReassociate); |
| StlDeque<OpndWithPriority> opnds(theReassociate->mm); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "simplifySubViaReassociation2 Sub("; |
| src1->print(Log::out()); |
| Log::out() << ", "; |
| src2->print(Log::out()); |
| Log::out() << "): " << ::std::endl; |
| } |
| |
| theReassociate->addAddAssoc(opnds, false, type, src1); |
| theReassociate->addAddAssoc(opnds, true, type, src2); |
| return theReassociate->simplifyReassociatedAdd(type, opnds); |
| } |
| |
| // checks for and performs possible re-associations of add |
| // makes no assumptions about types |
| Opnd* |
| Simplifier::simplifyMulViaReassociation2(Type* type, Opnd* src1, Opnd* src2) { |
| assert(theReassociate); |
| StlDeque<OpndWithPriority> opnds(theReassociate->mm); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "simplifyMulViaReassociation2 Mul("; |
| src1->print(Log::out()); |
| Log::out() << ", "; |
| src2->print(Log::out()); |
| Log::out() << "): " << ::std::endl; |
| } |
| |
| theReassociate->addMulAssoc(opnds, false, type, src1); |
| theReassociate->addMulAssoc(opnds, false, type, src2); |
| |
| return theReassociate->simplifyReassociatedMul(type, opnds); |
| } |
| |
| // checks for and performs possible re-associations of addOffset |
| Opnd* |
| Simplifier::simplifyAddOffsetViaReassociation(Opnd* uncompBase, |
| Opnd* offset) { |
| assert(theReassociate); |
| StlDeque<OpndWithPriority> opnds(theReassociate->mm); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "simplifyAddOffsetViaReassociation AddOffset("; |
| uncompBase->print(Log::out()); |
| Log::out() << ", "; |
| offset->print(Log::out()); |
| Log::out() << "): " << ::std::endl; |
| } |
| |
| theReassociate->addAddOffsetAssoc(opnds, false, uncompBase->getType(), uncompBase); |
| theReassociate->addAddOffsetAssoc(opnds, false, uncompBase->getType(), offset); |
| return theReassociate->simplifyReassociatedAddOffset(uncompBase->getType(), opnds); |
| } |
| |
| // checks for and performs possible re-associations of addOffsetPlusHeapbase |
| Opnd* |
| Simplifier::simplifyAddOffsetPlusHeapbaseViaReassociation(Opnd* compBase, |
| Opnd* offsetPlusHeapbase) { |
| assert(theReassociate); |
| StlDeque<OpndWithPriority> opnds(theReassociate->mm); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "simplifyAddViaReassociation2 Add("; |
| compBase->print(Log::out()); |
| Log::out() << ", "; |
| offsetPlusHeapbase->print(Log::out()); |
| Log::out() << "): " << ::std::endl; |
| } |
| |
| Type *type = irManager.getTypeManager().uncompressType(compBase->getType()); |
| theReassociate->addAddOffsetAssoc(opnds, false, type, compBase); |
| theReassociate->addAddOffsetAssoc(opnds, false, type, offsetPlusHeapbase); |
| return theReassociate->simplifyReassociatedAddOffset(type, opnds); |
| } |
| |
| |
| } //namespace Jitrino |
