Method for identifying hard-to-predict branches to enhance processor performance

Claim 1

A method of handling branches comprising the steps of: (a) inputting a source program having one or more branch instructions to a compiler; (b) compiling the source program to produce a machine-executable code therefrom, with a set of heuristics being applied to classify each of the one or more branch instructions inputting as a hard-to-predict type or a simple type of branch, the set of heuristics including identification of a conditional expression that specifies an array element access or a pointer reference; (c) running the machine-executable code on a processor that includes first and second branch predictor circuits.

Claim 2

A method of handling branches comprising the steps of: (a) inputting a source program having one or more branch instructions to a compiler; (b) compiling the source program to produce a machine-executable code therefrom, with a set of heuristics being applied to classify each of the one or more branch instructions inputting as a hard-to-predict type or a simple type of branch, the set of heuristics including identification of a conditional expression that specifies an array element access or a pointer reference; (c) running the machine-executable code on a processor that includes first and second branch predictor circuits.

Claim 8

A method of handling branch instructions comprising the steps of: (a) compiling a source program that includes first and second branch instructions to produce an intermediate code; (b) applying a set of heuristics to the intermediate code that classifies the first branch instruction as a hard-to-predict type, and the second branch instruction as a simple type; (c) generating machine-executable code from the intermediate code, the machine-executable code including information which identifies the first branch instruction as the hard-to-predict type, the machine-executable code converting the first branch instruction into predicated execution code; (d) running the machine-executable code on a processor that includes first and second branch predictors which respectively operate on the hard-to-predict and simple type branch instructions.

Claim 9

A method of handling branch instructions comprising the steps of: (a) compiling a source program that includes first and second branch instructions to produce an intermediate code; (b) applying a set of heuristics to the intermediate code that classifies the first branch instruction as a hard-to-predict type, and the second branch instruction as a simple type; (c) generating machine-executable code from the intermediate code, the machine-executable code including information which identifies the first branch instruction as the hard-to-predict type, the machine-executable code converting the first branch instruction into predicated execution code; (d) running the machine-executable code on a processor that includes first and second branch predictors which respectively operate on the hard-to-predict and simple type branch instructions.

Claim 12

A system for handling branch instructions of a computer program comprising: a compiler that generates a machine-executable code from a source code listing of the computer program, the compiler including an algorithm that classifies a branch instruction as a hard-to-predict type of branch instruction according to one or more heuristics, the hard-to-predict type of branch instruction having an associated hint bit that is set by the compiler, the one or more heuristics including identification of a conditional expression that specifies an array element access or a pointer reference; a processor that executes the machine-executable code generated by the compiler, the processor including first and second branch predictor circuits that predict target addresses of the branch instructions, wherein the hint bit determines which of the first or second branch predictor circuits is utilized for a particular branch instruction of the machine-executable code.

Claim 13

A system for handling branch instructions of a computer program comprising: a compiler that generates a machine-executable code from a source code listing of the computer program, the compiler including an algorithm that classifies a branch instruction as a hard-to-predict type of branch instruction according to one or more heuristics, the hard-to-predict type of branch instruction having an associated hint bit that is set by the compiler, the one or more heuristics including identification of a conditional expression that specifies an array element access or a pointer reference; a processor that executes the machine-executable code generated by the compiler, the processor including first and second branch predictor circuits that predict target addresses of the branch instructions, wherein the hint bit determines which of the first or second branch predictor circuits is utilized for a particular branch instruction of the machine-executable code.

Claim 16

A system for handling branch instructions of a computer program comprising: a compiler having a front-end that processes the source code listing and produces a high-level intermediate code that contains semantic information therefrom, an algorithm that operates on the high-level intermediate code to classify a branch instruction as a hard-to-predict type of branch instruction according to one or more heuristics, the one or more heuristics including identification of a conditional expression that specifies an array element access or a pointer reference, an optimizer that converts the high-level intermediate code operated upon by the algorithm into a low-level intermediate code, a portion of the hard-to-predict type of branch instructions being converted into predicate execution code, a code generator that generates a machine-executable code from the optimized low-level intermediate code, a remaining portion of the hard-to-predict branch instructions being marked with a hint bit; a processor that executes the machine-executable code generated by the compiler, the processor including first and second branch predictors that predict a target address of the branch instructions wherein the hint bit determines which of the first or second branch predictors is utilized for a particular branch instruction of the machine-executable code.

Claim 17

A system for handling branch instructions of a computer program comprising: a compiler having a front-end that processes the source code listing and produces a high-level intermediate code that contains semantic information therefrom, an algorithm that operates on the high-level intermediate code to classify a branch instruction as a hard-to-predict type of branch instruction according to one or more heuristics, the one or more heuristics including identification of a conditional expression that specifies an array element access or a pointer reference, an optimizer that converts the high-level intermediate code operated upon by the algorithm into a low-level intermediate code, a portion of the hard-to-predict type of branch instructions being converted into predicate execution code, a code generator that generates a machine-executable code from the optimized low-level intermediate code, a remaining portion of the hard-to-predict branch instructions being marked with a hint bit; a processor that executes the machine-executable code generated by the compiler, the processor including first and second branch predictors that predict a target address of the branch instructions wherein the hint bit determines which of the first or second branch predictors is utilized for a particular branch instruction of the machine-executable code.