| /* |
| * 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, Konstantin M. Anisimov, Igor V. Chebykin |
| * |
| */ |
| |
| #include "IpfLiveAnalyzer.h" |
| #include "IpfIrPrinter.h" |
| #include "IpfOpndManager.h" |
| |
| namespace Jitrino { |
| namespace IPF { |
| |
| //========================================================================================// |
| // QpNode |
| //========================================================================================// |
| |
| QpNode::QpNode(QpNode *predNode, QpMask nodeMask) : |
| predNode(predNode), |
| compNode(NULL), |
| nodeMask(nodeMask), |
| compMask(0), |
| liveMask(0) { |
| |
| QpNode *qpNode = predNode; |
| while (qpNode != NULL) { // iterate through all predecessors of the node |
| qpNode->orNodeMask(nodeMask); // add bits of this nodeMask in predecessor's nodeMasks |
| qpNode = qpNode->getPredNode(); // get next predecessor |
| } |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // make mask of all predicate spaces interfering with current one. These are all spaces |
| // except complementing ones |
| |
| void QpNode::initLiveMask() { |
| |
| QpNode *qpNode = this; |
| liveMask = 0; |
| while (qpNode != NULL) { |
| QpMask mask = qpNode->getCompMask(); // get nodeMask of complemening to current space |
| if (mask != MAX_QP_MASK) liveMask |= mask; // if there is complementing space (is not MAX_QP_MASK) - add masks |
| qpNode = qpNode->getPredNode(); // get next predecessor |
| } // |
| liveMask = ~liveMask; // this qpNode interfere with all others except complementing ones |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // if qpNode has complement node - get its nodeMask (just to speed up "getCompMask" method) |
| // else - set all ones in compMask |
| |
| void QpNode::initCompMask() { |
| |
| if (compNode == NULL) compMask = MAX_QP_MASK; |
| else compMask = compNode->getNodeMask(); |
| } |
| |
| //========================================================================================// |
| // QpTree |
| //========================================================================================// |
| |
| QpTree::QpTree(Cfg &cfg) : |
| cfg(cfg), |
| mm(cfg.getMM()), |
| qpMap(mm), |
| slot(0), |
| p0(cfg.getOpndManager()->getP0()) { |
| |
| qpMap.insert( make_pair(p0, new(mm) QpNode(NULL, MAX_QP_MASK)) ); // make root qpNode |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // build qpMap determining qp->qpNode relations. If qp is defined several times - the tree |
| // contains several entryes corresponding to the qp. |
| |
| void QpTree::makeQpTree(InstVector &insts) { |
| |
| IPF_ASSERT(qpMap.size() == 1); |
| |
| slot = 1; // init slot (position in mask) |
| for (InstVector::iterator it=insts.begin(); it!=insts.end(); it++) { |
| Inst *inst = *it; // iterate insts |
| |
| if (isDefOnePred(inst)) { // if inst defs one predicate opnd |
| OpndVector &opnds = inst->getOpnds(); // get opnds of the inst |
| QpNode *qpNode = findQpNode(opnds[0]); // inst qp is predecessor for predicates defined in the inst |
| makeQpNode(qpNode, opnds[2]); // make qpNode for the predicate opnd (it is always second one) |
| continue; |
| } |
| |
| if (isDefTwoPreds(inst)) { // if inst defs two predicate opnds |
| OpndVector &opnds = inst->getOpnds(); // get opnds of the inst |
| QpNode *qpNode = findQpNode(opnds[0]); // inst qp is predecessor for predicates defined in the inst |
| QpNode *p1Node = makeQpNode(qpNode, opnds[1]); // make qpNode for first predicate opnd |
| QpNode *p2Node = makeQpNode(qpNode, opnds[2]); // make qpNode for second predicate opnd |
| |
| if (isDefComps(inst) == false) continue; // inst does not define mutually complemen predicates - continue |
| if (p1Node != NULL) p1Node->setCompNode(p2Node); // p2Node complements p1Node |
| if (p2Node != NULL) p2Node->setCompNode(p1Node); // p1Node complements p2Node |
| } |
| } |
| |
| for (QpMap::iterator it=qpMap.begin(); it!=qpMap.end(); it++) { |
| QpNode *qpNode = it->second; // iterate all qpNodes in the tree |
| qpNode->initCompMask(); // set comp mask (to speed up getCompMask) |
| } |
| |
| for (QpMap::iterator it=qpMap.begin(); it!=qpMap.end(); it++) { |
| QpNode *qpNode = it->second; // iterate all qpNodes in the tree |
| qpNode->initLiveMask(); // set live masks (predicate spaces which do not complement) |
| } |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // find qpNode corresponding to "qp" from qpMap. There are can be several nodes |
| // corresponding to one qp. We should return least recent inserted one |
| |
| QpNode* QpTree::findQpNode(Opnd *qp) { |
| |
| QpMap::iterator it = qpMap.upper_bound(qp); |
| return (--it)->second; |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // remove qpNode corresponding to "qp" from qpMap. There are can be several nodes |
| // corresponding to one qp. We should remove least recent inserted one |
| |
| void QpTree::removeQpNode(Opnd *qp) { |
| |
| QpMap::iterator it = qpMap.upper_bound(qp); // find in qpMap last node corresponding to "qp" |
| qpMap.erase(--it); // remove the node from the tree |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| |
| void QpTree::printQpTree() { |
| |
| QpMap::iterator it = qpMap.upper_bound(p0); |
| printQpNode(--it, 0); |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| |
| QpNode* QpTree::makeQpNode(QpNode *predNode, Opnd *qp) { |
| |
| if (qp == p0) return NULL; // node for p0 has been created in constructor |
| slot <<= 1; // get next empty slot (position in mask) |
| QpNode *qpNode = new(mm) QpNode(predNode, slot); // create qpNode |
| qpMap.insert( make_pair(qp, qpNode) ); // insert the qpNode in qpTree |
| return qpNode; |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| |
| void QpTree::printQpNode(QpMap::iterator nodeIt, uint16 level) { |
| |
| QpNode *predNode = nodeIt->second; |
| Opnd *qp = nodeIt->first; |
| IPF_LOG << " " << IrPrinter::toString(predNode); |
| for (uint16 i=0; i<level; i++) IPF_LOG << " "; |
| IPF_LOG << " " << IrPrinter::toString(qp) << endl; |
| |
| for (QpMap::iterator it=qpMap.begin(); it!=qpMap.end(); it++) { |
| QpNode *qpNode = it->second; |
| if (qpNode->getPredNode() != predNode) continue; |
| printQpNode(it, level+1); |
| } |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // return true if the inst defines one pred opnd |
| |
| bool QpTree::isDefOnePred(Inst *inst) { |
| |
| switch (inst->getInstCode()) { |
| case INST_FRCPA : |
| case INST_FPRCPA : |
| case INST_FRSQRTA : |
| case INST_FPRSQRTA : return true; |
| default : return false; |
| } |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // return true if the inst defines two pred opnds |
| |
| bool QpTree::isDefTwoPreds(Inst *inst) { |
| |
| switch (inst->getInstCode()) { |
| case INST_CMP : |
| case INST_CMP4 : |
| case INST_FCMP : |
| case INST_TBIT : |
| case INST_TNAT : |
| case INST_FCLASS : return true; |
| default : return false; |
| } |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // return true if the inst defines two mutually complement preds |
| |
| bool QpTree::isDefComps(Inst *inst) { |
| |
| InstCode instCode = inst->getInstCode(); |
| if (instCode == INST_FCMP || instCode == INST_FCLASS) return true; |
| if (instCode == INST_TBIT || instCode == INST_TNAT) return true; |
| |
| CompVector &comps = inst->getComps(); |
| if (comps.size() < 2) return true; |
| if (comps[1] == CMPLT_CMP_CTYPE_NONE) return true; |
| if (comps[1] == CMPLT_CMP_CTYPE_UNC) return true; |
| return false; |
| } |
| |
| //========================================================================================// |
| // LiveManager |
| //========================================================================================// |
| |
| LiveManager::LiveManager(Cfg &cfg) : |
| cfg(cfg), |
| qpTree(cfg), |
| liveSet(cfg.getMM()) { |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| |
| void LiveManager::init(Node *node) { |
| |
| liveSet.clear(); // clear live set |
| node->mergeOutLiveSets(liveSet); // all opnds alive in successors are alive in current live set |
| |
| for (RegOpndSet::iterator it=liveSet.begin(); it!=liveSet.end(); it++) { |
| RegOpnd *opnd = *it; // |
| opnd->orQpMask(MAX_QP_MASK); // initially opnds alive in all pred spaces |
| } // |
| |
| if (node->getNodeKind() != NODE_BB) return; // if node is not BB - nothing to do |
| qpTree.makeQpTree(((BbNode *)node)->getInsts()); // make qpTree for current BB |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // add opnds used in the inst in liveSet. Or modify opnd's qpMask to reflect use under inst's qp |
| |
| void LiveManager::use(Inst *inst) { |
| |
| OpndVector &opnds = inst->getOpnds(); // get inst's opnds |
| RegOpnd *qp = (RegOpnd *)opnds[0]; // fist opnd is instruction qp |
| QpNode *qpNode = qpTree.findQpNode(qp); // find qpNode corresponding to the qp |
| |
| if (qp->isWritable()) { |
| qp->orQpMask(MAX_QP_MASK); // qp is alive in all pred spaces |
| liveSet.insert(qp); |
| } |
| |
| for (uint16 i=inst->getNumDst()+1; i<opnds.size(); i++) { |
| RegOpnd *opnd = (RegOpnd *)opnds[i]; |
| if (opnd->isWritable() == false) continue; |
| useOpnd(qpNode, opnd); |
| liveSet.insert(opnd); |
| } |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // remove opnds defined in the inst from liveSet. Or modify opnd's qpMask to reflect def |
| // under inst's qp |
| |
| void LiveManager::def(Inst *inst) { |
| |
| OpndVector &opnds = inst->getOpnds(); |
| RegOpnd *qp = (RegOpnd *)opnds[0]; // fist opnd is instruction qp |
| QpNode *qpNode = qpTree.findQpNode(qp); |
| |
| for (uint16 i=1; i<=inst->getNumDst(); i++) { |
| RegOpnd *opnd = (RegOpnd *)opnds[i]; |
| if (opnd->isWritable() == false) continue; |
| if (defOpnd(qpNode, opnd) == false) continue; |
| liveSet.erase(opnd); |
| } |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| |
| QpMask LiveManager::getLiveMask(RegOpnd *opnd) { |
| QpNode *qpNode = qpTree.findQpNode(opnd); |
| return qpNode->getLiveMask(); |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| |
| void LiveManager::useOpnd(QpNode *qpNode, RegOpnd *opnd) { |
| |
| QpMask mask = qpNode->getNodeMask(); // get mask of predicates alive in space of the qpNode |
| opnd->orQpMask(mask); // add mask to current opnd qpMask |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| |
| bool LiveManager::defOpnd(QpNode *qpNode, RegOpnd *opnd) { |
| |
| if (opnd->isQp()) qpTree.removeQpNode(opnd); // if we def predicate opnd - remove corresponding qpNode from qpTree |
| QpMask mask = opnd->getQpMask(); // get mask of pred spaces, the opnd alive in |
| if (mask == 0) return true; // if mask is zero - opnd is dead |
| |
| while ((mask & qpNode->getCompMask())==0) { // while opnd is dead in complement predicate space - propagate def up |
| qpNode = qpNode->getPredNode(); // get predecessor in qpTree |
| } // |
| |
| opnd->andQpMask(~(qpNode->getNodeMask())); // null bits corresponding the successors in opnd's qp mask |
| if (opnd->getQpMask()) return false; // opnd is alive in some predicate spaces |
| else return true; // opnd is dead |
| } |
| |
| } // IPF |
| } // Jitrino |
