Efficient use of the base register auto-increment feature of memory access instructions

Claim 2

A compiler optimization algorithm including the steps of: (i) identifying candidate memory access instructions for auto-increment synthesis; (ii) transforming candidate memory access instructions into memory access instructions that employ an addressing mode not supported by the target architecture; (iii) scheduling the memory access instructions that are not supported by the target architecture; and (iv) transforming the memory access instructions that are not supported by the target architecture into an auto-increment memory access instructions.

Claim 3

A compiler optimization algorithm for optimizing a low-level representation of a program for a target architecture that supports an auto-increment addressing mode, including the steps of: identifying candidate memory access instructions for auto-increment synthesis; transforming candidate memory access instructions into pseudo base+displacement memory access instructions, wherein the step of transforming candidate memory access instruction into pseudo base+displacement memory access instructions occurs prior to the step of instruction scheduling; scheduling the pseudo base+displacement memory instructions; and converting the pseudo base+displacement memory access instructions into memory access instructions that auto-increment their base register operands, wherein the step of converting the base+displacement memory access instructions into memory access instructions that auto-increment their base operands is performed after instruction scheduling.

Claim 4

A compiler optimization algorithm for optimizing a low-level representation of a program for a target architecture that supports an auto-increment addressing mode, including the steps of: identifying candidate memory access instructions for auto-increment synthesis; transforming candidate memory access instructions into pseudo base+displacement memory access instructions, wherein the step of transforming candidate memory access instruction into pseudo base+displacement memory access instructions occurs prior to the step of instruction scheduling; scheduling the pseudo base+displacement memory instructions; and converting the pseudo base+displacement memory access instructions into memory access instructions that auto-increment their base register operands, wherein the step of converting the base+displacement memory access instructions into memory access instructions that auto-increment their base operands is performed after instruction scheduling.

Claim 5

The method recited in claim 2 wherein the candidates are memory access instructions that occur in loops which specify an address that is a linear function of a loop induction variable.

Claim 6

The method recited in claim 2 further including the step of generating a list schedule for a loop to determine a maximum initiation interval (MAX ii ), estimating the minimum initiation interval (MIN ii ) and attempting to find a software pipeline schedule.

Claim 7

The method recited in claim 4 wherein if the software pipeline schedule is not found for a MIN ii less than MAX ii , the minimum initiation interval is incremented.

Claim 8

The method recited in claim 4 wherein if the software pipeline schedule is not found and MIN ii is greater than MAX ii , the list schedule for the loop is generated and auto-increments for the list schedule are synthesized.

Claim 9

The method recited in claim 4 further including the step of determining whether auto-increments can be synthesized for the software pipeline schedule when the software pipeline schedule is found for a MIN ii less than MAX ii .

Claim 10

The method recited in claim 7 further including the step of determining whether the software pipeline kernel can be register allocated when auto-increments can be synthesized for the software pipeline schedule.

Claim 11

The method recited in claim 8 further including the step of generating a software pipeline schedule when it is determined that the software pipeline kernel can be register allocated.

Claim 12

The method recited in claim 2 where the base+displacement addressing mode is not supported by the target architecture.

Claim 13

The method recited in claim 10 wherein all of the candidate memory instructions are converted to base+displacement instructions before scheduling.

Claim 14

The method recited in claim 2 where the base+displacement addressing mode is supported by the target architecture.

Claim 15

The method recited in claim 12 wherein all of the candidate memory instructions are converted to base+displacement instructions before scheduling.

Claim 16

A compiler optimization algorithm for optimizing a low-level representation of a program for a target architecture that supports an auto-increment addressing mode, including the steps of: identifying candidate memory access instructions for auto-increment synthesis; transforming candidate memory access instructions into pseudo base+displacement memory access instructions; and converting the pseudo base+displacement memory access instructions into memory access instructions that auto-increment their base resister operands, wherein the pseudo base+displacement memory access instructions are converted into memory access instructions that post-increment their base register operands, further including the step of determining whether the same base register is used by multiple memory access instruction scheduled in the same cycle.

Claim 17

A compiler optimization algorithm for optimizing a low-level representation of a program for a target architecture that supports an auto-increment addressing mode, including the steps of: identifying candidate memory access instructions for auto-increment synthesis; transforming candidate memory access instructions into pseudo base+displacement memory access instructions; and converting the pseudo base+displacement memory access instructions into memory access instructions that auto-increment their base resister operands, wherein the pseudo base+displacement memory access instructions are converted into memory access instructions that post-increment their base register operands, further including the step of determining whether the same base register is used by multiple memory access instruction scheduled in the same cycle.

Claim 18

The method recited in claim 14 wherein if the same base register is not used by at least two memory access instructions scheduled in the same cycle, upstream memory access instructions are transformed to post-increment their base register operands on behalf of the memory access instructions in that cycle.

Claim 19

The method recited in claim 14 further including the step of determining whether upstream memory access instructions can post-increment their base registers on behalf of downstream memory access instructions when the same base register is not used by multiple memory access instructions scheduled in the same cycle.

Claim 20

The method recited in claim 16 further including the step of transforming an upstream memory access instruction into a memory access instruction that post-increments its base register operand on behalf of a downstream memory access instruction when it is determined that the upstream memory access instruction can be post-increment its base register operand on behalf of the downstream memory access instruction.

Claim 21

The method recited in claim 17 further including the step of converting the downstream memory access instruction to use the appropriate base register.

Claim 22

The method recited in claim 14 further including the step of determining whether base register cloning is more efficient than inserting spill code.

Claim 23

The method recited in claim 19 further including the step of inserting spill code on behalf of a memory access instruction when it is determined that inserting spill code is more efficient than cloning a base register.

Claim 24

The method recited in claim 20 further including the step of converting the memory access instruction to use the appropriate base register.

Claim 25

The method recited in claim 19 further including the step of cloning the base register when it is determined that cloning the base register is more efficient than inserting spill code.

Claim 26

The method recited in claim 22 further including the step of converting the memory access instruction to use the appropriate base register.