gem5  v21.1.0.2
stack_dist_calc.hh
Go to the documentation of this file.
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
11  * unmodified and in its entirety in all distributions of the software,
12  * modified or unmodified, in source code or in binary form.
13  *
14  * Redistribution and use in source and binary forms, with or without
15  * modification, are permitted provided that the following conditions are
16  * met: redistributions of source code must retain the above copyright
17  * notice, this list of conditions and the following disclaimer;
18  * redistributions in binary form must reproduce the above copyright
19  * notice, this list of conditions and the following disclaimer in the
20  * documentation and/or other materials provided with the distribution;
21  * neither the name of the copyright holders nor the names of its
22  * contributors may be used to endorse or promote products derived from
23  * this software without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36  */
37 
38 #ifndef __MEM_STACK_DIST_CALC_HH__
39 #define __MEM_STACK_DIST_CALC_HH__
40 
41 #include <limits>
42 #include <map>
43 #include <vector>
44 
45 #include "base/types.hh"
46 
47 namespace gem5
48 {
49 
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;
184 
199  uint64_t getSum(Node* node, bool from_left, uint64_t sum_from_below,
200  uint64_t stack_dist, uint64_t level) const;
201 
210  uint64_t getSumsLeavesToRoot(Node* node) const;
211 
227  uint64_t updateSum(Node* node,
228  bool from_left, uint64_t sum_from_below, uint64_t level,
229  uint64_t stack_dist, bool discard_node);
230 
240  uint64_t updateSumsLeavesToRoot(Node* node, bool is_new_leaf);
241 
252  void updateTree();
253 
264  void sanityCheckTree(const Node* node, uint64_t level = 0) const;
265 
273  uint64_t getIndex() const { return index; }
274 
282  uint64_t getTreeDepth() const { return tree.size() - 1; }
283 
290  void printStack(int n = 5) const;
291 
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 
315  static constexpr uint64_t Infinity = std::numeric_limits<uint64_t>::max();
316 
317 
329  bool mark = false);
330 
344  bool addNewNode = true);
345 
346  private:
347 
351  struct Node
352  {
353  // Sum of the left children
354  uint64_t sumLeft;
355 
356  // Sum of the right children
357  uint64_t sumRight;
358 
359  // Flag to indicate that sumLeft has gone from non-zero value to 0
361 
362  // Flag to indicate that sumRight has gone from non-zero value to 0
364 
365  // Index of the current element in the Map
366  uint64_t nodeIndex;
367 
368  // Pointer to the parent
370 
371  // Flag to mark the node as the right/left child
373 
378  bool isMarked;
379 
384  Node() : sumLeft(0), sumRight(0), discardLeft(false),
385  discardRight(false), nodeIndex(0),
386  parent(nullptr), isLeftNode(true), isMarked(false)
387  { }
388  };
389 
398  uint64_t index;
399 
400  // Binary tree of partial sums
402 
403  // Hash map which returns last seen index of each address
405 
406  // Keeps count of number of the next unique index for each
407  // level in the tree
409 
410  // Dummy Stack for verification
412 
413  // Flag to enable verification of stack. (Slows down the simulation)
414  const bool verifyStack;
415 };
416 
417 } // namespace gem5
418 
419 #endif //__STACK_DIST_CALC_HH__
gem5::X86ISA::level
Bitfield< 20 > level
Definition: intmessage.hh:51
gem5::StackDistCalc::verifyStackDist
uint64_t verifyStackDist(const Addr r_address, bool update_stack=false)
This is an alternative implementation of the stack-distance in a naive way.
Definition: stack_dist_calc.cc:536
gem5::StackDistCalc::Infinity
static constexpr uint64_t Infinity
A convenient way of refering to infinity.
Definition: stack_dist_calc.hh:315
gem5::StackDistCalc::Node::sumRight
uint64_t sumRight
Definition: stack_dist_calc.hh:357
gem5::StackDistCalc::stack
std::vector< uint64_t > stack
Definition: stack_dist_calc.hh:411
gem5::StackDistCalc::updateSum
uint64_t updateSum(Node *node, bool from_left, uint64_t sum_from_below, uint64_t level, uint64_t stack_dist, bool discard_node)
Updates the nodes upwards recursively till the root.
Definition: stack_dist_calc.cc:101
gem5::StackDistCalc::Node::discardRight
bool discardRight
Definition: stack_dist_calc.hh:363
gem5::StackDistCalc::StackDistCalc
StackDistCalc(bool verify_stack=false)
Definition: stack_dist_calc.cc:49
gem5::StackDistCalc::getSumsLeavesToRoot
uint64_t getSumsLeavesToRoot(Node *node) const
Gets the sum from the leaf node specified.
Definition: stack_dist_calc.cc:238
std::vector< IndexNodeMap >
gem5::StackDistCalc::~StackDistCalc
~StackDistCalc()
Definition: stack_dist_calc.cc:76
gem5::StackDistCalc::Node
Node which takes form of Leaf, INode or Root.
Definition: stack_dist_calc.hh:351
gem5::StackDistCalc::Node::parent
Node * parent
Definition: stack_dist_calc.hh:369
gem5::StackDistCalc::updateTree
void updateTree()
updateTree is a tree balancing operation, which maintains the binary tree structure.
Definition: stack_dist_calc.cc:252
gem5::StackDistCalc::getTreeDepth
uint64_t getTreeDepth() const
Query depth of the tree (tree[0] represents leaf layer while tree[treeDepth] represents the root laye...
Definition: stack_dist_calc.hh:282
gem5::StackDistCalc::updateSumsLeavesToRoot
uint64_t updateSumsLeavesToRoot(Node *node, bool is_new_leaf)
Updates the leaf nodes and nodes above.
Definition: stack_dist_calc.cc:190
gem5::StackDistCalc::printStack
void printStack(int n=5) const
Print the last n items on the stack.
Definition: stack_dist_calc.cc:567
gem5::StackDistCalc::Node::isMarked
bool isMarked
Flag to indicate if this address is marked.
Definition: stack_dist_calc.hh:378
gem5::StackDistCalc::calcStackDistAndUpdate
std::pair< uint64_t, bool > calcStackDistAndUpdate(const Addr r_address, bool addNewNode=true)
Process the given address:
Definition: stack_dist_calc.cc:361
gem5::StackDistCalc::index
uint64_t index
Internal counter for address accesses (unique and non-unique) This counter increments everytime the c...
Definition: stack_dist_calc.hh:398
gem5::StackDistCalc
The stack distance calculator is a passive object that merely observes the addresses pass to it.
Definition: stack_dist_calc.hh:174
gem5::StackDistCalc::Node::Node
Node()
The discard flags are false by default they become true if the node is reached again in a future look...
Definition: stack_dist_calc.hh:384
std::pair
STL pair class.
Definition: stl.hh:58
gem5::StackDistCalc::getIndex
uint64_t getIndex() const
Return the counter for address accesses (unique and non-unique).
Definition: stack_dist_calc.hh:273
gem5::StackDistCalc::tree
TreeType tree
Definition: stack_dist_calc.hh:401
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::StackDistCalc::getSum
uint64_t getSum(Node *node, bool from_left, uint64_t sum_from_below, uint64_t stack_dist, uint64_t level) const
Gets sum from the node upwards recursively till the root.
Definition: stack_dist_calc.cc:215
gem5::ArmISA::n
Bitfield< 31 > n
Definition: misc_types.hh:455
types.hh
gem5::StackDistCalc::TreeType
std::vector< IndexNodeMap > TreeType
Definition: stack_dist_calc.hh:183
gem5::StackDistCalc::Node::sumLeft
uint64_t sumLeft
Definition: stack_dist_calc.hh:354
gem5::StackDistCalc::AddressIndexMap
std::map< Addr, uint64_t > AddressIndexMap
Definition: stack_dist_calc.hh:182
gem5::StackDistCalc::calcStackDist
std::pair< uint64_t, bool > calcStackDist(const Addr r_address, bool mark=false)
Process the given address.
Definition: stack_dist_calc.cc:463
gem5::StackDistCalc::nextIndex
std::vector< uint64_t > nextIndex
Definition: stack_dist_calc.hh:408
gem5::StackDistCalc::Node::isLeftNode
bool isLeftNode
Definition: stack_dist_calc.hh:372
gem5::StackDistCalc::verifyStack
const bool verifyStack
Definition: stack_dist_calc.hh:414
gem5::StackDistCalc::IndexNodeMap
std::map< uint64_t, Node * > IndexNodeMap
Definition: stack_dist_calc.hh:179
gem5::StackDistCalc::Node::nodeIndex
uint64_t nodeIndex
Definition: stack_dist_calc.hh:366
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::StackDistCalc::sanityCheckTree
void sanityCheckTree(const Node *node, uint64_t level=0) const
This method is used for verification purposes It recursively traverses upwards from the given node ti...
Definition: stack_dist_calc.cc:516
gem5::StackDistCalc::Node::discardLeft
bool discardLeft
Definition: stack_dist_calc.hh:360
gem5::StackDistCalc::aiMap
AddressIndexMap aiMap
Definition: stack_dist_calc.hh:404

Generated on Tue Sep 21 2021 12:25:47 for gem5 by doxygen 1.8.17