Path: utzoo!yunexus!geac!syntron!jtsv16!uunet!lll-winken!lll-tis!ames!mailrus!cwjcc!gatech!udel!rochester!dietz
From: dietz@cs.rochester.edu (Paul Dietz)
Newsgroups: comp.arch
Subject: Re: register save/restore
Summary: An Application of Network Flow
Message-ID: <1988Oct30.135800.7722@cs.rochester.edu>
Date: 30 Oct 88 18:58:00 GMT
Article-I.D.: cs.1988Oct30.135800.7722
References: <3300037@m.cs.uiuc.edu>
Reply-To: dietz@cs.rochester.edu (Paul Dietz)
Organization: U of Rochester, CS Dept, Rochester, NY
Lines: 13

"Callee-saves" and "caller-saves" are just two instances of a
more general register saving strategy.  Suppose we know the
call graph of the program, and we know which registers each
procedure uses.  Register save/restore code can be thought of
as occuring on the edges of this call graph.  If we know the
execution frequency of each arc in the graph, and if the time
to save/restore a register is independent of the number of
register being saved (a big if), the optimal code for saving/
restoring each register can be found using an algorithm for
maximum network flow (finding the cut of minimum total frequency
that disconnects all procedures using the register).

Paul F. Dietz
dietz@cs.rochester.edu