Co-related branch predictor

Question

This question is taken from Modern Processor Design by Shen and Lipasti.

Consider the following code segment within a loop body for problems 5:

   if (x is even) then                                (branch b1) 
           increment a                                 (b1 taken)
    if (x is a multiple of 10) then                    (branch b2) 
           increment b                                 (b2 taken)

Assume that the following list of 9 values of x is to be processed by 9 iterations of this loop. 8, 9, 10, 11, 12, 20, 29, 30, 31. Note: assume that predictor entries are updated by each dynamic branch before the next dynamic branch accesses the predictor (i.e., there is no update delay).

Assume a two-level branch prediction scheme is used. In addition to the one-bit predictor, a one bit global register (g) is used. Register g stores the direction of the last branch executed (which may not be the same branch as the branch currently being predicted) and is used to index into two separate one-bit branch history tables (BHTs) as shown below.

Depending on the value of g, one of the two BHTs is selected and used to do the normal one-bit prediction. Again, fill in the predicted and actual branch directions of b1 and b2 for nine iterations of the loop. Assume the initial value of g = 0, i.e., NT. For each prediction, depending on the current value of g, only one of the two BHTs is accessed and updated. Hence, some of the entries below should be empty.

Note: assume that predictor entries are updated by each dynamic branch before the next dynamic branch accesses the predictor (i.e. there is no update delay).

              8     9   10    11    12    20    29    30    31

For g=0

b1 predicted : __ N____ T____N___ _ __ T____ T_ __ __ T ______

b1 actual :__ T____ N____T____ N____ T____ T____ N____ T____ N__

b2 predicted: ____ __ N______ __ N____ __ _ _ __ N____ __ __ N

b2 actual :__ N____ N____T____ N____ N____ T____ N____ T____ N__

For g=1

b1 predicted: ____ ____ ____ __ N______ _ _ __ N_ _ __ N

b1 actual :__ T____N____ T____ N____ T____ T____ N____ T____ N__

b2 predicted: __ N______ __ N______ __ T____ N____ __ __ T____ __

b2 actual :__ N____N____ T____ N____N____ T____ N____ T____ N__

What is the logic behind these table values for both g=0 and g=1?