xref: /plan9-contrib/sys/src/cmd/ld/pass.c (revision 40d015479ed36701ae6dcfd8814f849fc6285e8d)
1*40d01547SDavid du Colombier #include	"l.h"
2*40d01547SDavid du Colombier 
3*40d01547SDavid du Colombier void
dodata(void)4*40d01547SDavid du Colombier dodata(void)
5*40d01547SDavid du Colombier {
6*40d01547SDavid du Colombier 	int i, t;
7*40d01547SDavid du Colombier 	Sym *s;
8*40d01547SDavid du Colombier 	Prog *p;
9*40d01547SDavid du Colombier 	long orig, v;
10*40d01547SDavid du Colombier 
11*40d01547SDavid du Colombier 	if(debug['v'])
12*40d01547SDavid du Colombier 		Bprint(&bso, "%5.2f dodata\n", cputime());
13*40d01547SDavid du Colombier 	Bflush(&bso);
14*40d01547SDavid du Colombier 	for(p = datap; p != P; p = p->link) {
15*40d01547SDavid du Colombier 		s = p->from.sym;
16*40d01547SDavid du Colombier 		if(p->as == ADYNT || p->as == AINIT)
17*40d01547SDavid du Colombier 			s->value = dtype;
18*40d01547SDavid du Colombier 		if(s->type == SBSS)
19*40d01547SDavid du Colombier 			s->type = SDATA;
20*40d01547SDavid du Colombier 		if(s->type != SDATA)
21*40d01547SDavid du Colombier 			diag("initialize non-data (%d): %s\n%P",
22*40d01547SDavid du Colombier 				s->type, s->name, p);
23*40d01547SDavid du Colombier 		v = p->from.offset + p->reg;
24*40d01547SDavid du Colombier 		if(v > s->value)
25*40d01547SDavid du Colombier 			diag("initialize bounds (%lld): %s\n%P",
26*40d01547SDavid du Colombier 				(vlong)s->value, s->name, p);
27*40d01547SDavid du Colombier 	}
28*40d01547SDavid du Colombier 
29*40d01547SDavid du Colombier 	if(debug['t']) {
30*40d01547SDavid du Colombier 		/*
31*40d01547SDavid du Colombier 		 * pull out string constants
32*40d01547SDavid du Colombier 		 */
33*40d01547SDavid du Colombier 		for(p = datap; p != P; p = p->link) {
34*40d01547SDavid du Colombier 			s = p->from.sym;
35*40d01547SDavid du Colombier 			if(p->to.type == D_SCONST)
36*40d01547SDavid du Colombier 				s->type = SSTRING;
37*40d01547SDavid du Colombier 		}
38*40d01547SDavid du Colombier 	}
39*40d01547SDavid du Colombier 
40*40d01547SDavid du Colombier 	/*
41*40d01547SDavid du Colombier 	 * pass 1
42*40d01547SDavid du Colombier 	 *	assign 'small' variables to data segment
43*40d01547SDavid du Colombier 	 *	(rationale is that data segment is more easily
44*40d01547SDavid du Colombier 	 *	 addressed through offset on REGSB)
45*40d01547SDavid du Colombier 	 */
46*40d01547SDavid du Colombier 	orig = 0;
47*40d01547SDavid du Colombier 	for(i=0; i<NHASH; i++)
48*40d01547SDavid du Colombier 	for(s = hash[i]; s != S; s = s->link) {
49*40d01547SDavid du Colombier 		t = s->type;
50*40d01547SDavid du Colombier 		if(t != SDATA && t != SBSS)
51*40d01547SDavid du Colombier 			continue;
52*40d01547SDavid du Colombier 		v = s->value;
53*40d01547SDavid du Colombier 		if(v == 0) {
54*40d01547SDavid du Colombier 			diag("%s: no size", s->name);
55*40d01547SDavid du Colombier 			v = 1;
56*40d01547SDavid du Colombier 		}
57*40d01547SDavid du Colombier 		v = rnd(v, 4);
58*40d01547SDavid du Colombier 		s->value = v;
59*40d01547SDavid du Colombier 		if(v > MINSIZ)
60*40d01547SDavid du Colombier 			continue;
61*40d01547SDavid du Colombier 		if(v >= 16)
62*40d01547SDavid du Colombier 			orig = rnd(orig, 16);
63*40d01547SDavid du Colombier 		else if(v >= 8)
64*40d01547SDavid du Colombier 			orig = rnd(orig, 8);
65*40d01547SDavid du Colombier 		s->value = orig;
66*40d01547SDavid du Colombier 		orig += v;
67*40d01547SDavid du Colombier 		s->type = SDATA1;
68*40d01547SDavid du Colombier 	}
69*40d01547SDavid du Colombier 
70*40d01547SDavid du Colombier 	/*
71*40d01547SDavid du Colombier 	 * pass 2
72*40d01547SDavid du Colombier 	 *	assign large 'data' variables to data segment
73*40d01547SDavid du Colombier 	 */
74*40d01547SDavid du Colombier 	for(i=0; i<NHASH; i++)
75*40d01547SDavid du Colombier 	for(s = hash[i]; s != S; s = s->link) {
76*40d01547SDavid du Colombier 		t = s->type;
77*40d01547SDavid du Colombier 		if(t != SDATA) {
78*40d01547SDavid du Colombier 			if(t == SDATA1)
79*40d01547SDavid du Colombier 				s->type = SDATA;
80*40d01547SDavid du Colombier 			continue;
81*40d01547SDavid du Colombier 		}
82*40d01547SDavid du Colombier 		v = s->value;
83*40d01547SDavid du Colombier 		if(v >= 16)
84*40d01547SDavid du Colombier 			orig = rnd(orig, 16);
85*40d01547SDavid du Colombier 		else if(v >= 8)
86*40d01547SDavid du Colombier 			orig = rnd(orig, 8);
87*40d01547SDavid du Colombier 		s->value = orig;
88*40d01547SDavid du Colombier 		orig += v;
89*40d01547SDavid du Colombier 	}
90*40d01547SDavid du Colombier 
91*40d01547SDavid du Colombier 	while(orig & 7)
92*40d01547SDavid du Colombier 		orig++;
93*40d01547SDavid du Colombier 	datsize = orig;
94*40d01547SDavid du Colombier 
95*40d01547SDavid du Colombier 	/*
96*40d01547SDavid du Colombier 	 * pass 3
97*40d01547SDavid du Colombier 	 *	everything else to bss segment
98*40d01547SDavid du Colombier 	 */
99*40d01547SDavid du Colombier 	for(i=0; i<NHASH; i++)
100*40d01547SDavid du Colombier 	for(s = hash[i]; s != S; s = s->link) {
101*40d01547SDavid du Colombier 		if(s->type != SBSS)
102*40d01547SDavid du Colombier 			continue;
103*40d01547SDavid du Colombier 		v = s->value;
104*40d01547SDavid du Colombier 		if(v >= 16)
105*40d01547SDavid du Colombier 			orig = rnd(orig, 16);
106*40d01547SDavid du Colombier 		else if(v >= 8)
107*40d01547SDavid du Colombier 			orig = rnd(orig, 8);
108*40d01547SDavid du Colombier 		s->value = orig;
109*40d01547SDavid du Colombier 		orig += v;
110*40d01547SDavid du Colombier 	}
111*40d01547SDavid du Colombier 	while(orig & 7)
112*40d01547SDavid du Colombier 		orig++;
113*40d01547SDavid du Colombier 	bsssize = orig-datsize;
114*40d01547SDavid du Colombier 
115*40d01547SDavid du Colombier 	xdefine("setSB", SDATA, 0L);
116*40d01547SDavid du Colombier 	xdefine("bdata", SDATA, 0L);
117*40d01547SDavid du Colombier 	xdefine("edata", SDATA, datsize);
118*40d01547SDavid du Colombier 	xdefine("end", SBSS, datsize+bsssize);
119*40d01547SDavid du Colombier 	xdefine("etext", STEXT, 0L);
120*40d01547SDavid du Colombier }
121*40d01547SDavid du Colombier 
122*40d01547SDavid du Colombier Prog*
brchain(Prog * p)123*40d01547SDavid du Colombier brchain(Prog *p)
124*40d01547SDavid du Colombier {
125*40d01547SDavid du Colombier 	int i;
126*40d01547SDavid du Colombier 
127*40d01547SDavid du Colombier 	for(i=0; i<20; i++) {
128*40d01547SDavid du Colombier 		if(p == P || !isbranch(p->as))
129*40d01547SDavid du Colombier 			return p;
130*40d01547SDavid du Colombier 		p = p->cond;
131*40d01547SDavid du Colombier 	}
132*40d01547SDavid du Colombier 	return P;
133*40d01547SDavid du Colombier }
134*40d01547SDavid du Colombier 
135*40d01547SDavid du Colombier void
follow(void)136*40d01547SDavid du Colombier follow(void)
137*40d01547SDavid du Colombier {
138*40d01547SDavid du Colombier 	if(debug['v'])
139*40d01547SDavid du Colombier 		Bprint(&bso, "%5.2f follow\n", cputime());
140*40d01547SDavid du Colombier 	Bflush(&bso);
141*40d01547SDavid du Colombier 
142*40d01547SDavid du Colombier 	firstp = prg();
143*40d01547SDavid du Colombier 	lastp = firstp;
144*40d01547SDavid du Colombier 	xfol(textp);
145*40d01547SDavid du Colombier 
146*40d01547SDavid du Colombier 	firstp = firstp->link;
147*40d01547SDavid du Colombier 	lastp->link = P;
148*40d01547SDavid du Colombier }
149*40d01547SDavid du Colombier 
150*40d01547SDavid du Colombier void
xfol(Prog * p)151*40d01547SDavid du Colombier xfol(Prog *p)
152*40d01547SDavid du Colombier {
153*40d01547SDavid du Colombier 	Prog *q, *r;
154*40d01547SDavid du Colombier 	int a, i;
155*40d01547SDavid du Colombier 
156*40d01547SDavid du Colombier loop:
157*40d01547SDavid du Colombier 	if(p == P)
158*40d01547SDavid du Colombier 		return;
159*40d01547SDavid du Colombier 	a = p->as;
160*40d01547SDavid du Colombier 	if(a == ATEXT)
161*40d01547SDavid du Colombier 		curtext = p;
162*40d01547SDavid du Colombier 	if(isbranch(a)) {
163*40d01547SDavid du Colombier 		q = p->cond;
164*40d01547SDavid du Colombier 		if(q != P) {
165*40d01547SDavid du Colombier 			p->mark |= FOLL;
166*40d01547SDavid du Colombier 			p = q;
167*40d01547SDavid du Colombier 			if(!(p->mark & FOLL))
168*40d01547SDavid du Colombier 				goto loop;
169*40d01547SDavid du Colombier 		}
170*40d01547SDavid du Colombier 	}
171*40d01547SDavid du Colombier 	if(p->mark & FOLL) {
172*40d01547SDavid du Colombier 		for(i=0,q=p; i<4; i++,q=q->link) {
173*40d01547SDavid du Colombier 			if(q == lastp)
174*40d01547SDavid du Colombier 				break;
175*40d01547SDavid du Colombier 			a = q->as;
176*40d01547SDavid du Colombier 			if(a == ANOP) {
177*40d01547SDavid du Colombier 				i--;
178*40d01547SDavid du Colombier 				continue;
179*40d01547SDavid du Colombier 			}
180*40d01547SDavid du Colombier 			if(isbranch(a) || isreturn(a))
181*40d01547SDavid du Colombier 				goto copy;
182*40d01547SDavid du Colombier 			if(q->cond == nil || (q->cond->mark&FOLL))
183*40d01547SDavid du Colombier 				continue;
184*40d01547SDavid du Colombier 			if(a != ABEQ && a != ABNE)
185*40d01547SDavid du Colombier 				continue;
186*40d01547SDavid du Colombier 		copy:
187*40d01547SDavid du Colombier 			for(;;) {
188*40d01547SDavid du Colombier 				r = prg();
189*40d01547SDavid du Colombier 				*r = *p;
190*40d01547SDavid du Colombier 				if(!(r->mark&FOLL))
191*40d01547SDavid du Colombier 					print("cant happen 1\n");
192*40d01547SDavid du Colombier 				r->mark |= FOLL;
193*40d01547SDavid du Colombier 				if(p != q) {
194*40d01547SDavid du Colombier 					p = p->link;
195*40d01547SDavid du Colombier 					lastp->link = r;
196*40d01547SDavid du Colombier 					lastp = r;
197*40d01547SDavid du Colombier 					continue;
198*40d01547SDavid du Colombier 				}
199*40d01547SDavid du Colombier 				lastp->link = r;
200*40d01547SDavid du Colombier 				lastp = r;
201*40d01547SDavid du Colombier 				if(isbranch(a) || isreturn(a))
202*40d01547SDavid du Colombier 					return;
203*40d01547SDavid du Colombier 				r->as = a == ABNE? ABEQ: ABNE;
204*40d01547SDavid du Colombier 				r->cond = p->link;
205*40d01547SDavid du Colombier 				r->link = p->cond;
206*40d01547SDavid du Colombier 				if(!(r->link->mark&FOLL))
207*40d01547SDavid du Colombier 					xfol(r->link);
208*40d01547SDavid du Colombier 				if(!(r->cond->mark&FOLL))
209*40d01547SDavid du Colombier 					print("cant happen 2\n");
210*40d01547SDavid du Colombier 				return;
211*40d01547SDavid du Colombier 			}
212*40d01547SDavid du Colombier 		}
213*40d01547SDavid du Colombier 		a = branchop();
214*40d01547SDavid du Colombier 		q = prg();
215*40d01547SDavid du Colombier 		q->as = a;
216*40d01547SDavid du Colombier 		q->line = p->line;
217*40d01547SDavid du Colombier 		q->to.type = D_BRANCH;
218*40d01547SDavid du Colombier 		q->to.offset = p->pc;
219*40d01547SDavid du Colombier 		q->cond = p;
220*40d01547SDavid du Colombier 		p = q;
221*40d01547SDavid du Colombier 	}
222*40d01547SDavid du Colombier 	p->mark |= FOLL;
223*40d01547SDavid du Colombier 	lastp->link = p;
224*40d01547SDavid du Colombier 	lastp = p;
225*40d01547SDavid du Colombier 	if(isbranch(a) || isreturn(a))
226*40d01547SDavid du Colombier 		return;
227*40d01547SDavid du Colombier 	if(p->cond != P)
228*40d01547SDavid du Colombier 	if(!iscall(a) && p->link != P) {
229*40d01547SDavid du Colombier 		q = brchain(p->link);
230*40d01547SDavid du Colombier 		if(canfollow(a))
231*40d01547SDavid du Colombier 		if(q != P && (q->mark&FOLL)) {
232*40d01547SDavid du Colombier 			p->as = relinv(a);
233*40d01547SDavid du Colombier 			p->link = p->cond;
234*40d01547SDavid du Colombier 			p->cond = q;
235*40d01547SDavid du Colombier 		}
236*40d01547SDavid du Colombier 		xfol(p->link);
237*40d01547SDavid du Colombier 		q = brchain(p->cond);
238*40d01547SDavid du Colombier 		if(q == P)
239*40d01547SDavid du Colombier 			q = p->cond;
240*40d01547SDavid du Colombier 		if(q->mark&FOLL) {
241*40d01547SDavid du Colombier 			p->cond = q;
242*40d01547SDavid du Colombier 			return;
243*40d01547SDavid du Colombier 		}
244*40d01547SDavid du Colombier 		p = q;
245*40d01547SDavid du Colombier 		goto loop;
246*40d01547SDavid du Colombier 	}
247*40d01547SDavid du Colombier 	p = p->link;
248*40d01547SDavid du Colombier 	goto loop;
249*40d01547SDavid du Colombier }
250*40d01547SDavid du Colombier 
251*40d01547SDavid du Colombier void
patch(void)252*40d01547SDavid du Colombier patch(void)
253*40d01547SDavid du Colombier {
254*40d01547SDavid du Colombier 	long c, vexit;
255*40d01547SDavid du Colombier 	Prog *p, *q;
256*40d01547SDavid du Colombier 	Sym *s;
257*40d01547SDavid du Colombier 	int a;
258*40d01547SDavid du Colombier 
259*40d01547SDavid du Colombier 	if(debug['v'])
260*40d01547SDavid du Colombier 		Bprint(&bso, "%5.2f patch\n", cputime());
261*40d01547SDavid du Colombier 	Bflush(&bso);
262*40d01547SDavid du Colombier 	mkfwd();
263*40d01547SDavid du Colombier 	s = lookup("exit", 0);
264*40d01547SDavid du Colombier 	vexit = s->value;
265*40d01547SDavid du Colombier 	for(p = firstp; p != P; p = p->link) {
266*40d01547SDavid du Colombier 		a = p->as;
267*40d01547SDavid du Colombier 		if(a == ATEXT)
268*40d01547SDavid du Colombier 			curtext = p;
269*40d01547SDavid du Colombier 		if((iscall(a) || isbranch(a) || isreturn(a)) &&
270*40d01547SDavid du Colombier 		   p->to.type != D_BRANCH && p->to.sym != S) {
271*40d01547SDavid du Colombier 			s = p->to.sym;
272*40d01547SDavid du Colombier 			switch(s->type) {
273*40d01547SDavid du Colombier 			default:
274*40d01547SDavid du Colombier 				diag("undefined: %s\n%P", s->name, p);
275*40d01547SDavid du Colombier 				s->type = STEXT;
276*40d01547SDavid du Colombier 				s->value = vexit;
277*40d01547SDavid du Colombier 				break;
278*40d01547SDavid du Colombier 			case STEXT:
279*40d01547SDavid du Colombier 				p->to.offset = s->value;
280*40d01547SDavid du Colombier 				break;
281*40d01547SDavid du Colombier 			case SUNDEF:
282*40d01547SDavid du Colombier 				if(!iscall(p->as))
283*40d01547SDavid du Colombier 					diag("help: SUNDEF in AB || ARET");
284*40d01547SDavid du Colombier 				p->to.offset = 0;
285*40d01547SDavid du Colombier 				p->cond = UP;
286*40d01547SDavid du Colombier 				break;
287*40d01547SDavid du Colombier 			}
288*40d01547SDavid du Colombier 			p->to.type = D_BRANCH;
289*40d01547SDavid du Colombier 		}
290*40d01547SDavid du Colombier 		if(p->cond == UP)
291*40d01547SDavid du Colombier 			continue;
292*40d01547SDavid du Colombier 		if(p->to.type == D_BRANCH)
293*40d01547SDavid du Colombier 			c = p->to.offset;
294*40d01547SDavid du Colombier 		else if(p->from.type == D_BRANCH)
295*40d01547SDavid du Colombier 			c = p->from.offset;
296*40d01547SDavid du Colombier 		else
297*40d01547SDavid du Colombier 			continue;
298*40d01547SDavid du Colombier 		for(q = firstp; q != P;) {
299*40d01547SDavid du Colombier 			if(q->forwd != P)
300*40d01547SDavid du Colombier 			if(c >= q->forwd->pc) {
301*40d01547SDavid du Colombier 				q = q->forwd;
302*40d01547SDavid du Colombier 				continue;
303*40d01547SDavid du Colombier 			}
304*40d01547SDavid du Colombier 			if(c == q->pc)
305*40d01547SDavid du Colombier 				break;
306*40d01547SDavid du Colombier 			q = q->link;
307*40d01547SDavid du Colombier 		}
308*40d01547SDavid du Colombier 		if(q == P) {
309*40d01547SDavid du Colombier 			diag("branch out of range %ld\n%P", c, p);
310*40d01547SDavid du Colombier 			p->to.type = D_NONE;
311*40d01547SDavid du Colombier 		}
312*40d01547SDavid du Colombier 		p->cond = q;
313*40d01547SDavid du Colombier 	}
314*40d01547SDavid du Colombier 
315*40d01547SDavid du Colombier 	for(p = firstp; p != P; p = p->link) {
316*40d01547SDavid du Colombier 		if(p->as == ATEXT)
317*40d01547SDavid du Colombier 			curtext = p;
318*40d01547SDavid du Colombier 		if(p->cond != P && p->cond != UP) {
319*40d01547SDavid du Colombier 			p->cond = brloop(p->cond);
320*40d01547SDavid du Colombier 			if(p->cond != P){
321*40d01547SDavid du Colombier 				if(p->to.type == D_BRANCH)
322*40d01547SDavid du Colombier 					p->to.offset = p->cond->pc;
323*40d01547SDavid du Colombier 				if(p->from.type == D_BRANCH)
324*40d01547SDavid du Colombier 					p->from.offset = p->cond->pc;
325*40d01547SDavid du Colombier 			}
326*40d01547SDavid du Colombier 		}
327*40d01547SDavid du Colombier 	}
328*40d01547SDavid du Colombier }
329*40d01547SDavid du Colombier 
330*40d01547SDavid du Colombier #define	LOG	6
331*40d01547SDavid du Colombier void
mkfwd(void)332*40d01547SDavid du Colombier mkfwd(void)
333*40d01547SDavid du Colombier {
334*40d01547SDavid du Colombier 	Prog *p;
335*40d01547SDavid du Colombier 	long dwn[LOG], cnt[LOG], i;
336*40d01547SDavid du Colombier 	Prog *lst[LOG];
337*40d01547SDavid du Colombier 
338*40d01547SDavid du Colombier 	for(i=0; i<LOG; i++) {
339*40d01547SDavid du Colombier 		if(i == 0)
340*40d01547SDavid du Colombier 			cnt[i] = 1; else
341*40d01547SDavid du Colombier 			cnt[i] = LOG * cnt[i-1];
342*40d01547SDavid du Colombier 		dwn[i] = 1;
343*40d01547SDavid du Colombier 		lst[i] = P;
344*40d01547SDavid du Colombier 	}
345*40d01547SDavid du Colombier 	i = 0;
346*40d01547SDavid du Colombier 	for(p = firstp; p != P; p = p->link) {
347*40d01547SDavid du Colombier 		if(p->as == ATEXT)
348*40d01547SDavid du Colombier 			curtext = p;
349*40d01547SDavid du Colombier 		i--;
350*40d01547SDavid du Colombier 		if(i < 0)
351*40d01547SDavid du Colombier 			i = LOG-1;
352*40d01547SDavid du Colombier 		p->forwd = P;
353*40d01547SDavid du Colombier 		dwn[i]--;
354*40d01547SDavid du Colombier 		if(dwn[i] <= 0) {
355*40d01547SDavid du Colombier 			dwn[i] = cnt[i];
356*40d01547SDavid du Colombier 			if(lst[i] != P)
357*40d01547SDavid du Colombier 				lst[i]->forwd = p;
358*40d01547SDavid du Colombier 			lst[i] = p;
359*40d01547SDavid du Colombier 		}
360*40d01547SDavid du Colombier 	}
361*40d01547SDavid du Colombier }
362*40d01547SDavid du Colombier 
363*40d01547SDavid du Colombier Prog*
brloop(Prog * p)364*40d01547SDavid du Colombier brloop(Prog *p)
365*40d01547SDavid du Colombier {
366*40d01547SDavid du Colombier 	Prog *q;
367*40d01547SDavid du Colombier 	int c;
368*40d01547SDavid du Colombier 
369*40d01547SDavid du Colombier 	for(c=0; p!=P;) {
370*40d01547SDavid du Colombier 		if(!isbranch(p->as))
371*40d01547SDavid du Colombier 			return p;
372*40d01547SDavid du Colombier 		q = p->cond;
373*40d01547SDavid du Colombier 		if(q <= p) {
374*40d01547SDavid du Colombier 			c++;
375*40d01547SDavid du Colombier 			if(q == p || c > 5000)
376*40d01547SDavid du Colombier 				break;
377*40d01547SDavid du Colombier 		}
378*40d01547SDavid du Colombier 		p = q;
379*40d01547SDavid du Colombier 	}
380*40d01547SDavid du Colombier 	return P;
381*40d01547SDavid du Colombier }
382