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