1 // Inferno utils/6l/pass.c
2 // http://code.google.com/p/inferno-os/source/browse/utils/6l/pass.c
3 //
4 // Copyright © 1994-1999 Lucent Technologies Inc. All rights reserved.
5 // Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
6 // Portions Copyright © 1997-1999 Vita Nuova Limited
7 // Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
8 // Portions Copyright © 2004,2006 Bruce Ellis
9 // Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
10 // Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
11 // Portions Copyright © 2009 The Go Authors. All rights reserved.
12 //
13 // Permission is hereby granted, free of charge, to any person obtaining a copy
14 // of this software and associated documentation files (the "Software"), to deal
15 // in the Software without restriction, including without limitation the rights
16 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 // copies of the Software, and to permit persons to whom the Software is
18 // furnished to do so, subject to the following conditions:
19 //
20 // The above copyright notice and this permission notice shall be included in
21 // all copies or substantial portions of the Software.
22 //
23 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
29 // THE SOFTWARE.
30
31 // Code and data passes.
32
33 #include "l.h"
34 #include "../ld/lib.h"
35 #include "../../pkg/runtime/stack.h"
36
37 static void xfol(Prog*, Prog**);
38
39 Prog*
40 brchain(Prog *p)
41 {
42 int i;
43
44 for(i=0; i<20; i++) {
45 if(p == P || p->as != AJMP)
46 return p;
47 p = p->pcond;
48 }
49 return P;
50 }
51
52 void
53 follow(void)
54 {
55 Prog *firstp, *lastp;
56
57 if(debug['v'])
58 Bprint(&bso, "%5.2f follow\n", cputime());
59 Bflush(&bso);
60
61 for(cursym = textp; cursym != nil; cursym = cursym->next) {
62 firstp = prg();
63 lastp = firstp;
64 xfol(cursym->text, &lastp);
65 lastp->link = nil;
66 cursym->text = firstp->link;
67 }
68 }
69
70 static int
71 nofollow(int a)
72 {
73 switch(a) {
74 case AJMP:
75 case ARET:
76 case AIRETL:
77 case AIRETQ:
78 case AIRETW:
79 case ARETFL:
80 case ARETFQ:
81 case ARETFW:
82 return 1;
83 }
84 return 0;
85 }
86
87 static int
88 pushpop(int a)
89 {
90 switch(a) {
91 case APUSHL:
92 case APUSHFL:
93 case APUSHQ:
94 case APUSHFQ:
95 case APUSHW:
96 case APUSHFW:
97 case APOPL:
98 case APOPFL:
99 case APOPQ:
100 case APOPFQ:
101 case APOPW:
102 case APOPFW:
103 return 1;
104 }
105 return 0;
106 }
107
108 static void
109 xfol(Prog *p, Prog **last)
110 {
111 Prog *q;
112 int i;
113 enum as a;
114
115 loop:
116 if(p == P)
117 return;
118 if(p->as == AJMP)
119 if((q = p->pcond) != P && q->as != ATEXT) {
120 /* mark instruction as done and continue layout at target of jump */
121 p->mark = 1;
122 p = q;
123 if(p->mark == 0)
124 goto loop;
125 }
126 if(p->mark) {
127 /*
128 * p goes here, but already used it elsewhere.
129 * copy up to 4 instructions or else branch to other copy.
130 */
131 for(i=0,q=p; i<4; i++,q=q->link) {
132 if(q == P)
133 break;
134 if(q == *last)
135 break;
136 a = q->as;
137 if(a == ANOP) {
138 i--;
139 continue;
140 }
141 if(nofollow(a) || pushpop(a))
142 break; // NOTE(rsc): arm does goto copy
143 if(q->pcond == P || q->pcond->mark)
144 continue;
145 if(a == ACALL || a == ALOOP)
146 continue;
147 for(;;) {
148 if(p->as == ANOP) {
149 p = p->link;
150 continue;
151 }
152 q = copyp(p);
153 p = p->link;
154 q->mark = 1;
155 (*last)->link = q;
156 *last = q;
157 if(q->as != a || q->pcond == P || q->pcond->mark)
158 continue;
159
160 q->as = relinv(q->as);
161 p = q->pcond;
162 q->pcond = q->link;
163 q->link = p;
164 xfol(q->link, last);
165 p = q->link;
166 if(p->mark)
167 return;
168 goto loop;
169 }
170 } /* */
171 q = prg();
172 q->as = AJMP;
173 q->line = p->line;
174 q->to.type = D_BRANCH;
175 q->to.offset = p->pc;
176 q->pcond = p;
177 p = q;
178 }
179
180 /* emit p */
181 p->mark = 1;
182 (*last)->link = p;
183 *last = p;
184 a = p->as;
185
186 /* continue loop with what comes after p */
187 if(nofollow(a))
188 return;
189 if(p->pcond != P && a != ACALL) {
190 /*
191 * some kind of conditional branch.
192 * recurse to follow one path.
193 * continue loop on the other.
194 */
195 q = brchain(p->link);
196 if(q != P && q->mark)
197 if(a != ALOOP) {
198 p->as = relinv(a);
199 p->link = p->pcond;
200 p->pcond = q;
201 }
202 xfol(p->link, last);
203 q = brchain(p->pcond);
204 if(q->mark) {
205 p->pcond = q;
206 return;
207 }
208 p = q;
209 goto loop;
210 }
211 p = p->link;
212 goto loop;
213 }
214
215 Prog*
216 byteq(int v)
217 {
218 Prog *p;
219
220 p = prg();
221 p->as = ABYTE;
222 p->from.type = D_CONST;
223 p->from.offset = v&0xff;
224 return p;
225 }
226
227 int
228 relinv(int a)
229 {
230
231 switch(a) {
232 case AJEQ: return AJNE;
233 case AJNE: return AJEQ;
234 case AJLE: return AJGT;
235 case AJLS: return AJHI;
236 case AJLT: return AJGE;
237 case AJMI: return AJPL;
238 case AJGE: return AJLT;
239 case AJPL: return AJMI;
240 case AJGT: return AJLE;
241 case AJHI: return AJLS;
242 case AJCS: return AJCC;
243 case AJCC: return AJCS;
244 case AJPS: return AJPC;
245 case AJPC: return AJPS;
246 case AJOS: return AJOC;
247 case AJOC: return AJOS;
248 }
249 diag("unknown relation: %s in %s", anames[a], TNAME);
250 errorexit();
251 return a;
252 }
253
254 void
255 patch(void)
256 {
257 int32 c;
258 Prog *p, *q;
259 Sym *s;
260 int32 vexit;
261
262 if(debug['v'])
263 Bprint(&bso, "%5.2f mkfwd\n", cputime());
264 Bflush(&bso);
265 mkfwd();
266 if(debug['v'])
267 Bprint(&bso, "%5.2f patch\n", cputime());
268 Bflush(&bso);
269
270 s = lookup("exit", 0);
271 vexit = s->value;
272 for(cursym = textp; cursym != nil; cursym = cursym->next)
273 for(p = cursym->text; p != P; p = p->link) {
274 if(HEADTYPE == Hwindows) {
275 // Windows
276 // Convert
277 // op n(GS), reg
278 // to
279 // MOVL 0x58(GS), reg
280 // op n(reg), reg
281 // The purpose of this patch is to fix some accesses
282 // to extern register variables (TLS) on Windows, as
283 // a different method is used to access them.
284 if(p->from.type == D_INDIR+D_GS
285 && p->to.type >= D_AX && p->to.type <= D_DI
286 && p->from.offset <= 8) {
287 q = appendp(p);
288 q->from = p->from;
289 q->from.type = D_INDIR + p->to.type;
290 q->to = p->to;
291 q->as = p->as;
292 p->as = AMOVQ;
293 p->from.type = D_INDIR+D_GS;
294 p->from.offset = 0x58;
295 }
296 }
297 if(HEADTYPE == Hlinux || HEADTYPE == Hfreebsd
298 || HEADTYPE == Hopenbsd) {
299 // ELF uses FS instead of GS.
300 if(p->from.type == D_INDIR+D_GS)
301 p->from.type = D_INDIR+D_FS;
302 if(p->to.type == D_INDIR+D_GS)
303 p->to.type = D_INDIR+D_FS;
304 }
305 if(p->as == ACALL || (p->as == AJMP && p->to.type != D_BRANCH)) {
306 s = p->to.sym;
307 if(s) {
308 if(debug['c'])
309 Bprint(&bso, "%s calls %s\n", TNAME, s->name);
310 if((s->type&~SSUB) != STEXT) {
311 /* diag prints TNAME first */
312 diag("undefined: %s", s->name);
313 s->type = STEXT;
314 s->value = vexit;
315 continue; // avoid more error messages
316 }
317 if(s->text == nil)
318 continue;
319 p->to.type = D_BRANCH;
320 p->to.offset = s->text->pc;
321 p->pcond = s->text;
322 continue;
323 }
324 }
325 if(p->to.type != D_BRANCH)
326 continue;
327 c = p->to.offset;
328 for(q = cursym->text; q != P;) {
329 if(c == q->pc)
330 break;
331 if(q->forwd != P && c >= q->forwd->pc)
332 q = q->forwd;
333 else
334 q = q->link;
335 }
336 if(q == P) {
337 diag("branch out of range in %s (%#ux)\n%P [%s]",
338 TNAME, c, p, p->to.sym ? p->to.sym->name : "<nil>");
339 p->to.type = D_NONE;
340 }
341 p->pcond = q;
342 }
343
344 for(cursym = textp; cursym != nil; cursym = cursym->next)
345 for(p = cursym->text; p != P; p = p->link) {
346 p->mark = 0; /* initialization for follow */
347 if(p->pcond != P) {
348 p->pcond = brloop(p->pcond);
349 if(p->pcond != P)
350 if(p->to.type == D_BRANCH)
351 p->to.offset = p->pcond->pc;
352 }
353 }
354 }
355
356 Prog*
357 brloop(Prog *p)
358 {
359 int c;
360 Prog *q;
361
362 c = 0;
363 for(q = p; q != P; q = q->pcond) {
364 if(q->as != AJMP)
365 break;
366 c++;
367 if(c >= 5000)
368 return P;
369 }
370 return q;
371 }
372
373 static char*
374 morename[] =
375 {
376 "runtime.morestack00",
377 "runtime.morestack10",
378 "runtime.morestack01",
379 "runtime.morestack11",
380
381 "runtime.morestack8",
382 "runtime.morestack16",
383 "runtime.morestack24",
384 "runtime.morestack32",
385 "runtime.morestack40",
386 "runtime.morestack48",
387 };
388 Prog* pmorestack[nelem(morename)];
389 Sym* symmorestack[nelem(morename)];
390
391 void
392 dostkoff(void)
393 {
394 Prog *p, *q, *q1;
395 int32 autoffset, deltasp;
396 int a, pcsize;
397 uint32 moreconst1, moreconst2, i;
398
399 for(i=0; i<nelem(morename); i++) {
400 symmorestack[i] = lookup(morename[i], 0);
401 if(symmorestack[i]->type != STEXT)
402 diag("morestack trampoline not defined - %s", morename[i]);
403 pmorestack[i] = symmorestack[i]->text;
404 }
405
406 for(cursym = textp; cursym != nil; cursym = cursym->next) {
407 if(cursym->text == nil || cursym->text->link == nil)
408 continue;
409
410 p = cursym->text;
411 parsetextconst(p->to.offset);
412 autoffset = textstksiz;
413 if(autoffset < 0)
414 autoffset = 0;
415
416 q = P;
417 if((p->from.scale & NOSPLIT) && autoffset >= StackSmall)
418 diag("nosplit func likely to overflow stack");
419
420 if(!(p->from.scale & NOSPLIT)) {
421 p = appendp(p); // load g into CX
422 p->as = AMOVQ;
423 if(HEADTYPE == Hlinux || HEADTYPE == Hfreebsd
424 || HEADTYPE == Hopenbsd) // ELF uses FS
425 p->from.type = D_INDIR+D_FS;
426 else
427 p->from.type = D_INDIR+D_GS;
428 p->from.offset = tlsoffset+0;
429 p->to.type = D_CX;
430 if(HEADTYPE == Hwindows) {
431 // movq %gs:0x58, %rcx
432 // movq (%rcx), %rcx
433 p->as = AMOVQ;
434 p->from.type = D_INDIR+D_GS;
435 p->from.offset = 0x58;
436 p->to.type = D_CX;
437
438
439 p = appendp(p);
440 p->as = AMOVQ;
441 p->from.type = D_INDIR+D_CX;
442 p->from.offset = 0;
443 p->to.type = D_CX;
444 }
445
446 if(debug['K']) {
447 // 6l -K means check not only for stack
448 // overflow but stack underflow.
449 // On underflow, INT 3 (breakpoint).
450 // Underflow itself is rare but this also
451 // catches out-of-sync stack guard info
452
453 p = appendp(p);
454 p->as = ACMPQ;
455 p->from.type = D_INDIR+D_CX;
456 p->from.offset = 8;
457 p->to.type = D_SP;
458
459 p = appendp(p);
460 p->as = AJHI;
461 p->to.type = D_BRANCH;
462 p->to.offset = 4;
463 q1 = p;
464
465 p = appendp(p);
466 p->as = AINT;
467 p->from.type = D_CONST;
468 p->from.offset = 3;
469
470 p = appendp(p);
471 p->as = ANOP;
472 q1->pcond = p;
473 }
474
475 if(autoffset < StackBig) { // do we need to call morestack?
476 if(autoffset <= StackSmall) {
477 // small stack
478 p = appendp(p);
479 p->as = ACMPQ;
480 p->from.type = D_SP;
481 p->to.type = D_INDIR+D_CX;
482 } else {
483 // large stack
484 p = appendp(p);
485 p->as = ALEAQ;
486 p->from.type = D_INDIR+D_SP;
487 p->from.offset = -(autoffset-StackSmall);
488 p->to.type = D_AX;
489
490 p = appendp(p);
491 p->as = ACMPQ;
492 p->from.type = D_AX;
493 p->to.type = D_INDIR+D_CX;
494 }
495
496 // common
497 p = appendp(p);
498 p->as = AJHI;
499 p->to.type = D_BRANCH;
500 p->to.offset = 4;
501 q = p;
502 }
503
504 /* 160 comes from 3 calls (3*8) 4 safes (4*8) and 104 guard */
505 moreconst1 = 0;
506 if(autoffset+160+textarg > 4096)
507 moreconst1 = (autoffset+160) & ~7LL;
508 moreconst2 = textarg;
509
510 // 4 varieties varieties (const1==0 cross const2==0)
511 // and 6 subvarieties of (const1==0 and const2!=0)
512 p = appendp(p);
513 if(moreconst1 == 0 && moreconst2 == 0) {
514 p->as = ACALL;
515 p->to.type = D_BRANCH;
516 p->pcond = pmorestack[0];
517 p->to.sym = symmorestack[0];
518 } else
519 if(moreconst1 != 0 && moreconst2 == 0) {
520 p->as = AMOVL;
521 p->from.type = D_CONST;
522 p->from.offset = moreconst1;
523 p->to.type = D_AX;
524
525 p = appendp(p);
526 p->as = ACALL;
527 p->to.type = D_BRANCH;
528 p->pcond = pmorestack[1];
529 p->to.sym = symmorestack[1];
530 } else
531 if(moreconst1 == 0 && moreconst2 <= 48 && moreconst2%8 == 0) {
532 i = moreconst2/8 + 3;
533 p->as = ACALL;
534 p->to.type = D_BRANCH;
535 p->pcond = pmorestack[i];
536 p->to.sym = symmorestack[i];
537 } else
538 if(moreconst1 == 0 && moreconst2 != 0) {
539 p->as = AMOVL;
540 p->from.type = D_CONST;
541 p->from.offset = moreconst2;
542 p->to.type = D_AX;
543
544 p = appendp(p);
545 p->as = ACALL;
546 p->to.type = D_BRANCH;
547 p->pcond = pmorestack[2];
548 p->to.sym = symmorestack[2];
549 } else {
550 p->as = AMOVQ;
551 p->from.type = D_CONST;
552 p->from.offset = (uint64)moreconst2 << 32;
553 p->from.offset |= moreconst1;
554 p->to.type = D_AX;
555
556 p = appendp(p);
557 p->as = ACALL;
558 p->to.type = D_BRANCH;
559 p->pcond = pmorestack[3];
560 p->to.sym = symmorestack[3];
561 }
562 }
563
564 if(q != P)
565 q->pcond = p->link;
566
567 if(autoffset) {
568 p = appendp(p);
569 p->as = AADJSP;
570 p->from.type = D_CONST;
571 p->from.offset = autoffset;
572 p->spadj = autoffset;
573 if(q != P)
574 q->pcond = p;
575 }
576 deltasp = autoffset;
577
578 if(debug['K'] > 1 && autoffset) {
579 // 6l -KK means double-check for stack overflow
580 // even after calling morestack and even if the
581 // function is marked as nosplit.
582 p = appendp(p);
583 p->as = AMOVQ;
584 p->from.type = D_INDIR+D_CX;
585 p->from.offset = 0;
586 p->to.type = D_BX;
587
588 p = appendp(p);
589 p->as = ASUBQ;
590 p->from.type = D_CONST;
591 p->from.offset = StackSmall+32;
592 p->to.type = D_BX;
593
594 p = appendp(p);
595 p->as = ACMPQ;
596 p->from.type = D_SP;
597 p->to.type = D_BX;
598
599 p = appendp(p);
600 p->as = AJHI;
601 p->to.type = D_BRANCH;
602 q1 = p;
603
604 p = appendp(p);
605 p->as = AINT;
606 p->from.type = D_CONST;
607 p->from.offset = 3;
608
609 p = appendp(p);
610 p->as = ANOP;
611 q1->pcond = p;
612 }
613
614 for(; p != P; p = p->link) {
615 pcsize = p->mode/8;
616 a = p->from.type;
617 if(a == D_AUTO)
618 p->from.offset += deltasp;
619 if(a == D_PARAM)
620 p->from.offset += deltasp + pcsize;
621 a = p->to.type;
622 if(a == D_AUTO)
623 p->to.offset += deltasp;
624 if(a == D_PARAM)
625 p->to.offset += deltasp + pcsize;
626
627 switch(p->as) {
628 default:
629 continue;
630 case APUSHL:
631 case APUSHFL:
632 deltasp += 4;
633 p->spadj = 4;
634 continue;
635 case APUSHQ:
636 case APUSHFQ:
637 deltasp += 8;
638 p->spadj = 8;
639 continue;
640 case APUSHW:
641 case APUSHFW:
642 deltasp += 2;
643 p->spadj = 2;
644 continue;
645 case APOPL:
646 case APOPFL:
647 deltasp -= 4;
648 p->spadj = -4;
649 continue;
650 case APOPQ:
651 case APOPFQ:
652 deltasp -= 8;
653 p->spadj = -8;
654 continue;
655 case APOPW:
656 case APOPFW:
657 deltasp -= 2;
658 p->spadj = -2;
659 continue;
660 case ARET:
661 break;
662 }
663
664 if(autoffset != deltasp)
665 diag("unbalanced PUSH/POP");
666
667 if(autoffset) {
668 p->as = AADJSP;
669 p->from.type = D_CONST;
670 p->from.offset = -autoffset;
671 p->spadj = -autoffset;
672 p = appendp(p);
673 p->as = ARET;
674 // If there are instructions following
675 // this ARET, they come from a branch
676 // with the same stackframe, so undo
677 // the cleanup.
678 p->spadj = +autoffset;
679 }
680 }
681 }
682 }
683
684 vlong
685 atolwhex(char *s)
686 {
687 vlong n;
688 int f;
689
690 n = 0;
691 f = 0;
692 while(*s == ' ' || *s == '\t')
693 s++;
694 if(*s == '-' || *s == '+') {
695 if(*s++ == '-')
696 f = 1;
697 while(*s == ' ' || *s == '\t')
698 s++;
699 }
700 if(s[0]=='0' && s[1]){
701 if(s[1]=='x' || s[1]=='X'){
702 s += 2;
703 for(;;){
704 if(*s >= '0' && *s <= '9')
705 n = n*16 + *s++ - '0';
706 else if(*s >= 'a' && *s <= 'f')
707 n = n*16 + *s++ - 'a' + 10;
708 else if(*s >= 'A' && *s <= 'F')
709 n = n*16 + *s++ - 'A' + 10;
710 else
711 break;
712 }
713 } else
714 while(*s >= '0' && *s <= '7')
715 n = n*8 + *s++ - '0';
716 } else
717 while(*s >= '0' && *s <= '9')
718 n = n*10 + *s++ - '0';
719 if(f)
720 n = -n;
721 return n;
722 }