BPred: Fix RAS to handle predicated call/return instructions.

Change RAS to fix issues with predicated call/return instructions.
Handled all cases in the life of a predicated call and return instruction.

4 files changed, 123 insertions, 57 deletions

diff --git a/src/cpu/o3/bpred_unit.hh b/src/cpu/o3/bpred_unit.hh
index d3ae93b38..673472b69 100644
--- a/src/cpu/o3/bpred_unit.hh
+++ b/src/cpu/o3/bpred_unit.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.
  *
@@ -196,7 +208,7 @@ class BPredUnit
                          ThreadID _tid)
             : seqNum(seq_num), pc(instPC), RASTarget(0), RASIndex(0),
               tid(_tid), predTaken(pred_taken), usedRAS(0),
-              wasCall(0), bpHistory(bp_history)
+              wasCall(0), wasReturn(0), validBTB(0), bpHistory(bp_history)
         {}
 
         bool operator==(const PredictorHistory &entry) const {
@@ -227,6 +239,10 @@ class BPredUnit
         /** Whether or not the instruction was a call. */
         bool wasCall;
 
+        /** Whether or not the instruction was a return. */
+        bool wasReturn;
+        /** Whether or not the instruction had a valid BTB entry. */
+        bool validBTB;
         /** Pointer to the history object passed back from the branch
          * predictor.  It is used to update or restore state of the
          * branch predictor.
diff --git a/src/cpu/o3/bpred_unit_impl.hh b/src/cpu/o3/bpred_unit_impl.hh
index 8502f342c..1e75de90c 100644
--- a/src/cpu/o3/bpred_unit_impl.hh
+++ b/src/cpu/o3/bpred_unit_impl.hh
@@ -196,7 +196,7 @@ BPredUnit<Impl>::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid)
     if (pred_taken) {
         if (inst->isReturn()) {
             ++usedRAS;
-
+            predict_record.wasReturn = true;
             // If it's a function return call, then look up the address
             // in the RAS.
             TheISA::PCState rasTop = RAS[tid].top();
@@ -231,6 +231,7 @@ BPredUnit<Impl>::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid)
 
             if (BTB.valid(pc.instAddr(), tid)) {
                 ++BTBHits;
+                predict_record.validBTB = true;
 
                 // If it's not a return, use the BTB to get the target addr.
                 target = BTB.lookup(pc.instAddr(), tid);
@@ -250,12 +251,17 @@ BPredUnit<Impl>::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid)
                       DPRINTF(Fetch, "BranchPred: [tid:%i]:[sn:%i] BPBTBUpdate"
                               " called for %s\n",
                               tid, inst->seqNum, inst->pcState());
+                } else if (inst->isCall() && !inst->isUncondCtrl()) {
+                      RAS[tid].pop();
                 }
                 TheISA::advancePC(target, inst->staticInst);
             }
 
         }
     } else {
+        if (inst->isReturn()) {
+           predict_record.wasReturn = true;
+        }
         TheISA::advancePC(target, inst->staticInst);
     }
 
@@ -302,12 +308,13 @@ BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn, ThreadID tid)
 
             RAS[tid].restore(pred_hist.front().RASIndex,
                              pred_hist.front().RASTarget);
-        } else if (pred_hist.front().wasCall) {
-            DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing speculative entry "
-                    "added to the RAS.\n",tid);
-
-            RAS[tid].pop();
-        }
+        } else if(pred_hist.front().wasCall && pred_hist.front().validBTB) {
+                 // Was a call but predicated false. Pop RAS here
+                 DPRINTF(Fetch, "BranchPred: [tid: %i] Squashing"
+                         "  Call [sn:%i] PC: %s Popping RAS\n", tid,
+                         pred_hist.front().seqNum, pred_hist.front().pc);
+                 RAS[tid].pop();
+           }
 
         // This call should delete the bpHistory.
         BPSquash(pred_hist.front().bpHistory);
@@ -377,18 +384,46 @@ BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn,
 
         BPUpdate((*hist_it).pc, actually_taken,
                  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);
+        if (actually_taken) {
+            if (hist_it->wasReturn && !hist_it->usedRAS) {
+                 DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted"
+                           "  return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
+                            hist_it->pc);
+                 RAS[tid].pop();
+            }
+           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);
+
+        } else {
+           //Actually not Taken
+           if (hist_it->usedRAS) {
+                DPRINTF(Fetch,"BranchPred: [tid: %i] Incorrectly predicted"
+                           "  return [sn:%i] PC: %s Restoring RAS\n", tid,
+                           hist_it->seqNum, hist_it->pc);
+                DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS"
+                               " to: %i, target: %s.\n", tid,
+                              hist_it->RASIndex, hist_it->RASTarget);
+                RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
+
+           } else if (hist_it->wasCall && hist_it->validBTB) {
+                 //Was a Call but predicated false. Pop RAS here
+                 DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted"
+                           "  Call [sn:%i] PC: %s Popping RAS\n", tid,
+                           hist_it->seqNum, hist_it->pc);
+                 RAS[tid].pop();
+           }
         }
         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);
+                       " PC %s  Actually Taken: %i\n", tid, hist_it->seqNum,
+                       hist_it->pc, actually_taken);
 
         pred_hist.erase(hist_it);
 
-        DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid, predHist[tid].size());
+        DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid,
+                                         predHist[tid].size());
     }
 }
 
diff --git a/src/cpu/o3/commit_impl.hh b/src/cpu/o3/commit_impl.hh
index b4cc4b017..bb82c37a8 100644
--- a/src/cpu/o3/commit_impl.hh
+++ b/src/cpu/o3/commit_impl.hh
@@ -1232,6 +1232,10 @@ DefaultCommit<Impl>::commitHead(DynInstPtr &head_inst, unsigned inst_num)
         delete head_inst->traceData;
         head_inst->traceData = NULL;
     }
+    if (head_inst->isReturn()) {
+        DPRINTF(Commit,"Return Instruction Committed [sn:%lli] PC %s \n",
+                        head_inst->seqNum, head_inst->pcState());
+    }
 
     // Update the commit rename map
     for (int i = 0; i < head_inst->numDestRegs(); i++) {
diff --git a/src/cpu/pred/tournament.cc b/src/cpu/pred/tournament.cc
index 3adafb608..b6320ca8a 100644
--- a/src/cpu/pred/tournament.cc
+++ b/src/cpu/pred/tournament.cc
@@ -258,59 +258,70 @@ TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history,
     local_predictor_hist = localHistoryTable[local_history_idx];
     local_predictor_idx = local_predictor_hist & localPredictorMask;
 
-    // Update the choice predictor to tell it which one was correct if
-    // there was a prediction.
     if (bp_history) {
         BPHistory *history = static_cast<BPHistory *>(bp_history);
-        if (history->localPredTaken != history->globalPredTaken) {
-            // If the local prediction matches the actual outcome,
-            // decerement the counter.  Otherwise increment the
-            // counter.
-            if (history->localPredTaken == taken) {
-                choiceCtrs[history->globalHistory].decrement();
-            } else if (history->globalPredTaken == taken){
-                choiceCtrs[history->globalHistory].increment();
-            }
-
-        }
-
-        // Update the counters and local history with the proper
-        // resolution of the branch.  Global history is updated
-        // speculatively and restored upon squash() calls, so it does not
-        // need to be updated.
+        // Update may also be called if the Branch target is incorrect even if
+        // the prediction is correct. In that case do not update the counters.
+        bool historyPred = false;
         unsigned old_local_pred_index = history->localHistory
-                 & localPredictorMask;
-        if (taken) {
-               globalCtrs[history->globalHistory].increment();
-               if (old_local_pred_index != invalidPredictorIndex) {
-                      localCtrs[old_local_pred_index].increment();
-               }
+                      & localPredictorMask;
+        if (history->globalUsed) {
+           historyPred = history->globalPredTaken;
         } else {
-               globalCtrs[history->globalHistory].decrement();
-               if (old_local_pred_index != invalidPredictorIndex) {
-                      localCtrs[old_local_pred_index].decrement();
-               }
-       }
-
-       if (squashed) {
-           if (taken) {
-              globalHistory = (history->globalHistory << 1) | 1;
-              globalHistory = globalHistory & globalHistoryMask;
-              if (history->localHistory != invalidPredictorIndex)
-                  localHistoryTable[local_history_idx] =
+           historyPred = history->localPredTaken;
+        }
+        if (historyPred != taken || !squashed) {
+            // Update the choice predictor to tell it which one was correct if
+            // there was a prediction.
+            if (history->localPredTaken != history->globalPredTaken) {
+                 // If the local prediction matches the actual outcome,
+                 // decerement the counter.  Otherwise increment the
+                 // counter.
+                 if (history->localPredTaken == taken) {
+                     choiceCtrs[history->globalHistory].decrement();
+                 } else if (history->globalPredTaken == taken) {
+                     choiceCtrs[history->globalHistory].increment();
+                 }
+
+             }
+
+             // Update the counters and local history with the proper
+             // resolution of the branch.  Global history is updated
+             // speculatively and restored upon squash() calls, so it does not
+             // need to be updated.
+             if (taken) {
+                  globalCtrs[history->globalHistory].increment();
+                  if (old_local_pred_index != invalidPredictorIndex) {
+                          localCtrs[old_local_pred_index].increment();
+                  }
+             } else {
+                  globalCtrs[history->globalHistory].decrement();
+                  if (old_local_pred_index != invalidPredictorIndex) {
+                          localCtrs[old_local_pred_index].decrement();
+                  }
+             }
+        }
+        if (squashed) {
+             if (taken) {
+                globalHistory = (history->globalHistory << 1) | 1;
+                globalHistory = globalHistory & globalHistoryMask;
+                if (old_local_pred_index != invalidPredictorIndex) {
+                    localHistoryTable[old_local_pred_index] =
                      (history->localHistory << 1) | 1;
-           } else {
-              globalHistory = (history->globalHistory << 1);
-              globalHistory = globalHistory & globalHistoryMask;
-              if (history->localHistory != invalidPredictorIndex) {
-                  localHistoryTable[local_history_idx] =
+                }
+             } else {
+                globalHistory = (history->globalHistory << 1);
+                globalHistory = globalHistory & globalHistoryMask;
+                if (old_local_pred_index != invalidPredictorIndex) {
+                     localHistoryTable[old_local_pred_index] =
                      history->localHistory << 1;
-              }
-           }
+                }
+             }
 
         }
         // We're done with this history, now delete it.
         delete history;
+
     }
 
     assert(globalHistory < globalPredictorSize &&