contrib/llvm/utils/TableGen/CodeGenRegisters.cpp

   1 //===- CodeGenRegisters.cpp - Register and RegisterClass Info -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines structures to encapsulate information gleaned from the
  11 // target register and register class definitions.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "CodeGenRegisters.h"
  16 #include "CodeGenTarget.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/StringExtras.h"
  19
  20 using namespace llvm;
  21
  22 //===----------------------------------------------------------------------===//
  23 //                              CodeGenRegister
  24 //===----------------------------------------------------------------------===//
  25
  26 CodeGenRegister::CodeGenRegister(Record *R, unsigned Enum)
  27   : TheDef(R),
  28     EnumValue(Enum),
  29     CostPerUse(R->getValueAsInt("CostPerUse")),
  30     SubRegsComplete(false)
  31 {}
  32
  33 const std::string &CodeGenRegister::getName() const {
  34   return TheDef->getName();
  35 }
  36
  37 namespace {
  38   struct Orphan {
  39     CodeGenRegister *SubReg;
  40     Record *First, *Second;
  41     Orphan(CodeGenRegister *r, Record *a, Record *b)
  42       : SubReg(r), First(a), Second(b) {}
  43   };
  44 }
  45
  46 const CodeGenRegister::SubRegMap &
  47 CodeGenRegister::getSubRegs(CodeGenRegBank &RegBank) {
  48   // Only compute this map once.
  49   if (SubRegsComplete)
  50     return SubRegs;
  51   SubRegsComplete = true;
  52
  53   std::vector<Record*> SubList = TheDef->getValueAsListOfDefs("SubRegs");
  54   std::vector<Record*> Indices = TheDef->getValueAsListOfDefs("SubRegIndices");
  55   if (SubList.size() != Indices.size())
  56     throw TGError(TheDef->getLoc(), "Register " + getName() +
  57                   " SubRegIndices doesn't match SubRegs");
  58
  59   // First insert the direct subregs and make sure they are fully indexed.
  60   for (unsigned i = 0, e = SubList.size(); i != e; ++i) {
  61     CodeGenRegister *SR = RegBank.getReg(SubList[i]);
  62     if (!SubRegs.insert(std::make_pair(Indices[i], SR)).second)
  63       throw TGError(TheDef->getLoc(), "SubRegIndex " + Indices[i]->getName() +
  64                     " appears twice in Register " + getName());
  65   }
  66
  67   // Keep track of inherited subregs and how they can be reached.
  68   SmallVector<Orphan, 8> Orphans;
  69
  70   // Clone inherited subregs and place duplicate entries on Orphans.
  71   // Here the order is important - earlier subregs take precedence.
  72   for (unsigned i = 0, e = SubList.size(); i != e; ++i) {
  73     CodeGenRegister *SR = RegBank.getReg(SubList[i]);
  74     const SubRegMap &Map = SR->getSubRegs(RegBank);
  75     for (SubRegMap::const_iterator SI = Map.begin(), SE = Map.end(); SI != SE;
  76          ++SI)
  77       if (!SubRegs.insert(*SI).second)
  78         Orphans.push_back(Orphan(SI->second, Indices[i], SI->first));
  79   }
  80
  81   // Process the composites.
  82   ListInit *Comps = TheDef->getValueAsListInit("CompositeIndices");
  83   for (unsigned i = 0, e = Comps->size(); i != e; ++i) {
  84     DagInit *Pat = dynamic_cast<DagInit*>(Comps->getElement(i));
  85     if (!Pat)
  86       throw TGError(TheDef->getLoc(), "Invalid dag '" +
  87                     Comps->getElement(i)->getAsString() +
  88                     "' in CompositeIndices");
  89     DefInit *BaseIdxInit = dynamic_cast<DefInit*>(Pat->getOperator());
  90     if (!BaseIdxInit || !BaseIdxInit->getDef()->isSubClassOf("SubRegIndex"))
  91       throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " +
  92                     Pat->getAsString());
  93
  94     // Resolve list of subreg indices into R2.
  95     CodeGenRegister *R2 = this;
  96     for (DagInit::const_arg_iterator di = Pat->arg_begin(),
  97          de = Pat->arg_end(); di != de; ++di) {
  98       DefInit *IdxInit = dynamic_cast<DefInit*>(*di);
  99       if (!IdxInit || !IdxInit->getDef()->isSubClassOf("SubRegIndex"))
 100         throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " +
 101                       Pat->getAsString());
 102       const SubRegMap &R2Subs = R2->getSubRegs(RegBank);
 103       SubRegMap::const_iterator ni = R2Subs.find(IdxInit->getDef());
 104       if (ni == R2Subs.end())
 105         throw TGError(TheDef->getLoc(), "Composite " + Pat->getAsString() +
 106                       " refers to bad index in " + R2->getName());
 107       R2 = ni->second;
 108     }
 109
 110     // Insert composite index. Allow overriding inherited indices etc.
 111     SubRegs[BaseIdxInit->getDef()] = R2;
 112
 113     // R2 is no longer an orphan.
 114     for (unsigned j = 0, je = Orphans.size(); j != je; ++j)
 115       if (Orphans[j].SubReg == R2)
 116           Orphans[j].SubReg = 0;
 117   }
 118
 119   // Now Orphans contains the inherited subregisters without a direct index.
 120   // Create inferred indexes for all missing entries.
 121   for (unsigned i = 0, e = Orphans.size(); i != e; ++i) {
 122     Orphan &O = Orphans[i];
 123     if (!O.SubReg)
 124       continue;
 125     SubRegs[RegBank.getCompositeSubRegIndex(O.First, O.Second, true)] =
 126       O.SubReg;
 127   }
 128   return SubRegs;
 129 }
 130
 131 //===----------------------------------------------------------------------===//
 132 //                            CodeGenRegisterClass
 133 //===----------------------------------------------------------------------===//
 134
 135 CodeGenRegisterClass::CodeGenRegisterClass(Record *R) : TheDef(R) {
 136   // Rename anonymous register classes.
 137   if (R->getName().size() > 9 && R->getName()[9] == '.') {
 138     static unsigned AnonCounter = 0;
 139     R->setName("AnonRegClass_"+utostr(AnonCounter++));
 140   }
 141
 142   std::vector<Record*> TypeList = R->getValueAsListOfDefs("RegTypes");
 143   for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
 144     Record *Type = TypeList[i];
 145     if (!Type->isSubClassOf("ValueType"))
 146       throw "RegTypes list member '" + Type->getName() +
 147         "' does not derive from the ValueType class!";
 148     VTs.push_back(getValueType(Type));
 149   }
 150   assert(!VTs.empty() && "RegisterClass must contain at least one ValueType!");
 151
 152   std::vector<Record*> RegList = R->getValueAsListOfDefs("MemberList");
 153   for (unsigned i = 0, e = RegList.size(); i != e; ++i) {
 154     Record *Reg = RegList[i];
 155     if (!Reg->isSubClassOf("Register"))
 156       throw "Register Class member '" + Reg->getName() +
 157             "' does not derive from the Register class!";
 158     Elements.push_back(Reg);
 159   }
 160
 161   // SubRegClasses is a list<dag> containing (RC, subregindex, ...) dags.
 162   ListInit *SRC = R->getValueAsListInit("SubRegClasses");
 163   for (ListInit::const_iterator i = SRC->begin(), e = SRC->end(); i != e; ++i) {
 164     DagInit *DAG = dynamic_cast<DagInit*>(*i);
 165     if (!DAG) throw "SubRegClasses must contain DAGs";
 166     DefInit *DAGOp = dynamic_cast<DefInit*>(DAG->getOperator());
 167     Record *RCRec;
 168     if (!DAGOp || !(RCRec = DAGOp->getDef())->isSubClassOf("RegisterClass"))
 169       throw "Operator '" + DAG->getOperator()->getAsString() +
 170         "' in SubRegClasses is not a RegisterClass";
 171     // Iterate over args, all SubRegIndex instances.
 172     for (DagInit::const_arg_iterator ai = DAG->arg_begin(), ae = DAG->arg_end();
 173          ai != ae; ++ai) {
 174       DefInit *Idx = dynamic_cast<DefInit*>(*ai);
 175       Record *IdxRec;
 176       if (!Idx || !(IdxRec = Idx->getDef())->isSubClassOf("SubRegIndex"))
 177         throw "Argument '" + (*ai)->getAsString() +
 178           "' in SubRegClasses is not a SubRegIndex";
 179       if (!SubRegClasses.insert(std::make_pair(IdxRec, RCRec)).second)
 180         throw "SubRegIndex '" + IdxRec->getName() + "' mentioned twice";
 181     }
 182   }
 183
 184   // Allow targets to override the size in bits of the RegisterClass.
 185   unsigned Size = R->getValueAsInt("Size");
 186
 187   Namespace = R->getValueAsString("Namespace");
 188   SpillSize = Size ? Size : EVT(VTs[0]).getSizeInBits();
 189   SpillAlignment = R->getValueAsInt("Alignment");
 190   CopyCost = R->getValueAsInt("CopyCost");
 191   Allocatable = R->getValueAsBit("isAllocatable");
 192   MethodBodies = R->getValueAsCode("MethodBodies");
 193   MethodProtos = R->getValueAsCode("MethodProtos");
 194 }
 195
 196 const std::string &CodeGenRegisterClass::getName() const {
 197   return TheDef->getName();
 198 }
 199
 200 //===----------------------------------------------------------------------===//
 201 //                               CodeGenRegBank
 202 //===----------------------------------------------------------------------===//
 203
 204 CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) {
 205   // Read in the user-defined (named) sub-register indices.
 206   // More indices will be synthesized later.
 207   SubRegIndices = Records.getAllDerivedDefinitions("SubRegIndex");
 208   std::sort(SubRegIndices.begin(), SubRegIndices.end(), LessRecord());
 209   NumNamedIndices = SubRegIndices.size();
 210
 211   // Read in the register definitions.
 212   std::vector<Record*> Regs = Records.getAllDerivedDefinitions("Register");
 213   std::sort(Regs.begin(), Regs.end(), LessRecord());
 214   Registers.reserve(Regs.size());
 215   // Assign the enumeration values.
 216   for (unsigned i = 0, e = Regs.size(); i != e; ++i)
 217     Registers.push_back(CodeGenRegister(Regs[i], i + 1));
 218 }
 219
 220 CodeGenRegister *CodeGenRegBank::getReg(Record *Def) {
 221   if (Def2Reg.empty())
 222     for (unsigned i = 0, e = Registers.size(); i != e; ++i)
 223       Def2Reg[Registers[i].TheDef] = &Registers[i];
 224
 225   if (CodeGenRegister *Reg = Def2Reg[Def])
 226     return Reg;
 227
 228   throw TGError(Def->getLoc(), "Not a known Register!");
 229 }
 230
 231 Record *CodeGenRegBank::getCompositeSubRegIndex(Record *A, Record *B,
 232                                                 bool create) {
 233   // Look for an existing entry.
 234   Record *&Comp = Composite[std::make_pair(A, B)];
 235   if (Comp || !create)
 236     return Comp;
 237
 238   // None exists, synthesize one.
 239   std::string Name = A->getName() + "_then_" + B->getName();
 240   Comp = new Record(Name, SMLoc(), Records);
 241   Records.addDef(Comp);
 242   SubRegIndices.push_back(Comp);
 243   return Comp;
 244 }
 245
 246 unsigned CodeGenRegBank::getSubRegIndexNo(Record *idx) {
 247   std::vector<Record*>::const_iterator i =
 248     std::find(SubRegIndices.begin(), SubRegIndices.end(), idx);
 249   assert(i != SubRegIndices.end() && "Not a SubRegIndex");
 250   return (i - SubRegIndices.begin()) + 1;
 251 }
 252
 253 void CodeGenRegBank::computeComposites() {
 254   // Precompute all sub-register maps. This will create Composite entries for
 255   // all inferred sub-register indices.
 256   for (unsigned i = 0, e = Registers.size(); i != e; ++i)
 257     Registers[i].getSubRegs(*this);
 258
 259   for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
 260     CodeGenRegister *Reg1 = &Registers[i];
 261     const CodeGenRegister::SubRegMap &SRM1 = Reg1->getSubRegs(*this);
 262     for (CodeGenRegister::SubRegMap::const_iterator i1 = SRM1.begin(),
 263          e1 = SRM1.end(); i1 != e1; ++i1) {
 264       Record *Idx1 = i1->first;
 265       CodeGenRegister *Reg2 = i1->second;
 266       // Ignore identity compositions.
 267       if (Reg1 == Reg2)
 268         continue;
 269       const CodeGenRegister::SubRegMap &SRM2 = Reg2->getSubRegs(*this);
 270       // Try composing Idx1 with another SubRegIndex.
 271       for (CodeGenRegister::SubRegMap::const_iterator i2 = SRM2.begin(),
 272            e2 = SRM2.end(); i2 != e2; ++i2) {
 273         std::pair<Record*, Record*> IdxPair(Idx1, i2->first);
 274         CodeGenRegister *Reg3 = i2->second;
 275         // Ignore identity compositions.
 276         if (Reg2 == Reg3)
 277           continue;
 278         // OK Reg1:IdxPair == Reg3. Find the index with Reg:Idx == Reg3.
 279         for (CodeGenRegister::SubRegMap::const_iterator i1d = SRM1.begin(),
 280              e1d = SRM1.end(); i1d != e1d; ++i1d) {
 281           if (i1d->second == Reg3) {
 282             std::pair<CompositeMap::iterator, bool> Ins =
 283               Composite.insert(std::make_pair(IdxPair, i1d->first));
 284             // Conflicting composition? Emit a warning but allow it.
 285             if (!Ins.second && Ins.first->second != i1d->first) {
 286               errs() << "Warning: SubRegIndex " << getQualifiedName(Idx1)
 287                      << " and " << getQualifiedName(IdxPair.second)
 288                      << " compose ambiguously as "
 289                      << getQualifiedName(Ins.first->second) << " or "
 290                      << getQualifiedName(i1d->first) << "\n";
 291             }
 292           }
 293         }
 294       }
 295     }
 296   }
 297
 298   // We don't care about the difference between (Idx1, Idx2) -> Idx2 and invalid
 299   // compositions, so remove any mappings of that form.
 300   for (CompositeMap::iterator i = Composite.begin(), e = Composite.end();
 301        i != e;) {
 302     CompositeMap::iterator j = i;
 303     ++i;
 304     if (j->first.second == j->second)
 305       Composite.erase(j);
 306   }
 307 }
 308
 309 void CodeGenRegBank::computeDerivedInfo() {
 310   computeComposites();
 311 }
 312