First attempt to import OpenMP runtime

llvm-svn: 191506

1 files changed, 499 insertions, 0 deletions

diff --git a/openmp/runtime/src/extractExternal.cpp b/openmp/runtime/src/extractExternal.cpp
new file mode 100644
index 00000000000..f9cbaa4b10c
--- /dev/null
+++ b/openmp/runtime/src/extractExternal.cpp
@@ -0,0 +1,499 @@
+/*
+ * extractExternal.cpp
+ * $Revision: 42181 $
+ * $Date: 2013-03-26 15:04:45 -0500 (Tue, 26 Mar 2013) $
+ */
+
+
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.txt for details.
+//
+//===----------------------------------------------------------------------===//
+
+
+#include <stdlib.h>
+#include <iostream>
+#include <strstream>
+#include <fstream>
+#include <string>
+#include <set>
+#include <map>
+
+/* Given a set of n object files h ('external' object files) and a set of m
+   object files o ('internal' object files),
+   1. Determines r, the subset of h that o depends on, directly or indirectly
+   2. Removes the files in h - r from the file system
+   3. For each external symbol defined in some file in r, rename it in r U o
+      by prefixing it with "__kmp_external_"
+   Usage:
+   hide.exe <n> <filenames for h> <filenames for o>
+
+   Thus, the prefixed symbols become hidden in the sense that they now have a special
+   prefix.
+*/
+
+using namespace std;
+
+void stop(char* errorMsg) {
+    printf("%s\n", errorMsg);
+    exit(1);
+}
+
+// an entry in the symbol table of a .OBJ file
+class Symbol {
+public:
+    __int64 name;
+    unsigned value;
+    unsigned short sectionNum, type;
+    char storageClass, nAux;
+};
+
+class _rstream : public istrstream {
+private:
+    const char *buf;
+protected:
+    _rstream(pair<const char*, streamsize> p):istrstream(p.first,p.second),buf(p.first){}
+    ~_rstream() {
+	delete[]buf;
+    }
+};
+
+/* A stream encapuslating the content of a file or the content of a string, overriding the
+   >> operator to read various integer types in binary form, as well as a symbol table
+   entry.
+*/
+class rstream : public _rstream {
+private:
+    template<class T>
+    inline rstream& doRead(T &x) {
+	read((char*)&x, sizeof(T));
+	return *this;
+    }
+    static pair<const char*, streamsize> getBuf(const char *fileName) {
+	ifstream raw(fileName,ios::binary | ios::in);
+	if(!raw.is_open())
+	    stop("rstream.getBuf: Error opening file");
+	raw.seekg(0,ios::end);
+	streampos fileSize = raw.tellg();
+	if(fileSize < 0)
+	    stop("rstream.getBuf: Error reading file");
+	char *buf = new char[fileSize];
+	raw.seekg(0,ios::beg);
+	raw.read(buf, fileSize);
+	return pair<const char*, streamsize>(buf,fileSize);
+    }
+public:
+    // construct from a string
+    rstream(const char *buf,streamsize size):_rstream(pair<const char*,streamsize>(buf, size)){}
+    /* construct from a file whole content is fully read once to initialize the content of
+       this stream
+    */
+    rstream(const char *fileName):_rstream(getBuf(fileName)){}
+    rstream& operator>>(int &x) {
+	return doRead(x);
+    }
+    rstream& operator>>(unsigned &x) {
+	return doRead(x);
+    }
+    rstream& operator>>(short &x) {
+	return doRead(x);
+    }
+    rstream& operator>>(unsigned short &x) {
+	return doRead(x);
+    }
+    rstream& operator>>(Symbol &e) {
+	read((char*)&e, 18);
+	return *this;
+    }
+};
+
+// string table in a .OBJ file
+class StringTable {
+private:
+    map<string, unsigned> directory;
+    size_t length;
+    char *data;
+
+    // make <directory> from <length> bytes in <data>
+    void makeDirectory(void) {
+	unsigned i = 4;
+	while(i < length) {
+	    string s = string(data + i);
+	    directory.insert(make_pair(s, i));
+	    i += s.size() + 1;
+	}
+    }
+    // initialize <length> and <data> with contents specified by the arguments
+    void init(const char *_data) {
+	unsigned _length = *(unsigned*)_data;
+
+	if(_length < sizeof(unsigned) || _length != *(unsigned*)_data)
+	    stop("StringTable.init: Invalid symbol table");
+	if(_data[_length - 1]) {
+	    // to prevent runaway strings, make sure the data ends with a zero
+	    data = new char[length = _length + 1];
+	    data[_length] = 0;
+	} else {
+	    data = new char[length = _length];
+	}
+	*(unsigned*)data = length;
+	memcpy(data + sizeof(unsigned), _data + sizeof(unsigned),
+	       length - sizeof(unsigned));
+	makeDirectory();
+    }
+public:
+    StringTable(rstream &f) {
+	/* Construct string table by reading from f.
+	 */
+	streampos s;
+	unsigned strSize;
+	char *strData;
+
+	s = f.tellg();
+	f>>strSize;
+	if(strSize < sizeof(unsigned))
+	    stop("StringTable: Invalid string table");
+	strData = new char[strSize];
+	*(unsigned*)strData = strSize;
+	// read the raw data into <strData>
+	f.read(strData + sizeof(unsigned), strSize - sizeof(unsigned));
+	s = f.tellg() - s;
+	if(s < strSize)
+	    stop("StringTable: Unexpected EOF");
+	init(strData);
+	delete[]strData;
+    }
+    StringTable(const set<string> &strings) {
+	/* Construct string table from given strings.
+	 */
+	char *p;
+	set<string>::const_iterator it;
+	size_t s;
+
+	// count required size for data
+	for(length = sizeof(unsigned), it = strings.begin(); it != strings.end(); ++it) {
+	    size_t l = (*it).size();
+
+	    if(l > (unsigned) 0xFFFFFFFF)
+		stop("StringTable: String too long");
+	    if(l > 8) {
+		length += l + 1;
+		if(length > (unsigned) 0xFFFFFFFF)
+		    stop("StringTable: Symbol table too long");
+	    }
+	}
+	data = new char[length];
+	*(unsigned*)data = length;
+	// populate data and directory
+	for(p = data + sizeof(unsigned), it = strings.begin(); it != strings.end(); ++it) {
+	    const string &str = *it;
+	    size_t l = str.size();
+	    if(l > 8) {
+		directory.insert(make_pair(str, p - data));
+		memcpy(p, str.c_str(), l);
+		p[l] = 0;
+		p += l + 1;
+	    }
+	}
+    }
+    ~StringTable() {
+	delete[] data;
+    }
+    /* Returns encoding for given string based on this string table.
+       Error if string length is greater than 8 but string is not in
+       the string table--returns 0.
+    */
+    __int64 encode(const string &str) {
+	__int64 r;
+
+	if(str.size() <= 8) {
+	    // encoded directly
+	    ((char*)&r)[7] = 0;
+	    strncpy((char*)&r, str.c_str(), 8);
+	    return r;
+	} else {
+	    // represented as index into table
+	    map<string,unsigned>::const_iterator it = directory.find(str);
+	    if(it == directory.end())
+		stop("StringTable::encode: String now found in string table");
+	    ((unsigned*)&r)[0] = 0;
+	    ((unsigned*)&r)[1] = (*it).second;
+	    return r;
+	}
+    }
+    /* Returns string represented by x based on this string table.
+       Error if x references an invalid position in the table--returns
+       the empty string.
+    */
+    string decode(__int64 x) const {
+	if(*(unsigned*)&x == 0) {
+	    // represented as index into table
+	    unsigned &p = ((unsigned*)&x)[1];
+	    if(p >= length)
+		stop("StringTable::decode: Invalid string table lookup");
+	    return string(data + p);
+	} else {
+	    // encoded directly
+	    char *p = (char*)&x;
+	    int i;
+
+	    for(i = 0; i < 8 && p[i]; ++i);
+	    return string(p, i);
+	}
+    }
+    void write(ostream &os) {
+	os.write(data, length);
+    }
+};
+
+/* for the named object file, determines the set of defined symbols and the set of undefined external symbols
+   and writes them to <defined> and <undefined> respectively
+*/
+void computeExternalSymbols(const char *fileName, set<string> *defined, set<string> *undefined){
+    streampos fileSize;
+    size_t strTabStart;
+    unsigned symTabStart, symNEntries;
+    rstream f(fileName);
+
+    f.seekg(0,ios::end);
+    fileSize = f.tellg();
+
+    f.seekg(8);
+    f >> symTabStart >> symNEntries;
+    // seek to the string table
+    f.seekg(strTabStart = symTabStart + 18 * (size_t)symNEntries);
+    if(f.eof()) {
+	printf("computeExternalSymbols: fileName='%s', fileSize = %lu, symTabStart = %u, symNEntries = %u\n",
+	       fileName, (unsigned long) fileSize, symTabStart, symNEntries);
+	stop("computeExternalSymbols: Unexpected EOF 1");
+    }
+    StringTable stringTable(f); // read the string table
+    if(f.tellg() != fileSize)
+	stop("computeExternalSymbols: Unexpected data after string table");
+
+    f.clear();
+    f.seekg(symTabStart); // seek to the symbol table
+
+    defined->clear(); undefined->clear();
+    for(int i = 0; i < symNEntries; ++i) {
+	// process each entry
+	Symbol e;
+
+	if(f.eof())
+	    stop("computeExternalSymbols: Unexpected EOF 2");
+	f>>e;
+	if(f.fail())
+	    stop("computeExternalSymbols: File read error");
+	if(e.nAux) { // auxiliary entry: skip
+	    f.seekg(e.nAux * 18, ios::cur);
+	    i += e.nAux;
+	}
+	// if symbol is extern and defined in the current file, insert it
+	if(e.storageClass == 2)
+	    if(e.sectionNum)
+		defined->insert(stringTable.decode(e.name));
+	    else
+		undefined->insert(stringTable.decode(e.name));
+    }
+}
+
+/* For each occurence of an external symbol in the object file named by
+   by <fileName> that is a member of <hide>, renames it by prefixing
+   with "__kmp_external_", writing back the file in-place
+*/
+void hideSymbols(char *fileName, const set<string> &hide) {
+    static const string prefix("__kmp_external_");
+    set<string> strings; // set of all occurring symbols, appropriately prefixed
+    streampos fileSize;
+    size_t strTabStart;
+    unsigned symTabStart, symNEntries;
+    int i;
+    rstream in(fileName);
+
+    in.seekg(0,ios::end);
+    fileSize = in.tellg();
+
+    in.seekg(8);
+    in >> symTabStart >> symNEntries;
+    in.seekg(strTabStart = symTabStart + 18 * (size_t)symNEntries);
+    if(in.eof())
+	stop("hideSymbols: Unexpected EOF");
+    StringTable stringTableOld(in); // read original string table
+
+    if(in.tellg() != fileSize)
+	stop("hideSymbols: Unexpected data after string table");
+
+    // compute set of occurring strings with prefix added
+    for(i = 0; i < symNEntries; ++i) {
+	Symbol e;
+
+	in.seekg(symTabStart + i * 18);
+	if(in.eof())
+	    stop("hideSymbols: Unexpected EOF");
+	in >> e;
+	if(in.fail())
+	    stop("hideSymbols: File read error");
+	if(e.nAux)
+	    i += e.nAux;
+	const string &s = stringTableOld.decode(e.name);
+	// if symbol is extern and found in <hide>, prefix and insert into strings,
+	// otherwise, just insert into strings without prefix
+	strings.insert( (e.storageClass == 2 && hide.find(s) != hide.end()) ?
+			prefix + s : s);
+    }
+
+    ofstream out(fileName, ios::trunc | ios::out | ios::binary);
+    if(!out.is_open())
+	stop("hideSymbols: Error opening output file");
+
+    // make new string table from string set
+    StringTable stringTableNew = StringTable(strings);
+
+    // copy input file to output file up to just before the symbol table
+    in.seekg(0);
+    char *buf = new char[symTabStart];
+    in.read(buf, symTabStart);
+    out.write(buf, symTabStart);
+    delete []buf;
+
+    // copy input symbol table to output symbol table with name translation
+    for(i = 0; i < symNEntries; ++i) {
+	Symbol e;
+
+	in.seekg(symTabStart + i*18);
+	if(in.eof())
+	    stop("hideSymbols: Unexpected EOF");
+	in >> e;
+	if(in.fail())
+	    stop("hideSymbols: File read error");
+	const string &s = stringTableOld.decode(e.name);
+	out.seekp(symTabStart + i*18);
+	e.name = stringTableNew.encode( (e.storageClass == 2 && hide.find(s) != hide.end()) ?
+					prefix + s : s);
+	out.write((char*)&e, 18);
+	if(out.fail())
+	    stop("hideSymbols: File write error");
+	if(e.nAux) {
+	    // copy auxiliary symbol table entries
+	    int nAux = e.nAux;
+	    for(int j = 1; j <= nAux; ++j) {
+		in >> e;
+		out.seekp(symTabStart + (i + j) * 18);
+		out.write((char*)&e, 18);
+	    }
+	    i += nAux;
+	}
+    }
+    // output string table
+    stringTableNew.write(out);
+}
+
+// returns true iff <a> and <b> have no common element
+template <class T>
+bool isDisjoint(const set<T> &a, const set<T> &b) {
+    set<T>::const_iterator ita, itb;
+
+    for(ita = a.begin(), itb = b.begin(); ita != a.end() && itb != b.end();) {
+	const T &ta = *ita, &tb = *itb;
+	if(ta < tb)
+	    ++ita;
+	else if (tb < ta)
+	    ++itb;
+	else
+	    return false;
+    }
+    return true;
+}
+
+/* precondition: <defined> and <undefined> are arrays with <nTotal> elements where
+   <nTotal> >= <nExternal>.  The first <nExternal> elements correspond to the external object
+   files and the rest correspond to the internal object files.
+   postcondition: file x is said to depend on file y if undefined[x] and defined[y] are not
+   disjoint.  Returns the transitive closure of the set of internal object files, as a set of
+   file indexes, under the 'depends on' relation, minus the set of internal object files.
+*/
+set<int> *findRequiredExternal(int nExternal, int nTotal, set<string> *defined, set<string> *undefined) {
+    set<int> *required = new set<int>;
+    set<int> fresh[2];
+    int i, cur = 0;
+    bool changed;
+
+    for(i = nTotal - 1; i >= nExternal; --i)
+	fresh[cur].insert(i);
+    do {
+	changed = false;
+	for(set<int>::iterator it = fresh[cur].begin(); it != fresh[cur].end(); ++it) {
+	    set<string> &s = undefined[*it];
+
+	    for(i = 0; i < nExternal; ++i) {
+		if(required->find(i) == required->end()) {
+		    if(!isDisjoint(defined[i], s)) {
+			// found a new qualifying element
+			required->insert(i);
+			fresh[1 - cur].insert(i);
+			changed = true;
+		    }
+		}
+	    }
+	}
+	fresh[cur].clear();
+	cur = 1 - cur;
+    } while(changed);
+    return required;
+}
+
+int main(int argc, char **argv) {
+    int nExternal, nInternal, i;
+    set<string> *defined, *undefined;
+    set<int>::iterator it;
+
+    if(argc < 3)
+	stop("Please specify a positive integer followed by a list of object filenames");
+    nExternal = atoi(argv[1]);
+    if(nExternal <= 0)
+	stop("Please specify a positive integer followed by a list of object filenames");
+    if(nExternal +  2 > argc)
+	stop("Too few external objects");
+    nInternal = argc - nExternal - 2;
+    defined = new set<string>[argc - 2];
+    undefined = new set<string>[argc - 2];
+
+    // determine the set of defined and undefined external symbols
+    for(i = 2; i < argc; ++i)
+	computeExternalSymbols(argv[i], defined + i - 2, undefined + i - 2);
+
+    // determine the set of required external files
+    set<int> *requiredExternal = findRequiredExternal(nExternal, argc - 2, defined, undefined);
+    set<string> hide;
+
+    /* determine the set of symbols to hide--namely defined external symbols of the
+       required external files
+    */
+    for(it = requiredExternal->begin(); it != requiredExternal->end(); ++it) {
+	int idx = *it;
+	set<string>::iterator it2;
+	/* We have to insert one element at a time instead of inserting a range because
+	   the insert member function taking a range doesn't exist on Windows* OS, at least
+	   at the time of this writing.
+	*/
+	for(it2 = defined[idx].begin(); it2 != defined[idx].end(); ++it2)
+	    hide.insert(*it2);
+    }
+
+    /* process the external files--removing those that are not required and hiding
+       the appropriate symbols in the others
+    */
+    for(i = 0; i < nExternal; ++i)
+	if(requiredExternal->find(i) != requiredExternal->end())
+	    hideSymbols(argv[2 + i], hide);
+	else
+	    remove(argv[2 + i]);
+    // hide the appropriate symbols in the internal files
+    for(i = nExternal + 2; i < argc; ++i)
+	hideSymbols(argv[i], hide);
+    return 0;
+}