Branch Prediction Championship Simulatorの続きを試す。
Branch Prediction Simulatorのトレースファイルの中身を解析する。
トレースファイルの中身を読んで見る
例えば、SHORT_MOBILE-24.bt9.trace.gz
の中身は以下のようになっている。大きく分けて4つの領域に分かれているように見える。
- たぶんトレースファイルの諸元のようなところ。
BT9_SPA_TRACE_FORMAT bt9_minor_version: 0 has_physical_address: 1 md5_checksum: conversion_date: original_stf_input_file: total_instruction_count: 1000000000 # Instruction count branch_instruction_count: 38684343 # Branch count invalid_physical_branch_target_count: 2226408 # Invalid Physical Target Count A32_instruction_count: 1000000000 # A32 instructions A64_instruction_count: 0 # A64 instructions T32_instruction_count: 0 # T32 instructions unidentified_instruction_count: 0 # Unidentified instructions
- ノード。つまり命令そのものを表す。ここでは、分岐命令しか定義しないようだ。
BT9_NODES #NODE id virtual_address physical_address opcode size NODE 0 0 - 0 0 NODE 1 0x40015a98 0xcb25ea98 0x1afffffb 4 class: JMP+DIR+CND behavior: DYN+DIR taken_cnt: 61 not_taken_cnt: 1 tgt_cnt: 1 # mnemonic: "bne 0x0000000040015a8c" NODE 2 0x40015a9c 0xcb25ea9c 0xeaffee70 4 class: JMP+DIR+UCD behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "b 0x0000000040011464" NODE 3 0xffff0008 0xcb174008 0xe59ff410 4 class: JMP+IND+UCD behavior: AT+DIR taken_cnt: 13 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "ldr pc, [pc, #1040] ; 0x00000000ffff0420" NODE 4 0xc0023f0c 0xcaa12f0c 0x1a000008 4 class: JMP+DIR+CND behavior: ANT+DIR taken_cnt: 0 not_taken_cnt: 13 tgt_cnt: 0 # mnemonic: "bne 0x00000000c0023f34" NODE 5 0xc0023f18 0xcaa12f18 0x3798f107 4 class: JMP+IND+CND behavior: DYN+IND taken_cnt: 12 not_taken_cnt: 1 tgt_cnt: 2 # mnemonic: "ldrcc pc, [r8, r7, lsl #2]" NODE 6 0xc0023f2c 0xcaa12f2c 0x2a000ebe 4 class: JMP+DIR+CND behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "bcs 0x00000000c0027a2c" NODE 7 0xc0027a50 0xcaa16a50 0xa00001f 4 class: JMP+DIR+CND behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "beq 0x00000000c0027ad4" NODE 8 0xc0027adc 0xcaa16adc 0x979ff101 4 class: JMP+IND+CND behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "ldrls pc, [pc, r1, lsl #2]" NODE 9 0xc0027c58 0xcaa16c58 0xea000016 4 class: JMP+DIR+UCD behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "b 0x00000000c0027cb8" NODE 10 0xc0027cc0 0xcaa16cc0 0xe89da870 4 class: RET+IND+UCD behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "ldm sp, {r4, r5, r6, r11, sp, pc}" NODE 11 0xc0023e0c 0xcaa12e0c 0x1a000006 4 class: JMP+DIR+CND behavior: DYN+DIR taken_cnt: 6 not_taken_cnt: 7 tgt_cnt: 1 # mnemonic: "bne 0x00000000c0023e2c" NODE 12 0xc0023e28 0xcaa12e28 0xe1b0f00e 4 class: RET+IND+UCD behavior: AT+IND taken_cnt: 7 not_taken_cnt: 0 tgt_cnt: 2 # mnemonic: "movs pc, lr" NODE 13 0x40011478 0xcb262478 0x512fff1e 4 class: RET+IND+CND behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "bxpl lr" NODE 14 0x40016c28 0xcb25dc28 0xe12fff35 4 class: CALL+IND+UCD behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "blx r5" NODE 15 0x4807ea34 0xe36cba34 0xeb000032 4 class: CALL+DIR+UCD behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "bl 0x000000004807eb04" NODE 16 0x4807eb1c 0xe36cbb1c 0xe12fff1e 4 class: RET+IND+UCD behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "bx lr" NODE 17 0x4807ea3c 0xe36cba3c 0xeb000051 4 class: CALL+DIR+UCD behavior: AT+DIR taken_cnt: 1 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "bl 0x000000004807eb88" NODE 18 0x4807eb90 0xe36cbb90 0xebffffea 4 class: CALL+DIR+UCD behavior: AT+DIR taken_cnt: 4 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "bl 0x000000004807eb40" NODE 19 0x4807eb50 0xe36cbb50 0xebfe4be4 4 class: CALL+DIR+UCD behavior: AT+DIR taken_cnt: 6 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "bl 0x0000000048011ae8" NODE 20 0x48011af0 0xe3640af0 0xe5bcf324 4 class: JMP+IND+UCD behavior: AT+DIR taken_cnt: 6 not_taken_cnt: 0 tgt_cnt: 1 # mnemonic: "ldr pc, [r12, #804]! ; 0x324" NODE 21 0xc003f0f4 0xcaa2e0f4 0xa000011 4 class: JMP+DIR+CND behavior: ANT+DIR taken_cnt: 0 not_taken_cnt: 6 tgt_cnt: 0 # mnemonic: "beq 0x00000000c003f140"
- エッジ。つまりノードからノードへどのように飛ぶのかを見ている。ある分岐命令から、次の分岐命令までどのように飛ぶ選択肢があるのかを示しているようだ。
BT9_EDGES #EDGE id src_id dest_id taken br_virt_target br_phy_target inst_cnt EDGE 0 0 1 N 0 - 6 traverse_cnt: 1 EDGE 1 1 1 T 0x40015a8c 0xcb25ea8c 3 traverse_cnt: 61 EDGE 2 1 2 N 0x40015a8c - 0 traverse_cnt: 1 EDGE 3 2 3 T 0x40011464 0xcb262464 3 traverse_cnt: 1 EDGE 4 3 4 T 0xc0023ec0 0xcaa12ec0 19 traverse_cnt: 13 EDGE 5 4 5 N 0xc002591c - 2 traverse_cnt: 13 EDGE 6 5 6 N 0xc00414ae - 4 traverse_cnt: 1 EDGE 7 6 7 T 0xc0027a2c 0xcaa16a2c 9 traverse_cnt: 1 EDGE 8 7 8 T 0xc0027ad4 0xcaa16ad4 2 traverse_cnt: 1 EDGE 9 8 9 T 0xc0027c38 0xcaa16c38 8 traverse_cnt: 1 EDGE 10 9 10 T 0xc0027cb8 0xcaa16cb8 2 traverse_cnt: 1
これから見て分かるのは、
- エッジ1 : ノードID1からノードID1へ、分岐成立
- エッジ2 : ノードID1からノードID2へ、分岐非成立
となるように表現されている。ここで矛盾がないようにこのノードが構成されているわけだが、まあ実際の実行ログから作られているだろうし、矛盾は含まれていないだろう。
- シーケンス
さきほどのエッジを使って、どの命令からどの命令へ移っていくのかが全部リストになっている。リストと言ってもひたすら数字が並んでいる。
1 // Node1 -> Node1 Taken 1 // Node1 -> Node1 Taken 1 // Node1 -> Node1 Taken 1 // Node1 -> Node1 Taken 1 // Node1 -> Node1 Taken 2 // Node1 -> Node2 UnTaken 3 // Node2 -> Node3 Taken 4 // Node3 -> Node4 Taken 5 // Node4 -> Node5 UnTaken 6 // Node5 -> Node6 UnTaken 7 // Node6 -> Node7 Taken 8 // Node7 -> Node8 Taken 9 // Node8 -> Node9 Taken 10 // Node9 -> Node10 Taken 11 12