Thanks for digging into this in more detail, Korey. It sounds to me like maybe the problem is that MIPS is setting predPC to the branch target, when (to account for the delay slot) it ought to be leaving predPC as PC+4 and setting predNPC to be the branch target. That way if the prediction turns out to be correct, then you set PC <- predPC and NPC <- predNPC and you get the right behavior for the following instruction.
Is there a reason it doesn't work this way? Steve On Fri, Apr 17, 2009 at 2:24 AM, Korey Sewell <[email protected]> wrote: > OK.... So I finally figured out what's wrong here and admittedly I'm a > bit apprehensive of the universal (all ISA) fix will be but we'll see. > > So let me explain the situation from the top: > > (1) In the Decode of O3, an unconditional pc-relative branch is > resolved and the prediciton history table is updated to remove the > resolved branch (since we've already updated the predictors with the > result). However, in the Execute stage the branch is seen as > mispredicted AGAIN, causing the code to want to update and delete > something from the prediction history. This triggers an assert and > breaks exeuction. > > (2) So a few questions emerge: > (2a) Why does this work with the previous hack disabling the early > resolve of branches in Decode? > Because the mispredict only happens once and in Execute the fetch is > redirected to the results of the execution so we only experience > performance degradation instead of non-functional peformance. > > (2b) How can we mispredict a branch in Execute after we've previously > resolved that branch in Decode? > It just seems that the mispredict() function isnt handling the MIPS > delay slots correctly. When a branch happens in MIPS, it sets the NPC > = PC + 4 and NNPC = target. However the code shows this: > > return readPredPC() != readNextPC() || > readPredNPC() != readNextNPC() || > readPredMicroPC() != readNextMicroPC(); > > Consider for MIPS, the predPC is the target and the predNPC is > target+4, then you're saying: > target != pc+4 > and > target+4 != target > which will be wrong in most cases. > > (3) How could this work for SPARC? > I'm not sure. My guess is that instructions in SPARC are disregarding > the delay slot in execution and setting the NPC to the target instead > of setting the NPC to PC+4. > SIDE ISSUE: Gabe, is SPARC not using the Unconditional Control flag? I > ran SPARC and put this assert (assert(!inst->UnCondCtrl()) in the > decode-branch-resolve optimization and it ran fine (for hello-world) > > > So if my guess on (3) is right then I dont right away see a quick fix > other than using a compiler directive. The MIPS code needs this in > mispredict(): > #if THE_ISA == MIPS_ISA > // Special case since a not-taken, cond. delay slot, effectively > // nullifies the delay slot instruction > if (isCondDelaySlot() && !predictTaken) { > return predPC != nextPC; > } else { > return predPC != nextNPC; > } > #else > return readPredPC() != readNextPC() || > readPredNPC() != readNextNPC() || > readPredMicroPC() != readNextMicroPC(); > #endif > > So that's the main issue that's happening and forcing MIPS to break > rather quickly. My solution for a fix? I guess it all depends on the > answer to (3), but it seems like there is going to have to be a > uniform way for how instructions specify their NPC and NNPC when an > instruction executes. > > I need to take a break from coding MIPS to handle a round of InOrder > issues (research!) but hopefully this discussion can lead us into a > uniform solution for when I get back to the code. > > On Thu, Apr 16, 2009 at 12:52 AM, Steve Reinhardt <[email protected]> > wrote: > > I see now, I missed that little change buried at the bottom. > > > > I recall that condition about unconditional PC-relative branches finding > out > > in decode that their target was mispredicted too. > > > > I'm wondering if you're not just hacking around the real problem here... > I > > don't see how this particular case is MIPS-specific, but I could believe > > that there may be some MIPS-specific details in how it's handled (like > maybe > > the nextPC is not getting updated correctly because of branch delay slots > or > > something). So your fix may be avoiding this correctness problem by > > preventing the model from handling this particular class of misprediction > > properly, forcing it to use an unrealistic but not broken path instead, > > while the right answer is to fix the real problem. > > > > Steve > > > > On Wed, Apr 15, 2009 at 9:16 PM, Korey Sewell <[email protected]> wrote: > >> > >> There is a bunch of DPRINTS in there that I kept in figuring out what's > >> going on. > >> > >> The actual fix is small in fetch_impl.hh: > >> " // Update the branch predictor. > >> +#if THE_ISA == MIPS_ISA > >> + if (fromDecode->decodeInfo[tid]. > >> branchMispredict && 0) { > >> +#else > >> if (fromDecode->decodeInfo[tid].branchMispredict) { > >> +#endif > >> " > >> A little lower in the fall-out of that selection statement you'll see 2 > >> different squash functions that get called in the branch predictor: > >> - One squashes all history behind the mispredicted instruction > >> - The other squashes all history and then updates some branch history > >> state (which is kind of confusing) > >> > >> I edited out the 2nd one from happening and things work again. > >> > >> The reason why you get a mispredict in decode is I think the fetching > >> scenario behind an unconditional PC-relative branch. You wont know > exactly > >> which direction to go until after decode. > >> > >> > >> On Wed, Apr 15, 2009 at 11:44 PM, Steve Reinhardt <[email protected]> > >> wrote: > >>> > >>> I'm confused... this patch looks like it pretty much just inserts a > bunch > >>> of DPRINTFs (plus the seemingly mistaken inclusion of a whitespace > change in > >>> mips/isa/decoder.isa). > >>> > >>> I don't know anything specific about the O3 predictor, but it makes > sense > >>> that the history is updated speculatively in decode, but I don't see > how you > >>> can even know whether a branch is mispredicted while you're still in > the > >>> decode stage, so the fixup would have to wait at least until execute > (and > >>> you may want to wait until commit if that makes recovery substantially > >>> simpler). > >>> > >>> Steve > >>> > >>> On Wed, Apr 15, 2009 at 8:15 PM, Korey Sewell <[email protected]> > wrote: > >>>> > >>>> This is the patch that will prevent me from committing. > >>>> > >>>> Basically, the decode stage is finding a mispredicted branch and then > >>>> deleting information out the branch history table for squashed > instructions > >>>> AND itself. > >>>> > >>>> This messes things up for when the actual mispredicted instruction > gets > >>>> to commit and wants to update the branch history. > >>>> > >>>> So basically, I ignored that condition and it branch prediction > started > >>>> working. I did the same for ALPHA and SPARC and it seemed to work for > Hello > >>>> World as well (maybe I just got lucky?) > >>>> > >>>> The next thing I guess I should do is run the quick/long regressions > on > >>>> ALPHA/SPARC to make sure I'm not breaking anything if I were to remove > that > >>>> code. > >>>> > >>>> Anybody have any thoughts on this (Gabe, Kevin?)? > >>>> > >>>> > >>>> On Wed, Apr 15, 2009 at 11:06 PM, Korey Sewell < > [email protected]> > >>>> wrote: > >>>>> > >>>>> # HG changeset patch > >>>>> # User Korey Sewell <[email protected]> > >>>>> # Date 1239850525 14400 > >>>>> # Node ID ce539a58327b78b049f8af0bf8a00737f2b97640 > >>>>> # Parent 7b685fee8773c2fe0bd09ec7abb0a43873aeed92 > >>>>> Fix Branch Prediction for MIPS. Namely, i dont see the reason for > >>>>> updating the branch history on anything that happens in decode. this > should > >>>>> happen only in commit, right? > >>>>> > >>>>> diff --git a/src/arch/mips/isa/decoder.isa > >>>>> b/src/arch/mips/isa/decoder.isa > >>>>> --- a/src/arch/mips/isa/decoder.isa > >>>>> +++ b/src/arch/mips/isa/decoder.isa > >>>>> @@ -135,7 +135,7 @@ decode OPCODE_HI default Unknown::unknow > >>>>> 0x2: movz({{ Rd = (Rt == 0) ? Rs : Rd; }}); > >>>>> 0x3: movn({{ Rd = (Rt != 0) ? Rs : Rd; }}); > >>>>> #if FULL_SYSTEM > >>>>> - 0x4: syscall({{ > >>>>> + 0x4: syscall({{ > >>>>> fault = new SystemCallFault(); > >>>>> }}); > >>>>> #else > >>>>> diff --git a/src/cpu/o3/bpred_unit_impl.hh > >>>>> b/src/cpu/o3/bpred_unit_impl.hh > >>>>> --- a/src/cpu/o3/bpred_unit_impl.hh > >>>>> +++ b/src/cpu/o3/bpred_unit_impl.hh > >>>>> @@ -173,6 +173,10 @@ BPredUnit<Impl>::predict(DynInstPtr &ins > >>>>> tid, pred_taken, inst->readPC()); > >>>>> } > >>>>> > >>>>> + DPRINTF(Fetch, "BranchPred: [tid:%i]: [sn:%i] Creating > prediction > >>>>> history " > >>>>> + "for PC %#x\n", > >>>>> + tid, inst->seqNum, inst->readPC()); > >>>>> + > >>>>> PredictorHistory predict_record(inst->seqNum, PC, pred_taken, > >>>>> bp_history, tid); > >>>>> > >>>>> @@ -249,7 +253,7 @@ void > >>>>> void > >>>>> BPredUnit<Impl>::update(const InstSeqNum &done_sn, unsigned tid) > >>>>> { > >>>>> - DPRINTF(Fetch, "BranchPred: [tid:%i]: Commiting branches until " > >>>>> + DPRINTF(Fetch, "BranchPred: [tid:%i]: Committing branches until > " > >>>>> "[sn:%lli].\n", tid, done_sn); > >>>>> > >>>>> while (!predHist[tid].empty() && > >>>>> @@ -290,7 +294,12 @@ BPredUnit<Impl>::squash(const InstSeqNum > >>>>> // This call should delete the bpHistory. > >>>>> BPSquash(pred_hist.front().bpHistory); > >>>>> > >>>>> + DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for > >>>>> [sn:%i] " > >>>>> + "PC %#x.\n", tid, pred_hist.front().seqNum, > >>>>> pred_hist.front().PC); > >>>>> + > >>>>> pred_hist.pop_front(); > >>>>> + > >>>>> + DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid, > >>>>> predHist[tid].size()); > >>>>> } > >>>>> > >>>>> } > >>>>> @@ -320,7 +329,13 @@ BPredUnit<Impl>::squash(const InstSeqNum > >>>>> // corresponding to the squash. In that case, don't bother > trying > >>>>> to > >>>>> // fix up the entry. > >>>>> if (!pred_hist.empty()) { > >>>>> - assert(pred_hist.front().seqNum == squashed_sn); > >>>>> + if (pred_hist.front().seqNum != squashed_sn) > >>>>> + { > >>>>> + DPRINTF(Fetch, "PredHist.front.sn = %i | squashed_sn = > >>>>> %i.\n", > >>>>> + pred_hist.front().seqNum, squashed_sn); > >>>>> + assert(pred_hist.front().seqNum == squashed_sn); > >>>>> + } > >>>>> + > >>>>> if (pred_hist.front().usedRAS) { > >>>>> ++RASIncorrect; > >>>>> } > >>>>> @@ -329,7 +344,13 @@ BPredUnit<Impl>::squash(const InstSeqNum > >>>>> pred_hist.front().bpHistory); > >>>>> > >>>>> BTB.update(pred_hist.front().PC, corr_target, tid); > >>>>> + > >>>>> + DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for > >>>>> [sn:%i] " > >>>>> + "PC %#x.\n", tid, pred_hist.front().seqNum, > >>>>> pred_hist.front().PC); > >>>>> + > >>>>> pred_hist.pop_front(); > >>>>> + > >>>>> + DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid, > >>>>> predHist[tid].size()); > >>>>> } > >>>>> } > >>>>> > >>>>> diff --git a/src/cpu/o3/fetch_impl.hh b/src/cpu/o3/fetch_impl.hh > >>>>> --- a/src/cpu/o3/fetch_impl.hh > >>>>> +++ b/src/cpu/o3/fetch_impl.hh > >>>>> @@ -939,7 +939,11 @@ DefaultFetch<Impl>::checkSignalsAndUpdat > >>>>> "from decode.\n",tid); > >>>>> > >>>>> // Update the branch predictor. > >>>>> +#if THE_ISA == MIPS_ISA > >>>>> + if (fromDecode->decodeInfo[tid].branchMispredict && 0) { > >>>>> +#else > >>>>> if (fromDecode->decodeInfo[tid].branchMispredict) { > >>>>> +#endif > >>>>> branchPred.squash(fromDecode->decodeInfo[tid].doneSeqNum, > >>>>> fromDecode->decodeInfo[tid].nextPC, > >>>>> > fromDecode->decodeInfo[tid].branchTaken, > >>>>> diff --git a/src/cpu/o3/iew_impl.hh b/src/cpu/o3/iew_impl.hh > >>>>> --- a/src/cpu/o3/iew_impl.hh > >>>>> +++ b/src/cpu/o3/iew_impl.hh > >>>>> @@ -1282,11 +1282,11 @@ DefaultIEW<Impl>::executeInsts() > >>>>> fetchRedirect[tid] = true; > >>>>> > >>>>> DPRINTF(IEW, "Execute: Branch mispredict > detected.\n"); > >>>>> - DPRINTF(IEW, "Predicted target was %#x, %#x.\n", > >>>>> + DPRINTF(IEW, "Predicted target was PC:%#x, > >>>>> NPC:%#x.\n", > >>>>> inst->readPredPC(), inst->readPredNPC()); > >>>>> DPRINTF(IEW, "Execute: Redirecting fetch to PC: %#x," > >>>>> " NPC: %#x.\n", inst->readNextPC(), > >>>>> - inst->readNextNPC()); > >>>>> + inst->readNextPC()); > >>>>> // If incorrect, then signal the ROB that it must be > >>>>> squashed. > >>>>> squashDueToBranch(inst, tid); > >>>>> > >>>>> _______________________________________________ > >>>>> m5-dev mailing list > >>>>> [email protected] > >>>>> http://m5sim.org/mailman/listinfo/m5-dev > >>>> > >>>> > >>>> > >>>> -- > >>>> ---------- > >>>> Korey L Sewell > >>>> Graduate Student - PhD Candidate > >>>> Computer Science & Engineering > >>>> University of Michigan > >>>> > >>>> _______________________________________________ > >>>> m5-dev mailing list > >>>> [email protected] > >>>> http://m5sim.org/mailman/listinfo/m5-dev > >>>> > >>> > >>> > >>> _______________________________________________ > >>> m5-dev mailing list > >>> [email protected] > >>> http://m5sim.org/mailman/listinfo/m5-dev > >>> > >> > >> > >> > >> -- > >> ---------- > >> Korey L Sewell > >> Graduate Student - PhD Candidate > >> Computer Science & Engineering > >> University of Michigan > >> > >> _______________________________________________ > >> m5-dev mailing list > >> [email protected] > >> http://m5sim.org/mailman/listinfo/m5-dev > >> > > > > > > _______________________________________________ > > m5-dev mailing list > > [email protected] > > http://m5sim.org/mailman/listinfo/m5-dev > > > > > > > > -- > ---------- > Korey L Sewell > Graduate Student - PhD Candidate > Computer Science & Engineering > University of Michigan > _______________________________________________ > m5-dev mailing list > [email protected] > http://m5sim.org/mailman/listinfo/m5-dev >
_______________________________________________ m5-dev mailing list [email protected] http://m5sim.org/mailman/listinfo/m5-dev
