GATE CS 2008 Q77 — Instruction Pipelining

In a pipelined processor with a branch delay slot, the instruction placed in the delay slot is always executed, regardless of whether the branch is taken or not.

To safely move an instruction into the branch delay slot from before the branch without modifying the program behavior, the following conditions must be met:

1. Data Dependency: No instruction remaining before the branch can depend on the instruction moved to the delay slot.
2. Branch Dependency: The branch condition must not depend on the instruction in the delay slot.

Let's analyze the instructions:

• I1 cannot be moved because I3 depends on $R2$ produced by I1.
• I2 cannot be moved because I4 depends on $R4$ produced by I2.
• I3 cannot be moved because the BRANCH condition depends on $R1$ produced by I3.
• I4 can be safely moved because no instruction between I4 and the BRANCH depends on it, and it does not affect the branch condition. Since I4 was executed before the branch in the original sequence, executing it in the delay slot (where it always executes) preserves the program semantics.

Therefore, I4 is the only instruction that can legitimately occupy the delay slot.