ocount.p

<B>Digital的Unix操作系统VAX 4.2源码</B>

(*#@(#)ocount.p	4.1	Ultrix	7/17/90 *)
(****************************************************************************
 *									    *
 *  Copyright (c) 1984 by						    *
 *  DIGITAL EQUIPMENT CORPORATION, Maynard, Massachusetts.		    *
 *  All rights reserved.						    *
 * 									    *
 *  This software is furnished under a license and may be used and copied   *
 *  only in  accordance with  the  terms  of  such  license  and with the   *
 *  inclusion of the above copyright notice. This software or  any  other   *
 *  copies thereof may not be provided or otherwise made available to any   *
 *  other person.  No title to and ownership of  the  software is  hereby   *
 *  transferred.							    *
 * 									    *
 *  The information in this software is  subject to change without notice   *
 *  and  should  not  be  construed as  a commitment by DIGITAL EQUIPMENT   *
 *  CORPORATION.							    *
 * 									    *
 *  DIGITAL assumes no responsibility for the use  or  reliability of its   *
 *  software on equipment which is not supplied by DIGITAL.		    *
 * 									    *
$Header: ocount.p,v 1.7 84/06/06 13:04:08 powell Exp $
 ****************************************************************************)
#include "globals.h"
#include "bexpr.h"
#include "optim.h"
#include "ocount.h"
#include "builtin.h"
#include "decls.h"

const
    MINCOUNTFORREG = 3;	{  number of references to get allocated to a register }
type
    StorageCount = record
	count : integer;
	offset : MemoryOffset;
	addressed : boolean;
    end;
    TempSet = set of 0..NUMTEMPS;
var
    refCount : array [0..MAXTEMPSTORAGE] of StorageCount;
    maxTemp : TempNumber;
    inUseTemps, inUseTempsToBeFreed : TempSet;

procedure InitTemps;
begin
    inUseTemps := [];
    inUseTempsToBeFreed := [];
    maxTemp := 0;
end;

function AllocTemp{ : TempNumber};
var
    t : TempNumber;
    found : boolean;
begin
    case target of
	TARGETVAX: begin
	    t := 1;
	    while not found and (t <= NUMTEMPS) do begin
		if not (t in inUseTemps) then begin
		    found := true;
		end else begin
		    t := t + 1;
		end;
	    end;
	    if not found then begin
		Error('AllocTemp: Too many temps?');
		t := NULLTEMP;
	    end else begin
		inUseTemps := inUseTemps + [t];
		if t > maxTemp then begin
		    maxTemp := t;
		end;
	    end;
	end;
	TARGETTITAN : begin
    { when unlimited temporaries works
	    maxTemp := maxTemp + 1;
	    t := maxTemp;
    }
	    t := 1;
	    while not found and (t <= NUMTEMPS) do begin
		if not (t in inUseTemps) then begin
		    found := true;
		end else begin
		    t := t + 1;
		end;
	    end;
	    if not found then begin
		Error('AllocTemp: Too many temps?');
		t := NULLTEMP;
	    end else begin
		inUseTemps := inUseTemps + [t];
		if t > maxTemp then begin
		    maxTemp := t;
		end;
	    end;
	end;
    end;
    AllocTemp := t;
end;

procedure FreeTemp{(t : TempNumber)};
begin
    case target of
	TARGETVAX : begin
	    if not (t in inUseTemps) or (t in inUseTempsToBeFreed) then begin
		ErrorNumber('FreeTemp: not in use? ',t);
	    end;
	    inUseTempsToBeFreed := inUseTempsToBeFreed + [t];
	end;
	TARGETTITAN : begin
	    if not (t in inUseTemps) or (t in inUseTempsToBeFreed) then begin
		ErrorNumber('FreeTemp: not in use? ',t);
	    end;
	    inUseTempsToBeFreed := inUseTempsToBeFreed + [t];
	end;
    end;
end;

procedure UpdateTemps;
begin
    inUseTemps := inUseTemps - inUseTempsToBeFreed;
    inUseTempsToBeFreed := [];
end;

procedure ReduceExprNeededCounts{(en : ExprNode; count : integer)};
var
    on : OptNode;
begin
    on := ExprToOpt(en);
    on := on^.rootEqual;
    on^.neededCount := on^.neededCount - count;
    on^.referencedCount := on^.referencedCount - count;
    if on^.tempNumber <> NULLTEMP then begin
	{ already a subexpression, children already reduced }
    end else begin
	ReduceNeededCounts(on,count);
    end;
end;

{ reduce use counts in all expression nodes used by this expression }
procedure ReduceNeededCounts{(on : OptNode; count : integer)};
var
    en, pen : ExprNode;
begin
    en := on^.expr;
    case en^.kind of
	EXPRCONST,
	EXPRVAR : { no descendents };
	EXPRNAME,
	EXPRSYM,
	EXPRSET : ExprError(en,'ReduceNeededCounts: unexpected expr');
	EXPRUNOP : begin
	    ReduceExprNeededCounts(en^.opnd,count);
	end;
	EXPRBINOP : begin
	    ReduceExprNeededCounts(en^.opnd1,count);
	    ReduceExprNeededCounts(en^.opnd2,count);
	end;
	EXPRSUBSCR : begin
	    ReduceExprNeededCounts(en^.arr,count);
	    ReduceExprNeededCounts(en^.subsExpr,count);
	end;
	EXPRDOT : begin
	    ReduceExprNeededCounts(en^.rec,count);
	end;
	EXPRDEREF : begin
	    ReduceExprNeededCounts(en^.ptr,count);
	end;
	EXPRFUNC : begin
	    ReduceExprNeededCounts(en^.func,count);
	    pen := en^.params^.first;
	    while pen <> nil do begin
		ReduceExprNeededCounts(pen,count);
		pen := pen^.next;
	    end;
	end;
	EXPRVAL : begin
	    ReduceExprNeededCounts(en^.exprVal,count);
	end;
	EXPRCHECK : begin
	    ReduceExprNeededCounts(en^.checkExpr,count);
	end;
    end;
end;

procedure CommonSubExpr{(en : ExprNode; mode : EvalMode; state : EvalState)};
var
    on, ron, cron : OptNode;
begin
    on := ExprToOpt(en);
    ron := on^.rootEqual;
    if not ron^.eligible and (ron^.neededCount > 1)
	and (ron^.nonTrivial or (ron^.containedNonTrivial <> nil))
    then begin
	{ got a possible subexpression }
	if SizeOf(en^.exprType) > WORDSIZE then begin
	    { cannot handle multiple word sub expression }
	end else if ron^.nonTrivial then begin
	    ron^.eligible := true;
	end else begin
	    { must contain a non-trivial expression }
	    cron := ron^.containedNonTrivial^.rootEqual;
	    { see if contained expression is needed only here }
	    if cron^.neededCount = ron^.neededCount then begin
		{ this is the only use of the nonTrivial expression }
		{ make this be the subexpression }
		ron^.eligible := true;
	    end;
	end;
    end;
    if ron^.eligible then begin
	if ron^.tempNumber <> NULLTEMP then begin
	    ron^.usedCount := ron^.usedCount + 1;
	    if state = EVALPRE then begin
		{ already calculated }
	    end else if state = EVALPOST then begin
	        if ron^.usedCount < ron^.neededCount then begin
		    { not finished with it yet }
		end else begin
		    if TraceOptim then begin
			write(output,'CSE: ',on^.uniqueId:1,' ',on^.usage,' ',
			    state:1,' freetemp=',ron^.tempNumber,' ');
			WriteExpr(output,on^.expr);
			writeln(output);
		    end;
		    { finished with saved value }
		    FreeTemp(ron^.tempNumber);
		end;
	    end else begin
		{ reuse saved value }
		if ron^.usedCount = ron^.neededCount then begin
		    on^.usage := OUSELAST;
		    refCount[MAXTSTORAGE+ron^.tempNumber].count :=
				    refCount[MAXTSTORAGE+ron^.tempNumber].count
				    + on^.loopNest;
		    if TraceOptim then begin
			write(output,'CSE: ',on^.uniqueId:1,' ',on^.usage,' ',
			    state:1,' freetemp=',ron^.tempNumber,' ');
			WriteExpr(output,on^.expr);
			writeln(output);
		    end;
		    FreeTemp(ron^.tempNumber);
		end else begin
		    on^.usage := OUSEMIDDLE;
		    refCount[MAXTSTORAGE+ron^.tempNumber].count :=
				    refCount[MAXTSTORAGE+ron^.tempNumber].count
				    + on^.loopNest;
		    if TraceOptim then begin
			write(output,'CSE: ',on^.uniqueId:1,' ',on^.usage,' ',state:1,' ');
			WriteExpr(output,on^.expr);
			writeln(output);
		    end;
		end;
	    end;
	end else begin
	    { allocate temp to save it in }
	    ron^.tempNumber := AllocTemp;
	    if ron^.tempNumber = NULLTEMP then begin
		{ couldn't allocate a temp }
		ron^.eligible := false;	{ can't make it a cse }
	    end else begin
		{ will save a value, make it look like it was used }
		if TraceOptim then begin
		    write(output,'Reduce: rc=',ron^.referencedCount:1,', nc=',
			ron^.neededCount:1,', uc=', ron^.usedCount:1,
			', temp=',ron^.tempNumber:1,', expr=');
		    WriteExpr(output,on^.expr);
		    writeln(output);
		end;
		ReduceNeededCounts(ron,ron^.referencedCount-1);
		{ evaluate expression }
		if ron^.address then begin
		    { cse is the address }
		    DoCountExpr(en,EVALPOINT);
		end else begin
		    DoCountExpr(en,mode);
		end;
		if state = EVALPRE then begin
		    on^.usage := OUSEGENERATE;
		    refCount[MAXTSTORAGE+ron^.tempNumber].count :=
				    refCount[MAXTSTORAGE+ron^.tempNumber].count
				    + on^.loopNest;
		    if TraceOptim then begin
			write(output,'CSE: ',on^.uniqueId:1,' ',on^.usage,' ',state:1,' ');
			WriteExpr(output,on^.expr);
			writeln(output);
		    end;
		end else begin
		    on^.usage := OUSEFIRST;
		    refCount[MAXTSTORAGE+ron^.tempNumber].count :=
				    refCount[MAXTSTORAGE+ron^.tempNumber].count
				    + on^.loopNest;
		    if TraceOptim then begin
			write(output,'CSE: ',on^.uniqueId:1,' ',on^.usage,' ',state:1,' ');
			WriteExpr(output,on^.expr);
			writeln(output);
		    end;
		end;
		{ count this as a use, too }
		ron^.usedCount := ron^.usedCount + 1;
	    end;
	end;
    end else begin
	{ not subexpression, do normal evaluate }
	DoCountExpr(en,mode);
    end;
end;

procedure InitCounts;
var
    index : integer;
begin
    InitTemps;
    for index := 0 to MAXTEMPSTORAGE do begin
	refCount[index].count := 0;
	refCount[index].offset := index * WORDSIZE;
	refCount[index].addressed := false;
    end;
end;

procedure ComputeCounts(proc : ProcNode);
var
    rooton, classon, equalon, on : OptNode;
    vn : VarNode;
    index : integer;
begin
    rooton := cseRootExpr[EXPRVAR];
    if rooton <> nil then begin
	classon := rooton;
	repeat
	    vn := classon^.expr^.exprVar;
	    if vn^.address.kind = MEMGLOBAL then begin
		{ don't worry about globals }
	    end else if (vn^.address.kind <> MEMFAST) or
		    (vn^.address.proc <> proc)
	    then begin
		{ doesn't qualify, but tally uplevel refs }
		proc^.doesUpLevel := proc^.doesUpLevel + [vn^.address.level]; 
	    end else begin
		{ candidate }
		index := trunc(vn^.address.offset) div WORDSIZE;
		if proc^.displayLevel in proc^.containsUpLevel then begin
		    { possible uplevel reference, assume worst }
		    refCount[index].addressed := true;
		end else begin
		    equalon := classon;
		    repeat
			if equalon^.rootEqual = equalon then begin
			    (* Experiment: just multiply by reference count 
			    on := equalon;
			    repeat
				refCount[index].count := refCount[index].count
						+ on^.loopNest;
				on := on^.nextEqual;
			    until on = equalon;
			    *)
			    refCount[index].count := refCount[index].count
				+ equalon^.loopNest * equalon^.referencedCount;
			end;
			equalon := equalon^.nextCongruent;
		    until equalon = classon;
		end;
	    end;
	    classon := classon^.nextClass;
	until classon = rooton;
    end;
    if proc^.enclosing <> nil then begin
	proc^.enclosing^.containsUpLevel := proc^.enclosing^.containsUpLevel +
		    proc^.doesUpLevel;
    end;
end;

procedure SortArray(l, r : integer);
var
    i, j : integer;
    tmp : StorageCount;
begin
    for i := l to r do begin
	if refCount[i].addressed then begin
	    refCount[i].count := -1000000-refCount[i].count;
	end;
    end;
    for i := l to r-1 do begin
	for j := i+1 to r do begin
	    if refCount[i].count < refCount[j].count then begin
		tmp := refCount[i];
		refCount[i] := refCount[j];
		refCount[j] := tmp;
	    end;
	end;
    end;
end;

procedure ReassignStorage(proc : ProcNode);
var
    index, maxindex, ireg : integer;
    tm : TempMapNode;
begin
    ComputeCounts(proc);

    case target of
	TARGETVAX : begin
	    maxindex := trunc(proc^.mem^.maximum[MEMFAST]) div WORDSIZE - 1;
	    for index := 1 to maxTemp do begin
		refCount[maxindex+index] := refCount[MAXTSTORAGE+index];
	    end;
	    maxindex := maxindex + maxTemp;
	    if TraceOptim then begin
		writeln(output,'Reassign storage before T',maxindex-maxTemp:1,
				' O',maxTemp:1);
		for index := 0 to maxindex do begin
		    writeln(output,index:3,refCount[index].count:5,
			    trunc(refCount[index].offset) div WORDSIZE:5,' ',
			    refCount[index].addressed);