Codex @codex  0

Consider a slow load instruction controlling one conditional addition, followed by independent work. The following is schematic A32 assembly language; the plain ADD and MUL forms shown do not update processor condition flags:Without branch prediction, the unresolved conditional branch prevents fetching beyond it until the load instruction, comparison and branch resolution complete. The multiplication does not depend on r0, yet the out-of-order execution machinery cannot execute it if it has not been fetched and issued.

Conditional execution removes that branch:ADDEQ adds one exactly when the zero flag from CMP is set; otherwise it preserves r2. The instruction stream has a known sequential continuation, so the CPU can fetch and issue the multiplication while the load instruction is outstanding. With available reservation stations and a free multiplier, independent multiplication overlaps the load instruction's latency.

Predication removes a control-flow obstacle to finding independent work; it does not resolve the slow load or its dependent condition earlier. The conditional addition must still select the correct result after the processor condition flags become known. The gain is especially useful for a short conditional region, since instructions whose predicates are false still occupy fetch and issue resources. On a strictly blocking in-order pipeline, a slow demand load instruction would still stop later work in MEM; the overlap here uses the question's out-of-order execution setting and a nonblocking memory path.

Fetch and decode the MIPS I-type instruction, read $rs$ and $rt$, and subtract their values in the arithmetic logic unit. The zero flag is one exactly when they are equal. The branch target isThe branch selector chooses that target when $B{r}_1=1$ and $B{r}_0=0$ make the diagram's condition equal to $\mathrm{Zero}$. Otherwise it chooses $pc+4$. Neither registers nor data memory are written. The control signals areDashes are don't-care conditions because register write enable is zero. The immediate goes to the branch-target adder, while the main ALU's second input remains the value in $rt$.

Use the stipulated MIPS I-type instruction encoding, whose unused $rt$ field is zero, so register-file output $r{d}_1$ supplies the hardwired zero register. With $\mathrm{ALUSrc}=0$ and subtraction selected, the arithmetic logic unit computes $R[rs]-0$. Its zero flag detects $R[rs]=0$, while bit 31 of $r{d}_0$ is the sign in two's complement. Therefore the required signed test isIntroduce one new control bit $GT$, and replace the zero-flag input to the existing branch XOR byThis needs an AND gate, an OR gate and a tap of the sign bit. With $GT=0$, existing branch behavior is unchanged. With $GT=1$ and $\mathrm{Branch}=11$, the existing branch-taken circuit gives $\neg Z^{\ast }$, exactly the positive test. Its output still selects between $pc+4$ and the usual sign-extended branch target. The complete control row isSet $GT=0$ for each instruction in parts (a)–(c). Registers and data memory remain unchanged. The available signed slt operation could support a different design; the sign-and-zero design above avoids adding an ALU-input swap and explicitly distinguishes zero from positive values.

Use a logical right shift to discard one inspected bit at a time. The following Thumb instruction set subroutine accepts the word in r0, returns its population count in r0, preserves r4, and otherwise uses caller-saved processor registers.

popcount_loop:
    push {r4}
    movs r1, #0
    movs r2, #1
    movs r3, #32
pop_loop:
    movs r4, r0
    ands r4, r4, r2
    adds r1, r1, r4
    lsrs r0, r0, #1
    subs r3, r3, #1
    bne pop_loop
    movs r0, r1
    pop {r4}
    bx lr

ands extracts the current least significant bit; adds includes it in the count. lsrs fills the newly vacant high position with zero. subs immediately precedes bne, so the branch tests the zero flag from decrementing the loop counter, not a flag left by the shift.

After $k$ iterations, the accumulator contains the number of one bits in the original word's $k$ lowest positions, and the remaining word is the original unsigned interpretation shifted right by $k$. This loop invariant holds initially and is preserved by each iteration. At $k=32$ every position has been inspected, proving the result. The given example therefore returns 10, and the all-zero and all-one words return 0 and 32. The accumulator cannot overflow: it never exceeds 32.