Hewlett-packard Company

Hewlett-packard Development Company, L.P.

Vatsa Santhanam

David H Gross

John Kwan

Dz-Ching Ju

Daryl K Odnert

Carol Linda Thompson

David Mitford Gillies

Paul S Chan

Vasanth Bala

Manoj Dadoo

Karl W Pettis

Vugranam C Sreedhar

A software mechanism for enabling a programmer to embed selected machine instructions into program source code in a convenient fashion, and optionally restricting the re-ordering of such instructions by the compiler without making any significant modifications to the compiler processing. Using a table-driven approach, the mechanism parses the embedded machine instruction constructs and verifies syntax and semantic correctness. The mechanism then translates the constructs into low-level compiler internal representations that may be integrated into other compiler code with minimal compiler changes. When also supported by a robust underlying inter-module optimization framework, library routines containing embedded machine instructions according to the present invention can be inlined into applications. When those applications invoke such library routines, the present invention enables the routines to be optimized more effectively, thereby improving run-time application performance. A mechanism is also disclosed using a '_fpreg' data type to enable floating-point arithmetic to be programmed from a source level where the programmer gains access to the full width of the floating-point register representation of the underlying processor.

Programmatic access to the widest mode floating-point arithmetic supported by a processor

A &#x3a6; function provides a mechanism for static single assignment in the presence of predicated code. Guards placed on each source operand of the &#x3a6; function indicate the condition under which the corresponding source operand is live and provide correct materialization of the &#x3a6; functions after code reordering. For control functions &#x3a6;representing a confluence of live reaching definitions at a join point in the control flow graph, the guards indicate the basic block which is the source of the edge associated with the source operand. The &#x3a6;operands are paired with the source basic block of the incoming edge(s) along which they are live. The operands are also ordered according to a topological ordering of their associated block. This ordering is maintained through subsequent code transformations. In the topological ordering, the source of the edge from which the definition was passed is defined. A predicate &#x3a6; function &#x3a6;, represents the confluence of definitions in a straight line of code in which some of the definitions have been predicated. For &#x3a6;, the guards on the source operands indicate the predicate under which the corresponding operand is live. The order of the operands is such that the &#x3a6;function can be fully materialized by inserting a copy from each source operand to the target variable, in the corresponding order, and each predicated by the associated predicate guard.

Method and apparatus for ordered predicate phi in static single assignment form

A software mechanism for enabling a programmer to embed selected machine instructions into program source code in a convenient fashion, and optionally restricting the re-ordering of such instructions by the compiler without making any significant modifications to the compiler processing. Using a table-driven approach, the mechanism parses the embedded machine instruction constructs and verifies syntax and semantic correctness. The mechanism then translates the constructs into low-level compiler internal representations that may be integrated into other compiler code with minimal compiler changes. When also supported by a robust underlying inter-module optimization framework, library routines containing embedded machine instructions according to the present invention can be inlined into applications. When those applications invoke such library routines, the present invention enables the routines to be optimized more effectively, thereby improving run-time application performance. A mechanism is also disclosed using a &ldquo;_fpreg&rdquo; data type to enable floating-point arithmetic to be programmed from a source level where the programmer gains access to the full width of the floating-point register representation of the underlying processor.

A regime of keywords modifying a volatile type-qualifier for use in source code accessing volatile objects via, for example, pointers to volatile memory locations. Each keyword permits corresponding selected optimizations by a compiler even though the volatile type-qualifier is also declared. Users select and combine keywords so as to relax corresponding optimization constraints otherwise ordained by use of the volatile type-qualifier.

User controlled relaxation of optimization constraints related to volatile memory references

A compiler optimization algorithm that deals with aggressive strength reduction of integer machine instructions found in loops. The algorithm permits the strength reduction of such machine instructions whose execution may be guarded by predicate values. In addition, the algorithm allows the strength reduction of address calculations consumed by memory reference instructions accessing data in a segmented virtual address space. The algorithm also permits aggressive SSA-based strength reduction of non-address integer computations found in loops that are linear functions of loop induction variables. The algorithm incorporates profitability considerations by reducing the cost of updating strength-reduction temporaries and ensures that the strength-reduction transformation results in an overall reduction of the path-lengths within loop bodies, without creating excessive register pressure.

Cost-sensitive SSA-based strength reduction algorithm for a machine with predication support and segmented addresses

Optimization of source code with embedded machine instructions

A method and system for detecting and eliminating interferences between resources in SSA-form &phgr;-instructions so that an optimizing compiler can translate optimized SSA-form code back to non-SSA-form code. The method traverses the control flow graph associated with an SSA-form program or routine in order to analyze each &phgr;-instruction within the SSA-form program or routine. All possible pairs of resources associated with each &phgr;-instruction are analyzed for interference. Once all interferences have been detected, the method inserts copy instructions into the SSA-form intermediate-level code program or routine in order to eliminate the interferences.

Method and system for eliminating phi instruction resource interferences and redundant copy instructions from static-single-assignment-form computer code

The present invention is a compiler optimization algorithm that reduces address computation overhead for architectures that support an auto-increment addressing mode for memory access instructions. The compiler algorithm identifies opportunities for auto-increment synthesis in a low level intermediate representation. Candidate loads and stores are transformed to use a base+displacement addressing mode (even if a base+displacement addressing mode is not supported in the target architecture) prior to instruction scheduling. After instruction scheduling, the pseudo (base+displacement) instructions are transformed back into memory operations that increment their base register operands to set up effective memory addresses.

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

A compiler that facilitates efficient insertion of explicit data prefetch instructions into loop structures within applications uses simple address expression analysis to determine data prefetching requirements. Analysis and explicit data cache prefetch instruction insertion are performed by the compiler in a machine-instruction level optimizer to provide access to more accurate expected loop iteration latency information. Such prefetch instruction insertion strategy tolerates worst-case alignment of user data structures relative to data cache lines. Execution profiles from previous runs of an application are exploited in the insertion of prefetch instructions into loops with internal control flow. Cache line reuse patterns across loop iterations are recognized to eliminate unnecessary prefetch instructions. The prefetch insertion algorithm is integrated with other low-level optimization phases, such as loop unrolling, register reassociation, and instruction scheduling. An alternative embodiment of the compiler limits the insertion of explicit prefetch instructions to those situations where the lower bound on the achievable loop iteration latency is unlikely to be increased as a result of the insertion.

Efficient explicit data prefetching analysis and code generation in a

Optimization techniques are implemented by means of a program analyzer used in connection with a program compiler to optimize usage of limited register resources in a computer processor. The first optimization technique, called interprocedural global variable promotion allows the global variables of a program to be accessed in common registers across a plurality of procedures. Moreover, a single common register can be used for different global variables in distinct regions of a program call graph. This is realized by identifying subgraphs, of the program call graph, called webs, where the variable is used. The second optimization technique, called spill code motion, involves the identification of regions of the call graph, called clusters, that facilitate the movement of spill instructions to procedures which are executed relatively less often. This decreases the overhead of register saves and restores which must be executed for procedure calls.

Method and apparatus for compiling computer programs with

A computer software compiler system and method for distributing a machine independent computer program, created on a native computer platform, to heterogeneous target computer platforms. The system comprises a producer which receives the machine independent computer program as input and which generates compiler intermediate representation. The system operates in a machine independent manner according to an HPcode-Plus compiler intermediate language. Thus, the compiler intermediate representation is machine independent and represents an architecture neutral distribution format (ANDF). The compiler intermediate representation, being architecture neutral, can be distributed to heterogeneous target computer platforms. At the heterogeneous target computer platforms, the compiler intermediate representation can be translated in a machine dependent manner into object code representations such that the object code representations are architecture dependent, or machine dependent, on the target computer platforms.

Growing community of inventors

Campbell, CA, United States of America

Vatsa Santhanam