[Simit-arm-cvs] simit-arm/decgen bin_pattern.cpp,NONE,1.1.2.1 bin_pattern.hpp,NONE,1.1.2.1 undef.cpp
Brought to you by:
weiqin04
Menu
▾
▴
[Simit-arm-cvs] simit-arm/decgen bin_pattern.cpp,NONE,1.1.2.1 bin_pattern.hpp,NONE,1.1.2.1 undef.cpp,NONE,1.2.2.1 Makefile.am,1.1.1.1,1.1.1.1.2.1 inst_type.h,1.2,1.2.2.1 main.cpp,1.2,1.2.2.1 parse_idef.y,1.2,1.2.2.1
Update of /cvsroot/simit-arm/simit-arm/decgen In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3564 Modified Files: Tag: sc_branch Makefile.am inst_type.h main.cpp parse_idef.y Added Files: Tag: sc_branch bin_pattern.cpp bin_pattern.hpp undef.cpp Log Message: improved decgen by allowing computing unused opcode space Index: main.cpp =================================================================== RCS file: /cvsroot/simit-arm/simit-arm/decgen/main.cpp,v retrieving revision 1.2 retrieving revision 1.2.2.1 diff -C2 -d -r1.2 -r1.2.2.1 *** main.cpp 12 Nov 2004 06:32:59 -0000 1.2 --- main.cpp 3 Apr 2005 20:09:58 -0000 1.2.2.1 *************** *** 10,14 **** --- 10,17 ---- #include "decode_theiling.h" + using std::vector; + extern int yyparse(); + extern bool compute_undef(vector<DecodeEntry> &); using namespace std; *************** *** 29,32 **** --- 32,36 ---- << " -1bit Use only 1 bit decoding" << endl << " -theiling Use the Theiling algorithm" << endl + << " -i Compute undefined opcode space" << endl << endl; exit(1); *************** *** 51,54 **** --- 55,59 ---- char *xfname = NULL; /* output xml file */ bool theiling = false; + bool invert = false; int i; *************** *** 58,61 **** --- 63,67 ---- { if (strcmp(argv[i], "-o")==0) cfname = argv[++i]; + else if (strcmp(argv[i], "-i")==0) invert = true; else if (strcmp(argv[i], "-x")==0) xfname = argv[++i]; else if (strcmp(argv[i], "-g")==0) gamma= atof(argv[++i]); *************** *** 89,92 **** --- 95,101 ---- fclose(dec_in); + if (invert) + compute_undef(entries); + /* open output file, if any */ ofstream dec_out; Index: Makefile.am =================================================================== RCS file: /cvsroot/simit-arm/simit-arm/decgen/Makefile.am,v retrieving revision 1.1.1.1 retrieving revision 1.1.1.1.2.1 diff -C2 -d -r1.1.1.1 -r1.1.1.1.2.1 *** Makefile.am 24 Sep 2004 03:11:00 -0000 1.1.1.1 --- Makefile.am 3 Apr 2005 20:09:58 -0000 1.1.1.1.2.1 *************** *** 28,31 **** --- 28,32 ---- decode.h decode_table.h huffman.h decode_tree.h \ decode_theiling.h \ + bin_pattern.cpp bin_pattern.hpp undef.cpp \ inst_type.h $(DECPARSE_SRC) $(DECPARSE_HDR) $(DECLEX_SRC) --- NEW FILE: undef.cpp --- /* this file is the adapter between two libraries */ #include <vector> #include <list> #include <string> #include "decode.h" #include "bin_pattern.hpp" using std::list; using std::vector; using std::string; static BinPattern entry2pattern(DecodeEntry& entry) { int ii; int nbits = INSTSIZE * 8; string spat; for (ii=nbits-1; ii>=0; ii--) { if (!entry.mask.bit_n(ii)) { spat += '-'; } else if (entry.signature.bit_n(ii)) { spat += '1'; } else { spat += '0'; } } return BinPattern(spat); } static DecodeEntry pattern2entry(BinPattern& pat) { string mask = "0x" + pat.get_hex_mask(); string sign = "0x" + pat.get_hex_signature(); return DecodeEntry(mask.c_str(), sign.c_str(), "null", 1e-10); } bool compute_undef(vector<DecodeEntry>& entries) { list<BinPattern> pats; vector<DecodeEntry>::iterator ent_it; for (ent_it = entries.begin(); ent_it!=entries.end(); ent_it++) { pats.push_back(entry2pattern(*ent_it)); } list<BinPattern> results; inverse(pats, results); // augment the original entries with null ones list<BinPattern>::iterator pat_it; for (pat_it = results.begin(); pat_it!=results.end(); pat_it++) { entries.push_back(pattern2entry(*pat_it)); } } --- NEW FILE: bin_pattern.cpp --- #include "bin_pattern.hpp" #include <cstring> using std::ostream; using std::string; using std::list; #define BITS_PER_UNSIGNED (sizeof(unsigned)*8) #define BYTES_PER_UNSIGNED (sizeof(unsigned)) static unsigned pop_count(unsigned val) { static unsigned char pop_count_table[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, }; unsigned count = 0; for (unsigned ii=0; ii<BYTES_PER_UNSIGNED; ii++) { count += pop_count_table[(unsigned char)val]; val >>= 8; } return count; } binary_pattern::binary_pattern(const string& str) { len = str.length(); /* allocate space for the data */ unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; data = new unsigned[wlen*2]; /* reset the data to zero */ memset(data, 0, wlen*2*BYTES_PER_UNSIGNED); const char *cstr = str.c_str(); for (unsigned ii=0; ii<len; ii++) { unsigned wpos = ii/BITS_PER_UNSIGNED; unsigned bpos = ii%BITS_PER_UNSIGNED; if (cstr[len-ii-1]=='1') { data[wpos] |= 1<<bpos; data[wlen+wpos] |= 1<<bpos; } else if (cstr[len-ii-1]=='0') { data[wpos] |= 1<<bpos; } } } binary_pattern::binary_pattern(unsigned length) : len(length) { /* allocate space for the data */ unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; data = new unsigned[wlen*2]; /* reset the data to zero */ memset(data, 0, wlen*2*BYTES_PER_UNSIGNED); } binary_pattern::binary_pattern(const binary_pattern& pat) { len = pat.len; /* allocate space for the data */ unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; data = new unsigned[wlen*2]; /* copy the data */ memcpy(data, pat.data, wlen*2*BYTES_PER_UNSIGNED); } binary_pattern::~binary_pattern() { delete [] data; } binary_pattern& binary_pattern::operator = (const binary_pattern& pat) { if (len==pat.len) { unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; memcpy(data, pat.data, wlen*2*BYTES_PER_UNSIGNED); } else { delete [] data; len = pat.len; /* allocate space for the data */ unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; data = new unsigned[wlen*2]; /* copy the data */ memcpy(data, pat.data, wlen*2*BYTES_PER_UNSIGNED); } return *this; } bool binary_pattern::overlap(const binary_pattern &pat) const { assert(len==pat.len); /* allocate space for the data */ unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; /* check all words */ for (unsigned ii=0; ii<wlen; ii++) { /* consider bits that are significant for both */ unsigned mask = data[ii] & pat.data[ii]; unsigned sig = data[wlen+ii] ^ pat.data[wlen+ii]; /* see if there is conflict */ if (mask & sig) return false; } return true; } bool binary_pattern::contain(const binary_pattern& pat) const { assert(len==pat.len); /* allocate space for the data */ unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; /* check all words */ for (unsigned ii=0; ii<wlen; ii++) { /* see if mask1 is smaller all mask2 */ if ((data[ii] & pat.data[ii]) != data[ii]) return false; /* if there is difference in value, see if significant */ unsigned sig = data[wlen+ii] ^ pat.data[wlen+ii]; if (data[ii] & sig) return false; } return true; } unsigned binary_pattern::distance(const binary_pattern& pat) const { assert(len==pat.len); /* allocate space for the data */ unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; unsigned dist = 0; /* check all words */ for (unsigned ii=0; ii<wlen; ii++) { /* consider bits that are significant for both */ unsigned mask = data[ii] & pat.data[ii]; unsigned sig = data[wlen+ii] ^ pat.data[wlen+ii]; /* see if there is conflict */ dist += pop_count(mask & sig); } return dist; } bool binary_pattern::mergeable(const binary_pattern& pat) const { assert(len==pat.len); /* allocate space for the data */ unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; unsigned dist = 0; unsigned overflow1 = 0, overflow2 = 0; /* check all words */ for (unsigned ii=0; ii<wlen; ii++) { /* consider bits that are significant for both */ unsigned mask = data[ii] & pat.data[ii]; unsigned sig = data[wlen+ii] ^ pat.data[wlen+ii]; overflow1 |= data[ii] & ~mask; overflow2 |= pat.data[ii] & ~mask; /* see if there is conflict */ dist += pop_count(mask & sig); } if (overflow1 && overflow2) return false; return dist==1; } #if 0 list<BinPattern> binary_pattern::diff(const binary_pattern& x) const { assert(this->contain(x)); list<BinPattern> ret; const char *str1 = this->data.c_str(); const char *str2 = x.data.c_str(); for (unsigned int i = 0; i<this->get_length(); i++) { if (str1[i]=='-' && str2[i]=='0') { string s(str1); s[i] = '1'; ret.push_back(s); } else if (str1[i]=='-' && str2[i]=='1') { string s(str1); s[i] = '0'; ret.push_back(s); } } return ret; } string binary_pattern::get_mask() const { string ret = data; for (unsigned int i=0; i<data.length(); i++) { if (ret[i]=='-') ret[i] = '0'; else ret[i] = '1'; } return ret; } string binary_pattern::get_signature() const { string ret = data; for (unsigned int i=0; i<data.length(); i++) { if (ret[i]=='-') ret[i] = '0'; } return ret; } #endif #define hex_char(_v) ((_v<10)?(_v+'0'):(_v+'A'-10)) string binary_pattern::get_str() const { string ret(len, '-'); unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; for (unsigned ii=0; ii<len; ii++) { unsigned wpos = ii/BITS_PER_UNSIGNED; unsigned bpos = ii%BITS_PER_UNSIGNED; if (data[wpos] & (1<<bpos)) { if (data[wpos+wlen] & (1<<bpos)) ret[len-ii-1] = '1'; else ret[len-ii-1] = '0'; } } return ret; } string binary_pattern::get_hex_mask() const { /* length of the pattern in hexidecimal */ unsigned hlen = (len+3)/4; string ret(hlen, '0'); for (unsigned ii=0; ii<len; ii+=4, hlen--) { unsigned wpos = ii/BITS_PER_UNSIGNED; unsigned bpos = ii%BITS_PER_UNSIGNED; unsigned val = (data[wpos]>>bpos) & 15; ret[hlen-1] = hex_char(val); } return ret; } string binary_pattern::get_hex_signature() const { /* length of the pattern in hexidecimal */ unsigned hlen = (len+3)/4; string ret(hlen, '0'); unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; for (unsigned ii=0; ii<len; ii+=4, hlen--) { unsigned wpos = ii/BITS_PER_UNSIGNED; unsigned bpos = ii%BITS_PER_UNSIGNED; unsigned val = (data[wpos+wlen]>>bpos) & 15; ret[hlen-1] = hex_char(val); } return ret; } ostream& binary_pattern::print(ostream& os) const { return os << this->get_str(); } const BinPattern operator + (const BinPattern& x, const BinPattern& y) { /* get the total length */ unsigned len = x.len + y.len; BinPattern result(len); /* copy the data from the low order bits*/ unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; unsigned ywlen = (y.len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; unsigned xwlen = (x.len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; /* copy over the LSBs */ memcpy(result.data, y.data, ywlen*BYTES_PER_UNSIGNED); memcpy(result.data+wlen, y.data+ywlen, ywlen*BYTES_PER_UNSIGNED); if (y.len%BITS_PER_UNSIGNED==0) { memcpy(result.data+ywlen, x.data, xwlen*BYTES_PER_UNSIGNED); memcpy(result.data+ywlen+wlen, x.data+xwlen, xwlen*BYTES_PER_UNSIGNED); } else { /* the position for the lsb from x*/ unsigned bpos = y.len%BITS_PER_UNSIGNED; for (unsigned ii=0; ii<xwlen; ii++) { result.data[ywlen-1+ii] |= x.data[ii] << bpos; result.data[wlen+ywlen-1+ii] |= x.data[ii+xwlen] << bpos; if (ywlen+ii<wlen) { result.data[ywlen+ii] |= x.data[ii] >> (BITS_PER_UNSIGNED-bpos); result.data[wlen+ywlen+ii] |= x.data[ii+xwlen] >> (BITS_PER_UNSIGNED-bpos); } } } return result; } const BinPattern operator ^ (const BinPattern& x, const BinPattern& y) { assert(x.len == y.len); BinPattern result(x.len); unsigned wlen = (x.len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; for (unsigned ii=0; ii<wlen; ii++) { /* consider bits that are significant for both */ unsigned mask = x.data[ii] & y.data[ii]; unsigned sig = x.data[wlen+ii] ^ y.data[wlen+ii]; unsigned diff = mask & sig; result.data[ii] = (x.data[ii] | y.data[ii]) & (~diff); result.data[ii+wlen] = (x.data[wlen+ii] | y.data[wlen+ii]) & (~diff); } return result; } bool operator == (const BinPattern& x, const BinPattern& y) { assert(x.len == y.len); unsigned wlen = (x.len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; for (unsigned ii=0; ii<wlen; ii++) { if (x.data[ii]!=y.data[ii]) return false; if (x.data[ii+wlen]!=y.data[ii+wlen]) return false; } return true; } bool operator != (const BinPattern& x, const BinPattern& y) { return !(x==y); } ostream& operator << (ostream& os, const BinPattern& x) { return os << x.get_str(); } static void SCC_minimal(list<binary_pattern>& pats) { list<binary_pattern>::iterator iit, jjt; for (iit=pats.begin(); iit!=pats.end();) { bool del = false; for (jjt=iit, jjt++; jjt!=pats.end();) { if ((*iit).contain(*jjt)) { jjt = pats.erase(jjt); } else if ((*jjt).contain(*iit)) { del = true; iit = pats.erase(iit); break; } else { jjt++; } } if (!del) iit++; } } static void iterated_merge(list<binary_pattern>& pats) { bool change = true; while (change) { change = false; /* remove nonessential ones first */ SCC_minimal(pats); list<binary_pattern> new_pats; list<binary_pattern>::iterator iit, jjt; for (iit=pats.begin(); iit!=pats.end();) { bool del = false; for (jjt=iit, jjt++; jjt!=pats.end();) { /* see if possible to merge */ if ((*iit).mergeable(*jjt)) { change = true; /* merge and push it to the back of the back */ new_pats.push_back((*iit)^(*jjt)); /* see if the result contains its sources */ if (new_pats.back().contain(*jjt)) { jjt = pats.erase(jjt); } else if (new_pats.back().contain(*iit)) { del = true; iit = pats.erase(iit); break; } else { assert(0); jjt++; } } else jjt++; } if (!del) iit++; } pats.insert(pats.end(), new_pats.begin(), new_pats.end()); } } void exclude_cube(list<binary_pattern>& pats, const binary_pattern& x) { assert(pats.size()>0); unsigned len = pats.front().get_length(); unsigned wlen = (len+BITS_PER_UNSIGNED-1)/BITS_PER_UNSIGNED; list<binary_pattern>::iterator iit; for (iit=pats.begin(); iit!=pats.end();) { /* the simplest case, remove iit */ if (x.contain(*iit)) { iit = pats.erase(iit); } else if ((*iit).overlap(x)) { for (unsigned ii=0; ii<wlen; ii++) { unsigned diff = ~(*iit).data[ii] & x.data[ii]; unsigned inv = ~x.data[wlen+ii]; for (unsigned jj=0; diff; jj++, diff>>=1) { if (diff&1) { BinPattern new_pat = *iit; new_pat.data[ii] |= 1<<jj; new_pat.data[ii+wlen] |= inv & (1<<jj); pats.push_back(new_pat); } } } iit = pats.erase(iit); } else iit++; } } /* get the inverse of the cubes */ void inverse(list<binary_pattern>& pats, list<binary_pattern>& result) { /* simplify the space first */ iterated_merge(pats); assert(pats.size()>0); unsigned len = pats.front().len; /* the full space */ result.push_back(binary_pattern(len)); unsigned ii=0; list<binary_pattern>::iterator iit; for (iit=pats.begin(); iit!=pats.end(); iit++, ii++) { exclude_cube(result, *iit); if (ii==5) { SCC_minimal(result); ii=0; } } /* simplify the final result */ iterated_merge(result); } Index: parse_idef.y =================================================================== RCS file: /cvsroot/simit-arm/simit-arm/decgen/parse_idef.y,v retrieving revision 1.2 retrieving revision 1.2.2.1 diff -C2 -d -r1.2 -r1.2.2.1 *** parse_idef.y 12 Nov 2004 06:32:59 -0000 1.2 --- parse_idef.y 3 Apr 2005 20:09:58 -0000 1.2.2.1 *************** *** 49,53 **** void yyerror (char *s) { ! std::cerr << s << "near line " << mylineno+1 << std::endl; } --- 49,53 ---- void yyerror (char *s) { ! std::cerr << s << " near line " << mylineno+1 << std::endl; } Index: inst_type.h =================================================================== RCS file: /cvsroot/simit-arm/simit-arm/decgen/inst_type.h,v retrieving revision 1.2 retrieving revision 1.2.2.1 diff -C2 -d -r1.2 -r1.2.2.1 *** inst_type.h 12 Nov 2004 06:32:59 -0000 1.2 --- inst_type.h 3 Apr 2005 20:09:58 -0000 1.2.2.1 *************** *** 55,58 **** --- 55,60 ---- unsigned int ucast() const {return (unsigned int)val;} + bool bit_n(unsigned n) {return (val>>n)&1;} + private: *************** *** 133,136 **** --- 135,140 ---- unsigned int ucast() const {return (unsigned int)val;} + bool bit_n(unsigned n) {return (val>>n)&1;} + private: --- NEW FILE: bin_pattern.hpp --- #ifndef __MAD_BIN_PATTERN_HPP__ #define __MAD_BIN_PATTERN_HPP__ #include <iostream> #include <string> #include <cassert> #include <list> #include "config.h" /** binary pattern class. */ typedef class binary_pattern { public: /** Constructor. */ binary_pattern(const std::string& d); /** Constructor. */ binary_pattern(unsigned len); /** Copy constructor. */ binary_pattern(const binary_pattern& pat); /** Destructor. */ ~binary_pattern(); /** Assignment operator */ binary_pattern& operator = (const binary_pattern& pat); /** Get the length of the pattern. */ unsigned get_length() const {return len;} /** Distance between patterns (number of conflicting bits) */ unsigned distance(const binary_pattern& pat) const; bool mergeable(const binary_pattern& pat) const; /** Check if this pattern contains the other. */ bool contain(const binary_pattern& pat) const; /** Overlap is weaker than contains. */ bool overlap(const binary_pattern& pat) const; #if 0 /** return a difference vector A-B. */ std::vector<binary_pattern> diff(const binary_pattern& pat) const; /** Get the mask of the pattern, in binary format. */ std::string get_mask() const; /** Get the signature of the pattern, in binary format. */ std::string get_signature() const; #endif /** Get the string representing the pattern, in '0', '1', '-' */ std::string get_str() const; /** Get the mask of the pattern, in hexadecimal w/o 0x. */ std::string get_hex_mask() const; /** Get the signature of the pattern, in hexadecimal w/o 0x. */ std::string get_hex_signature() const; /** Output the pattern. */ std::ostream& print(std::ostream& os) const; private: /* pointer to array of masks and signatures (mask first) * data[0]'s LSB is the lowest bit */ unsigned *data; /* length of the pattern */ unsigned len; friend const binary_pattern operator + (const binary_pattern& x, const binary_pattern& y); friend const binary_pattern operator ^ (const binary_pattern& x, const binary_pattern& y); friend bool operator == (const binary_pattern& x, const binary_pattern& y); friend bool operator != (const binary_pattern& x, const binary_pattern& y); friend void inverse(std::list<binary_pattern>& pats, std::list<binary_pattern>& result); friend void exclude_cube(std::list<binary_pattern>& pats, const binary_pattern& cube); } BinPattern; /** Concatenate two patterns. * @param x The high order bits. * @param y The low order bits. */ const binary_pattern operator + (const binary_pattern& x, const binary_pattern& y); /** Consensus of two patterns. */ const binary_pattern operator ^ (const binary_pattern& x, const binary_pattern& y); /** The equality operator */ bool operator == (const BinPattern& x, const BinPattern& y); /** The inequality operator */ bool operator != (const BinPattern& x, const BinPattern& y); /** Inverion of the boolean space. * @param pats The original space. * @param result The inverted space. */ void inverse(std::list<binary_pattern>& pats, std::list<binary_pattern>& result); /** Exclude a cube from a list of cubes. * @param pats The cubes to work on. * @param cube The cube to exclude. */ void exclude_cube(std::list<binary_pattern>& pats, const binary_pattern& cube); /** Output the pattern. */ std::ostream& operator << (std::ostream& os, const BinPattern& x); #endif |
