liblink: create new library based on linker code

There is an enormous amount of code moving around in this CL,
but the code is the same, and it is invoked in the same ways.
This CL is preparation for the new linker structure, not the new
structure itself.

The new library's definition is in include/link.h.

The main change is the use of a Link structure to hold all the
linker-relevant state, replacing the smattering of global variables.
The Link structure should both make it clearer which state must
be carried around and make it possible to parallelize more easily
later.

The main body of the linker has moved into the architecture-independent
cmd/ld directory. That includes the list of known header types, so the
distinction between Hplan9x32 and Hplan9x64 is removed (no other
header type distinguished 32- and 64-bit formats), and code for unused
formats such as ipaq kernels has been deleted.

The code being deleted from 5l, 6l, and 8l reappears in liblink or in ld.
Because multiple files are being merged in the liblink directory,
it is not possible to show the diffs nicely in hg.

The Prog and Addr structures have been unified into an
architecture-independent form and moved to link.h, where they will
be shared by all tools: the assemblers, the compilers, and the linkers.
The unification makes it possible to write architecture-independent
traversal of Prog lists, among other benefits.

The Sym structures cannot be unified: they are too fundamentally
different between the linker and the compilers. Instead, liblink defines
an LSym - a linker Sym - to be used in the Prog and Addr structures,
and the linker now refers exclusively to LSyms. The compilers will
keep using their own syms but will fill out the corresponding LSyms in
the Prog and Addr structures.

Although code from 5l, 6l, and 8l is now in a single library, the
code has been arranged so that only one architecture needs to
be linked into a particular program: 5l will not contain the code
needed for x86 instruction layout, for example.

The object file writing code in liblink/obj.c is from cmd/gc/obj.c.

Preparation for golang.org/s/go13linker work.

This CL does not build by itself. It depends on 35740044
and will be submitted at the same time.

R=iant
CC=golang-dev
https://codereview.appspot.com/35790044

1 files changed, 298 insertions, 0 deletions

diff --git a/src/liblink/pcln.c b/src/liblink/pcln.c
new file mode 100644
index 000000000..21eb94414
--- /dev/null
+++ b/src/liblink/pcln.c
@@ -0,0 +1,298 @@
+// Copyright 2013 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <link.h>
+
+static void
+addvarint(Link *ctxt, Pcdata *d, uint32 val)
+{
+	int32 n;
+	uint32 v;
+	uchar *p;
+
+	USED(ctxt);
+
+	n = 0;
+	for(v = val; v >= 0x80; v >>= 7)
+		n++;
+	n++;
+
+	if(d->n + n > d->m) {
+		d->m = (d->n + n)*2;
+		d->p = erealloc(d->p, d->m);
+	}
+
+	p = d->p + d->n;
+	for(v = val; v >= 0x80; v >>= 7)
+		*p++ = v | 0x80;
+	*p++ = v;
+	d->n += n;
+}
+
+// funcpctab writes to dst a pc-value table mapping the code in func to the values
+// returned by valfunc parameterized by arg. The invocation of valfunc to update the
+// current value is, for each p,
+//
+//	val = valfunc(func, val, p, 0, arg);
+//	record val as value at p->pc;
+//	val = valfunc(func, val, p, 1, arg);
+//
+// where func is the function, val is the current value, p is the instruction being
+// considered, and arg can be used to further parameterize valfunc.
+static void
+funcpctab(Link *ctxt, Pcdata *dst, LSym *func, char *desc, int32 (*valfunc)(Link*, LSym*, int32, Prog*, int32, void*), void* arg)
+{
+	int dbg, i;
+	int32 oldval, val, started;
+	uint32 delta;
+	vlong pc;
+	Prog *p;
+
+	// To debug a specific function, uncomment second line and change name.
+	dbg = 0;
+	//dbg = strcmp(func->name, "main.main") == 0;
+	//dbg = strcmp(desc, "pctofile") == 0;
+
+	ctxt->debugpcln += dbg;
+
+	dst->n = 0;
+
+	if(ctxt->debugpcln)
+		Bprint(ctxt->bso, "funcpctab %s [valfunc=%s]\n", func->name, desc);
+
+	val = -1;
+	oldval = val;
+	if(func->text == nil)
+		return;
+
+	pc = func->text->pc;
+	
+	if(ctxt->debugpcln)
+		Bprint(ctxt->bso, "%6llux %6d %P\n", pc, val, func->text);
+
+	started = 0;
+	for(p=func->text; p != nil; p = p->link) {
+		// Update val. If it's not changing, keep going.
+		val = valfunc(ctxt, func, val, p, 0, arg);
+		if(val == oldval && started) {
+			val = valfunc(ctxt, func, val, p, 1, arg);
+			if(ctxt->debugpcln)
+				Bprint(ctxt->bso, "%6llux %6s %P\n", (vlong)p->pc, "", p);
+			continue;
+		}
+
+		// If the pc of the next instruction is the same as the
+		// pc of this instruction, this instruction is not a real
+		// instruction. Keep going, so that we only emit a delta
+		// for a true instruction boundary in the program.
+		if(p->link && p->link->pc == p->pc) {
+			val = valfunc(ctxt, func, val, p, 1, arg);
+			if(ctxt->debugpcln)
+				Bprint(ctxt->bso, "%6llux %6s %P\n", (vlong)p->pc, "", p);
+			continue;
+		}
+
+		// The table is a sequence of (value, pc) pairs, where each
+		// pair states that the given value is in effect from the current position
+		// up to the given pc, which becomes the new current position.
+		// To generate the table as we scan over the program instructions,
+		// we emit a "(value" when pc == func->value, and then
+		// each time we observe a change in value we emit ", pc) (value".
+		// When the scan is over, we emit the closing ", pc)".
+		//
+		// The table is delta-encoded. The value deltas are signed and
+		// transmitted in zig-zag form, where a complement bit is placed in bit 0,
+		// and the pc deltas are unsigned. Both kinds of deltas are sent
+		// as variable-length little-endian base-128 integers,
+		// where the 0x80 bit indicates that the integer continues.
+
+		if(ctxt->debugpcln)
+			Bprint(ctxt->bso, "%6llux %6d %P\n", (vlong)p->pc, val, p);
+
+		if(started) {
+			addvarint(ctxt, dst, (p->pc - pc) / ctxt->arch->minlc);
+			pc = p->pc;
+		}
+		delta = val - oldval;
+		if(delta>>31)
+			delta = 1 | ~(delta<<1);
+		else
+			delta <<= 1;
+		addvarint(ctxt, dst, delta);
+		oldval = val;
+		started = 1;
+		val = valfunc(ctxt, func, val, p, 1, arg);
+	}
+
+	if(started) {
+		if(ctxt->debugpcln)
+			Bprint(ctxt->bso, "%6llux done\n", (vlong)func->text->pc+func->size);
+		addvarint(ctxt, dst, (func->value+func->size - pc) / ctxt->arch->minlc);
+		addvarint(ctxt, dst, 0); // terminator
+	}
+
+	if(ctxt->debugpcln) {
+		Bprint(ctxt->bso, "wrote %d bytes to %p\n", dst->n, dst);
+		for(i=0; i<dst->n; i++)
+			Bprint(ctxt->bso, " %02ux", dst->p[i]);
+		Bprint(ctxt->bso, "\n");
+	}
+
+	ctxt->debugpcln -= dbg;
+}
+
+// pctofileline computes either the file number (arg == 0)
+// or the line number (arg == 1) to use at p.
+// Because p->lineno applies to p, phase == 0 (before p)
+// takes care of the update.
+static int32
+pctofileline(Link *ctxt, LSym *sym, int32 oldval, Prog *p, int32 phase, void *arg)
+{
+	int32 i, l;
+	LSym *f;
+	Pcln *pcln;
+
+	if(p->as == ctxt->arch->ATEXT || p->as == ctxt->arch->ANOP || p->as == ctxt->arch->AUSEFIELD || p->lineno == 0 || phase == 1)
+		return oldval;
+	linkgetline(ctxt, sym->hist, p->lineno, &f, &l);
+	if(f == nil) {
+	//	print("getline failed for %s %P\n", ctxt->cursym->name, p);
+		return oldval;
+	}
+	if(arg == nil)
+		return l;
+	pcln = arg;
+	
+	if(f == pcln->lastfile)
+		return pcln->lastindex;
+
+	for(i=0; i<pcln->nfile; i++) {
+		if(pcln->file[i] == f) {
+			pcln->lastfile = f;
+			pcln->lastindex = i;
+			return i;
+		}
+	}
+
+	if(pcln->nfile >= pcln->mfile) {
+		pcln->mfile = (pcln->nfile+1)*2;
+		pcln->file = erealloc(pcln->file, pcln->mfile*sizeof pcln->file[0]);
+	}
+	pcln->file[pcln->nfile++] = f;
+	pcln->lastfile = f;
+	pcln->lastindex = i;
+	return i;
+}
+
+// pctospadj computes the sp adjustment in effect.
+// It is oldval plus any adjustment made by p itself.
+// The adjustment by p takes effect only after p, so we
+// apply the change during phase == 1.
+static int32
+pctospadj(Link *ctxt, LSym *sym, int32 oldval, Prog *p, int32 phase, void *arg)
+{
+	USED(arg);
+	USED(sym);
+
+	if(oldval == -1) // starting
+		oldval = 0;
+	if(phase == 0)
+		return oldval;
+	if(oldval + p->spadj < -10000 || oldval + p->spadj > 1100000000) {
+		ctxt->diag("overflow in spadj: %d + %d = %d", oldval, p->spadj, oldval + p->spadj);
+		sysfatal("bad code");
+	}
+	return oldval + p->spadj;
+}
+
+// pctopcdata computes the pcdata value in effect at p.
+// A PCDATA instruction sets the value in effect at future
+// non-PCDATA instructions.
+// Since PCDATA instructions have no width in the final code,
+// it does not matter which phase we use for the update.
+static int32
+pctopcdata(Link *ctxt, LSym *sym, int32 oldval, Prog *p, int32 phase, void *arg)
+{
+	USED(sym);
+
+	if(phase == 0 || p->as != ctxt->arch->APCDATA || p->from.offset != (uintptr)arg)
+		return oldval;
+	if((int32)p->to.offset != p->to.offset) {
+		ctxt->diag("overflow in PCDATA instruction: %P", p);
+		sysfatal("bad code");
+	}
+	return p->to.offset;
+}
+
+void
+linkpcln(Link *ctxt, LSym *cursym)
+{
+	Prog *p;
+	Pcln *pcln;
+	int i, npcdata, nfuncdata, n;
+	uint32 *havepc, *havefunc;
+
+	ctxt->cursym = cursym;
+
+	pcln = emallocz(sizeof *pcln);
+	cursym->pcln = pcln;
+
+	npcdata = 0;
+	nfuncdata = 0;
+	for(p = cursym->text; p != nil; p = p->link) {
+		if(p->as == ctxt->arch->APCDATA && p->from.offset >= npcdata)
+			npcdata = p->from.offset+1;
+		if(p->as == ctxt->arch->AFUNCDATA && p->from.offset >= nfuncdata)
+			nfuncdata = p->from.offset+1;
+	}
+
+	pcln->pcdata = emallocz(npcdata*sizeof pcln->pcdata[0]);
+	pcln->npcdata = npcdata;
+	pcln->funcdata = emallocz(nfuncdata*sizeof pcln->funcdata[0]);
+	pcln->funcdataoff = emallocz(nfuncdata*sizeof pcln->funcdataoff[0]);
+	pcln->nfuncdata = nfuncdata;
+
+	funcpctab(ctxt, &pcln->pcsp, cursym, "pctospadj", pctospadj, nil);
+	funcpctab(ctxt, &pcln->pcfile, cursym, "pctofile", pctofileline, pcln);
+	funcpctab(ctxt, &pcln->pcline, cursym, "pctoline", pctofileline, nil);
+	
+	// tabulate which pc and func data we have.
+	n = ((npcdata+31)/32 + (nfuncdata+31)/32)*4;
+	havepc = emallocz(n);
+	havefunc = havepc + (npcdata+31)/32;
+	for(p = cursym->text; p != nil; p = p->link) {
+		if(p->as == ctxt->arch->AFUNCDATA) {
+			if((havefunc[p->from.offset/32]>>(p->from.offset%32))&1)
+				ctxt->diag("multiple definitions for FUNCDATA $%d", p->from.offset);
+			havefunc[p->from.offset/32] |= 1<<(p->from.offset%32);
+		}
+		if(p->as == ctxt->arch->APCDATA)
+			havepc[p->from.offset/32] |= 1<<(p->from.offset%32);
+	}
+	// pcdata.
+	for(i=0; i<npcdata; i++) {
+		if(!(havepc[i/32]>>(i%32))&1) 
+			continue;
+		funcpctab(ctxt, &pcln->pcdata[i], cursym, "pctopcdata", pctopcdata, (void*)(uintptr)i);
+	}
+	free(havepc);
+	
+	// funcdata
+	if(nfuncdata > 0) {
+		for(p = cursym->text; p != nil; p = p->link) {
+			if(p->as == ctxt->arch->AFUNCDATA) {
+				i = p->from.offset;
+				pcln->funcdataoff[i] = p->to.offset;
+				if(p->to.type != ctxt->arch->D_CONST) {
+					// TODO: Dedup.
+					//funcdata_bytes += p->to.sym->size;
+					pcln->funcdata[i] = p->to.sym;
+				}
+			}
+		}
+	}
+}