Determination of target location for transfer of processor control

Patent metadata

Field	Value
Publication number	US-2016378491-A1
Application number	US-201514752660-A
Country	US
Kind code	A1
Filing date	Jun 26, 2015
Priority date	Jun 26, 2015
Publication date	Dec 29, 2016
Grant date	—

Abstract

Methods and apparatus are disclosed for eliminating explicit control flow instructions (for example, branch instructions) from atomic instruction blocks according to a block-based instructions set architecture (ISA). In one example of the disclosed technology, an explicit data graph execution (EDGE) ISA processor is configured to fetch instruction blocks from a memory and execute at least one of the instruction blocks, each of the instruction blocks being encoded to have one or more exit points determining a target location of a next instruction block. Processor control circuitry evaluates one or more predicates for instructions encoded within a first one of the instruction blocks, and based on the evaluating, transfers control of the processor to a second instruction block at a target location that is not specified by a control flow instruction in the first instruction block.

First claim

We claim:

1 . An apparatus comprising a block-based instruction set architecture (ISA) processor, the apparatus comprising:
memory; one or more processer cores configured to fetch a plurality of instruction blocks from the memory and execute a current instruction block of the plurality of instruction blocks, the current instruction block having a number of one or more exit points; and control logic circuitry configured to transfer control of the processor from the current instruction block to a next instruction block at a target location determined by one of the current instruction block's exit points.

2 . The apparatus of claim 1 , wherein the current instruction block includes at least one fewer control flow instructions than the number of exit points for the current instruction block.

3 . The apparatus of claim 1 , wherein the control logic circuitry is configured to transfer control of the processor to the next instruction block at the target location, wherein the target location is not encoded by a control flow instruction in the current instruction block.

4 . The apparatus of claim 3 , wherein the control logic circuitry is configured to determine that the target location is at an address immediately following the current instruction block.

5 . The apparatus of claim 1 , wherein the control logic circuitry is configured to determine the target location of the next instruction block based at least in part on exit type information encoded in an instruction header for the current instruction block.

6 . The apparatus of claim 5 , further comprising a core scheduler configured to map the instruction blocks for execution on respective ones of the processor cores, the core scheduler being configured to speculatively execute at least one control flow instruction based at least in part on the exit type information.

7 . The apparatus of claim 1 , wherein:
the current instruction block includes at least one fewer control flow instructions than the number of exit points for the current instruction block, the at least one fewer control flow instructions include at least one or more of the following: branch, jump, procedure call, or procedure return; each of the at least one fewer control flow instructions are either conditionally or unconditionally based on a predicate for at least one of the control flow instructions; and each of the at least one fewer control flow instructions indicates a target location as either a relative or absolute address.

8 . The apparatus of claim 1 , wherein the control logic circuitry is configured to transfer control of the processor by performing at least one or more of the following acts:
storing a value indicating a memory location of the next instruction block in a program counter register; signaling at least one of the processor cores to fetch an instruction block from a target location stored in a program counter register; or writing a target location address to a memory location and signaling at least one of the processor cores to fetch an instruction block from a target location designated by the memory location.

9 . The apparatus of claim 1 , wherein:
the instructions in the instruction blocks are to be executed by respective ones of the processor cores in an order according to availability of dependencies for each of the respective instructions.

10 . An apparatus comprising a block-based processor, the processor comprising:
one or more processer cores configured to fetch instruction blocks from a memory and execute at least one of the instruction blocks, each of the instruction blocks being encoded to have one or more exit points to determine a target location of a next instruction block; and control logic circuitry configured to transfer control of the processor to the determined target location in response to performance of operations, the operations comprising:
an operation to evaluate one or more predicates for instructions encoded within a first one of the instruction blocks, and
based on the operation to evaluate, an operation to transfer control of the processor to a second instruction block at the target location, wherein the target location is not specified by a control flow instruction in the first instruction block.

11 . The apparatus of claim 10 , wherein the evaluating is based at least in part on an exit type code encoded in an instruction header of the first one of the instruction blocks.

12 . The apparatus of claim 10 , wherein the target location for the second instruction block is located at a memory location immediately before or after the first instruction block in memory.

13 . The apparatus of claim 10 , wherein the target location for the second instruction block is determined as if the first instruction block executed a call, return, or branch instruction.

14 . The apparatus of claim 10 , further comprising a core scheduler for mapping the instruction blocks for execution on respective ones of the processor cores, the core scheduler being configured to avoid branch prediction based at least in part on exit type information encoded in a header of at least one of the instruction blocks.

15 . One or more computer-readable storage media storing computer-readable instructions that when executed by a computer cause the computer to perform a method, the computer-readable instructions comprising:
instructions to emit one or more instruction blocks for execution by a block-based processor, at least one of the instruction blocks including one or more exit points encoded within the instruction block, the at least one of the instruction blocks including one fewer branch instructions than the number of exit points.

16 . The computer-readable storage media of claim 15 , wherein the instructions further comprise instructions to store the emitted instruction blocks in one or more computer-readable storage media or devices.

17 . The computer-readable storage media of claim 15 , wherein the instructions further comprise instructions to encode an instruction header in the at least one of the instruction blocks, the instruction header including one or more branch exit types that indicate at least one target location that is not designated by any of the control flow instructions encoded in the instruction block.

18 . The computer-readable storage media of claim 15 , wherein the instructions further comprise instructions to encode an instruction header in the at least one of the instruction blocks, the instruction header including one or more branch exit types that indicate that a next instruction block contiguous to the at least one instruction blocks is to be a target location for a control flow instruction, the target location not being designated by any of the control flow instructions encoded in the instruction block.

19 . The computer-readable storage media of claim 15 , wherein the instructions further comprise instructions to encode an instruction header in the at least one of the instruction blocks, the instruction header including one or more branch exit types that indicate that a next instruction block contiguous to the at least one instruction blocks is to be a target location for a control flow instruction, the branch exit types being encoded within bits 31 through 14 of the instruction header, and at least one of the branch exit type being encoded by the three-bit pattern 010.

20 . The computer-readable storage media of claim 15 , wherein the instructions further comprise instructions to analyze a predicate graph for t

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Burger Douglas C
• Smith Aaron L
• Gray Jan S

Classifications

• G06F9/3802 Primary

  Instruction prefetching · CPC title

• G06F9/3005 Primary

  to perform operations for flow control · CPC title

• G06F9/30054

  Unconditional branch instructions · CPC title

• G06F9/3858

  Result writeback, i.e. updating the architectural state or memory · CPC title

• G06F9/3854

  Instruction completion, e.g. retiring, committing or graduating · CPC title