Wed, 26 May 1993 22:53:26 GMT

Related articles |
---|

Evaluation Tech. Needed for Register Allocation yhshiau@csie.nctu.edu.tw) (1993-05-24) |

Re: Evaluation Tech. Needed for Register Allocation preston@dawn.cs.rice.edu (1993-05-24) |

Re: Evaluation Tech. Needed for Register Allocation yhshiau@csie.nctu.edu.tw) (1993-05-25) |

Re: Evaluation Tech. Needed for Register Allocation preston@dawn.cs.rice.edu (1993-05-26) |

Newsgroups: | comp.compilers |

From: | preston@dawn.cs.rice.edu (Preston Briggs) |

Keywords: | registers, optimize |

Organization: | Rice University, Houston |

References: | 93-05-115 93-05-123 |

Date: | Wed, 26 May 1993 22:53:26 GMT |

yhshiau@csie.nctu.edu.tw (Yuh-Horng Shiau(dcp78804)) writes:

*>Instead of defining a live range based on single touchstone, such as*

*>instruction number in Chaitin's algorithm and basic block number in*

*>the priority-based algorithm (proposed by Chow and Hennessy)*

Before we go further, I need to try and clarify some misunderstandings.

(This might be a better subject for e-mail, but perhaps others will

benefit).

Chow and Hennessy (and Larus and Hilfinger) represent each live range as a

set of basic blocks. Thus, they can determine if two live ranges

interfere by computing the intersection of their two sets -- if the

intersection is empty, there is no interference.

This approach is imprecise (but safely conservative) in that two live

ranges that don't actually interfere may have intersecting live ranges.

For example

A = <expression 1> Block 1

B = A + <expression 2>

if (p)

{ Block 2

C = B + <expression 3>

D = C

}

print C, D Block 2

return

Here, no variables need interfere; however, Chow & Hennessy's approach

would compute that B interferes with A, C, and D and that C and D

interfere with each other. The live ranges of the variables would be:

A { 1 }

B { 1, 2 }

C { 2, 3 }

D { 2, 3 }

By performing the appropriate set intersections, Chow and Hennessy arrive

at their conservative solution.

Chaitin et al. don't really have a similar concept of live range (they use

the words, but in a different sense than Chow and Hennessy). Instead,

they compute interference directly from the control-flow graph and

appropriate data-flow information.

Conceptually, they compute live_out information for each basic block (that

is, the set of variables live at the output of each basic block). For our

example, these would look like

A = <expression 1> Block 1

B = A + <expression 2>

if (p)

{ B }

{

C = B + <expression 3> Block 2

D = C

} { C, D }

print C, D Block 3

return

{ }

The steps to building the interference graph go like this

init the graph G to empty

for each block B, do

init Live to equal B.live_out

for each instruction I in B (in reverse order) do

if I is a copy instruction (e.g. D := C) then

remove the source of the copy (i.e., C) from Live

endif

for each var V defined in I do

for each member M of Live do

add an interference between V and M to G

endfor

endfor

Live := Live - I.defs (remove all defined vars from Live)

Live := Live + I.refs (add all references vars to Live)

endfor

endfor

Note the special handling of copies. It's necessary because otherwise we

might think that C and D interfere even though they obviously have the

same value and may therefore be in the same register.

*>we define a live range by using a two-dimensional*

*>representation (T, B). Where T is a global time stamp for each*

*>instruction in considering, and B is the basic block number that contains*

*>the instruction in considering. For example,*

*>*

*> +--------+*

*> | |*

*> | sr <- | Symbolic register sr is first defined in time Td in block B1.*

*> | |*

*> +--------+*

*> |*

*> V*

*> +--------+*

*> | |*

*> | <- sr | Symbolic register sr is last used in time Tu in block B2.*

*> | |*

*> +--------+*

*>*

*>The live range of symbolic register sr is defined as a set of pairs as*

*>follows:*

*>*

*> LR(sr) = {(T, B) | Td <= T <= Tu, B <= {B1, B2}} (simplified).*

*>*

*>Using this definition, we can exhibit the real life time of a symbolic*

*>register (Td --> Tu) that instruction number and basic block number cannot*

*>exhibit.*

I guess I don't understand. It looks like your equation would give

sr = { (B1,Td) (B1,Td+1) ... (B1,Tu-1) (B1,Tu)

(B2,Td) (B2,Td+1) ... (B2,Tu-1) (B2,Tu) }

You'll want to remove all the pairs of (B1,Tn), Tn is not in B1.

Same for T's not in B2.

It looks like you're trying to improve the precision of Chow and Hennessy,

but you pay a large cost in the size of the sets. Additionally, you still

won't handle the case of copies. Why not use Chaitin's approach? It's

faster and more precise.

Preston Briggs

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.