/*
 * Copyright (C) 1996-1998 by the Board of Trustees
 *    of Leland Stanford Junior University.
 * 
 * This file is part of the SimOS distribution. 
 * See LICENSE file for terms of the license. 
 *
 */


	/*
	 *  mc.h  -  Generic definitions for the MXS compiler
	 *
	 *	Jim Bennett
	 *	1993, 1994
	 */

#include "bitv.h"


struct s_lnks					/* Links in the graph	*/
	{					/* of basic blocks	*/
	struct	s_lnks	*next;
	struct	s_bb	*blk;
	uint	target;				/* Address of block	*/
	};

struct s_plnks					/* Links in the graph	*/
	{					/* of procedures	*/
	struct	s_plnks	*next;
	struct	s_plst	*proc;
	};

struct s_ilnks					/* Links in the graph	*/
	{					/* of dependencies	*/
	struct	s_ilnks	*next;
	struct	s_inst	*inst;
	int	latency;			/* Time till rslt ready	*/
	int	p_lat;				/* Probabilistic latency */
	};

struct s_unabs					/* Unabsorbed latencies	*/
	{
	struct	s_unabs *next;
	int	reg;
	int	latency;
	int	p_lat;
	};

struct s_inst					/* Instruction list	*/
	{
	struct	s_inst	*next;			/* Doubly linked list	*/
	struct	s_inst	*prev;
	int	cadr;				/* Instruction address	*/
	int	op;				/* Opcode		*/
	int	r1, r2, r3;			/* Register operands	*/
	int	imm;				/* Immediate operand	*/
	struct	s_ilnks	*deps;			/* Dependency list	*/
	int	dst_lat;			/* Latency till dest	*/
	int	dst_plat;			/* reg is available.	*/
	int	ready;				/* If ready to go	*/
	int	latency;			/* Overall latency till	*/
	int	p_lat;				/* end of basic block	*/
	float	cost;				/* Cost to schedule	*/
	};

struct s_bb					/* Basic block list	*/
	{
	struct	s_bb	*next;
	uint	addr;				/* Range of basic block	*/
	uint	nextaddr;
	uint	dlyaddr;			/* Address of delay slot */
	int	conditional;			/* If block ends with	*/
						/* conditional branch	*/
	int	cadr;				/* Address after compilation */
	int	old_cadr;
	int	lstcadr;
	int	visited;			/* Flag for graph traversal */

	int	callno;				/* Which call in proc	*/
	struct	s_plst	*callproc;		/* Call target (if any)	*/

	struct	s_inst	*inst;			/* Instruction list	*/
	struct	s_inst	*last_i;		/* Tail pointer for list */
	struct	s_lnks	*succ;			/* Successors in graph	*/
	struct	s_lnks	*pred;			/* Predecessors		*/

	BITVEC	gens;				/* Definitions generated */
	BITVEC	kills;				/* and killed		*/
	BITVEC	rd_in;				/* Reaching definitions	*/
	BITVEC	rd_out;

	BITVEC	uses;				/* Register uses and	*/
	BITVEC	defs;				/* defines		*/
	BITVEC	lv_in;				/* Live variables	*/
	BITVEC	lv_out;

	struct	s_unabs	*unabs;			/* Unabsorbed latency	*/
						/* end of block.	*/
	};

struct	s_lr					/* Live range (of def)	*/
	{
	struct	s_lr	*next;
	struct	s_bb	*blk;
	int	cadr;				/* Addresses in block	*/
	int	lstcadr;
	int	reg;
	int	cadr_def;			/* Flag: true if the	*/
						/* statement at cadr	*/
						/* defines the reg.	*/
	};

struct s_plst					/* Procedure list	*/
	{
	struct	s_plst	*next;
	uint	addr;			/* Range of procedure addresses	*/
	uint	nextaddr;
	int	cadr;			/* Range of compiled addresses	*/
	int	nxtadr;
	struct	s_lnks	*blklst;	/* Basic blocks of procedure	*/
	struct	s_bb	*tailblk;	/* Terminal block of proc.	*/
	struct	s_plnks	*succ;		/* Successors in call graph	*/
	struct	s_plnks	*pred;		/* Predecessors			*/
	int	visited;		/* Flag for graph traversal	*/
	int	cycle;			/* Cycle ID if part of cycle	*/
	int	height;			/* Distance from leaf node	*/
	int	valid;			/* If a valid procedure		*/
	int	ncalls;			/* Number of calls in procedure	*/
	int	ndefs;			/* Dimension of live range tables */
	struct	s_lr	**ranges;	/* Table of live ranges		*/
	int	*fixed_ranges;		/* Un-renamable live ranges	*/
	char	*name;
	};

struct s_bra					/* Branch description	*/
	{
	uint	target;				/* Branch target	*/
	int	delayed;			/* If delay slot	*/
	int	conditional;			/* If conditional br	*/
	int	call;				/* If procedure call	*/
	int	indirect;			/* For indexed branches	*/
	};


	/* Special control opcode, outside normal opcode range	*/
	/* (used only by compiler, never seen by simulator)	*/

#define	CTL_BR	(MAX_OP+1)


	/* OUTSIDE indicates that successor (or predecessor) block is	*/
	/* 		outside the procedure.				*/
	/* UNKNOWN indicates that successor (or predecessor) block	*/
	/*		can't be determined.				*/
	/* COLLISION indicates a collision at that index in the hash	*/
	/*		table.						*/
	/* ALL_PROC indicates that the successor procedure could be	*/
	/*		any procedure.					*/

#define	OUTSIDE		((struct s_bb *)0xffffffff)
#define	UNKNOWN		((struct s_bb *)0xfffffffe)
#define	COLLISION	((struct s_bb *)0xfffffffd)
#define	ALL_PROC	((struct s_plst *)0xffffffff)
#define	SYSC_PROC	((struct s_plst *)0xfffffffd)


	/* Handy macros for decoding CPU instructions, and	*/
	/* accessing the CPU registers				*/

#define	RSRI(i) (((i)>>21)&0x1f)		/* Get register index	*/
#define RTRI(i) (((i)>>16)&0x1f)
#define RDRI(i) (((i)>>11)&0x1f)

/* The XOR of the low order bit is so that the odd numbered	*/
/* single precision register maps to the high order half of	*/
/* the overlaying double precision register.  This is due to	*/
/* the machine that I'm running the simulator on being big	*/
/* endian.  On a little endian machine, it would not be needed.	*/

#ifdef LITTLE_ENDIAN
#define FTRI(i) ((((i)>>16)&0x1f)+FPREG)	/* Get register index	*/
#define FSRI(i) ((((i)>>11)&0x1f)+FPREG)
#define FDRI(i) ((((i)>> 6)&0x1f)+FPREG)

#else
#define FTRI(i) (((((i)>>16)&0x1f)^0x0001)+FPREG)
#define FSRI(i) (((((i)>>11)&0x1f)^0x0001)+FPREG)
#define FDRI(i) (((((i)>> 6)&0x1f)^0x0001)+FPREG)
#endif

#define DTRI(i) ((((i)>>16)&0x1e)+FPREG)
#define DSRI(i) ((((i)>>11)&0x1e)+FPREG)
#define DDRI(i) ((((i)>> 6)&0x1e)+FPREG)

#define SHAMT(i) (((i)>>6)&0x1f)
#define	IMMED(i) (((i)&0x8000)?((i)&0x0000ffff)-0x10000:((i)&0x0000ffff))


	/*  REG_NO  -  Map odd half of floating point register pair to	*/
	/*		an even number.					*/

#define	IS_FPREG(reg)	(((reg) >= FPREG) && ((reg) < MAX_FP))

#define	IS_FPCTL(reg)	(((reg) & (~0x01)) == FPCTL)

#define	REG_NO(reg)	(IS_FPREG(reg) ? (reg) & (~0x01) : (reg))

#define	REG_EQ(r1,r2)	(REG_NO(r1) == REG_NO(r2))


	/*
	 *  External procedure declarations
	 */

extern	struct s_bb *add_bb (struct s_bb *blk, uint target);
extern	struct s_bb *bb_alloc (uint addr);
extern	void bb_free (struct s_bb *blk);
extern	struct s_bb *find_bb (struct s_bb *blk, uint addr);
extern	void delete_bb (struct s_bb *first_blk, struct s_bb *blk);
extern	void add_succ (struct s_bb *blk, struct s_bb *tblk, uint target);
extern	void add_pred (struct s_bb *blk, struct s_bb *tblk);
extern	struct s_lnks *add_link (struct s_lnks *lnk, struct s_bb *blk);
extern	struct s_lnks *merge_lnks (struct s_lnks *ll1, struct s_lnks *ll2);
extern	struct s_lnks *lnk_alloc (void);
extern	void lnk_free (struct s_lnks *lnk);
extern	void free_lnks (struct s_lnks *lnk);

extern	void add_bb_hash (struct s_bb *blk, uint addr);
extern	struct s_bb *addr_to_bb (uint addr);
extern	void add_synonym (uint addr, int cadr);
#ifndef MIPSY_MXS
extern	void write_bb_hash (FILE *pof, struct ms_header *hdr);
#endif

extern	void unvisit_bb_graph (struct s_lnks *blklst);
extern	void visit_bb_graph (struct s_lnks *roots, int depth,
			void (*func)(int depth, struct s_bb *blk));
extern	void print_bb_node (int depth, struct s_bb *blk);

extern	int mc_proc (char *tbuf, uint tbase, struct s_bb *blk,
				INST *ctbuf, int taken, int ninst);
extern	INST *bb_pass (FILE *bbfile, char *tbuf, uint tbase, uint tmax,
			struct s_plst *proclist, int *p_ninst, int *p_room);
extern	int callg_pass (struct s_plst *proclist, INST *ctbuf, int ninst);
extern	struct s_plnks *add_p_link (struct s_plnks *lnk, struct s_plst *proc);
extern	void mc_untangle (struct s_plst *proclist);
extern	int mc_rank_cycles (struct s_plst *proclist);
extern	struct s_plst *cadr_to_proc (struct s_plst *proclist, int cadr);

extern	struct s_bb *proc_entry (struct s_plst *proc);

extern	void dataflow_pass (struct s_plst *proclist, INST *ctbuf, int height);
extern	void rename_vars (struct s_plst *proclist, INST *ctbuf, int max_height);
extern	int schedule_pass (struct s_plst *proclist, INST *ctbuf,
		int ninst, int room, int height, float prob, uint print_block,
		char *print_proc_name);
extern	INST *flatten_cseg (struct s_plst *proclist, INST *ctbuf, int *ninst);

extern	void live_ranges (struct s_plst *proc, INST *ctbuf, int ndefs);
extern	int def_to_reg (struct s_plst *proc, INST *ctbuf, int def);

extern	struct s_plst *addproc (struct s_plst *proclist, uint addr, char *name);

extern	void reschedule (struct s_bb *blk, struct s_unabs *unabsorbed,
						INST *ctbuf, float prob);
extern	struct s_unabs *absorb_latencies (struct s_unabs *unabsorbed,
						struct s_inst *sched);
extern	struct s_unabs *add_unabs (struct s_unabs *unabsorbed,
				int reg, int latency, int p_lat);