1/*
2 * Copyright (c) 2014-2015 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
--- 25 unchanged lines hidden (view full) ---
36 *
37 * Authors: Kanishk Sugand
38 * Andreas Hansson
39 */
40
41#ifndef __MEM_STACK_DIST_CALC_HH__
42#define __MEM_STACK_DIST_CALC_HH__
43
44#include <limits>
45#include <map>
46#include <vector>
47
48#include "base/types.hh"
49
50/**
51 * The stack distance calculator is a passive object that merely
52 * observes the addresses pass to it. It calculates stack distances
53 * of incoming addresses based on the partial sum hierarchy tree
54 * algorithm described by Alamasi et al.
55 * http://doi.acm.org/10.1145/773039.773043.
56 *
--- 109 unchanged lines hidden (view full) ---
166 * on the top of an STL vector stack, and SD is returned as
167 * Infinity. If a non unique address is encountered then the previous
168 * entry in the STL vector is removed, all the entities above it are
169 * pushed down, and the address is pushed at the top of the stack).
170 *
171 * A printStack(int numOfEntitiesToPrint) is provided to print top n entities
172 * in both (tree and STL based dummy stack).
173 */
174class StackDistCalc
175{
176
177 private:
178
179 struct Node;
180
181 typedef std::map<uint64_t, Node*> IndexNodeMap;
182 typedef std::map<Addr, uint64_t> AddressIndexMap;
--- 76 unchanged lines hidden (view full) ---
259 *
260 * @param node pointer to the node whose sanity is being checked
261 * @param level the level at which this node is located in the tree
262 *
263 */
264 void sanityCheckTree(const Node* node, uint64_t level = 0) const;
265
266 /**
267 * Return the counter for address accesses (unique and
268 * non-unique). This is further used to dump stats at
269 * regular intervals.
270 *
271 * @return The stack distance of the current address.
272 */
273 uint64_t getIndex() const { return index; }
274
--- 25 unchanged lines hidden (view full) ---
300 * @return Stack distance which is calculated by this alternative
301 * implementation
302 *
303 */
304 uint64_t verifyStackDist(const Addr r_address,
305 bool update_stack = false);
306
307 public:
308 StackDistCalc(bool verify_stack = false);
309
310 ~StackDistCalc();
311
312 /**
313 * A convenient way of refering to infinity.
314 */
315 static constexpr uint64_t Infinity = std::numeric_limits<uint64_t>::max();
316
317
318 /**
319 * Process the given address. If Mark is true then set the
320 * mark flag of the leaf node.
321 * This function returns the stack distance of the incoming
322 * address and the previous status of the mark flag.
323 *
324 * @param r_address The current address to process
325 * @param mark set the mark flag for the address.
326 * @return The stack distance of the current address and the mark flag.
327 */
328 std::pair<uint64_t, bool> calcStackDist(const Addr r_address,
329 bool mark = false);
330
331 /**
332 * Process the given address:
333 * - Lookup the tree for the given address
334 * - delete old node if found in tree
335 * - add a new node (if addNewNode flag is set)
336 * This function returns the stack distance of the incoming
337 * address and the status of the mark flag.
338 *
339 * @param r_address The current address to process
340 * @param addNewNode If true, a new node is added to the tree
341 * @return The stack distance of the current address and the mark flag.
342 */
343 std::pair<uint64_t, bool> calcStackDistAndUpdate(const Addr r_address,
344 bool addNewNode = true);
345
346 private:
347
348 /**
349 * Node which takes form of Leaf, INode or Root
350 */
351 struct Node{
352 // Sum of the left children
--- 53 unchanged lines hidden (view full) ---
406 // level in the tree
407 std::vector<uint64_t> nextIndex;
408
409 // Dummy Stack for verification
410 std::vector<uint64_t> stack;
411
412 // Flag to enable verification of stack. (Slows down the simulation)
413 const bool verifyStack;
414};
415
416
417#endif //__STACK_DIST_CALC_HH__
2 * Copyright (c) 2014-2015 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
--- 25 unchanged lines hidden (view full) ---
36 *
37 * Authors: Kanishk Sugand
38 * Andreas Hansson
39 */
40
41#ifndef __MEM_STACK_DIST_CALC_HH__
42#define __MEM_STACK_DIST_CALC_HH__
43
44#include <limits>
45#include <map>
46#include <vector>
47
48#include "base/types.hh"
49
50/**
51 * The stack distance calculator is a passive object that merely
52 * observes the addresses pass to it. It calculates stack distances
53 * of incoming addresses based on the partial sum hierarchy tree
54 * algorithm described by Alamasi et al.
55 * http://doi.acm.org/10.1145/773039.773043.
56 *
--- 109 unchanged lines hidden (view full) ---
166 * on the top of an STL vector stack, and SD is returned as
167 * Infinity. If a non unique address is encountered then the previous
168 * entry in the STL vector is removed, all the entities above it are
169 * pushed down, and the address is pushed at the top of the stack).
170 *
171 * A printStack(int numOfEntitiesToPrint) is provided to print top n entities
172 * in both (tree and STL based dummy stack).
173 */
174class StackDistCalc
175{
176
177 private:
178
179 struct Node;
180
181 typedef std::map<uint64_t, Node*> IndexNodeMap;
182 typedef std::map<Addr, uint64_t> AddressIndexMap;
--- 76 unchanged lines hidden (view full) ---
259 *
260 * @param node pointer to the node whose sanity is being checked
261 * @param level the level at which this node is located in the tree
262 *
263 */
264 void sanityCheckTree(const Node* node, uint64_t level = 0) const;
265
266 /**
267 * Return the counter for address accesses (unique and
268 * non-unique). This is further used to dump stats at
269 * regular intervals.
270 *
271 * @return The stack distance of the current address.
272 */
273 uint64_t getIndex() const { return index; }
274
--- 25 unchanged lines hidden (view full) ---
300 * @return Stack distance which is calculated by this alternative
301 * implementation
302 *
303 */
304 uint64_t verifyStackDist(const Addr r_address,
305 bool update_stack = false);
306
307 public:
308 StackDistCalc(bool verify_stack = false);
309
310 ~StackDistCalc();
311
312 /**
313 * A convenient way of refering to infinity.
314 */
315 static constexpr uint64_t Infinity = std::numeric_limits<uint64_t>::max();
316
317
318 /**
319 * Process the given address. If Mark is true then set the
320 * mark flag of the leaf node.
321 * This function returns the stack distance of the incoming
322 * address and the previous status of the mark flag.
323 *
324 * @param r_address The current address to process
325 * @param mark set the mark flag for the address.
326 * @return The stack distance of the current address and the mark flag.
327 */
328 std::pair<uint64_t, bool> calcStackDist(const Addr r_address,
329 bool mark = false);
330
331 /**
332 * Process the given address:
333 * - Lookup the tree for the given address
334 * - delete old node if found in tree
335 * - add a new node (if addNewNode flag is set)
336 * This function returns the stack distance of the incoming
337 * address and the status of the mark flag.
338 *
339 * @param r_address The current address to process
340 * @param addNewNode If true, a new node is added to the tree
341 * @return The stack distance of the current address and the mark flag.
342 */
343 std::pair<uint64_t, bool> calcStackDistAndUpdate(const Addr r_address,
344 bool addNewNode = true);
345
346 private:
347
348 /**
349 * Node which takes form of Leaf, INode or Root
350 */
351 struct Node{
352 // Sum of the left children
--- 53 unchanged lines hidden (view full) ---
406 // level in the tree
407 std::vector<uint64_t> nextIndex;
408
409 // Dummy Stack for verification
410 std::vector<uint64_t> stack;
411
412 // Flag to enable verification of stack. (Slows down the simulation)
413 const bool verifyStack;
414};
415
416
417#endif //__STACK_DIST_CALC_HH__