| /* |
| * 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 { |
| |
| //========================================================================================// |
| // LiveAnalyzer |
| //========================================================================================// |
| |
| LiveAnalyzer::LiveAnalyzer(Cfg &cfg) : |
| cfg(cfg), |
| mm(cfg.getMM()), |
| workSet(mm), |
| liveManager(cfg), |
| liveSet(liveManager.getLiveSet()), |
| dceFlag(false) { |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| |
| void LiveAnalyzer::analyze() { |
| |
| NodeVector &nodes = cfg.search(SEARCH_POST_ORDER); // get postordered node list |
| for (int16 i=nodes.size()-1; i>=0; i--) { // iterate nodes |
| Node *node = nodes[i]; // |
| node->setVisited(false); // mark node unvisited |
| if (dceFlag == false) node->clearLiveSet(); // clear node's live set |
| workSet.push_back(node); // put node in workSet (reverse order) |
| } |
| |
| while (workSet.size() > 0) { // while there is node to analyze |
| Node *node = workSet.back(); // get last workSet node |
| node->setVisited(true); // mark the node visited |
| workSet.pop_back(); // remove the node from workSet |
| if (analyzeNode(node) == false) { // node's live set has changed - live sets of predecessor need evaluation |
| pushPreds(node); // put predecessors in workSet |
| } |
| } |
| |
| if (VERIFY_ON) verify(); |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| |
| void LiveAnalyzer::dce() { |
| |
| IPF_LOG << endl << " Dead code:" << endl; |
| dceFlag = true; |
| analyze(); |
| dceFlag = false; |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // check if node's liveSets coincide with calculated ones |
| // check if liveSet of Enter node is empty (except inArgs including implicit arg b0) |
| |
| void LiveAnalyzer::verify() { |
| |
| NodeVector &nodes = cfg.search(SEARCH_POST_ORDER); // get nodes postorder |
| |
| for (uint16 i=0; i<nodes.size(); i++) { // iterate it |
| if (analyzeNode(nodes[i]) == false) { // if node's liveSet does not coincide with calculated one |
| IPF_ERR << " node" << nodes[i]->getId() << endl; // throw error message |
| } |
| } |
| |
| RegOpndSet enterLiveSet = cfg.getEnterNode()->getLiveSet(); // get liveSet of Enter node |
| RegOpndVector &inArgs = cfg.getOpndManager()->getInArgs(); // get inArgs |
| for (uint16 i=0; i<inArgs.size(); i++) { // |
| enterLiveSet.erase(inArgs[i]); // remove inArgs from enterLiveSet |
| } // |
| |
| enterLiveSet.erase(cfg.getOpndManager()->getB0()); // remove b0 from enterLiveSet |
| if (enterLiveSet.size() == 0) return; // if enterLiveSet is empty - Ok |
| |
| IPF_ERR << " size " << enterLiveSet.size() << endl; |
| for (RegOpndSet::iterator it=enterLiveSet.begin(); it!=enterLiveSet.end(); it++) { |
| IPF_ERR << " alive opnd on method enter " << IrPrinter::toString(*it) |
| << " " << IrPrinter::toString(cfg.getMethodDesc()) << endl; |
| } |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // recalculate live set for the node |
| // if it has not changed - return true, else - return false |
| |
| bool LiveAnalyzer::analyzeNode(Node *node) { |
| |
| liveManager.init(node); // init LiveManager with current node |
| if (LOG_ON) { |
| IPF_LOG << endl << " Qp Tree for node" << node->getId() << endl; |
| liveManager.printQpTree(); |
| } |
| |
| RegOpndSet &oldLiveSet = node->getLiveSet(); // get current node live set (on node enter) |
| if (node->getNodeKind() != NODE_BB) { // liveSet is not going to change |
| if (oldLiveSet == liveSet) return true; // if live set has not changed - nothing to do |
| node->setLiveSet(liveSet); // set liveSet for the current node |
| return false; // live set of the node has changed |
| } |
| |
| InstVector &insts = ((BbNode *)node)->getInsts(); |
| for(int16 i=insts.size()-1; i>=0; i--) { // iterate through node insts postorder |
| Inst *inst = insts[i]; // |
| if (dceFlag && isInstDead(inst)) { // if dce is activated and inst is dead |
| IPF_LOG << " node" << setw(3) << left << node->getId(); |
| IPF_LOG << IrPrinter::toString(inst) << endl; |
| insts.erase(insts.begin()+i); // remove inst from InstVector of current node |
| liveManager.def(inst); // change liveSet according with inst def |
| } else { // |
| liveManager.def(inst); // change liveSet according with inst def |
| liveManager.use(inst); // change liveSet according with inst use |
| } |
| } |
| |
| if (oldLiveSet == liveSet) return true; // if live set has not changed - nothing to do |
| node->setLiveSet(liveSet); // set liveSet for the current node |
| return false; // live set of the node has changed |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // push all predecessors of the node in workSet (ignore preds which are in workSet already) |
| |
| void LiveAnalyzer::pushPreds(Node *node) { |
| |
| EdgeVector &edges = node->getInEdges(); // get in edges |
| for (uint16 i=0; i<edges.size(); i++) { // iterate |
| Node *pred = edges[i]->getSource(); // get predecessor |
| if (pred->isVisited() == false) continue; // if predecessor is in workSet - ignore |
| workSet.push_back(pred); // push predecessor in workSet |
| pred->setVisited(false); // mark it unvisited |
| } |
| } |
| |
| //----------------------------------------------------------------------------------------// |
| // Check if instruction can be removed from inst vector. |
| // Do not remove instruction having "side effects" (like "call") |
| |
| bool LiveAnalyzer::isInstDead(Inst *inst) { |
| |
| if (inst->isCall()) return false; // "call" inst is never dead |
| if (inst->getInstCode() == INST_ALLOC) return false; // "alloc" inst is never dead |
| |
| uint16 numDst = inst->getNumDst(); // get num of dst opnds |
| if (numDst == 0) return false; // if there is no dst opnds - ignore |
| |
| OpndVector &opnds = inst->getOpnds(); // get inst opnds |
| RegOpnd *qp = (RegOpnd *)opnds[0]; // get qp of the inst |
| QpMask mask = liveManager.getLiveMask(qp); // get mask for this qp space |
| for (uint16 i=1; i<numDst+1; i++) { // iterate dst opnds |
| RegOpnd *dst = (RegOpnd *)opnds[i]; // |
| if (dst->isAlive(mask)) return false; // if dst is alive - inst is alive |
| } |
| return true; // there is no alive dst opnd - inst is dead |
| } |
| |
| } // IPF |
| } // Jitrino |
