Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | /* |
2 | * ========== Copyright Header Begin ========================================== | |
3 | * | |
4 | * OpenSPARC T2 Processor File: TsoChecker.h | |
5 | * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. | |
6 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES. | |
7 | * | |
8 | * The above named program is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU General Public | |
10 | * License version 2 as published by the Free Software Foundation. | |
11 | * | |
12 | * The above named program is distributed in the hope that it will be | |
13 | * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | * General Public License for more details. | |
16 | * | |
17 | * You should have received a copy of the GNU General Public | |
18 | * License along with this work; if not, write to the Free Software | |
19 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. | |
20 | * | |
21 | * ========== Copyright Header End ============================================ | |
22 | */ | |
23 | #ifndef RIESLING_TSOCHECKER_H | |
24 | #define RIESLING_TSOCHECKER_H | |
25 | /************************************************************************ | |
26 | ** | |
27 | ** Copyright (C) 2002, Sun Microsystems, Inc. | |
28 | ** | |
29 | ** Sun considers its source code as an unpublished, proprietary | |
30 | ** trade secret and it is available only under strict license provisions. | |
31 | ** This copyright notice is placed here only to protect Sun in the event | |
32 | ** the source is deemed a published work. Disassembly, decompilation, | |
33 | ** or other means of reducing the object code to human readable form | |
34 | ** is prohibited by the license agreement under which this code is | |
35 | ** provided to the user or company in possession of this copy." | |
36 | ** | |
37 | *************************************************************************/ | |
38 | #include <iostream> | |
39 | #include <fstream> | |
40 | #include <list> | |
41 | #include <vector> | |
42 | ||
43 | #include "TsoCheckerDefs.h" | |
44 | #include "TsoCheckerCmd.h" | |
45 | #include "TsoNode.h" | |
46 | #include "TsoEdge.h" | |
47 | #include "MemoryAccessHistory.h" | |
48 | ||
49 | namespace Tso { | |
50 | ||
51 | /** | |
52 | * TSOchecker is designed to perform on-the-fly TSO memory consistency model check | |
53 | * in the RTL-Riesling co-sim environment with no limiation on which diags can be | |
54 | * checked against TSO compliance. The kernel of the algorithm is a digraph which | |
55 | * is generated according to instruction's memory access order, program order, and | |
56 | * data dependence, and is constructed in a way that a cycle in the grpah indicates | |
57 | * a TSO violation. | |
58 | * <p> | |
59 | * Note that instructions that do not need to comply with TSO model are not included | |
60 | * in forming the digraph. These instructions include block load, block store, and | |
61 | * block init store, as well as those accessing to I/O address space. Membar is also | |
62 | * not considered in current algorithm, however, this can be in the enhancement plan. | |
63 | * <p> | |
64 | * The TSOchecker defines a single API to other program. The TsoChecker class is the | |
65 | * class where the API locates. It implements the service routines to handle this API. | |
66 | * The fields of this API are defined in the TsoCheckerCmd.h. | |
67 | * <p> | |
68 | * Whenever the API method is called, a node is created. If the entry belongs to the | |
69 | * type of instructions that have to comply with the TSO memory model, it is placed | |
70 | * into the digrpah. However, all entries for one instruction can appear as only one | |
71 | * node in the graph. The routine then create edges between nodes based on their | |
72 | * data dependence and program order constraints. An edge can be a output-depednence | |
73 | * edge, a flow-dependece edge, an anti-dependence edge, a load-load program order | |
74 | * edge, a load-store program order edge, or a store-store program order edge. Finally, | |
75 | * the program checks if there is a cycle in the digraph, and prun the digraph. | |
76 | * <p> | |
77 | * If there is a TSO violation, the program throw an exception and print out the existing | |
78 | * digraph in a text file named TsoViolationDiGraph, which can be processed using the | |
79 | * dot program (as of this writing, it is in /net/suntools/export/tools/sparc/bin/dot). | |
80 | * <p> | |
81 | * @see TsoCheckerCmd.h | |
82 | * @see MemoryAccessHistory.h | |
83 | * @see MemoryAccessHistoryItem.h | |
84 | * @see TsoNode.h | |
85 | * @see TsoEdge.h | |
86 | */ | |
87 | class TsoChecker { | |
88 | ||
89 | public: | |
90 | /** | |
91 | * Default constructor | |
92 | */ | |
93 | TsoChecker(); | |
94 | ||
95 | /** | |
96 | * Copy constructor | |
97 | * | |
98 | * @param orig The TsoChecker object to copy. | |
99 | */ | |
100 | TsoChecker( const TsoChecker &orig ); | |
101 | ||
102 | /** | |
103 | * Destructor | |
104 | */ | |
105 | virtual ~TsoChecker(); | |
106 | ||
107 | /** | |
108 | * Equality operator | |
109 | * | |
110 | * @param rhs The right hand side of the equality operator | |
111 | * @return Return true if this objec and rhs are equal, | |
112 | * otherwise return false | |
113 | */ | |
114 | bool operator==( const TsoChecker &rhs ) const; | |
115 | ||
116 | /** | |
117 | * Assignment operator | |
118 | * | |
119 | * @param rhs The right hand side of the assignment operator. | |
120 | * @return The lvalue of the assignment. | |
121 | */ | |
122 | const TsoChecker & operator=( const TsoChecker &rhs ); | |
123 | ||
124 | /** | |
125 | * Return a string representation of this TsoChecker object. | |
126 | */ | |
127 | std::string toString() const; | |
128 | ||
129 | /** | |
130 | * Initialize private data structures | |
131 | */ | |
132 | void init(int nstrands); | |
133 | ||
134 | /** | |
135 | * Handle memory access registration and TSO violation check. <br> | |
136 | * This is the main method other program calls to perform TSO violation check. | |
137 | * It performs the following tasks: | |
138 | * - create TsoNode for an input request | |
139 | * - book-keep the content of a TsoNode, especially if a node's instruction | |
140 | * contains multiple TSO node. | |
141 | * - maintain the node in the tmpList_ until they form a consecutive instruction | |
142 | * sequence | |
143 | * - form data dependence edges of the node | |
144 | * - form program order edges of the nodes that is in consecutive instruction sequence | |
145 | * - check TSO violation and prun the TSO digraph | |
146 | * - report error and print out the TSO digraph if violating the TSO rules | |
147 | * | |
148 | * @param cmd TsoCheckerCmd data structure containing TSO API fields | |
149 | * @see TsoCheckerCmd.h | |
150 | */ | |
151 | void input(TsoCheckerCmd& cmd); | |
152 | ||
153 | /** | |
154 | * Another form of input() method | |
155 | */ | |
156 | void input(uint32_t tid, uint64_t iseq, enum INSTR_TYPE itype, enum MEM_CMD cmd, | |
157 | uint64_t addr, uint64_t data, uint8_t sizeV, enum DATA_SRC dsrc, | |
158 | uint64_t macc, uint64_t gobs, uint64_t time); | |
159 | ||
160 | /** | |
161 | * Find the node in tmpList_ that belongs to the same instruction | |
162 | * @param cmd The entry TsoCheckerCmd data structure | |
163 | * @return matched TSO node pointer or NULL | |
164 | */ | |
165 | TsoNode* findNode(TsoCheckerCmd& cmd); | |
166 | ||
167 | /** | |
168 | * Find the prvious TSO node in the nodeList_ | |
169 | * @param ntype TSO node type, TSO_LOAD or TSO_STORE | |
170 | * @param tid Thread ID used to select nodeList_ | |
171 | * @return matched TSO node pointer or NULL | |
172 | * @see TsoCheckerDefs.h | |
173 | */ | |
174 | TsoNode* findPrev(enum TSO_NODE_TYPE ntype, uint32_t tid); | |
175 | ||
176 | /** | |
177 | * Insert a node into tmpList_ in is iseq ascending order | |
178 | * @param tid Thread ID to select tmpList_ | |
179 | * @param np Node pointer to be inserted | |
180 | */ | |
181 | void tmpListInsert(uint32_t tid, TsoNode *np); | |
182 | ||
183 | /** | |
184 | * Form data dependence edge for the node. The types of data dependence edges | |
185 | * include flow, anti, and output. Two methods, storeCommit() and loadAccess() | |
186 | * in the MemoryAccessHistory class are called depending on the input node type. | |
187 | * @param np Pointer of the node | |
188 | * @see MemoryAccessHistory.h | |
189 | */ | |
190 | void formDataDependenceEdges(TsoNode *np); | |
191 | ||
192 | /** | |
193 | * Form program order edge for the node. <br> | |
194 | * If the node is a load, then | |
195 | * - a load-load program order edge is created from the previous TSO load to this load. | |
196 | * If the node is a store, then | |
197 | * - a load-store program order edge is created from the provious TSO load to this store, | |
198 | * - a store-store program order edge is created from the provious TSO store to this store | |
199 | */ | |
200 | void formProgramOrderEdges(uint32_t tid); | |
201 | ||
202 | /** | |
203 | * Check to see if a node can be removed. A node does not check for TSO violation | |
204 | * unless it is removable. <br> | |
205 | * A load node can be removed as long as it is not the last load node in the nodeList_. <br> | |
206 | * A store node cannot be removed unless the following conditions are all met: | |
207 | * - not the last store node in the nodeList_ | |
208 | * - all nodes corresponding to its valid bytes of data all become old | |
209 | * - its retire time has passed | |
210 | * @param np Pointer of node to be checked | |
211 | * @return a boolean | |
212 | */ | |
213 | bool canRemove(TsoNode *np); | |
214 | ||
215 | /** | |
216 | * Check if there is a path from nodeP to startNodeP in the digraph consisting of | |
217 | * TSO nodes, data dependence edges, and program order edges. <br> | |
218 | * Checking TSO violation in this algorithm is equivalen to check if there is a cycle | |
219 | * in the digraph. checkCycle(&n1, &n1) can be used to check if a cycle is formed for | |
220 | * node n1. | |
221 | * @param nodeP Pointer of node to be checked | |
222 | * @param startNodeP Pointer of node that begins the check | |
223 | * @return a boolean | |
224 | */ | |
225 | bool checkCycle(TsoNode *nodeP, TsoNode *startNodeP); | |
226 | ||
227 | /** | |
228 | * Remove a node in the MemoryAccessHistory and all its edges. | |
229 | * @param np Pointer of the node | |
230 | */ | |
231 | void removeNode(TsoNode *np); | |
232 | ||
233 | /** | |
234 | * Return a string of a node's output edge in the format of dot program | |
235 | * @param node Pointer of the node | |
236 | * @return the string | |
237 | */ | |
238 | std::string printOutEdges(TsoNode* node); | |
239 | ||
240 | /** | |
241 | * Print the digraph for the nodes in the nodeList_ to output file named | |
242 | * TsoViolationDiGraph (flag=ERROR) or TsoDigraph (flag=NORMAL) in the | |
243 | * dot-processable text format. | |
244 | * <p> | |
245 | * - Use "dot -Tps TsoViolationDigraph -o TsoViolationDigraph.ps" to | |
246 | * generate ps file for TSO violation nodes | |
247 | * - Use "dot -Tps TsoDigraph -o TsoDigraph.ps" to | |
248 | * generate ps file for remaining TSO nodes | |
249 | * - goto http://www.research.att.com/sw/tools/graphviz for more info | |
250 | * about the dot program | |
251 | * @param flag Flag determines which output file name to be used | |
252 | */ | |
253 | void printNodeList(int flag); | |
254 | ||
255 | /** | |
256 | * This method is the same as printNodeList(NORMAL). | |
257 | */ | |
258 | void printNodeList(); | |
259 | ||
260 | /****************************************************************** | |
261 | * Private variable get/set methods | |
262 | ******************************************************************/ | |
263 | void setTime(uint64_t time) { time_ = time; } | |
264 | uint64_t getTime() const { return time_; } | |
265 | ||
266 | protected: | |
267 | ||
268 | private: | |
269 | /** | |
270 | * maccHist_ contains the memory update history based on the store instructions | |
271 | * @see MemoryAccessHistory.h | |
272 | */ | |
273 | MemoryAccessHistory maccHist_; | |
274 | ||
275 | /** | |
276 | * nodeList_ is a pointer to an array of TsoNode pointer lists: one list per thread. <br> | |
277 | * The list contains nodes that have been in program order, and are candidates | |
278 | * for TSO vialation check and prun | |
279 | */ | |
280 | std::list<TsoNode*> *nodeList_; | |
281 | ||
282 | /** | |
283 | * tmpList_ is a pointer to an array of TsoNode pointer lists: one list per thread. <br> | |
284 | * The list contains node that have not yet been in program order. | |
285 | */ | |
286 | std::list<TsoNode*> *tmpList_; | |
287 | ||
288 | /** | |
289 | * lastPoIseq_ is a pointer to an uint64_t array: one field per thread. <br> | |
290 | * It indicates the last Instruction sequence number that is in the nodeList_. | |
291 | */ | |
292 | uint64_t *lastPoIseq_; // last Program Order Iseq | |
293 | ||
294 | /** | |
295 | * time_ indicates the time when the access happens | |
296 | */ | |
297 | uint64_t time_; | |
298 | int listSize_; | |
299 | }; | |
300 | } /* namespace Tso */ | |
301 | ||
302 | #endif /* _TSOCHECKER_H */ |