.IIF	NDF	RSX	RSX	=	1	;Assume RSX	;01+
	.TITLE	CC204
	.ident	/X01U05/

	.NLIST	BEX, CND
	.ENABL	LC, GBL
	.LIST	MEB						;01 -

;
; C COMPILER
; COMPUTE COSTS USING SETHI-ULLMAN ALGORITHM.
;
; VERSION X01
;
; DAVID G. CONROY	09-FEB-78
; LAST UPDATED:		23-MAY-79
;
; Edit history
; 01 04-Mar-80 MM	Added RT11 support
; 02 02-Jun-80 MM	Added EIS stuff
; 03 15-Dec-80 MM	Changed XOR
; u1 27-Aug-81 CCG	Fixed Sethi for odd reg and float allocation.
; u2 11-Sep-81 CCG	Changed default to float from double.
; 04 10-Feb-82 MM	Merged sources.
; 05 11-Feb-82 MM	Problem with "while ((n /= 2) > 0)"
; u3 02-Apr-82 CCG	Fixed bug causing trashing of R0.
; u4 05-Apr-82 CCG	Allow use of R1 sometimes.
; u5 19-Apr-82 CCG	Fixed cost of JSR if no args (looks like unary).
; u6 21-Jul-82 CCG	Added OP.MLL and OP.DLL to OPDOPE, removed OP.CVM.
; u7 28-Sep-82 CCG	Changed CLASFY calling sequence.
;

	.GLOBL	SETHI
	.GLOBL	NTWO						;02
	.GLOBL	FLIP
	.GLOBL	OPDOPE

;
; TABLE USED TO REVERSE CONDITIONALS.
;

FLIP:	.WORD	OP.EQ		;EQ
	.WORD	OP.NE		;NE
	.WORD	OP.GT		;LT
	.WORD	OP.GE		;LE
	.WORD	OP.LE		;GE
	.WORD	OP.LT		;GT
	.WORD	OP.GTU		;LTU
	.WORD	OP.GEU		;LEU
	.WORD	OP.LEU		;GEU
	.WORD	OP.LTU		;GTU
	.PAGE

; SETHI
;+
; ** SETHI - SETHI ULLMAN ALGORITHM
;
; THIS ROUTINE WALKS THROUGH A TREE, EVALUATING THE COST OF COMPUTING
; THE NODE (IN REGISTERS) AND SAVING THE RESULT IN THE HGPR FIELD  OF
; THE NODE. FLOATING POINT COSTS ARE NOT SET UP BECAUSE ALL  FLOATING
; POINT TREES HAVE A KIND OF ANY IN THE NON EIS COMPILER.
;
; THE ALGORITHM IS A CLASSICAL SETHI-ULLMAN WITH A FEW SPECIAL  TESTS
; FOR ',', ':', AND OTHER 'NO EVALUATE' OPS.
;
; THIS ROUTINE ALSO SWOPS COMMUTATIVE OPERATORS WHEN IT IS DESIREABLE
; TO DO SO.
;
; INPUTS:
;	R5=TREE
;
; OUTPUTS:
;	R5=TREE (WITH COSTS ALL SET UP)
;
; USES:
;	R0
;-

SETHI:	MOV	R1,-(SP)	;SAVE REGISTERS
	MOV	R2,-(SP)	;
	MOV	R3,-(SP)	;
	MOV	R4,-(SP)	;
	MOV	R5,-(SP)	;

	MOV	(R5),R4		;OP
	MOV	R4,R3		;OPDOPE
	ASL	R3		;
	MOV	OPDOPE(R3),R3	;

	MOV	#1,E.HFPR(R5)	;ALL NODES USE AC0		;u3
	MOV	#1,E.HGPR(R5)	;AND R0				;u4
	BIT	#LEAF,R3	;DONE IF LEAF.
	BEQ	10$		;				;u5
	JMP	130$		;EXIT				;u5

10$:	MOV	E.LOP(R5),R1	;DO LEFT.			;u5
	MOV	R1,R5		;
	CALL	SETHI		;
	MOV	(SP),R5		;

;
; UNARY.
; NT = NL UNLESS INT TO LONG, WHEN NT = NL+1
;

	MOV	E.ROP(R5),R2	;IS THERE A RIGHT OP ?
	BNE	30$		;BINARY.
	MOV	E.HFPR(R1),E.HFPR(R5) ;COPY FP REGS		;u1
	MOV	E.HGPR(R1),E.HGPR(R5) ;SET GP REGS
	CMPB	E.TYPE(R5),#TY.LNG ;IN CASE OF CONVERSIONS
	BNE	120$		;				;u5
	CMPB	E.TYPE(R1),#TY.LNG ;
	BEQ	120$		;				;u5
	INC	E.HGPR(R5)	;FIX GP COST
	BR	120$		;CHAIN				;u5

;
; BINARY.
; IF NL != NR, NT = MAX(NL, NR);
; IF NL == NR, NT = NL+1 UNLESS OP IS COMMA, COLON OR ASSIGNMENT.
;

30$:	MOV	R2,R5		;DO RIGHT.
	CALL	SETHI		;
	MOV	(SP),R5		;

; First do it for floating point regs				;u1+
;
	MOV	E.HFPR(R1),R0	;NL
	CMP	R0,E.HFPR(R2)	;NL :: NR
	BHIS	40$		; SKIP IF NL > NR
	MOV	E.HFPR(R2),R0	;NL
40$:	MOV	R0,E.HFPR(R5)	;NT = MAX( NL, NR )

; Now compute max for general regs
;
	MOV	E.HGPR(R1),R0	;NL
	CMP	R0,E.HGPR(R2)	;NL :: NR
	BHIS	50$		; SKIP IF NL > NR
	MOV	E.HGPR(R2),R0	;NL
50$:	MOV	R0,E.HGPR(R5)	;NT = MAX( NL, NR )

	CMPB	E.TYPE(R5),#TY.FLT	;IS THIS A FLOATING OP ?
	BHIS	70$		;SKIP IF SO

; Non-floating, fix up general regs
;
	CMP	E.HGPR(R1),E.HGPR(R2)	;NL == NR ?
	BNE	60$		; SKIP IF NOT
	BIT	#NOP1,R3	;NEED NL+1 ?
	BNE	60$		;NO.
	INC	E.HGPR(R5)	;FIX GP COST
60$:	CALL	NTWO		;SEE IF 2 REGISTERS ARE NEEDED
	BCS	120$		;NO
	INC	E.HGPR(R5)	;FIX COST
	BR	120$		; CONTINUE

; Floating, fix up FP regs
;
70$:	CMP	E.HFPR(R1),E.HFPR(R2)	;NL == NR ?
	BNE	60$		; SKIP IF NOT
	BIT	#NOP1,R3	;NEED NL+1 ?
	BNE	60$		;NO.
	INC	E.HFPR(R5)	;FIX FP COST			;u1-

;
; SPECIAL FOR CALL.
; A CALL USES ALL OF THE FLOATING POINT
; REGISTERS, AND R0-R1. HOWEVER, IT MAY USE
; MORE IF EITHER THE ARGLIST OR THE NAME
; IS HARD.
;

120$:	CMP	(R5),#OP.JSR	;IS THIS A CALL?
	BNE	125$		;NO
	MOV	#99.,E.HFPR(R5)	;MAKE FP COST VERY LARGE
	CMP	E.HGPR(R5),#2	;AND GUARANTEE THE		;u3
	BHIS	125$		;MINIMUM
	MOV	#2,E.HGPR(R5)	;CALL COST (subr can use r0-r1)	;u3

125$:	TST	E.ROP(R5)	;IS THERE A RIGHT OP ?		;u4
	BEQ	130$		;EXIT IF UNARY			;u4
;
; IF OP IS COMMUTATIVE, SEE IF SWOP IS
; A GOOD DEAL.
;
	BIT	#COMMUT,R3	;IS THE OPERATION COMMUTATIVE?	;u4
	BEQ	130$		;NO, DONE
	MOV	R1,R0		;CLASSIFY ROP			;u7
	MOV	R2,R1		;CLASSIFY ROP
	CALL	CLASFY		;
	MOV	R0,-(SP)	;
	MOV	R1,R0		;CLASSIFY LOP			;u7
	MOV	E.LOP(R5),R1	;CLASSIFY LOP			;u7
	CALL	CLASFY		;
	CMP	R0,(SP)+	;LEFT :: RIGHT
	BHIS	130$		;BR IF THE WAY IT SHOULD BE
	MOV	E.ROP(R5),E.LOP(R5) ;SWOP			;u7
	MOV	R1,E.ROP(R5)	;SWOP
	BIT	#RELOP,R3	;MAY ALSO HAVE TO ADJUST RELATION
	BEQ	130$		;
	SUB	#OP.EQ,R4	;
	ASL	R4		;
	MOV	FLIP(R4),(R5)	;

130$:	MOV	(SP)+,R5	;RETURN
	MOV	(SP)+,R4	;
	MOV	(SP)+,R3	;
	MOV	(SP)+,R2	;
	MOV	(SP)+,R1	;
	RETURN			;

; NTWO
;+
; ** NTWO  - TWO REGISTER TEST					;u1+
;
; THESE ROUTINES LOOK FOR TREES THAT REQUIRE A PAIR OF REGISTERS.
;
; DIV/MOD GET AN EVEN/ODD PAIR
; ALL LONGS GET AN EVEN/ODD PAIR
;
; INPUTS:
;	R5=TREE
;
; OUTPUTS:
;	C=0 IF PAIR REQUIRED
;
; All pairs are now allocated as even/odd by GETREG.  To simplify things,
; all odd requests are simply given even/odd pairs.  See comments at
; GETREG for register allocation scheme.


NTWO:
	MOV	R0,-(SP)	;SAVE REGISTERS

	CMPB	E.TYPE(R5),#TY.LNG	;CHECK TYPE
	BEQ	NTWYES		;ALL LONGS NEED TWO
	BHI	NTWNO		;FLOATS NEVER DO

	MOV	(R5),R0		;TEST OPDOPE FOR 'NEED A PAIR'
	ASL	R0		;
	BIT	#PAIR!ODD,OPDOPE(R0); Odd requires pair for safety	;u4
	BEQ	NTWNO		;PAIR NOT REQUIRED

NTWYES:	CLC			;NEED A PAIR
	BR	NTWRET		;

NTWNO:	SEC			;DON'T NEED A PAIR
NTWRET:	MOV	(SP)+,R0	;
	RETURN			;				;u1-

; OPDOPE
;+
; PASS 2 OPDOPE TABLE
;
; 000001		LEAF
; 000002		BINARY OP (RELIC, UNUSED)
; 000004		COMMUTATIVE OPERATOR
; 000010		RELATIONAL OPERATOR
; 000020		INT OPS REQUIRE REGISTER PAIR
; 000040		ODD REGISTER (NOT USED IN NON EIS COMPILER)
; 000100		MODIFY DELETES CONSTANT ZEROS ON LEFT
; 000200		MODIFY DELETES CONSTANT ZEROS ON RIGHT
; 000400		INT OP SETS CVNZ OK
; 001000		INT OP SETS NZ OK
; 002000		NL == NR => NT = NL; NOT NT = NL+1
; 004000		OP RETURNS 0/1 (LOGICAL OP'S)
;-

LEAF	==	000001
BINOP	==	000002
COMMUT	==	000004
RELOP	==	000010
PAIR	==	000020
ODD	==	000040
DZOL	==	000100
DZOR	==	000200
OKCC	==	000400
OKNZ	==	001000
NOP1	==	002000
L01	==	004000						;04
NOETAB	==	010000	;If can't be used in ETAB after CTAB.	;05+
			;The problem comes with constructions
			;such as "while ((n /= 2) > 0)" in which
			;the operation sets the condition codes
			;incorrectly.  Honest, it does.		;05-

OPDOPE:	.WORD	000000		;OP.EOF

	.WORD	001001		;OP.CON
	.WORD	001001		;OP.ID
	.WORD	001001		;OP.LID
	.WORD	000001		;OP.LCN (NOT SEEN)
	.WORD	000001		;OP.DCN (NOT SEEN)
	.WORD	001001		;OP.REG
	.WORD	001001		;OP.INX
	.WORD	001001		;OP.AUI
	.WORD	001001		;OP.AUD

	.WORD	001706		;OP.ADD
	.WORD	001602		;OP.SUB
	.WORD	000046		;OP.MUL		;ODD
	.WORD	000022		;OP.DIV		;PAIR			;07
	.WORD	000022		;OP.MOD		;PAIR			;07
	.WORD	000202		;OP.ASL
	.WORD	000202		;OP.ASR
	.WORD	000006		;OP.AND
	.WORD	001306		;OP.OR
	.WORD	001306		;OP.XOR					;03

	.WORD	003602		;OP.ADA
	.WORD	003602		;OP.SBA
	.WORD	013042		;OP.MUA		;ODD			;05
	.WORD	013022		;OP.DVA		;PAIR			;07/05
	.WORD	013022		;OP.MOA		;PAIR			;07/05
	.WORD	003202		;OP.ALA
	.WORD	003202		;OP.ARA
	.WORD	002002		;OP.ANA
	.WORD	003202		;OP.ORA
	.WORD	003202		;OP.XRA

	.WORD	005416		;OP.EQ
	.WORD	005416		;OP.NE
	.WORD	005416		;OP.LT
	.WORD	005416		;OP.LE
	.WORD	005416		;OP.GE
	.WORD	005416		;OP.GT
	.WORD	005416		;OP.LTU
	.WORD	005416		;OP.LEU
	.WORD	005416		;OP.GEU
	.WORD	005416		;OP.GTU

	.WORD	004002		;OP.AA
	.WORD	004002		;OP.OO
	.WORD	001000		;OP.INB
	.WORD	010000		;OP.INA	;Not in ETAB after CTAB		;05
	.WORD	001000		;OP.DEB
	.WORD	010000		;OP.DEA	;Not in ETAB after CTAB		;05
	.WORD	003002		;OP.ASG

	.WORD	001000		;OP.ADR
	.WORD	001000		;OP.IND
	.WORD	001400		;OP.NEG
	.WORD	001000		;OP.COM
	.WORD	004000		;OP.NOT

	.WORD	000002		;OP.QRY
	.WORD	002002		;OP.CLN
	.WORD	002002		;OP.CMA
	.WORD	002002		;OP.SEQ
	.WORD	001302		;OP.BIC
	.WORD	003202		;OP.BCA
	.WORD	001006		;OP.BIT
	.WORD	000002		;OP.JSR
	.WORD	000002		;OP.CVR
	.WORD	000026		;OP.MLL				;u6
	.WORD	000002		;OP.FSR
	.WORD	000002		;OP.FSM
	.WORD	001000		;OP.LOD
	.WORD	000001		;OP.CST
	.WORD	000022		;OP.DLL (OP.NAC in pass 1)	;u6

	.WORD	000000		;OP.SEM
	.WORD	000000		;OP.DOT
	.WORD	000000		;OP.ARO
	.WORD	000000		;OP.LPA
	.WORD	000000		;OP.RPA
	.WORD	000000		;OP.LSQ
	.WORD	000000		;OP.RSQ
	.WORD	000000		;OP.LBR
	.WORD	000000		;OP.RBR

	.WORD	000001		;OP.FCN (NOT SEEN)		;u2
	.WORD	000000		;OP.115

	.WORD	000000		;OP.INT
	.WORD	000000		;OP.CHR
	.WORD	000000		;OP.FLT
	.WORD	000000		;OP.DBL
	.WORD	000000		;OP.UNS
	.WORD	000000		;OP.LNG
	.WORD	000000		;OP.STR
	.WORD	000000		;OP.AUT
	.WORD	000000		;OP.STA
	.WORD	000000		;OP.EXT
	.WORD	000000		;OP.GOT
	.WORD	000000		;OP.RET
	.WORD	000000		;OP.IF
	.WORD	000000		;OP.WHI
	.WORD	000000		;OP.ELS
	.WORD	000000		;OP.SWI
	.WORD	000000		;OP.CAS
	.WORD	000000		;OP.BRK
	.WORD	000000		;OP.CTN
	.WORD	000000		;OP.DO
	.WORD	000000		;OP.DEF
	.WORD	000000		;OP.FOR
	.WORD	000000		;OP.TYP

	.END