Reference made herein and listed at the end are incorporated herein as necessary for understanding and implementing of the present invention.
Saturating arithmetic is widely used in digital signal processing (DSP) applications. Full-word saturating arithmetic operations work by setting their result to a pre-defined maximum or minimum in those situations where the corresponding basic 2's complement operations overflow or underflow.
Modern digital signal processors provide fast implementations of saturating operations. At the same time, many DSP applications are written in a standard programming language (such as ANSI C) with saturating operations coded as subroutines or macros in terms of basic 2's complement operations. In order to provide fast execution of such programs it is important to have an optimizing compiler automatically recognize and convert code fragments to individual saturating operations whenever possible.
The prior art in compiling for digital signal processors with saturating operations can be divided into two categories: a) special data types or intrinsic functions are used to signal to the compiler which +/− operations should be treated as saturating; and b) pattern matching of program fragments is used to discover saturating operations. The task of automatically recognizing saturating operations is complicated by the fact that there are many ways of programming such operations. An optimizing compiler relying on simple pattern recognition would have to test for a large number of patterns.
The present invention solves the problem of recognizing saturating addition and subtraction by capturing the essence of these operations in a set of data-flow program analysis equations that can be solved using well-known techniques in the area of optimizing compilers (see Ref 1, 5, 6, 7).
The method of formulating and solving equations that facilitate recognition of full word saturating addition and subtraction, includes formulating, for each basis addition statement z=x+y or subtraction statement z=x−y, data flow equations that describe properties of the program statements being analyzed; and solving the data flow equations.
The following properties of the program can be used:                (a) the values BITS of program variables as Boolean functions of the sign bits of x, y and z;        (b) the condition COND under which program statements are executed as Boolean functions of the sign bits of x, y and z; and        (c) the condition REACH of which values of variables reach any given use of z when overflow/underflow/neither occurs.        
The method includes replacing z in a statement S of the program that uses z with the use of zsat if and only if all of the following conditions hold for that statement S: a) the only values of z that reach S assigns SATMAX to z when overflow has occurred, c) the only values of z that reach S assigns SATMIN to z if underflow has occurred, and d) the only values of z that reaches S is from the basis statement A if no underflow and no overflow has occurred. Finally the statements made unnecessary by the replacement of uses of z with zsat are removed.
The equations for BITS, COND and REACH may use dense techniques or sparse program representation. The method values and conditions are approximated using global data flow analysis, which includes a lattice for approximating the properties (the values and conditions BITS, COND, REACH) and a system of equations relating approximations to various program points. Lattice vectors assigned to the variables can be compressed.
The REACH properties include a constant value COF(E,v) taken by the variable v when the edge E is executed, if overflow had occurred; a constant value CUF(E,v) taken by the variable v when the edge E is executed, if underflow had occurred; and a Boolean flag ISZ(E,v) which indicates whether v carries the same value as the variable z in the basis statement A when the edge E is executed and neither overflow nor underflow had occurred.
These and other aspects of the present invention will become apparent from the following detailed description of the invention, when considered in conjunction with accompanying drawings.
USPTO Backgrounds
USPTO Backgrounds