// Derived from Inferno utils/6c/peep.c
// http://code.google.com/p/inferno-os/source/browse/utils/6c/peep.c
//
//	Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
//	Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
//	Portions Copyright © 1997-1999 Vita Nuova Limited
//	Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
//	Portions Copyright © 2004,2006 Bruce Ellis
//	Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
//	Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
//	Portions Copyright © 2009 The Go Authors.  All rights reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

#include <u.h>
#include <libc.h>
#include "gg.h"
#include "opt.h"

static void	conprop(Flow *r);
static void	elimshortmov(Graph *g);
static int	prevl(Flow *r, int reg);
static void	pushback(Flow *r);
static int	regconsttyp(Adr*);
static int	subprop(Flow*);
static int	copyprop(Graph*, Flow*);
static int	copy1(Adr*, Adr*, Flow*, int);
static int	copyas(Adr*, Adr*);
static int	copyau(Adr*, Adr*);
static int	copysub(Adr*, Adr*, Adr*, int);

static uint32	gactive;

// do we need the carry bit
static int
needc(Prog *p)
{
	ProgInfo info;

	while(p != P) {
		proginfo(&info, p);
		if(info.flags & UseCarry)
			return 1;
		if(info.flags & (SetCarry|KillCarry))
			return 0;
		p = p->link;
	}
	return 0;
}

static Flow*
rnops(Flow *r)
{
	Prog *p;
	Flow *r1;

	if(r != nil)
	for(;;) {
		p = r->prog;
		if(p->as != ANOP || p->from.type != D_NONE || p->to.type != D_NONE)
			break;
		r1 = uniqs(r);
		if(r1 == nil)
			break;
		r = r1;
	}
	return r;
}

void
peep(Prog *firstp)
{
	Flow *r, *r1;
	Graph *g;
	Prog *p, *p1;
	int t;

	g = flowstart(firstp, sizeof(Flow));
	if(g == nil)
		return;
	gactive = 0;

	// byte, word arithmetic elimination.
	elimshortmov(g);

	// constant propagation
	// find MOV $con,R followed by
	// another MOV $con,R without
	// setting R in the interim
	for(r=g->start; r!=nil; r=r->link) {
		p = r->prog;
		switch(p->as) {
		case ALEAL:
		case ALEAQ:
			if(regtyp(&p->to))
			if(p->from.sym != nil)
			if(p->from.index == D_NONE || p->from.index == D_CONST)
				conprop(r);
			break;

		case AMOVB:
		case AMOVW:
		case AMOVL:
		case AMOVQ:
		case AMOVSS:
		case AMOVSD:
			if(regtyp(&p->to))
			if(p->from.type == D_CONST)
				conprop(r);
			break;
		}
	}

loop1:
	if(debug['P'] && debug['v'])
		dumpit("loop1", g->start, 0);

	t = 0;
	for(r=g->start; r!=nil; r=r->link) {
		p = r->prog;
		switch(p->as) {
		case AMOVL:
		case AMOVQ:
		case AMOVSS:
		case AMOVSD:
			if(regtyp(&p->to))
			if(regtyp(&p->from)) {
				if(copyprop(g, r)) {
					excise(r);
					t++;
				} else
				if(subprop(r) && copyprop(g, r)) {
					excise(r);
					t++;
				}
			}
			break;

		case AMOVBLZX:
		case AMOVWLZX:
		case AMOVBLSX:
		case AMOVWLSX:
			if(regtyp(&p->to)) {
				r1 = rnops(uniqs(r));
				if(r1 != nil) {
					p1 = r1->prog;
					if(p->as == p1->as && p->to.type == p1->from.type){
						p1->as = AMOVL;
						t++;
					}
				}
			}
			break;

		case AMOVBQSX:
		case AMOVBQZX:
		case AMOVWQSX:
		case AMOVWQZX:
		case AMOVLQSX:
		case AMOVLQZX:
		case AMOVQL:
			if(regtyp(&p->to)) {
				r1 = rnops(uniqs(r));
				if(r1 != nil) {
					p1 = r1->prog;
					if(p->as == p1->as && p->to.type == p1->from.type){
						p1->as = AMOVQ;
						t++;
					}
				}
			}
			break;

		case AADDL:
		case AADDQ:
		case AADDW:
			if(p->from.type != D_CONST || needc(p->link))
				break;
			if(p->from.offset == -1){
				if(p->as == AADDQ)
					p->as = ADECQ;
				else
				if(p->as == AADDL)
					p->as = ADECL;
				else
					p->as = ADECW;
				p->from = zprog.from;
				break;
			}
			if(p->from.offset == 1){
				if(p->as == AADDQ)
					p->as = AINCQ;
				else if(p->as == AADDL)
					p->as = AINCL;
				else
					p->as = AINCW;
				p->from = zprog.from;
				break;
			}
			break;

		case ASUBL:
		case ASUBQ:
		case ASUBW:
			if(p->from.type != D_CONST || needc(p->link))
				break;
			if(p->from.offset == -1) {
				if(p->as == ASUBQ)
					p->as = AINCQ;
				else
				if(p->as == ASUBL)
					p->as = AINCL;
				else
					p->as = AINCW;
				p->from = zprog.from;
				break;
			}
			if(p->from.offset == 1){
				if(p->as == ASUBQ)
					p->as = ADECQ;
				else
				if(p->as == ASUBL)
					p->as = ADECL;
				else
					p->as = ADECW;
				p->from = zprog.from;
				break;
			}
			break;
		}
	}
	if(t)
		goto loop1;

	// MOVLQZX removal.
	// The MOVLQZX exists to avoid being confused for a
	// MOVL that is just copying 32-bit data around during
	// copyprop.  Now that copyprop is done, remov MOVLQZX R1, R2
	// if it is dominated by an earlier ADDL/MOVL/etc into R1 that
	// will have already cleared the high bits.
	//
	// MOVSD removal.
	// We never use packed registers, so a MOVSD between registers
	// can be replaced by MOVAPD, which moves the pair of float64s
	// instead of just the lower one.  We only use the lower one, but
	// the processor can do better if we do moves using both.
	for(r=g->start; r!=nil; r=r->link) {
		p = r->prog;
		if(p->as == AMOVLQZX)
		if(regtyp(&p->from))
		if(p->from.type == p->to.type)
		if(prevl(r, p->from.type))
			excise(r);
		
		if(p->as == AMOVSD)
		if(regtyp(&p->from))
		if(regtyp(&p->to))
			p->as = AMOVAPD;
	}

	// load pipelining
	// push any load from memory as early as possible
	// to give it time to complete before use.
	for(r=g->start; r!=nil; r=r->link) {
		p = r->prog;
		switch(p->as) {
		case AMOVB:
		case AMOVW:
		case AMOVL:
		case AMOVQ:
		case AMOVLQZX:
			if(regtyp(&p->to) && !regconsttyp(&p->from))
				pushback(r);
		}
	}
	
	flowend(g);
}

static void
pushback(Flow *r0)
{
	Flow *r, *b;
	Prog *p0, *p, t;
	
	b = nil;
	p0 = r0->prog;
	for(r=uniqp(r0); r!=nil && uniqs(r)!=nil; r=uniqp(r)) {
		p = r->prog;
		if(p->as != ANOP) {
			if(!regconsttyp(&p->from) || !regtyp(&p->to))
				break;
			if(copyu(p, &p0->to, nil) || copyu(p0, &p->to, nil))
				break;
		}
		if(p->as == ACALL)
			break;
		b = r;
	}
	
	if(b == nil) {
		if(debug['v']) {
			print("no pushback: %P\n", r0->prog);
			if(r)
				print("\t%P [%d]\n", r->prog, uniqs(r)!=nil);
		}
		return;
	}

	if(debug['v']) {
		print("pushback\n");
		for(r=b;; r=r->link) {
			print("\t%P\n", r->prog);
			if(r == r0)
				break;
		}
	}

	t = *r0->prog;
	for(r=uniqp(r0);; r=uniqp(r)) {
		p0 = r->link->prog;
		p = r->prog;
		p0->as = p->as;
		p0->lineno = p->lineno;
		p0->from = p->from;
		p0->to = p->to;

		if(r == b)
			break;
	}
	p0 = r->prog;
	p0->as = t.as;
	p0->lineno = t.lineno;
	p0->from = t.from;
	p0->to = t.to;

	if(debug['v']) {
		print("\tafter\n");
		for(r=b;; r=r->link) {
			print("\t%P\n", r->prog);
			if(r == r0)
				break;
		}
	}
}

void
excise(Flow *r)
{
	Prog *p;

	p = r->prog;
	if(debug['P'] && debug['v'])
		print("%P ===delete===\n", p);

	p->as = ANOP;
	p->from = zprog.from;
	p->to = zprog.to;

	ostats.ndelmov++;
}

int
regtyp(Adr *a)
{
	int t;

	t = a->type;
	if(t >= D_AX && t <= D_R15)
		return 1;
	if(t >= D_X0 && t <= D_X0+15)
		return 1;
	return 0;
}

// movb elimination.
// movb is simulated by the linker
// when a register other than ax, bx, cx, dx
// is used, so rewrite to other instructions
// when possible.  a movb into a register
// can smash the entire 32-bit register without
// causing any trouble.
//
// TODO: Using the Q forms here instead of the L forms
// seems unnecessary, and it makes the instructions longer.
static void
elimshortmov(Graph *g)
{
	Prog *p;
	Flow *r;

	for(r=g->start; r!=nil; r=r->link) {
		p = r->prog;
		if(regtyp(&p->to)) {
			switch(p->as) {
			case AINCB:
			case AINCW:
				p->as = AINCQ;
				break;
			case ADECB:
			case ADECW:
				p->as = ADECQ;
				break;
			case ANEGB:
			case ANEGW:
				p->as = ANEGQ;
				break;
			case ANOTB:
			case ANOTW:
				p->as = ANOTQ;
				break;
			}
			if(regtyp(&p->from) || p->from.type == D_CONST) {
				// move or artihmetic into partial register.
				// from another register or constant can be movl.
				// we don't switch to 64-bit arithmetic if it can
				// change how the carry bit is set (and the carry bit is needed).
				switch(p->as) {
				case AMOVB:
				case AMOVW:
					p->as = AMOVQ;
					break;
				case AADDB:
				case AADDW:
					if(!needc(p->link))
						p->as = AADDQ;
					break;
				case ASUBB:
				case ASUBW:
					if(!needc(p->link))
						p->as = ASUBQ;
					break;
				case AMULB:
				case AMULW:
					p->as = AMULQ;
					break;
				case AIMULB:
				case AIMULW:
					p->as = AIMULQ;
					break;
				case AANDB:
				case AANDW:
					p->as = AANDQ;
					break;
				case AORB:
				case AORW:
					p->as = AORQ;
					break;
				case AXORB:
				case AXORW:
					p->as = AXORQ;
					break;
				case ASHLB:
				case ASHLW:
					p->as = ASHLQ;
					break;
				}
			} else if(p->from.type >= D_NONE) {
				// explicit zero extension, but don't
				// do that if source is a byte register
				// (only AH can occur and it's forbidden).
				switch(p->as) {
				case AMOVB:
					p->as = AMOVBQZX;
					break;
				case AMOVW:
					p->as = AMOVWQZX;
					break;
				}
			}
		}
	}
}

// is 'a' a register or constant?
static int
regconsttyp(Adr *a)
{
	if(regtyp(a))
		return 1;
	switch(a->type) {
	case D_CONST:
	case D_FCONST:
	case D_SCONST:
	case D_ADDR:
		return 1;
	}
	return 0;
}

// is reg guaranteed to be truncated by a previous L instruction?
static int
prevl(Flow *r0, int reg)
{
	Prog *p;
	Flow *r;
	ProgInfo info;

	for(r=uniqp(r0); r!=nil; r=uniqp(r)) {
		p = r->prog;
		if(p->to.type == reg) {
			proginfo(&info, p);
			if(info.flags & RightWrite) {
				if(info.flags & SizeL)
					return 1;
				return 0;
			}
		}
	}
	return 0;
}

/*
 * the idea is to substitute
 * one register for another
 * from one MOV to another
 *	MOV	a, R0
 *	ADD	b, R0	/ no use of R1
 *	MOV	R0, R1
 * would be converted to
 *	MOV	a, R1
 *	ADD	b, R1
 *	MOV	R1, R0
 * hopefully, then the former or latter MOV
 * will be eliminated by copy propagation.
 */
static int
subprop(Flow *r0)
{
	Prog *p;
	ProgInfo info;
	Adr *v1, *v2;
	Flow *r;
	int t;

	if(debug['P'] && debug['v'])
		print("subprop %P\n", r0->prog);
	p = r0->prog;
	v1 = &p->from;
	if(!regtyp(v1)) {
		if(debug['P'] && debug['v'])
			print("\tnot regtype %D; return 0\n", v1);
		return 0;
	}
	v2 = &p->to;
	if(!regtyp(v2)) {
		if(debug['P'] && debug['v'])
			print("\tnot regtype %D; return 0\n", v2);
		return 0;
	}
	for(r=uniqp(r0); r!=nil; r=uniqp(r)) {
		if(debug['P'] && debug['v'])
			print("\t? %P\n", r->prog);
		if(uniqs(r) == nil) {
			if(debug['P'] && debug['v'])
				print("\tno unique successor\n");
			break;
		}
		p = r->prog;
		if(p->as == AVARDEF || p->as == AVARKILL)
			continue;
		proginfo(&info, p);
		if(info.flags & Call) {
			if(debug['P'] && debug['v'])
				print("\tfound %P; return 0\n", p);
			return 0;
		}

		if(info.reguse | info.regset) {
			if(debug['P'] && debug['v'])
				print("\tfound %P; return 0\n", p);
			return 0;
		}

		if((info.flags & Move) && (info.flags & (SizeL|SizeQ|SizeF|SizeD)) && p->to.type == v1->type)
			goto gotit;

		if(copyau(&p->from, v2) ||
		   copyau(&p->to, v2)) {
		   	if(debug['P'] && debug['v'])
		   		print("\tcopyau %D failed\n", v2);
			break;
		}
		if(copysub(&p->from, v1, v2, 0) ||
		   copysub(&p->to, v1, v2, 0)) {
		   	if(debug['P'] && debug['v'])
		   		print("\tcopysub failed\n");
			break;
		}
	}
	if(debug['P'] && debug['v'])
		print("\tran off end; return 0\n");
	return 0;

gotit:
	copysub(&p->to, v1, v2, 1);
	if(debug['P']) {
		print("gotit: %D->%D\n%P", v1, v2, r->prog);
		if(p->from.type == v2->type)
			print(" excise");
		print("\n");
	}
	for(r=uniqs(r); r!=r0; r=uniqs(r)) {
		p = r->prog;
		copysub(&p->from, v1, v2, 1);
		copysub(&p->to, v1, v2, 1);
		if(debug['P'])
			print("%P\n", r->prog);
	}
	t = v1->type;
	v1->type = v2->type;
	v2->type = t;
	if(debug['P'])
		print("%P last\n", r->prog);
	return 1;
}

/*
 * The idea is to remove redundant copies.
 *	v1->v2	F=0
 *	(use v2	s/v2/v1/)*
 *	set v1	F=1
 *	use v2	return fail
 *	-----------------
 *	v1->v2	F=0
 *	(use v2	s/v2/v1/)*
 *	set v1	F=1
 *	set v2	return success
 */
static int
copyprop(Graph *g, Flow *r0)
{
	Prog *p;
	Adr *v1, *v2;

	USED(g);
	if(debug['P'] && debug['v'])
		print("copyprop %P\n", r0->prog);
	p = r0->prog;
	v1 = &p->from;
	v2 = &p->to;
	if(copyas(v1, v2))
		return 1;
	gactive++;
	return copy1(v1, v2, r0->s1, 0);
}

static int
copy1(Adr *v1, Adr *v2, Flow *r, int f)
{
	int t;
	Prog *p;

	if(r->active == gactive) {
		if(debug['P'])
			print("act set; return 1\n");
		return 1;
	}
	r->active = gactive;
	if(debug['P'])
		print("copy %D->%D f=%d\n", v1, v2, f);
	for(; r != nil; r = r->s1) {
		p = r->prog;
		if(debug['P'])
			print("%P", p);
		if(!f && uniqp(r) == nil) {
			f = 1;
			if(debug['P'])
				print("; merge; f=%d", f);
		}
		t = copyu(p, v2, nil);
		switch(t) {
		case 2:	/* rar, can't split */
			if(debug['P'])
				print("; %D rar; return 0\n", v2);
			return 0;

		case 3:	/* set */
			if(debug['P'])
				print("; %D set; return 1\n", v2);
			return 1;

		case 1:	/* used, substitute */
		case 4:	/* use and set */
			if(f) {
				if(!debug['P'])
					return 0;
				if(t == 4)
					print("; %D used+set and f=%d; return 0\n", v2, f);
				else
					print("; %D used and f=%d; return 0\n", v2, f);
				return 0;
			}
			if(copyu(p, v2, v1)) {
				if(debug['P'])
					print("; sub fail; return 0\n");
				return 0;
			}
			if(debug['P'])
				print("; sub %D/%D", v2, v1);
			if(t == 4) {
				if(debug['P'])
					print("; %D used+set; return 1\n", v2);
				return 1;
			}
			break;
		}
		if(!f) {
			t = copyu(p, v1, nil);
			if(!f && (t == 2 || t == 3 || t == 4)) {
				f = 1;
				if(debug['P'])
					print("; %D set and !f; f=%d", v1, f);
			}
		}
		if(debug['P'])
			print("\n");
		if(r->s2)
			if(!copy1(v1, v2, r->s2, f))
				return 0;
	}
	return 1;
}

/*
 * return
 * 1 if v only used (and substitute),
 * 2 if read-alter-rewrite
 * 3 if set
 * 4 if set and used
 * 0 otherwise (not touched)
 */
int
copyu(Prog *p, Adr *v, Adr *s)
{
	ProgInfo info;

	switch(p->as) {
	case AJMP:
		if(s != nil) {
			if(copysub(&p->to, v, s, 1))
				return 1;
			return 0;
		}
		if(copyau(&p->to, v))
			return 1;
		return 0;

	case ARET:
		if(s != nil)
			return 1;
		return 3;

	case ACALL:
		if(REGEXT && v->type <= REGEXT && v->type > exregoffset)
			return 2;
		if(REGARG >= 0 && v->type == (uchar)REGARG)
			return 2;
		if(v->type == p->from.type)
			return 2;

		if(s != nil) {
			if(copysub(&p->to, v, s, 1))
				return 1;
			return 0;
		}
		if(copyau(&p->to, v))
			return 4;
		return 3;

	case ATEXT:
		if(REGARG >= 0 && v->type == (uchar)REGARG)
			return 3;
		return 0;
	}

	if(p->as == AVARDEF || p->as == AVARKILL)
		return 0;
	proginfo(&info, p);

	if((info.reguse|info.regset) & RtoB(v->type))
		return 2;
		
	if(info.flags & LeftAddr)
		if(copyas(&p->from, v))
			return 2;

	if((info.flags & (RightRead|RightWrite)) == (RightRead|RightWrite))
		if(copyas(&p->to, v))
			return 2;
	
	if(info.flags & RightWrite) {
		if(copyas(&p->to, v)) {
			if(s != nil)
				return copysub(&p->from, v, s, 1);
			if(copyau(&p->from, v))
				return 4;
			return 3;
		}
	}
	
	if(info.flags & (LeftAddr|LeftRead|LeftWrite|RightAddr|RightRead|RightWrite)) {
		if(s != nil) {
			if(copysub(&p->from, v, s, 1))
				return 1;
			return copysub(&p->to, v, s, 1);
		}
		if(copyau(&p->from, v))
			return 1;
		if(copyau(&p->to, v))
			return 1;
	}

	return 0;
}

/*
 * direct reference,
 * could be set/use depending on
 * semantics
 */
static int
copyas(Adr *a, Adr *v)
{
	if(a->type != v->type)
		return 0;
	if(regtyp(v))
		return 1;
	if(v->type == D_AUTO || v->type == D_PARAM)
		if(v->offset == a->offset)
			return 1;
	return 0;
}

int
sameaddr(Addr *a, Addr *v)
{
	if(a->type != v->type)
		return 0;
	if(regtyp(v))
		return 1;
	if(v->type == D_AUTO || v->type == D_PARAM)
		if(v->offset == a->offset)
			return 1;
	return 0;
}

/*
 * either direct or indirect
 */
static int
copyau(Adr *a, Adr *v)
{

	if(copyas(a, v)) {
		if(debug['P'] && debug['v'])
			print("\tcopyau: copyas returned 1\n");
		return 1;
	}
	if(regtyp(v)) {
		if(a->type-D_INDIR == v->type) {
			if(debug['P'] && debug['v'])
				print("\tcopyau: found indir use - return 1\n");
			return 1;
		}
		if(a->index == v->type) {
			if(debug['P'] && debug['v'])
				print("\tcopyau: found index use - return 1\n");
			return 1;
		}
	}
	return 0;
}

/*
 * substitute s for v in a
 * return failure to substitute
 */
static int
copysub(Adr *a, Adr *v, Adr *s, int f)
{
	int t;

	if(copyas(a, v)) {
		t = s->type;
		if(t >= D_AX && t <= D_R15 || t >= D_X0 && t <= D_X0+15) {
			if(f)
				a->type = t;
		}
		return 0;
	}
	if(regtyp(v)) {
		t = v->type;
		if(a->type == t+D_INDIR) {
			if((s->type == D_BP || s->type == D_R13) && a->index != D_NONE)
				return 1;	/* can't use BP-base with index */
			if(f)
				a->type = s->type+D_INDIR;
//			return 0;
		}
		if(a->index == t) {
			if(f)
				a->index = s->type;
			return 0;
		}
		return 0;
	}
	return 0;
}

static void
conprop(Flow *r0)
{
	Flow *r;
	Prog *p, *p0;
	int t;
	Adr *v0;

	p0 = r0->prog;
	v0 = &p0->to;
	r = r0;

loop:
	r = uniqs(r);
	if(r == nil || r == r0)
		return;
	if(uniqp(r) == nil)
		return;

	p = r->prog;
	t = copyu(p, v0, nil);
	switch(t) {
	case 0:	// miss
	case 1:	// use
		goto loop;

	case 2:	// rar
	case 4:	// use and set
		break;

	case 3:	// set
		if(p->as == p0->as)
		if(p->from.type == p0->from.type)
		if(p->from.node == p0->from.node)
		if(p->from.offset == p0->from.offset)
		if(p->from.scale == p0->from.scale)
		if(p->from.type == D_FCONST && p->from.u.dval == p0->from.u.dval)
		if(p->from.index == p0->from.index) {
			excise(r);
			goto loop;
		}
		break;
	}
}

int
smallindir(Addr *a, Addr *reg)
{
	return regtyp(reg) &&
		a->type == D_INDIR + reg->type &&
		a->index == D_NONE &&
		0 <= a->offset && a->offset < 4096;
}

int
stackaddr(Addr *a)
{
	return regtyp(a) && a->type == D_SP;
}