1. Field
Various different embodiments relate to methods, apparatus, or systems for prefetching instructions. In particular, various different embodiments relate to methods, apparatus, or systems for prefetching instructions using cache line history.
2. Background Information
Processors and other instruction processing apparatus commonly perform instruction prefetching in order to help increase performance. Processor speed (e.g., the speed of execution of instructions by the processor) typically is significantly faster than the speed of the memory subsystem (e.g., the speed of accessing instructions from memory). Instruction prefetching may involve speculatively fetching or otherwise accessing instructions from memory before the processor requests the instructions for execution. The prefetched instructions may be stored in a processor cache until they are ready to be executed. When the prefetched instructions ready to be executed, the instructions may be accessed from the cache, more rapidly than they could have been accessed from memory. However, if the instructions were not prefetched and were not available in the instruction cache (e.g. an instruction cache miss), the execution logic of the processor may need to wait for the instructions to be accessed from main memory, which may take a significant amount of time. This may tend to significantly reduce the overall throughput of the processor. This tends to be especially significant for instruction working sets that do not fit in the processor cache(s). Accordingly, the prefetching of the instructions may help to improve performance by reducing the amount of time the execution logic of the processor needs to wait for instructions for it to execute.
Instructions are not always processed sequentially one after the other. Certain types of instructions, such as branch instructions, jump instructions, function calls, traps, and other types of control flow transfer instructions, may cause processing to branch, jump, or otherwise move around in the instruction sequence or control flow. For example, the processor may process a group of instructions sequentially until a control flow transfer instruction (e.g., a branch instruction) is encountered, and then the control flow transfer instruction may cause the processor to jump or branch to a target instruction at another non-sequential or discontinuous location in the instruction sequence (e.g., the target instruction may be separated from the control flow transfer instruction by one or more or potentially many intervening instructions).
In some cases, the number of intervening instructions between the target instruction and the control flow transfer instruction may be relatively small (e.g., in the case of a so-called short control flow transfer instruction), in which case the target instruction may potentially be within the same cache line as the control flow transfer instruction or in a subsequent cache line. However, in other cases, the number of intervening instructions between the target instruction and the control flow transfer instruction may alternatively be sufficiently larger (e.g., in the case of a so-called long control flow transfer instruction), in which case the target instruction may be in a non-sequential cache line relative to the cache line of the control flow transfer instruction (e.g., separated by one or more or potentially many intervening cache lines). As used herein the cache line that has a target instruction of an instruction of a given cache line may be referred to as a target cache line.
As a result, instruction prefetching may involve not only sequential prefetching of cache lines (e.g., prefetch line L and then prefetch subsequent line L+1) but also non-sequential prefetching of cache lines (e.g., prefetch line L and the prefetch line L+N, where N≠1).