1/*
2 * Copyright (c) 2013-2014,2016 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are
16 * met: redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer;
18 * redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution;
21 * neither the name of the copyright holders nor the names of its
22 * contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 * Authors: Andrew Bardsley
38 */
39
40#include "cpu/minor/fetch2.hh"
41
42#include <string>
43
44#include "arch/decoder.hh"
45#include "arch/utility.hh"
46#include "cpu/minor/pipeline.hh"
47#include "cpu/pred/bpred_unit.hh"
48#include "debug/Branch.hh"
49#include "debug/Fetch.hh"
50#include "debug/MinorTrace.hh"
51
52namespace Minor
53{
54
55Fetch2::Fetch2(const std::string &name,
56 MinorCPU &cpu_,
57 MinorCPUParams ¶ms,
58 Latch<ForwardLineData>::Output inp_,
59 Latch<BranchData>::Output branchInp_,
60 Latch<BranchData>::Input predictionOut_,
61 Latch<ForwardInstData>::Input out_,
62 std::vector<InputBuffer<ForwardInstData>> &next_stage_input_buffer) :
63 Named(name),
64 cpu(cpu_),
65 inp(inp_),
66 branchInp(branchInp_),
67 predictionOut(predictionOut_),
68 out(out_),
69 nextStageReserve(next_stage_input_buffer),
70 outputWidth(params.decodeInputWidth),
71 processMoreThanOneInput(params.fetch2CycleInput),
72 branchPredictor(*params.branchPred),
73 fetchInfo(params.numThreads),
74 threadPriority(0)
75{
76 if (outputWidth < 1)
77 fatal("%s: decodeInputWidth must be >= 1 (%d)\n", name, outputWidth);
78
79 if (params.fetch2InputBufferSize < 1) {
80 fatal("%s: fetch2InputBufferSize must be >= 1 (%d)\n", name,
81 params.fetch2InputBufferSize);
82 }
83
84 /* Per-thread input buffers */
85 for (ThreadID tid = 0; tid < params.numThreads; tid++) {
86 inputBuffer.push_back(
87 InputBuffer<ForwardLineData>(
88 name + ".inputBuffer" + std::to_string(tid), "lines",
89 params.fetch2InputBufferSize));
90 }
91}
92
93const ForwardLineData *
94Fetch2::getInput(ThreadID tid)
95{
96 /* Get a line from the inputBuffer to work with */
97 if (!inputBuffer[tid].empty()) {
98 return &(inputBuffer[tid].front());
99 } else {
100 return NULL;
101 }
102}
103
104void
105Fetch2::popInput(ThreadID tid)
106{
107 if (!inputBuffer[tid].empty()) {
108 inputBuffer[tid].front().freeLine();
109 inputBuffer[tid].pop();
110 }
111
112 fetchInfo[tid].inputIndex = 0;
113}
114
115void
116Fetch2::dumpAllInput(ThreadID tid)
117{
118 DPRINTF(Fetch, "Dumping whole input buffer\n");
119 while (!inputBuffer[tid].empty())
120 popInput(tid);
121
122 fetchInfo[tid].inputIndex = 0;
123 fetchInfo[tid].havePC = false;
124}
125
126void
127Fetch2::updateBranchPrediction(const BranchData &branch)
128{
129 MinorDynInstPtr inst = branch.inst;
130
131 /* Don't even consider instructions we didn't try to predict or faults */
132 if (inst->isFault() || !inst->triedToPredict)
133 return;
134
135 switch (branch.reason) {
136 case BranchData::NoBranch:
137 /* No data to update */
138 break;
139 case BranchData::Interrupt:
140 /* Never try to predict interrupts */
141 break;
142 case BranchData::SuspendThread:
143 /* Don't need to act on suspends */
144 break;
145 case BranchData::HaltFetch:
146 /* Don't need to act on fetch wakeup */
147 break;
148 case BranchData::BranchPrediction:
149 /* Shouldn't happen. Fetch2 is the only source of
150 * BranchPredictions */
151 break;
152 case BranchData::UnpredictedBranch:
153 /* Unpredicted branch or barrier */
154 DPRINTF(Branch, "Unpredicted branch seen inst: %s\n", *inst);
155 branchPredictor.squash(inst->id.fetchSeqNum,
156 branch.target, true, inst->id.threadId);
157 // Update after squashing to accomodate O3CPU
158 // using the branch prediction code.
159 branchPredictor.update(inst->id.fetchSeqNum,
160 inst->id.threadId);
161 break;
162 case BranchData::CorrectlyPredictedBranch:
163 /* Predicted taken, was taken */
164 DPRINTF(Branch, "Branch predicted correctly inst: %s\n", *inst);
165 branchPredictor.update(inst->id.fetchSeqNum,
166 inst->id.threadId);
167 break;
168 case BranchData::BadlyPredictedBranch:
169 /* Predicted taken, not taken */
170 DPRINTF(Branch, "Branch mis-predicted inst: %s\n", *inst);
171 branchPredictor.squash(inst->id.fetchSeqNum,
172 branch.target /* Not used */, false, inst->id.threadId);
173 // Update after squashing to accomodate O3CPU
174 // using the branch prediction code.
175 branchPredictor.update(inst->id.fetchSeqNum,
176 inst->id.threadId);
177 break;
178 case BranchData::BadlyPredictedBranchTarget:
179 /* Predicted taken, was taken but to a different target */
180 DPRINTF(Branch, "Branch mis-predicted target inst: %s target: %s\n",
181 *inst, branch.target);
182 branchPredictor.squash(inst->id.fetchSeqNum,
183 branch.target, true, inst->id.threadId);
184 break;
185 }
186}
187
188void
189Fetch2::predictBranch(MinorDynInstPtr inst, BranchData &branch)
190{
191 Fetch2ThreadInfo &thread = fetchInfo[inst->id.threadId];
192 TheISA::PCState inst_pc = inst->pc;
193
194 assert(!inst->predictedTaken);
195
196 /* Skip non-control/sys call instructions */
197 if (inst->staticInst->isControl() ||
198 inst->staticInst->isSyscall())
199 {
200 /* Tried to predict */
201 inst->triedToPredict = true;
202
203 DPRINTF(Branch, "Trying to predict for inst: %s\n", *inst);
204
205 if (branchPredictor.predict(inst->staticInst,
206 inst->id.fetchSeqNum, inst_pc,
207 inst->id.threadId))
208 {
209 inst->predictedTaken = true;
210 inst->predictedTarget = inst_pc;
211 branch.target = inst_pc;
212 }
213 } else {
214 DPRINTF(Branch, "Not attempting prediction for inst: %s\n", *inst);
215 }
216
217 /* If we predict taken, set branch and update sequence numbers */
218 if (inst->predictedTaken) {
219 /* Update the predictionSeqNum and remember the streamSeqNum that it
220 * was associated with */
221 thread.expectedStreamSeqNum = inst->id.streamSeqNum;
222
223 BranchData new_branch = BranchData(BranchData::BranchPrediction,
224 inst->id.threadId,
225 inst->id.streamSeqNum, thread.predictionSeqNum + 1,
226 inst->predictedTarget, inst);
227
228 /* Mark with a new prediction number by the stream number of the
229 * instruction causing the prediction */
230 thread.predictionSeqNum++;
231 branch = new_branch;
232
233 DPRINTF(Branch, "Branch predicted taken inst: %s target: %s"
234 " new predictionSeqNum: %d\n",
235 *inst, inst->predictedTarget, thread.predictionSeqNum);
236 }
237}
238
239void
240Fetch2::evaluate()
241{
242 /* Push input onto appropriate input buffer */
243 if (!inp.outputWire->isBubble())
244 inputBuffer[inp.outputWire->id.threadId].setTail(*inp.outputWire);
245
246 ForwardInstData &insts_out = *out.inputWire;
247 BranchData prediction;
248 BranchData &branch_inp = *branchInp.outputWire;
249
250 assert(insts_out.isBubble());
251
252 /* React to branches from Execute to update local branch prediction
253 * structures */
254 updateBranchPrediction(branch_inp);
255
256 /* If a branch arrives, don't try and do anything about it. Only
257 * react to your own predictions */
258 if (branch_inp.isStreamChange()) {
259 DPRINTF(Fetch, "Dumping all input as a stream changing branch"
260 " has arrived\n");
261 dumpAllInput(branch_inp.threadId);
262 fetchInfo[branch_inp.threadId].havePC = false;
263 }
264
265 assert(insts_out.isBubble());
266 /* Even when blocked, clear out input lines with the wrong
267 * prediction sequence number */
268 for (ThreadID tid = 0; tid < cpu.numThreads; tid++) {
269 Fetch2ThreadInfo &thread = fetchInfo[tid];
270
271 thread.blocked = !nextStageReserve[tid].canReserve();
272
273 const ForwardLineData *line_in = getInput(tid);
274
275 while (line_in &&
276 thread.expectedStreamSeqNum == line_in->id.streamSeqNum &&
277 thread.predictionSeqNum != line_in->id.predictionSeqNum)
278 {
279 DPRINTF(Fetch, "Discarding line %s"
280 " due to predictionSeqNum mismatch (expected: %d)\n",
281 line_in->id, thread.predictionSeqNum);
282
283 popInput(tid);
284 fetchInfo[tid].havePC = false;
285
286 if (processMoreThanOneInput) {
287 DPRINTF(Fetch, "Wrapping\n");
288 line_in = getInput(tid);
289 } else {
290 line_in = NULL;
291 }
292 }
293 }
294
295 ThreadID tid = getScheduledThread();
296 DPRINTF(Fetch, "Scheduled Thread: %d\n", tid);
297
298 assert(insts_out.isBubble());
299 if (tid != InvalidThreadID) {
300 Fetch2ThreadInfo &fetch_info = fetchInfo[tid];
301
302 const ForwardLineData *line_in = getInput(tid);
303
304 unsigned int output_index = 0;
305
306 /* Pack instructions into the output while we can. This may involve
307 * using more than one input line. Note that lineWidth will be 0
308 * for faulting lines */
309 while (line_in &&
310 (line_in->isFault() ||
311 fetch_info.inputIndex < line_in->lineWidth) && /* More input */
312 output_index < outputWidth && /* More output to fill */
313 prediction.isBubble() /* No predicted branch */)
314 {
315 ThreadContext *thread = cpu.getContext(line_in->id.threadId);
316 TheISA::Decoder *decoder = thread->getDecoderPtr();
317
318 /* Discard line due to prediction sequence number being wrong but
319 * without the streamSeqNum number having changed */
320 bool discard_line =
321 fetch_info.expectedStreamSeqNum == line_in->id.streamSeqNum &&
322 fetch_info.predictionSeqNum != line_in->id.predictionSeqNum;
323
324 /* Set the PC if the stream changes. Setting havePC to false in
325 * a previous cycle handles all other change of flow of control
326 * issues */
327 bool set_pc = fetch_info.lastStreamSeqNum != line_in->id.streamSeqNum;
328
329 if (!discard_line && (!fetch_info.havePC || set_pc)) {
330 /* Set the inputIndex to be the MachInst-aligned offset
331 * from lineBaseAddr of the new PC value */
332 fetch_info.inputIndex =
333 (line_in->pc.instAddr() & BaseCPU::PCMask) -
334 line_in->lineBaseAddr;
335 DPRINTF(Fetch, "Setting new PC value: %s inputIndex: 0x%x"
336 " lineBaseAddr: 0x%x lineWidth: 0x%x\n",
337 line_in->pc, fetch_info.inputIndex, line_in->lineBaseAddr,
338 line_in->lineWidth);
339 fetch_info.pc = line_in->pc;
340 fetch_info.havePC = true;
341 decoder->reset();
342 }
343
344 /* The generated instruction. Leave as NULL if no instruction
345 * is to be packed into the output */
346 MinorDynInstPtr dyn_inst = NULL;
347
348 if (discard_line) {
349 /* Rest of line was from an older prediction in the same
350 * stream */
351 DPRINTF(Fetch, "Discarding line %s (from inputIndex: %d)"
352 " due to predictionSeqNum mismatch (expected: %d)\n",
353 line_in->id, fetch_info.inputIndex,
354 fetch_info.predictionSeqNum);
355 } else if (line_in->isFault()) {
356 /* Pack a fault as a MinorDynInst with ->fault set */
357
358 /* Make a new instruction and pick up the line, stream,
359 * prediction, thread ids from the incoming line */
360 dyn_inst = new MinorDynInst(line_in->id);
361
362 /* Fetch and prediction sequence numbers originate here */
363 dyn_inst->id.fetchSeqNum = fetch_info.fetchSeqNum;
364 dyn_inst->id.predictionSeqNum = fetch_info.predictionSeqNum;
365 /* To complete the set, test that exec sequence number has
366 * not been set */
367 assert(dyn_inst->id.execSeqNum == 0);
368
369 dyn_inst->pc = fetch_info.pc;
370
371 /* Pack a faulting instruction but allow other
372 * instructions to be generated. (Fetch2 makes no
373 * immediate judgement about streamSeqNum) */
374 dyn_inst->fault = line_in->fault;
375 DPRINTF(Fetch, "Fault being passed output_index: "
376 "%d: %s\n", output_index, dyn_inst->fault->name());
377 } else {
378 uint8_t *line = line_in->line;
379
380 TheISA::MachInst inst_word;
381 /* The instruction is wholly in the line, can just
382 * assign */
383 inst_word = TheISA::gtoh(
384 *(reinterpret_cast<TheISA::MachInst *>
385 (line + fetch_info.inputIndex)));
386
387 if (!decoder->instReady()) {
388 decoder->moreBytes(fetch_info.pc,
389 line_in->lineBaseAddr + fetch_info.inputIndex,
390 inst_word);
391 DPRINTF(Fetch, "Offering MachInst to decoder addr: 0x%x\n",
392 line_in->lineBaseAddr + fetch_info.inputIndex);
393 }
394
395 /* Maybe make the above a loop to accomodate ISAs with
396 * instructions longer than sizeof(MachInst) */
397
398 if (decoder->instReady()) {
399 /* Make a new instruction and pick up the line, stream,
400 * prediction, thread ids from the incoming line */
401 dyn_inst = new MinorDynInst(line_in->id);
402
403 /* Fetch and prediction sequence numbers originate here */
404 dyn_inst->id.fetchSeqNum = fetch_info.fetchSeqNum;
405 dyn_inst->id.predictionSeqNum = fetch_info.predictionSeqNum;
406 /* To complete the set, test that exec sequence number
407 * has not been set */
408 assert(dyn_inst->id.execSeqNum == 0);
409
410 /* Note that the decoder can update the given PC.
411 * Remember not to assign it until *after* calling
412 * decode */
413 StaticInstPtr decoded_inst = decoder->decode(fetch_info.pc);
414 dyn_inst->staticInst = decoded_inst;
415
416 dyn_inst->pc = fetch_info.pc;
417 DPRINTF(Fetch, "decoder inst %s\n", *dyn_inst);
418
419 // Collect some basic inst class stats
420 if (decoded_inst->isLoad())
421 loadInstructions++;
422 else if (decoded_inst->isStore())
423 storeInstructions++;
424 else if (decoded_inst->isAtomic())
425 amoInstructions++;
426 else if (decoded_inst->isVector())
427 vecInstructions++;
428 else if (decoded_inst->isFloating())
429 fpInstructions++;
430 else if (decoded_inst->isInteger())
431 intInstructions++;
432
433 DPRINTF(Fetch, "Instruction extracted from line %s"
434 " lineWidth: %d output_index: %d inputIndex: %d"
435 " pc: %s inst: %s\n",
436 line_in->id,
437 line_in->lineWidth, output_index, fetch_info.inputIndex,
438 fetch_info.pc, *dyn_inst);
439
440#if THE_ISA == X86_ISA || THE_ISA == ARM_ISA
441 /* In SE mode, it's possible to branch to a microop when
442 * replaying faults such as page faults (or simply
443 * intra-microcode branches in X86). Unfortunately,
444 * as Minor has micro-op decomposition in a separate
445 * pipeline stage from instruction decomposition, the
446 * following advancePC (which may follow a branch with
447 * microPC() != 0) *must* see a fresh macroop. This
448 * kludge should be improved with an addition to PCState
449 * but I offer it in this form for the moment
450 *
451 * X86 can branch within microops so we need to deal with
452 * the case that, after a branch, the first un-advanced PC
453 * may be pointing to a microop other than 0. Once
454 * advanced, however, the microop number *must* be 0 */
455 fetch_info.pc.upc(0);
456 fetch_info.pc.nupc(1);
457#endif
458
459 /* Advance PC for the next instruction */
460 TheISA::advancePC(fetch_info.pc, decoded_inst);
461
462 /* Predict any branches and issue a branch if
463 * necessary */
464 predictBranch(dyn_inst, prediction);
465 } else {
466 DPRINTF(Fetch, "Inst not ready yet\n");
467 }
468
469 /* Step on the pointer into the line if there's no
470 * complete instruction waiting */
471 if (decoder->needMoreBytes()) {
472 fetch_info.inputIndex += sizeof(TheISA::MachInst);
473
474 DPRINTF(Fetch, "Updated inputIndex value PC: %s"
475 " inputIndex: 0x%x lineBaseAddr: 0x%x lineWidth: 0x%x\n",
476 line_in->pc, fetch_info.inputIndex, line_in->lineBaseAddr,
477 line_in->lineWidth);
478 }
479 }
480
481 if (dyn_inst) {
482 /* Step to next sequence number */
483 fetch_info.fetchSeqNum++;
484
485 /* Correctly size the output before writing */
486 if (output_index == 0) {
487 insts_out.resize(outputWidth);
488 }
489 /* Pack the generated dynamic instruction into the output */
490 insts_out.insts[output_index] = dyn_inst;
491 output_index++;
492
493 /* Output MinorTrace instruction info for
494 * pre-microop decomposition macroops */
495 if (DTRACE(MinorTrace) && !dyn_inst->isFault() &&
496 dyn_inst->staticInst->isMacroop())
497 {
498 dyn_inst->minorTraceInst(*this);
499 }
500 }
501
502 /* Remember the streamSeqNum of this line so we can tell when
503 * we change stream */
504 fetch_info.lastStreamSeqNum = line_in->id.streamSeqNum;
505
506 /* Asked to discard line or there was a branch or fault */
507 if (!prediction.isBubble() || /* The remains of a
508 line with a prediction in it */
509 line_in->isFault() /* A line which is just a fault */)
510 {
511 DPRINTF(Fetch, "Discarding all input on branch/fault\n");
512 dumpAllInput(tid);
513 fetch_info.havePC = false;
514 line_in = NULL;
515 } else if (discard_line) {
516 /* Just discard one line, one's behind it may have new
517 * stream sequence numbers. There's a DPRINTF above
518 * for this event */
519 popInput(tid);
520 fetch_info.havePC = false;
521 line_in = NULL;
522 } else if (fetch_info.inputIndex == line_in->lineWidth) {
523 /* Got to end of a line, pop the line but keep PC
524 * in case this is a line-wrapping inst. */
525 popInput(tid);
526 line_in = NULL;
527 }
528
529 if (!line_in && processMoreThanOneInput) {
530 DPRINTF(Fetch, "Wrapping\n");
531 line_in = getInput(tid);
532 }
533 }
534
535 /* The rest of the output (if any) should already have been packed
536 * with bubble instructions by insts_out's initialisation */
537 }
538 if (tid == InvalidThreadID) {
539 assert(insts_out.isBubble());
540 }
541 /** Reserve a slot in the next stage and output data */
542 *predictionOut.inputWire = prediction;
543
544 /* If we generated output, reserve space for the result in the next stage
545 * and mark the stage as being active this cycle */
546 if (!insts_out.isBubble()) {
547 /* Note activity of following buffer */
548 cpu.activityRecorder->activity();
549 insts_out.threadId = tid;
550 nextStageReserve[tid].reserve();
551 }
552
553 /* If we still have input to process and somewhere to put it,
554 * mark stage as active */
555 for (ThreadID i = 0; i < cpu.numThreads; i++)
556 {
557 if (getInput(i) && nextStageReserve[i].canReserve()) {
558 cpu.activityRecorder->activateStage(Pipeline::Fetch2StageId);
559 break;
560 }
561 }
562
563 /* Make sure the input (if any left) is pushed */
564 if (!inp.outputWire->isBubble())
565 inputBuffer[inp.outputWire->id.threadId].pushTail();
566}
567
568inline ThreadID
569Fetch2::getScheduledThread()
570{
571 /* Select thread via policy. */
572 std::vector<ThreadID> priority_list;
573
574 switch (cpu.threadPolicy) {
575 case Enums::SingleThreaded:
576 priority_list.push_back(0);
577 break;
578 case Enums::RoundRobin:
579 priority_list = cpu.roundRobinPriority(threadPriority);
580 break;
581 case Enums::Random:
582 priority_list = cpu.randomPriority();
583 break;
584 default:
585 panic("Unknown fetch policy");
586 }
587
588 for (auto tid : priority_list) {
| 1/*
2 * Copyright (c) 2013-2014,2016 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are
16 * met: redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer;
18 * redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution;
21 * neither the name of the copyright holders nor the names of its
22 * contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 * Authors: Andrew Bardsley
38 */
39
40#include "cpu/minor/fetch2.hh"
41
42#include <string>
43
44#include "arch/decoder.hh"
45#include "arch/utility.hh"
46#include "cpu/minor/pipeline.hh"
47#include "cpu/pred/bpred_unit.hh"
48#include "debug/Branch.hh"
49#include "debug/Fetch.hh"
50#include "debug/MinorTrace.hh"
51
52namespace Minor
53{
54
55Fetch2::Fetch2(const std::string &name,
56 MinorCPU &cpu_,
57 MinorCPUParams ¶ms,
58 Latch<ForwardLineData>::Output inp_,
59 Latch<BranchData>::Output branchInp_,
60 Latch<BranchData>::Input predictionOut_,
61 Latch<ForwardInstData>::Input out_,
62 std::vector<InputBuffer<ForwardInstData>> &next_stage_input_buffer) :
63 Named(name),
64 cpu(cpu_),
65 inp(inp_),
66 branchInp(branchInp_),
67 predictionOut(predictionOut_),
68 out(out_),
69 nextStageReserve(next_stage_input_buffer),
70 outputWidth(params.decodeInputWidth),
71 processMoreThanOneInput(params.fetch2CycleInput),
72 branchPredictor(*params.branchPred),
73 fetchInfo(params.numThreads),
74 threadPriority(0)
75{
76 if (outputWidth < 1)
77 fatal("%s: decodeInputWidth must be >= 1 (%d)\n", name, outputWidth);
78
79 if (params.fetch2InputBufferSize < 1) {
80 fatal("%s: fetch2InputBufferSize must be >= 1 (%d)\n", name,
81 params.fetch2InputBufferSize);
82 }
83
84 /* Per-thread input buffers */
85 for (ThreadID tid = 0; tid < params.numThreads; tid++) {
86 inputBuffer.push_back(
87 InputBuffer<ForwardLineData>(
88 name + ".inputBuffer" + std::to_string(tid), "lines",
89 params.fetch2InputBufferSize));
90 }
91}
92
93const ForwardLineData *
94Fetch2::getInput(ThreadID tid)
95{
96 /* Get a line from the inputBuffer to work with */
97 if (!inputBuffer[tid].empty()) {
98 return &(inputBuffer[tid].front());
99 } else {
100 return NULL;
101 }
102}
103
104void
105Fetch2::popInput(ThreadID tid)
106{
107 if (!inputBuffer[tid].empty()) {
108 inputBuffer[tid].front().freeLine();
109 inputBuffer[tid].pop();
110 }
111
112 fetchInfo[tid].inputIndex = 0;
113}
114
115void
116Fetch2::dumpAllInput(ThreadID tid)
117{
118 DPRINTF(Fetch, "Dumping whole input buffer\n");
119 while (!inputBuffer[tid].empty())
120 popInput(tid);
121
122 fetchInfo[tid].inputIndex = 0;
123 fetchInfo[tid].havePC = false;
124}
125
126void
127Fetch2::updateBranchPrediction(const BranchData &branch)
128{
129 MinorDynInstPtr inst = branch.inst;
130
131 /* Don't even consider instructions we didn't try to predict or faults */
132 if (inst->isFault() || !inst->triedToPredict)
133 return;
134
135 switch (branch.reason) {
136 case BranchData::NoBranch:
137 /* No data to update */
138 break;
139 case BranchData::Interrupt:
140 /* Never try to predict interrupts */
141 break;
142 case BranchData::SuspendThread:
143 /* Don't need to act on suspends */
144 break;
145 case BranchData::HaltFetch:
146 /* Don't need to act on fetch wakeup */
147 break;
148 case BranchData::BranchPrediction:
149 /* Shouldn't happen. Fetch2 is the only source of
150 * BranchPredictions */
151 break;
152 case BranchData::UnpredictedBranch:
153 /* Unpredicted branch or barrier */
154 DPRINTF(Branch, "Unpredicted branch seen inst: %s\n", *inst);
155 branchPredictor.squash(inst->id.fetchSeqNum,
156 branch.target, true, inst->id.threadId);
157 // Update after squashing to accomodate O3CPU
158 // using the branch prediction code.
159 branchPredictor.update(inst->id.fetchSeqNum,
160 inst->id.threadId);
161 break;
162 case BranchData::CorrectlyPredictedBranch:
163 /* Predicted taken, was taken */
164 DPRINTF(Branch, "Branch predicted correctly inst: %s\n", *inst);
165 branchPredictor.update(inst->id.fetchSeqNum,
166 inst->id.threadId);
167 break;
168 case BranchData::BadlyPredictedBranch:
169 /* Predicted taken, not taken */
170 DPRINTF(Branch, "Branch mis-predicted inst: %s\n", *inst);
171 branchPredictor.squash(inst->id.fetchSeqNum,
172 branch.target /* Not used */, false, inst->id.threadId);
173 // Update after squashing to accomodate O3CPU
174 // using the branch prediction code.
175 branchPredictor.update(inst->id.fetchSeqNum,
176 inst->id.threadId);
177 break;
178 case BranchData::BadlyPredictedBranchTarget:
179 /* Predicted taken, was taken but to a different target */
180 DPRINTF(Branch, "Branch mis-predicted target inst: %s target: %s\n",
181 *inst, branch.target);
182 branchPredictor.squash(inst->id.fetchSeqNum,
183 branch.target, true, inst->id.threadId);
184 break;
185 }
186}
187
188void
189Fetch2::predictBranch(MinorDynInstPtr inst, BranchData &branch)
190{
191 Fetch2ThreadInfo &thread = fetchInfo[inst->id.threadId];
192 TheISA::PCState inst_pc = inst->pc;
193
194 assert(!inst->predictedTaken);
195
196 /* Skip non-control/sys call instructions */
197 if (inst->staticInst->isControl() ||
198 inst->staticInst->isSyscall())
199 {
200 /* Tried to predict */
201 inst->triedToPredict = true;
202
203 DPRINTF(Branch, "Trying to predict for inst: %s\n", *inst);
204
205 if (branchPredictor.predict(inst->staticInst,
206 inst->id.fetchSeqNum, inst_pc,
207 inst->id.threadId))
208 {
209 inst->predictedTaken = true;
210 inst->predictedTarget = inst_pc;
211 branch.target = inst_pc;
212 }
213 } else {
214 DPRINTF(Branch, "Not attempting prediction for inst: %s\n", *inst);
215 }
216
217 /* If we predict taken, set branch and update sequence numbers */
218 if (inst->predictedTaken) {
219 /* Update the predictionSeqNum and remember the streamSeqNum that it
220 * was associated with */
221 thread.expectedStreamSeqNum = inst->id.streamSeqNum;
222
223 BranchData new_branch = BranchData(BranchData::BranchPrediction,
224 inst->id.threadId,
225 inst->id.streamSeqNum, thread.predictionSeqNum + 1,
226 inst->predictedTarget, inst);
227
228 /* Mark with a new prediction number by the stream number of the
229 * instruction causing the prediction */
230 thread.predictionSeqNum++;
231 branch = new_branch;
232
233 DPRINTF(Branch, "Branch predicted taken inst: %s target: %s"
234 " new predictionSeqNum: %d\n",
235 *inst, inst->predictedTarget, thread.predictionSeqNum);
236 }
237}
238
239void
240Fetch2::evaluate()
241{
242 /* Push input onto appropriate input buffer */
243 if (!inp.outputWire->isBubble())
244 inputBuffer[inp.outputWire->id.threadId].setTail(*inp.outputWire);
245
246 ForwardInstData &insts_out = *out.inputWire;
247 BranchData prediction;
248 BranchData &branch_inp = *branchInp.outputWire;
249
250 assert(insts_out.isBubble());
251
252 /* React to branches from Execute to update local branch prediction
253 * structures */
254 updateBranchPrediction(branch_inp);
255
256 /* If a branch arrives, don't try and do anything about it. Only
257 * react to your own predictions */
258 if (branch_inp.isStreamChange()) {
259 DPRINTF(Fetch, "Dumping all input as a stream changing branch"
260 " has arrived\n");
261 dumpAllInput(branch_inp.threadId);
262 fetchInfo[branch_inp.threadId].havePC = false;
263 }
264
265 assert(insts_out.isBubble());
266 /* Even when blocked, clear out input lines with the wrong
267 * prediction sequence number */
268 for (ThreadID tid = 0; tid < cpu.numThreads; tid++) {
269 Fetch2ThreadInfo &thread = fetchInfo[tid];
270
271 thread.blocked = !nextStageReserve[tid].canReserve();
272
273 const ForwardLineData *line_in = getInput(tid);
274
275 while (line_in &&
276 thread.expectedStreamSeqNum == line_in->id.streamSeqNum &&
277 thread.predictionSeqNum != line_in->id.predictionSeqNum)
278 {
279 DPRINTF(Fetch, "Discarding line %s"
280 " due to predictionSeqNum mismatch (expected: %d)\n",
281 line_in->id, thread.predictionSeqNum);
282
283 popInput(tid);
284 fetchInfo[tid].havePC = false;
285
286 if (processMoreThanOneInput) {
287 DPRINTF(Fetch, "Wrapping\n");
288 line_in = getInput(tid);
289 } else {
290 line_in = NULL;
291 }
292 }
293 }
294
295 ThreadID tid = getScheduledThread();
296 DPRINTF(Fetch, "Scheduled Thread: %d\n", tid);
297
298 assert(insts_out.isBubble());
299 if (tid != InvalidThreadID) {
300 Fetch2ThreadInfo &fetch_info = fetchInfo[tid];
301
302 const ForwardLineData *line_in = getInput(tid);
303
304 unsigned int output_index = 0;
305
306 /* Pack instructions into the output while we can. This may involve
307 * using more than one input line. Note that lineWidth will be 0
308 * for faulting lines */
309 while (line_in &&
310 (line_in->isFault() ||
311 fetch_info.inputIndex < line_in->lineWidth) && /* More input */
312 output_index < outputWidth && /* More output to fill */
313 prediction.isBubble() /* No predicted branch */)
314 {
315 ThreadContext *thread = cpu.getContext(line_in->id.threadId);
316 TheISA::Decoder *decoder = thread->getDecoderPtr();
317
318 /* Discard line due to prediction sequence number being wrong but
319 * without the streamSeqNum number having changed */
320 bool discard_line =
321 fetch_info.expectedStreamSeqNum == line_in->id.streamSeqNum &&
322 fetch_info.predictionSeqNum != line_in->id.predictionSeqNum;
323
324 /* Set the PC if the stream changes. Setting havePC to false in
325 * a previous cycle handles all other change of flow of control
326 * issues */
327 bool set_pc = fetch_info.lastStreamSeqNum != line_in->id.streamSeqNum;
328
329 if (!discard_line && (!fetch_info.havePC || set_pc)) {
330 /* Set the inputIndex to be the MachInst-aligned offset
331 * from lineBaseAddr of the new PC value */
332 fetch_info.inputIndex =
333 (line_in->pc.instAddr() & BaseCPU::PCMask) -
334 line_in->lineBaseAddr;
335 DPRINTF(Fetch, "Setting new PC value: %s inputIndex: 0x%x"
336 " lineBaseAddr: 0x%x lineWidth: 0x%x\n",
337 line_in->pc, fetch_info.inputIndex, line_in->lineBaseAddr,
338 line_in->lineWidth);
339 fetch_info.pc = line_in->pc;
340 fetch_info.havePC = true;
341 decoder->reset();
342 }
343
344 /* The generated instruction. Leave as NULL if no instruction
345 * is to be packed into the output */
346 MinorDynInstPtr dyn_inst = NULL;
347
348 if (discard_line) {
349 /* Rest of line was from an older prediction in the same
350 * stream */
351 DPRINTF(Fetch, "Discarding line %s (from inputIndex: %d)"
352 " due to predictionSeqNum mismatch (expected: %d)\n",
353 line_in->id, fetch_info.inputIndex,
354 fetch_info.predictionSeqNum);
355 } else if (line_in->isFault()) {
356 /* Pack a fault as a MinorDynInst with ->fault set */
357
358 /* Make a new instruction and pick up the line, stream,
359 * prediction, thread ids from the incoming line */
360 dyn_inst = new MinorDynInst(line_in->id);
361
362 /* Fetch and prediction sequence numbers originate here */
363 dyn_inst->id.fetchSeqNum = fetch_info.fetchSeqNum;
364 dyn_inst->id.predictionSeqNum = fetch_info.predictionSeqNum;
365 /* To complete the set, test that exec sequence number has
366 * not been set */
367 assert(dyn_inst->id.execSeqNum == 0);
368
369 dyn_inst->pc = fetch_info.pc;
370
371 /* Pack a faulting instruction but allow other
372 * instructions to be generated. (Fetch2 makes no
373 * immediate judgement about streamSeqNum) */
374 dyn_inst->fault = line_in->fault;
375 DPRINTF(Fetch, "Fault being passed output_index: "
376 "%d: %s\n", output_index, dyn_inst->fault->name());
377 } else {
378 uint8_t *line = line_in->line;
379
380 TheISA::MachInst inst_word;
381 /* The instruction is wholly in the line, can just
382 * assign */
383 inst_word = TheISA::gtoh(
384 *(reinterpret_cast<TheISA::MachInst *>
385 (line + fetch_info.inputIndex)));
386
387 if (!decoder->instReady()) {
388 decoder->moreBytes(fetch_info.pc,
389 line_in->lineBaseAddr + fetch_info.inputIndex,
390 inst_word);
391 DPRINTF(Fetch, "Offering MachInst to decoder addr: 0x%x\n",
392 line_in->lineBaseAddr + fetch_info.inputIndex);
393 }
394
395 /* Maybe make the above a loop to accomodate ISAs with
396 * instructions longer than sizeof(MachInst) */
397
398 if (decoder->instReady()) {
399 /* Make a new instruction and pick up the line, stream,
400 * prediction, thread ids from the incoming line */
401 dyn_inst = new MinorDynInst(line_in->id);
402
403 /* Fetch and prediction sequence numbers originate here */
404 dyn_inst->id.fetchSeqNum = fetch_info.fetchSeqNum;
405 dyn_inst->id.predictionSeqNum = fetch_info.predictionSeqNum;
406 /* To complete the set, test that exec sequence number
407 * has not been set */
408 assert(dyn_inst->id.execSeqNum == 0);
409
410 /* Note that the decoder can update the given PC.
411 * Remember not to assign it until *after* calling
412 * decode */
413 StaticInstPtr decoded_inst = decoder->decode(fetch_info.pc);
414 dyn_inst->staticInst = decoded_inst;
415
416 dyn_inst->pc = fetch_info.pc;
417 DPRINTF(Fetch, "decoder inst %s\n", *dyn_inst);
418
419 // Collect some basic inst class stats
420 if (decoded_inst->isLoad())
421 loadInstructions++;
422 else if (decoded_inst->isStore())
423 storeInstructions++;
424 else if (decoded_inst->isAtomic())
425 amoInstructions++;
426 else if (decoded_inst->isVector())
427 vecInstructions++;
428 else if (decoded_inst->isFloating())
429 fpInstructions++;
430 else if (decoded_inst->isInteger())
431 intInstructions++;
432
433 DPRINTF(Fetch, "Instruction extracted from line %s"
434 " lineWidth: %d output_index: %d inputIndex: %d"
435 " pc: %s inst: %s\n",
436 line_in->id,
437 line_in->lineWidth, output_index, fetch_info.inputIndex,
438 fetch_info.pc, *dyn_inst);
439
440#if THE_ISA == X86_ISA || THE_ISA == ARM_ISA
441 /* In SE mode, it's possible to branch to a microop when
442 * replaying faults such as page faults (or simply
443 * intra-microcode branches in X86). Unfortunately,
444 * as Minor has micro-op decomposition in a separate
445 * pipeline stage from instruction decomposition, the
446 * following advancePC (which may follow a branch with
447 * microPC() != 0) *must* see a fresh macroop. This
448 * kludge should be improved with an addition to PCState
449 * but I offer it in this form for the moment
450 *
451 * X86 can branch within microops so we need to deal with
452 * the case that, after a branch, the first un-advanced PC
453 * may be pointing to a microop other than 0. Once
454 * advanced, however, the microop number *must* be 0 */
455 fetch_info.pc.upc(0);
456 fetch_info.pc.nupc(1);
457#endif
458
459 /* Advance PC for the next instruction */
460 TheISA::advancePC(fetch_info.pc, decoded_inst);
461
462 /* Predict any branches and issue a branch if
463 * necessary */
464 predictBranch(dyn_inst, prediction);
465 } else {
466 DPRINTF(Fetch, "Inst not ready yet\n");
467 }
468
469 /* Step on the pointer into the line if there's no
470 * complete instruction waiting */
471 if (decoder->needMoreBytes()) {
472 fetch_info.inputIndex += sizeof(TheISA::MachInst);
473
474 DPRINTF(Fetch, "Updated inputIndex value PC: %s"
475 " inputIndex: 0x%x lineBaseAddr: 0x%x lineWidth: 0x%x\n",
476 line_in->pc, fetch_info.inputIndex, line_in->lineBaseAddr,
477 line_in->lineWidth);
478 }
479 }
480
481 if (dyn_inst) {
482 /* Step to next sequence number */
483 fetch_info.fetchSeqNum++;
484
485 /* Correctly size the output before writing */
486 if (output_index == 0) {
487 insts_out.resize(outputWidth);
488 }
489 /* Pack the generated dynamic instruction into the output */
490 insts_out.insts[output_index] = dyn_inst;
491 output_index++;
492
493 /* Output MinorTrace instruction info for
494 * pre-microop decomposition macroops */
495 if (DTRACE(MinorTrace) && !dyn_inst->isFault() &&
496 dyn_inst->staticInst->isMacroop())
497 {
498 dyn_inst->minorTraceInst(*this);
499 }
500 }
501
502 /* Remember the streamSeqNum of this line so we can tell when
503 * we change stream */
504 fetch_info.lastStreamSeqNum = line_in->id.streamSeqNum;
505
506 /* Asked to discard line or there was a branch or fault */
507 if (!prediction.isBubble() || /* The remains of a
508 line with a prediction in it */
509 line_in->isFault() /* A line which is just a fault */)
510 {
511 DPRINTF(Fetch, "Discarding all input on branch/fault\n");
512 dumpAllInput(tid);
513 fetch_info.havePC = false;
514 line_in = NULL;
515 } else if (discard_line) {
516 /* Just discard one line, one's behind it may have new
517 * stream sequence numbers. There's a DPRINTF above
518 * for this event */
519 popInput(tid);
520 fetch_info.havePC = false;
521 line_in = NULL;
522 } else if (fetch_info.inputIndex == line_in->lineWidth) {
523 /* Got to end of a line, pop the line but keep PC
524 * in case this is a line-wrapping inst. */
525 popInput(tid);
526 line_in = NULL;
527 }
528
529 if (!line_in && processMoreThanOneInput) {
530 DPRINTF(Fetch, "Wrapping\n");
531 line_in = getInput(tid);
532 }
533 }
534
535 /* The rest of the output (if any) should already have been packed
536 * with bubble instructions by insts_out's initialisation */
537 }
538 if (tid == InvalidThreadID) {
539 assert(insts_out.isBubble());
540 }
541 /** Reserve a slot in the next stage and output data */
542 *predictionOut.inputWire = prediction;
543
544 /* If we generated output, reserve space for the result in the next stage
545 * and mark the stage as being active this cycle */
546 if (!insts_out.isBubble()) {
547 /* Note activity of following buffer */
548 cpu.activityRecorder->activity();
549 insts_out.threadId = tid;
550 nextStageReserve[tid].reserve();
551 }
552
553 /* If we still have input to process and somewhere to put it,
554 * mark stage as active */
555 for (ThreadID i = 0; i < cpu.numThreads; i++)
556 {
557 if (getInput(i) && nextStageReserve[i].canReserve()) {
558 cpu.activityRecorder->activateStage(Pipeline::Fetch2StageId);
559 break;
560 }
561 }
562
563 /* Make sure the input (if any left) is pushed */
564 if (!inp.outputWire->isBubble())
565 inputBuffer[inp.outputWire->id.threadId].pushTail();
566}
567
568inline ThreadID
569Fetch2::getScheduledThread()
570{
571 /* Select thread via policy. */
572 std::vector<ThreadID> priority_list;
573
574 switch (cpu.threadPolicy) {
575 case Enums::SingleThreaded:
576 priority_list.push_back(0);
577 break;
578 case Enums::RoundRobin:
579 priority_list = cpu.roundRobinPriority(threadPriority);
580 break;
581 case Enums::Random:
582 priority_list = cpu.randomPriority();
583 break;
584 default:
585 panic("Unknown fetch policy");
586 }
587
588 for (auto tid : priority_list) {
|