| /* |
| * 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, Mikhail Y. Fursov |
| */ |
| |
| #include "Ia32CodeLayoutTopDown.h" |
| #include "Ia32IRManager.h" |
| #include "Log.h" |
| #include "Ia32Printer.h" |
| namespace Jitrino |
| { |
| namespace Ia32 { |
| /** |
| * Class to perform top-down block layout. |
| * The layout algorithm is similar to the one described in the paper |
| * "Profile Guided Code Positioning" by Hansen & Pettis. |
| */ |
| |
| TopDownLayout::TopDownLayout(IRManager* irm) |
| : Linearizer(irm), |
| memManager("ia32::topdown_layout"), |
| lastBlk(NULL), |
| neighboursBlocks(memManager), |
| blockInfos(memManager, irm->getFlowGraph()->getMaxNodeId(), NULL) |
| { |
| const Nodes& nodes = irManager->getFlowGraph()->getNodes(); |
| for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) { |
| Node * node=*it; |
| if (node->isBlockNode()){ |
| TopDownLayoutBlockInfo* info = new (memManager) TopDownLayoutBlockInfo(); |
| info->block = (BasicBlock*)node; |
| blockInfos[node->getId()]= info; |
| } |
| } |
| } |
| |
| // Do complete top down code layout |
| void TopDownLayout::linearizeCfgImpl() { |
| assert(irManager->getFlowGraph()->isEdgeProfileConsistent()); |
| BasicBlock * blk; |
| |
| lastBlk = NULL; |
| |
| // Check that nodes have no layout successors set |
| #ifdef _DEBUG |
| const Nodes& postOrderNodes = irManager->getFlowGraph()->getNodesPostOrder(); |
| for (Nodes::const_iterator it = postOrderNodes.begin(), end = postOrderNodes.end(); it!=end; ++it) { |
| Node* node = *it; |
| if (node->isBlockNode()){ |
| assert(((BasicBlock *)node)->getLayoutSucc()==NULL); |
| } |
| } |
| #endif |
| |
| while ((blk = pickLayoutCandidate()) != NULL) { |
| layoutBlock(blk); |
| } |
| } |
| |
| |
| |
| |
| |
| |
| // Layout "blk" after "lastBlk". Do all bookkeeping and branch updates as needed |
| void TopDownLayout::layoutBlock(BasicBlock *blk) { |
| TopDownLayoutBlockInfo* bInfo = blockInfos[blk->getId()]; |
| assert(!bInfo->isLayouted()); |
| if (Log::isEnabled()) { |
| Log::out() << "layoutBlock("; |
| IRPrinter::printNodeName(Log::out(), blk); |
| Log::out() << ")" << std::endl; |
| } |
| // Remove the block from the localityMap if it is there |
| if (bInfo->isLayoutNeighbour()) { |
| neighboursBlocks.erase(bInfo); |
| } |
| bInfo->state = TopDownLayoutBlockInfo::LAYOUTED; |
| |
| if (lastBlk) { |
| lastBlk->setLayoutSucc(blk); |
| } else { |
| // Check our assumption that the first block laid-out is the entry block. |
| assert(blk== irManager->getFlowGraph()->getEntryNode()); |
| } |
| lastBlk = blk; |
| } |
| |
| |
| |
| // Pick and return the next block to be laid-out |
| #define PROB_SIMILAR_FACTOR 0.9 |
| |
| BasicBlock * TopDownLayout::pickLayoutCandidate() { |
| if (lastBlk == NULL) { |
| // Layout the entry block |
| return (BasicBlock*)irManager->getFlowGraph()->getEntryNode(); |
| } |
| // Return most likely successor of lastBlk if it has not already been placed |
| // and if branch inversion is either not needed or is possible |
| // (i.e. predicate is available). Given two almost equally likely |
| // successors, pick the one that is not a Join block. This will help |
| // reduce taken branches. |
| Edge *bestEdge = NULL; |
| const Edges& outEdges=lastBlk->getOutEdges(); |
| for (Edges::const_iterator ite = outEdges.begin(), ende = outEdges.end(); ite!=ende; ++ite) { |
| Edge* edge = *ite; |
| Node *succ = edge->getTargetNode(); |
| if (!succ->isBlockNode()) { |
| continue; |
| } |
| TopDownLayoutBlockInfo* info = blockInfos[succ->getId()]; |
| if (info->isLayouted() ) { |
| continue; |
| } |
| if (!edge->isFalseEdge() && !canEdgeBeMadeToFallThrough(edge)) { |
| continue; |
| } |
| if (bestEdge == NULL) { |
| bestEdge = edge; |
| } |
| double bestEdgeWeight = bestEdge->getEdgeProb(); |
| double edgeWeight = edge->getEdgeProb(); |
| |
| if ( edgeWeight > bestEdgeWeight || (edgeWeight >= bestEdgeWeight * PROB_SIMILAR_FACTOR |
| && edge->getTargetNode()->getInDegree() == 1 && bestEdge->getTargetNode()->getInDegree() > 1)) |
| { |
| bestEdge = edge; |
| } |
| } |
| |
| // Before returning or choosing a block from the connectivity map, update |
| // the layoutValue information to successors not chosen or already laid out. |
| if (bestEdge) { |
| BasicBlock* headBlock = (BasicBlock*)bestEdge->getTargetNode(); |
| processSuccLayoutValue(lastBlk, headBlock); |
| return headBlock; |
| } |
| |
| processSuccLayoutValue(lastBlk, NULL); |
| |
| #if _DEBUG |
| // Find node with the greatest layoutValue in the connectedBlkMap |
| // Check assumption that the iterator accesses map elements in ordered fashion |
| const TopDownLayoutBlockInfo* prevInfo = NULL; |
| for (SortedBlockInfoSet::iterator it = neighboursBlocks.begin(), end = neighboursBlocks.end(); it!=end; ++it) { |
| TopDownLayoutBlockInfo *bInfo = *it; |
| assert(prevInfo == NULL || TopDownLayoutBlockInfo::less(bInfo, prevInfo)); |
| prevInfo = bInfo; |
| } |
| #endif |
| if (Log::isEnabled()) { |
| printConnectedBlkMap(Log::out()); |
| } |
| |
| if (neighboursBlocks.empty()) { |
| return NULL; |
| } |
| |
| TopDownLayoutBlockInfo* info = *neighboursBlocks.begin(); |
| BasicBlock * locBlk = info->block; |
| if (Log::isEnabled()) { |
| Log::out() << "Picking "; |
| IRPrinter::printNodeName(Log::out(), locBlk); |
| Log::out() << " " << info->layoutValue<< ::std::endl; |
| } |
| assert(info->isLayoutNeighbour()); |
| return locBlk; |
| } |
| |
| |
| // Update layoutValue information for all successors of node that have not yet been laid out. |
| // If a successor is a dispatch node, recursively process its successors, since |
| // dispatch nodes are not being laid out. |
| void TopDownLayout::processSuccLayoutValue(Node *node, BasicBlock * layoutSucc) { |
| const Edges& outEdges = node->getOutEdges(); |
| for (Edges::const_iterator ite = outEdges.begin(), ende = outEdges.end(); ite!=ende; ++ite) { |
| Edge* edge = *ite; |
| Node *succ = edge->getTargetNode(); |
| if (succ->isDispatchNode()) { |
| processSuccLayoutValue(succ, layoutSucc); |
| } else if (succ->isBlockNode()) { |
| TopDownLayoutBlockInfo* succInfo = blockInfos[succ->getId()]; |
| if (succ != layoutSucc && !succInfo->isLayouted()) { |
| if (succInfo->isLayoutNeighbour()) { //remove from sorted map and insert latter to sort again. |
| neighboursBlocks.erase(succInfo); |
| } |
| succInfo->layoutValue+=node->getExecCount() * edge->getEdgeProb(); |
| succInfo->state = TopDownLayoutBlockInfo::LAYOUT_NEIGHBOUR; |
| neighboursBlocks.insert(succInfo); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "Block "; |
| IRPrinter::printNodeName(Log::out(), succInfo->block); |
| Log::out() << " is in neighbors set." << std::endl; |
| } |
| } |
| } |
| } |
| } |
| |
| |
| // |
| // Print the contents of the connectivity map |
| // |
| void TopDownLayout::printConnectedBlkMap(::std::ostream & os) { |
| os << "Neighbors set contents: "; |
| for (SortedBlockInfoSet::iterator it = neighboursBlocks.begin(), end = neighboursBlocks.end(); it != end; ++it) { |
| TopDownLayoutBlockInfo* info= *it; |
| IRPrinter::printNodeName(os, info->block); |
| os << " " << info->layoutValue << ::std::endl; |
| } |
| } |
| |
| } |
| } |
