Adaptive branch prediction motivation

  for( i = 0; i < 1000000; i++ ){
      ...
      if( i & 1 ){ ... then_part ... } // conditional branch, alternates
             else{ ... else_part ... } //   between taken and untaken
      ...
  }                                    // loop branch
   

consider trying to predict the conditional branch used to implement
  the if-then-else

  - with 1-bit history => 100% mispredict rate

  - with 2-bit saturating counter => 100% mispredict rate if predictor
                                            starts in wrong weak state
                                  =>  50% mispredict rate otherwise


look at the path history in arriving at the conditional branch

   pseudo-code                 trace:
   -----------                 ------
   loop: ...                          ...             \
         and                           |               |
         cmp                           v               |
         bc  else_part         cond branch // taken    |
                                       |               |
   then_part: ...                      |               |
         br  join_point                |               |  first iteration
                                       v               |
   else_part: ...                 (else_part)          |
                                       |               |
   join_part: ...                      |               |
                                       |               |
         cmp                           v               |
         bc  loop              loop branch // taken   /
                                       v              \
                               cond branch // untaken  |
                                       v               |
                                  (then_part)          |
                                       v               |  second iteration
                               join branch // taken    |
                                       v               |
                               loop branch // taken   /

                                      ...

                                       v              \
                        1      cond branch // taken    |  i_th iteration
                                       v               |
                        1      loop branch // taken   /
                                       |
                                       v              \
                        0      cond branch // untaken  |
                                       v               |  i+1_st iteration
                        1      join branch // taken    |
                                       v               |
                        1      loop branch // taken   /


history of branches (ignoring last iteration with fall through of loop branch)

         cbr   lbr    cbr    jbr   lbr   cbr   lbr    cbr    jbr   lbr
    ... taken taken untaken taken taken taken taken untaken taken taken  ...
          1     1      0      1     1     1     1      0      1     1

  global history:     1101111011... = { 11 + 011 }*


individual branches

  cbr:    1            0                  1            0                 ...
  jbr:                        1                               1          ...
  lbr:          1                   1           1                   1    ...

  cbr alternates:     101010...
  jbr always taken:    1 1 1...   (visited every other iteration)
  lbr strongly taken: 111111...


need way to adaptively predict cbr behavior - remember in history register

  use individual branch history shift register to choose alternate predictor
    cbr, private cbr BHSR = 0 => predict taken
    cbr, private cbr BHSR = 1 => predict untaken

  or use global branch history shift register
    cbr, global BHSR = 011 => predict taken
    cbr, global BHSR = 111 => predict untaken