cmd/gc, cmd/ld, runtime: compact liveness bitmaps

Reduce footprint of liveness bitmaps by about 5x.

1. Mark all liveness bitmap symbols as 4-byte aligned
(they were aligned to a larger size by default).

2. The bitmap data is a bitmap count n followed by n bitmaps.
Each bitmap begins with its own count m giving the number
of bits. All the m's are the same for the n bitmaps.
Emit this bitmap length once instead of n times.

3. Many bitmaps within a function have the same bit values,
but each call site was given a distinct bitmap. Merge duplicate
bitmaps so that no bitmap is written more than once.

4. Many functions end up with the same aggregate bitmap data.
We used to name the bitmap data funcname.gcargs and funcname.gclocals.
Instead, name it gclocals.<md5 of data> and mark it dupok so
that the linker coalesces duplicate sets. This cut the bitmap
data remaining after step 3 by 40%; I was not expecting it to
be quite so dramatic.

Applied to "go build -ldflags -w code.google.com/p/go.tools/cmd/godoc":

                bitmaps           pclntab           binary on disk
before this CL  1326600           1985854           12738268
4-byte align    1154288 (0.87x)   1985854 (1.00x)   12566236 (0.99x)
one bitmap len   782528 (0.54x)   1985854 (1.00x)   12193500 (0.96x)
dedup bitmap     414748 (0.31x)   1948478 (0.98x)   11787996 (0.93x)
dedup bitmap set 245580 (0.19x)   1948478 (0.98x)   11620060 (0.91x)

While here, remove various dead blocks of code from plive.c.

Fixes issue 6929.
Fixes issue 7568.

LGTM=khr
R=khr
CC=golang-codereviews
https://codereview.appspot.com/83630044

1 files changed, 12 insertions, 2 deletions

diff --git a/src/liblink/objfile.c b/src/liblink/objfile.c
index 52ec90d68..b60253625 100644
--- a/src/liblink/objfile.c
+++ b/src/liblink/objfile.c
@@ -485,7 +485,7 @@ readsym(Link *ctxt, Biobuf *f, char *pkg, char *pn)
 	static int ndup;
 	char *name;
 	Reloc *r;
-	LSym *s;
+	LSym *s, *dup;
 	Pcln *pc;
 	Auto *a;
 	
@@ -502,11 +502,14 @@ readsym(Link *ctxt, Biobuf *f, char *pkg, char *pn)
 	if(v != 0)
 		v = ctxt->version;
 	s = linklookup(ctxt, name, v);
+	dup = nil;
 	if(s->type != 0 && s->type != SXREF) {
 		if(s->type != SBSS && s->type != SNOPTRBSS && !dupok && !s->dupok)
 			sysfatal("duplicate symbol %s (types %d and %d) in %s and %s", s->name, s->type, t, s->file, pn);
-		if(s->np > 0)
+		if(s->np > 0) {
+			dup = s;
 			s = linklookup(ctxt, ".dup", ndup++); // scratch
+		}
 	}
 	s->file = pkg;
 	s->dupok = dupok;
@@ -537,6 +540,13 @@ readsym(Link *ctxt, Biobuf *f, char *pkg, char *pn)
 		}
 	}
 	
+	if(s->np > 0 && dup != nil && dup->np > 0 && strncmp(s->name, "gclocals·", 10) == 0) {
+		// content-addressed garbage collection liveness bitmap symbol.
+		// double check for hash collisions.
+		if(s->np != dup->np || memcmp(s->p, dup->p, s->np) != 0)
+			sysfatal("dupok hash collision for %s in %s and %s", s->name, s->file, pn);
+	}
+	
 	if(s->type == STEXT) {
 		s->args = rdint(f);
 		s->locals = rdint(f);