stack_dist_calc.hh revision 10614
110614Skanishk.sugand@arm.com/* 210614Skanishk.sugand@arm.com * Copyright (c) 2014 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 * Andreas Hansson 3910614Skanishk.sugand@arm.com */ 4010614Skanishk.sugand@arm.com 4110614Skanishk.sugand@arm.com#ifndef __MEM_STACK_DIST_CALC_HH__ 4210614Skanishk.sugand@arm.com#define __MEM_STACK_DIST_CALC_HH__ 4310614Skanishk.sugand@arm.com 4410614Skanishk.sugand@arm.com#include <map> 4510614Skanishk.sugand@arm.com#include <vector> 4610614Skanishk.sugand@arm.com 4710614Skanishk.sugand@arm.com#include "base/types.hh" 4810614Skanishk.sugand@arm.com#include "mem/packet.hh" 4910614Skanishk.sugand@arm.com#include "params/StackDistCalc.hh" 5010614Skanishk.sugand@arm.com#include "sim/sim_object.hh" 5110614Skanishk.sugand@arm.com#include "sim/stats.hh" 5210614Skanishk.sugand@arm.com 5310614Skanishk.sugand@arm.com/** 5410614Skanishk.sugand@arm.com * The stack distance calculator is a passive object that merely 5510614Skanishk.sugand@arm.com * observes the addresses pass to it. It calculates stack distances 5610614Skanishk.sugand@arm.com * of incoming addresses based on the partial sum hierarchy tree 5710614Skanishk.sugand@arm.com * algorithm described by Alamasi et al. 5810614Skanishk.sugand@arm.com * http://doi.acm.org/10.1145/773039.773043. 5910614Skanishk.sugand@arm.com * 6010614Skanishk.sugand@arm.com * A tree structure is maintained and updated at each transaction 6110614Skanishk.sugand@arm.com * (unique or non-unique). The tree is implemented as an STL vector 6210614Skanishk.sugand@arm.com * with layers of the form <map> Each layer in this tree is an 6310614Skanishk.sugand@arm.com * ordered map <uint64_t, Node*>. Nodes are structs which take form 6410614Skanishk.sugand@arm.com * of leaf, intermediate and root nodes. For example, in a tree with 3 6510614Skanishk.sugand@arm.com * layers, tree[0][5] gives a leaf node pointer for key=5 tree[1][1] 6610614Skanishk.sugand@arm.com * gives an intermediate node pointer for key=1 tree[2][0] gives the 6710614Skanishk.sugand@arm.com * root node in the tree. 6810614Skanishk.sugand@arm.com * 6910614Skanishk.sugand@arm.com * At every transaction a hash-map (aiMap) is looked up to check if 7010614Skanishk.sugand@arm.com * the address was already encountered before. Based on this lookup a 7110614Skanishk.sugand@arm.com * transaction can be termed as unique or non-unique. 7210614Skanishk.sugand@arm.com * 7310614Skanishk.sugand@arm.com * In addition to the normal stack distance calculation, a feature to 7410614Skanishk.sugand@arm.com * mark an old node in the tree is added. This is useful if it is 7510614Skanishk.sugand@arm.com * required to see the reuse pattern. For example, BackInvalidates 7610614Skanishk.sugand@arm.com * from a lower level (e.g. membus to L2), can be marked (isMarked 7710614Skanishk.sugand@arm.com * flag of Node set to True). Then later if this same address is 7810614Skanishk.sugand@arm.com * accessed (by L1), the value of the isMarked flag would be 7910614Skanishk.sugand@arm.com * True. This would give some insight on how the BackInvalidates 8010614Skanishk.sugand@arm.com * policy of the lower level affect the read/write accesses in an 8110614Skanishk.sugand@arm.com * application. 8210614Skanishk.sugand@arm.com * 8310614Skanishk.sugand@arm.com * There are two functions provided to interface with the calculator: 8410614Skanishk.sugand@arm.com * 1. pair<uint64_t, bool> calcStackDistAndUpdate(Addr r_address, 8510614Skanishk.sugand@arm.com * bool addNewNode) 8610614Skanishk.sugand@arm.com * At every unique transaction a new leaf node is added at tree[0](leaf layer) 8710614Skanishk.sugand@arm.com * and linked to the layer above (if addNewNode is True). The sums of all 8810614Skanishk.sugand@arm.com * the intermediate nodes is updated till the root. The stack-distance is 8910614Skanishk.sugand@arm.com * returned as a Constant representing INFINITY. 9010614Skanishk.sugand@arm.com * 9110614Skanishk.sugand@arm.com * At every non-unique transaction the tree is traversed from the 9210614Skanishk.sugand@arm.com * leaf at the returned index to the root, the old node is deleted 9310614Skanishk.sugand@arm.com * from the tree, and the sums (to the right are collected) and 9410614Skanishk.sugand@arm.com * decremented. The collected sum represets the stack distance of the 9510614Skanishk.sugand@arm.com * found node. If this node was marked then a bool flag set to True 9610614Skanishk.sugand@arm.com * is returned with the stack_distance. During this operation a node 9710614Skanishk.sugand@arm.com * is discarded at the leaf layer always. Moreover during the 9810614Skanishk.sugand@arm.com * traversal upwards using the updateSum() method, if an intermediate 9910614Skanishk.sugand@arm.com * node is found with no children connected to it, then that is 10010614Skanishk.sugand@arm.com * discarded too. 10110614Skanishk.sugand@arm.com * 10210614Skanishk.sugand@arm.com * The return value of this function is a pair representing the 10310614Skanishk.sugand@arm.com * stack_distance and the value of the marked flag. 10410614Skanishk.sugand@arm.com * 10510614Skanishk.sugand@arm.com * 2. pair<uint64_t , bool> calcStackDist(Addr r_address, bool mark) 10610614Skanishk.sugand@arm.com * This is a stripped down version of the above function which is used to 10710614Skanishk.sugand@arm.com * just inspect the tree, and mark a leaf node (if mark flag is set). The 10810614Skanishk.sugand@arm.com * functionality to add a new node is removed. 10910614Skanishk.sugand@arm.com * 11010614Skanishk.sugand@arm.com * At every unique transaction the stack-distance is returned as a constant 11110614Skanishk.sugand@arm.com * representing INFINITY. 11210614Skanishk.sugand@arm.com * 11310614Skanishk.sugand@arm.com * At every non-unique transaction the tree is traversed from the 11410614Skanishk.sugand@arm.com * leaf at the returned index to the root, and the sums (to the right) 11510614Skanishk.sugand@arm.com * are collected. The collected sum represets the stack distance of 11610614Skanishk.sugand@arm.com * the found node. 11710614Skanishk.sugand@arm.com * 11810614Skanishk.sugand@arm.com * This function does NOT Modify the stack. (No node is added or 11910614Skanishk.sugand@arm.com * deleted). It is just used to mark a node already created and get 12010614Skanishk.sugand@arm.com * its stack distance. 12110614Skanishk.sugand@arm.com * 12210614Skanishk.sugand@arm.com * The return value of this function is a pair representing the stack 12310614Skanishk.sugand@arm.com * distance and the value of the marked flag. 12410614Skanishk.sugand@arm.com * 12510614Skanishk.sugand@arm.com * The table below depicts the usage of the Algorithm using the functions: 12610614Skanishk.sugand@arm.com * pair<uint64_t Stack_dist, bool isMarked> calcStackDistAndUpdate 12710614Skanishk.sugand@arm.com * (Addr r_address, bool addNewNode) 12810614Skanishk.sugand@arm.com * pair<uint64_t Stack_dist, bool isMarked> calcStackDist 12910614Skanishk.sugand@arm.com * (Addr r_address, bool mark) 13010614Skanishk.sugand@arm.com * 13110614Skanishk.sugand@arm.com * | Function | Arguments |Return Val |Use For| 13210614Skanishk.sugand@arm.com * |calcStackDistAndUpdate|r_address, True|I/SD,False |A,GD,GM| 13310614Skanishk.sugand@arm.com * |calcStackDistAndUpdate|r_address,False|SD,prevMark|D,GD,GM| 13410614Skanishk.sugand@arm.com * |calcStackDist |r_address,False|SD,prevMark| GD,GM| 13510614Skanishk.sugand@arm.com * |calcStackDist |r_address, True|SD,prevMark| GD,GM| 13610614Skanishk.sugand@arm.com * 13710614Skanishk.sugand@arm.com * (*A: Allocate an address in stack, if old entry present then it is deleted, 13810614Skanishk.sugand@arm.com * *U: Delete old-address from stack, no new entry is added 13910614Skanishk.sugand@arm.com * *GD: Get-Stack distance of an address, 14010614Skanishk.sugand@arm.com * *GM: Get value of Mark flag, indicates if that address has been touched 14110614Skanishk.sugand@arm.com * before, 14210614Skanishk.sugand@arm.com * *I: stack-distance = infinity, 14310614Skanishk.sugand@arm.com * *SD: Stack Distance 14410614Skanishk.sugand@arm.com * *r_address: address to be added, *prevMark: value of isMarked flag 14510614Skanishk.sugand@arm.com * of the Node) 14610614Skanishk.sugand@arm.com * 14710614Skanishk.sugand@arm.com * Invalidates refer to a type of packet that removes something from 14810614Skanishk.sugand@arm.com * a cache, either autonoumously (due-to cache's own replacement 14910614Skanishk.sugand@arm.com * policy), or snoops from other caches which invalidate something 15010614Skanishk.sugand@arm.com * inside our cache. 15110614Skanishk.sugand@arm.com * 15210614Skanishk.sugand@arm.com * Usage | Function to use |Typical Use | 15310614Skanishk.sugand@arm.com * Add new entry |calcStackDistAndUpdate|Read/Write Allocate | 15410614Skanishk.sugand@arm.com * Delete Old Entry |calcStackDistAndUpdate|Writebacks/Cleanevicts| 15510614Skanishk.sugand@arm.com * Dist.of Old entry|calcStackDist |Cleanevicts/Invalidate| 15610614Skanishk.sugand@arm.com * 15710614Skanishk.sugand@arm.com * Node Balancing: The tree structure is maintained by an 15810614Skanishk.sugand@arm.com * updateTree() operation called when an intermediate node is 15910614Skanishk.sugand@arm.com * required. The update operation is roughly categorized as a root 16010614Skanishk.sugand@arm.com * update or intermediate layer update. When number of leaf nodes 16110614Skanishk.sugand@arm.com * grow over a power of 2 then a new layer is added at the top of the 16210614Skanishk.sugand@arm.com * tree and a new root node is initialized. The old node at the lower 16310614Skanishk.sugand@arm.com * layer is connected to this. In an intermediate node update 16410614Skanishk.sugand@arm.com * operation a new intermediate node is added to the required layer. 16510614Skanishk.sugand@arm.com * 16610614Skanishk.sugand@arm.com * Debugging: Debugging can be enabled by setting the verifyStack flag 16710614Skanishk.sugand@arm.com * true. Debugging is implemented using a dummy stack that behaves in 16810614Skanishk.sugand@arm.com * a naive way, using STL vectors (i.e each unique address is pushed 16910614Skanishk.sugand@arm.com * on the top of an STL vector stack, and SD is returned as 17010614Skanishk.sugand@arm.com * Infinity. If a non unique address is encountered then the previous 17110614Skanishk.sugand@arm.com * entry in the STL vector is removed, all the entities above it are 17210614Skanishk.sugand@arm.com * pushed down, and the address is pushed at the top of the stack). 17310614Skanishk.sugand@arm.com * 17410614Skanishk.sugand@arm.com * A printStack(int numOfEntitiesToPrint) is provided to print top n entities 17510614Skanishk.sugand@arm.com * in both (tree and STL based dummy stack). 17610614Skanishk.sugand@arm.com */ 17710614Skanishk.sugand@arm.comclass StackDistCalc : public SimObject 17810614Skanishk.sugand@arm.com{ 17910614Skanishk.sugand@arm.com 18010614Skanishk.sugand@arm.com private: 18110614Skanishk.sugand@arm.com 18210614Skanishk.sugand@arm.com struct Node; 18310614Skanishk.sugand@arm.com 18410614Skanishk.sugand@arm.com typedef std::map<uint64_t, Node*> IndexNodeMap; 18510614Skanishk.sugand@arm.com typedef std::map<Addr, uint64_t> AddressIndexMap; 18610614Skanishk.sugand@arm.com typedef std::vector<IndexNodeMap> TreeType; 18710614Skanishk.sugand@arm.com 18810614Skanishk.sugand@arm.com /** 18910614Skanishk.sugand@arm.com * Gets sum from the node upwards recursively till the root. This 19010614Skanishk.sugand@arm.com * function is called first by getSumsLeavesToRoot, and then 19110614Skanishk.sugand@arm.com * recursively calls itself. 19210614Skanishk.sugand@arm.com * 19310614Skanishk.sugand@arm.com * @param node pointer to the node which is updated 19410614Skanishk.sugand@arm.com * @param from_left variable which says that the request arrived 19510614Skanishk.sugand@arm.com * from the left 19610614Skanishk.sugand@arm.com * @param sum_from_below Sum of left and right children below 19710614Skanishk.sugand@arm.com * @param level level in the tree the calling node is located 19810614Skanishk.sugand@arm.com * @param stack_dist stack distance of the node below 19910614Skanishk.sugand@arm.com * @return The stack distance of the current address. 20010614Skanishk.sugand@arm.com * 20110614Skanishk.sugand@arm.com */ 20210614Skanishk.sugand@arm.com uint64_t getSum(Node* node, bool from_left, uint64_t sum_from_below, 20310614Skanishk.sugand@arm.com uint64_t stack_dist, uint64_t level) const; 20410614Skanishk.sugand@arm.com 20510614Skanishk.sugand@arm.com /** 20610614Skanishk.sugand@arm.com * Gets the sum from the leaf node specified. This function 20710614Skanishk.sugand@arm.com * is called by calcStackDist. 20810614Skanishk.sugand@arm.com * 20910614Skanishk.sugand@arm.com * @param node pointer to the node which is updated 21010614Skanishk.sugand@arm.com * @return The stack distance of the current address. 21110614Skanishk.sugand@arm.com * 21210614Skanishk.sugand@arm.com */ 21310614Skanishk.sugand@arm.com uint64_t getSumsLeavesToRoot(Node* node) const; 21410614Skanishk.sugand@arm.com 21510614Skanishk.sugand@arm.com /** 21610614Skanishk.sugand@arm.com * Updates the nodes upwards recursively till the root. 21710614Skanishk.sugand@arm.com * This function is first called by updateSumsLeavesToRoot, 21810614Skanishk.sugand@arm.com * and then it recursively calls itself. 21910614Skanishk.sugand@arm.com * 22010614Skanishk.sugand@arm.com * @param node pointer to the node which is updated 22110614Skanishk.sugand@arm.com * @param from_left variable which says that the request arrived 22210614Skanishk.sugand@arm.com * from the left 22310614Skanishk.sugand@arm.com * @param sum_from_below Sum of left and right children below 22410614Skanishk.sugand@arm.com * @param level level in the tree the calling node is located 22510614Skanishk.sugand@arm.com * @param stack_dist stack distance of the node below 22610614Skanishk.sugand@arm.com * @param discard_node whether the calling node was discarded or not 22710614Skanishk.sugand@arm.com * @return The stack distance of the current address. 22810614Skanishk.sugand@arm.com * 22910614Skanishk.sugand@arm.com */ 23010614Skanishk.sugand@arm.com uint64_t updateSum(Node* node, 23110614Skanishk.sugand@arm.com bool from_left, uint64_t sum_from_below, uint64_t level, 23210614Skanishk.sugand@arm.com uint64_t stack_dist, bool discard_node); 23310614Skanishk.sugand@arm.com 23410614Skanishk.sugand@arm.com /** 23510614Skanishk.sugand@arm.com * Updates the leaf nodes and nodes above. This function is 23610614Skanishk.sugand@arm.com * called by the calcStackDistAndUpdate. 23710614Skanishk.sugand@arm.com * 23810614Skanishk.sugand@arm.com * @param node pointer to the node which is updated 23910614Skanishk.sugand@arm.com * @param is_new_leaf is true if this is a newly added node 24010614Skanishk.sugand@arm.com * @return The stack distance of the current address. 24110614Skanishk.sugand@arm.com * 24210614Skanishk.sugand@arm.com */ 24310614Skanishk.sugand@arm.com uint64_t updateSumsLeavesToRoot(Node* node, bool is_new_leaf); 24410614Skanishk.sugand@arm.com 24510614Skanishk.sugand@arm.com /** 24610614Skanishk.sugand@arm.com * updateTree is a tree balancing operation, which maintains the 24710614Skanishk.sugand@arm.com * binary tree structure. 24810614Skanishk.sugand@arm.com * This method is called whenever index%2 == 0 (i.e. every 24910614Skanishk.sugand@arm.com * alternate cycle) The two main operation are : 25010614Skanishk.sugand@arm.com * OP1. Moving the root node one layer up if index counter 25110614Skanishk.sugand@arm.com * crosses power of 2 25210614Skanishk.sugand@arm.com * OP2. Addition of intermediate nodes as and when required 25310614Skanishk.sugand@arm.com * and linking them to their parents in the layer above. 25410614Skanishk.sugand@arm.com */ 25510614Skanishk.sugand@arm.com void updateTree(); 25610614Skanishk.sugand@arm.com 25710614Skanishk.sugand@arm.com /** 25810614Skanishk.sugand@arm.com * This method is used for verification purposes 25910614Skanishk.sugand@arm.com * It recursively traverses upwards from the given node till 26010614Skanishk.sugand@arm.com * the root to check if the ultimate parent node (root-node) points 26110614Skanishk.sugand@arm.com * to null. 26210614Skanishk.sugand@arm.com * 26310614Skanishk.sugand@arm.com * @param node pointer to the node whose sanity is being checked 26410614Skanishk.sugand@arm.com * @param level the level at which this node is located in the tree 26510614Skanishk.sugand@arm.com * 26610614Skanishk.sugand@arm.com */ 26710614Skanishk.sugand@arm.com void sanityCheckTree(const Node* node, uint64_t level = 0) const; 26810614Skanishk.sugand@arm.com 26910614Skanishk.sugand@arm.com /** 27010614Skanishk.sugand@arm.com * A convenient way of refering to infinity. 27110614Skanishk.sugand@arm.com */ 27210614Skanishk.sugand@arm.com static constexpr uint64_t Infinity = std::numeric_limits<uint64_t>::max(); 27310614Skanishk.sugand@arm.com 27410614Skanishk.sugand@arm.com /** 27510614Skanishk.sugand@arm.com * Process the given address. If Mark is true then set the 27610614Skanishk.sugand@arm.com * mark flag of the leaf node. 27710614Skanishk.sugand@arm.com * This function returns the stack distance of the incoming 27810614Skanishk.sugand@arm.com * address and the previous status of the mark flag. 27910614Skanishk.sugand@arm.com * 28010614Skanishk.sugand@arm.com * @param r_address The current address to process 28110614Skanishk.sugand@arm.com * @param mark set the mark flag for the address. 28210614Skanishk.sugand@arm.com * @return The stack distance of the current address and the mark flag. 28310614Skanishk.sugand@arm.com */ 28410614Skanishk.sugand@arm.com std::pair<uint64_t , bool> calcStackDist(const Addr r_address, 28510614Skanishk.sugand@arm.com bool mark = false); 28610614Skanishk.sugand@arm.com 28710614Skanishk.sugand@arm.com /** 28810614Skanishk.sugand@arm.com * Process the given address: 28910614Skanishk.sugand@arm.com * - Lookup the tree for the given address 29010614Skanishk.sugand@arm.com * - delete old node if found in tree 29110614Skanishk.sugand@arm.com * - add a new node (if addNewNode flag is set) 29210614Skanishk.sugand@arm.com * This function returns the stack distance of the incoming 29310614Skanishk.sugand@arm.com * address and the status of the mark flag. 29410614Skanishk.sugand@arm.com * 29510614Skanishk.sugand@arm.com * @param r_address The current address to process 29610614Skanishk.sugand@arm.com * @param addNewNode If true, a new node is added to the tree 29710614Skanishk.sugand@arm.com * @return The stack distance of the current address and the mark flag. 29810614Skanishk.sugand@arm.com */ 29910614Skanishk.sugand@arm.com std::pair<uint64_t, bool> calcStackDistAndUpdate(const Addr r_address, 30010614Skanishk.sugand@arm.com bool addNewNode = true); 30110614Skanishk.sugand@arm.com 30210614Skanishk.sugand@arm.com /** 30310614Skanishk.sugand@arm.com * Return the counter for address accesses (unique and 30410614Skanishk.sugand@arm.com * non-unique). This is further used to dump stats at 30510614Skanishk.sugand@arm.com * regular intervals. 30610614Skanishk.sugand@arm.com * 30710614Skanishk.sugand@arm.com * @return The stack distance of the current address. 30810614Skanishk.sugand@arm.com */ 30910614Skanishk.sugand@arm.com uint64_t getIndex() const { return index; } 31010614Skanishk.sugand@arm.com 31110614Skanishk.sugand@arm.com /** 31210614Skanishk.sugand@arm.com * Query depth of the tree (tree[0] represents leaf layer while 31310614Skanishk.sugand@arm.com * tree[treeDepth] represents the root layer, all layers in 31410614Skanishk.sugand@arm.com * between contain intermediate nodes) 31510614Skanishk.sugand@arm.com * 31610614Skanishk.sugand@arm.com * @return Tree depth 31710614Skanishk.sugand@arm.com */ 31810614Skanishk.sugand@arm.com uint64_t getTreeDepth() const { return tree.size() - 1; } 31910614Skanishk.sugand@arm.com 32010614Skanishk.sugand@arm.com /** 32110614Skanishk.sugand@arm.com * Print the last n items on the stack. 32210614Skanishk.sugand@arm.com * This method prints top n entries in the tree based implementation as 32310614Skanishk.sugand@arm.com * well as dummy stack. 32410614Skanishk.sugand@arm.com * @param n Number of entries to print 32510614Skanishk.sugand@arm.com */ 32610614Skanishk.sugand@arm.com void printStack(int n = 5) const; 32710614Skanishk.sugand@arm.com 32810614Skanishk.sugand@arm.com /** 32910614Skanishk.sugand@arm.com * This is an alternative implementation of the stack-distance 33010614Skanishk.sugand@arm.com * in a naive way. It uses simple STL vector to represent the stack. 33110614Skanishk.sugand@arm.com * It can be used in parallel for debugging purposes. 33210614Skanishk.sugand@arm.com * It is 10x slower than the tree based implemenation. 33310614Skanishk.sugand@arm.com * 33410614Skanishk.sugand@arm.com * @param r_address The current address to process 33510614Skanishk.sugand@arm.com * @param update_stack Flag to indicate if stack should be updated 33610614Skanishk.sugand@arm.com * @return Stack distance which is calculated by this alternative 33710614Skanishk.sugand@arm.com * implementation 33810614Skanishk.sugand@arm.com * 33910614Skanishk.sugand@arm.com */ 34010614Skanishk.sugand@arm.com uint64_t verifyStackDist(const Addr r_address, 34110614Skanishk.sugand@arm.com bool update_stack = false); 34210614Skanishk.sugand@arm.com 34310614Skanishk.sugand@arm.com public: 34410614Skanishk.sugand@arm.com 34510614Skanishk.sugand@arm.com /** 34610614Skanishk.sugand@arm.com * Convenience method to get the params when registering stats. 34710614Skanishk.sugand@arm.com */ 34810614Skanishk.sugand@arm.com const StackDistCalcParams* params() const 34910614Skanishk.sugand@arm.com { return reinterpret_cast<const StackDistCalcParams*>(_params); } 35010614Skanishk.sugand@arm.com 35110614Skanishk.sugand@arm.com StackDistCalc(const StackDistCalcParams* p); 35210614Skanishk.sugand@arm.com 35310614Skanishk.sugand@arm.com ~StackDistCalc(); 35410614Skanishk.sugand@arm.com 35510614Skanishk.sugand@arm.com void regStats(); 35610614Skanishk.sugand@arm.com 35710614Skanishk.sugand@arm.com /** 35810614Skanishk.sugand@arm.com * Update the tree and the statistics. 35910614Skanishk.sugand@arm.com * 36010614Skanishk.sugand@arm.com * @param cmd Command from the packet 36110614Skanishk.sugand@arm.com * @param addr Address to put on the stack 36210614Skanishk.sugand@arm.com */ 36310614Skanishk.sugand@arm.com void update(const MemCmd& cmd, Addr addr); 36410614Skanishk.sugand@arm.com 36510614Skanishk.sugand@arm.com private: 36610614Skanishk.sugand@arm.com 36710614Skanishk.sugand@arm.com /** 36810614Skanishk.sugand@arm.com * Node which takes form of Leaf, INode or Root 36910614Skanishk.sugand@arm.com */ 37010614Skanishk.sugand@arm.com struct Node{ 37110614Skanishk.sugand@arm.com // Sum of the left children 37210614Skanishk.sugand@arm.com uint64_t sumLeft; 37310614Skanishk.sugand@arm.com 37410614Skanishk.sugand@arm.com // Sum of the right children 37510614Skanishk.sugand@arm.com uint64_t sumRight; 37610614Skanishk.sugand@arm.com 37710614Skanishk.sugand@arm.com // Flag to indicate that sumLeft has gone from non-zero value to 0 37810614Skanishk.sugand@arm.com bool discardLeft; 37910614Skanishk.sugand@arm.com 38010614Skanishk.sugand@arm.com // Flag to indicate that sumRight has gone from non-zero value to 0 38110614Skanishk.sugand@arm.com bool discardRight; 38210614Skanishk.sugand@arm.com 38310614Skanishk.sugand@arm.com // Index of the current element in the Map 38410614Skanishk.sugand@arm.com uint64_t nodeIndex; 38510614Skanishk.sugand@arm.com 38610614Skanishk.sugand@arm.com // Pointer to the parent 38710614Skanishk.sugand@arm.com Node* parent; 38810614Skanishk.sugand@arm.com 38910614Skanishk.sugand@arm.com // Flag to mark the node as the right/left child 39010614Skanishk.sugand@arm.com bool isLeftNode; 39110614Skanishk.sugand@arm.com 39210614Skanishk.sugand@arm.com /** 39310614Skanishk.sugand@arm.com * Flag to indicate if this address is marked. Used in case 39410614Skanishk.sugand@arm.com * where stack distance of a touched address is required. 39510614Skanishk.sugand@arm.com */ 39610614Skanishk.sugand@arm.com bool isMarked; 39710614Skanishk.sugand@arm.com 39810614Skanishk.sugand@arm.com /** 39910614Skanishk.sugand@arm.com * The discard flags are false by default they become true if 40010614Skanishk.sugand@arm.com * the node is reached again in a future lookup. 40110614Skanishk.sugand@arm.com */ 40210614Skanishk.sugand@arm.com Node() : sumLeft(0), sumRight(0), discardLeft(false), 40310614Skanishk.sugand@arm.com discardRight(false), nodeIndex(0), 40410614Skanishk.sugand@arm.com parent(nullptr), isLeftNode(true), isMarked(false) 40510614Skanishk.sugand@arm.com { } 40610614Skanishk.sugand@arm.com }; 40710614Skanishk.sugand@arm.com 40810614Skanishk.sugand@arm.com /** 40910614Skanishk.sugand@arm.com * Internal counter for address accesses (unique and non-unique) 41010614Skanishk.sugand@arm.com * This counter increments everytime the calcStackDist() method is 41110614Skanishk.sugand@arm.com * called. This counter is used as a key for the hash- map at the 41210614Skanishk.sugand@arm.com * leaf layer. Practically at every call to the calculator this 41310614Skanishk.sugand@arm.com * counter is incremented and a new leaf node is added in the tree 41410614Skanishk.sugand@arm.com * at the leaf layer using this counter value as the key. 41510614Skanishk.sugand@arm.com */ 41610614Skanishk.sugand@arm.com uint64_t index; 41710614Skanishk.sugand@arm.com 41810614Skanishk.sugand@arm.com // Binary tree of partial sums 41910614Skanishk.sugand@arm.com TreeType tree; 42010614Skanishk.sugand@arm.com 42110614Skanishk.sugand@arm.com // Hash map which returns last seen index of each address 42210614Skanishk.sugand@arm.com AddressIndexMap aiMap; 42310614Skanishk.sugand@arm.com 42410614Skanishk.sugand@arm.com // Keeps count of number of the next unique index for each 42510614Skanishk.sugand@arm.com // level in the tree 42610614Skanishk.sugand@arm.com std::vector<uint64_t> nextIndex; 42710614Skanishk.sugand@arm.com 42810614Skanishk.sugand@arm.com // Dummy Stack for verification 42910614Skanishk.sugand@arm.com std::vector<uint64_t> stack; 43010614Skanishk.sugand@arm.com 43110614Skanishk.sugand@arm.com // Flag to enable verification of stack. (Slows down the simulation) 43210614Skanishk.sugand@arm.com const bool verifyStack; 43310614Skanishk.sugand@arm.com 43410614Skanishk.sugand@arm.com // Disable the linear histograms 43510614Skanishk.sugand@arm.com const bool disableLinearHists; 43610614Skanishk.sugand@arm.com 43710614Skanishk.sugand@arm.com // Disable the logarithmic histograms 43810614Skanishk.sugand@arm.com const bool disableLogHists; 43910614Skanishk.sugand@arm.com 44010614Skanishk.sugand@arm.com // Reads linear histogram 44110614Skanishk.sugand@arm.com Stats::Histogram readLinearHist; 44210614Skanishk.sugand@arm.com 44310614Skanishk.sugand@arm.com // Reads logarithmic histogram 44410614Skanishk.sugand@arm.com Stats::SparseHistogram readLogHist; 44510614Skanishk.sugand@arm.com 44610614Skanishk.sugand@arm.com // Writes linear histogram 44710614Skanishk.sugand@arm.com Stats::Histogram writeLinearHist; 44810614Skanishk.sugand@arm.com 44910614Skanishk.sugand@arm.com // Writes logarithmic histogram 45010614Skanishk.sugand@arm.com Stats::SparseHistogram writeLogHist; 45110614Skanishk.sugand@arm.com 45210614Skanishk.sugand@arm.com}; 45310614Skanishk.sugand@arm.com 45410614Skanishk.sugand@arm.com#endif //__STACK_DIST_CALC_HH__ 455