dfnDragOps.stats
Copyright © 1986 by Xerox Corporation. All rights reserved.
Peter Kessler, February 21, 1986 11:15:25 am PST
dfn is an implementation Tarjan's depth first numbering algorithm. It does very little arithmetic and a lot of list chasing. The program has three parts: initializing a graph, depth first numbering the graph, and then printing out the results. The depth first numbering of the graph takes 0.0968 secs on a Dorado (February 21, 1986).
The statistics below refer to simulating the three parts of the program on Lizard.
(1) Initializing the graph:

Starting interpreter at February 21, 1986 11:19:56 am PST

Inst 130812 start, cycle: 560280, pc: 4023262B, opcode: 21B
LC1
s1, old: 2202531B (591193), new: 1B (1)
Inst done. newPC: 4023263B, rtnPC: 4023263B, regS: 1B, regL: 1B, control: nextInst

instructions: 130813, cycles: 560281
bytes/inst: 2.66, cycles/inst: 4.28, cycles/reject: 2.21
instBytesUsed: 348576, instBytesFlushed: 33708
euFetches: 55989, euStores: 2441
goodPredictions: 54368, badPredictions: 1221, uncond jumps: 1786, calls: 1301
(fallThruGood: 0, jumpGood: 54368, fallThruBad: 0, jumpBad: 1221)
stackOver: 0
instBufferCycles: 115805, returnInterlockCycles: 768, lookaheadRejectCycles: 1467

IFU cache - probes: 246486, misses: 222, mapMisses: 2, dirtyWrites: 0, rejectCycles: 1563
miss rate: %0.09, reject cycles/probe: 0.01
EU cache - probes: 58430, misses: 35136, mapMisses: 84, dirtyWrites: 957, rejectCycles: 252040
miss rate: %60.13, reject cycles/probe: 4.31

55029 (42.0%): RJNEBJ 27856 (63.3%): LRI2 26736 (83.8%): RRI 1600 (85.0%): JB
1327 (86.0%): RADD 1300 (87.0%): ALS 1299 (88.0%): RET 1219 (88.9%): LIB
1201 (89.8%): LIQB 1201 (90.7%): LFC 1197 (91.7%): SR0 1117 (92.5%): LRI1
940 (93.2%): LR2 865 (93.9%): WRI 680 (94.4%): SRI2 560 (94.8%): RJEBJ
514 (95.2%): RVADD 381 (95.5%): ADDDB 380 (95.8%): ADD 380 (96.1%): DIS
380 (96.4%): LR0 380 (96.7%): LR1 380 (97.0%): ADDB 368 (97.3%): RSUB
357 (97.5%): SRI1 306 (97.8%): LC0 280 (98.0%): LR5 280 (98.2%): QADD
280 (98.4%): LRI3 280 (98.6%): SRI5 253 (98.8%): LR3 253 (99.0%): SRI3
253 (99.2%): SUBDB 184 (99.3%): JS 184 (99.5%): QSUB 184 (99.6%): RAND
184 (99.8%): SHR 122 (99.9%): ROR 100 (99.9%): DFC 5 (99.9%): SRI0
4 (99.9%): SIP 3 (99.9%): LC1 2 (99.9%): RVSUB 2 (99.9%): LIDB
2 (100.%): JDB 1 (100.%): DUP 1 (100.%): ASL 1 (100.%): AS
1 (100.%): WSB 1 (100.%): SHL

Note: Statistics biased.
(2) Depth first numbering the graph:

Inst 268696 start, cycle: 925122, pc: 4023272B, opcode: 321B
LFC 172306B (pc: 4015600B)
Inst done. newPC: 4015600B, rtnPC: 4023275B, regS: 0B, regL: 1B, control: doCall

instructions: 137884, cycles: 364844
bytes/inst: 2.19, cycles/inst: 2.65, cycles/reject: 3.59
instBytesUsed: 301830, instBytesFlushed: 84825
euFetches: 40419, euStores: 1182
goodPredictions: 23641, badPredictions: 9829, uncond jumps: 7143, calls: 1380
(fallThruGood: 90, jumpGood: 23551, fallThruBad: 36, jumpBad: 9793)
stackOver: 0
instBufferCycles: 51654, returnInterlockCycles: 2252, lookaheadRejectCycles: 322

IFU cache - probes: 189442, misses: 64, mapMisses: 0, dirtyWrites: 0, rejectCycles: 448
miss rate: %0.03, reject cycles/probe: 0.00
EU cache - probes: 41601, misses: 13857, mapMisses: 134, dirtyWrites: 588, rejectCycles: 101063
miss rate: %33.31, reject cycles/probe: 2.43

12113 (8.78%): LRI0 10574 (16.4%): JNEBBJ 10307 (23.9%): RRI 10051 (31.2%): LRI5
9621 (38.1%): RJNEBJ 7033 (43.2%): JB 6270 (47.8%): ADDB 5914 (52.1%): RJEBJ
5908 (56.4%): ADD 5732 (60.5%): RB 5709 (64.7%): LR2 5544 (68.7%): RJGEBJ
5418 (72.6%): RADD 4059 (75.5%): LR0 3838 (78.3%): SR0 3136 (80.6%): QADD
3100 (82.8%): LR3 2936 (85.0%): SR4 2782 (87.0%): RSUB 2772 (89.0%): LR8
1416 (90.0%): LFC 1301 (91.0%): ALS 1191 (91.8%): RET 1090 (92.6%): LC0
1048 (93.4%): ROR 1025 (94.1%): JEBBJ 995 (94.9%): LRI1 592 (95.3%): LRI2
509 (95.7%): LIQB 498 (96.0%): LC1 338 (96.3%): WSB 330 (96.5%): SIP
328 (96.7%): LR6 328 (97.0%): RJGBJ 321 (97.2%): RRX 314 (97.4%): DIS
264 (97.6%): RJLBJ 222 (97.8%): LIP 214 (97.9%): SRI1 210 (98.1%): WRI
200 (98.2%): LR1 186 (98.4%): RVSUB 182 (98.5%): SHR 178 (98.6%): SUBB
174 (98.8%): LIB 164 (98.9%): LRI4 154 (99.0%): RVADD 152 (99.1%): RETN
116 (99.2%): PSB 100 (99.3%): LC6 100 (99.3%): SRI2 78 (99.4%): WB
76 (99.4%): DUP 74 (99.5%): JS 74 (99.5%): RJLEBJ 73 (99.6%): RJEB
72 (99.7%): RETK 72 (99.7%): RAI 72 (99.8%): WAI 56 (99.8%): RSB
53 (99.8%): RJNEB 38 (99.9%): SRI0 36 (99.9%): JDB 35 (99.9%): SUB
22 (99.9%): LR4 16 (99.9%): AS 16 (100.%): CST

Note: Statistics biased.
(3) Printing out the results of the numbering:

Inst 269705 start, cycle: 928005, pc: 4014447B, opcode: 377B
X377 0B (0)
s1, old: 2200000B (589824), new: 0B (0)
Inst done. newPC: 4007760B, rtnPC: 4014452B, regS: 1B, regL: 1B, control: doCall

instructions: 1009, cycles: 2884
bytes/inst: 3.00, cycles/inst: 2.86, cycles/reject: 2.27
instBytesUsed: 3022, instBytesFlushed: 1315
euFetches: 301, euStores: 0
goodPredictions: 100, badPredictions: 1, uncond jumps: 1, calls: 100
(fallThruGood: 0, jumpGood: 100, fallThruBad: 0, jumpBad: 1)
stackOver: 0
instBufferCycles: 421, returnInterlockCycles: 4, lookaheadRejectCycles: 14

IFU cache - probes: 1616, misses: 4, mapMisses: 0, dirtyWrites: 0, rejectCycles: 28
miss rate: %0.25, reject cycles/probe: 0.02
EU cache - probes: 301, misses: 152, mapMisses: 0, dirtyWrites: 30, rejectCycles: 1244
miss rate: %50.50, reject cycles/probe: 4.13

201 (19.9%): DIS 201 (39.8%): LRI0 102 (49.9%): RET 101 (59.9%): ALS
101 (69.9%): RJNEBJ 100 (79.8%): LR1 100 (89.7%): LFC 100 (99.7%): RRI
1 (99.8%): LIQB 1 (99.9%): JB 1 (100.%): X377

Note: Statistics biased.
(4) the statistics for the complete program:

Note: start of dump requested by user.

instructions: 269706, cycles: 928009
bytes/inst: 2.42, cycles/inst: 3.44, cycles/reject: 2.60
instBytesUsed: 653428, instBytesFlushed: 119848
euFetches: 96709, euStores: 3623
goodPredictions: 78109, badPredictions: 11051, uncond jumps: 8930, calls: 2781
(fallThruGood: 90, jumpGood: 78019, fallThruBad: 36, jumpBad: 11015)
stackOver: 0
instBufferCycles: 167880, returnInterlockCycles: 3024, lookaheadRejectCycles: 1803

IFU cache - probes: 437544, misses: 290, mapMisses: 2, dirtyWrites: 0, rejectCycles: 2039
miss rate: %0.07, reject cycles/probe: 0.00
EU cache - probes: 100332, misses: 49145, mapMisses: 218, dirtyWrites: 1575, rejectCycles: 354347
miss rate: %48.98, reject cycles/probe: 3.53

64751 (24.0%): RJNEBJ 37143 (37.7%): RRI 28448 (48.3%): LRI2 12314 (52.8%): LRI0
10574 (56.8%): JNEBBJ 10051 (60.5%): LRI5 8634 (63.7%): JB 6745 (66.2%): RADD
6650 (68.7%): ADDB 6649 (71.1%): LR2 6474 (73.5%): RJEBJ 6288 (75.9%): ADD
5732 (78.0%): RB 5544 (80.0%): RJGEBJ 5035 (81.9%): SR0 4439 (83.5%): LR0
3416 (84.8%): QADD 3353 (86.1%): LR3 3150 (87.2%): RSUB 2936 (88.3%): SR4
2772 (89.3%): LR8 2717 (90.3%): LFC 2702 (91.3%): ALS 2592 (92.3%): RET
2112 (93.1%): LRI1 1711 (93.7%): LIQB 1396 (94.2%): LC0 1393 (94.8%): LIB
1170 (95.2%): ROR 1075 (95.6%): WRI 1025 (96.0%): JEBBJ 895 (96.3%): DIS
780 (96.6%): SRI2 680 (96.8%): LR1 668 (97.1%): RVADD 571 (97.3%): SRI1
501 (97.5%): LC1 381 (97.6%): ADDDB 366 (97.8%): SHR 339 (97.9%): WSB
334 (98.0%): SIP 328 (98.1%): LR6 328 (98.3%): RJGBJ 321 (98.4%): RRX
280 (98.5%): LR5 280 (98.6%): LRI3 280 (98.7%): SRI5 264 (98.8%): RJLBJ
258 (98.9%): JS 253 (99.0%): SRI3 253 (99.1%): SUBDB 222 (99.2%): LIP
188 (99.2%): RVSUB 184 (99.3%): QSUB 184 (99.4%): RAND 178 (99.4%): SUBB
164 (99.5%): LRI4 152 (99.5%): RETN 116 (99.6%): PSB 100 (99.6%): LC6
100 (99.7%): DFC 78 (99.7%): WB 77 (99.7%): DUP 74 (99.7%): RJLEBJ
73 (99.8%): RJEB 72 (99.8%): RETK 72 (99.8%): RAI 72 (99.8%): WAI
56 (99.9%): RSB 53 (99.9%): RJNEB 43 (99.9%): SRI0 38 (99.9%): JDB
35 (99.9%): SUB 22 (99.9%): LR4 17 (99.9%): AS 16 (100.%): CST
2 (100.%): LIDB 1 (100.%): ASL 1 (100.%): SHL 1 (100.%): X377

Note: end of dump requested by user.