Browse Prior Art Database

Range analysis with bitwise operations

IP.com Disclosure Number: IPCOM000012367D
Original Publication Date: 2003-May-01
Included in the Prior Art Database: 2003-May-01
Document File: 4 page(s) / 57K

Publishing Venue

IBM

Abstract

A method is disclosed for efficiently calculating value ranges under logical bitwise operations. Keywords: Value range propagation, Interval arithmetic, bitwise operations, AND, OR, NOT, XOR

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 35% of the total text.

Page 1 of 4

Range analysis with bitwise operations

A program is disclosed that allows variables, each representing a range of values, to be combined under logical bitwise operations to give a result range of values with exact tight bounds.

     An example of a use of value range arithmetic is in compilers. Compilers attempt to track the values of variables through the program so that some redundant operations can be omitted or other operations can be simplified. For example if the value of a variable is known to be within a certain range then a comparison of that value with another may be seen to be always true or always false.

     One technique is to track the range of values of a integer variable by giving it upper and lower limits, so that it is known to be between a maximum and minimum value. These maximum and minimum values can be manipulated if for example two variables are added. These are some of the known techniques for tracking value ranges through arithmetic, not bitwise, operations:

Mark William Stephenson

Bitwise: Optimizing Bitwidths Using Data-Range Propagation (2000), available at http://citeseer.nj.nec.com/stephenson00bitwise.html; and

Jason R. C. Patterson - Accurate Static Branch Prediction by Value Range Propagation in {SIGPLAN} Conference on Programming Language Design and Implementation (1995, pp 67-78), available at http://citeseer.nj.nec.com/patterson95accurate.html.

     Tracking value ranges of integer variables through logical bitwise operations such as bitwise AND or OR would be a useful extension to these ideas. Existing solutions for bitwise operations are approximate, slow, or do not work for negative variables. For example the maximum of an AND operation is bounded by the maximum of values of the inputs, but this is an upper bound. The maximum of an OR operation bounded by the maximum of the inputs rounded up to the next power of 2 minus 1, but this is an upper bound. A simple exact technique would be to try every possible value of each input variable, then for each possible value do the bitwise operation, then combine all the possible output values to give a resulting range. This is computationally infeasible for variables spanning a large range. This invention allows the range to be modified due to the effect of bitwise operations, giving tight upper and lower bounds on the result. This solution is exact. This allows a compiler to do a better job of tracking the ranges of variables through the program being compiled, and allows the compiler to eliminate more operations. The four main operations to consider are bitwise AND, bitwise OR, bitwise NOT and bitwise XOR.

Operations:

Page 2 of 4


1.


2.


3.


4.

Range: [min, max] = inclusive range

     To find the maximum of two ranges under the AND operation it is not sufficient to do a bitwise AND of the maximum values of the inputs.

E.g. [01011b, 10110b] & [11001b, 11011b] = [01000b, 10011b] [00000b, 01001b] & [00000b, 01010b] = [00000b, 01001b]

   For unsigned operands: To find the maximum...