110614Skanishk.sugand@arm.com/* 210995Sandreas.sandberg@arm.com * Copyright (c) 2014-2015 ARM Limited 310614Skanishk.sugand@arm.com * All rights reserved 410614Skanishk.sugand@arm.com * 510614Skanishk.sugand@arm.com * The license below extends only to copyright in the software and shall 610614Skanishk.sugand@arm.com * not be construed as granting a license to any other intellectual 710614Skanishk.sugand@arm.com * property including but not limited to intellectual property relating 810614Skanishk.sugand@arm.com * to a hardware implementation of the functionality of the software 910614Skanishk.sugand@arm.com * licensed hereunder. You may use the software subject to the license 1010614Skanishk.sugand@arm.com * terms below provided that you ensure that this notice is replicated 1110614Skanishk.sugand@arm.com * unmodified and in its entirety in all distributions of the software, 1210614Skanishk.sugand@arm.com * modified or unmodified, in source code or in binary form. 1310614Skanishk.sugand@arm.com * 1410614Skanishk.sugand@arm.com * Redistribution and use in source and binary forms, with or without 1510614Skanishk.sugand@arm.com * modification, are permitted provided that the following conditions are 1610614Skanishk.sugand@arm.com * met: redistributions of source code must retain the above copyright 1710614Skanishk.sugand@arm.com * notice, this list of conditions and the following disclaimer; 1810614Skanishk.sugand@arm.com * redistributions in binary form must reproduce the above copyright 1910614Skanishk.sugand@arm.com * notice, this list of conditions and the following disclaimer in the 2010614Skanishk.sugand@arm.com * documentation and/or other materials provided with the distribution; 2110614Skanishk.sugand@arm.com * neither the name of the copyright holders nor the names of its 2210614Skanishk.sugand@arm.com * contributors may be used to endorse or promote products derived from 2310614Skanishk.sugand@arm.com * this software without specific prior written permission. 2410614Skanishk.sugand@arm.com * 2510614Skanishk.sugand@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2610614Skanishk.sugand@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2710614Skanishk.sugand@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2810614Skanishk.sugand@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2910614Skanishk.sugand@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3010614Skanishk.sugand@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3110614Skanishk.sugand@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3210614Skanishk.sugand@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3310614Skanishk.sugand@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3410614Skanishk.sugand@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3510614Skanishk.sugand@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3610614Skanishk.sugand@arm.com * 3710614Skanishk.sugand@arm.com * Authors: Kanishk Sugand 3810614Skanishk.sugand@arm.com */ 3910614Skanishk.sugand@arm.com 4010995Sandreas.sandberg@arm.com#include "mem/stack_dist_calc.hh" 4110995Sandreas.sandberg@arm.com 4210995Sandreas.sandberg@arm.com#include "base/chunk_generator.hh" 4310614Skanishk.sugand@arm.com#include "base/intmath.hh" 4410614Skanishk.sugand@arm.com#include "base/trace.hh" 4510614Skanishk.sugand@arm.com#include "debug/StackDist.hh" 4610614Skanishk.sugand@arm.com 4710995Sandreas.sandberg@arm.comStackDistCalc::StackDistCalc(bool verify_stack) 4810995Sandreas.sandberg@arm.com : index(0), 4910995Sandreas.sandberg@arm.com verifyStack(verify_stack) 5010614Skanishk.sugand@arm.com{ 5110614Skanishk.sugand@arm.com // Instantiate a new root and leaf layer 5210614Skanishk.sugand@arm.com // Map type variable, representing a layer in the tree 5310614Skanishk.sugand@arm.com IndexNodeMap tree_level; 5410614Skanishk.sugand@arm.com 5510614Skanishk.sugand@arm.com // Initialize tree count for leaves 5610614Skanishk.sugand@arm.com nextIndex.push_back(0); 5710614Skanishk.sugand@arm.com 5810614Skanishk.sugand@arm.com // Add the initial leaf layer to the tree 5910614Skanishk.sugand@arm.com tree.push_back(tree_level); 6010614Skanishk.sugand@arm.com 6110614Skanishk.sugand@arm.com // Create a root node. Node type variable in the topmost layer 6210614Skanishk.sugand@arm.com Node* root_node = new Node(); 6310614Skanishk.sugand@arm.com 6410614Skanishk.sugand@arm.com // Initialize tree count for root 6510614Skanishk.sugand@arm.com nextIndex.push_back(1); 6610614Skanishk.sugand@arm.com 6710614Skanishk.sugand@arm.com // Add the empty root layer to the tree 6810614Skanishk.sugand@arm.com tree.push_back(tree_level); 6910614Skanishk.sugand@arm.com 7010614Skanishk.sugand@arm.com // Add the initial root to the tree 7110614Skanishk.sugand@arm.com tree[1][root_node->nodeIndex] = root_node; 7210614Skanishk.sugand@arm.com} 7310614Skanishk.sugand@arm.com 7410614Skanishk.sugand@arm.comStackDistCalc::~StackDistCalc() 7510614Skanishk.sugand@arm.com{ 7610614Skanishk.sugand@arm.com // Walk through each layer and destroy the nodes 7710614Skanishk.sugand@arm.com for (auto& layer : tree) { 7810614Skanishk.sugand@arm.com for (auto& index_node : layer) { 7910614Skanishk.sugand@arm.com // each map entry contains an index and a node 8010614Skanishk.sugand@arm.com delete index_node.second; 8110614Skanishk.sugand@arm.com } 8210614Skanishk.sugand@arm.com // Clear each layer in the tree 8310614Skanishk.sugand@arm.com layer.clear(); 8410614Skanishk.sugand@arm.com } 8510614Skanishk.sugand@arm.com 8610614Skanishk.sugand@arm.com // Clear the tree 8710614Skanishk.sugand@arm.com tree.clear(); 8810614Skanishk.sugand@arm.com aiMap.clear(); 8910614Skanishk.sugand@arm.com nextIndex.clear(); 9010614Skanishk.sugand@arm.com 9110614Skanishk.sugand@arm.com // For verification 9210614Skanishk.sugand@arm.com stack.clear(); 9310614Skanishk.sugand@arm.com} 9410614Skanishk.sugand@arm.com 9510614Skanishk.sugand@arm.com// The updateSum method is a recursive function which updates 9610614Skanishk.sugand@arm.com// the node sums till the root. It also deletes the nodes that 9710614Skanishk.sugand@arm.com// are not used anymore. 9810614Skanishk.sugand@arm.comuint64_t 9910614Skanishk.sugand@arm.comStackDistCalc::updateSum(Node* node, bool from_left, 10010614Skanishk.sugand@arm.com uint64_t sum_from_below, uint64_t level, 10110614Skanishk.sugand@arm.com uint64_t stack_dist, bool discard_node) 10210614Skanishk.sugand@arm.com{ 10310614Skanishk.sugand@arm.com ++level; 10410614Skanishk.sugand@arm.com 10510614Skanishk.sugand@arm.com // Make a copy of the node variables and work on them 10610614Skanishk.sugand@arm.com // as a node may be deleted by this function 10710614Skanishk.sugand@arm.com uint64_t node_sum_l = node->sumLeft; 10810614Skanishk.sugand@arm.com uint64_t node_sum_r = node->sumRight; 10910614Skanishk.sugand@arm.com bool node_left = node->isLeftNode; 11010614Skanishk.sugand@arm.com bool node_discard_left = node->discardLeft; 11110614Skanishk.sugand@arm.com bool node_discard_right = node->discardRight; 11210614Skanishk.sugand@arm.com uint64_t node_n_index = node->nodeIndex; 11310614Skanishk.sugand@arm.com Node* node_parent_ptr = node->parent; 11410614Skanishk.sugand@arm.com 11510614Skanishk.sugand@arm.com // For verification 11610614Skanishk.sugand@arm.com if (verifyStack) { 11710614Skanishk.sugand@arm.com // This sanity check makes sure that the left_sum and 11810614Skanishk.sugand@arm.com // right_sum of the node is not greater than the 11910614Skanishk.sugand@arm.com // maximum possible value given by the leaves below it 12010614Skanishk.sugand@arm.com // for example a node in layer 3 (tree[3]) can at most 12110614Skanishk.sugand@arm.com // have 8 leaves (4 to the left and 4 to the right) 12210614Skanishk.sugand@arm.com // thus left_sum and right_sum should be <= 4 12310614Skanishk.sugand@arm.com panic_if(node_sum_l > (1 << (level - 1)), 12410614Skanishk.sugand@arm.com "Error in sum left of level %ul, node index %ull, " 12510614Skanishk.sugand@arm.com "Sum = %ull \n", level, node_n_index, node_sum_l); 12610614Skanishk.sugand@arm.com 12710614Skanishk.sugand@arm.com panic_if(node_sum_r > (1 << (level - 1)), 12810614Skanishk.sugand@arm.com "Error in sum right of level %ul, node index %ull, " 12910614Skanishk.sugand@arm.com "Sum = %ull \n", level, node_n_index, node_sum_r); 13010614Skanishk.sugand@arm.com } 13110614Skanishk.sugand@arm.com 13210614Skanishk.sugand@arm.com // Update the left sum or the right sum depending on the 13310614Skanishk.sugand@arm.com // from_left flag. Variable stack_dist is updated only 13410614Skanishk.sugand@arm.com // when arriving from Left. 13510614Skanishk.sugand@arm.com if (from_left) { 13610614Skanishk.sugand@arm.com // update sumLeft 13710614Skanishk.sugand@arm.com node_sum_l = sum_from_below; 13810614Skanishk.sugand@arm.com stack_dist += node_sum_r; 13910614Skanishk.sugand@arm.com } else { 14010614Skanishk.sugand@arm.com // update sum_r 14110614Skanishk.sugand@arm.com node_sum_r = sum_from_below; 14210614Skanishk.sugand@arm.com } 14310614Skanishk.sugand@arm.com 14410614Skanishk.sugand@arm.com // sum_from_below == 0 can be a leaf discard operation 14510614Skanishk.sugand@arm.com if (discard_node && !sum_from_below) { 14610614Skanishk.sugand@arm.com if (from_left) 14710614Skanishk.sugand@arm.com node_discard_left = true; 14810614Skanishk.sugand@arm.com else 14910614Skanishk.sugand@arm.com node_discard_right = true; 15010614Skanishk.sugand@arm.com } 15110614Skanishk.sugand@arm.com 15210614Skanishk.sugand@arm.com // Update the node variables with new values 15310614Skanishk.sugand@arm.com node->nodeIndex = node_n_index; 15410614Skanishk.sugand@arm.com node->sumLeft = node_sum_l; 15510614Skanishk.sugand@arm.com node->sumRight = node_sum_r; 15610614Skanishk.sugand@arm.com node->isLeftNode = node_left; 15710614Skanishk.sugand@arm.com node->discardLeft = node_discard_left; 15810614Skanishk.sugand@arm.com node->discardRight = node_discard_right; 15910614Skanishk.sugand@arm.com 16010614Skanishk.sugand@arm.com // Delete the node if it is not required anymore 16110614Skanishk.sugand@arm.com if (node_discard_left && node_discard_right && 16210614Skanishk.sugand@arm.com discard_node && node_parent_ptr && !sum_from_below) { 16310614Skanishk.sugand@arm.com delete node; 16410614Skanishk.sugand@arm.com tree[level].erase(node_n_index); 16510614Skanishk.sugand@arm.com discard_node = true; 16610614Skanishk.sugand@arm.com } else { 16710614Skanishk.sugand@arm.com // propogate discard_node as false upwards if the 16810614Skanishk.sugand@arm.com // above conditions are not met. 16910614Skanishk.sugand@arm.com discard_node = false; 17010614Skanishk.sugand@arm.com } 17110614Skanishk.sugand@arm.com 17210614Skanishk.sugand@arm.com // Recursively call the updateSum operation till the 17310614Skanishk.sugand@arm.com // root node is reached 17410614Skanishk.sugand@arm.com if (node_parent_ptr) { 17510614Skanishk.sugand@arm.com stack_dist = updateSum(node_parent_ptr, node_left, 17610614Skanishk.sugand@arm.com node_sum_l + node_sum_r, 17710614Skanishk.sugand@arm.com level, stack_dist, discard_node); 17810614Skanishk.sugand@arm.com } 17910614Skanishk.sugand@arm.com 18010614Skanishk.sugand@arm.com return stack_dist; 18110614Skanishk.sugand@arm.com} 18210614Skanishk.sugand@arm.com 18310614Skanishk.sugand@arm.com// This function is called by the calcStackDistAndUpdate function 18410614Skanishk.sugand@arm.com// If is_new_leaf is true then a new leaf is added otherwise a leaf 18510614Skanishk.sugand@arm.com// removed from the tree. In both cases the tree is updated using 18610614Skanishk.sugand@arm.com// the updateSum operation. 18710614Skanishk.sugand@arm.comuint64_t 18810614Skanishk.sugand@arm.comStackDistCalc::updateSumsLeavesToRoot(Node* node, bool is_new_leaf) 18910614Skanishk.sugand@arm.com{ 19010614Skanishk.sugand@arm.com uint64_t level = 0; 19110614Skanishk.sugand@arm.com uint64_t stack_dist = 0; 19210614Skanishk.sugand@arm.com 19310614Skanishk.sugand@arm.com if (is_new_leaf) { 19410614Skanishk.sugand@arm.com node->sumLeft = 1; 19510614Skanishk.sugand@arm.com updateSum(node->parent, 19610614Skanishk.sugand@arm.com node->isLeftNode, node->sumLeft, 19710614Skanishk.sugand@arm.com level, 0, false); 19810614Skanishk.sugand@arm.com 19910614Skanishk.sugand@arm.com stack_dist = Infinity; 20010614Skanishk.sugand@arm.com } else { 20110614Skanishk.sugand@arm.com node->sumLeft = 0; 20210614Skanishk.sugand@arm.com stack_dist = updateSum(node->parent, 20310614Skanishk.sugand@arm.com node->isLeftNode, 0, 20410614Skanishk.sugand@arm.com level, stack_dist, true); 20510614Skanishk.sugand@arm.com } 20610614Skanishk.sugand@arm.com 20710614Skanishk.sugand@arm.com return stack_dist; 20810614Skanishk.sugand@arm.com} 20910614Skanishk.sugand@arm.com 21010614Skanishk.sugand@arm.com// This method is a recursive function which calculates 21110614Skanishk.sugand@arm.com// the node sums till the root. 21210614Skanishk.sugand@arm.comuint64_t 21310614Skanishk.sugand@arm.comStackDistCalc::getSum(Node* node, bool from_left, uint64_t sum_from_below, 21410614Skanishk.sugand@arm.com uint64_t stack_dist, uint64_t level) const 21510614Skanishk.sugand@arm.com{ 21610614Skanishk.sugand@arm.com ++level; 21710614Skanishk.sugand@arm.com // Variable stack_dist is updated only 21810614Skanishk.sugand@arm.com // when arriving from Left. 21911321Ssteve.reinhardt@amd.com if (from_left) { 22010614Skanishk.sugand@arm.com stack_dist += node->sumRight; 22110614Skanishk.sugand@arm.com } 22210614Skanishk.sugand@arm.com 22310614Skanishk.sugand@arm.com // Recursively call the getSum operation till the 22410614Skanishk.sugand@arm.com // root node is reached 22511321Ssteve.reinhardt@amd.com if (node->parent) { 22610614Skanishk.sugand@arm.com stack_dist = getSum(node->parent, node->isLeftNode, 22710614Skanishk.sugand@arm.com node->sumLeft + node->sumRight, 22810614Skanishk.sugand@arm.com stack_dist, level); 22910614Skanishk.sugand@arm.com } 23010614Skanishk.sugand@arm.com 23110614Skanishk.sugand@arm.com return stack_dist; 23210614Skanishk.sugand@arm.com} 23310614Skanishk.sugand@arm.com 23410614Skanishk.sugand@arm.com// This function is called by the calcStackDistance function 23510614Skanishk.sugand@arm.comuint64_t 23610614Skanishk.sugand@arm.comStackDistCalc::getSumsLeavesToRoot(Node* node) const 23710614Skanishk.sugand@arm.com{ 23810614Skanishk.sugand@arm.com return getSum(node->parent, node->isLeftNode, 0, 0, 0); 23910614Skanishk.sugand@arm.com} 24010614Skanishk.sugand@arm.com 24110614Skanishk.sugand@arm.com// Update tree is a tree balancing operation which maintains 24210614Skanishk.sugand@arm.com// the binary tree structure. This method is called whenever 24310614Skanishk.sugand@arm.com// index%2 == 0 (i.e. every alternate cycle) 24410614Skanishk.sugand@arm.com// The two main operation are : 24510614Skanishk.sugand@arm.com// OP1. moving the root node one layer up if index counter 24610614Skanishk.sugand@arm.com// crosses power of 2 24710614Skanishk.sugand@arm.com// OP2. Addition of intermediate nodes as and when required 24810614Skanishk.sugand@arm.com// and linking them to their parents in the layer above. 24910614Skanishk.sugand@arm.comvoid 25010614Skanishk.sugand@arm.comStackDistCalc::updateTree() 25110614Skanishk.sugand@arm.com{ 25210614Skanishk.sugand@arm.com uint64_t i; 25310614Skanishk.sugand@arm.com 25410614Skanishk.sugand@arm.com if (isPowerOf2(index)) { 25510614Skanishk.sugand@arm.com // OP1. moving the root node one layer up if index counter 25610614Skanishk.sugand@arm.com // crosses power of 2 25710614Skanishk.sugand@arm.com // If index counter crosses a power of 2, then add a 25810614Skanishk.sugand@arm.com // new tree layer above and create a new Root node in it. 25910614Skanishk.sugand@arm.com // After the root is created the old node 26010614Skanishk.sugand@arm.com // in the layer below is updated to point to this 26110614Skanishk.sugand@arm.com // newly created root node. The sum_l of this new root node 26210614Skanishk.sugand@arm.com // becomes the sum_l + sum_r of the old node. 26310614Skanishk.sugand@arm.com // 26410614Skanishk.sugand@arm.com // After this root update operation a chain of intermediate 26510614Skanishk.sugand@arm.com // nodes is created from root layer to tree[1](one layer 26610614Skanishk.sugand@arm.com // above the leaf layer) 26710614Skanishk.sugand@arm.com 26810614Skanishk.sugand@arm.com // Create a new root node 26910614Skanishk.sugand@arm.com Node* newRootNode = new Node(); 27010614Skanishk.sugand@arm.com 27110614Skanishk.sugand@arm.com // Update its sum_l as the sum_l+sum_r from below 27210614Skanishk.sugand@arm.com newRootNode->sumLeft = tree[getTreeDepth()][0]->sumRight + 27310614Skanishk.sugand@arm.com tree[getTreeDepth()][0]->sumLeft; 27410614Skanishk.sugand@arm.com // Update its discard left flag if the node below has 27510614Skanishk.sugand@arm.com // has both discardLeft and discardRight set. 27610614Skanishk.sugand@arm.com newRootNode->discardLeft = tree[getTreeDepth()][0]->discardLeft && 27710614Skanishk.sugand@arm.com tree[getTreeDepth()][0]->discardRight; 27810614Skanishk.sugand@arm.com 27910614Skanishk.sugand@arm.com // Map type variable, representing a layer in the tree 28010614Skanishk.sugand@arm.com IndexNodeMap treeLevel; 28110614Skanishk.sugand@arm.com // Add a new layer to the tree 28210614Skanishk.sugand@arm.com tree.push_back(treeLevel); 28310614Skanishk.sugand@arm.com nextIndex.push_back(1); 28410614Skanishk.sugand@arm.com tree[getTreeDepth()][newRootNode->nodeIndex] = newRootNode; 28510614Skanishk.sugand@arm.com 28610614Skanishk.sugand@arm.com // Update the parent pointer at lower layer to 28710614Skanishk.sugand@arm.com // point to newly created root node 28810614Skanishk.sugand@arm.com tree[getTreeDepth() - 1][0]->parent = tree[getTreeDepth()][0]; 28910614Skanishk.sugand@arm.com 29010614Skanishk.sugand@arm.com // Add intermediate nodes from root till bottom (one layer above the 29110614Skanishk.sugand@arm.com // leaf layer) 29210614Skanishk.sugand@arm.com for (i = getTreeDepth() - 1; i >= 1; --i) { 29310614Skanishk.sugand@arm.com Node* newINode = new Node(); 29410614Skanishk.sugand@arm.com // newNode is left or right child depending on the number of nodes 29510614Skanishk.sugand@arm.com // in that layer 29610614Skanishk.sugand@arm.com if (nextIndex[i] % 2 == 0) { 29710614Skanishk.sugand@arm.com newINode->isLeftNode = true; 29810614Skanishk.sugand@arm.com } else { 29910614Skanishk.sugand@arm.com newINode->isLeftNode = false; 30010614Skanishk.sugand@arm.com } 30110614Skanishk.sugand@arm.com 30210614Skanishk.sugand@arm.com newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; 30310614Skanishk.sugand@arm.com newINode->nodeIndex = ++nextIndex[i] - 1; 30410614Skanishk.sugand@arm.com tree[i][newINode->nodeIndex] = newINode; 30510614Skanishk.sugand@arm.com } 30610614Skanishk.sugand@arm.com } else { 30710614Skanishk.sugand@arm.com // OP2. Addition of intermediate nodes as and when required 30810614Skanishk.sugand@arm.com // and linking them to their parents in the layer above. 30910614Skanishk.sugand@arm.com // 31010614Skanishk.sugand@arm.com // At layer 1 a new INode is added whenever index%(2^1)==0 31110614Skanishk.sugand@arm.com // (multiples of 2) 31210614Skanishk.sugand@arm.com // 31310614Skanishk.sugand@arm.com // At layer 2 a new INode is added whenever index%(2^2)==0 31410614Skanishk.sugand@arm.com // (multiples of 4) 31510614Skanishk.sugand@arm.com // 31610614Skanishk.sugand@arm.com // At layer 3 a new INode is added whenever index%(2^3)==0 31710614Skanishk.sugand@arm.com // (multiples of 8) 31810614Skanishk.sugand@arm.com //... 31910614Skanishk.sugand@arm.com // 32010614Skanishk.sugand@arm.com // At layer N a new INode is added whenever index%(2^N)==0 32110614Skanishk.sugand@arm.com // (multiples of 2^N) 32210614Skanishk.sugand@arm.com for (i = getTreeDepth() - 1; i >= 1; --i) { 32310614Skanishk.sugand@arm.com // Traverse each layer from root to leaves and add a new 32410614Skanishk.sugand@arm.com // intermediate node if required. Link the parent_ptr of 32510614Skanishk.sugand@arm.com // the new node to the parent in the above layer. 32610614Skanishk.sugand@arm.com 32710614Skanishk.sugand@arm.com if ((index % (1 << i)) == 0) { 32810614Skanishk.sugand@arm.com // Checks if current (index % 2^treeDepth) == 0 if true 32910614Skanishk.sugand@arm.com // a new node at that layer is created 33010614Skanishk.sugand@arm.com Node* newINode = new Node(); 33110614Skanishk.sugand@arm.com 33210614Skanishk.sugand@arm.com // newNode is left or right child depending on the 33310614Skanishk.sugand@arm.com // number of nodes in that layer. 33410614Skanishk.sugand@arm.com if (nextIndex[i] % 2 == 0) { 33510614Skanishk.sugand@arm.com newINode->isLeftNode = true; 33610614Skanishk.sugand@arm.com } else { 33710614Skanishk.sugand@arm.com newINode->isLeftNode = false; 33810614Skanishk.sugand@arm.com } 33910614Skanishk.sugand@arm.com 34010614Skanishk.sugand@arm.com // Pointing to its parent in the upper layer 34110614Skanishk.sugand@arm.com newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; 34210614Skanishk.sugand@arm.com newINode->nodeIndex = ++nextIndex[i] - 1; 34310614Skanishk.sugand@arm.com tree[i][newINode->nodeIndex] = newINode; 34410614Skanishk.sugand@arm.com } 34510614Skanishk.sugand@arm.com } 34610614Skanishk.sugand@arm.com } 34710614Skanishk.sugand@arm.com} 34810614Skanishk.sugand@arm.com 34910614Skanishk.sugand@arm.com// This function is called everytime to get the stack distance and add 35010614Skanishk.sugand@arm.com// a new node. A feature to mark an old node in the tree is 35110614Skanishk.sugand@arm.com// added. This is useful if it is required to see the reuse 35210614Skanishk.sugand@arm.com// pattern. For example, BackInvalidates from the lower level (Membus) 35310614Skanishk.sugand@arm.com// to L2, can be marked (isMarked flag of Node set to True). And then 35410614Skanishk.sugand@arm.com// later if this same address is accessed by L1, the value of the 35510614Skanishk.sugand@arm.com// isMarked flag would be True. This would give some insight on how 35610614Skanishk.sugand@arm.com// the BackInvalidates policy of the lower level affect the read/write 35710614Skanishk.sugand@arm.com// accesses in an application. 35810614Skanishk.sugand@arm.comstd::pair< uint64_t, bool> 35910614Skanishk.sugand@arm.comStackDistCalc::calcStackDistAndUpdate(const Addr r_address, bool addNewNode) 36010614Skanishk.sugand@arm.com{ 36110614Skanishk.sugand@arm.com Node* newLeafNode; 36210614Skanishk.sugand@arm.com 36310614Skanishk.sugand@arm.com auto ai = aiMap.lower_bound(r_address); 36410614Skanishk.sugand@arm.com 36510614Skanishk.sugand@arm.com // Default value of flag indicating as the left or right leaf 36610614Skanishk.sugand@arm.com bool isLeft = true; 36710614Skanishk.sugand@arm.com // Default value of isMarked flag for each node. 36810614Skanishk.sugand@arm.com bool _mark = false; 36910614Skanishk.sugand@arm.com // By default stackDistacne is treated as infinity 37010614Skanishk.sugand@arm.com uint64_t stack_dist; 37110614Skanishk.sugand@arm.com 37210614Skanishk.sugand@arm.com // Lookup aiMap by giving address as the key: 37310614Skanishk.sugand@arm.com // If found take address and Lookup in tree 37410614Skanishk.sugand@arm.com // Update tree from leaves by making B(found index) = 0 37510614Skanishk.sugand@arm.com // Add sums to right till root while Updating them 37610614Skanishk.sugand@arm.com // Stack Distance of that address sums to right 37710614Skanishk.sugand@arm.com if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { 37810614Skanishk.sugand@arm.com // key already exists 37910614Skanishk.sugand@arm.com // save the index counter value when this address was 38010614Skanishk.sugand@arm.com // encountered before and update it to the current index value 38111189Sandreas.hansson@arm.com uint64_t r_index = ai->second; 38210614Skanishk.sugand@arm.com 38310614Skanishk.sugand@arm.com if (addNewNode) { 38410614Skanishk.sugand@arm.com // Update aiMap aiMap(Address) = current index 38510614Skanishk.sugand@arm.com ai->second = index; 38610614Skanishk.sugand@arm.com } else { 38710614Skanishk.sugand@arm.com aiMap.erase(r_address); 38810614Skanishk.sugand@arm.com } 38910614Skanishk.sugand@arm.com 39010614Skanishk.sugand@arm.com // Call update tree operation on the tree starting with 39110614Skanishk.sugand@arm.com // the r_index value found above. This function would return 39210614Skanishk.sugand@arm.com // the value of the stack distcance. 39310614Skanishk.sugand@arm.com stack_dist = updateSumsLeavesToRoot(tree[0][r_index], false); 39410614Skanishk.sugand@arm.com newLeafNode = tree[0][r_index]; 39510614Skanishk.sugand@arm.com // determine if this node was marked earlier 39610614Skanishk.sugand@arm.com _mark = newLeafNode->isMarked; 39710614Skanishk.sugand@arm.com delete newLeafNode; 39810614Skanishk.sugand@arm.com tree[0].erase(r_index); 39910614Skanishk.sugand@arm.com } else { 40010614Skanishk.sugand@arm.com if (addNewNode) { 40110614Skanishk.sugand@arm.com // Update aiMap aiMap(Address) = current index 40210614Skanishk.sugand@arm.com aiMap[r_address] = index; 40310614Skanishk.sugand@arm.com } 40410614Skanishk.sugand@arm.com // Update infinity bin count 40510614Skanishk.sugand@arm.com // By default stackDistacne is treated as infinity 40610614Skanishk.sugand@arm.com stack_dist = Infinity; 40710614Skanishk.sugand@arm.com } 40810614Skanishk.sugand@arm.com 40910614Skanishk.sugand@arm.com if (addNewNode) { 41010614Skanishk.sugand@arm.com // If index%2 == 0 then update tree 41110614Skanishk.sugand@arm.com if (index % 2 == 0) { 41210614Skanishk.sugand@arm.com updateTree(); 41310614Skanishk.sugand@arm.com } else { 41410614Skanishk.sugand@arm.com // At odd values of index counter, a new right-type node is 41510614Skanishk.sugand@arm.com // added to the leaf layer, else a left-type node is added 41610614Skanishk.sugand@arm.com isLeft = false; 41710614Skanishk.sugand@arm.com } 41810614Skanishk.sugand@arm.com 41910614Skanishk.sugand@arm.com // Add new leaf node in the leaf layer (tree[0]) 42010614Skanishk.sugand@arm.com // set n_index = current index 42110614Skanishk.sugand@arm.com newLeafNode = new Node(); 42210614Skanishk.sugand@arm.com ++nextIndex[0]; 42310614Skanishk.sugand@arm.com newLeafNode->nodeIndex=index; 42410614Skanishk.sugand@arm.com newLeafNode->isLeftNode=isLeft; 42510614Skanishk.sugand@arm.com // Point the parent pointer to the intermediate node above 42610614Skanishk.sugand@arm.com newLeafNode->parent = tree[1][nextIndex[1] - 1]; 42710614Skanishk.sugand@arm.com tree[0][index] = newLeafNode; 42810614Skanishk.sugand@arm.com // call an update operation which would update the tree after 42910614Skanishk.sugand@arm.com // addition of this new leaf node. 43010614Skanishk.sugand@arm.com updateSumsLeavesToRoot(tree[0][index], true); 43110614Skanishk.sugand@arm.com 43210614Skanishk.sugand@arm.com // For verification 43310614Skanishk.sugand@arm.com if (verifyStack) { 43410614Skanishk.sugand@arm.com // This function checks the sanity of the tree to make sure the 43510614Skanishk.sugand@arm.com // last node in the link of parent pointers is the root node. 43610614Skanishk.sugand@arm.com // It takes a leaf node as an argument and traveses upwards till 43710614Skanishk.sugand@arm.com // the root layer to check if the last parent is null 43810614Skanishk.sugand@arm.com sanityCheckTree(tree[0][index]); 43910614Skanishk.sugand@arm.com 44010614Skanishk.sugand@arm.com // Push the same element in debug stack, and check 44110614Skanishk.sugand@arm.com uint64_t verify_stack_dist = verifyStackDist(r_address, true); 44210614Skanishk.sugand@arm.com panic_if(verify_stack_dist != stack_dist, 44310614Skanishk.sugand@arm.com "Expected stack-distance for address \ 44410614Skanishk.sugand@arm.com %#lx is %#lx but found %#lx", 44510614Skanishk.sugand@arm.com r_address, verify_stack_dist, stack_dist); 44610614Skanishk.sugand@arm.com printStack(); 44710614Skanishk.sugand@arm.com } 44810614Skanishk.sugand@arm.com 44910614Skanishk.sugand@arm.com // The index counter is updated at the end of each transaction 45010614Skanishk.sugand@arm.com // (unique or non-unique) 45110614Skanishk.sugand@arm.com ++index; 45210614Skanishk.sugand@arm.com } 45310614Skanishk.sugand@arm.com 45410614Skanishk.sugand@arm.com return (std::make_pair(stack_dist, _mark)); 45510614Skanishk.sugand@arm.com} 45610614Skanishk.sugand@arm.com 45710614Skanishk.sugand@arm.com// This function is called everytime to get the stack distance 45810614Skanishk.sugand@arm.com// no new node is added. It can be used to mark a previous access 45910614Skanishk.sugand@arm.com// and inspect the value of the mark flag. 46010614Skanishk.sugand@arm.comstd::pair< uint64_t, bool> 46110614Skanishk.sugand@arm.comStackDistCalc::calcStackDist(const Addr r_address, bool mark) 46210614Skanishk.sugand@arm.com{ 46310614Skanishk.sugand@arm.com // Default value of isMarked flag for each node. 46410614Skanishk.sugand@arm.com bool _mark = false; 46510614Skanishk.sugand@arm.com 46610614Skanishk.sugand@arm.com auto ai = aiMap.lower_bound(r_address); 46710614Skanishk.sugand@arm.com 46810614Skanishk.sugand@arm.com // By default stackDistacne is treated as infinity 46910614Skanishk.sugand@arm.com uint64_t stack_dist = 0; 47010614Skanishk.sugand@arm.com 47110614Skanishk.sugand@arm.com // Lookup aiMap by giving address as the key: 47210614Skanishk.sugand@arm.com // If found take address and Lookup in tree 47310614Skanishk.sugand@arm.com // Add sums to right till root 47410614Skanishk.sugand@arm.com // Stack Distance of that address sums to right 47510614Skanishk.sugand@arm.com if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { 47610614Skanishk.sugand@arm.com // key already exists 47710614Skanishk.sugand@arm.com // save the index counter value when this address was 47810614Skanishk.sugand@arm.com // encountered before 47911189Sandreas.hansson@arm.com uint64_t r_index = ai->second; 48010614Skanishk.sugand@arm.com 48110614Skanishk.sugand@arm.com // Get the value of mark flag if previously marked 48210614Skanishk.sugand@arm.com _mark = tree[0][r_index]->isMarked; 48310614Skanishk.sugand@arm.com // Mark the leaf node if required 48410614Skanishk.sugand@arm.com tree[0][r_index]->isMarked = mark; 48510614Skanishk.sugand@arm.com 48610614Skanishk.sugand@arm.com // Call get sums operation on the tree starting with 48710614Skanishk.sugand@arm.com // the r_index value found above. This function would return 48810614Skanishk.sugand@arm.com // the value of the stack distcance. 48910614Skanishk.sugand@arm.com stack_dist = getSumsLeavesToRoot(tree[0][r_index]); 49010614Skanishk.sugand@arm.com } else { 49110614Skanishk.sugand@arm.com // Update infinity bin count 49210614Skanishk.sugand@arm.com // By default stackDistacne is treated as infinity 49310614Skanishk.sugand@arm.com stack_dist = Infinity; 49410614Skanishk.sugand@arm.com } 49510614Skanishk.sugand@arm.com 49610614Skanishk.sugand@arm.com // For verification 49710614Skanishk.sugand@arm.com if (verifyStack) { 49810614Skanishk.sugand@arm.com // Calculate the SD of the same address in the debug stack 49910614Skanishk.sugand@arm.com uint64_t verify_stack_dist = verifyStackDist(r_address); 50010614Skanishk.sugand@arm.com panic_if(verify_stack_dist != stack_dist, 50110614Skanishk.sugand@arm.com "Expected stack-distance for address \ 50210614Skanishk.sugand@arm.com %#lx is %#lx but found %#lx", 50310614Skanishk.sugand@arm.com r_address, verify_stack_dist, stack_dist); 50410614Skanishk.sugand@arm.com 50510614Skanishk.sugand@arm.com printStack(); 50610614Skanishk.sugand@arm.com } 50710614Skanishk.sugand@arm.com 50810614Skanishk.sugand@arm.com return std::make_pair(stack_dist, _mark); 50910614Skanishk.sugand@arm.com} 51010614Skanishk.sugand@arm.com 51110614Skanishk.sugand@arm.com// For verification 51210614Skanishk.sugand@arm.com// Simple sanity check for the tree 51310614Skanishk.sugand@arm.comvoid 51410614Skanishk.sugand@arm.comStackDistCalc::sanityCheckTree(const Node* node, uint64_t level) const 51510614Skanishk.sugand@arm.com{ 51610614Skanishk.sugand@arm.com const Node* next_up = node->parent; 51710614Skanishk.sugand@arm.com 51810614Skanishk.sugand@arm.com for (uint64_t i = level + 1; i < getTreeDepth() - level; ++i) { 51910614Skanishk.sugand@arm.com next_up = next_up->parent; 52010614Skanishk.sugand@arm.com panic_if(!next_up, "Sanity check failed for node %ull \n", 52110614Skanishk.sugand@arm.com node->nodeIndex); 52210614Skanishk.sugand@arm.com } 52310614Skanishk.sugand@arm.com 52410614Skanishk.sugand@arm.com // At the root layer the parent_ptr should be null 52510614Skanishk.sugand@arm.com panic_if(next_up->parent, "Sanity check failed for node %ull \n", 52610614Skanishk.sugand@arm.com node->nodeIndex); 52710614Skanishk.sugand@arm.com} 52810614Skanishk.sugand@arm.com 52910614Skanishk.sugand@arm.com// This method can be called to compute the stack distance in a naive 53010614Skanishk.sugand@arm.com// way It can be used to verify the functionality of the stack 53110614Skanishk.sugand@arm.com// distance calculator. It uses std::vector to compute the stack 53210614Skanishk.sugand@arm.com// distance using a naive stack. 53310614Skanishk.sugand@arm.comuint64_t 53410614Skanishk.sugand@arm.comStackDistCalc::verifyStackDist(const Addr r_address, bool update_stack) 53510614Skanishk.sugand@arm.com{ 53610614Skanishk.sugand@arm.com bool found = false; 53710614Skanishk.sugand@arm.com uint64_t stack_dist = 0; 53810614Skanishk.sugand@arm.com auto a = stack.rbegin(); 53910614Skanishk.sugand@arm.com 54010614Skanishk.sugand@arm.com for (; a != stack.rend(); ++a) { 54110614Skanishk.sugand@arm.com if (*a == r_address) { 54210614Skanishk.sugand@arm.com found = true; 54310614Skanishk.sugand@arm.com break; 54410614Skanishk.sugand@arm.com } else { 54510614Skanishk.sugand@arm.com ++stack_dist; 54610614Skanishk.sugand@arm.com } 54710614Skanishk.sugand@arm.com } 54810614Skanishk.sugand@arm.com 54910614Skanishk.sugand@arm.com if (found) { 55010614Skanishk.sugand@arm.com ++a; 55110614Skanishk.sugand@arm.com if (update_stack) 55210614Skanishk.sugand@arm.com stack.erase(a.base()); 55310614Skanishk.sugand@arm.com } else { 55410614Skanishk.sugand@arm.com stack_dist = Infinity; 55510614Skanishk.sugand@arm.com } 55610614Skanishk.sugand@arm.com 55710614Skanishk.sugand@arm.com if (update_stack) 55810614Skanishk.sugand@arm.com stack.push_back(r_address); 55910614Skanishk.sugand@arm.com 56010614Skanishk.sugand@arm.com return stack_dist; 56110614Skanishk.sugand@arm.com} 56210614Skanishk.sugand@arm.com 56310614Skanishk.sugand@arm.com// This method is useful to print top n entities in the stack. 56410614Skanishk.sugand@arm.comvoid 56510614Skanishk.sugand@arm.comStackDistCalc::printStack(int n) const 56610614Skanishk.sugand@arm.com{ 56710614Skanishk.sugand@arm.com Node* node; 56810614Skanishk.sugand@arm.com int count = 0; 56910614Skanishk.sugand@arm.com 57010614Skanishk.sugand@arm.com DPRINTF(StackDist, "Printing last %d entries in tree\n", n); 57110614Skanishk.sugand@arm.com 57210614Skanishk.sugand@arm.com // Walk through leaf layer to display the last n nodes 57310614Skanishk.sugand@arm.com for (auto it = tree[0].rbegin(); (count < n) && (it != tree[0].rend()); 57410614Skanishk.sugand@arm.com ++it, ++count) { 57510614Skanishk.sugand@arm.com node = it->second; 57611189Sandreas.hansson@arm.com uint64_t r_index = node->nodeIndex; 57710614Skanishk.sugand@arm.com 57810614Skanishk.sugand@arm.com // Lookup aiMap using the index returned by the leaf iterator 57910614Skanishk.sugand@arm.com for (auto ai = aiMap.rbegin(); ai != aiMap.rend(); ++ai) { 58010614Skanishk.sugand@arm.com if (ai->second == r_index) { 58110614Skanishk.sugand@arm.com DPRINTF(StackDist,"Tree leaves, Rightmost-[%d] = %#lx\n", 58210614Skanishk.sugand@arm.com count, ai->first); 58310614Skanishk.sugand@arm.com break; 58410614Skanishk.sugand@arm.com } 58510614Skanishk.sugand@arm.com } 58610614Skanishk.sugand@arm.com } 58710614Skanishk.sugand@arm.com 58810614Skanishk.sugand@arm.com DPRINTF(StackDist,"Tree depth = %#ld\n", getTreeDepth()); 58910614Skanishk.sugand@arm.com 59010614Skanishk.sugand@arm.com if (verifyStack) { 59110614Skanishk.sugand@arm.com DPRINTF(StackDist,"Printing Last %d entries in VerifStack \n", n); 59210614Skanishk.sugand@arm.com count = 0; 59310614Skanishk.sugand@arm.com for (auto a = stack.rbegin(); (count < n) && (a != stack.rend()); 59410614Skanishk.sugand@arm.com ++a, ++count) { 59510614Skanishk.sugand@arm.com DPRINTF(StackDist, "Verif Stack, Top-[%d] = %#lx\n", count, *a); 59610614Skanishk.sugand@arm.com } 59710614Skanishk.sugand@arm.com } 59810614Skanishk.sugand@arm.com} 599