Unit 2.
2 Branch Handling
Types of Branches
A branch in a computer program is an instruction that communicates a device to start implementing several
instructions instead of simply performing the instructions in order. In high-level languages, these are
defined as flow control phases and are established into the language. In assembly programming, branch
instructions are established into a CPU.
Branches are used to transmission control, unconditionally or conditionally, to a stated position of the
program. Unconditional branches are continually taken. In contrast, conditional branches contain a
condition and thus are either taken or not taken, based on either the particular condition is true or false.
Branch Problem:
Holds the concept of Control dependency.(Note: Explain Control dependency in context of Branches)
Approaches/Key Elements to Branch handling
The first method is whether branch delay slots are used. The simple branch handling generally
results in one or two wasted pipeline cycles, known as bubbles, after each branch instruction. With
delayed branching, alternatively, unutilized bubbles are filled until possible with executable
instructions.
The second method is responsible for how unresolved conditional branches are handled. The
processor can use one of three basic techniques. When unresolved conditional branches block the
processing of branches until the particular condition can be computed, it can be concerned with
blocking branch processing.
Early pipelined processors such as the MC 68020, MC 68030, and 80386 employed this ineffective
way of branch handling.
The other method to cope with unresolved conditional branches is to facilitate speculative branch
processing. In this case, for each unresolved conditional branch, a prediction is built for the result
of the condition and processing extends along the guessed path.
The prediction is a guess as to whether the branch is expected to be taken or not, that is, whether
the sequential or the taken path is expected to be followed. After resolution of the specified
condition, the guess is determined. If it proves right, the process is extended.
If the guess is wrong, all speculatively executed instructions are rejected and the execution is
sustained along the right path. Speculative branch processing is the prevailing approach at
present. It is widely used in recent ILP-processors, especially in superscalar ones.
The last circumstance for handling unresolved conditional branches is to follow both possible
implementation paths and reject the incorrect path after resolution of the particular condition. This
method is known as multiway branching and has been used in some unproved or prototype VLIW
machines.
The third and final method of branch handling is whether the architecture supports appropriate
means to prevent conditional branches. If there are such means applicable, it can have guarded
execution. In a sense, control dependencies are restored by data dependencies.
Although guarded execution probably has the highest performance potential among the schemes
overviewed, it also has crucial drawbacks. It requires either a significant extension to or a
redefinition of the instruction set architecture. In VLIW architectures, although a few main-line
architectures also provide guarded instructions to some extent such as the HP PA, DEC Alpha, and
SPARC V9 architectures.
Delayed Branching:
When branches are processed by a pipeline simply, after each taken branch, at least one cycle remains
unutilized. This is because of the assembly line-like apathy of pipelining. Instruction slots following
branches are known as branch delay slots.
Delay slots can also appear following load instructions; these are defined load delay slots. Branch
delay slots are wasted during traditional execution. However, when delayed branching is employed,
these slots can be at least partly used.
'B~c.h -e~dtemi-
·12{x~ ~~ed./~
u.
4 f~!. -u. t~J.
~e- u
C ar, e.- m..J WY"Y> e_ Oe.s.s )
C--~[Link].--fhe n--u~g _,
f
~'r.)e_~
_,
j__
UJ..l.¼-h
11
ocfe,~
ofhe_ e)('e~
~·
-eY..~ ari4
~e)efe_
t~
gtaf-q~
~crne
-[Link]~
ti',~"-Wj
bLl .
- A • •
t NT
-r
0
I
o , T
n C-_V'i e.£.£ ro·r
dw ·c-~ tc-vJJ:~
~- 4
ta.t(Ll;\
t~..tt,
k?1&1Ac...h
CU'l~ ~ty! .h \3><1..~ch Tu~tcVJ 1i'lt\en [Link].
k no eiJ bo u.1 cct cl e.u,.d~ g, € •
0 r.-ree•
.. .
· Tu .:tw.. t.L){'_ Q.., "'4 :tfl c.t- t Y"l [Link]. "-"' J
J.& Ill¾ ttu Au't{J1f Ut'n 8 H,- · CB 'I-€! "t_l-J. '.stJ,\.I [Link] e ) .
I
lr>o~ R, r R':l.. -~ .~
A-d..cl Rr, R1 ,. t
0U-h)f Ii
Taker,
bHl nM o 1a::ket) t ---&rne_g
Nor t ~ !:> er ..tune.,.
®
f) r~ [Link].t,-T):-
. - - - - - - - - - - - - - - - ~~h
tI _gt ~ ~ ( ~ ~
ro [Link]<~u ,,
Wea-kl~ YlOt- 1a)<~
0 '
.t{o~
C c,
A~_gt_t me lDb ~ pt OD 1-unE,j
~~um~J~or~ ~,]
t0 hV) r~tum B~
,-J _, w~a
f<.,c;:O t Ni'
~,~I N,- wr-J.-?> A
R,~~ 3 NT NT"J_ __, p>ei:l • .-r Oht
NT
~Nr .., t1
, t- .[Link] et
l
to)
!A&~ .[Link] e o B'c)-co,~ c Cc:J-roec-t-
X
W- a.t
' ._/"
[Link].e.
l})t,t-
ct
.,&ke..n H&r) t..--e._
--cl n .[Link] +o i e. e- e-
r~-t [Link]
\
I
I 9 c- ,xfo
-
2-~ [Link]) 4! q X <:f Cf
er~ ~
-;:
t• ' X• r(')x
t'lftln~
o..d..ch-{'~_s ~ •etUTD
ooo at)
'
litlb
De:> I t.,_ )-e e:> I
ot o
a, I I
0
~\.J So o
80 t<) ,
t)
0 (fot3') ,co I
t()t I '-----'
~r &,oo -0
rt o • 90 b 'O
~i; to~~
tr! I
~.[Link]+'~
P->TA-C
t~t')~~~e_f
A c-ces..~ Ca~e)
gFc_/a.f 4 r~w
ca1 +...- NT ,'.I,. nch.o..& st tJ o 01 u Cl.,.,_ m aJ ')1'/-dJ Y> ecJ
4-l.---__,
,VlgJy--rl o..&J ,F'f'
,----------....:---+--=____:_--==--....1..:~ ~ --_!---f- F)
A
R
l
Ut~
c_on-htln~ F.'t 'i
btrtll')cl, a..d.d')-t.S.s
•
:[Link]
tt1~e.t-- a..n& ..u
a~ci!secJ qsS o~a.t1ve1d
¥l'Y)
l,
w en C'f_c.[Link] :InrlY-n B~ Y) tici4 'rtl !
anol en~, tn . B'frt~ 1 ~ v; B iA ,ter~ei/ · •
t:1 t.U-l:H, _ 'J__ ~., cJ,.-; h t) i D '"i h t.. .-! a_rn e.
~LJ-f~
,.U {m~l-en,o,_!ed cg q • ~ - ~ I 1:1- o or ·
~ttu C(~~ow(tu.t Ca_d-1e~ ,-
1
~"Tl c_ seJi.e,-t')ef-
[Link] oUUl {oY)I
----, ti PA
1 f+l Brt BTI It- 1
wh~ f F-A -=- M.w. i.n BT I~ -the.t"> BT I an.d $ii t
t -r d e ~
1
Cf <>-L fp<l, e_cl & [Link]
~i-t
,!.!. u, "4 ""
BTh+
'l)ex t- If'-A , r -- -,
Bm
11 1'
#' f r-
\-tl_r) l1.h U\ 11l;tte~
C1 nc1[r-,,_q cU " rttf = ""1 -t1o.. ,, " .
o{ b'>et.,.__.,
eite~ ~<'Ir,--,< at.M ¼<--
h-t- ;tD,L b ~ M :ta..\=>. -ifie >-tlu..Q.l--!':t_ mo.c!U
£ho U--t--t tht ~ctU:rn 1- m ll~• fe_rf-o ~an
q~' e_ •
r"f ec..n'ni tt e_ t-o ~u__ ~~... ,
q) 2Wfr. , a) f'!)ttkl-i "-"":'I LMn ~•"'-'1
bl~''-- u a
t-) fh~ Y1 cJ,-, ¾a~ .but1f- y r- _ _
w /o !:,..,. ne,h f-,..ul.l ,:kn-,, 1 fer<>-1-, cl ","-8. 11 ';t- k ri w uDhc..t- to
,--,e)d:- !..! vctu ;:n, e. Pl- L-U cl e<--1 d '-' ,,_.,
a ~c!.f+l~ o'Y' b')-0.Y)c..h re.1 .
~-1.»-, t.t) [Link]-e__cJ- b~n ci, aJl:..o½ r t-rv, e.q / .Je_t.[Link](
"f\.C fy-n f'° rn ::f-\rl e, W )-() r~ ct C / We_ c_a_U
Jl- b~C-h ~[Link]-tYO ~ .
#'Mltlti b,-,,.,, e.J.l~ _ \i
I both ",i;j""-"+iae 11 °""' e<tj+, V Q~ \ '
p,1.w1ecJ , w~ e,, Ctln&.[Link]'tm -fer -:tl-,e r,._,.,u, 'ife#
~e,s o l~ r pc:L#) ..u DJn-ec_t- be..urroe_g eu_/~~i--
fo .,- .:tlu, f\'J f I e- f e_ ct , . , u/-,.,,J \--e./f-nee/ a.i IM 1
@v:/ '~)..,
, . i
~~~[Link]
I
~,U€YJ~ 1 f C£;;nJ)'-f/ona1 I:,,_,, l'1 ch
f_y_ ~ T I Y ) €..q geto~ n Cao,, ctl~o
flU.h q~ , H01~ niW:ttll..[Link]
~~Y)uJ~ g})culd ~11,ow 0
cU~r_o~ ~
~LLUf~te_U t.u,~€)fl!Je.d h~ncne.a
tP-ltt
~ -- ~ b~- ® 1
whlc..h
- -r
D'()e ..,U
(FA,._
CZJ"6oe~ r C:.e:i-oec-t-
-
M<U:fl~c1,,
-
QXeLl..1.±e.d
tFALf
an..ol
q ri Cor<l Ft&~, b , ~ Tu I><) ~-....nt-- ~" Q"'"
CanuJJ etj,
Guarded execution
Guarded execution is a means to eliminate; at least partly, conditional branches. The idea is to introduce
conditional operate instructions into the architecture and use them to replace conditional branches.
Conditional operate instructions are called guarded instructions. A guarded instruction consists of two parts,
a conditional part called the guard and an operational part which is a traditional instruction. It can be
expressed, for instance, in the form −
(guard) instruction
The execution of guarded instruction depends on the following condition: if the specified guard is true, the
associated instruction will be executed; if the guard turns out to be false, the instruction behaves like a NOP.
For instance, the α architecture provides conditional move instructions which are guarded instructions, with
the following syntax and semantics (DEC, 1992) −
cmovxx [Link], [Link], [Link]
cmovxx [Link], #[Link], [Link]
where
xx indicates a condition
[Link] is an integer, read-only 64-bit operand stored in register ra
[Link] is an integer, read-only 64-bit operand stored in register rb
[Link] is an integer, write-only 64-bit operand stored in register rc
#[Link] is an integer 64-bit literal
This instruction operates as follows. Register ra is tested.
The instruction mnemonics specify the condition of the guarded execution −
cmoveq // cmove if the contents of register ra are equal to zero
cmovge // cmove if the contents of register ra are greater than or equal to zero
cmovgt // cmove if the contents of register ra are greater than zero
cmovlbc // cmove if the low bit of register ra is clear
cmovlbs // cmove if the low bit of register ra is set
cmovle // cmove if the contents of register ra are less than or equal to zero
cmovlt // cmove if the contents of register ra are less than zero
cmovne // cmove if the contents of register ra are not equal to zero
Forward conditional branches can be eliminated by using guarded instructions with the opposite condition as
specified in the corresponding conditional branch. For instance, consider the code sequence
beq ra, label // if (ra)=0 branch to ‘label’
or rb, rb, rc // else move (rb) into rc
The SPARC V9 (1994) also offers some similar conditional move instructions. The HP Precision
Architecture (1985) introduced guarded instructions in a more comprehensive way than the DEC α. Here, all
integer operate instructions are guarded instructions of the form
[Link] operands
The given condition (cond) relates to the result of the operation. If the specified condition is true, for
instance, the result is positive, the following instructions will be nullified.
There are two types of guarding execution such as full guarding and restricted guarding. In full guarding all
instructions are assumed to be guarded, whereas in restricted guarding only operating instructions (ALU
instructions) have a guarded form.
This restricted form of guarding takes into account the fact that in existing architectures the instruction code
space is usually squeezed and in most cases only a few additional bits are available for specifying guard
conditions.