deleted file mode 100644
--- a/tools/reorder/Makefile
+++ /dev/null
@@ -1,74 +0,0 @@
-# This Source Code Form is subject to the terms of the Mozilla Public
-# License, v. 2.0. If a copy of the MPL was not distributed with this
-# file, You can obtain one at http://mozilla.org/MPL/2.0/.
-
-# Redefine this to something that makes sense for you.
-MOZ_SRC=/usr/src/seamonkey-clean/mozilla
-MKLINKSCRIPT=$(MOZ_SRC)/config/mklinkscript.pl
-
-ifdef DEBUG
-CFLAGS=-g -Wall
-CXXFLAGS=-g -Wall
-else
-CFLAGS=-O2
-CXXFLAGS=-O2
-endif
-
-ifdef PROFILE
-CFLAGS += -pg -g
-CXXFLAGS += -pg -g
-endif
-
-TARGETS=\
- libmcount.so \
- libcygprof.so \
- addrs2text \
- garope \
- grope \
- histogram \
- mapaddrs \
- rseed \
- test \
- $(NULL)
-
-all: $(TARGETS)
-
-libmcount.so: mcount.c
- $(CC) -shared $(CFLAGS) -o $@ $<
-
-libcygprof.so: cygprof.c
- $(CC) -shared $(CFLAGS) -o $@ $<
-
-addrs2text: addrs2text.o
-
-garope: garope.cpp elf_symbol_table.o elf_utils.o
-grope: grope.cpp elf_symbol_table.o elf_utils.o
-histogram: histogram.cpp elf_symbol_table.o elf_utils.o
-mapaddrs: mapaddrs.cpp elf_symbol_table.o elf_utils.o
-rseed: rseed.c
-elf_symbol_table.o: elf_symbol_table.cpp elf_symbol_table.h elf_utils.h interval_map.h
-elf_utils.o: elf_utils.cpp elf_utils.h
-
-# Build these with -pg so we get profiling info
-TEST_CFLAGS=-ffunction-sections -finstrument-functions -O2
-
-test: test.o mult.o test.ldscript
- $(CXX) -Wl,-T,test.ldscript -O2 -o $@ $^
-
-test.ldscript: test.order $(MKLINKSCRIPT)
- perl $(MKLINKSCRIPT) -o $@ $<
-
-# This should really be generated by one of the fine tools, above. If
-# it hasn't been, create an empty ordering file.
-test.order:
- touch $@
-
-mult.o: mult.c
- $(CC) $(TEST_CFLAGS) -c -o $@ $<
-
-test.o: test.cpp
- $(CXX) $(TEST_CFLAGS) -c -o $@ $<
-
-clean:
- rm -f $(TARGETS) test.ldscript *.o *~ core
-
deleted file mode 100644
--- a/tools/reorder/addrs2text.cpp
+++ /dev/null
@@ -1,33 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-/*
-
- Converts a binary stream of address references to a text stream,
- hexadecimal, newline separated.
-
- */
-
-#include <stdio.h>
-#include <unistd.h>
-
-int
-main(int argc, char *argv[])
-{
- unsigned int buf[1024];
- ssize_t cb;
-
- while ((cb = read(STDIN_FILENO, buf, sizeof buf)) > 0) {
- if (cb % sizeof buf[0])
- fprintf(stderr, "unaligned read\n");
-
- unsigned int *addr = buf;
- unsigned int *limit = buf + (cb / 4);
-
- for (; addr < limit; ++addr)
- printf("%x\n", *addr);
- }
-
- return 0;
-}
deleted file mode 100644
--- a/tools/reorder/cygprof.c
+++ /dev/null
@@ -1,27 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-/*
-
- A stub library to LD_PRELOAD against an image that's been compiled
- with -finstrument-functions. It dumps the address of the function
- that's being entered upon function entry, and the address that's
- being returned to on function exit. Addresses are dumped as binary
- data to stdout.
-
- */
-
-#include <unistd.h>
-
-void
-__cyg_profile_func_enter(void *this_fn, void *call_site)
-{
- write(STDOUT_FILENO, &this_fn, sizeof this_fn);
-}
-
-void
-__cyg_profile_func_exit(void *this_fn, void *call_site)
-{
- write(STDOUT_FILENO, &call_site, sizeof call_site);
-}
deleted file mode 100644
--- a/tools/reorder/elf_symbol_table.cpp
+++ /dev/null
@@ -1,117 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-#include <string>
-#include <fstream>
-#include <errno.h>
-#include <fcntl.h>
-#include <stdlib.h>
-#include <stdio.h>
-#include <unistd.h>
-#include <sys/stat.h>
-
-#include "elf_symbol_table.h"
-#include "elf_utils.h"
-
-int
-elf_symbol_table::init(const char *name)
-{
- // Open the file readonly.
- m_fd = open(name, O_RDONLY);
- if (m_fd < 0) {
- perror(name);
- return m_fd;
- }
-
- // Get its size.
- struct stat statbuf;
- if (fstat(m_fd, &statbuf) < 0) {
- perror(name);
- return -1;
- }
-
- m_size = statbuf.st_size;
-
- // Memory map it.
- m_mapping = mmap(0, m_size, PROT_READ, MAP_SHARED, m_fd, 0);
- if (m_mapping == MAP_FAILED) {
- perror(name);
- return -1;
- }
-
- // Make sure it's an ELF header.
- const Elf32_Ehdr *ehdr = reinterpret_cast<const Elf32_Ehdr *>(m_mapping);
- if (elf_verify_header(ehdr) < 0)
- return -1;
-
- const char *mapping = reinterpret_cast<const char *>(m_mapping);
-
- // Find the section headers
- const Elf32_Shdr *shdrs
- = reinterpret_cast<const Elf32_Shdr *>(mapping + ehdr->e_shoff);
-
- // find the section header string table, .shstrtab
- const Elf32_Shdr *shstrtabsh = shdrs + ehdr->e_shstrndx;
- const char *shstrtab = mapping + shstrtabsh->sh_offset;
-
- // parse the sections we care about
- int shndx = 0;
- const Elf32_Shdr *shlimit = shdrs + ehdr->e_shnum;
- for (const Elf32_Shdr *shdr = shdrs; shdr < shlimit; ++shdr, ++shndx) {
- basic_string<char> name(shstrtab + shdr->sh_name);
- if (name == ".symtab") {
- m_symbols = reinterpret_cast<const Elf32_Sym *>(mapping + shdr->sh_offset);
- m_nsymbols = shdr->sh_size / sizeof(Elf32_Sym);
- }
- else if (name == ".strtab") {
- m_strtab = mapping + shdr->sh_offset;
- }
- else if (name == ".text") {
- m_text_shndx = shndx;
- }
- }
-
- // Parse the symbol table
- const Elf32_Sym *limit = m_symbols + m_nsymbols;
- for (const Elf32_Sym *sym = m_symbols; sym < limit; ++sym) {
- if (is_function(sym)) {
-#ifdef DEBUG
- hex(cout);
- cout << sym->st_value << endl;
-#endif
- m_rsymtab.put(sym->st_value, sym->st_value + sym->st_size, sym);
- }
- }
-
- return 0;
-}
-
-int
-elf_symbol_table::finish()
-{
- if (m_mapping != MAP_FAILED) {
- munmap(m_mapping, m_size);
- m_mapping = MAP_FAILED;
- }
-
- if (m_fd >= 0) {
- close(m_fd);
- m_fd = -1;
- }
-
- return 0;
-}
-
-const Elf32_Sym *
-elf_symbol_table::lookup(unsigned int addr) const
-{
- rsymtab_t::const_iterator result = m_rsymtab.get(addr);
- return result != m_rsymtab.end() ? reinterpret_cast<const Elf32_Sym *>(*result) : 0;
-}
-
-const char *
-elf_symbol_table::get_symbol_name(const Elf32_Sym *sym) const
-{
- return m_strtab + sym->st_name;
-}
deleted file mode 100644
--- a/tools/reorder/elf_symbol_table.h
+++ /dev/null
@@ -1,82 +0,0 @@
-/* -*- Mode: C++ -*- */
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-#ifndef elf_symbol_table_h__
-#define elf_symbol_table_h__
-
-/*
-
- Utility class for reading ELF symbol tables.
-
- */
-
-#include <elf.h>
-#include <sys/mman.h>
-
-#include "interval_map.h"
-
-class elf_symbol_table {
-protected:
- int m_fd;
- void *m_mapping;
- size_t m_size;
- const char *m_strtab;
- const Elf32_Sym *m_symbols;
- int m_nsymbols;
- int m_text_shndx;
-
- typedef interval_map<unsigned int, const Elf32_Sym *> rsymtab_t;
- rsymtab_t m_rsymtab;
-
- int verify_elf_header(const Elf32_Ehdr *hdr);
- int finish();
-
-public:
- elf_symbol_table()
- : m_fd(-1),
- m_mapping(MAP_FAILED),
- m_size(0),
- m_strtab(0),
- m_symbols(0),
- m_nsymbols(0),
- m_text_shndx(0) {}
-
- ~elf_symbol_table() { finish(); }
-
- /**
- * Read the symbol table information from the specified file. (This will
- * memory-map the file.)
- *
- * Currently, only symbols from the `.text' section are loaded.
- */
- int init(const char *file);
-
- /**
- * Determine what symbol the specified image address corresponds
- * to. Addresses need not refer to a symbol's start address:
- * symbol size information is used to reverse-map the address.
- */
- const Elf32_Sym *lookup(unsigned int addr) const;
-
- /**
- * Determine the symbol name for the specified symbol.
- */
- const char *get_symbol_name(const Elf32_Sym *sym) const;
-
- /**
- * Return `true' if the specified symbol is a function.
- */
- bool is_function(const Elf32_Sym *sym) const {
- return (sym->st_size > 0) &&
- (ELF32_ST_TYPE(sym->st_info) == STT_FUNC) &&
- (sym->st_shndx == m_text_shndx); }
-
- typedef const Elf32_Sym *const_iterator;
-
- const_iterator begin() const { return const_iterator(m_symbols); }
- const_iterator end() const { return const_iterator(m_symbols + m_nsymbols); }
-};
-
-#endif // elf_symbol_table_h__
deleted file mode 100644
--- a/tools/reorder/elf_utils.cpp
+++ /dev/null
@@ -1,36 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-#include <fstream>
-#include "elf_utils.h"
-
-int
-elf_verify_header(const Elf32_Ehdr *hdr)
-{
- if (hdr->e_ident[EI_MAG0] != ELFMAG0
- || hdr->e_ident[EI_MAG1] != ELFMAG1
- || hdr->e_ident[EI_MAG2] != ELFMAG2
- || hdr->e_ident[EI_MAG3] != ELFMAG3) {
- cerr << "not an elf file" << endl;
- return -1;
- }
-
- if (hdr->e_ident[EI_CLASS] != ELFCLASS32) {
- cerr << "not a 32-bit elf file" << endl;
- return -1;
- }
-
- if (hdr->e_ident[EI_DATA] != ELFDATA2LSB) {
- cerr << "not a little endian elf file" << endl;
- return -1;
- }
-
- if (hdr->e_ident[EI_VERSION] != EV_CURRENT) {
- cerr << "incompatible version" << endl;
- return -1;
- }
-
- return 0;
-}
-
deleted file mode 100644
--- a/tools/reorder/elf_utils.h
+++ /dev/null
@@ -1,23 +0,0 @@
-/* -*- Mode: C++ -*- */
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-#ifndef elf_utils_h__
-#define elf_utils_h__
-
-/*
-
- Random utilities for twiddling ELF files.
-
- */
-
-#include "elf.h"
-
-/**
- * Verify that an ELF header is sane. Currently hard-coded to x86.
- */
-int
-elf_verify_header(const Elf32_Ehdr *hdr);
-
-#endif
deleted file mode 100755
--- a/tools/reorder/func-by-addr.sh
+++ /dev/null
@@ -1,18 +0,0 @@
-#!/bin/sh
-#
-# This Source Code Form is subject to the terms of the Mozilla Public
-# License, v. 2.0. If a copy of the MPL was not distributed with this
-# file, You can obtain one at http://mozilla.org/MPL/2.0/.
-#
-# Print the code symbols from an ELF file.
-#
-
-# Find the text segment by searching through the section headers
-TEXT=`readelf --section-headers $1 | awk '$2 == ".text" { print $1; }' | sed -e 's/\[//g' -e 's/\]//g'`
-
-# Now print all of the FUNC-type symbols in the text segment, including
-# address, size, and symbol name.
-readelf --syms $1 |
- awk "\$4 == \"FUNC\" && \$7 == \"${TEXT}\" { printf \"%s %8d %s\n\", \$2, \$3, \$8; }" |
- sort -u
-
deleted file mode 100644
--- a/tools/reorder/garope.cpp
+++ /dev/null
@@ -1,765 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-/*
-
- A program that attempts to find an optimal function ordering for an
- executable using a genetic algorithm whose fitness function is
- computed using runtime profile information.
-
- The fitness function was inspired by Nat Friedman's <nat@nat.org>
- work on `grope':
-
- _GNU Rope - A Subroutine Position Optimizer_
- <http://www.hungry.com/~shaver/grope/grope.ps>
-
- Brendan Eich <brendan@mozilla.org> told me tales about Scott Furman
- doing something like this, which sort of made me want to try it.
-
- As far as I can tell, it would take a lot of computers a lot of time
- to actually find something useful on a non-trivial program using
- this.
-
- */
-
-#include <assert.h>
-#include <fstream>
-#include <hash_map>
-#include <vector>
-#include <limits.h>
-#include <unistd.h>
-#include <stdio.h>
-#include <fcntl.h>
-
-#include "elf_symbol_table.h"
-
-#define _GNU_SOURCE
-#include <getopt.h>
-
-#define PAGE_SIZE 4096
-#define SYMBOL_ALIGN 4
-
-//----------------------------------------------------------------------
-
-class call_pair
-{
-public:
- const Elf32_Sym *m_lo;
- const Elf32_Sym *m_hi;
-
- call_pair(const Elf32_Sym *site1, const Elf32_Sym *site2)
- {
- if (site1 < site2) {
- m_lo = site1;
- m_hi = site2;
- }
- else {
- m_hi = site1;
- m_lo = site2;
- }
- }
-
- friend bool
- operator==(const call_pair &lhs, const call_pair &rhs)
- {
- return (lhs.m_lo == rhs.m_lo) && (lhs.m_hi == rhs.m_hi);
- }
-};
-
-// Straight outta plhash.c!
-#define GOLDEN_RATIO 0x9E3779B9U
-
-template<>
-struct hash<call_pair>
-{
- size_t operator()(const call_pair &pair) const
- {
- size_t h = (reinterpret_cast<size_t>(pair.m_hi) >> 4);
- h += (reinterpret_cast<size_t>(pair.m_lo) >> 4);
- h *= GOLDEN_RATIO;
- return h;
- }
-};
-
-//----------------------------------------------------------------------
-
-struct hash<const Elf32_Sym *>
-{
- size_t operator()(const Elf32_Sym *sym) const
- {
- return (reinterpret_cast<size_t>(sym) >> 4) * GOLDEN_RATIO;
- }
-};
-
-//----------------------------------------------------------------------
-
-typedef hash_map<call_pair, unsigned int> call_graph_t;
-call_graph_t call_graph;
-
-typedef hash_map<const Elf32_Sym *, unsigned int> histogram_t;
-histogram_t histogram;
-long long total_calls = 0;
-
-elf_symbol_table symtab;
-
-bool opt_debug = false;
-int opt_generations = 10;
-int opt_mutate = 0;
-const char *opt_out = "order.out";
-int opt_population_size = 100;
-int opt_tick = 0;
-bool opt_verbose = false;
-int opt_window = 0;
-
-static struct option long_options[] = {
- { "debug", no_argument, 0, 'd' },
- { "exe", required_argument, 0, 'e' },
- { "generations", required_argument, 0, 'g' },
- { "help", no_argument, 0, '?' },
- { "mutate", required_argument, 0, 'm' },
- { "out", required_argument, 0, 'o' },
- { "population", required_argument, 0, 'p' },
- { "seed", required_argument, 0, 's' },
- { "tick", optional_argument, 0, 't' },
- { "verbose", no_argument, 0, 'v' },
- { "window", required_argument, 0, 'w' },
- { 0, 0, 0, 0 }
-};
-
-//----------------------------------------------------------------------
-
-static long long
-llrand()
-{
- long long result;
- result = (long long) rand();
- result *= (long long) (unsigned int) (RAND_MAX + 1);
- result += (long long) rand();
- return result;
-}
-
-//----------------------------------------------------------------------
-
-class symbol_order {
-public:
- typedef vector<const Elf32_Sym *> vector_t;
- typedef long long score_t;
-
- static const score_t max_score;
-
- /**
- * A vector of symbols that is this ordering.
- */
- vector_t m_ordering;
-
- /**
- * The symbol ordering's score.
- */
- score_t m_score;
-
- symbol_order() : m_score(0) {}
-
- /**
- * ``Shuffle'' a symbol ordering, randomizing it.
- */
- void shuffle();
-
- /**
- * Initialize this symbol ordering by performing a crossover from
- * two ``parent'' symbol orderings.
- */
- void crossover_from(const symbol_order *father, const symbol_order *mother);
-
- /**
- * Randomly mutate this symbol ordering.
- */
- void mutate();
-
- /**
- * Score a symbol ordering based on paginated locality.
- */
- score_t compute_score_page();
-
- /**
- * Score a symbol ordering based on a sliding window.
- */
- score_t compute_score_window(int window_size);
-
- static score_t compute_score(symbol_order &order);
-
- /**
- * Use the symbol table to dump the ordered symbolic constants.
- */
- void dump_symbols() const;
-
- friend ostream &
- operator<<(ostream &out, const symbol_order &order);
-};
-
-const symbol_order::score_t
-symbol_order::max_score = ~((symbol_order::score_t)1 << ((sizeof(symbol_order::score_t) * 8) - 1));
-
-symbol_order::score_t
-symbol_order::compute_score_page()
-{
- m_score = 0;
-
- unsigned int off = 0; // XXX in reality, probably not page-aligned to start
-
- vector_t::const_iterator end = m_ordering.end(),
- last = end,
- sym = m_ordering.begin();
-
- while (sym != end) {
- vector_t page;
-
- // If we had a symbol that spilled over from the last page,
- // then include it here.
- if (last != end)
- page.push_back(*last);
-
- // Pack symbols into the page
- do {
- page.push_back(*sym);
-
- int size = (*sym)->st_size;
- size += SYMBOL_ALIGN - 1;
- size &= ~(SYMBOL_ALIGN - 1);
-
- off += size;
- } while (++sym != end && off < PAGE_SIZE);
-
- // Remember if there was spill-over.
- off %= PAGE_SIZE;
- last = (off != 0) ? sym : end;
-
- // Now score the page as the count of all calls to symbols on
- // the page, less calls between the symbols on the page.
- vector_t::const_iterator page_end = page.end();
- for (vector_t::const_iterator i = page.begin(); i != page_end; ++i) {
- histogram_t::const_iterator func = histogram.find(*i);
- if (func == histogram.end())
- continue;
-
- m_score += func->second;
-
- vector_t::const_iterator j = i;
- for (++j; j != page_end; ++j) {
- call_graph_t::const_iterator call =
- call_graph.find(call_pair(*i, *j));
-
- if (call != call_graph.end())
- m_score -= call->second;
- }
- }
- }
-
- assert(m_score >= 0);
-
- // Integer reciprocal so we minimize instead of maximize.
- if (m_score == 0)
- m_score = 1;
-
- m_score = (total_calls / m_score) + 1;
-
- return m_score;
-}
-
-symbol_order::score_t
-symbol_order::compute_score_window(int window_size)
-{
- m_score = 0;
-
- vector_t::const_iterator *window = new vector_t::const_iterator[window_size];
- int window_fill = 0;
-
- vector_t::const_iterator end = m_ordering.end(),
- sym = m_ordering.begin();
-
- for (; sym != end; ++sym) {
- histogram_t::const_iterator func = histogram.find(*sym);
- if (func != histogram.end()) {
- long long scale = ((long long) 1) << window_size;
-
- m_score += func->second * scale * 2;
-
- vector_t::const_iterator *limit = window + window_fill;
- vector_t::const_iterator *iter;
- for (iter = window ; iter < limit; ++iter) {
- call_graph_t::const_iterator call =
- call_graph.find(call_pair(*sym, **iter));
-
- if (call != call_graph.end())
- m_score -= (call->second * scale);
-
- scale >>= 1;
- }
- }
-
- // Slide the window.
- vector_t::const_iterator *begin = window;
- vector_t::const_iterator *iter;
- for (iter = window + (window_size - 1); iter > begin; --iter)
- *iter = *(iter - 1);
-
- if (window_fill < window_size)
- ++window_fill;
-
- *window = sym;
- }
-
- delete[] window;
-
- assert(m_score >= 0);
-
- // Integer reciprocal so we minimize instead of maximize.
- if (m_score == 0)
- m_score = 1;
-
- m_score = (total_calls / m_score) + 1;
-
- return m_score;
-}
-
-symbol_order::score_t
-symbol_order::compute_score(symbol_order &order)
-{
- if (opt_window)
- return order.compute_score_window(opt_window);
-
- return order.compute_score_page();
-}
-
-void
-symbol_order::shuffle()
-{
- vector_t::iterator sym = m_ordering.begin();
- vector_t::iterator end = m_ordering.end();
- for (; sym != end; ++sym) {
- int i = rand() % m_ordering.size();
- const Elf32_Sym *temp = *sym;
- *sym = m_ordering[i];
- m_ordering[i] = temp;
- }
-}
-
-void
-symbol_order::crossover_from(const symbol_order *father, const symbol_order *mother)
-{
- histogram_t used;
-
- m_ordering = vector_t(father->m_ordering.size(), 0);
-
- vector_t::const_iterator parent_sym = father->m_ordering.begin();
- vector_t::iterator sym = m_ordering.begin();
- vector_t::iterator end = m_ordering.end();
-
- for (; sym != end; ++sym, ++parent_sym) {
- if (rand() % 2) {
- *sym = *parent_sym;
- used[*parent_sym] = 1;
- }
- }
-
- parent_sym = mother->m_ordering.begin();
- sym = m_ordering.begin();
-
- for (; sym != end; ++sym) {
- if (! *sym) {
- while (used[*parent_sym])
- ++parent_sym;
-
- *sym = *parent_sym++;
- }
- }
-}
-
-void
-symbol_order::mutate()
-{
- int i, j;
- i = rand() % m_ordering.size();
- j = rand() % m_ordering.size();
-
- const Elf32_Sym *temp = m_ordering[i];
- m_ordering[i] = m_ordering[j];
- m_ordering[j] = temp;
-}
-
-void
-symbol_order::dump_symbols() const
-{
- ofstream out(opt_out);
-
- vector_t::const_iterator sym = m_ordering.begin();
- vector_t::const_iterator end = m_ordering.end();
- for (; sym != end; ++sym)
- out << symtab.get_symbol_name(*sym) << endl;
-
- out.close();
-}
-
-ostream &
-operator<<(ostream &out, const symbol_order &order)
-{
- out << "symbol_order(" << order.m_score << ") ";
-
- symbol_order::vector_t::const_iterator sym = order.m_ordering.begin();
- symbol_order::vector_t::const_iterator end = order.m_ordering.end();
- for (; sym != end; ++sym)
- out.form("%08x ", *sym);
-
- out << endl;
-
- return out;
-}
-
-//----------------------------------------------------------------------
-
-static void
-usage(const char *name)
-{
- cerr << "usage: " << name << " [options] [<file> ...]" << endl;
- cerr << " Options:" << endl;
- cerr << " --debug, -d" << endl;
- cerr << " Print lots of verbose debugging cruft." << endl;
- cerr << " --exe=<image>, -e <image> (required)" << endl;
- cerr << " Specify the executable image from which to read symbol information." << endl;
- cerr << " --generations=<num>, -g <num>" << endl;
- cerr << " Specify the number of generations to run the GA (default is 10)." << endl;
- cerr << " --help, -?" << endl;
- cerr << " Print this message and exit." << endl;
- cerr << " --mutate=<num>, -m <num>" << endl;
- cerr << " Mutate every <num>th individual, or zero for no mutation (default)." << endl;
- cerr << " --out=<file>, -o <file>" << endl;
- cerr << " Specify the output file to which to dump the symbol ordering of the" << endl;
- cerr << " best individual (default is `order.out')." << endl;
- cerr << " --population=<num>, -p <num>" << endl;
- cerr << " Set the population size to <num> individuals (default is 100)." << endl;
- cerr << " --seed=<num>, -s <num>" << endl;
- cerr << " Specify a seed to srand()." << endl;
- cerr << " --tick[=<num>], -t [<num>]" << endl;
- cerr << " When reading address data, print a dot to stderr every <num>th" << endl;
- cerr << " address processed from the call trace. If specified with no argument," << endl;
- cerr << " a dot will be printed for every million addresses processed." << endl;
- cerr << " --verbose, -v" << endl;
- cerr << " Issue progress messages to stderr." << endl;
- cerr << " --window=<num>, -w <num>" << endl;
- cerr << " Use a sliding window instead of pagination to score orderings." << endl;
- cerr << endl;
- cerr << "This program uses a genetic algorithm to produce an `optimal' ordering for" << endl;
- cerr << "an executable based on call patterns." << endl;
- cerr << endl;
- cerr << "Addresses from a call trace are read as binary data from the files" << endl;
- cerr << "specified, or from stdin if no files are specified. These addresses" << endl;
- cerr << "are used with the symbolic information from the executable to create" << endl;
- cerr << "a call graph. This call graph is used to `score' arbitrary symbol" << endl;
- cerr << "orderings, and provides the fitness function for the GA." << endl;
- cerr << endl;
-}
-
-/**
- * Using the symbol table, map a stream of address references into a
- * callgraph and a histogram.
- */
-static void
-map_addrs(int fd)
-{
- const Elf32_Sym *last = 0;
- unsigned int buf[128];
- ssize_t cb;
-
- unsigned int count = 0;
- while ((cb = read(fd, buf, sizeof buf)) > 0) {
- if (cb % sizeof buf[0])
- fprintf(stderr, "unaligned read\n");
-
- unsigned int *addr = buf;
- unsigned int *limit = buf + (cb / 4);
-
- for (; addr < limit; ++addr) {
- const Elf32_Sym *sym = symtab.lookup(*addr);
-
- if (last && sym && last != sym) {
- ++total_calls;
- ++histogram[sym];
- ++call_graph[call_pair(last, sym)];
-
- if (opt_tick && (++count % opt_tick == 0)) {
- cerr << ".";
- flush(cerr);
- }
- }
-
- last = sym;
- }
- }
-
- if (opt_tick)
- cerr << endl;
-
- cerr << "Total calls: " << total_calls << endl;
- total_calls *= 1024;
-
- if (opt_window)
- total_calls <<= (opt_window + 1);
-}
-
-static symbol_order *
-pick_parent(symbol_order *ordering, int max, int index)
-{
- while (1) {
- index -= ordering->m_score;
- if (index < 0)
- break;
-
- ++ordering;
- }
-
- return ordering;
-}
-
-/**
- * The main program
- */
-int
-main(int argc, char *argv[])
-{
- const char *opt_exe = 0;
-
- int c;
- while (1) {
- int option_index = 0;
- c = getopt_long(argc, argv, "?de:g:m:o:p:s:t:vw:", long_options, &option_index);
-
- if (c < 0)
- break;
-
- switch (c) {
- case '?':
- usage(argv[0]);
- return 0;
-
- case 'd':
- opt_debug = true;
- break;
-
- case 'e':
- opt_exe = optarg;
- break;
-
- case 'g':
- opt_generations = atoi(optarg);
- break;
-
- case 'm':
- opt_mutate = atoi(optarg);
- break;
-
- case 'o':
- opt_out = optarg;
- break;
-
- case 'p':
- opt_population_size = atoi(optarg);
- break;
-
- case 's':
- srand(atoi(optarg));
- break;
-
- case 't':
- opt_tick = optarg ? atoi(optarg) : 1000000;
- break;
-
- case 'v':
- opt_verbose = true;
- break;
-
- case 'w':
- opt_window = atoi(optarg);
- if (opt_window < 0 || opt_window > 8) {
- cerr << "invalid window size: " << opt_window << endl;
- return 1;
- }
-
- break;
-
- default:
- usage(argv[0]);
- return 1;
- }
- }
-
- // Make sure an image was specified
- if (! opt_exe) {
- usage(argv[0]);
- return 1;
- }
-
- // Read the sym table.
- symtab.init(opt_exe);
-
- // Process addresses to construct the call graph.
- if (optind >= argc) {
- map_addrs(STDIN_FILENO);
- }
- else {
- do {
- int fd = open(argv[optind], O_RDONLY);
- if (fd < 0) {
- perror(argv[optind]);
- return 1;
- }
-
- map_addrs(fd);
- close(fd);
- } while (++optind < argc);
- }
-
- if (opt_debug) {
- cerr << "Call graph:" << endl;
-
- call_graph_t::const_iterator limit = call_graph.end();
- call_graph_t::const_iterator i;
- for (i = call_graph.begin(); i != limit; ++i) {
- const call_pair& pair = i->first;
- cerr.form("%08x %08x %10d\n",
- pair.m_lo->st_value,
- pair.m_hi->st_value,
- i->second);
- }
- }
-
- // Collect the symbols into a vector
- symbol_order::vector_t ordering;
- elf_symbol_table::const_iterator end = symtab.end();
- for (elf_symbol_table::const_iterator sym = symtab.begin(); sym != end; ++sym) {
- if (symtab.is_function(sym))
- ordering.push_back(sym);
- }
-
- if (opt_verbose) {
- symbol_order initial;
- initial.m_ordering = ordering;
- cerr << "created initial ordering, score=" << symbol_order::compute_score(initial) << endl;
-
- if (opt_debug)
- cerr << initial;
- }
-
- // Create a population.
- if (opt_verbose)
- cerr << "creating population" << endl;
-
- symbol_order *population = new symbol_order[opt_population_size];
-
- symbol_order::score_t total = 0, min = symbol_order::max_score, max = 0;
-
- // Score it.
- symbol_order *order = population;
- symbol_order *limit = population + opt_population_size;
- for (; order < limit; ++order) {
- order->m_ordering = ordering;
- order->shuffle();
-
- symbol_order::score_t score = symbol_order::compute_score(*order);
-
- if (opt_debug)
- cerr << *order;
-
- if (min > score)
- min = score;
- if (max < score)
- max = score;
-
- total += score;
- }
-
- if (opt_verbose) {
- cerr << "Initial population";
- cerr << ": min=" << min;
- cerr << ", max=" << max;
- cerr << " mean=" << (total / opt_population_size);
- cerr << endl;
- }
-
-
- // Run the GA.
- if (opt_verbose)
- cerr << "begininng ga" << endl;
-
- symbol_order::score_t best = 0;
-
- for (int generation = 1; generation <= opt_generations; ++generation) {
- // Create a new population.
- symbol_order *offspring = new symbol_order[opt_population_size];
-
- symbol_order *kid = offspring;
- symbol_order *offspring_limit = offspring + opt_population_size;
- for (; kid < offspring_limit; ++kid) {
- // Pick parents.
- symbol_order *father, *mother;
- father = pick_parent(population, max, llrand() % total);
- mother = pick_parent(population, max, llrand() % total);
-
- // Create a kid.
- kid->crossover_from(father, mother);
-
- // Mutate, possibly.
- if (opt_mutate) {
- if (rand() % opt_mutate == 0)
- kid->mutate();
- }
- }
-
- delete[] population;
- population = offspring;
-
- // Score the new population.
- total = 0;
- min = symbol_order::max_score;
- max = 0;
-
- symbol_order *fittest = 0;
-
- limit = offspring_limit;
- for (order = population; order < limit; ++order) {
- symbol_order::score_t score = symbol_order::compute_score(*order);
-
- if (opt_debug)
- cerr << *order;
-
- if (min > score)
- min = score;
-
- if (max < score)
- max = score;
-
- if (best < score) {
- best = score;
- fittest = order;
- }
-
- total += score;
- }
-
- if (opt_verbose) {
- cerr << "Generation " << generation;
- cerr << ": min=" << min;
- cerr << ", max=" << max;
- if (fittest)
- cerr << "*";
- cerr << " mean=" << (total / opt_population_size);
- cerr << endl;
- }
-
- // If we've found a new ``best'' individual, dump it.
- if (fittest)
- fittest->dump_symbols();
- }
-
- delete[] population;
- return 0;
-}
deleted file mode 100644
--- a/tools/reorder/grope.cpp
+++ /dev/null
@@ -1,532 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-/*
-
- A program that computes a function ordering for an executable based
- on runtime profile information.
-
- This program is directly based on work done by Roger Chickering
- <rogc@netscape.com> in
-
- <http://bugzilla.mozilla.org/show_bug.cgi?id=65845>
-
- to implement Nat Friedman's <nat@nat.org> `grope',
-
- _GNU Rope - A Subroutine Position Optimizer_
- <http://www.hungry.com/~shaver/grope/grope.ps>
-
- Specifically, it implements the procedure re-ordering algorithm
- described in:
-
- K. Pettis and R. Hansen. ``Profile-Guided Core Position.'' In
- _Proceedings of the Int. Conference on Programming Language Design
- and Implementation_, pages 16-27, June 1990.
-
- */
-
-#include <assert.h>
-#include <fstream>
-#include <hash_set>
-#include <map>
-#include <set>
-#include <list>
-#include <vector>
-#include <limits.h>
-#include <unistd.h>
-#include <stdio.h>
-#include <fcntl.h>
-
-#include "elf_symbol_table.h"
-
-#define _GNU_SOURCE
-#include <getopt.h>
-
-elf_symbol_table symtab;
-
-// Straight outta plhash.c!
-#define GOLDEN_RATIO 0x9E3779B9U
-
-struct hash<const Elf32_Sym *>
-{
- size_t operator()(const Elf32_Sym *sym) const {
- return (reinterpret_cast<size_t>(sym) >> 4) * GOLDEN_RATIO; }
-};
-
-typedef unsigned int call_count_t;
-
-struct call_graph_arc
-{
- const Elf32_Sym *m_from;
- const Elf32_Sym *m_to;
- call_count_t m_count;
-
- call_graph_arc(const Elf32_Sym *left, const Elf32_Sym *right, call_count_t count = 0)
- : m_count(count)
- {
- assert(left != right);
-
- if (left > right) {
- m_from = left;
- m_to = right;
- }
- else {
- m_from = right;
- m_to = left;
- }
- }
-
- friend bool
- operator==(const call_graph_arc &lhs, const call_graph_arc &rhs)
- {
- return (lhs.m_from == rhs.m_from) && (lhs.m_to == rhs.m_to);
- }
-
- friend ostream &
- operator<<(ostream &out, const call_graph_arc &arc)
- {
- out << &arc << ": ";
- out.form("<(%s %s) %d>",
- symtab.get_symbol_name(arc.m_from),
- symtab.get_symbol_name(arc.m_to),
- arc.m_count);
-
- return out;
- }
-};
-
-struct hash<call_graph_arc *>
-{
- size_t
- operator()(const call_graph_arc* arc) const
- {
- size_t result;
- result = reinterpret_cast<unsigned long>(arc->m_from);
- result ^= reinterpret_cast<unsigned long>(arc->m_to) >> 16;
- result ^= reinterpret_cast<unsigned long>(arc->m_to) << 16;
- result *= GOLDEN_RATIO;
- return result;
- }
-};
-
-struct equal_to<call_graph_arc *>
-{
- bool
- operator()(const call_graph_arc* lhs, const call_graph_arc *rhs) const
- {
- return *lhs == *rhs;
- }
-};
-
-typedef hash_set<call_graph_arc *> arc_container_t;
-arc_container_t arcs;
-
-typedef multimap<const Elf32_Sym *, call_graph_arc *> arc_map_t;
-arc_map_t from_map;
-arc_map_t to_map;
-
-struct less_call_graph_arc_count
-{
- bool
- operator()(const call_graph_arc *lhs, const call_graph_arc *rhs) const
- {
- if (lhs->m_count == rhs->m_count) {
- if (lhs->m_from == rhs->m_from)
- return lhs->m_to > rhs->m_to;
-
- return lhs->m_from > rhs->m_from;
- }
- return lhs->m_count > rhs->m_count;
- }
-};
-
-typedef set<call_graph_arc *, less_call_graph_arc_count> arc_count_index_t;
-
-bool opt_debug = false;
-const char *opt_out = "order.out";
-int opt_tick = 0;
-bool opt_verbose = false;
-int opt_window = 16;
-
-static struct option long_options[] = {
- { "debug", no_argument, 0, 'd' },
- { "exe", required_argument, 0, 'e' },
- { "help", no_argument, 0, '?' },
- { "out", required_argument, 0, 'o' },
- { "tick", optional_argument, 0, 't' },
- { "verbose", no_argument, 0, 'v' },
- { "window", required_argument, 0, 'w' },
- { 0, 0, 0, 0 }
-};
-
-//----------------------------------------------------------------------
-
-static void
-usage(const char *name)
-{
- cerr << "usage: " << name << " [options] [<file> ...]" << endl;
- cerr << " Options:" << endl;
- cerr << " --debug, -d" << endl;
- cerr << " Print lots of verbose debugging cruft." << endl;
- cerr << " --exe=<image>, -e <image> (required)" << endl;
- cerr << " Specify the executable image from which to read symbol information." << endl;
- cerr << " --help, -?" << endl;
- cerr << " Print this message and exit." << endl;
- cerr << " --out=<file>, -o <file>" << endl;
- cerr << " Specify the output file to which to dump the symbol ordering of the" << endl;
- cerr << " best individual (default is `order.out')." << endl;
- cerr << " --tick[=<num>], -t [<num>]" << endl;
- cerr << " When reading address data, print a dot to stderr every <num>th" << endl;
- cerr << " address processed from the call trace. If specified with no argument," << endl;
- cerr << " a dot will be printed for every million addresses processed." << endl;
- cerr << " --verbose, -v" << endl;
- cerr << " Issue progress messages to stderr." << endl;
- cerr << " --window=<num>, -w <num>" << endl;
- cerr << " Use a sliding window instead of pagination to score orderings." << endl;
-}
-
-/**
- * Using the symbol table, map a stream of address references into a
- * callgraph.
- */
-static void
-map_addrs(int fd)
-{
- long long total_calls = 0;
- typedef list<const Elf32_Sym *> window_t;
-
- window_t window;
- int window_size = 0;
- unsigned int buf[128];
- ssize_t cb;
-
- while ((cb = read(fd, buf, sizeof buf)) > 0) {
- if (cb % sizeof buf[0])
- fprintf(stderr, "unaligned read\n");
-
- unsigned int *addr = buf;
- unsigned int *limit = buf + (cb / 4);
-
- for (; addr < limit; ++addr) {
- const Elf32_Sym *sym = symtab.lookup(*addr);
- if (! sym)
- continue;
-
- ++total_calls;
-
- window.push_front(sym);
-
- if (window_size >= opt_window)
- window.pop_back();
- else
- ++window_size;
-
- window_t::const_iterator i = window.begin();
- window_t::const_iterator end = window.end();
- for (; i != end; ++i) {
- if (sym != *i) {
- call_graph_arc *arc;
- call_graph_arc key(sym, *i);
- arc_container_t::iterator iter = arcs.find(&key);
- if (iter == arcs.end()) {
- arc = new call_graph_arc(sym, *i);
- arcs.insert(arc);
- from_map.insert(arc_map_t::value_type(arc->m_from, arc));
- to_map.insert(arc_map_t::value_type(arc->m_to, arc));
- }
- else
- arc = const_cast<call_graph_arc *>(*iter);
-
- ++(arc->m_count);
- }
- }
-
- if (opt_verbose && opt_tick && (total_calls % opt_tick == 0)) {
- cerr << ".";
- flush(cerr);
- }
- }
- }
-
- if (opt_verbose) {
- if (opt_tick)
- cerr << endl;
-
- cerr << "Total calls: " << total_calls << endl;
- }
-}
-
-static void
-remove_from(arc_map_t& map, const Elf32_Sym *sym, const call_graph_arc *arc)
-{
- pair<arc_map_t::iterator, arc_map_t::iterator> p
- = map.equal_range(sym);
-
- for (arc_map_t::iterator i = p.first; i != p.second; ++i) {
- if (i->second == arc) {
- map.erase(i);
- break;
- }
- }
-}
-
-/**
- * The main program
- */
-int
-main(int argc, char *argv[])
-{
- const char *opt_exe = 0;
-
- int c;
- while (1) {
- int option_index = 0;
- c = getopt_long(argc, argv, "?de:o:t:vw:", long_options, &option_index);
-
- if (c < 0)
- break;
-
- switch (c) {
- case '?':
- usage(argv[0]);
- return 0;
-
- case 'd':
- opt_debug = true;
- break;
-
- case 'e':
- opt_exe = optarg;
- break;
-
- case 'o':
- opt_out = optarg;
- break;
-
- case 't':
- opt_tick = optarg ? atoi(optarg) : 1000000;
- break;
-
- case 'v':
- opt_verbose = true;
- break;
-
- case 'w':
- opt_window = atoi(optarg);
- if (opt_window <= 0) {
- cerr << "invalid window size: " << opt_window << endl;
- return 1;
- }
- break;
-
- default:
- usage(argv[0]);
- return 1;
- }
- }
-
- // Make sure an image was specified
- if (! opt_exe) {
- usage(argv[0]);
- return 1;
- }
-
- // Read the sym table.
- symtab.init(opt_exe);
-
- // Process addresses to construct the weighted call graph.
- if (optind >= argc) {
- map_addrs(STDIN_FILENO);
- }
- else {
- do {
- int fd = open(argv[optind], O_RDONLY);
- if (fd < 0) {
- perror(argv[optind]);
- return 1;
- }
-
- map_addrs(fd);
- close(fd);
- } while (++optind < argc);
- }
-
- // Emit the ordering.
- ofstream out(opt_out);
-
- // Collect all of the arcs into a sorted container, with arcs
- // having the largest weight at the front.
- arc_count_index_t sorted_arcs(arcs.begin(), arcs.end());
-
- while (sorted_arcs.size()) {
- if (opt_debug) {
- cerr << "==========================================" << endl << endl;
-
- cerr << "Sorted Arcs:" << endl;
- for (arc_count_index_t::const_iterator iter = sorted_arcs.begin();
- iter != sorted_arcs.end();
- ++iter) {
- cerr << **iter << endl;
- }
-
- cerr << endl << "Arc Container:" << endl;
- for (arc_container_t::const_iterator iter = arcs.begin();
- iter != arcs.end();
- ++iter) {
- cerr << **iter << endl;
- }
-
- cerr << endl << "From Map:" << endl;
- for (arc_map_t::const_iterator iter = from_map.begin();
- iter != from_map.end();
- ++iter) {
- cerr << symtab.get_symbol_name(iter->first) << ": " << *(iter->second) << endl;
- }
-
- cerr << endl << "To Map:" << endl;
- for (arc_map_t::const_iterator iter = to_map.begin();
- iter != to_map.end();
- ++iter) {
- cerr << symtab.get_symbol_name(iter->first) << ": " << *(iter->second) << endl;
- }
-
- cerr << endl;
- }
-
- // The first arc in the sorted set will have the largest
- // weight. Pull it out, and emit its sink.
- arc_count_index_t::iterator max = sorted_arcs.begin();
- call_graph_arc *arc = const_cast<call_graph_arc *>(*max);
-
- sorted_arcs.erase(max);
-
- if (opt_debug)
- cerr << "pulling " << *arc << endl;
-
- arcs.erase(arc);
- remove_from(from_map, arc->m_from, arc);
- remove_from(to_map, arc->m_to, arc);
-
- out << symtab.get_symbol_name(arc->m_to) << endl;
-
- // Merge arc->m_to into arc->m_from. First, modify anything
- // that used to point to arc->m_to to point to arc->m_from.
- typedef list<call_graph_arc *> arc_list_t;
- arc_list_t map_add_queue;
-
- pair<arc_map_t::iterator, arc_map_t::iterator> p;
-
- // Find all the arcs that point to arc->m_to.
- p = to_map.equal_range(arc->m_to);
- for (arc_map_t::iterator i = p.first; i != p.second; ++i) {
- // Remove the arc that points to arc->m_to (`doomed') from
- // all of our indicies.
- call_graph_arc *doomed = i->second;
- const Elf32_Sym *source = doomed->m_from;
-
- sorted_arcs.erase(doomed);
- arcs.erase(doomed);
- remove_from(from_map, source, doomed);
- // N.B. that `doomed' will be removed from the `to_map'
- // after the loop completes.
-
- // Create a new (or locate an existing) arc whose source
- // was the doomed arc's source, and whose sink is
- // arc->m_from (i.e., the node that subsumed arc->m_to).
- call_graph_arc *merge;
- call_graph_arc key = call_graph_arc(source, arc->m_from);
- arc_container_t::iterator iter = arcs.find(&key);
-
- if (iter == arcs.end()) {
- merge = new call_graph_arc(source, arc->m_from);
-
- arcs.insert(merge);
- from_map.insert(arc_map_t::value_type(merge->m_from, merge));
- map_add_queue.push_back(merge);
- }
- else {
- // We found an existing arc: temporarily remove it
- // from the sorted index.
- merge = const_cast<call_graph_arc *>(*iter);
- sorted_arcs.erase(merge);
- }
-
- // Include the doomed arc's weight in the merged arc, and
- // (re-)insert it into the sorted index.
- merge->m_count += doomed->m_count;
- sorted_arcs.insert(merge);
-
- delete doomed;
- }
-
- to_map.erase(p.first, p.second);
-
- for (arc_list_t::iterator merge = map_add_queue.begin();
- merge != map_add_queue.end();
- map_add_queue.erase(merge++)) {
- to_map.insert(arc_map_t::value_type((*merge)->m_to, *merge));
- }
-
- // Now, roll anything that arc->m_to used to point at into
- // what arc->m_from now points at.
-
- // Collect all of the arcs that originate at arc->m_to.
- p = from_map.equal_range(arc->m_to);
- for (arc_map_t::iterator i = p.first; i != p.second; ++i) {
- // Remove the arc originating from arc->m_to (`doomed')
- // from all of our indicies.
- call_graph_arc *doomed = i->second;
- const Elf32_Sym *sink = doomed->m_to;
-
- // There shouldn't be any self-referential arcs.
- assert(sink != arc->m_to);
-
- sorted_arcs.erase(doomed);
- arcs.erase(doomed);
- remove_from(to_map, sink, doomed);
- // N.B. that `doomed' will be removed from the `from_map'
- // once the loop completes.
-
- // Create a new (or locate an existing) arc whose source
- // is arc->m_from and whose sink was the removed arc's
- // sink.
- call_graph_arc *merge;
- call_graph_arc key = call_graph_arc(arc->m_from, sink);
- arc_container_t::iterator iter = arcs.find(&key);
-
- if (iter == arcs.end()) {
- merge = new call_graph_arc(arc->m_from, sink);
-
- arcs.insert(merge);
-
- map_add_queue.push_back(merge);
- to_map.insert(arc_map_t::value_type(merge->m_to, merge));
- }
- else {
- // We found an existing arc: temporarily remove it
- // from the sorted index.
- merge = const_cast<call_graph_arc *>(*iter);
- sorted_arcs.erase(merge);
- }
-
- // Include the doomed arc's weight in the merged arc, and
- // (re-)insert it into the sorted index.
- merge->m_count += doomed->m_count;
- sorted_arcs.insert(merge);
-
- delete doomed;
- }
-
- from_map.erase(p.first, p.second);
-
- for (arc_list_t::iterator merge = map_add_queue.begin();
- merge != map_add_queue.end();
- map_add_queue.erase(merge++)) {
- from_map.insert(arc_map_t::value_type((*merge)->m_from, *merge));
- }
- }
-
- out.close();
- return 0;
-}
deleted file mode 100644
--- a/tools/reorder/histogram.cpp
+++ /dev/null
@@ -1,142 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-/*
-
- A program that computes a call histogram from runtime call
- information. It reads a list of address references (e.g., as
- computed by libcygprof.so), and uses an ELF image to map the
- addresses to functions.
-
- */
-
-#include <fstream>
-#include <hash_map>
-#include <limits.h>
-#include <unistd.h>
-#include <stdio.h>
-#include <fcntl.h>
-
-#include "elf_symbol_table.h"
-
-#define _GNU_SOURCE
-#include <getopt.h>
-
-const char *opt_exe;
-int opt_tick = 0;
-
-elf_symbol_table table;
-
-typedef hash_map<unsigned int, unsigned int> histogram_t;
-histogram_t histogram;
-
-static struct option long_options[] = {
- { "exe", required_argument, 0, 'e' },
- { "tick", optional_argument, 0, 't' },
- { 0, 0, 0, 0 }
-};
-
-static void
-usage(const char *name)
-{
- cerr << "usage: " << name << " --exe=<image> [--tick[=count]]" << endl;
-}
-
-static void
-map_addrs(int fd)
-{
- // Read the binary addresses from stdin.
- unsigned int buf[128];
- ssize_t cb;
-
- unsigned int count = 0;
- while ((cb = read(fd, buf, sizeof buf)) > 0) {
- if (cb % sizeof buf[0])
- fprintf(stderr, "unaligned read\n");
-
- unsigned int *addr = buf;
- unsigned int *limit = buf + (cb / 4);
-
- for (; addr < limit; ++addr) {
- const Elf32_Sym *sym = table.lookup(*addr);
- if (sym)
- ++histogram[reinterpret_cast<unsigned int>(sym)];
-
- if (opt_tick && (++count % opt_tick == 0)) {
- cerr << ".";
- flush(cerr);
- }
- }
- }
-
- if (opt_tick)
- cerr << endl;
-}
-
-int
-main(int argc, char *argv[])
-{
- int c;
- while (1) {
- int option_index = 0;
- c = getopt_long(argc, argv, "e:t", long_options, &option_index);
-
- if (c < 0)
- break;
-
- switch (c) {
- case 'e':
- opt_exe = optarg;
- break;
-
- case 't':
- opt_tick = optarg ? atoi(optarg) : 1000000;
- break;
-
- default:
- usage(argv[0]);
- return 1;
- }
- }
-
- if (! opt_exe) {
- usage(argv[0]);
- return 1;
- }
-
- table.init(opt_exe);
-
- // Process addresses.
- if (optind >= argc) {
- map_addrs(STDIN_FILENO);
- }
- else {
- do {
- int fd = open(argv[optind], O_RDONLY);
- if (fd < 0) {
- perror(argv[optind]);
- return 1;
- }
-
- map_addrs(fd);
- close(fd);
- } while (++optind < argc);
- }
-
- // Emit the histogram.
- histogram_t::const_iterator limit = histogram.end();
- histogram_t::const_iterator i;
- for (i = histogram.begin(); i != limit; ++i) {
- const Elf32_Sym *sym = reinterpret_cast<const Elf32_Sym *>(i->first);
- cout.form("%08x %6d %2d %10d ",
- sym->st_value,
- sym->st_size,
- sym->st_shndx,
- i->second);
-
- cout << table.get_symbol_name(sym) << endl;
- }
-
- return 0;
-}
deleted file mode 100644
--- a/tools/reorder/interval_map.h
+++ /dev/null
@@ -1,326 +0,0 @@
-/* -*- Mode: C++ -*- */
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-#ifndef interval_map_h__
-#define interval_map_h__
-
-/*
-
- A utility class that maps an interval to an object, allowing clients
- to look up the object by a point within the interval.
-
- */
-
-// TODO:
-// - removing intervals
-// - container iterators
-
-#include <fstream>
-#include <assert.h>
-
-template<class coord, class T>
-class interval_map {
-protected:
- class const_iterator;
- friend class const_iterator;
-
- struct node {
- T m_data;
- coord m_min;
- coord m_max;
- node *m_before; // intervals before this one
- node *m_within; // intervals within this one
- node *m_after; // intervals after this one
- int m_bal;
- };
-
-public:
- /**
- * A unidirectional const iterator that is used to enumerate the
- * intervals that overlap a specific point.
- */
- class const_iterator {
- protected:
- const node *m_node;
- const coord m_point;
-
- friend class interval_map;
- const_iterator(const node *n, const coord &point)
- : m_node(n), m_point(point) {}
-
- void advance();
-
- public:
- const_iterator() : m_node(0), m_point(0) {}
-
- const_iterator(const const_iterator &iter)
- : m_node(iter.m_node), m_point(iter.m_point) {}
-
- const_iterator &
- operator=(const const_iterator &iter) {
- m_node = iter.m_node;
- m_point = iter.m_point; }
-
- const T &
- operator*() const { return m_node->m_data; }
-
- const T *
- operator->() const { return &m_node->m_data; }
-
- const_iterator &
- operator++() { advance(); return *this; }
-
- const_iterator
- operator++(int) {
- const_iterator temp(*this);
- advance();
- return temp; }
-
- bool
- operator==(const const_iterator &iter) const {
- return m_node == iter.m_node; }
-
- bool
- operator!=(const const_iterator &iter) const {
- return !iter.operator==(*this); }
- };
-
- interval_map() : m_root(0) {}
-
- ~interval_map() { delete m_root; }
-
- /**
- * Insert aData for the interval [aMin, aMax]
- */
- void put(coord min, coord max, const T &data) {
- put_into(&m_root, min, max, data);
-#ifdef DEBUG
- verify(m_root, 0);
-#endif
- }
-
-
- /**
- * Return an iterator that will enumerate the data for all intervals
- * intersecting |aPoint|.
- */
- const_iterator get(coord point) const;
-
- /**
- * Return an iterator that marks the end-point of iteration.
- */
- const_iterator end() const {
- return const_iterator(0, 0); }
-
-protected:
- void put_into(node **link, coord min, coord max, const T &data, bool *subsumed = 0);
-
- void left_rotate(node **link, node *node);
- void right_rotate(node **link, node *node);
-#ifdef DEBUG
- void verify(node *node, int depth);
-#endif
- node *m_root;
-};
-
-template<class coord, class T>
-void
-interval_map<coord, T>::put_into(node **root, coord min, coord max, const T &data, bool *subsumed)
-{
- assert(min < max);
- node *interval = *root;
-
- if (interval) {
- bool before = min < interval->m_min;
- bool after = max > interval->m_max;
-
- if (!before || !after) {
- // The interval we're adding does not completely subsume
- // the |interval|. So we've got one of these situations:
- //
- // |======| |======| |======|
- // |------| |--| |------|
- //
- // where |==| is the existing interval, and |--| is the
- // new interval we're inserting. If there's left or right
- // slop, then we ``split'' the new interval in half:
- //
- // |======| |======|
- // |--|---| |---|--|
- //
- // and insert it both in the ``within'' and ``before'' (or
- // ``after'') subtrees.
- //
- if (before) {
- if (max > interval->m_min) {
- put_into(&interval->m_within, interval->m_min, max, data);
- max = interval->m_min;
- }
-
- bool was_subsumed = true;
- put_into(&interval->m_before, min, max, data, &was_subsumed);
-
- if (! was_subsumed) {
- if (interval->m_bal < 0) {
- if (interval->m_before->m_bal > 0)
- left_rotate(&interval->m_before, interval->m_before);
-
- right_rotate(root, interval);
- }
- else
- --interval->m_bal;
-
- if (subsumed)
- *subsumed = (interval->m_bal == 0);
- }
-
- return;
- }
-
- if (after) {
- if (min < interval->m_max) {
- put_into(&interval->m_within, min, interval->m_max, data);
- min = interval->m_max;
- }
-
- bool was_subsumed = true;
- put_into(&interval->m_after, min, max, data, &was_subsumed);
-
- if (! was_subsumed) {
- if (interval->m_bal > 0) {
- if (interval->m_after->m_bal < 0)
- right_rotate(&interval->m_after, interval->m_after);
-
- left_rotate(root, interval);
- }
- else
- ++interval->m_bal;
-
- if (subsumed)
- *subsumed = (interval->m_bal == 0);
- }
-
- return;
- }
-
- put_into(&interval->m_within, min, max, data);
- return;
- }
-
- // If we get here, the interval we're adding completely
- // subsumes |interval|. We'll go ahead and insert a new
- // interval immediately above |interval|, with |interval| as
- // the new interval's |m_within|.
- }
-
- if (subsumed)
- *subsumed = false;
-
- node *n = new node();
- n->m_data = data;
- n->m_before = n->m_after = 0;
- n->m_min = min;
- n->m_max = max;
- n->m_within = interval;
- n->m_bal = 0;
- *root = n;
-}
-
-/*
- * (*link) (*link)
- * | == left rotate ==> |
- * (x) (y)
- * / \ / \
- * a (y) <== right rotate == (x) c
- * / \ / \
- * b c a b
- */
-template<class coord, class T>
-void
-interval_map<coord, T>::left_rotate(node **link, node *x)
-{
- node *y = x->m_after;
- x->m_after = y->m_before;
- *link = y;
- y->m_before = x;
- --x->m_bal;
- --y->m_bal;
-}
-
-template<class coord, class T>
-void
-interval_map<coord, T>::right_rotate(node **link, node *y)
-{
- node *x = y->m_before;
- y->m_before = x->m_after;
- *link = x;
- x->m_after = y;
- ++y->m_bal;
- ++x->m_bal;
-}
-
-template<class coord, class T>
-interval_map<coord, T>::const_iterator
-interval_map<coord, T>::get(coord point) const
-{
- node *interval = m_root;
-
- while (interval) {
- if (point < interval->m_min)
- interval = interval->m_before;
- else if (point > interval->m_max)
- interval = interval->m_after;
- else
- break;
- }
-
- return const_iterator(interval, point);
-}
-
-
-template<class coord, class T>
-void
-interval_map<coord, T>::const_iterator::advance()
-{
- assert(m_node);
-
- m_node = m_node->m_within;
-
- while (m_node) {
- if (m_point < m_node->m_min)
- m_node = m_node->m_before;
- else if (m_point > m_node->m_max)
- m_node = m_node->m_after;
- else
- break;
- }
-}
-
-#ifdef DEBUG
-template<class coord, class T>
-void
-interval_map<coord, T>::verify(node<coord, T> *node, int depth)
-{
- if (node->m_after)
- verify(node->m_after, depth + 1);
-
- for (int i = 0; i < depth; ++i)
- cout << " ";
-
- hex(cout);
- cout << node << "(";
- dec(cout);
- cout << node->m_bal << ")";
- hex(cout);
- cout << "[" << node->m_min << "," << node->m_max << "]";
- cout << "@" << node->m_data;
- cout << endl;
-
- if (node->m_before)
- verify(node->m_before, depth + 1);
-}
-#endif // DEBUG
-
-#endif // interval_map_h__
deleted file mode 100644
--- a/tools/reorder/mapaddrs.cpp
+++ /dev/null
@@ -1,97 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-/*
-
- A program that reverse-maps a binary stream of address references to
- function names.
-
- */
-
-#include <fstream>
-#include <unistd.h>
-#include <fcntl.h>
-#include <stdio.h>
-
-#include "elf_symbol_table.h"
-
-#define _GNU_SOURCE
-#include <getopt.h>
-
-static int
-map_addrs(int fd, elf_symbol_table &table)
-{
- // Read the binary addresses from stdin.
- unsigned int buf[128];
- ssize_t cb;
-
- while ((cb = read(fd, buf, sizeof buf)) > 0) {
- if (cb % sizeof buf[0])
- fprintf(stderr, "unaligned read\n");
-
- unsigned int *addr = buf;
- unsigned int *limit = buf + (cb / 4);
-
- for (; addr < limit; ++addr) {
- const Elf32_Sym *sym = table.lookup(*addr);
- if (sym)
- cout << table.get_symbol_name(sym) << endl;
- }
- }
-
- return 0;
-}
-
-static struct option long_options[] = {
- { "exe", required_argument, 0, 'e' },
- { 0, 0, 0, 0 }
-};
-
-static void
-usage()
-{
- cerr << "usage: mapaddrs --exe=exe file ..." << endl;
-}
-
-int
-main(int argc, char *argv[])
-{
- elf_symbol_table table;
-
- while (1) {
- int option_index = 0;
- int c = getopt_long(argc, argv, "e:", long_options, &option_index);
-
- if (c < 0)
- break;
-
- switch (c) {
- case 'e':
- table.init(optarg);
- break;
-
- default:
- usage();
- return 1;
- }
- }
-
- if (optind >= argc) {
- map_addrs(STDIN_FILENO, table);
- }
- else {
- do {
- int fd = open(argv[optind], O_RDONLY);
- if (fd < 0) {
- perror(argv[optind]);
- return 1;
- }
-
- map_addrs(fd, table);
- close(fd);
- } while (++optind < argc);
- }
-
- return 0;
-}
deleted file mode 100644
--- a/tools/reorder/mcount.c
+++ /dev/null
@@ -1,38 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-/*
-
- A library that can be LD_PRELOAD-ed to dump a function's address on
- function entry.
-
- */
-
-#include <unistd.h>
-
-/**
- * When compiled with `-pg' (or even just `-p'), gcc inserts a call to
- * |mcount| in each function prologue. This implementation of |mcount|
- * will grab the return address from the stack, and write it to stdout
- * as a binary stream, creating a gross execution trace the
- * instrumented program.
- *
- * For more info on gcc inline assembly, see:
- *
- * <http://www.ibm.com/developerworks/linux/library/l-ia.html?dwzone=linux>
- *
- */
-void
-mcount()
-{
- register unsigned int caller;
- unsigned int buf[1];
-
- // Grab the return address.
- asm("movl 4(%%esp),%0"
- : "=r"(caller));
-
- buf[0] = caller;
- write(STDOUT_FILENO, buf, sizeof buf[0]);
-}
deleted file mode 100755
--- a/tools/reorder/missing-syms.pl
+++ /dev/null
@@ -1,36 +0,0 @@
-#!/usr/bin/perl -w
-#
-# This Source Code Form is subject to the terms of the Mozilla Public
-# License, v. 2.0. If a copy of the MPL was not distributed with this
-# file, You can obtain one at http://mozilla.org/MPL/2.0/.
-
-#
-# List the missing symbols (or, do a set difference).
-#
-
-use 5.004;
-use strict;
-use Getopt::Long;
-
-$::opt_help = 0;
-$::opt_defined = "mozilla-bin.order";
-GetOptions("help", "defined=s");
-
-if ($::opt_help) {
- die "usage: missing-syms.pl --defined=<file> <symlist>";
-}
-
-$::Defined = { };
-
-open(DEFINED, "<$::opt_defined") || die "couldn't open defined symbol list $::opt_defined";
-while (<DEFINED>) {
- chomp;
- $::Defined{$_} = 1;
-}
-close(DEFINED);
-
-while (<>) {
- chomp;
- print "$_\n" unless ($::Defined{$_});
-}
-
deleted file mode 100644
--- a/tools/reorder/mult.c
+++ /dev/null
@@ -1,8 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-int mult(int a, int b)
-{
- return a * b;
-}
deleted file mode 100644
--- a/tools/reorder/rseed.c
+++ /dev/null
@@ -1,33 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-/*
-
- A program that reads /dev/random to produce a seed for srand(3).
-
- */
-
-#include <stdio.h>
-#include <fcntl.h>
-
-int
-main(int argc, char *argv[])
-{
- int fd, ok, seed = 0;
-
- fd = open("/dev/random", O_RDONLY);
- if (fd < 0) {
- perror("/dev/random");
- return 1;
- }
-
- ok = read(fd, &seed, sizeof seed);
- if (ok > 0)
- printf("%d\n", seed);
- else
- perror("/dev/random");
-
- close(fd);
- return 0;
-}
deleted file mode 100755
--- a/tools/reorder/syms-by-addr.sh
+++ /dev/null
@@ -1,19 +0,0 @@
-#!/bin/sh
-#
-# This Source Code Form is subject to the terms of the Mozilla Public
-# License, v. 2.0. If a copy of the MPL was not distributed with this
-# file, You can obtain one at http://mozilla.org/MPL/2.0/.
-
-#
-# Print the code symbols from an ELF file.
-#
-
-# Find the text segment by searching through the section headers
-TEXT=`readelf --section-headers $1 | awk '$2 == ".text" { print $1; }' | sed -e 's/\[//g' -e 's/\]//g'`
-
-# Now print all of the FUNC-type symbols in the text segment, including
-# address, size, and symbol name.
-readelf --syms $1 |
- awk "\$7 == \"${TEXT}\" { printf \"%s %8d %7s %6s %7s %s\n\", \$2, \$3, \$4, \$5, \$6, \$8; }" |
- sort -u
-
deleted file mode 100644
--- a/tools/reorder/test.cpp
+++ /dev/null
@@ -1,89 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-extern "C" int mult(int l, int r);
-
-extern "C" {
-
-inline
-int
-farfle(int a, int b)
-{
- return a * b + a / b;
-}
-
-static
-int
-ballywhoo(int a, int b)
-{
- // So it can't get inlined
- if (a > 4)
- ballywhoo(a - 1, a + 1);
-
- return a + b;
-}
-
-static
-int
-blimpyburger(char a, int b)
-{
- if (a == 'f')
- return b;
-
- return 0;
-}
-
-}
-
-class foo
-{
-public:
- static int get_flooby() { static int flooby = 12; return flooby; }
-
- static int divide(int a, int b);
-
- foo() {}
- foo(int a);
- virtual ~foo() {}
-
- int bar();
-
- int baz(int a) { return a ? baz(a - 1) : 0; }
-};
-
-foo::foo(int a)
-{
-}
-
-int
-foo::divide(int a, int b)
-{
- static int phlegm = 12;
- return a / b * ++phlegm;
-}
-
-int
-foo::bar()
-{
- return 12;
-}
-
-int main(int argc, char* argv[])
-{
- int a = mult(5, 4);
- a = ballywhoo(5, 2);
- a = farfle(a, 6);
- a = blimpyburger('q', 4);
-
- foo f;
- f.get_flooby();
- a = f.bar();
-
- a = foo::divide(a, 12) + f.baz(6);
-
- foo f2(12);
- f2.baz(15);
-
- return a > 99 ? 1 : 0;
-}