HW #3 Solution Given basic block 01 loadAI rarp, 12 => ra // rarp ri ra 02 loadAI rarp, 16 => rb // rarp ri ra rb 03 add ri, ra => rc // rarp ri rb rc 04 sub rb, ri => rd // rarp rb rc rd 05 mult rc, rd => re // rarp rb re 06 multI rb, 2 => rf // rarp re rf 07 add re, rf => rg // rarp rg 08 storeAI rg => rarp, 8 // rarp 09 jmp -> L003 // rarp // Occur: 3 2 2 3 2 2 2 2 2 // Range: 9 3 2 4 2 1 2 1 1 Assume rarp is initially assigned to r0, and ri is initially assigned to r1. Also assume that rarp is needed in the following basic block. Starred instructions are original instructions. Top-down (simple) // r0 r1 r2 r3 (live values at end of instruction) 01 loadI 1000 => r3 // rarp ri - spill 02 store r1 => r3 // rarp - - - *03 loadAI r0, 12 => r2 // rarp - ra - *04 loadAI r0, 16 => r1 // rarp rb ra - 05 loadI 1000 => r3 // rarp rb ra spill 06 load r3 => r3 // rarp rb ra ri *07 add r3, r2 => r2 // rarp rb rc ri 08 loadI 1004 => r3 // rarp rb rc spill 09 store r2 => r3 // rarp rb - - 0A loadI 1000 => r3 // rarp rb - spill 0B load r3 => r2 // rarp rb ri - *0C sub r1, r2 => r2 // rarp rb rd - 0D loadI 1004 => r3 // rarp rb rd spill 0E load r3 => r3 // rarp rb rd rc *0F mult r3, r2 => r2 // rarp rb re - *10 multI r1, 2 => r3 // rarp rb re rf *11 add r2, r3 => r2 // rarp rb rg - *12 storeAI r2 => r0, 8 // rarp rb - - *13 jmp -> L003 // rarp rb - - Assume that the spill area starts at 1000. Top-down (efficient) // r0 r1 r2 r3 (live values at end of instruction) 01 i2i r1, r2 // rarp - ri - *02 loadAI r0, 12 => r3 // rarp - ri ra *03 loadAI r0, 16 => r1 // rarp rb ri ra *04 add r2, r3 => r3 // rarp rb ri rc *05 sub r1, r2 => r2 // rarp rb rd rc *06 mult r3, r2 => r2 // rarp rb re - *07 multI r1, 2 => r3 // rarp - re rf *08 add r2, r3 => r2 // rarp - rg - *09 storeAI r2 => r0, 8 // rarp - - - *0A jmp -> L003 // rarp - - - It is my understanding that the physical registers can be reused if the live range of its value has ended. Bottom-up // r0 r1 r2 r3 (live values at end of instruction) *01 loadAI r0, 12 => r2 // rarp ri ra - *02 loadAI r0, 16 => r3 // rarp ri ra rb *03 add r1, r2 => r2 // rarp ri rc rb *04 sub r3, r1 => r1 // rarp rd rc rb *05 mult r2, r1 => r1 // rarp re - rb *06 multI r3, 2 => r2 // rarp re rf - *07 add r1, r2 => r1 // rarp rg - - *08 storeAI r1 => r0, 8 // rarp *09 jmp -> L003 // rarp