cpu: Revamp saturating counters

Revamp the SatCounter class, improving comments, implementing
increment, decrement and read operators to solve an old todo,
and adding missing error checking.

Change-Id: Ia057c423c90652ebd966b6b91a3471b17800f933
Signed-off-by: Daniel <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/17992
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Jason Lowe-Power <jason@lowepower.com>
Tested-by: kokoro <noreply+kokoro@google.com>

cpu: Proposal for changing the indirect branch predictor interface

Now the indirect branch predictor handles its own GHR instead of getting
the one from the direction predictor.

Also, now the commit method of the indirect predictor is called for every
pending branch on an update, as the indirect predictors may want to update
their interal structures/histories with the information of each branch.

Change-Id: I7053fbea42a53960a3bc1ba32912cc99c160511e
Reviewed-on: https://gem5-review.googlesource.com/c/15318
Reviewed-by: Andreas Sandberg <andreas.sandberg@arm.com>
Maintainer: Andreas Sandberg <andreas.sandberg@arm.com>

cpu: Made TAGE a SimObject that can be used by other predictors

The TAGE implementation is now a SimObject so that other branch predictors
can easily use it. It has also been updated with the latest available TAGE
implementation from Andre Seznec:

http://www.irisa.fr/alf/downloads/seznec/TAGE-GSC-IMLI.tar

Change-Id: I2251b8b2d7f94124f9955f52b917dc3b064f090e
Reviewed-on: https://gem5-review.googlesource.com/c/15317
Reviewed-by: Giacomo Travaglini <giacomo.travaglini@arm.com>
Maintainer: Andreas Sandberg <andreas.sandberg@arm.com>

style: [patch 1/22] use /r/3648/ to reorganize includes

cpu: disallow speculative update of branch predictor tables (o3)

The Minor and o3 cpu models share the branch prediction
code. Minor relies on the BPredUnit::squash() function
to update the branch predictor tables on a branch mispre-
diction. This is fine because Minor executes in-order, so
the update is on the correct path. However, this causes the
branch predictor to be updated on out-of-order branch
mispredictions when using the o3 model, which should not
be the case.

This patch guards against speculative update of the branch
prediction tables. On a branch misprediction, BPredUnit::squash()
calls BpredUnit::update(..., squashed = true). The underlying
branch predictor tests against the value of squashed. If it is
true, it restores any speculatively updated internal state
it might have (e.g., global/local branch history), then returns.
If false, it updates its prediction tables. Previously, exist-
ing predictors did not test against the "squashed" parameter.

To accomodate for this change, the Minor model must now call
BPredUnit::squash() then BPredUnit::update(..., squashed = false)
on branch mispredictions. Before, calling BpredUnit::squash()
performed the prediction tables update.

The effect is a slight MPKI improvement when using the o3
model. A further patch should perform the same modifications
for the indirect target predictor and BTB (less critical).

Signed-off-by: Jason Lowe-Power <jason@lowepower.com>

cpu: correct comments in tournament branch predictor

The tournament predictor is presented as doing speculative
update of the global history and non-speculative update
of the local history used to generate the branch prediction.
However, the code does speculative update of both histories.

Signed-off-by: Jason Lowe-Power <jason@lowepower.com>

cpu: Implement per-thread GHRs

Branch predictors that use GHRs should index them on a
per-thread basis. This makes that so.

This is a re-spin of fb51231 after the revert (bd1c6789).

cpu: Add an indirect branch target predictor

This patch adds a configurable indirect branch predictor that can be indexed
by a combination of GHR and path history hashes. Implements the functionality
described in:

"Target prediction for indirect jumps" by Chang, Hao, and Patt
http://dl.acm.org/citation.cfm?id=264209

This is a re-spin of fb9d142 after the revert (bd1c6789).

Revert power patch sets with unexpected interactions

The following patches had unexpected interactions with the current
upstream code and have been reverted for now:

e07fd01651f3: power: Add support for power models
831c7f2f9e39: power: Low-power idle power state for idle CPUs
4f749e00b667: power: Add power states to ClockedObject

Signed-off-by: Andreas Sandberg <andreas.sandberg@arm.com>

cpu: Implement per-thread GHRs

Branch predictors that use GHRs should index them on a
per-thread basis. This makes that so.

cpu: Add an indirect branch target predictor

This patch adds a configurable indirect branch predictor that can be indexed
by a combination of GHR and path history hashes. Implements the functionality
described in:

"Target prediction for indirect jumps" by Chang, Hao, and Patt
http://dl.acm.org/citation.cfm?id=264209

cpu: pred: Local Predictor Reset in Tournament Predictor

When a branch gets squashed, it's speculative branch predictor state should get
rolled back in squash(). However, only the globalHistory state was being
rolled back. This patch adds (at least some) support for rolling back the
local predictor state also.

Committed by: Nilay Vaish <nilay@cs.wisc.edu>

cpu: re-organizes the branch predictor structure.

Committed by: Nilay Vaish <nilay@cs.wisc.edu>

cpu: Fix incorrect speculative branch predictor behavior

When a branch mispredicted gem5 would squash all history after and including
the mispredicted branch. However, the mispredicted branch is still speculative
and its history is required to rollback state if another, older, branch
mispredicts. This leads to things like RAS corruption.

cpu: remove local/globalHistoryBits params from branch pred

having separate params for the local/globalHistoryBits and the
local/globalPredictorSize can lead to inconsistencies if they
are not carefully set. this patch dervies the number of bits
necessary to index into the local/global predictors based on
their size.

the value of the localHistoryTableSize for the ARM O3 CPU has been
increased to 1024 from 64, which is more accurate for an A15 based
on some correlation against A15 hardware.

branch predictor: move out of o3 and inorder cpus
This patch moves the branch predictor files in the o3 and inorder directories
to src/cpu/pred. This allows sharing the branch predictor across different
cpu models.

This patch was originally posted by Timothy Jones in July 2010
but never made it to the repository.

TournamentBP: Fix some bugs with table sizes and counters
globalHistoryBits, globalPredictorSize, and choicePredictorSize are decoupled.
globalHistoryBits controls how much history is kept, global and choice
predictor sizes control how much of that history is used when accessing
predictor tables. This way, global and choice predictors can actually be
different sizes, and it is no longer possible to walk off the predictor arrays
and cause a seg fault.

There are now individual thresholds for choice, global, and local saturating
counters, so that taken/not taken decisions are correct even when the
predictors' counters' sizes are different.

The interface for localPredictorSize has been removed from TournamentBP because
the value can be calculated from localHistoryBits.

Committed by: Nilay Vaish <nilay@cs.wisc.edu>

o3: Fix a couple of issues with the local predictor.

Fix some issues with the local predictor and the way it's indexed.

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.

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

O3: Fix uninitialized variable in the tournament branch predictor.

Branch predictor: Fixes the tournament branch predictor.

Branch predictor could not predict a branch in a nested loop because:
1. The global history was not updated after a mispredict squash.
2. The global history was updated in the fetch stage. The choice predictors
that were updated used the changed global history. This is incorrect, as
it incorporates the state of global history after the branch in
encountered. Fixed update to choice predictor using the global history
state before the branch happened.
3. The global predictor table was also updated using the global history state
before the branch happened as above.

Additionally, parameters to initialize ctr and history size were reversed.

BPRED: Fixed the treshold-bug in the tournament predictor.

Suppose the saturating counters of a branch predictor contain n bits. When the
counter is between 0 and (2^(n-1) - 1), boundaries included, the branch is
predicted as not taken. When the counter is between 2^(n-1) and (2^n - 1),
boundaries included, the branch is predicted as taken.

move: put predictor includes and cc files into the same place