Efficient stack utilization for compiling and executing nested if-else constructs in a vector data processing system

• US 5,790,854 A
• Filed: 08/03/1995
• Issued: 08/04/1998
• Est. Priority Date: 03/31/1993
• Status: Expired due to Fees

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Seaton, Robert W. Jr., Spielman, Jason, Goke, L. Rodney, Huang, Yee-Wei, Gallup, deceased, Michael G.
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): Nguyen, Cuong H.
• Application Number:
  US08/510,948
• Time in Patent Office: 1,097 Days
• Field of Search: 395/562-563, 395/800.02, 395/800.03, 395/800.07, 395/800.04, 395/800.09, 395/800.06, 395/800.05, 395/800.22, 395/581, 395/379 , 395/383-384, 395/701, 395/708, 395/709, 364/736.01, 364/736.03, 711/147
• US Class Current: 717/150
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/78 comprising a single central processing unit
• CPC Class Codes: G06F 15/8023 Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: G06F 15/8092 Array of vector units
• CPC Class Codes: G06F 7/49921 Saturation, i.e. clipping the result to a minimum or maximum value
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence
• CPC Class Codes: G06F 7/57 Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations G06F7/49, G06F7/491 take precedence
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 8/447 Target code generation
• CPC Class Codes: G06F 9/30 Arrangements for executing machine instructions, e.g. instruction decode for executing microinstructions G06F9/22
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30065 Loop control instructions; iterative instructions, e.g. LOOP, REPEAT
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30079 Pipeline control instructions, e.g. multicycle NOP
• CPC Class Codes: G06F 9/30083 Power or thermal control instructions
• CPC Class Codes: G06F 9/30094 Condition code generation, e.g. Carry, Zero flag
• CPC Class Codes: G06F 9/30101 Special purpose registers
• CPC Class Codes: G06F 9/30116 Shadow registers, e.g. coupled registers, not forming part of the register space
• CPC Class Codes: G06F 9/3802 : Instruction prefetching
• CPC Class Codes: G06F 9/3812 : with instruction modification, e.g. store into instruction stream
• CPC Class Codes: G06F 9/3851 : from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3867 : using instruction pipelines
• CPC Class Codes: G06F 9/3877 : using a slave processor, e.g. coprocessor peripheral processor G06F13/12; vector processor G06F15/8053
• CPC Class Codes: G06F 9/3887 : controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/3889 : controlled by multiple instructions, e.g. MIMD, decoupled access or execute
• CPC Class Codes: G06N 3/063 : using electronic means

Abstract

A computer-implemented method is provided for compiling software code that performs nested conditional constructs in vector data processors (10). A vector bit stack (128) to record which processing elements (16) were activated and which processing elements were deactivated during execution of a nested conditional construct. Subsequently, when an end of a first nested conditional construct is encountered, a state of the processing elements at a point in time in which the first nested conditional construct was initiated may be popped off of the vector bit stack and a second conditional construct or any other operation may be executed. Therefore, conditional constructs may be executed while ensuring the proper state of the processing elements. The compiler program effectively utilizes the vector bit stack to store prior states of each of the processing elements of the vector data processor such that the processing elements may be efficiently restored to a correct intermediate value.

Claims

1. A method for compiling a nested conditional construct for a vector data processor, comprising the computer-implemented steps of:

providing a first program for the vector data processor in a first software language, the program including the nested conditional construct;

initiating translation of the first program for the vector data processor from the first software language to a second program in a second software language by a data processor;

recognizing the nested conditional construct in the first program;

translating a first portion of the first program for the vector data processor from the first software language to a first portion of the second program in the second software language, the first portion of the second program determining when a condition in the nested conditional construct is true and when the condition in the nested conditional construct is false;

providing a second portion of the second program wherein a first vector instruction set stores a first state of each of a plurality of processing elements of the vector data processor in a first vector register when the condition in the nested conditional construct is true;

providing a third portion of the second program wherein a second vector instruction set deactivates each of the plurality of processing elements for which the nested conditional construct is false;

providing a fourth portion of the software program wherein a third vector instruction set which logically combines a second state of each of the plurality of processing elements with the first state of each of the plurality of processing elements of the vector data processor; and

providing a fifth portion of the software program wherein a fourth vector instruction set retrieves a first register value from the first vector register to provide a third state for each of the plurality of processing elements of the vector data processor.

2. The method for compiling of claim 1 wherein the first vector register is used as a stack for a state of each of the plurality of processing elements.

3. The method of compiling of claim 1 wherein the second software language is a microcode language for the vector data processor.

4. The method of compiling of claim 1 wherein the first vector instruction set, comprises:

a vector shift instruction for shifting the first state of each of the plurality of processing elements of the vector data processor in the first vector register.

5. The method of compiling of claim 1 wherein the second vector instruction set, comprises:

a vector conditional instruction for activating a first portion of the plurality of processing elements when the condition in the nested conditional construct is true.

6. The method of claim 1 wherein the third vector instruction set, comprises:

a first vector shift instruction for shifting the first state of each of the plurality of processing elements of the vector data processor in a second vector register;

a vector conditional instruction which activates each of the plurality of processing elements when the second state of each of the plurality of processing elements is logically combined with the first state of each of the plurality of processing elements of the vector data processor;

a vector exclusive OR instruction which logically combines the second state of each of the plurality of processing elements with the first state of each of the plurality of processing elements of the vector data processor and stores a result in the second vector register; and

a second vector shift instruction which accesses the result in the second vector register to determine a new state of the plurality of processing elements of the vector data processor.

7. The method of claim 1 wherein the fourth vector instruction set, comprises:

a vector rotate instruction for rotating the first state of each of the plurality of processing elements of the vector data processor from the first vector register to provide a current state of the plurality of processing elements of the vector data processor.

8. A method for compiling a nested conditional construct for a vector data processor, comprising the computer-implemented steps of:

providing a first program for the vector data processor in a first software language, the program including the nested conditional construct;

initiating translation of the first program for the vector data processor from the first software language to a second program in a second software language by a data processor;

recognizing the nested conditional construct in the first program;

enabling the data processor to determine if the nested conditional construct may be optimized for the vector data processor;

translating the first program for the vector data processor from the first software language to the second program in the second software language in a first set of steps when the nested conditional construct may not be optimized, the first set of steps comprising the steps of;

translating a first portion of the first program for the vector data processor from the first software language to a first portion of the second program in the second software language, the first portion of the second program determining when a condition in the nested conditional construct is true and when the condition in the nested conditional construct is false;

providing a second portion of the second program wherein a first vector instruction set stores a first state of each of a plurality of processing elements of the vector data processor in a first vector register when the condition in the nested conditional construct is true;

providing a third portion of the second program wherein a second vector instruction set deactivates each of the plurality of processing elements for which the nested conditional construct is false;

providing a fourth portion of the software program wherein a third vector instruction set which logically combines a second state of each of the plurality of processing elements with the first state of each of the plurality of processing elements of the vector data processor; and

providing a fifth portion of the software program wherein a fourth vector instruction set retrieves a first register value from the first vector register to provide a third state for each of the plurality of processing elements of the vector data processor;

translating the first program for the vector data processor from the first software language to the second program in the second software language in a second set of steps when the nested conditional construct may be optimized, the second set of steps comprising the steps of;

determining when each of the plurality of processing elements is active in the first state;

translating a sixth portion of the software program wherein a fifth vector instruction set programs the vector data processor to execute a first optimized function when each of the plurality of processing elements is active in the first state;

determining when a nested conditional construct is a predetermined nested conditional construct form which may be optimized when each of the plurality of processing elements is not active in the first state; and

translating a seventh portion of the software program wherein a sixth vector instruction set programs the vector data processor to execute a second optimized function when the nested conditional construct is the predetermined nested conditional construct form.

9. The method of claim 8 wherein the first optimized function comprises the steps of:

receiving a first instruction;

decoding the first instruction to provide a first plurality of control signals;

accessing an enable value from an enabled one of the plurality of processing elements in response to a first portion of the plurality of control signals, the enable value selectively enabling the enabled one of the plurality of processing elements to participate in execution of the first instruction and indicating the first state of each of the plurality of processing elements;

accessing a history value from the enabled one of the plurality of processing elements in response to a second portion of the plurality of control signals;

selectively modifying the enable value in response to a logic state of the history value;

accessing a plurality of enable values from each of an enabled portion of the plurality of processing elements in response to the first portion of the plurality of control signals, each of the plurality of enable values selectively enabling a corresponding one of the plurality of processing elements to participate in execution of the first instruction;

accessing a plurality of history values from each of the enabled portion of the plurality of processing elements in response to the second portion of the plurality of control signals, each of the plurality of history values corresponding to one of the enabled portions of the plurality of processing elements; and

selectively modifying each of the plurality of enable values in response to a logic state of a corresponding one of the plurality of history values.

10. The method of claim 8 wherein the predetermined nested conditional construct form which may be optimized is a right-hand conditional chain.

11. The method of claim 10 further comprising the steps of:

setting a plurality of history bits which correspond to a plurality of processing elements which were previously active;

executing a first vector conditional operation, the first vector conditional operation comprising the steps of;

receiving a first instruction;

decoding the first instruction to provide a first plurality of control signals;

accessing an enable value corresponding to a processing element in response to a first portion of the first plurality of control signals;

selectively enabling the processing element to participate in execution of the first instruction when the enable value is in an asserted state;

executing a comparison operation in response to a second portion of the plurality of control signals, the processing element being used during execution of the comparison operation when the processing element is enabled to participate;

selectively negating the enable value corresponding to the processing element when the processing element is enabled to participate, the enables value being negated when the condition of the comparison operation has not been met;

accessing the plurality of enable values from each of the plurality of processing elements in response to a first portion of the second plurality of control signals;

selectively enabling a portion of the plurality of processing elements to participate in execution of the first instruction, each of the portion of the plurality of processing elements having an enable value in an asserted state;

executing a comparison operation in response to a second portion of the plurality of control signals, each of the portion of the plurality of processing elements being used during execution of the comparison operation; and

selectively negating each of a portion of the plurality of enable values corresponding to the portion of the plurality of processing elements when the condition of the comparison operation has not been met; and

executing a second vector conditional operation, the second vector conditional operation comprising the steps of;

receiving a second instruction;

decoding the second instruction to provide a second plurality of control signals;

accessing an enable value from an enabled one of the plurality of processing elements in response to a first portion of the plurality of control signals, the enable value selectively enabling the enabled one of the plurality of processing elements to participate in execution of the second instruction and indicating the first state of each of the plurality of processing elements;

accessing a history value from the enabled one of the plurality of processing elements in response to a second portion of the plurality of control signals;

selectively modifying the enable value in response to a logic state of the history value;

accessing a plurality of enable values from each of an enabled portion of the plurality of processing elements in response to the first portion of the plurality of control signals, each of the plurality of enable values selectively enabling a corresponding one of the plurality of processing elements to participate in execution of the second instruction;

accessing a plurality of history values from each of the enabled portion of the plurality of processing elements in response to the second portion of the plurality of control signals, each of the plurality of history values corresponding to one of the enabled portions of the plurality of processing elements;

selectively modifying each of the plurality of enable values in response to a logic state of a corresponding one of the plurality of history values;

negating the plurality of history bits of each of the plurality of processing elements; and

executing a vector rotate instruction for rotating the first state of each of the plurality of processing elements of the vector data processor from the first vector register to provide a current state of the plurality of processing elements of the vector data processor.

12. The method of claim 8 wherein the predetermined nested conditional construct form which may be optimized is a solitary-if chain which only includes an if conditional construct.

13. The method of compiling of claim 8 wherein the second software language is a microcode language for the vector data processor.

14. The method of compiling of claim 8 wherein the first vector instruction set, comprises:

a vector shift instruction for shifting the first state of each of the plurality of processing elements of the vector data processor in the first vector register.

15. The method of compiling of claim 8 wherein the second vector instruction set, comprises:

a vector conditional instruction for activating a first portion of the plurality of processing elements when the condition in the nested conditional construct is true.

16. The method of claim 8 wherein the third vector instruction set, comprises:

a first vector shift instruction for shifting the first state of each of the plurality of processing elements of the vector data processor in a second vector register;

a vector conditional instruction which activates each of the plurality of processing elements when the second state of each of the plurality of processing elements is logically combined with the first state of each of the plurality of processing elements of the vector data processor;

a vector exclusive OR instruction which logically combines the second state of each of the plurality of processing elements with the first state of each of the plurality of processing elements of the vector data processor and stores a result in the second vector register; and

a second vector shift instruction which accesses the result in the second vector register to determine a new state of the plurality of processing elements of the vector data processor.

17. The method of claim 16 wherein the fourth vector instruction set, comprises:

a vector rotate instruction for rotating the first state of each of the plurality of processing elements of the vector data processor from the first vector register to provide a current state of the plurality of processing elements of the vector data processor.

18. A method for compiling a nested conditional construct for a vector data processor, comprising the computer-implemented steps of:

providing a first program for the vector data processor in a first software language, the program including the nested conditional construct;

initiating translation of the first program for the vector data processor from the first software language to a second program in a second software language by a data processor;

recognizing the nested conditional construct in the first program;

enabling the data processor to determine if the nested conditional construct may be optimized for the vector data processor;

translating the first program in the first software language to the second program in the second software language using a general vector conditional construct program; and

optimizing a translation of the first program to the second program such that the first program in the first software language is translated to the second program in the second software language using an optimized vector conditional construct program.

19. The method of claim 18 wherein the general vector conditional construct program, comprises the steps of:

translating the first program for the vector data processor from the first software language to the second program in the second software language in a first set of steps when the nested conditional construct may not be optimized, the first set of steps comprising the steps of;

translating a first portion of the first program for the vector data processor from the first software language to a first portion of the second program in the second software language, the first portion of the second program determining when a condition in the nested conditional construct is true and when the condition in the nested conditional construct is false;

providing a second portion of the second program wherein a first vector instruction set stores a first state of each of a plurality of processing elements of the vector data processor in a first vector register when the condition in the nested conditional construct is true;

providing a third portion of the second program wherein a second vector instruction set deactivates each of the plurality of processing elements for which the nested conditional construct is false;

providing a fourth portion of the software program wherein a third vector instruction set which logically combines a second state of each of the plurality of processing elements with the first state of each of the plurality of processing elements of the vector data processor; and

providing a fifth portion of the software program wherein a fourth vector instruction set retrieves a first register value from the first vector register to provide a third state for each of the plurality of processing elements of the vector data processor.

20. The method of claim 19 wherein the optimized vector conditional construct program comprises the steps of:

determining when each of the plurality of processing elements is active in the first state; and

translating a sixth portion of the software program wherein a fifth vector instruction set programs the vector data processor to execute a first optimized function when each of the plurality of processing elements is active in the first state.

21. The method of claim 20 wherein the first optimized function comprises the steps of:

receiving a first instruction;

decoding the first instruction to provide a first plurality of control signals;

accessing an enable value from an enabled one of the plurality of processing elements in response to a first portion of the plurality of control signals, the enable value selectively enabling the enabled one of the plurality of processing elements to participate in execution of the first instruction and indicating the first state of each of the plurality of processing elements;

accessing a history value from the enabled one of the plurality of processing elements in response to a second portion of the plurality of control signals;

selectively modifying the enable value in response to a logic state of the history value;

accessing a plurality of enable values from each of an enabled portion of the plurality of processing elements in response to the first portion of the plurality of control signals, each of the plurality of enable values selectively enabling a corresponding one of the plurality of processing elements to participate in execution of the first instruction;

accessing a plurality of history values from each of the enabled portion of the plurality of processing elements in response to the second portion of the plurality of control signals, each of the plurality of history values corresponding to one of the enabled portions of the plurality of processing elements; and

selectively modifying each of the plurality of enable values in response to a logic state of a corresponding one of the plurality of history values.

22. The method of claim 19 wherein the optimized vector conditional construct program comprises the steps of:

determining when a nested conditional construct is a predetermined nested conditional construct form which may be optimized; and

translating a seventh portion of the software program wherein a sixth vector instruction set programs the vector data processor to execute a second optimized function when the nested conditional construct is the predetermined nested conditional construct form.

23. The method of claim 22 wherein the predetermined nested conditional construct form which may be optimized is a right-hand conditional chain.

24. The method of claim 23 further comprising the steps of:

setting a plurality of history bits which correspond to a plurality of processing elements which were previously active;

executing a first vector conditional operation, the first vector conditional operation comprising the steps of;

receiving a first instruction;

decoding the first instruction to provide a first plurality of control signals;

accessing an enable value corresponding to a processing element in response to a first portion of the first plurality of control signals;

selectively enabling the processing element to participate in execution of the first instruction when the enable value is in an asserted state;

executing a comparison operation in response to a second portion of the plurality of control signals, the processing element being used during execution of the comparison operation when the processing element is enabled to participate;

selectively negating the enable value corresponding to the processing element when the processing element is enabled to participate, the enables value being negated when the condition of the comparison operation has not been met;

accessing the plurality of enable values from each of the plurality of processing elements in response to a first portion of the second plurality of control signals;

selectively enabling a portion of the plurality of processing elements to participate in execution of the first instruction, each of the portion of the plurality of processing elements having an enable value in an asserted state;

executing a comparison operation in response to a second portion of the plurality of control signals, each of the portion of the plurality of processing elements being used during execution of the comparison operation; and

selectively negating each of a portion of the plurality of enable values corresponding to the portion of the plurality of processing elements when the condition of the comparison operation has not been met; and

executing a second vector conditional operation, the second vector conditional operation comprising the steps of;

receiving a second instruction;

decoding the second instruction to provide a second plurality of control signals;

accessing an enable value from an enabled one of the plurality of processing elements in response to a first portion of the plurality of control signals, the enable value selectively enabling the enabled one of the plurality of processing elements to participate in execution of the second instruction and indicating the first state of each of the plurality of processing elements;

accessing a history value from the enabled one of the plurality of processing elements in response to a second portion of the plurality of control signals;

selectively modifying the enable value in response to a logic state of the history value;

accessing a plurality of enable values from each of an enabled portion of the plurality of processing elements in response to the first portion of the plurality of control signals, each of the plurality of enable values selectively enabling a corresponding one of the plurality of processing elements to participate in execution of the second instruction;

accessing a plurality of history values from each of the enabled portion of the plurality of processing elements in response to the second portion of the plurality of control signals, each of the plurality of history values corresponding to one of the enabled portions of the plurality of processing elements;

selectively modifying each of the plurality of enable values in response to a logic state of a corresponding one of the plurality of history values;

negating the plurality of history bits of each of the plurality of processing elements; and

executing a vector rotate instruction for rotating the first state of each of the plurality of processing elements of the vector data processor from the first vector register to provide a current state of the plurality of processing elements of the vector data processor.

25. The method of claim 22 wherein the predetermined nested conditional construct form which may be optimized is a solitary-if chain which only includes an if conditional construct.