1/*
2 * Copyright (c) 2013-2014 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 <string>
41
42#include "arch/decoder.hh"
43#include "arch/utility.hh"
44#include "cpu/minor/fetch2.hh"
45#include "cpu/minor/pipeline.hh"
46#include "cpu/pred/bpred_unit.hh"
47#include "debug/Branch.hh"
48#include "debug/Fetch.hh"
49#include "debug/MinorTrace.hh"
50
51namespace Minor
52{
53
54Fetch2::Fetch2(const std::string &name,
55 MinorCPU &cpu_,
56 MinorCPUParams &params,
57 Latch<ForwardLineData>::Output inp_,
58 Latch<BranchData>::Output branchInp_,
59 Latch<BranchData>::Input predictionOut_,
60 Latch<ForwardInstData>::Input out_,
61 Reservable &next_stage_input_buffer) :
62 Named(name),
63 cpu(cpu_),
64 inp(inp_),
65 branchInp(branchInp_),
66 predictionOut(predictionOut_),
67 out(out_),
68 nextStageReserve(next_stage_input_buffer),
69 outputWidth(params.decodeInputWidth),
70 processMoreThanOneInput(params.fetch2CycleInput),
71 branchPredictor(*params.branchPred),
72 inputBuffer(name + ".inputBuffer", "lines", params.fetch2InputBufferSize),
73 inputIndex(0),
74 pc(TheISA::PCState(0)),
75 havePC(false),
76 lastStreamSeqNum(InstId::firstStreamSeqNum),
77 fetchSeqNum(InstId::firstFetchSeqNum),
78 expectedStreamSeqNum(InstId::firstStreamSeqNum),
79 predictionSeqNum(InstId::firstPredictionSeqNum)
80{
81 if (outputWidth < 1)
82 fatal("%s: decodeInputWidth must be >= 1 (%d)\n", name, outputWidth);
83
84 if (params.fetch2InputBufferSize < 1) {
85 fatal("%s: fetch2InputBufferSize must be >= 1 (%d)\n", name,
86 params.fetch2InputBufferSize);
87 }
88}
89
90const ForwardLineData *
91Fetch2::getInput()
92{
93 /* Get a line from the inputBuffer to work with */
94 if (!inputBuffer.empty()) {
95 return &(inputBuffer.front());
96 } else {
97 return NULL;
98 }
99}
100
101void
102Fetch2::popInput()
103{
104 if (!inputBuffer.empty()) {
105 inputBuffer.front().freeLine();
106 inputBuffer.pop();
107 }
108
109 inputIndex = 0;
110}
111
112void
113Fetch2::dumpAllInput()
114{
115 DPRINTF(Fetch, "Dumping whole input buffer\n");
116 while (!inputBuffer.empty())
117 popInput();
118
119 inputIndex = 0;
120}
121
122void
123Fetch2::updateBranchPrediction(const BranchData &branch)
124{
125 MinorDynInstPtr inst = branch.inst;
126
127 /* Don't even consider instructions we didn't try to predict or faults */
128 if (inst->isFault() || !inst->triedToPredict)
129 return;
130
131 switch (branch.reason) {
132 case BranchData::NoBranch:
133 /* No data to update */
134 break;
135 case BranchData::Interrupt:
136 /* Never try to predict interrupts */
137 break;
138 case BranchData::SuspendThread:
139 /* Don't need to act on suspends */
140 break;
141 case BranchData::WakeupFetch:
142 /* Don't need to act on wakeups, no instruction tied to action. */
143 break;
144 case BranchData::HaltFetch:
145 /* Don't need to act on fetch wakeup */
146 break;
147 case BranchData::BranchPrediction:
148 /* Shouldn't happen. Fetch2 is the only source of
149 * BranchPredictions */
150 break;
151 case BranchData::UnpredictedBranch:
152 /* Unpredicted branch or barrier */
153 DPRINTF(Branch, "Unpredicted branch seen inst: %s\n", *inst);
154 branchPredictor.squash(inst->id.fetchSeqNum,
155 branch.target, true, inst->id.threadId);
156 break;
157 case BranchData::CorrectlyPredictedBranch:
158 /* Predicted taken, was taken */
159 DPRINTF(Branch, "Branch predicted correctly inst: %s\n", *inst);
160 branchPredictor.update(inst->id.fetchSeqNum,
161 inst->id.threadId);
162 break;
163 case BranchData::BadlyPredictedBranch:
164 /* Predicted taken, not taken */
165 DPRINTF(Branch, "Branch mis-predicted inst: %s\n", *inst);
166 branchPredictor.squash(inst->id.fetchSeqNum,
167 branch.target /* Not used */, false, inst->id.threadId);
168 break;
169 case BranchData::BadlyPredictedBranchTarget:
170 /* Predicted taken, was taken but to a different target */
171 DPRINTF(Branch, "Branch mis-predicted target inst: %s target: %s\n",
172 *inst, branch.target);
173 branchPredictor.squash(inst->id.fetchSeqNum,
174 branch.target, true, inst->id.threadId);
175 break;
176 }
177}
178
179void
180Fetch2::predictBranch(MinorDynInstPtr inst, BranchData &branch)
181{
182 TheISA::PCState inst_pc = inst->pc;
183
184 assert(!inst->predictedTaken);
185
186 /* Skip non-control/sys call instructions */
187 if (inst->staticInst->isControl() ||
188 inst->staticInst->isSyscall())
189 {
190 /* Tried to predict */
191 inst->triedToPredict = true;
192
193 DPRINTF(Branch, "Trying to predict for inst: %s\n", *inst);
194
195 if (branchPredictor.predict(inst->staticInst,
196 inst->id.fetchSeqNum, inst_pc,
197 inst->id.threadId))
198 {
199 inst->predictedTaken = true;
200 inst->predictedTarget = inst_pc;
201 branch.target = inst_pc;
202 }
203 } else {
204 DPRINTF(Branch, "Not attempting prediction for inst: %s\n", *inst);
205 }
206
207 /* If we predict taken, set branch and update sequence numbers */
208 if (inst->predictedTaken) {
209 /* Update the predictionSeqNum and remember the streamSeqNum that it
210 * was associated with */
211 expectedStreamSeqNum = inst->id.streamSeqNum;
212
213 BranchData new_branch = BranchData(BranchData::BranchPrediction,
214 inst->id.streamSeqNum, predictionSeqNum + 1,
215 inst->predictedTarget, inst);
216
217 /* Mark with a new prediction number by the stream number of the
218 * instruction causing the prediction */
219 predictionSeqNum++;
220 branch = new_branch;
221
222 DPRINTF(Branch, "Branch predicted taken inst: %s target: %s"
223 " new predictionSeqNum: %d\n",
224 *inst, inst->predictedTarget, predictionSeqNum);
225 }
226}
227
228void
229Fetch2::evaluate()
230{
231 inputBuffer.setTail(*inp.outputWire);
232 ForwardInstData &insts_out = *out.inputWire;
233 BranchData prediction;
234 BranchData &branch_inp = *branchInp.outputWire;
235
236 assert(insts_out.isBubble());
237
238 blocked = false;
239
240 /* React to branches from Execute to update local branch prediction
241 * structures */
242 updateBranchPrediction(branch_inp);
243
244 /* If a branch arrives, don't try and do anything about it. Only
245 * react to your own predictions */
246 if (branch_inp.isStreamChange()) {
247 DPRINTF(Fetch, "Dumping all input as a stream changing branch"
248 " has arrived\n");
249 dumpAllInput();
250 havePC = false;
251 }
252
253 /* Even when blocked, clear out input lines with the wrong
254 * prediction sequence number */
255 {
256 const ForwardLineData *line_in = getInput();
257
258 while (line_in &&
259 expectedStreamSeqNum == line_in->id.streamSeqNum &&
260 predictionSeqNum != line_in->id.predictionSeqNum)
261 {
262 DPRINTF(Fetch, "Discarding line %s"
263 " due to predictionSeqNum mismatch (expected: %d)\n",
264 line_in->id, predictionSeqNum);
265
266 popInput();
267 havePC = false;
268
269 if (processMoreThanOneInput) {
270 DPRINTF(Fetch, "Wrapping\n");
271 line_in = getInput();
272 } else {
273 line_in = NULL;
274 }
275 }
276 }
277
278 if (!nextStageReserve.canReserve()) {
279 blocked = true;
280 } else {
281 const ForwardLineData *line_in = getInput();
282
283 unsigned int output_index = 0;
284
285 /* Pack instructions into the output while we can. This may involve
286 * using more than one input line. Note that lineWidth will be 0
287 * for faulting lines */
288 while (line_in &&
289 (line_in->isFault() ||
290 inputIndex < line_in->lineWidth) && /* More input */
291 output_index < outputWidth && /* More output to fill */
292 prediction.isBubble() /* No predicted branch */)
293 {
294 ThreadContext *thread = cpu.getContext(line_in->id.threadId);
295 TheISA::Decoder *decoder = thread->getDecoderPtr();
296
297 /* Discard line due to prediction sequence number being wrong but
298 * without the streamSeqNum number having changed */
299 bool discard_line =
300 expectedStreamSeqNum == line_in->id.streamSeqNum &&
301 predictionSeqNum != line_in->id.predictionSeqNum;
302
303 /* Set the PC if the stream changes. Setting havePC to false in
304 * a previous cycle handles all other change of flow of control
305 * issues */
306 bool set_pc = lastStreamSeqNum != line_in->id.streamSeqNum;
307
308 if (!discard_line && (!havePC || set_pc)) {
309 /* Set the inputIndex to be the MachInst-aligned offset
310 * from lineBaseAddr of the new PC value */
311 inputIndex =
312 (line_in->pc.instAddr() & BaseCPU::PCMask) -
313 line_in->lineBaseAddr;
314 DPRINTF(Fetch, "Setting new PC value: %s inputIndex: 0x%x"
315 " lineBaseAddr: 0x%x lineWidth: 0x%x\n",
316 line_in->pc, inputIndex, line_in->lineBaseAddr,
317 line_in->lineWidth);
318 pc = line_in->pc;
319 havePC = true;
320 decoder->reset();
321 }
322
323 /* The generated instruction. Leave as NULL if no instruction
324 * is to be packed into the output */
325 MinorDynInstPtr dyn_inst = NULL;
326
327 if (discard_line) {
328 /* Rest of line was from an older prediction in the same
329 * stream */
330 DPRINTF(Fetch, "Discarding line %s (from inputIndex: %d)"
331 " due to predictionSeqNum mismatch (expected: %d)\n",
332 line_in->id, inputIndex, predictionSeqNum);
333 } else if (line_in->isFault()) {
334 /* Pack a fault as a MinorDynInst with ->fault set */
335
336 /* Make a new instruction and pick up the line, stream,
337 * prediction, thread ids from the incoming line */
338 dyn_inst = new MinorDynInst(line_in->id);
339
340 /* Fetch and prediction sequence numbers originate here */
341 dyn_inst->id.fetchSeqNum = fetchSeqNum;
342 dyn_inst->id.predictionSeqNum = predictionSeqNum;
343 /* To complete the set, test that exec sequence number has
344 * not been set */
345 assert(dyn_inst->id.execSeqNum == 0);
346
347 dyn_inst->pc = pc;
348
349 /* Pack a faulting instruction but allow other
350 * instructions to be generated. (Fetch2 makes no
351 * immediate judgement about streamSeqNum) */
352 dyn_inst->fault = line_in->fault;
353 DPRINTF(Fetch, "Fault being passed output_index: "
354 "%d: %s\n", output_index, dyn_inst->fault->name());
355 } else {
356 uint8_t *line = line_in->line;
357
358 TheISA::MachInst inst_word;
359 /* The instruction is wholly in the line, can just
360 * assign */
361 inst_word = TheISA::gtoh(
362 *(reinterpret_cast<TheISA::MachInst *>
363 (line + inputIndex)));
364
365 if (!decoder->instReady()) {
366 decoder->moreBytes(pc,
367 line_in->lineBaseAddr + inputIndex, inst_word);
368 DPRINTF(Fetch, "Offering MachInst to decoder"
369 " addr: 0x%x\n", line_in->lineBaseAddr + inputIndex);
370 }
371
372 /* Maybe make the above a loop to accomodate ISAs with
373 * instructions longer than sizeof(MachInst) */
374
375 if (decoder->instReady()) {
376 /* Make a new instruction and pick up the line, stream,
377 * prediction, thread ids from the incoming line */
378 dyn_inst = new MinorDynInst(line_in->id);
379
380 /* Fetch and prediction sequence numbers originate here */
381 dyn_inst->id.fetchSeqNum = fetchSeqNum;
382 dyn_inst->id.predictionSeqNum = predictionSeqNum;
383 /* To complete the set, test that exec sequence number
384 * has not been set */
385 assert(dyn_inst->id.execSeqNum == 0);
386
387 /* Note that the decoder can update the given PC.
388 * Remember not to assign it until *after* calling
389 * decode */
390 StaticInstPtr decoded_inst = decoder->decode(pc);
391 dyn_inst->staticInst = decoded_inst;
392
393 dyn_inst->pc = pc;
394
395 DPRINTF(Fetch, "Instruction extracted from line %s"
396 " lineWidth: %d output_index: %d inputIndex: %d"
397 " pc: %s inst: %s\n",
398 line_in->id,
399 line_in->lineWidth, output_index, inputIndex,
400 pc, *dyn_inst);
401
402#if THE_ISA == X86_ISA || THE_ISA == ARM_ISA
403 /* In SE mode, it's possible to branch to a microop when
404 * replaying faults such as page faults (or simply
405 * intra-microcode branches in X86). Unfortunately,
406 * as Minor has micro-op decomposition in a separate
407 * pipeline stage from instruction decomposition, the
408 * following advancePC (which may follow a branch with
409 * microPC() != 0) *must* see a fresh macroop. This
410 * kludge should be improved with an addition to PCState
411 * but I offer it in this form for the moment
412 *
413 * X86 can branch within microops so we need to deal with
414 * the case that, after a branch, the first un-advanced PC
415 * may be pointing to a microop other than 0. Once
416 * advanced, however, the microop number *must* be 0 */
417 pc.upc(0);
418 pc.nupc(1);
419#endif
420
421 /* Advance PC for the next instruction */
422 TheISA::advancePC(pc, decoded_inst);
423
424 /* Predict any branches and issue a branch if
425 * necessary */
426 predictBranch(dyn_inst, prediction);
427 } else {
428 DPRINTF(Fetch, "Inst not ready yet\n");
429 }
430
431 /* Step on the pointer into the line if there's no
432 * complete instruction waiting */
433 if (decoder->needMoreBytes()) {
434 inputIndex += sizeof(TheISA::MachInst);
435
436 DPRINTF(Fetch, "Updated inputIndex value PC: %s"
437 " inputIndex: 0x%x lineBaseAddr: 0x%x lineWidth: 0x%x\n",
438 line_in->pc, inputIndex, line_in->lineBaseAddr,
439 line_in->lineWidth);
440 }
441 }
442
443 if (dyn_inst) {
444 /* Step to next sequence number */
445 fetchSeqNum++;
446
447 /* Correctly size the output before writing */
448 if (output_index == 0)
449 insts_out.resize(outputWidth);
450 /* Pack the generated dynamic instruction into the output */
451 insts_out.insts[output_index] = dyn_inst;
452 output_index++;
453
454 /* Output MinorTrace instruction info for
455 * pre-microop decomposition macroops */
456 if (DTRACE(MinorTrace) && !dyn_inst->isFault() &&
457 dyn_inst->staticInst->isMacroop())
458 {
459 dyn_inst->minorTraceInst(*this);
460 }
461 }
462
463 /* Remember the streamSeqNum of this line so we can tell when
464 * we change stream */
465 lastStreamSeqNum = line_in->id.streamSeqNum;
466
467 /* Asked to discard line or there was a branch or fault */
468 if (!prediction.isBubble() || /* The remains of a
469 line with a prediction in it */
470 line_in->isFault() /* A line which is just a fault */)
471 {
472 DPRINTF(Fetch, "Discarding all input on branch/fault\n");
473 dumpAllInput();
474 havePC = false;
475 line_in = NULL;
476 } else if (discard_line) {
477 /* Just discard one line, one's behind it may have new
478 * stream sequence numbers. There's a DPRINTF above
479 * for this event */
480 popInput();
481 havePC = false;
482 line_in = NULL;
483 } else if (inputIndex == line_in->lineWidth) {
484 /* Got to end of a line, pop the line but keep PC
485 * in case this is a line-wrapping inst. */
486 popInput();
487 line_in = NULL;
488 }
489
490 if (!line_in && processMoreThanOneInput) {
491 DPRINTF(Fetch, "Wrapping\n");
492 line_in = getInput();
493 }
494 }
495
496 /* The rest of the output (if any) should already have been packed
497 * with bubble instructions by insts_out's initialisation */
498 }
499
500 /** Reserve a slot in the next stage and output data */
501 *predictionOut.inputWire = prediction;
502
503 /* If we generated output, reserve space for the result in the next stage
504 * and mark the stage as being active this cycle */
505 if (!insts_out.isBubble()) {
506 /* Note activity of following buffer */
507 cpu.activityRecorder->activity();
508 nextStageReserve.reserve();
509 }
510
511 /* If we still have input to process and somewhere to put it,
512 * mark stage as active */
513 if (getInput() && nextStageReserve.canReserve())
514 cpu.activityRecorder->activateStage(Pipeline::Fetch2StageId);
515
516 /* Make sure the input (if any left) is pushed */
517 inputBuffer.pushTail();
518}
519
520bool
521Fetch2::isDrained()
522{
523 return inputBuffer.empty() &&
524 (*inp.outputWire).isBubble() &&
525 (*predictionOut.inputWire).isBubble();
526}
527
528void
529Fetch2::minorTrace() const
530{
531 std::ostringstream data;
532
533 if (blocked)
534 data << 'B';
535 else
536 (*out.inputWire).reportData(data);
537
538 MINORTRACE("inputIndex=%d havePC=%d predictionSeqNum=%d insts=%s\n",
539 inputIndex, havePC, predictionSeqNum, data.str());
540 inputBuffer.minorTrace();
541}
542
543}