Browse Prior Art Database

Method for predicate analysis Disclosure Number: IPCOM000007516D
Publication Date: 2002-Apr-02

Publishing Venue

The Prior Art Database


Disclosed is a method for predicate analysis. Benefits include improved functionality and improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 15% of the total text.

Method for predicate analysis

Disclosed is a method for predicate analysis. Benefits include improved functionality and improved performance.


              Predicated execution is one of the innovative features of 64-bit architecture. It offers instruction-level parallelism. Conventional program analysis methods, though still applicable, can only generate conservative results instead of accurate ones because they assume that all operations may or may not be executed independently. This assumption negatively impacts the performance of some crucial areas, such as scheduling and register allocation. To generate high-quality code for the architectures offering predicated execution, a compiler must take into account the relations among predicates in its analysis and transformation phases. Predicate analysis is an analysis phase that analyzes the relations among predicates.

              Predicate-aware data flow analysis yields significantly more accurate results than conventional data flow analysis when applied to predicated code. Most optimizations, including register allocation and instruction scheduling, are based onthe analysis results by solving one or more data flow problems. Generated code can be more efficient when applying predicated-aware analyses (see Figure 1).

              The cmp instruction sets p to true and q to false if the condition (x<y) is true and reverses these values if the condition is false. When allocating registers, the live-ranges of the variables a and b are overlapped if the analysis is predicate ­insensitive. As a result, two different physical registers must be assigned to a and b. However, p and q are complementary. For example, p and q are never both true. The live-ranges of a and b are not overlapped. This example illustrates how predicate analysis can assist register allocation. Instruction scheduling and many other optimizations can also be more effective when taking into account the relations among predicates.

              A predicate may have multiple reaching definitions. Then, predicate analysis becomes more complicated. Control flow can cause multiple definitions. Furthermore, parallel compare instructions optimize compound conditions. Parallel compare instructions can reduce the critical path due to compound conditions, but may-definitions of predicates are introduced. An example illustrates the impact of parallel compare instructions (see Figure 2).

              The definition of pl at sl is to initialize to false. The definitions of pl at s2 and s3 are may-definitions. If the condition in an ‘or’ compare instruction is true, pl is set. If the condition is false, the value of pl remains unchanged.

              To address the problem of multiple reaching definitions, previous predicate analysis approaches are based on a static single assignment (SSA) form. For example, Figure 3(b) shows the assembly pseudo-code of the contents of Figure 3(a), and Figure 3(c) shows the SSA form of the contents of Figure 3(b). Based on SSA form, different symbols are created to represent...