Eliminating maximum/minimum operations in loop bounds

Details Eliminating maximum/minimum operations in loop bounds Eliminating maximum/minimum operations in loop bounds

2007-08-21

2011-12-27

Dam, Tuan (Department: 2192)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C717S154000, C717S159000

Reexamination Certificate

active

08087012

ABSTRACT:
A technique is provided for eliminating maximum and minimum expressions within loop bounds are provided. A loop in a code is identified. The loop is determined to meet conditions, which require an upper loop bound and a lower loop bound to contain maximum and minimum expressions, loop-invariant operands, a predetermined size for a code size, and a total number of instructions to be greater than a predetermined constant. A profitability of loop versioning is determined based on a performance gain of a fast version of the loop, a probability of executing the fast version of the loop at runtime, and an overhead for performing loop versioning. A pair of lower loop bound and upper loop bound values resulting in a constant number is identified. A loop iteration value is checked to be a non-zero constant. Branches are identified, and loop versioning is performed to generate a versioned loop.

REFERENCES:
patent: 5781777 (1998-07-01), Sato et al.
patent: 5842021 (1998-11-01), Odani et al.
patent: 6341371 (2002-01-01), Tandri
patent: 6343375 (2002-01-01), Gupta et al.
patent: 6507947 (2003-01-01), Schreiber et al.
patent: 6665864 (2003-12-01), Kawahito et al.
patent: 6745384 (2004-06-01), Biggerstaff
patent: 6938249 (2005-08-01), Roediger et al.
patent: 6988266 (2006-01-01), Lam et al.
patent: 6993757 (2006-01-01), Rajagopalan
patent: 7086046 (2006-08-01), Barsness et al.
patent: 7386842 (2008-06-01), Eichenberger et al.
patent: 7395531 (2008-07-01), Eichenberger et al.
patent: 7779399 (2010-08-01), Huang et al.
patent: 7856627 (2010-12-01), Archambault et al.
patent: 2003/0097652 (2003-05-01), Roediger et al.
patent: 2003/0208749 (2003-11-01), Rajagopalan
patent: 2004/0221281 (2004-11-01), Suganuma
patent: 2005/0283773 (2005-12-01), Eichenberger et al.
patent: 2006/0048119 (2006-03-01), Ren et al.
patent: 2007/0169058 (2007-07-01), Eichenberger et al.
“Termination Analysis of Logic Programs Through Combination of Type-Based Norms”, Maurice Bruynooghe, [online], Apr. 2007, pp. 1-44, [Retrived from Internet on Jul. 22, 2011], <http://delivery.acm.org/10.1145/1220000/1216378/p1-bruynooghe.pdf>.
“Array Bounds Check Elimination for the Java HotSpot™ Client Compiler”, Thomas Würthinger,[online], 2007, pp. 125-133,[Retrieved from Internet on Jul. 22, 2011], <URL: http://delivery.acm.org/10.1145/1300000/1294343/p125-wurthinger.pdf>.
“Space-Efficient Scheduling of Nested Parallelism”, Girija J. Narlikar et al., [online], 1999, pp. 138-173, [Retrieved from Internet on Jul. 22, 2011], <URL: http://delivery.acm.org/10.1145/320000/314607/p138-narlikar.pdf>.
“Fast, Effective Dynamic Compilation”, Joel Auslander et al., [online], 1996, pp. 1-11, Retrieved from Internet onJul. 22, 2011: <URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.4382&rep=repl&type=pdf>.
“Efficient and Effective Array Bound Checking”, Thi Viet Nganguyen et al., [online], 2005, pp. 527-570, Retrived from Internet on Jul. 22, 2011, <URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.7085&rep=rep1&type=pdf>.
“Design and exploitation of a high-performance SIMD floating-point unit” , Catterfee S et al.[online], Mar. 2005,pp. 377-391, retrieved from Internet on Jul. 22, 2011 <URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5388790>.
Suganuma, et al, “Overview of the IBM Java Just-in-Tome (JIT) Compiler”, IBM Systems Journal vol. 39, No. 1, 2000, pp. 175-193.

Affiliated with

Also associated with

Rating

Eliminating maximum/minimum operations in loop bounds does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Eliminating maximum/minimum operations in loop bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Eliminating maximum/minimum operations in loop bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4299119