OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
113 } | 113 } |
114 } | 114 } |
115 | 115 |
116 bool IsEmpty() const { | 116 bool IsEmpty() const { |
117 for (int i = 0; i < data_length_; i++) { | 117 for (int i = 0; i < data_length_; i++) { |
118 if (data_[i] != 0) return false; | 118 if (data_[i] != 0) return false; |
119 } | 119 } |
120 return true; | 120 return true; |
121 } | 121 } |
122 | 122 |
| 123 bool Equals(const BitVector& other) { |
| 124 for (int i = 0; i < data_length_; i++) { |
| 125 if (data_[i] != other.data_[i]) return false; |
| 126 } |
| 127 return true; |
| 128 } |
| 129 |
123 int length() const { return length_; } | 130 int length() const { return length_; } |
124 | 131 |
125 private: | 132 private: |
126 int length_; | 133 int length_; |
127 int data_length_; | 134 int data_length_; |
128 uint32_t* data_; | 135 uint32_t* data_; |
129 }; | 136 }; |
130 | 137 |
131 | 138 |
132 class ReachingDefinitionsData BASE_EMBEDDED { | 139 // Simple fixed-capacity list-based worklist (managed as a queue) of |
| 140 // pointers to T. |
| 141 template<typename T> |
| 142 class WorkList BASE_EMBEDDED { |
| 143 public: |
| 144 // The worklist cannot grow bigger than size. We keep one item empty to |
| 145 // distinguish between empty and full. |
| 146 WorkList(int size) |
| 147 : capacity_(size + 1), head_(0), tail_(0), queue_(capacity_) { |
| 148 for (int i = 0; i < capacity_; i++) queue_.Add(NULL); |
| 149 } |
| 150 |
| 151 bool is_empty() { return head_ == tail_; } |
| 152 |
| 153 bool is_full() { |
| 154 // The worklist is full if head is at 0 and tail is at capacity - 1: |
| 155 // head == 0 && tail == capacity-1 ==> tail - head == capacity - 1 |
| 156 // or if tail is immediately to the left of head: |
| 157 // tail+1 == head ==> tail - head == -1 |
| 158 int diff = tail_ - head_; |
| 159 return (diff == -1 || diff == capacity_ - 1); |
| 160 } |
| 161 |
| 162 void Insert(T* item) { |
| 163 ASSERT(!is_full()); |
| 164 queue_[tail_++] = item; |
| 165 if (tail_ == capacity_) tail_ = 0; |
| 166 } |
| 167 |
| 168 T* Remove() { |
| 169 ASSERT(!is_empty()); |
| 170 T* item = queue_[head_++]; |
| 171 if (head_ == capacity_) head_ = 0; |
| 172 return item; |
| 173 } |
| 174 |
| 175 private: |
| 176 int capacity_; // Including one empty slot. |
| 177 int head_; // Where the first item is. |
| 178 int tail_; // Where the next inserted item will go. |
| 179 List<T*> queue_; |
| 180 }; |
| 181 |
| 182 |
| 183 struct ReachingDefinitionsData BASE_EMBEDDED { |
133 public: | 184 public: |
134 ReachingDefinitionsData() : rd_in_(NULL), kill_(NULL), gen_(NULL) {} | 185 ReachingDefinitionsData() : rd_in_(NULL), kill_(NULL), gen_(NULL) {} |
135 | 186 |
136 void Initialize(int definition_count) { | 187 void Initialize(int definition_count) { |
137 rd_in_ = new BitVector(definition_count); | 188 rd_in_ = new BitVector(definition_count); |
138 kill_ = new BitVector(definition_count); | 189 kill_ = new BitVector(definition_count); |
139 gen_ = new BitVector(definition_count); | 190 gen_ = new BitVector(definition_count); |
140 } | 191 } |
141 | 192 |
142 BitVector* rd_in() { return rd_in_; } | 193 BitVector* rd_in() { return rd_in_; } |
(...skipping 29 matching lines...) Expand all Loading... |
172 // traversal orders. | 223 // traversal orders. |
173 virtual void Traverse(bool mark, | 224 virtual void Traverse(bool mark, |
174 ZoneList<Node*>* preorder, | 225 ZoneList<Node*>* preorder, |
175 ZoneList<Node*>* postorder) = 0; | 226 ZoneList<Node*>* postorder) = 0; |
176 | 227 |
177 int number() { return number_; } | 228 int number() { return number_; } |
178 void set_number(int number) { number_ = number; } | 229 void set_number(int number) { number_ = number; } |
179 | 230 |
180 // Functions used by data-flow analyses. | 231 // Functions used by data-flow analyses. |
181 virtual void InitializeReachingDefinitions(int definition_count, | 232 virtual void InitializeReachingDefinitions(int definition_count, |
182 List<BitVector*>* variables); | 233 List<BitVector*>* variables, |
| 234 WorkList<Node>* worklist, |
| 235 bool mark); |
| 236 virtual void ComputeRDOut(BitVector* result) = 0; |
| 237 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark) = 0; |
183 | 238 |
184 #ifdef DEBUG | 239 #ifdef DEBUG |
185 void AssignNodeNumber(); | 240 void AssignNodeNumber(); |
186 void PrintReachingDefinitions(); | 241 void PrintReachingDefinitions(); |
187 virtual void PrintText() = 0; | 242 virtual void PrintText() = 0; |
188 #endif | 243 #endif |
189 | 244 |
190 protected: | 245 protected: |
191 ReachingDefinitionsData rd_; | 246 ReachingDefinitionsData rd_; |
192 | 247 |
(...skipping 16 matching lines...) Expand all Loading... |
209 ASSERT(predecessor != NULL); | 264 ASSERT(predecessor != NULL); |
210 predecessors_.Add(predecessor); | 265 predecessors_.Add(predecessor); |
211 } | 266 } |
212 | 267 |
213 void AddSuccessor(Node* successor) { UNREACHABLE(); } | 268 void AddSuccessor(Node* successor) { UNREACHABLE(); } |
214 | 269 |
215 void Traverse(bool mark, | 270 void Traverse(bool mark, |
216 ZoneList<Node*>* preorder, | 271 ZoneList<Node*>* preorder, |
217 ZoneList<Node*>* postorder); | 272 ZoneList<Node*>* postorder); |
218 | 273 |
| 274 void ComputeRDOut(BitVector* result); |
| 275 void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
| 276 |
219 #ifdef DEBUG | 277 #ifdef DEBUG |
220 void PrintText(); | 278 void PrintText(); |
221 #endif | 279 #endif |
222 | 280 |
223 private: | 281 private: |
224 ZoneList<Node*> predecessors_; | 282 ZoneList<Node*> predecessors_; |
225 | 283 |
226 DISALLOW_COPY_AND_ASSIGN(ExitNode); | 284 DISALLOW_COPY_AND_ASSIGN(ExitNode); |
227 }; | 285 }; |
228 | 286 |
(...skipping 25 matching lines...) Expand all Loading... |
254 | 312 |
255 void AddInstruction(AstNode* instruction) { | 313 void AddInstruction(AstNode* instruction) { |
256 instructions_.Add(instruction); | 314 instructions_.Add(instruction); |
257 } | 315 } |
258 | 316 |
259 void Traverse(bool mark, | 317 void Traverse(bool mark, |
260 ZoneList<Node*>* preorder, | 318 ZoneList<Node*>* preorder, |
261 ZoneList<Node*>* postorder); | 319 ZoneList<Node*>* postorder); |
262 | 320 |
263 void InitializeReachingDefinitions(int definition_count, | 321 void InitializeReachingDefinitions(int definition_count, |
264 List<BitVector*>* variables); | 322 List<BitVector*>* variables, |
| 323 WorkList<Node>* worklist, |
| 324 bool mark); |
| 325 void ComputeRDOut(BitVector* result); |
| 326 void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
265 | 327 |
266 #ifdef DEBUG | 328 #ifdef DEBUG |
267 void PrintText(); | 329 void PrintText(); |
268 #endif | 330 #endif |
269 | 331 |
270 private: | 332 private: |
271 Node* predecessor_; | 333 Node* predecessor_; |
272 Node* successor_; | 334 Node* successor_; |
273 ZoneList<AstNode*> instructions_; | 335 ZoneList<AstNode*> instructions_; |
274 | 336 |
(...skipping 19 matching lines...) Expand all Loading... |
294 successor0_ = successor; | 356 successor0_ = successor; |
295 } else { | 357 } else { |
296 successor1_ = successor; | 358 successor1_ = successor; |
297 } | 359 } |
298 } | 360 } |
299 | 361 |
300 void Traverse(bool mark, | 362 void Traverse(bool mark, |
301 ZoneList<Node*>* preorder, | 363 ZoneList<Node*>* preorder, |
302 ZoneList<Node*>* postorder); | 364 ZoneList<Node*>* postorder); |
303 | 365 |
| 366 void ComputeRDOut(BitVector* result); |
| 367 void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
| 368 |
304 #ifdef DEBUG | 369 #ifdef DEBUG |
305 void PrintText(); | 370 void PrintText(); |
306 #endif | 371 #endif |
307 | 372 |
308 private: | 373 private: |
309 Node* predecessor_; | 374 Node* predecessor_; |
310 Node* successor0_; | 375 Node* successor0_; |
311 Node* successor1_; | 376 Node* successor1_; |
312 | 377 |
313 DISALLOW_COPY_AND_ASSIGN(BranchNode); | 378 DISALLOW_COPY_AND_ASSIGN(BranchNode); |
(...skipping 19 matching lines...) Expand all Loading... |
333 | 398 |
334 void AddSuccessor(Node* successor) { | 399 void AddSuccessor(Node* successor) { |
335 ASSERT(successor_ == NULL && successor != NULL); | 400 ASSERT(successor_ == NULL && successor != NULL); |
336 successor_ = successor; | 401 successor_ = successor; |
337 } | 402 } |
338 | 403 |
339 void Traverse(bool mark, | 404 void Traverse(bool mark, |
340 ZoneList<Node*>* preorder, | 405 ZoneList<Node*>* preorder, |
341 ZoneList<Node*>* postorder); | 406 ZoneList<Node*>* postorder); |
342 | 407 |
| 408 void ComputeRDOut(BitVector* result); |
| 409 void UpdateRDIn(WorkList<Node>* worklist, bool mark); |
| 410 |
343 #ifdef DEBUG | 411 #ifdef DEBUG |
344 void PrintText(); | 412 void PrintText(); |
345 #endif | 413 #endif |
346 | 414 |
347 private: | 415 private: |
348 ZoneList<Node*> predecessors_; | 416 ZoneList<Node*> predecessors_; |
349 Node* successor_; | 417 Node* successor_; |
350 | 418 |
351 DISALLOW_COPY_AND_ASSIGN(JoinNode); | 419 DISALLOW_COPY_AND_ASSIGN(JoinNode); |
352 }; | 420 }; |
(...skipping 237 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
590 List<BitVector*> variables_; | 658 List<BitVector*> variables_; |
591 | 659 |
592 DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions); | 660 DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions); |
593 }; | 661 }; |
594 | 662 |
595 | 663 |
596 } } // namespace v8::internal | 664 } } // namespace v8::internal |
597 | 665 |
598 | 666 |
599 #endif // V8_DATAFLOW_H_ | 667 #endif // V8_DATAFLOW_H_ |
OLD | NEW |