OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library object_graph; | 5 library object_graph; |
6 | 6 |
7 import 'dart:async'; | 7 import 'dart:async'; |
8 import 'dart:collection'; | 8 import 'dart:collection'; |
9 import 'dart:typed_data'; | 9 import 'dart:typed_data'; |
10 | 10 |
11 import 'package:logging/logging.dart'; | 11 import 'package:logging/logging.dart'; |
12 | 12 |
| 13 class _JenkinsSmiHash { |
| 14 static int combine(int hash, int value) { |
| 15 hash = 0x1fffffff & (hash + value); |
| 16 hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10)); |
| 17 return hash ^ (hash >> 6); |
| 18 } |
| 19 |
| 20 static int finish(int hash) { |
| 21 hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3)); |
| 22 hash = hash ^ (hash >> 11); |
| 23 return 0x1fffffff & (hash + ((0x00003fff & hash) << 15)); |
| 24 } |
| 25 |
| 26 static int hash3(a, b, c) => finish(combine(combine(combine(0, a), b), c)); |
| 27 } |
| 28 |
| 29 // Map<[uint32, uint32, uint32], uint32> |
| 30 class AddressMapper { |
| 31 final Uint32List _table; |
| 32 |
| 33 // * 4 ~/3 for 75% load factor |
| 34 // * 4 for four-tuple entries |
| 35 AddressMapper(int N) : _table = new Uint32List((N * 4 ~/ 3) * 4); |
| 36 |
| 37 int _scanFor(int high, int mid, int low) { |
| 38 var hash = _JenkinsSmiHash.hash3(high, mid, low); |
| 39 var start = (hash % _table.length) & ~3; |
| 40 var index = start; |
| 41 do { |
| 42 if (_table[index + 3] == 0) return index; |
| 43 if (_table[index] == high && |
| 44 _table[index + 1] == mid && |
| 45 _table[index + 2] == low) return index; |
| 46 index = (index + 4) % _table.length; |
| 47 } while (index != start); |
| 48 |
| 49 throw new Exception("Interal error: table full"); |
| 50 } |
| 51 |
| 52 int get(int high, int mid, int low) { |
| 53 int index = _scanFor(high, mid, low); |
| 54 if (_table[index + 3] == 0) return null; |
| 55 return _table[index + 3]; |
| 56 } |
| 57 |
| 58 int put(int high, int mid, int low, int id) { |
| 59 if (id == 0) throw new Exception("Internal error: invalid id"); |
| 60 |
| 61 int index = _scanFor(high, mid, low); |
| 62 if ((_table[index + 3] != 0)) { |
| 63 throw new Exception("Internal error: attempt to overwrite key"); |
| 64 } |
| 65 _table[index] = high; |
| 66 _table[index + 1] = mid; |
| 67 _table[index + 2] = low; |
| 68 _table[index + 3] = id; |
| 69 return id; |
| 70 } |
| 71 } |
| 72 |
| 73 |
13 // Port of dart::ReadStream from vm/datastream.h. | 74 // Port of dart::ReadStream from vm/datastream.h. |
14 class _ReadStream { | 75 // |
| 76 // The heap snapshot is a series of variable-length unsigned integers. For |
| 77 // each byte in the stream, the high bit marks the last byte of an integer and |
| 78 // the low 7 bits are the payload. The payloads are sent in little endian |
| 79 // order. |
| 80 // The largest values used are 64-bit addresses. |
| 81 // We read in 4 payload chunks (28-bits) to stay in Smi range on Javascript. |
| 82 // We read them into instance variables ('low', 'mid' and 'high') to avoid |
| 83 // allocating a container. |
| 84 class ReadStream { |
15 int position = 0; | 85 int position = 0; |
16 int _size = 0; | 86 int _size = 0; |
17 final List<ByteData> _chunks; | 87 final List<ByteData> _chunks; |
18 | 88 |
19 _ReadStream(this._chunks) { | 89 ReadStream(this._chunks) { |
20 int n = _chunks.length; | 90 int n = _chunks.length; |
21 for (var i = 0; i < n; i++) { | 91 for (var i = 0; i < n; i++) { |
22 var chunk = _chunks[i]; | 92 var chunk = _chunks[i]; |
23 if (i + 1 != n) { | 93 if (i + 1 != n) { |
24 assert(chunk.lengthInBytes == (1 << 20)); | 94 assert(chunk.lengthInBytes == (1 << 20)); |
25 } | 95 } |
26 _size += chunk.lengthInBytes; | 96 _size += chunk.lengthInBytes; |
27 } | 97 } |
28 } | 98 } |
29 | 99 |
30 int get pendingBytes => _size - position; | 100 int get pendingBytes => _size - position; |
31 | 101 |
32 int getUint8(i) { | 102 int _getUint8(i) { |
33 return _chunks[i >> 20].getUint8(i & 0xFFFFF); | 103 return _chunks[i >> 20].getUint8(i & 0xFFFFF); |
34 } | 104 } |
35 | 105 |
36 int readUnsigned() { | 106 int low = 0; |
37 int result = 0; | 107 int mid = 0; |
38 int shift = 0; | 108 int high = 0; |
39 while (getUint8(position) <= maxUnsignedDataPerByte) { | 109 |
40 result |= getUint8(position) << shift; | 110 int get clampedUint32 { |
41 shift += dataBitsPerByte; | 111 if (high != 0 || mid > 0xF) { |
42 position++; | 112 return 0xFFFFFFFF; |
| 113 } else { |
| 114 // Not shift as JS shifts are signed 32-bit. |
| 115 return mid * 0x10000000 + low; |
43 } | 116 } |
44 result |= (getUint8(position) & byteMask) << shift; | 117 } |
45 position++; | 118 |
46 return result; | 119 bool get isZero { |
| 120 return (high == 0) && (mid == 0) && (low == 0); |
| 121 } |
| 122 |
| 123 void readUnsigned() { |
| 124 low = 0; |
| 125 mid = 0; |
| 126 high = 0; |
| 127 |
| 128 // Low 28 bits. |
| 129 var digit = _getUint8(position++); |
| 130 if (digit > maxUnsignedDataPerByte) { |
| 131 low |= (digit & byteMask << 0); |
| 132 return; |
| 133 } |
| 134 low |= (digit << 0); |
| 135 |
| 136 digit = _getUint8(position++); |
| 137 if (digit > maxUnsignedDataPerByte) { |
| 138 low |= ((digit & byteMask) << 7); |
| 139 return; |
| 140 } |
| 141 low |= (digit << 7); |
| 142 |
| 143 digit = _getUint8(position++); |
| 144 if (digit > maxUnsignedDataPerByte) { |
| 145 low |= ((digit & byteMask) << 14); |
| 146 return; |
| 147 } |
| 148 low |= (digit << 14); |
| 149 |
| 150 digit = _getUint8(position++); |
| 151 if (digit > maxUnsignedDataPerByte) { |
| 152 low |= ((digit & byteMask) << 21); |
| 153 return; |
| 154 } |
| 155 low |= (digit << 21); |
| 156 |
| 157 // Mid 28 bits. |
| 158 digit = _getUint8(position++); |
| 159 if (digit > maxUnsignedDataPerByte) { |
| 160 mid |= (digit & byteMask << 0); |
| 161 return; |
| 162 } |
| 163 mid |= (digit << 0); |
| 164 |
| 165 digit = _getUint8(position++); |
| 166 if (digit > maxUnsignedDataPerByte) { |
| 167 mid |= ((digit & byteMask) << 7); |
| 168 return; |
| 169 } |
| 170 mid |= (digit << 7); |
| 171 |
| 172 digit = _getUint8(position++); |
| 173 if (digit > maxUnsignedDataPerByte) { |
| 174 mid |= ((digit & byteMask) << 14); |
| 175 return; |
| 176 } |
| 177 mid |= (digit << 14); |
| 178 |
| 179 digit = _getUint8(position++); |
| 180 if (digit > maxUnsignedDataPerByte) { |
| 181 mid |= ((digit & byteMask) << 21); |
| 182 return; |
| 183 } |
| 184 mid |= (digit << 21); |
| 185 |
| 186 // High 28 bits. |
| 187 digit = _getUint8(position++); |
| 188 if (digit > maxUnsignedDataPerByte) { |
| 189 high |= (digit & byteMask << 0); |
| 190 return; |
| 191 } |
| 192 high |= (digit << 0); |
| 193 |
| 194 digit = _getUint8(position++); |
| 195 if (digit > maxUnsignedDataPerByte) { |
| 196 high |= ((digit & byteMask) << 7); |
| 197 return; |
| 198 } |
| 199 high |= (digit << 7); |
| 200 throw new Exception("Format error: snapshot field exceeds 64 bits"); |
| 201 } |
| 202 |
| 203 void skipUnsigned() { |
| 204 while (_getUint8(position++) <= maxUnsignedDataPerByte); |
47 } | 205 } |
48 | 206 |
49 static const int dataBitsPerByte = 7; | 207 static const int dataBitsPerByte = 7; |
50 static const int byteMask = (1 << dataBitsPerByte) - 1; | 208 static const int byteMask = (1 << dataBitsPerByte) - 1; |
51 static const int maxUnsignedDataPerByte = byteMask; | 209 static const int maxUnsignedDataPerByte = byteMask; |
52 } | 210 } |
53 | 211 |
54 class ObjectVertex { | 212 class ObjectVertex { |
55 // 0 represents invalid/uninitialized, 1 is the root. | 213 // 0 represents invalid/uninitialized, 1 is the root. |
56 final int _id; | 214 final int _id; |
57 final ObjectGraph _graph; | 215 final ObjectGraph _graph; |
58 | 216 |
59 ObjectVertex._(this._id, this._graph); | 217 ObjectVertex._(this._id, this._graph); |
60 | 218 |
61 bool get isRoot => _id == 1; | 219 bool get isRoot => _id == 1; |
62 | 220 |
63 bool operator ==(other) => _id == other._id && _graph == other._graph; | 221 bool operator ==(other) => _id == other._id && _graph == other._graph; |
64 int get hashCode => _id; | 222 int get hashCode => _id; |
65 | 223 |
66 int get retainedSize => _graph._retainedSizes[_id]; | 224 int get retainedSize => _graph._retainedSizes[_id]; |
67 ObjectVertex get dominator => new ObjectVertex._(_graph._doms[_id], _graph); | 225 ObjectVertex get dominator => new ObjectVertex._(_graph._doms[_id], _graph); |
68 | 226 |
69 int get shallowSize { | 227 int get shallowSize { |
70 var stream = new _ReadStream(_graph._chunks); | 228 var stream = new ReadStream(_graph._chunks); |
71 stream.position = _graph._positions[_id]; | 229 stream.position = _graph._positions[_id]; |
72 stream.readUnsigned(); // addr | 230 stream.skipUnsigned(); // addr |
73 return stream.readUnsigned(); // shallowSize | 231 stream.readUnsigned(); // shallowSize |
| 232 return stream.clampedUint32; |
74 } | 233 } |
75 | 234 |
76 int get vmCid { | 235 int get vmCid { |
77 var stream = new _ReadStream(_graph._chunks); | 236 var stream = new ReadStream(_graph._chunks); |
78 stream.position = _graph._positions[_id]; | 237 stream.position = _graph._positions[_id]; |
79 stream.readUnsigned(); // addr | 238 stream.skipUnsigned(); // addr |
80 stream.readUnsigned(); // shallowSize | 239 stream.skipUnsigned(); // shallowSize |
81 return stream.readUnsigned(); // cid | 240 stream.readUnsigned(); // cid |
| 241 return stream.clampedUint32; |
82 } | 242 } |
83 | 243 |
84 get successors => new _SuccessorsIterable(_graph, _id); | 244 get successors => new _SuccessorsIterable(_graph, _id); |
85 | 245 |
86 int get address { | 246 String get address { |
87 // Note that everywhere else in this file, "address" really means an address | 247 // Note that everywhere else in this file, "address" really means an address |
88 // scaled down by kObjectAlignment. They were scaled down so they would fit | 248 // scaled down by kObjectAlignment. They were scaled down so they would fit |
89 // into Smis on the client. | 249 // into Smis on the client. |
90 var stream = new _ReadStream(_graph._chunks); | 250 var stream = new ReadStream(_graph._chunks); |
91 stream.position = _graph._positions[_id]; | 251 stream.position = _graph._positions[_id]; |
92 var scaledAddr = stream.readUnsigned(); | 252 stream.readUnsigned(); |
93 return scaledAddr * _graph._kObjectAlignment; | 253 |
| 254 // Complicated way to do (high:mid:low * _kObjectAlignment).toHexString() |
| 255 // without intermediate values exceeding int32. |
| 256 |
| 257 var strAddr = ""; |
| 258 var carry = 0; |
| 259 combine4(nibble) { |
| 260 nibble = nibble * _graph._kObjectAlignment + carry; |
| 261 carry = nibble >> 4; |
| 262 nibble = nibble & 0xF; |
| 263 strAddr = nibble.toRadixString(16) + strAddr; |
| 264 } |
| 265 combine28(twentyEightBits) { |
| 266 for (int shift = 0; shift < 28; shift += 4) { |
| 267 combine4((twentyEightBits >> shift) & 0xF); |
| 268 } |
| 269 } |
| 270 combine28(stream.low); |
| 271 combine28(stream.mid); |
| 272 combine28(stream.high); |
| 273 return strAddr; |
94 } | 274 } |
95 | 275 |
96 List<ObjectVertex> dominatorTreeChildren() { | 276 List<ObjectVertex> dominatorTreeChildren() { |
97 var N = _graph._N; | 277 var N = _graph._N; |
98 var doms = _graph._doms; | 278 var doms = _graph._doms; |
99 | 279 |
100 var parentId = _id; | 280 var parentId = _id; |
101 var domChildren = []; | 281 var domChildren = []; |
102 | 282 |
103 for (var childId = 1; childId <= N; childId++) { | 283 for (var childId = 1; childId <= N; childId++) { |
(...skipping 10 matching lines...) Expand all Loading... |
114 final ObjectGraph _graph; | 294 final ObjectGraph _graph; |
115 final int _id; | 295 final int _id; |
116 | 296 |
117 _SuccessorsIterable(this._graph, this._id); | 297 _SuccessorsIterable(this._graph, this._id); |
118 | 298 |
119 Iterator<ObjectVertex> get iterator => new _SuccessorsIterator(_graph, _id); | 299 Iterator<ObjectVertex> get iterator => new _SuccessorsIterator(_graph, _id); |
120 } | 300 } |
121 | 301 |
122 class _SuccessorsIterator implements Iterator<ObjectVertex> { | 302 class _SuccessorsIterator implements Iterator<ObjectVertex> { |
123 final ObjectGraph _graph; | 303 final ObjectGraph _graph; |
124 _ReadStream _stream; | 304 ReadStream _stream; |
125 | 305 |
126 ObjectVertex current; | 306 ObjectVertex current; |
127 | 307 |
128 _SuccessorsIterator(this._graph, int id) { | 308 _SuccessorsIterator(this._graph, int id) { |
129 _stream = new _ReadStream(this._graph._chunks); | 309 _stream = new ReadStream(this._graph._chunks); |
130 _stream.position = _graph._positions[id]; | 310 _stream.position = _graph._positions[id]; |
131 _stream.readUnsigned(); // addr | 311 _stream.skipUnsigned(); // addr |
132 _stream.readUnsigned(); // shallowSize | 312 _stream.skipUnsigned(); // shallowSize |
133 var cid = _stream.readUnsigned(); | 313 _stream.skipUnsigned(); // cid |
134 assert((cid & ~0xFFFF) == 0); // Sanity check: cid's are 16 bit. | |
135 } | 314 } |
136 | 315 |
137 bool moveNext() { | 316 bool moveNext() { |
138 while (true) { | 317 while (true) { |
139 var nextAddr = _stream.readUnsigned(); | 318 _stream.readUnsigned(); |
140 if (nextAddr == 0) return false; | 319 if (_stream.isZero) return false; |
141 var nextId = _graph._addrToId[nextAddr]; | 320 var nextId = _graph._addrToId.get(_stream.high, _stream.mid, _stream.low); |
142 if (nextId == null) continue; // Reference to VM isolate's heap. | 321 if (nextId == null) continue; // Reference to VM isolate's heap. |
143 current = new ObjectVertex._(nextId, _graph); | 322 current = new ObjectVertex._(nextId, _graph); |
144 return true; | 323 return true; |
145 } | 324 } |
146 } | 325 } |
147 } | 326 } |
148 | 327 |
149 class _VerticesIterable extends IterableBase<ObjectVertex> { | 328 class _VerticesIterable extends IterableBase<ObjectVertex> { |
150 final ObjectGraph _graph; | 329 final ObjectGraph _graph; |
151 | 330 |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
225 return this; | 404 return this; |
226 } | 405 } |
227 | 406 |
228 final List<ByteData> _chunks; | 407 final List<ByteData> _chunks; |
229 | 408 |
230 int _kObjectAlignment; | 409 int _kObjectAlignment; |
231 int _N; | 410 int _N; |
232 int _E; | 411 int _E; |
233 int _size; | 412 int _size; |
234 | 413 |
235 Map<int, int> _addrToId = new Map<int, int>(); | 414 AddressMapper _addrToId; |
236 | 415 |
237 // Indexed by node id, with id 0 representing invalid/uninitialized. | 416 // Indexed by node id, with id 0 representing invalid/uninitialized. |
238 Uint32List _positions; // Position of the node in the snapshot. | 417 Uint32List _positions; // Position of the node in the snapshot. |
239 Uint32List _postOrderOrdinals; // post-order index -> id | 418 Uint32List _postOrderOrdinals; // post-order index -> id |
240 Uint32List _postOrderIndices; // id -> post-order index | 419 Uint32List _postOrderIndices; // id -> post-order index |
241 Uint32List _firstPreds; // Offset into preds. | 420 Uint32List _firstPreds; // Offset into preds. |
242 Uint32List _preds; | 421 Uint32List _preds; |
243 Uint32List _doms; | 422 Uint32List _doms; |
244 Uint32List _retainedSizes; | 423 Uint32List _retainedSizes; |
245 | 424 |
246 void _buildPositions() { | 425 void _buildPositions() { |
247 var N = _N; | 426 var N = _N; |
248 var addrToId = _addrToId; | 427 var addrToId = new AddressMapper(N); |
249 | 428 |
250 var positions = new Uint32List(N + 1); | 429 var positions = new Uint32List(N + 1); |
251 | 430 |
252 var stream = new _ReadStream(_chunks); | 431 var stream = new ReadStream(_chunks); |
253 _kObjectAlignment = stream.readUnsigned(); | 432 stream.readUnsigned(); |
| 433 _kObjectAlignment = stream.clampedUint32; |
254 | 434 |
255 var id = 1; | 435 var id = 1; |
256 while (stream.pendingBytes > 0) { | 436 while (stream.pendingBytes > 0) { |
257 positions[id] = stream.position; | 437 positions[id] = stream.position; |
258 var addr = stream.readUnsigned(); | 438 stream.readUnsigned(); // addr |
259 stream.readUnsigned(); // shallowSize | 439 addrToId.put(stream.high, stream.mid, stream.low, id); |
260 stream.readUnsigned(); // cid | 440 stream.skipUnsigned(); // shallowSize |
261 addrToId[addr] = id; | 441 stream.skipUnsigned(); // cid |
262 | 442 |
263 var succAddr = stream.readUnsigned(); | 443 stream.readUnsigned(); |
264 while (succAddr != 0) { | 444 while (!stream.isZero) { |
265 succAddr = stream.readUnsigned(); | 445 stream.readUnsigned(); |
266 } | 446 } |
267 id++; | 447 id++; |
268 } | 448 } |
269 assert(id == (N + 1)); | 449 assert(id == (N + 1)); |
270 | 450 |
271 var root = addrToId[0]; | 451 var root = addrToId.get(0, 0, 0); |
272 assert(root == 1); | 452 assert(root == 1); |
273 | 453 |
| 454 _addrToId = addrToId; |
274 _positions = positions; | 455 _positions = positions; |
275 } | 456 } |
276 | 457 |
277 void _buildPostOrder() { | 458 void _buildPostOrder() { |
278 var N = _N; | 459 var N = _N; |
279 var E = 0; | 460 var E = 0; |
280 var addrToId = _addrToId; | 461 var addrToId = _addrToId; |
281 var positions = _positions; | 462 var positions = _positions; |
282 | 463 |
283 var postOrderOrdinals = new Uint32List(N); | 464 var postOrderOrdinals = new Uint32List(N); |
284 var postOrderIndices = new Uint32List(N + 1); | 465 var postOrderIndices = new Uint32List(N + 1); |
285 var stackNodes = new Uint32List(N); | 466 var stackNodes = new Uint32List(N); |
286 var stackCurrentEdgePos = new Uint32List(N); | 467 var stackCurrentEdgePos = new Uint32List(N); |
287 | 468 |
288 var visited = new Uint8List(N + 1); | 469 var visited = new Uint8List(N + 1); |
289 var postOrderIndex = 0; | 470 var postOrderIndex = 0; |
290 var stackTop = 0; | 471 var stackTop = 0; |
291 var root = 1; | 472 var root = 1; |
292 | 473 |
293 stackNodes[0] = root; | 474 stackNodes[0] = root; |
294 | 475 |
295 var stream = new _ReadStream(_chunks); | 476 var stream = new ReadStream(_chunks); |
296 stream.position = positions[root]; | 477 stream.position = positions[root]; |
297 stream.readUnsigned(); // addr | 478 stream.skipUnsigned(); // addr |
298 stream.readUnsigned(); // shallowSize | 479 stream.skipUnsigned(); // shallowSize |
299 stream.readUnsigned(); // cid | 480 stream.skipUnsigned(); // cid |
300 stackCurrentEdgePos[0] = stream.position; | 481 stackCurrentEdgePos[0] = stream.position; |
301 visited[root] = 1; | 482 visited[root] = 1; |
302 | 483 |
303 while (stackTop >= 0) { | 484 while (stackTop >= 0) { |
304 var n = stackNodes[stackTop]; | 485 var n = stackNodes[stackTop]; |
305 var edgePos = stackCurrentEdgePos[stackTop]; | 486 var edgePos = stackCurrentEdgePos[stackTop]; |
306 | 487 |
307 stream.position = edgePos; | 488 stream.position = edgePos; |
308 var childAddr = stream.readUnsigned(); | 489 stream.readUnsigned(); // childAddr |
309 if (childAddr != 0) { | 490 if (!stream.isZero) { |
310 stackCurrentEdgePos[stackTop] = stream.position; | 491 stackCurrentEdgePos[stackTop] = stream.position; |
311 var childId = addrToId[childAddr]; | 492 var childId = addrToId.get(stream.high, stream.mid, stream.low); |
312 if (childId == null) continue; // Reference to VM isolate's heap. | 493 if (childId == null) continue; // Reference to VM isolate's heap. |
313 E++; | 494 E++; |
314 if (visited[childId] == 1) continue; | 495 if (visited[childId] == 1) continue; |
315 | 496 |
316 stackTop++; | 497 stackTop++; |
317 stackNodes[stackTop] = childId; | 498 stackNodes[stackTop] = childId; |
318 | 499 |
319 stream.position = positions[childId]; | 500 stream.position = positions[childId]; |
320 stream.readUnsigned(); // addr | 501 stream.skipUnsigned(); // addr |
321 stream.readUnsigned(); // shallowSize | 502 stream.skipUnsigned(); // shallowSize |
322 stream.readUnsigned(); // cid | 503 stream.skipUnsigned(); // cid |
323 stackCurrentEdgePos[stackTop] = stream.position; // i.e., first edge | 504 stackCurrentEdgePos[stackTop] = stream.position; // i.e., first edge |
324 visited[childId] = 1; | 505 visited[childId] = 1; |
325 } else { | 506 } else { |
326 // Done with all children. | 507 // Done with all children. |
327 postOrderIndices[n] = postOrderIndex; | 508 postOrderIndices[n] = postOrderIndex; |
328 postOrderOrdinals[postOrderIndex++] = n; | 509 postOrderOrdinals[postOrderIndex++] = n; |
329 stackTop--; | 510 stackTop--; |
330 } | 511 } |
331 } | 512 } |
332 | 513 |
(...skipping 13 matching lines...) Expand all Loading... |
346 | 527 |
347 // This is first filled with the predecessor counts, then reused to hold the | 528 // This is first filled with the predecessor counts, then reused to hold the |
348 // offset to the first predecessor (see alias below). | 529 // offset to the first predecessor (see alias below). |
349 // + 1 because 0 is a sentinel | 530 // + 1 because 0 is a sentinel |
350 // + 1 so the number of predecessors can be found from the difference with | 531 // + 1 so the number of predecessors can be found from the difference with |
351 // the next node's offset. | 532 // the next node's offset. |
352 var numPreds = new Uint32List(N + 2); | 533 var numPreds = new Uint32List(N + 2); |
353 var preds = new Uint32List(E); | 534 var preds = new Uint32List(E); |
354 | 535 |
355 // Count predecessors of each node. | 536 // Count predecessors of each node. |
356 var stream = new _ReadStream(_chunks); | 537 var stream = new ReadStream(_chunks); |
357 for (var i = 1; i <= N; i++) { | 538 for (var i = 1; i <= N; i++) { |
358 stream.position = positions[i]; | 539 stream.position = positions[i]; |
359 stream.readUnsigned(); // addr | 540 stream.skipUnsigned(); // addr |
360 stream.readUnsigned(); // shallowSize | 541 stream.skipUnsigned(); // shallowSize |
361 stream.readUnsigned(); // cid | 542 stream.skipUnsigned(); // cid |
362 var succAddr = stream.readUnsigned(); | 543 stream.readUnsigned(); // succAddr |
363 while (succAddr != 0) { | 544 while (!stream.isZero) { |
364 var succId = addrToId[succAddr]; | 545 var succId = addrToId.get(stream.high, stream.mid, stream.low); |
365 if (succId != null) { | 546 if (succId != null) { |
366 numPreds[succId]++; | 547 numPreds[succId]++; |
367 } else { | 548 } else { |
368 // Reference to VM isolate's heap. | 549 // Reference to VM isolate's heap. |
369 } | 550 } |
370 succAddr = stream.readUnsigned(); | 551 stream.readUnsigned(); // succAddr |
371 } | 552 } |
372 } | 553 } |
373 | 554 |
374 // Assign indices into predecessors array. | 555 // Assign indices into predecessors array. |
375 var firstPreds = numPreds; // Alias. | 556 var firstPreds = numPreds; // Alias. |
376 var nextPreds = new Uint32List(N + 1); | 557 var nextPreds = new Uint32List(N + 1); |
377 var predIndex = 0; | 558 var predIndex = 0; |
378 for (var i = 1; i <= N; i++) { | 559 for (var i = 1; i <= N; i++) { |
379 var thisPredIndex = predIndex; | 560 var thisPredIndex = predIndex; |
380 predIndex += numPreds[i]; | 561 predIndex += numPreds[i]; |
381 firstPreds[i] = thisPredIndex; | 562 firstPreds[i] = thisPredIndex; |
382 nextPreds[i] = thisPredIndex; | 563 nextPreds[i] = thisPredIndex; |
383 } | 564 } |
384 assert(predIndex == E); | 565 assert(predIndex == E); |
385 firstPreds[N + 1] = E; // Extra entry for cheap boundary detection. | 566 firstPreds[N + 1] = E; // Extra entry for cheap boundary detection. |
386 | 567 |
387 // Fill predecessors array. | 568 // Fill predecessors array. |
388 for (var i = 1; i <= N; i++) { | 569 for (var i = 1; i <= N; i++) { |
389 stream.position = positions[i]; | 570 stream.position = positions[i]; |
390 stream.readUnsigned(); // addr | 571 stream.skipUnsigned(); // addr |
391 stream.readUnsigned(); // shallowSize | 572 stream.skipUnsigned(); // shallowSize |
392 stream.readUnsigned(); // cid | 573 stream.skipUnsigned(); // cid |
393 var succAddr = stream.readUnsigned(); | 574 stream.readUnsigned(); // succAddr |
394 while (succAddr != 0) { | 575 while (!stream.isZero) { |
395 var succId = addrToId[succAddr]; | 576 var succId = addrToId.get(stream.high, stream.mid, stream.low); |
396 if (succId != null) { | 577 if (succId != null) { |
397 var predIndex = nextPreds[succId]++; | 578 var predIndex = nextPreds[succId]++; |
398 preds[predIndex] = i; | 579 preds[predIndex] = i; |
399 } else { | 580 } else { |
400 // Reference to VM isolate's heap. | 581 // Reference to VM isolate's heap. |
401 } | 582 } |
402 succAddr = stream.readUnsigned(); | 583 stream.readUnsigned(); // succAddr |
403 } | 584 } |
404 } | 585 } |
405 | 586 |
406 _firstPreds = firstPreds; | 587 _firstPreds = firstPreds; |
407 _preds = preds; | 588 _preds = preds; |
408 } | 589 } |
409 | 590 |
410 // "A Simple, Fast Dominance Algorithm" | 591 // "A Simple, Fast Dominance Algorithm" |
411 // Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy | 592 // Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy |
412 void _buildDominators() { | 593 void _buildDominators() { |
(...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
488 void _calculateRetainedSizes() { | 669 void _calculateRetainedSizes() { |
489 var N = _N; | 670 var N = _N; |
490 | 671 |
491 var size = 0; | 672 var size = 0; |
492 var positions = _positions; | 673 var positions = _positions; |
493 var postOrderOrdinals = _postOrderOrdinals; | 674 var postOrderOrdinals = _postOrderOrdinals; |
494 var doms = _doms; | 675 var doms = _doms; |
495 var retainedSizes = new Uint32List(N + 1); | 676 var retainedSizes = new Uint32List(N + 1); |
496 | 677 |
497 // Start with retained size as shallow size. | 678 // Start with retained size as shallow size. |
498 var reader = new _ReadStream(_chunks); | 679 var reader = new ReadStream(_chunks); |
499 for (var i = 1; i <= N; i++) { | 680 for (var i = 1; i <= N; i++) { |
500 reader.position = positions[i]; | 681 reader.position = positions[i]; |
501 reader.readUnsigned(); // addr | 682 reader.skipUnsigned(); // addr |
502 var shallowSize = reader.readUnsigned(); | 683 reader.readUnsigned(); // shallowSize |
| 684 var shallowSize = reader.clampedUint32; |
503 retainedSizes[i] = shallowSize; | 685 retainedSizes[i] = shallowSize; |
504 size += shallowSize; | 686 size += shallowSize; |
505 } | 687 } |
506 | 688 |
507 // In post order (bottom up), add retained size to dominator's retained | 689 // In post order (bottom up), add retained size to dominator's retained |
508 // size, skipping root. | 690 // size, skipping root. |
509 for (var o = 0; o < (N - 1); o++) { | 691 for (var o = 0; o < (N - 1); o++) { |
510 var i = postOrderOrdinals[o]; | 692 var i = postOrderOrdinals[o]; |
511 assert(i != 1); | 693 assert(i != 1); |
512 retainedSizes[doms[i]] += retainedSizes[i]; | 694 retainedSizes[doms[i]] += retainedSizes[i]; |
513 } | 695 } |
514 | 696 |
515 _retainedSizes = retainedSizes; | 697 _retainedSizes = retainedSizes; |
516 _size = size; | 698 _size = size; |
517 } | 699 } |
518 } | 700 } |
OLD | NEW |