CodeGenMapTable.cpp [plain text]
#include "CodeGenTarget.h"
#include "llvm/Support/Format.h"
#include "llvm/TableGen/Error.h"
using namespace llvm;
typedef std::map<std::string, std::vector<Record*> > InstrRelMapTy;
typedef std::map<std::vector<Init*>, std::vector<Record*> > RowInstrMapTy;
namespace {
class InstrMap {
private:
std::string Name;
std::string FilterClass;
ListInit *RowFields;
ListInit *ColFields;
ListInit *KeyCol;
std::vector<ListInit*> ValueCols;
public:
InstrMap(Record* MapRec) {
Name = MapRec->getName();
const RecordVal *Filter = MapRec->getValue("FilterClass");
FilterClass = Filter->getValue()->getAsUnquotedString();
RowFields = MapRec->getValueAsListInit("RowFields");
ColFields = MapRec->getValueAsListInit("ColFields");
KeyCol = MapRec->getValueAsListInit("KeyCol");
ListInit *ColValList = MapRec->getValueAsListInit("ValueCols");
if (ColValList->getSize() == 0)
PrintFatalError(MapRec->getLoc(), "InstrMapping record `" +
MapRec->getName() + "' has empty " + "`ValueCols' field!");
for (unsigned i = 0, e = ColValList->getSize(); i < e; i++) {
ListInit *ColI = dyn_cast<ListInit>(ColValList->getElement(i));
if (ColI->getSize() != ColFields->getSize())
PrintFatalError(MapRec->getLoc(), "Record `" + MapRec->getName() +
"', field `ValueCols' entries don't match with " +
" the entries in 'ColFields'!");
ValueCols.push_back(ColI);
}
}
std::string getName() const {
return Name;
}
std::string getFilterClass() {
return FilterClass;
}
ListInit *getRowFields() const {
return RowFields;
}
ListInit *getColFields() const {
return ColFields;
}
ListInit *getKeyCol() const {
return KeyCol;
}
const std::vector<ListInit*> &getValueCols() const {
return ValueCols;
}
};
}
namespace {
class MapTableEmitter {
private:
const CodeGenTarget &Target;
InstrMap InstrMapDesc;
std::vector<Record*> InstrDefs;
RowInstrMapTy RowInstrMap;
std::vector<Record*> KeyInstrVec;
DenseMap<Record*, std::vector<Record*> > MapTable;
public:
MapTableEmitter(CodeGenTarget &Target, RecordKeeper &Records, Record *IMRec):
Target(Target), InstrMapDesc(IMRec) {
const std::string FilterClass = InstrMapDesc.getFilterClass();
InstrDefs = Records.getAllDerivedDefinitions(FilterClass);
}
void buildRowInstrMap();
bool isKeyColInstr(Record* CurInstr);
Record *getInstrForColumn(Record *KeyInstr, ListInit *CurValueCol);
void buildMapTable();
void emitBinSearch(raw_ostream &OS, unsigned TableSize);
void emitTablesWithFunc(raw_ostream &OS);
unsigned emitBinSearchTable(raw_ostream &OS);
void emitMapFuncBody(raw_ostream &OS, unsigned TableSize);
};
}
void MapTableEmitter::buildRowInstrMap() {
for (unsigned i = 0, e = InstrDefs.size(); i < e; i++) {
Record *CurInstr = InstrDefs[i];
std::vector<Init*> KeyValue;
ListInit *RowFields = InstrMapDesc.getRowFields();
for (unsigned j = 0, endRF = RowFields->getSize(); j < endRF; j++) {
Init *RowFieldsJ = RowFields->getElement(j);
Init *CurInstrVal = CurInstr->getValue(RowFieldsJ)->getValue();
KeyValue.push_back(CurInstrVal);
}
if (isKeyColInstr(CurInstr))
KeyInstrVec.push_back(CurInstr);
RowInstrMap[KeyValue].push_back(CurInstr);
}
}
bool MapTableEmitter::isKeyColInstr(Record* CurInstr) {
ListInit *ColFields = InstrMapDesc.getColFields();
ListInit *KeyCol = InstrMapDesc.getKeyCol();
bool MatchFound = true;
for (unsigned j = 0, endCF = ColFields->getSize();
(j < endCF) && MatchFound; j++) {
RecordVal *ColFieldName = CurInstr->getValue(ColFields->getElement(j));
std::string CurInstrVal = ColFieldName->getValue()->getAsUnquotedString();
std::string KeyColValue = KeyCol->getElement(j)->getAsUnquotedString();
MatchFound = (CurInstrVal == KeyColValue);
}
return MatchFound;
}
void MapTableEmitter::buildMapTable() {
const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols();
unsigned NumOfCols = ValueCols.size();
for (unsigned j = 0, endKI = KeyInstrVec.size(); j < endKI; j++) {
Record *CurKeyInstr = KeyInstrVec[j];
std::vector<Record*> ColInstrVec(NumOfCols);
for (unsigned ColIdx = 0; ColIdx < NumOfCols; ColIdx++) {
ListInit *CurValueCol = ValueCols[ColIdx];
Record *ColInstr = getInstrForColumn(CurKeyInstr, CurValueCol);
ColInstrVec[ColIdx] = ColInstr;
}
MapTable[CurKeyInstr] = ColInstrVec;
}
}
Record *MapTableEmitter::getInstrForColumn(Record *KeyInstr,
ListInit *CurValueCol) {
ListInit *RowFields = InstrMapDesc.getRowFields();
std::vector<Init*> KeyValue;
for (unsigned j = 0, endRF = RowFields->getSize(); j < endRF; j++) {
Init *RowFieldsJ = RowFields->getElement(j);
Init *KeyInstrVal = KeyInstr->getValue(RowFieldsJ)->getValue();
KeyValue.push_back(KeyInstrVal);
}
const std::vector<Record*> &RelatedInstrVec = RowInstrMap[KeyValue];
ListInit *ColFields = InstrMapDesc.getColFields();
Record *MatchInstr = NULL;
for (unsigned i = 0, e = RelatedInstrVec.size(); i < e; i++) {
bool MatchFound = true;
Record *CurInstr = RelatedInstrVec[i];
for (unsigned j = 0, endCF = ColFields->getSize();
(j < endCF) && MatchFound; j++) {
Init *ColFieldJ = ColFields->getElement(j);
Init *CurInstrInit = CurInstr->getValue(ColFieldJ)->getValue();
std::string CurInstrVal = CurInstrInit->getAsUnquotedString();
Init *ColFieldJVallue = CurValueCol->getElement(j);
MatchFound = (CurInstrVal == ColFieldJVallue->getAsUnquotedString());
}
if (MatchFound) {
if (MatchInstr) PrintFatalError("Multiple matches found for `" + KeyInstr->getName() +
"', for the relation `" + InstrMapDesc.getName());
MatchInstr = CurInstr;
}
}
return MatchInstr;
}
unsigned MapTableEmitter::emitBinSearchTable(raw_ostream &OS) {
const std::vector<const CodeGenInstruction*> &NumberedInstructions =
Target.getInstructionsByEnumValue();
std::string TargetName = Target.getName();
const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols();
unsigned NumCol = ValueCols.size();
unsigned TotalNumInstr = NumberedInstructions.size();
unsigned TableSize = 0;
OS << "static const uint16_t "<<InstrMapDesc.getName();
OS << "Table[]["<< NumCol+1 << "] = {\n";
for (unsigned i = 0; i < TotalNumInstr; i++) {
Record *CurInstr = NumberedInstructions[i]->TheDef;
std::vector<Record*> ColInstrs = MapTable[CurInstr];
std::string OutStr("");
unsigned RelExists = 0;
if (ColInstrs.size()) {
for (unsigned j = 0; j < NumCol; j++) {
if (ColInstrs[j] != NULL) {
RelExists = 1;
OutStr += ", ";
OutStr += TargetName;
OutStr += "::";
OutStr += ColInstrs[j]->getName();
} else { OutStr += ", -1";}
}
if (RelExists) {
OS << " { " << TargetName << "::" << CurInstr->getName();
OS << OutStr <<" },\n";
TableSize++;
}
}
}
if (!TableSize) {
OS << " { " << TargetName << "::" << "INSTRUCTION_LIST_END, ";
OS << TargetName << "::" << "INSTRUCTION_LIST_END }";
}
OS << "}; // End of " << InstrMapDesc.getName() << "Table\n\n";
return TableSize;
}
void MapTableEmitter::emitBinSearch(raw_ostream &OS, unsigned TableSize) {
OS << " unsigned mid;\n";
OS << " unsigned start = 0;\n";
OS << " unsigned end = " << TableSize << ";\n";
OS << " while (start < end) {\n";
OS << " mid = start + (end - start)/2;\n";
OS << " if (Opcode == " << InstrMapDesc.getName() << "Table[mid][0]) {\n";
OS << " break;\n";
OS << " }\n";
OS << " if (Opcode < " << InstrMapDesc.getName() << "Table[mid][0])\n";
OS << " end = mid;\n";
OS << " else\n";
OS << " start = mid + 1;\n";
OS << " }\n";
OS << " if (start == end)\n";
OS << " return -1; // Instruction doesn't exist in this table.\n\n";
}
void MapTableEmitter::emitMapFuncBody(raw_ostream &OS,
unsigned TableSize) {
ListInit *ColFields = InstrMapDesc.getColFields();
const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols();
emitBinSearch(OS, TableSize);
if (ValueCols.size() > 1) {
for (unsigned i = 0, e = ValueCols.size(); i < e; i++) {
ListInit *ColumnI = ValueCols[i];
for (unsigned j = 0, ColSize = ColumnI->getSize(); j < ColSize; j++) {
std::string ColName = ColFields->getElement(j)->getAsUnquotedString();
OS << " if (in" << ColName;
OS << " == ";
OS << ColName << "_" << ColumnI->getElement(j)->getAsUnquotedString();
if (j < ColumnI->getSize() - 1) OS << " && ";
else OS << ")\n";
}
OS << " return " << InstrMapDesc.getName();
OS << "Table[mid]["<<i+1<<"];\n";
}
OS << " return -1;";
}
else
OS << " return " << InstrMapDesc.getName() << "Table[mid][1];\n";
OS <<"}\n\n";
}
void MapTableEmitter::emitTablesWithFunc(raw_ostream &OS) {
ListInit *ColFields = InstrMapDesc.getColFields();
const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols();
OS << "// "<< InstrMapDesc.getName() << "\n";
OS << "int "<< InstrMapDesc.getName() << "(uint16_t Opcode";
if (ValueCols.size() > 1) {
for (unsigned i = 0, e = ColFields->getSize(); i < e; i++) {
std::string ColName = ColFields->getElement(i)->getAsUnquotedString();
OS << ", enum " << ColName << " in" << ColName << ") {\n";
}
} else { OS << ") {\n"; }
unsigned TableSize = emitBinSearchTable(OS);
emitMapFuncBody(OS, TableSize);
}
static void emitEnums(raw_ostream &OS, RecordKeeper &Records) {
std::vector<Record*> InstrMapVec;
InstrMapVec = Records.getAllDerivedDefinitions("InstrMapping");
std::map<std::string, std::vector<Init*> > ColFieldValueMap;
for (unsigned i = 0, e = InstrMapVec.size(); i < e; i++) {
Record *CurMap = InstrMapVec[i];
ListInit *ColFields;
ColFields = CurMap->getValueAsListInit("ColFields");
ListInit *List = CurMap->getValueAsListInit("ValueCols");
std::vector<ListInit*> ValueCols;
unsigned ListSize = List->getSize();
for (unsigned j = 0; j < ListSize; j++) {
ListInit *ListJ = dyn_cast<ListInit>(List->getElement(j));
if (ListJ->getSize() != ColFields->getSize())
PrintFatalError("Record `" + CurMap->getName() + "', field "
"`ValueCols' entries don't match with the entries in 'ColFields' !");
ValueCols.push_back(ListJ);
}
for (unsigned j = 0, endCF = ColFields->getSize(); j < endCF; j++) {
for (unsigned k = 0; k < ListSize; k++){
std::string ColName = ColFields->getElement(j)->getAsUnquotedString();
ColFieldValueMap[ColName].push_back((ValueCols[k])->getElement(j));
}
}
}
for (std::map<std::string, std::vector<Init*> >::iterator
II = ColFieldValueMap.begin(), IE = ColFieldValueMap.end();
II != IE; II++) {
std::vector<Init*> FieldValues = (*II).second;
for (unsigned i = 0; i < FieldValues.size() - 1; i++) {
Init *CurVal = FieldValues[i];
for (unsigned j = i+1; j < FieldValues.size(); j++) {
if (CurVal == FieldValues[j]) {
FieldValues.erase(FieldValues.begin()+j);
}
}
}
OS << "enum " << (*II).first << " {\n";
for (unsigned i = 0, endFV = FieldValues.size(); i < endFV; i++) {
OS << "\t" << (*II).first << "_" << FieldValues[i]->getAsUnquotedString();
if (i != endFV - 1)
OS << ",\n";
else
OS << "\n};\n\n";
}
}
}
namespace llvm {
void EmitMapTable(RecordKeeper &Records, raw_ostream &OS) {
CodeGenTarget Target(Records);
std::string TargetName = Target.getName();
std::vector<Record*> InstrMapVec;
InstrMapVec = Records.getAllDerivedDefinitions("InstrMapping");
if (!InstrMapVec.size())
return;
OS << "#ifdef GET_INSTRMAP_INFO\n";
OS << "#undef GET_INSTRMAP_INFO\n";
OS << "namespace llvm {\n\n";
OS << "namespace " << TargetName << " {\n\n";
emitEnums(OS, Records);
for (unsigned i = 0, e = InstrMapVec.size(); i < e; i++) {
MapTableEmitter IMap(Target, Records, InstrMapVec[i]);
IMap.buildRowInstrMap();
IMap.buildMapTable();
IMap.emitTablesWithFunc(OS);
}
OS << "} // End " << TargetName << " namespace\n";
OS << "} // End llvm namespace\n";
OS << "#endif // GET_INSTRMAP_INFO\n\n";
}
}