bpred_unit.hh revision 10330
111986Sandreas.sandberg@arm.com/*
211986Sandreas.sandberg@arm.com * Copyright (c) 2011-2012, 2014 ARM Limited
311986Sandreas.sandberg@arm.com * Copyright (c) 2010 The University of Edinburgh
411986Sandreas.sandberg@arm.com * All rights reserved
511986Sandreas.sandberg@arm.com *
611986Sandreas.sandberg@arm.com * The license below extends only to copyright in the software and shall
711986Sandreas.sandberg@arm.com * not be construed as granting a license to any other intellectual
811986Sandreas.sandberg@arm.com * property including but not limited to intellectual property relating
911986Sandreas.sandberg@arm.com * to a hardware implementation of the functionality of the software
1011986Sandreas.sandberg@arm.com * licensed hereunder.  You may use the software subject to the license
1111986Sandreas.sandberg@arm.com * terms below provided that you ensure that this notice is replicated
1211986Sandreas.sandberg@arm.com * unmodified and in its entirety in all distributions of the software,
1311986Sandreas.sandberg@arm.com * modified or unmodified, in source code or in binary form.
1411986Sandreas.sandberg@arm.com *
1511986Sandreas.sandberg@arm.com * Copyright (c) 2004-2005 The Regents of The University of Michigan
1611986Sandreas.sandberg@arm.com * All rights reserved.
1711986Sandreas.sandberg@arm.com *
1811986Sandreas.sandberg@arm.com * Redistribution and use in source and binary forms, with or without
1911986Sandreas.sandberg@arm.com * modification, are permitted provided that the following conditions are
2011986Sandreas.sandberg@arm.com * met: redistributions of source code must retain the above copyright
2111986Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer;
2211986Sandreas.sandberg@arm.com * redistributions in binary form must reproduce the above copyright
2311986Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer in the
2411986Sandreas.sandberg@arm.com * documentation and/or other materials provided with the distribution;
2511986Sandreas.sandberg@arm.com * neither the name of the copyright holders nor the names of its
2611986Sandreas.sandberg@arm.com * contributors may be used to endorse or promote products derived from
2711986Sandreas.sandberg@arm.com * this software without specific prior written permission.
2811986Sandreas.sandberg@arm.com *
2911986Sandreas.sandberg@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3011986Sandreas.sandberg@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3111986Sandreas.sandberg@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3211986Sandreas.sandberg@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3311986Sandreas.sandberg@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3411986Sandreas.sandberg@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3511986Sandreas.sandberg@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3611986Sandreas.sandberg@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3711986Sandreas.sandberg@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3811986Sandreas.sandberg@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3911986Sandreas.sandberg@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4011986Sandreas.sandberg@arm.com *
4111986Sandreas.sandberg@arm.com * Authors: Kevin Lim
4211986Sandreas.sandberg@arm.com *          Korey Sewell
4311986Sandreas.sandberg@arm.com *          Timothy M. Jones
4411986Sandreas.sandberg@arm.com *          Nilay Vaish
4511986Sandreas.sandberg@arm.com */
4611986Sandreas.sandberg@arm.com
4711986Sandreas.sandberg@arm.com#ifndef __CPU_PRED_BPRED_UNIT_HH__
4811986Sandreas.sandberg@arm.com#define __CPU_PRED_BPRED_UNIT_HH__
4911986Sandreas.sandberg@arm.com
5011986Sandreas.sandberg@arm.com#include <deque>
5111986Sandreas.sandberg@arm.com
5211986Sandreas.sandberg@arm.com#include "base/statistics.hh"
5311986Sandreas.sandberg@arm.com#include "base/types.hh"
5411986Sandreas.sandberg@arm.com#include "cpu/pred/btb.hh"
5511986Sandreas.sandberg@arm.com#include "cpu/pred/ras.hh"
5611986Sandreas.sandberg@arm.com#include "cpu/inst_seq.hh"
5711986Sandreas.sandberg@arm.com#include "cpu/static_inst.hh"
5811986Sandreas.sandberg@arm.com#include "params/BranchPredictor.hh"
5911986Sandreas.sandberg@arm.com#include "sim/sim_object.hh"
6011986Sandreas.sandberg@arm.com
6111986Sandreas.sandberg@arm.com/**
6211986Sandreas.sandberg@arm.com * Basically a wrapper class to hold both the branch predictor
6311986Sandreas.sandberg@arm.com * and the BTB.
6411986Sandreas.sandberg@arm.com */
6511986Sandreas.sandberg@arm.comclass BPredUnit : public SimObject
6611986Sandreas.sandberg@arm.com{
6711986Sandreas.sandberg@arm.com  public:
6811986Sandreas.sandberg@arm.com      typedef BranchPredictorParams Params;
6911986Sandreas.sandberg@arm.com    /**
7011986Sandreas.sandberg@arm.com     * @param params The params object, that has the size of the BP and BTB.
7111986Sandreas.sandberg@arm.com     */
7211986Sandreas.sandberg@arm.com    BPredUnit(const Params *p);
7311986Sandreas.sandberg@arm.com
7411986Sandreas.sandberg@arm.com    /**
7511986Sandreas.sandberg@arm.com     * Registers statistics.
7611986Sandreas.sandberg@arm.com     */
7711986Sandreas.sandberg@arm.com    void regStats();
7811986Sandreas.sandberg@arm.com
7911986Sandreas.sandberg@arm.com    /** Perform sanity checks after a drain. */
8011986Sandreas.sandberg@arm.com    void drainSanityCheck() const;
8111986Sandreas.sandberg@arm.com
8211986Sandreas.sandberg@arm.com    /**
8311986Sandreas.sandberg@arm.com     * Predicts whether or not the instruction is a taken branch, and the
8411986Sandreas.sandberg@arm.com     * target of the branch if it is taken.
8511986Sandreas.sandberg@arm.com     * @param inst The branch instruction.
8611986Sandreas.sandberg@arm.com     * @param PC The predicted PC is passed back through this parameter.
8711986Sandreas.sandberg@arm.com     * @param tid The thread id.
8811986Sandreas.sandberg@arm.com     * @return Returns if the branch is taken or not.
8911986Sandreas.sandberg@arm.com     */
9011986Sandreas.sandberg@arm.com    bool predict(StaticInstPtr &inst, const InstSeqNum &seqNum,
9111986Sandreas.sandberg@arm.com                 TheISA::PCState &pc, ThreadID tid);
9211986Sandreas.sandberg@arm.com    bool predictInOrder(StaticInstPtr &inst, const InstSeqNum &seqNum,
9311986Sandreas.sandberg@arm.com                        int asid, TheISA::PCState &instPC,
9411986Sandreas.sandberg@arm.com                        TheISA::PCState &predPC, ThreadID tid);
9511986Sandreas.sandberg@arm.com
9611986Sandreas.sandberg@arm.com    // @todo: Rename this function.
9711986Sandreas.sandberg@arm.com    virtual void uncondBranch(void * &bp_history) = 0;
9811986Sandreas.sandberg@arm.com
9911986Sandreas.sandberg@arm.com    /**
10011986Sandreas.sandberg@arm.com     * Tells the branch predictor to commit any updates until the given
10111986Sandreas.sandberg@arm.com     * sequence number.
10211986Sandreas.sandberg@arm.com     * @param done_sn The sequence number to commit any older updates up until.
10311986Sandreas.sandberg@arm.com     * @param tid The thread id.
10411986Sandreas.sandberg@arm.com     */
10511986Sandreas.sandberg@arm.com    void update(const InstSeqNum &done_sn, ThreadID tid);
10611986Sandreas.sandberg@arm.com
10711986Sandreas.sandberg@arm.com    /**
10811986Sandreas.sandberg@arm.com     * Squashes all outstanding updates until a given sequence number.
10911986Sandreas.sandberg@arm.com     * @param squashed_sn The sequence number to squash any younger updates up
11011986Sandreas.sandberg@arm.com     * until.
11111986Sandreas.sandberg@arm.com     * @param tid The thread id.
11211986Sandreas.sandberg@arm.com     */
11311986Sandreas.sandberg@arm.com    void squash(const InstSeqNum &squashed_sn, ThreadID tid);
11411986Sandreas.sandberg@arm.com
11511986Sandreas.sandberg@arm.com    /**
11611986Sandreas.sandberg@arm.com     * Squashes all outstanding updates until a given sequence number, and
11711986Sandreas.sandberg@arm.com     * corrects that sn's update with the proper address and taken/not taken.
11811986Sandreas.sandberg@arm.com     * @param squashed_sn The sequence number to squash any younger updates up
11911986Sandreas.sandberg@arm.com     * until.
12011986Sandreas.sandberg@arm.com     * @param corr_target The correct branch target.
12111986Sandreas.sandberg@arm.com     * @param actually_taken The correct branch direction.
12211986Sandreas.sandberg@arm.com     * @param tid The thread id.
12311986Sandreas.sandberg@arm.com     */
12411986Sandreas.sandberg@arm.com    void squash(const InstSeqNum &squashed_sn,
12511986Sandreas.sandberg@arm.com                const TheISA::PCState &corr_target,
12611986Sandreas.sandberg@arm.com                bool actually_taken, ThreadID tid);
12711986Sandreas.sandberg@arm.com
12811986Sandreas.sandberg@arm.com    /**
12911986Sandreas.sandberg@arm.com     * @param bp_history Pointer to the history object.  The predictor
13011986Sandreas.sandberg@arm.com     * will need to update any state and delete the object.
13111986Sandreas.sandberg@arm.com     */
13211986Sandreas.sandberg@arm.com    virtual void squash(void *bp_history) = 0;
13311986Sandreas.sandberg@arm.com
13411986Sandreas.sandberg@arm.com    /**
13511986Sandreas.sandberg@arm.com     * Looks up a given PC in the BP to see if it is taken or not taken.
13611986Sandreas.sandberg@arm.com     * @param inst_PC The PC to look up.
13711986Sandreas.sandberg@arm.com     * @param bp_history Pointer that will be set to an object that
13811986Sandreas.sandberg@arm.com     * has the branch predictor state associated with the lookup.
13911986Sandreas.sandberg@arm.com     * @return Whether the branch is taken or not taken.
14011986Sandreas.sandberg@arm.com     */
14111986Sandreas.sandberg@arm.com    virtual bool lookup(Addr instPC, void * &bp_history) = 0;
14211986Sandreas.sandberg@arm.com
14311986Sandreas.sandberg@arm.com     /**
14411986Sandreas.sandberg@arm.com     * If a branch is not taken, because the BTB address is invalid or missing,
14511986Sandreas.sandberg@arm.com     * this function sets the appropriate counter in the global and local
14611986Sandreas.sandberg@arm.com     * predictors to not taken.
14711986Sandreas.sandberg@arm.com     * @param inst_PC The PC to look up the local predictor.
14811986Sandreas.sandberg@arm.com     * @param bp_history Pointer that will be set to an object that
14911986Sandreas.sandberg@arm.com     * has the branch predictor state associated with the lookup.
15011986Sandreas.sandberg@arm.com     */
15111986Sandreas.sandberg@arm.com    virtual void btbUpdate(Addr instPC, void * &bp_history) = 0;
15211986Sandreas.sandberg@arm.com
15311986Sandreas.sandberg@arm.com    /**
15411986Sandreas.sandberg@arm.com     * Looks up a given PC in the BTB to see if a matching entry exists.
15511986Sandreas.sandberg@arm.com     * @param inst_PC The PC to look up.
15611986Sandreas.sandberg@arm.com     * @return Whether the BTB contains the given PC.
15711986Sandreas.sandberg@arm.com     */
15811986Sandreas.sandberg@arm.com    bool BTBValid(Addr instPC)
15911986Sandreas.sandberg@arm.com    { return BTB.valid(instPC, 0); }
160
161    /**
162     * Looks up a given PC in the BTB to get the predicted target.
163     * @param inst_PC The PC to look up.
164     * @return The address of the target of the branch.
165     */
166    TheISA::PCState BTBLookup(Addr instPC)
167    { return BTB.lookup(instPC, 0); }
168
169    /**
170     * Updates the BP with taken/not taken information.
171     * @param inst_PC The branch's PC that will be updated.
172     * @param taken Whether the branch was taken or not taken.
173     * @param bp_history Pointer to the branch predictor state that is
174     * associated with the branch lookup that is being updated.
175     * @param squashed Set to true when this function is called during a
176     * squash operation.
177     * @todo Make this update flexible enough to handle a global predictor.
178     */
179    virtual void update(Addr instPC, bool taken, void *bp_history,
180                        bool squashed) = 0;
181     /**
182     * Deletes the associated history with a branch, performs no predictor
183     * updates.  Used for branches that mispredict and update tables but
184     * are still speculative and later retire.
185     * @param bp_history History to delete associated with this predictor
186     */
187    virtual void retireSquashed(void *bp_history) = 0;
188
189    /**
190     * Updates the BTB with the target of a branch.
191     * @param inst_PC The branch's PC that will be updated.
192     * @param target_PC The branch's target that will be added to the BTB.
193     */
194    void BTBUpdate(Addr instPC, const TheISA::PCState &target)
195    { BTB.update(instPC, target, 0); }
196
197    void dump();
198
199  private:
200    struct PredictorHistory {
201        /**
202         * Makes a predictor history struct that contains any
203         * information needed to update the predictor, BTB, and RAS.
204         */
205        PredictorHistory(const InstSeqNum &seq_num, Addr instPC,
206                         bool pred_taken, void *bp_history,
207                         ThreadID _tid)
208            : seqNum(seq_num), pc(instPC), bpHistory(bp_history), RASTarget(0),
209              RASIndex(0), tid(_tid), predTaken(pred_taken), usedRAS(0), pushedRAS(0),
210              wasCall(0), wasReturn(0), wasSquashed(0)
211        {}
212
213        bool operator==(const PredictorHistory &entry) const {
214            return this->seqNum == entry.seqNum;
215        }
216
217        /** The sequence number for the predictor history entry. */
218        InstSeqNum seqNum;
219
220        /** The PC associated with the sequence number. */
221        Addr pc;
222
223        /** Pointer to the history object passed back from the branch
224         * predictor.  It is used to update or restore state of the
225         * branch predictor.
226         */
227        void *bpHistory;
228
229        /** The RAS target (only valid if a return). */
230        TheISA::PCState RASTarget;
231
232        /** The RAS index of the instruction (only valid if a call). */
233        unsigned RASIndex;
234
235        /** The thread id. */
236        ThreadID tid;
237
238        /** Whether or not it was predicted taken. */
239        bool predTaken;
240
241        /** Whether or not the RAS was used. */
242        bool usedRAS;
243
244        /* Whether or not the RAS was pushed */
245        bool pushedRAS;
246
247        /** Whether or not the instruction was a call. */
248        bool wasCall;
249
250        /** Whether or not the instruction was a return. */
251        bool wasReturn;
252
253        /** Whether this instruction has already mispredicted/updated bp */
254        bool wasSquashed;
255    };
256
257    typedef std::deque<PredictorHistory> History;
258
259    /** Number of the threads for which the branch history is maintained. */
260    uint32_t numThreads;
261
262    /**
263     * The per-thread predictor history. This is used to update the predictor
264     * as instructions are committed, or restore it to the proper state after
265     * a squash.
266     */
267    std::vector<History> predHist;
268
269    /** The BTB. */
270    DefaultBTB BTB;
271
272    /** The per-thread return address stack. */
273    std::vector<ReturnAddrStack> RAS;
274
275    /** Stat for number of BP lookups. */
276    Stats::Scalar lookups;
277    /** Stat for number of conditional branches predicted. */
278    Stats::Scalar condPredicted;
279    /** Stat for number of conditional branches predicted incorrectly. */
280    Stats::Scalar condIncorrect;
281    /** Stat for number of BTB lookups. */
282    Stats::Scalar BTBLookups;
283    /** Stat for number of BTB hits. */
284    Stats::Scalar BTBHits;
285    /** Stat for number of times the BTB is correct. */
286    Stats::Scalar BTBCorrect;
287    /** Stat for percent times an entry in BTB found. */
288    Stats::Formula BTBHitPct;
289    /** Stat for number of times the RAS is used to get a target. */
290    Stats::Scalar usedRAS;
291    /** Stat for number of times the RAS is incorrect. */
292    Stats::Scalar RASIncorrect;
293};
294
295#endif // __CPU_PRED_BPRED_UNIT_HH__
296