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

1 files changed, 50 insertions, 13 deletions

diff --git a/src/cpu/o3/bpred_unit_impl.hh b/src/cpu/o3/bpred_unit_impl.hh
index e0292e232..8502f342c 100644
--- a/src/cpu/o3/bpred_unit_impl.hh
+++ b/src/cpu/o3/bpred_unit_impl.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-2005 The Regents of The University of Michigan
  * All rights reserved.
  *
@@ -166,12 +178,11 @@ BPredUnit<Impl>::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid)
         BPUncond(bp_history);
     } else {
         ++condPredicted;
-
         pred_taken = BPLookup(pc.instAddr(), bp_history);
 
-        DPRINTF(Fetch, "BranchPred: [tid:%i]: Branch predictor predicted %i "
-                "for PC %s\n",
-                tid, pred_taken, inst->pcState());
+        DPRINTF(Fetch, "BranchPred:[tid:%i]: [sn:%i] Branch predictor"
+                " predicted %i for PC %s\n",
+                tid, inst->seqNum,  pred_taken, inst->pcState());
     }
 
     DPRINTF(Fetch, "BranchPred: [tid:%i]: [sn:%i] Creating prediction history "
@@ -231,6 +242,15 @@ BPredUnit<Impl>::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid)
                 DPRINTF(Fetch, "BranchPred: [tid:%i]: BTB doesn't have a "
                         "valid entry.\n",tid);
                 pred_taken = false;
+                // The Direction of the branch predictor is altered because the
+                // BTB did not have an entry
+                // The predictor needs to be updated accordingly
+                if (!inst->isCall() && !inst->isReturn()) {
+                      BPBTBUpdate(pc.instAddr(), bp_history);
+                      DPRINTF(Fetch, "BranchPred: [tid:%i]:[sn:%i] BPBTBUpdate"
+                              " called for %s\n",
+                              tid, inst->seqNum, inst->pcState());
+                }
                 TheISA::advancePC(target, inst->staticInst);
             }
 
@@ -261,7 +281,7 @@ BPredUnit<Impl>::update(const InstSeqNum &done_sn, ThreadID tid)
         // Update the branch predictor with the correct results.
         BPUpdate(predHist[tid].back().pc,
                  predHist[tid].back().predTaken,
-                 predHist[tid].back().bpHistory);
+                 predHist[tid].back().bpHistory, false);
 
         predHist[tid].pop_back();
     }
@@ -356,12 +376,15 @@ BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn,
         }
 
         BPUpdate((*hist_it).pc, actually_taken,
-                 pred_hist.front().bpHistory);
-
-        BTB.update((*hist_it).pc, corrTarget, tid);
-
-        DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i] "
-                "PC %s.\n", tid, (*hist_it).seqNum, (*hist_it).pc);
+                 pred_hist.front().bpHistory, true);
+        if (actually_taken){
+            DPRINTF(Fetch,"BranchPred: [tid: %i] BTB Update called for [sn:%i]"
+                           " PC: %s\n", tid,(*hist_it).seqNum, (*hist_it).pc);
+            BTB.update((*hist_it).pc, corrTarget, tid);
+        }
+        DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i]"
+                       " PC %s  Actually Taken: %i\n", tid, (*hist_it).seqNum,
+                       (*hist_it).pc, actually_taken);
 
         pred_hist.erase(hist_it);
 
@@ -407,12 +430,26 @@ BPredUnit<Impl>::BPLookup(Addr instPC, void * &bp_history)
 
 template <class Impl>
 void
-BPredUnit<Impl>::BPUpdate(Addr instPC, bool taken, void *bp_history)
+BPredUnit<Impl>::BPBTBUpdate(Addr instPC, void * &bp_history)
+{
+    if (predictor == Local) {
+        return localBP->BTBUpdate(instPC, bp_history);
+    } else if (predictor == Tournament) {
+        return tournamentBP->BTBUpdate(instPC, bp_history);
+    } else {
+        panic("Predictor type is unexpected value!");
+    }
+}
+
+template <class Impl>
+void
+BPredUnit<Impl>::BPUpdate(Addr instPC, bool taken, void *bp_history,
+                 bool squashed)
 {
     if (predictor == Local) {
         localBP->update(instPC, taken, bp_history);
     } else if (predictor == Tournament) {
-        tournamentBP->update(instPC, taken, bp_history);
+        tournamentBP->update(instPC, taken, bp_history, squashed);
     } else {
         panic("Predictor type is unexpected value!");
     }