CODEWITHSUNDEEP
compiler-constructioncompiler-theory
BinaryLust
BinaryLust

Reputation: 21

Computing Liveness of Arrays and Other Non-Scalars in Low Level Intermediate Code

I am having trouble wrapping my head around the concept of calculating array liveness since they are non-scalar values. All books and courses that talk about liveness always use scalar values only but non-scalars seem to need their liveness calculated differently, for example when an array element is defined by assignment that does not necessarily mean the whole array is not live anymore before that point like it does with scalar values. To further complicate things you can only access definitions and uses of an array in high level intermediate code, when we go to lower levels this information partially disappears. Does anybody have any idea how to do this?

Edit: My ultimate goal is to produce interference graphs for graph coloring of stack frames to minimize their size so I will need the the liveness info or live ranges to be precise. The problem is really a 2 part problem. First how do we calculate liveness of non-scalar values in high level intermediate code, second how do we translate that solution into the low level intermediate code version.

Edit: Here is an example of the problem in C, it would be very similar in an AST or high level intermediate code though.

void testFunction() {
    int n;
    int i[100]; // array is declared here

                // array is dead before this point
    i[10] = n;  // array elements are used/defined here, the array is live
    n = i[11];  // array elements are used/defined here, array is still live


    // other code here

    i[12] = n;  // array elements are used/defined here, array is still live
    i[13] = n;  // array elements are used/defined here again but for the            
                // last time, after this the array is not live
 }

In low level intermediate code those array accesses break down into many instructions though, and after optimizations we can lose detail on exactly when the array elements are used and defined because instructions can get somewhat scrambled so it becomes a bit of a mess.

n = i[10]

becomes something like

t0 = 10        // the element of the array we are indexing into
t1 = t0 * size // the size of each element of the array
t2 = &i        // the base address of the array named "i"
t3 = t1 + t2
n  = *t3

Edit: I think I can possibly just add meta data to low level dereferencing instructions to get the definitions and uses of non-scalars on the low level intermediate code like below.

t0 = &i // this would not count as a use since it is only the 
        // address of the array i

n = *t0 // use of i
*t0 = n // definition of i

That only leaves the problem of extracting liveness/live ranges of non-scalars. Scalar liveness is calculated as a backward dataflow problem, a variable becomes live when a use of it is seen and dies when we encounter a definition of it. For non-scalar liveness it's lifetime seems to need to extend from the first def or use encountered until the last definition encountered on each flow path. I am thinking of calculating the reaching definitions of a non-scalar first then using that to compute def-use and use-def chains, then combine all of the use-def chains together into a single live range. I think this would give the proper live ranges for any non-scalar as long as it's initial definition wasn't done outside the function?, In that case it would be live all the way up until the function entry point. So this wouldn't work for globals but they will be considered always live anyway and don't need to have their liveness calculated. Am I missing anything? and can anybody think of a better way of doing this?

Upvotes: 2

Views: 231

Answers (1)

rici
rici

Reputation: 241881

Liveness analysis is always a conservative estimate. A "live" variable may well never be used. (Its future uses might be conditional, even based on conditions whose values might already be determined.) What's important is only that a non-live variable is guaranteed to not be needed. The more precise the analysis, the more optimisation possibilities will be presented, but there is a trade-off: more precise analyses might be prohibitively expensive compared with the possible value added.

In this light, it's worth asking what value can be generated from knowing that part of an array is not live. Only in very unusual circumstances is it possible to recycle part of an array, for example.

So treating the array as though it were a single entity is a reasonable approach. In this approximation an array is live if any element in the array is; only in the case that no element in the array will be needed do we remove the array from the live set. It's clear that this is a conservative approximation; as indicated, it probably provides as much useful information as can be applied.

It can be useful to know the value of a particular array element, but even there it is often considered sufficient to be able to know that the entire array will not be mutated, rather than trying to track mutability of individual elements. Once an array is known to be immutable, it may be possible to deduce the value of an element at a known index, allowing constant-folding of expressions involving lookup tables. Some compilers definitely do that, but again there is a trade-off between complexity and value-added, and absolute precision is not required in cases where it would be hard or impossible to perform a completely precise analysis.

Upvotes: 1

Related Questions