! File: RESHUF.RTN ! ! This work was supported by the Advanced Research ! Projects Agency of the Office of the Secretary of ! Defense (F44620-73-C-0074) and is monitored by the ! Air Force Office of Scientific Research. ! ! THE FOLLOWING ROUTINES TRY TO ASSIGN A TEMP-NAME TO A REGISTER ! IN SPITE OF CONFLICTING TEMP-NAMES PREVIOUSLY ASSIGNED TO THAT ! REGISTER, BY MOVING THEM AROUND TO OTHER REGISTERS IF POSSIBLE. Module RESHUF = Begin Require 'bliss.req'; Literal SRCHWIDTH=3, SRCHDEPTH=4, INF=SRCHWIDTH+1; Macro RELTNREP(A) = RELEASESPACE(A,SZ_TNREP) %; Forward Routine TRS; ! SIMPLE BUBBLE SORT OF THE INDIRECT VECTOR V OF SIZE N. Routine SORT(V : Ref Vector,N : Integer) : Novalue = Begin Decr I From .N-2 To 0 Do Decr J From .I To 0 Do If .V[.J] Gtr .V[.I+1] Then SWAP(V[.J],V[.I+1]) End; Macro ENCLOSES(T,TN)= ! TRUE IF LIFETIME OF TN IS ENTIRELY WITHIN THAT OF T. ( T[tn_lon_fu] Lequ TN[tn_lon_fu] And T[tn_lon_lu] Gequ TN[tn_lon_lu] And T[tn_fon_fu] Lequ TN[tn_fon_fu] And T[tn_fon_lu] Gequ TN[tn_fon_lu] ) %; ! TRUE IF TN MUST REMAIN IN THE REG TO WHICH IT IS ALREADY ASSIGNED. Routine SPLCASE(TN : Ref GT)= Begin Local L : Ref LSTHDR, TR : Ref TNREPR, T : Ref GT; ! cannot reshuffle specific register usages If .TN[tn_request] Eql SRREQDB Then Return TRUE; ! tempnames not bound to anything else (e.g. free) are available If .TN[tn_pref] Eqla 0 Then Return FALSE; ! cannot reshuffle tempnames which are bind preferences or which ! have bind preferences to them If .TN[tn_type] Eql BNDPREF Then Return TRUE; L = .TN[tn_pref]; TR = .L; Until (TR = .TR[itm_rlink]) Eqla .L Do Begin T = .TR[tnr_ptr]; If .T[tn_type] Eql BNDPREF And .T[gt_reg] Eql .TN Then Return TRUE End; Return FALSE End; ! THIS ROUTINE COUNTS THE NUMBER OF CONFLICTS BETWEEN TN AND THE ! TEMP-NAMES ALREADY ON REGLIST, AND RECORDS IN THE VECTOR CLIST ! THE TN REPRESENTATIVES OF THE CONFLICTING TN'S. Global Routine COUNTCONFLICTS(TN : Ref GT,REGLIST : Ref TNREPR,CLIST : Ref Vector)= Begin Macro OVERLAPFON=(((.T[tn_fon_fu]-.TN[tn_fon_lu])*(.TN[tn_fon_fu]-.T[tn_fon_lu])) Geq 0) %; Local N : Integer, TR : Ref TNREPR, CNT : Integer, T : Ref GT; N = (.REGLIST - REGS) / 8; ! cannot move conflicts into reserved registers If .RESERVED<.N,1,0> Then Return INF; ! cannot move conflicts into closed registers If EMPTY(.REGLIST) Then Return INF; CNT = 0; TR = .REGLIST; Until (TR = .TR[itm_rlink]) Eqla .REGLIST Do Begin T = .TR[tnr_ptr]; ! anything beyond guaranteed not to conflict If .T[tn_lon_fu] Gtru .TN[tn_lon_lu] Then Exitloop; ! if the LON's overlap If .T[tn_lon_lu] Gequ .TN[tn_lon_fu] Then ! if the FON's overlap also If OVERLAPFON Then ! if 'T' completely encloses 'TN' then don't use this register. ! is this to avoid reshuffling the target of the inner TN? If .CNT Eql 0 And ENCLOSES(.T,.TN) Then Return INF ! don't move special case TN's Else If SPLCASE(.T) Then Return INF ! one more TN found Else If (CNT = .CNT+1) Leq SRCHWIDTH Then CLIST[.CNT-1] = .TR End; Return .CNT End; Routine TEMPINSERT(TN : Ref GT,LIST : Ref TNREPR)= Begin Local TR : Ref TNREPR, L : Ref TNREPR, X : Ref TNREPR, T : Ref GT; ! does this imply that it is possible for TN to not be inserted? TR = .LIST; Until (TR = .TR[itm_rlink]) Eqla .LIST Do Begin T = .TR[tnr_ptr]; If .T[tn_lon_fu] Lssu .TN[tn_lon_fu] Then L = .TR Else Begin X = TNREP(.TN); LINK(.X,.L); Exitloop End End; X[tnr_req] = .TN[tn_request]; TN[tn_request] = SRREQDB; Return .X End; Routine MAKEPERM(T : Ref TNREPR,LST : Ref LSTHDR) : Novalue = Begin Local TN : Ref GT; TN = .T[tnr_ptr]; TN[tn_request] = .T[tnr_req]; TN[tn_bind_list] = .LST End; ! this routine moves a TN which had been found to conflict back onto ! its original register list. Routine REINSERT(TP : Ref TNREPR,LST : Ref TNREPR) : Novalue = Begin Local TR : Ref TNREPR, L : Ref TNREPR, TN : Ref GT, T : Ref GT; ! does this imply that it is possible for the TN to not be placed ! back on the list? TN = .TP[tnr_ptr]; TR = .LST; Until (TR = .TR[itm_rlink]) Eqla .LST Do Begin T = .TR[tnr_ptr]; If .T[tn_lon_fu] Lssu .TN[tn_lon_fu] Then L = .TR Else Begin LINK(.TP,.L); Exitloop End End End; ! TRIES TO LINK A TEMP NAME ONTO A REGLIST, IN SPITE OF CONFLICTING ! TEMP NAMES ALREADY ON SAME. IT REMOVES THE CONFLICTING TN'S, ! TRYING TO FIT THEM ONTO OTHER REGLISTS. (IN FITTING THEM ! IT COULD END UP CALLING TRS, WHICH WOULD CALL THIS ROUTINE. THE ! DEPTH OF THIS INDIRECT RECURSION IS LIMITED BY "SRCHDEPTH", AND ! PARAMETER "DEPTH".) Global Routine TRYALT(TN : Ref GT,CNT : Integer,LIST : Ref LSTHDR, CONFLIX : Ref Vector,DEPTH : Integer) = Begin Local N : Integer, LSTLON : Integer, LSTFON : Integer, GTSTLON : Integer, GTSTFON : Integer, SVLONF : Integer, SVLONL : Integer, SVFONF : Integer, SVFONL : Integer, SVPMIT : Ref GT, Z : Integer, T : Ref GT, TP : Ref TNREPR; ! if count conflicts found too many conflicts N = (.LIST - REGS) / 8; If .CNT Gtr SRCHWIDTH Then FAIL; ! REMOVE ALL CONFLICTS TEMPORARILY. also note the lower and upper ! LON/FON bounds of TN and set its bounds to this to make it look like ! it spans the entire conflicting range. SVPMIT = .TN[tn_permit]; SVLONF = LSTLON = .TN[tn_lon_fu]; SVLONL = GTSTLON = .TN[tn_lon_lu]; SVFONF = LSTFON = .TN[tn_fon_fu]; SVFONL = GTSTFON = .TN[tn_fon_lu]; Decr I From .CNT-1 To 0 Do Begin TP = .CONFLIX[.I]; T = .TP[tnr_ptr]; DELINK(.TP); If .T[tn_lon_fu] Lssu .LSTLON Then LSTLON = .T[tn_lon_fu]; If .T[tn_lon_lu] Gtru .GTSTLON Then GTSTLON = .T[tn_lon_lu]; If .T[tn_fon_fu] Lssu .LSTFON Then LSTFON = .T[tn_fon_fu]; If .T[tn_fon_lu] Gtru .GTSTFON Then GTSTFON = .T[tn_fon_lu] End; ! INSERT TN INTO LIST, ALSO TEMPORARILY TP = TEMPINSERT(.TN,.LIST); TN[tn_permit] = 0; TN[tn_lon_fu] = .LSTLON; TN[tn_lon_lu] = .GTSTLON; TN[tn_fon_fu] = .LSTFON; TN[tn_fon_lu] = .GTSTFON; ! NOW TRY TO PUT THE CONFLICTING TN'S ELSEWHERE. Z = .CNT; Decr I From .CNT-1 To 0 Do Begin T = .CONFLIX[.I]; ! try settling this conflict by using another open register If TRYOPREG(.T[tnr_ptr]) Then Begin Z = .Z - 1; RELTNREP(.T) End ! try settling this conflict by shuffling registers Else If TRS(.T[tnr_ptr],.DEPTH-1) Then Begin Z = .Z - 1; RELTNREP(.T) End End; TN[tn_permit] = .SVPMIT; TN[tn_lon_fu] = .SVLONF; TN[tn_lon_lu] = .SVLONL; TN[tn_fon_fu] = .SVFONF; TN[tn_fon_lu] = .SVFONL; ! if we were able to move conflicts If .Z Eql 0 Then Begin MAKEPERM(.TP,.LIST); Return TRUE End; ! if conflicts could not be moved DELINK(.TP); TN[tn_request] = .TP[tnr_req]; RELTNREP(.TP); ! re-insert the conflicts. do recursive side effects create any problems? ! I assume SPLCASE is responsible for that. Decr I From .Z-1 To 0 Do REINSERT(.CONFLIX[.I],.LIST); Return FALSE End; ! THIS IS THE CONTROLLING ROUTINE FOR REGISTER REPACKING. ! ! 'TN' has been found by the caller to not be able to fit in any ! of the open registers. this routine attempts to reshuffle the ! registers in order to make it fit. 'depth' is the recursion ! depth and is used to limit searches. Global Routine TRS(TN : Ref GT,DEPTH : Integer) = Begin Macro RPART= 0, 0,32,0 %, CPART= 0,32,32,0 %; ! must be high word for sorting Local N : Integer, K : Integer, R : BlockVector[6,1,Quad], C : Vector[6*SRCHWIDTH,Quad]; If .DEPTH Leq 0 Then FAIL; ! count the number of conflicts each register has with 'TN' Decr I From 5 To 0 Do Begin R[.I,RPART] = .I; R[.I,CPART] = COUNTCONFLICTS(.TN,REGS[.I],C[.I*SRCHWIDTH]) End; ! sort the conflicts so the register with the fewest conflicts ! will be examined first SORT(R,6); ! try reshuffling each register to see if TN can be made to fit Incr I From 0 To 5 Do Begin K = .R[.I,RPART]; N = .R[.I,CPART]; ! if there are a reasonable number of conflicts... If .N Leq SRCHWIDTH Then Begin ! try moving the conflicts from this register. if it works then success If TRYALT(.TN,.N,REGS[.K],C[.K*SRCHWIDTH],.DEPTH) Then SUCCESS; ! why is this necessary? maybe because tryalt itself restores what ! it changed but it is recursive and so changes below it have changed ! conflicts If .I Neq 5 Then Begin Decr J From 5 To .I+1 Do Begin K = .R[.J,RPART]; R[.J,CPART] = COUNTCONFLICTS(.TN,REGS[.K],C[.K*SRCHWIDTH]) End; SORT(R[.I+1,RPART],5-.I) End End End; FAIL End; End Eludom