Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Reexamination Certificate
2000-06-26
2003-06-24
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
C711S214000, C711S215000
Reexamination Certificate
active
06584557
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of programming in which an output pointer to a first data item is generated by combination of an input pointer to a second data item, and an offset.
BACKGROUND OF THE INVENTION
In some programming languages, it is necessary to cast a pointer to a first data item to a pointer to a second data item. The nature of the cast depends on the relationship between the data items and on the implementation and target processor. Pointer casting is employed in procedural languages such as C and object-oriented languages such as C++. As an example, in object oriented programming languages such as C++ there are many situations where it is necessary to calculate a pointer to an instance of one class from a pointer to an instance of another class. The arithmetic required depends on the relationship between the two classes, the relationship of the two instances, and upon specific implementation details of the compiler and target processor involved.
Example cases where pointer calculations arise include the following.
Cast of pointer to instance of Derived class to pointer to instance of Base class: class D (Derived) inherits from class B (Base) and a method of class D invokes a method inherited from class B then, as part of the implementation of the invocation, the compiler must generate object code to cast the pointer to the instance of class D to a pointer to the instance of class B. In the case of public inheritance this cast is implicitly generated by the compiler.
Cast of pointer to instance of Base class to pointer to instance of Derived class: If class D (Derived) inherits from class B (Base) and a virtual method of class B is invoked, and that virtual method is overridden (has an implementation defined) in class D then polymorphic behaviour results. The class D method will be invoked so, as part of the implementation of the invocation, the compiler must generate object code to calculate the instance pointer for class D. This is an implicit cast from a pointer to an instance of class B to a pointer to an instance of class D.
Invocation of a method on a data member: If class C contains member data for which it is desired to invoke an object method, then as part of the implementation of the invocation the compiler must generate object code to calculate a pointer to the data member from the instance pointer of the containing class C.
Access to a data member: If a class contains member data, and direct access to the member data is required (e.g. for a load or store operation), then the compiler must generate object code for the appropriate address arithmetic to access that data. This arithmetic may be performed in the ALU (Arithmetic Logic Unit) of the processor, or as part of the access itself by use of base+offset arithmetic in the load/store unit of the processor.
Typically pointer arithmetic involves adding or subtracting a fixed offset, which may be zero, and also dealing with the case where the input pointer p is NULL. In the case of zero offset, no arithmetic (and hence no code) is involved. In the non-zero offset case the compiler has to deal with two cases—the input pointer p could be NULL or non-NULL. In general NULL is taken to be represented by the value 0.
If the pointer is NULL, then the result of any such calculation should also be NULL.
If the pointer is non-NULL, then the calculation should proceed to add or subtract the offset as required.
The compiler generates appropriate instruction sequences to achieve this conditional arithmetic. In existing processor implementations this will typically comprise a test of the pointer for non-zero, followed by some conditional logic (e.g. conditional branch or conditional execution) and an add/subtract instruction to amend the pointer with the relevant offset.
In general, in the case where the offset is non-zero, the conditional pointer arithmetic tends to be clumsy and slow.
Because existing implementations of the conditional arithmetic for the case when the offset is non-zero are clumsy and slow, compilers typically use the following strategies to mitigate the problem.
Wherever possible, ensure that the offsets involved are zero. This avoids the non-zero offset case. This strategy trades data layout simplicity for safety and speed.
Ignore the NULL pointer issue, and generate unconditional offset arithmetic. This is fast but unsafe since it does not deal with the NULL pointer case. This strategy trades safety for speed and code compactness.
Generate fully conditional code that deals with the NULL pointer case. This is safe code, but is slower and larger than case
2
. This strategy trades speed and code compactness for safety.
Strategy
1
can make the data layout more complex. For example if class D inherits from class B then the instance data inherited from class B would be placed at offset
0
within the instance data for class D. Furthermore, if class D has a virtual function table pointer whereas class B does not, then under this strategy the virtual function table pointer cannot be placed at offset
0
within the instance data of class D since this position is already occupied by the instance data inherited from class B.
Additionally strategy
1
cannot be universally applied. In the case of multiple inheritance data from each of the base classes cannot all appear at offset zero in the instance data of the derived class. Furthermore, in the case of aggregation where a class has more than one item of member data, strategy
1
cannot be universally applied because not all the member data can have zero offset.
It would be desirable to provide a technique and apparatus which ameliorates at least some of the disadvantages of the prior art.
SUMMARY OF THE INVENTION
According to one aspect of the invention, therefore, there is provided a processor for calculating an output pointer to a first data item by combination of an input pointer to a second data item with an offset, the processor including logic for generating, in a single operation, a zero value for the output pointer when the input pointer is zero and an output pointer value calculated as the offset value added to, or subtracted from, the input pointer value when the input pointer is non-zero.
Thus in accordance with the invention, a single instruction primitive is defined that allows the processor to carry out, in a single operation, the conditional arithmetic described above thereby avoiding the need, in the prior art, for a plurality of processor instructions to carry out the same operation.
In accordance with another aspect of the invention there is provided a compiler that supports the new instruction, the compiler being implemented as a compiler program product comprising a computer readable medium on which is recorded compiler code for generating an output pointer to a first data member by combination of an input pointer to a second data member and an offset, the compiler code including means for generating a single instruction which when executed on a processor of a data processing system causes .the generation of a zero output when the input pointer is zero and causes the generation of an output pointer value equal to the offset value added to, or subtracted from, the input pointer value when the input pointer is non-zero.
It will be appreciated that the present invention also encompasses object code, which may or may not have been compiled from source code, that includes the new instruction. According to another aspect of the invention therefore there is provided a computer program product comprising a computer readable medium having recorded thereon object program code which when executed on a processor of the computer causes the processor to generate the value for an output pointer to a first data member by combining a value for an input pointer to a second data member and an offset, the object code means including a processor instruction to cause the processor to generate, in a single operation, a zero value for the output pointer when the input pointer is zero and
August Casey P.
Buchenhorner Michael J.
Elmore Reba I.
International Business Machines - Corporation
LandOfFree
Processor and method for generating a pointer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processor and method for generating a pointer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processor and method for generating a pointer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3158375