/*                            
 * 68K/386 32-bit C compiler.
 *
 * copyright (c) 1996, David Lindauer
 * 
 * This compiler is intended for educational use.  It may not be used
 * for profit without the express written consent of the author.
 *
 * It may be freely redistributed, as long as this notice remains intact
 * and sources are distributed along with any executables derived from them.
 *
 * The author is not responsible for damages, either direct or consequential,
 * that may arise from use of this software.
 *
 * V2.05 June 2002
 * David Lindauer, gclind01@starbase.spd.louisville.edu
 *
 * Credits to Mathew Brandt for original K&R C compiler
 *
 */
/*
 * iflow.c
 *
 * create flow graph and dominator tree
 */
/* Define this to get a dump of the flow graph and dominator tree 
 * These are dumped into ccfg.$$$
 */
#define DEBUG

#include        <stdio.h>
#include				<malloc.h>
#include 				<string.h>
#include				"utype.h"	
#include				"cmdline.h"	
#include        "lists.h"
#include        "expr.h"
#include        "c.h"
#include				"iexpr.h"
#include				"iopt.h"
#include 				"diag.h"

extern BLOCKLIST *blockhead;
extern int blocknum;

BLOCKLIST **blockarray;										 
#ifdef DEBUG
static FILE *ofil;

/* dump the flow graph */
static void  dump_flowgraph(BLOCKLIST *list)
{
	while (list) {
		BLOCKLIST *list1 = list->block->flowfwd;
		fprintf(ofil,"\n%d: ",list->block->blocknum+1);
		while (list1) {
		  fprintf(ofil," %d",list1->block->blocknum+1);
			list1 = list1->link;
		}
		fprintf(ofil," *");
		list1 = list->block->flowback;
		while (list1) {
		  fprintf(ofil," %d",list1->block->blocknum+1);
			list1 = list1->link;
		}
		list = list->link;
	}
}
#endif
/* find a label on the list */
static BLOCKLIST*findlab(int labnum)
{
	BLOCKLIST *head = blockhead->link;
	while (head) {
		QUAD *ihead = head->block->head;
		ihead = ihead->fwd;
		while (ihead && ihead->dc.opcode != i_label) {
			if (ihead->dc.opcode == i_block)
				head = head->link;
			ihead = ihead->fwd;
		}
		if (ihead->dc.label == labnum)
			break;
		head = head->link;
	}
	return head;
}
/* insert on a flowgraph node */
static void flowinsert(BLOCKLIST **pos, BLOCKLIST *value)
{
	BLOCKLIST *nblock = xalloc(sizeof(BLOCKLIST));
	nblock->link = (*pos);
	(*pos) = nblock;
	nblock->block = value->block;
}
/* create the flowgraph */
static void gather_flowgraph(BLOCKLIST *list)
{
	BLOCKLIST *temp;
	int i = 0;
	blockarray = xalloc(blocknum * sizeof(BLOCKLIST **));
	while (list) {
		QUAD *tail = list->block->tail;
		blockarray[i++] = list;
		switch(tail->dc.opcode) {
			case i_goto:
				temp = findlab(tail->dc.label);
				if (temp) {
					flowinsert(&temp->block->flowback,list);
					flowinsert(&list->block->flowfwd,temp);
				}
				else DIAG("flow:unfound label");
				break;
			case i_dc:
				while (tail->dc.opcode == i_dc) {
					temp = findlab(tail->dc.label);
					if (temp) {
						flowinsert(&temp->block->flowback,list);
						flowinsert(&list->block->flowfwd,temp);
					}
					else DIAG("flow:unfound label");
					tail = tail->fwd;
				}
				break;
			case i_coswitch:
				temp = findlab(tail->dc.label);
				if (temp) {
					flowinsert(&temp->block->flowback,list);
					flowinsert(&list->block->flowfwd,temp);
				}
				else DIAG("flow:unfound label");
				break;
			case i_je: case i_jne:
			case i_jl: case i_jc:
			case i_jg: case i_ja:
			case i_jle: case i_jbe:
			case i_jge: case i_jnc:
				temp = findlab(tail->dc.label);
				if (temp) {
					flowinsert(&temp->block->flowback,list);
					flowinsert(&list->block->flowfwd,temp);
				}
				else DIAG("flow:unfound label");
			default:
				temp= list->link;
				if (temp) {
					flowinsert(&temp->block->flowback,list);
					flowinsert(&list->block->flowfwd,temp);
				}
				break;
		}
		list = list->link;
	}
}
/* main routine for creating flowgraph and dominator info */
void flows_and_doms(void)
{
	gather_flowgraph(blockhead);
#ifdef DEBUG
	ofil = fopen("ccfg.$$$","w");
	if (ofil) {
		fprintf(ofil,"Flowgraph dump\n");
		dump_flowgraph(blockhead);
		fclose(ofil);
	}
#endif
}
