BP: Fix several Branch Predictor issues.

1. Updates the Branch Predictor correctly to the state
   just after a mispredicted branch, if a squash occurs.
2. If a BTB does not find an entry, the branch is predicted not taken.
   The global history is modified to correctly reflect this prediction.
3. Local history is now updated at the fetch stage instead of
   execute stage.
4. In the Update stage of the branch predictor the local predictors are
   now correctly updated according to the state of local history during
   fetch stage.

This patch also improves performance by as much as 17% on some benchmarks

4 files changed, 108 insertions, 35 deletions

diff --git a/src/cpu/pred/2bit_local.cc b/src/cpu/pred/2bit_local.cc
index dc8cf50b7..4d18c419b 100644
--- a/src/cpu/pred/2bit_local.cc
+++ b/src/cpu/pred/2bit_local.cc
@@ -79,6 +79,14 @@ LocalBP::reset()
     }
 }
 
+void
+LocalBP::BTBUpdate(Addr &branch_addr, void * &bp_history)
+{
+// Place holder for a function that is called to update predictor history when
+// a BTB entry is invalid or not found.
+}
+
+
 bool
 LocalBP::lookup(Addr &branch_addr, void * &bp_history)
 {
diff --git a/src/cpu/pred/2bit_local.hh b/src/cpu/pred/2bit_local.hh
index 8b7bb8463..01a0b64db 100644
--- a/src/cpu/pred/2bit_local.hh
+++ b/src/cpu/pred/2bit_local.hh
@@ -1,4 +1,16 @@
 /*
+ * Copyright (c) 2011 ARM Limited
+ * All rights reserved
+ *
+ * The license below extends only to copyright in the software and shall
+ * not be construed as granting a license to any other intellectual
+ * property including but not limited to intellectual property relating
+ * to a hardware implementation of the functionality of the software
+ * licensed hereunder.  You may use the software subject to the license
+ * terms below provided that you ensure that this notice is replicated
+ * unmodified and in its entirety in all distributions of the software,
+ * modified or unmodified, in source code or in binary form.
+ *
  * Copyright (c) 2004-2006 The Regents of The University of Michigan
  * All rights reserved.
  *
@@ -65,6 +77,15 @@ class LocalBP
     bool lookup(Addr &branch_addr, void * &bp_history);
 
     /**
+     * Updates the branch predictor to Not Taken if a BTB entry is
+     * invalid or not found.
+     * @param branch_addr The address of the branch to look up.
+     * @param bp_history Pointer to any bp history state.
+     * @return Whether or not the branch is taken.
+     */
+    void BTBUpdate(Addr &branch_addr, void * &bp_history);
+
+    /**
      * Updates the branch predictor with the actual result of a branch.
      * @param branch_addr The address of the branch to update.
      * @param taken Whether or not the branch was taken.
diff --git a/src/cpu/pred/tournament.cc b/src/cpu/pred/tournament.cc
index 9608dc011..3adafb608 100644
--- a/src/cpu/pred/tournament.cc
+++ b/src/cpu/pred/tournament.cc
@@ -1,4 +1,16 @@
 /*
+ * Copyright (c) 2011 ARM Limited
+ * All rights reserved
+ *
+ * The license below extends only to copyright in the software and shall
+ * not be construed as granting a license to any other intellectual
+ * property including but not limited to intellectual property relating
+ * to a hardware implementation of the functionality of the software
+ * licensed hereunder.  You may use the software subject to the license
+ * terms below provided that you ensure that this notice is replicated
+ * unmodified and in its entirety in all distributions of the software,
+ * modified or unmodified, in source code or in binary form.
+ *
  * Copyright (c) 2004-2006 The Regents of The University of Michigan
  * All rights reserved.
  *
@@ -146,6 +158,18 @@ TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx)
         (localHistoryTable[local_history_idx] << 1);
 }
 
+
+void
+TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history)
+{
+    unsigned local_history_idx = calcLocHistIdx(branch_addr);
+    //Update Global History to Not Taken
+    globalHistory = globalHistory & (globalHistoryMask - 1);
+    //Update Local History to Not Taken
+    localHistoryTable[local_history_idx] =
+       localHistoryTable[local_history_idx] & (localPredictorMask - 1);
+}
+
 bool
 TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
 {
@@ -174,6 +198,7 @@ TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
     history->localPredTaken = local_prediction;
     history->globalPredTaken = global_prediction;
     history->globalUsed = choice_prediction;
+    history->localHistory = local_predictor_idx;
     bp_history = (void *)history;
 
     assert(globalHistory < globalPredictorSize &&
@@ -184,30 +209,22 @@ TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
     // all histories.
     if (choice_prediction) {
         if (global_prediction) {
-//            updateHistoriesTaken(local_history_idx);
-//            globalCtrs[globalHistory].increment();
-//            localCtrs[local_history_idx].increment();
             updateGlobalHistTaken();
+            updateLocalHistTaken(local_history_idx);
             return true;
         } else {
-//            updateHistoriesNotTaken(local_history_idx);
-//            globalCtrs[globalHistory].decrement();
-//            localCtrs[local_history_idx].decrement();
             updateGlobalHistNotTaken();
+            updateLocalHistNotTaken(local_history_idx);
             return false;
         }
     } else {
         if (local_prediction) {
-//            updateHistoriesTaken(local_history_idx);
-//            globalCtrs[globalHistory].increment();
-//            localCtrs[local_history_idx].increment();
             updateGlobalHistTaken();
+            updateLocalHistTaken(local_history_idx);
             return true;
         } else {
-//            updateHistoriesNotTaken(local_history_idx);
-//            globalCtrs[globalHistory].decrement();
-//            localCtrs[local_history_idx].decrement();
             updateGlobalHistNotTaken();
+            updateLocalHistNotTaken(local_history_idx);
             return false;
         }
     }
@@ -222,16 +239,18 @@ TournamentBP::uncondBr(void * &bp_history)
     history->localPredTaken = true;
     history->globalPredTaken = true;
     history->globalUsed = true;
+    history->localHistory = invalidPredictorIndex;
     bp_history = static_cast<void *>(history);
 
     updateGlobalHistTaken();
 }
 
 void
-TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history)
+TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history,
+                     bool squashed)
 {
     unsigned local_history_idx;
-    unsigned local_predictor_idx;
+    unsigned local_predictor_idx M5_VAR_USED;
     unsigned local_predictor_hist;
 
     // Get the local predictor's current prediction
@@ -259,33 +278,34 @@ TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history)
         // resolution of the branch.  Global history is updated
         // speculatively and restored upon squash() calls, so it does not
         // need to be updated.
+        unsigned old_local_pred_index = history->localHistory
+                 & localPredictorMask;
         if (taken) {
-               localCtrs[local_predictor_idx].increment();
                globalCtrs[history->globalHistory].increment();
-
-               updateLocalHistTaken(local_history_idx);
+               if (old_local_pred_index != invalidPredictorIndex) {
+                      localCtrs[old_local_pred_index].increment();
+               }
         } else {
-               localCtrs[local_predictor_idx].decrement();
                globalCtrs[history->globalHistory].decrement();
-
-               updateLocalHistNotTaken(local_history_idx);
+               if (old_local_pred_index != invalidPredictorIndex) {
+                      localCtrs[old_local_pred_index].decrement();
+               }
        }
 
-       bool mispredict = false;
-
-       //global predictor used and mispredicted
-       if (history->globalUsed && history->globalPredTaken != taken)
-           mispredict = true;
-       //local predictor used and mispredicted
-       else if (!history->globalUsed && history->localPredTaken != taken)
-           mispredict = true;
-
-       if (mispredict) {
+       if (squashed) {
            if (taken) {
-              globalHistory = globalHistory | 1;
+              globalHistory = (history->globalHistory << 1) | 1;
+              globalHistory = globalHistory & globalHistoryMask;
+              if (history->localHistory != invalidPredictorIndex)
+                  localHistoryTable[local_history_idx] =
+                     (history->localHistory << 1) | 1;
            } else {
-              unsigned mask = globalHistoryMask - 1;
-              globalHistory = globalHistory & mask;
+              globalHistory = (history->globalHistory << 1);
+              globalHistory = globalHistory & globalHistoryMask;
+              if (history->localHistory != invalidPredictorIndex) {
+                  localHistoryTable[local_history_idx] =
+                     history->localHistory << 1;
+              }
            }
 
         }
diff --git a/src/cpu/pred/tournament.hh b/src/cpu/pred/tournament.hh
index 96bd43ed6..f9df2a61d 100644
--- a/src/cpu/pred/tournament.hh
+++ b/src/cpu/pred/tournament.hh
@@ -1,4 +1,16 @@
 /*
+ * Copyright (c) 2011 ARM Limited
+ * All rights reserved
+ *
+ * The license below extends only to copyright in the software and shall
+ * not be construed as granting a license to any other intellectual
+ * property including but not limited to intellectual property relating
+ * to a hardware implementation of the functionality of the software
+ * licensed hereunder.  You may use the software subject to the license
+ * terms below provided that you ensure that this notice is replicated
+ * unmodified and in its entirety in all distributions of the software,
+ * modified or unmodified, in source code or in binary form.
+ *
  * Copyright (c) 2004-2006 The Regents of The University of Michigan
  * All rights reserved.
  *
@@ -79,15 +91,24 @@ class TournamentBP
      * @param bp_history Pointer that will be set to the BPHistory object.
      */
     void uncondBr(void * &bp_history);
-
+    /**
+     * Updates the branch predictor to Not Taken if a BTB entry is
+     * invalid or not found.
+     * @param branch_addr The address of the branch to look up.
+     * @param bp_history Pointer to any bp history state.
+     * @return Whether or not the branch is taken.
+     */
+    void BTBUpdate(Addr &branch_addr, void * &bp_history);
     /**
      * Updates the branch predictor with the actual result of a branch.
      * @param branch_addr The address of the branch to update.
      * @param taken Whether or not the branch was taken.
      * @param bp_history Pointer to the BPHistory object that was created
      * when the branch was predicted.
+     * @param squashed is set when this function is called during a squash
+     * operation.
      */
-    void update(Addr &branch_addr, bool taken, void *bp_history);
+    void update(Addr &branch_addr, bool taken, void *bp_history, bool squashed);
 
     /**
      * Restores the global branch history on a squash.
@@ -149,11 +170,14 @@ class TournamentBP
         static int newCount;
 #endif
         unsigned globalHistory;
+        unsigned localHistory;
         bool localPredTaken;
         bool globalPredTaken;
         bool globalUsed;
     };
 
+    /** Flag for invalid predictor index */
+    static const int invalidPredictorIndex = -1;
     /** Local counters. */
     std::vector<SatCounter> localCtrs;