utils/TableGen/AsmWriterEmitter.cpp

   1 //===- AsmWriterEmitter.cpp - Generate an assembly writer -----------------===//
   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 tablegen backend is emits an assembly printer for the current target.
  11 // Note that this is currently fairly skeletal, but will grow over time.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "AsmWriterEmitter.h"
  16 #include "CodeGenTarget.h"
  17 #include "Record.h"
  18 #include "llvm/ADT/StringExtras.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/MathExtras.h"
  21 #include <algorithm>
  22 #include <sstream>
  23 #include <iostream>
  24 using namespace llvm;
  25
  26 static bool isIdentChar(char C) {
  27   return (C >= 'a' && C <= 'z') ||
  28          (C >= 'A' && C <= 'Z') ||
  29          (C >= '0' && C <= '9') ||
  30          C == '_';
  31 }
  32
  33 // This should be an anon namespace, this works around a GCC warning.
  34 namespace llvm {
  35   struct AsmWriterOperand {
  36     enum OpType {
  37       // Output this text surrounded by quotes to the asm.
  38       isLiteralTextOperand,
  39       // This is the name of a routine to call to print the operand.
  40       isMachineInstrOperand,
  41       // Output this text verbatim to the asm writer.  It is code that
  42       // will output some text to the asm.
  43       isLiteralStatementOperand
  44     } OperandType;
  45
  46     /// Str - For isLiteralTextOperand, this IS the literal text.  For
  47     /// isMachineInstrOperand, this is the PrinterMethodName for the operand..
  48     /// For isLiteralStatementOperand, this is the code to insert verbatim
  49     /// into the asm writer.
  50     std::string Str;
  51
  52     /// MiOpNo - For isMachineInstrOperand, this is the operand number of the
  53     /// machine instruction.
  54     unsigned MIOpNo;
  55
  56     /// MiModifier - For isMachineInstrOperand, this is the modifier string for
  57     /// an operand, specified with syntax like ${opname:modifier}.
  58     std::string MiModifier;
  59
  60     // To make VS STL happy
  61     AsmWriterOperand(OpType op = isLiteralTextOperand):OperandType(op) {}
  62
  63     AsmWriterOperand(const std::string &LitStr,
  64                      OpType op = isLiteralTextOperand)
  65       : OperandType(op), Str(LitStr) {}
  66
  67     AsmWriterOperand(const std::string &Printer, unsigned OpNo,
  68                      const std::string &Modifier,
  69                      OpType op = isMachineInstrOperand)
  70       : OperandType(op), Str(Printer), MIOpNo(OpNo),
  71       MiModifier(Modifier) {}
  72
  73     bool operator!=(const AsmWriterOperand &Other) const {
  74       if (OperandType != Other.OperandType || Str != Other.Str) return true;
  75       if (OperandType == isMachineInstrOperand)
  76         return MIOpNo != Other.MIOpNo || MiModifier != Other.MiModifier;
  77       return false;
  78     }
  79     bool operator==(const AsmWriterOperand &Other) const {
  80       return !operator!=(Other);
  81     }
  82
  83     /// getCode - Return the code that prints this operand.
  84     std::string getCode() const;
  85   };
  86 }
  87
  88 namespace llvm {
  89   class AsmWriterInst {
  90   public:
  91     std::vector<AsmWriterOperand> Operands;
  92     const CodeGenInstruction *CGI;
  93
  94     AsmWriterInst(const CodeGenInstruction &CGI, unsigned Variant);
  95
  96     /// MatchesAllButOneOp - If this instruction is exactly identical to the
  97     /// specified instruction except for one differing operand, return the
  98     /// differing operand number.  Otherwise return ~0.
  99     unsigned MatchesAllButOneOp(const AsmWriterInst &Other) const;
 100
 101   private:
 102     void AddLiteralString(const std::string &Str) {
 103       // If the last operand was already a literal text string, append this to
 104       // it, otherwise add a new operand.
 105       if (!Operands.empty() &&
 106           Operands.back().OperandType == AsmWriterOperand::isLiteralTextOperand)
 107         Operands.back().Str.append(Str);
 108       else
 109         Operands.push_back(AsmWriterOperand(Str));
 110     }
 111   };
 112 }
 113
 114
 115 std::string AsmWriterOperand::getCode() const {
 116   if (OperandType == isLiteralTextOperand)
 117     return "O << \"" + Str + "\"; ";
 118
 119   if (OperandType == isLiteralStatementOperand) {
 120     return Str;
 121   }
 122
 123   std::string Result = Str + "(MI";
 124   if (MIOpNo != ~0U)
 125     Result += ", " + utostr(MIOpNo);
 126   if (!MiModifier.empty())
 127     Result += ", \"" + MiModifier + '"';
 128   return Result + "); ";
 129 }
 130
 131
 132 /// ParseAsmString - Parse the specified Instruction's AsmString into this
 133 /// AsmWriterInst.
 134 ///
 135 AsmWriterInst::AsmWriterInst(const CodeGenInstruction &CGI, unsigned Variant) {
 136   this->CGI = &CGI;
 137   unsigned CurVariant = ~0U;  // ~0 if we are outside a {.|.|.} region, other #.
 138
 139   // NOTE: Any extensions to this code need to be mirrored in the
 140   // AsmPrinter::printInlineAsm code that executes as compile time (assuming
 141   // that inline asm strings should also get the new feature)!
 142   const std::string &AsmString = CGI.AsmString;
 143   std::string::size_type LastEmitted = 0;
 144   while (LastEmitted != AsmString.size()) {
 145     std::string::size_type DollarPos =
 146       AsmString.find_first_of("${|}\\", LastEmitted);
 147     if (DollarPos == std::string::npos) DollarPos = AsmString.size();
 148
 149     // Emit a constant string fragment.
 150
 151     if (DollarPos != LastEmitted) {
 152       if (CurVariant == Variant || CurVariant == ~0U) {
 153         for (; LastEmitted != DollarPos; ++LastEmitted)
 154           switch (AsmString[LastEmitted]) {
 155           case '\n':
 156             AddLiteralString("\\n");
 157             break;
 158           case '\t':
 159             Operands.push_back(
 160               // We recognize a tab as an operand delimeter.  Either
 161               // output column padding if enabled or emit a space.
 162               AsmWriterOperand("PadToColumn(OperandColumn++);\n",
 163                                AsmWriterOperand::isLiteralStatementOperand));
 164             break;
 165           case '"':
 166             AddLiteralString("\\\"");
 167             break;
 168           case '\\':
 169             AddLiteralString("\\\\");
 170             break;
 171           default:
 172             AddLiteralString(std::string(1, AsmString[LastEmitted]));
 173             break;
 174           }
 175       } else {
 176         LastEmitted = DollarPos;
 177       }
 178     } else if (AsmString[DollarPos] == '\\') {
 179       if (DollarPos+1 != AsmString.size() &&
 180           (CurVariant == Variant || CurVariant == ~0U)) {
 181         if (AsmString[DollarPos+1] == 'n') {
 182           AddLiteralString("\\n");
 183         } else if (AsmString[DollarPos+1] == 't') {
 184           Operands.push_back(
 185             // We recognize a tab as an operand delimeter.  Either
 186             // output column padding if enabled or emit a space.
 187             AsmWriterOperand("PadToColumn(OperandColumn++);\n",
 188                              AsmWriterOperand::isLiteralStatementOperand));
 189         } else if (std::string("${|}\\").find(AsmString[DollarPos+1])
 190                    != std::string::npos) {
 191           AddLiteralString(std::string(1, AsmString[DollarPos+1]));
 192         } else {
 193           throw "Non-supported escaped character found in instruction '" +
 194             CGI.TheDef->getName() + "'!";
 195         }
 196         LastEmitted = DollarPos+2;
 197         continue;
 198       }
 199     } else if (AsmString[DollarPos] == '{') {
 200       if (CurVariant != ~0U)
 201         throw "Nested variants found for instruction '" +
 202               CGI.TheDef->getName() + "'!";
 203       LastEmitted = DollarPos+1;
 204       CurVariant = 0;   // We are now inside of the variant!
 205     } else if (AsmString[DollarPos] == '|') {
 206       if (CurVariant == ~0U)
 207         throw "'|' character found outside of a variant in instruction '"
 208           + CGI.TheDef->getName() + "'!";
 209       ++CurVariant;
 210       ++LastEmitted;
 211     } else if (AsmString[DollarPos] == '}') {
 212       if (CurVariant == ~0U)
 213         throw "'}' character found outside of a variant in instruction '"
 214           + CGI.TheDef->getName() + "'!";
 215       ++LastEmitted;
 216       CurVariant = ~0U;
 217     } else if (DollarPos+1 != AsmString.size() &&
 218                AsmString[DollarPos+1] == '$') {
 219       if (CurVariant == Variant || CurVariant == ~0U) {
 220         AddLiteralString("$");  // "$$" -> $
 221       }
 222       LastEmitted = DollarPos+2;
 223     } else {
 224       // Get the name of the variable.
 225       std::string::size_type VarEnd = DollarPos+1;
 226
 227       // handle ${foo}bar as $foo by detecting whether the character following
 228       // the dollar sign is a curly brace.  If so, advance VarEnd and DollarPos
 229       // so the variable name does not contain the leading curly brace.
 230       bool hasCurlyBraces = false;
 231       if (VarEnd < AsmString.size() && '{' == AsmString[VarEnd]) {
 232         hasCurlyBraces = true;
 233         ++DollarPos;
 234         ++VarEnd;
 235       }
 236
 237       while (VarEnd < AsmString.size() && isIdentChar(AsmString[VarEnd]))
 238         ++VarEnd;
 239       std::string VarName(AsmString.begin()+DollarPos+1,
 240                           AsmString.begin()+VarEnd);
 241
 242       // Modifier - Support ${foo:modifier} syntax, where "modifier" is passed
 243       // into printOperand.  Also support ${:feature}, which is passed into
 244       // PrintSpecial.
 245       std::string Modifier;
 246
 247       // In order to avoid starting the next string at the terminating curly
 248       // brace, advance the end position past it if we found an opening curly
 249       // brace.
 250       if (hasCurlyBraces) {
 251         if (VarEnd >= AsmString.size())
 252           throw "Reached end of string before terminating curly brace in '"
 253                 + CGI.TheDef->getName() + "'";
 254
 255         // Look for a modifier string.
 256         if (AsmString[VarEnd] == ':') {
 257           ++VarEnd;
 258           if (VarEnd >= AsmString.size())
 259             throw "Reached end of string before terminating curly brace in '"
 260               + CGI.TheDef->getName() + "'";
 261
 262           unsigned ModifierStart = VarEnd;
 263           while (VarEnd < AsmString.size() && isIdentChar(AsmString[VarEnd]))
 264             ++VarEnd;
 265           Modifier = std::string(AsmString.begin()+ModifierStart,
 266                                  AsmString.begin()+VarEnd);
 267           if (Modifier.empty())
 268             throw "Bad operand modifier name in '"+ CGI.TheDef->getName() + "'";
 269         }
 270
 271         if (AsmString[VarEnd] != '}')
 272           throw "Variable name beginning with '{' did not end with '}' in '"
 273                 + CGI.TheDef->getName() + "'";
 274         ++VarEnd;
 275       }
 276       if (VarName.empty() && Modifier.empty())
 277         throw "Stray '$' in '" + CGI.TheDef->getName() +
 278               "' asm string, maybe you want $$?";
 279
 280       if (VarName.empty()) {
 281         // Just a modifier, pass this into PrintSpecial.
 282         Operands.push_back(AsmWriterOperand("PrintSpecial", ~0U, Modifier));
 283       } else {
 284         // Otherwise, normal operand.
 285         unsigned OpNo = CGI.getOperandNamed(VarName);
 286         CodeGenInstruction::OperandInfo OpInfo = CGI.OperandList[OpNo];
 287
 288         if (CurVariant == Variant || CurVariant == ~0U) {
 289           unsigned MIOp = OpInfo.MIOperandNo;
 290           Operands.push_back(AsmWriterOperand(OpInfo.PrinterMethodName, MIOp,
 291                                               Modifier));
 292         }
 293       }
 294       LastEmitted = VarEnd;
 295     }
 296   }
 297
 298   Operands.push_back(
 299     AsmWriterOperand("EmitComments(*MI);\n",
 300                      AsmWriterOperand::isLiteralStatementOperand));
 301   AddLiteralString("\\n");
 302 }
 303
 304 /// MatchesAllButOneOp - If this instruction is exactly identical to the
 305 /// specified instruction except for one differing operand, return the differing
 306 /// operand number.  If more than one operand mismatches, return ~1, otherwise
 307 /// if the instructions are identical return ~0.
 308 unsigned AsmWriterInst::MatchesAllButOneOp(const AsmWriterInst &Other)const{
 309   if (Operands.size() != Other.Operands.size()) return ~1;
 310
 311   unsigned MismatchOperand = ~0U;
 312   for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 313     if (Operands[i] != Other.Operands[i]) {
 314       if (MismatchOperand != ~0U)  // Already have one mismatch?
 315         return ~1U;
 316       else
 317         MismatchOperand = i;
 318     }
 319   }
 320   return MismatchOperand;
 321 }
 322
 323 static void PrintCases(std::vector<std::pair<std::string,
 324                        AsmWriterOperand> > &OpsToPrint, raw_ostream &O) {
 325   O << "    case " << OpsToPrint.back().first << ": ";
 326   AsmWriterOperand TheOp = OpsToPrint.back().second;
 327   OpsToPrint.pop_back();
 328
 329   // Check to see if any other operands are identical in this list, and if so,
 330   // emit a case label for them.
 331   for (unsigned i = OpsToPrint.size(); i != 0; --i)
 332     if (OpsToPrint[i-1].second == TheOp) {
 333       O << "\n    case " << OpsToPrint[i-1].first << ": ";
 334       OpsToPrint.erase(OpsToPrint.begin()+i-1);
 335     }
 336
 337   // Finally, emit the code.
 338   O << TheOp.getCode();
 339   O << "break;\n";
 340 }
 341
 342
 343 /// EmitInstructions - Emit the last instruction in the vector and any other
 344 /// instructions that are suitably similar to it.
 345 static void EmitInstructions(std::vector<AsmWriterInst> &Insts,
 346                              raw_ostream &O) {
 347   AsmWriterInst FirstInst = Insts.back();
 348   Insts.pop_back();
 349
 350   std::vector<AsmWriterInst> SimilarInsts;
 351   unsigned DifferingOperand = ~0;
 352   for (unsigned i = Insts.size(); i != 0; --i) {
 353     unsigned DiffOp = Insts[i-1].MatchesAllButOneOp(FirstInst);
 354     if (DiffOp != ~1U) {
 355       if (DifferingOperand == ~0U)  // First match!
 356         DifferingOperand = DiffOp;
 357
 358       // If this differs in the same operand as the rest of the instructions in
 359       // this class, move it to the SimilarInsts list.
 360       if (DifferingOperand == DiffOp || DiffOp == ~0U) {
 361         SimilarInsts.push_back(Insts[i-1]);
 362         Insts.erase(Insts.begin()+i-1);
 363       }
 364     }
 365   }
 366
 367   O << "  case " << FirstInst.CGI->Namespace << "::"
 368     << FirstInst.CGI->TheDef->getName() << ":\n";
 369   for (unsigned i = 0, e = SimilarInsts.size(); i != e; ++i)
 370     O << "  case " << SimilarInsts[i].CGI->Namespace << "::"
 371       << SimilarInsts[i].CGI->TheDef->getName() << ":\n";
 372   for (unsigned i = 0, e = FirstInst.Operands.size(); i != e; ++i) {
 373     if (i != DifferingOperand) {
 374       // If the operand is the same for all instructions, just print it.
 375       O << "    " << FirstInst.Operands[i].getCode();
 376     } else {
 377       // If this is the operand that varies between all of the instructions,
 378       // emit a switch for just this operand now.
 379       O << "    switch (MI->getOpcode()) {\n";
 380       std::vector<std::pair<std::string, AsmWriterOperand> > OpsToPrint;
 381       OpsToPrint.push_back(std::make_pair(FirstInst.CGI->Namespace + "::" +
 382                                           FirstInst.CGI->TheDef->getName(),
 383                                           FirstInst.Operands[i]));
 384
 385       for (unsigned si = 0, e = SimilarInsts.size(); si != e; ++si) {
 386         AsmWriterInst &AWI = SimilarInsts[si];
 387         OpsToPrint.push_back(std::make_pair(AWI.CGI->Namespace+"::"+
 388                                             AWI.CGI->TheDef->getName(),
 389                                             AWI.Operands[i]));
 390       }
 391       std::reverse(OpsToPrint.begin(), OpsToPrint.end());
 392       while (!OpsToPrint.empty())
 393         PrintCases(OpsToPrint, O);
 394       O << "    }";
 395     }
 396     O << "\n";
 397   }
 398   O << "    break;\n";
 399 }
 400
 401 void AsmWriterEmitter::
 402 FindUniqueOperandCommands(std::vector<std::string> &UniqueOperandCommands,
 403                           std::vector<unsigned> &InstIdxs,
 404                           std::vector<unsigned> &InstOpsUsed) const {
 405   InstIdxs.assign(NumberedInstructions.size(), ~0U);
 406
 407   // This vector parallels UniqueOperandCommands, keeping track of which
 408   // instructions each case are used for.  It is a comma separated string of
 409   // enums.
 410   std::vector<std::string> InstrsForCase;
 411   InstrsForCase.resize(UniqueOperandCommands.size());
 412   InstOpsUsed.assign(UniqueOperandCommands.size(), 0);
 413
 414   for (unsigned i = 0, e = NumberedInstructions.size(); i != e; ++i) {
 415     const AsmWriterInst *Inst = getAsmWriterInstByID(i);
 416     if (Inst == 0) continue;  // PHI, INLINEASM, DBG_LABEL, etc.
 417
 418     std::string Command;
 419     if (Inst->Operands.empty())
 420       continue;   // Instruction already done.
 421
 422     Command = "    " + Inst->Operands[0].getCode() + "\n";
 423
 424     // If this is the last operand, emit a return.
 425     if (Inst->Operands.size() == 1) {
 426       Command += "    return true;\n";
 427     }
 428
 429     // Check to see if we already have 'Command' in UniqueOperandCommands.
 430     // If not, add it.
 431     bool FoundIt = false;
 432     for (unsigned idx = 0, e = UniqueOperandCommands.size(); idx != e; ++idx)
 433       if (UniqueOperandCommands[idx] == Command) {
 434         InstIdxs[i] = idx;
 435         InstrsForCase[idx] += ", ";
 436         InstrsForCase[idx] += Inst->CGI->TheDef->getName();
 437         FoundIt = true;
 438         break;
 439       }
 440     if (!FoundIt) {
 441       InstIdxs[i] = UniqueOperandCommands.size();
 442       UniqueOperandCommands.push_back(Command);
 443       InstrsForCase.push_back(Inst->CGI->TheDef->getName());
 444
 445       // This command matches one operand so far.
 446       InstOpsUsed.push_back(1);
 447     }
 448   }
 449
 450   // For each entry of UniqueOperandCommands, there is a set of instructions
 451   // that uses it.  If the next command of all instructions in the set are
 452   // identical, fold it into the command.
 453   for (unsigned CommandIdx = 0, e = UniqueOperandCommands.size();
 454        CommandIdx != e; ++CommandIdx) {
 455
 456     for (unsigned Op = 1; ; ++Op) {
 457       // Scan for the first instruction in the set.
 458       std::vector<unsigned>::iterator NIT =
 459         std::find(InstIdxs.begin(), InstIdxs.end(), CommandIdx);
 460       if (NIT == InstIdxs.end()) break;  // No commonality.
 461
 462       // If this instruction has no more operands, we isn't anything to merge
 463       // into this command.
 464       const AsmWriterInst *FirstInst =
 465         getAsmWriterInstByID(NIT-InstIdxs.begin());
 466       if (!FirstInst || FirstInst->Operands.size() == Op)
 467         break;
 468
 469       // Otherwise, scan to see if all of the other instructions in this command
 470       // set share the operand.
 471       bool AllSame = true;
 472       // Keep track of the maximum, number of operands or any
 473       // instruction we see in the group.
 474       size_t MaxSize = FirstInst->Operands.size();
 475
 476       for (NIT = std::find(NIT+1, InstIdxs.end(), CommandIdx);
 477            NIT != InstIdxs.end();
 478            NIT = std::find(NIT+1, InstIdxs.end(), CommandIdx)) {
 479         // Okay, found another instruction in this command set.  If the operand
 480         // matches, we're ok, otherwise bail out.
 481         const AsmWriterInst *OtherInst =
 482           getAsmWriterInstByID(NIT-InstIdxs.begin());
 483
 484         if (OtherInst &&
 485             OtherInst->Operands.size() > FirstInst->Operands.size())
 486           MaxSize = std::max(MaxSize, OtherInst->Operands.size());
 487
 488         if (!OtherInst || OtherInst->Operands.size() == Op ||
 489             OtherInst->Operands[Op] != FirstInst->Operands[Op]) {
 490           AllSame = false;
 491           break;
 492         }
 493       }
 494       if (!AllSame) break;
 495
 496       // Okay, everything in this command set has the same next operand.  Add it
 497       // to UniqueOperandCommands and remember that it was consumed.
 498       std::string Command = "    " + FirstInst->Operands[Op].getCode() + "\n";
 499
 500       // If this is the last operand, emit a return after the code.
 501       if (FirstInst->Operands.size() == Op+1 &&
 502           // Don't early-out too soon.  Other instructions in this
 503           // group may have more operands.
 504           FirstInst->Operands.size() == MaxSize) {
 505         Command += "    return true;\n";
 506       }
 507
 508       UniqueOperandCommands[CommandIdx] += Command;
 509       InstOpsUsed[CommandIdx]++;
 510     }
 511   }
 512
 513   // Prepend some of the instructions each case is used for onto the case val.
 514   for (unsigned i = 0, e = InstrsForCase.size(); i != e; ++i) {
 515     std::string Instrs = InstrsForCase[i];
 516     if (Instrs.size() > 70) {
 517       Instrs.erase(Instrs.begin()+70, Instrs.end());
 518       Instrs += "...";
 519     }
 520
 521     if (!Instrs.empty())
 522       UniqueOperandCommands[i] = "    // " + Instrs + "\n" +
 523         UniqueOperandCommands[i];
 524   }
 525 }
 526
 527
 528
 529 void AsmWriterEmitter::run(raw_ostream &O) {
 530   EmitSourceFileHeader("Assembly Writer Source Fragment", O);
 531
 532   CodeGenTarget Target;
 533   Record *AsmWriter = Target.getAsmWriter();
 534   std::string ClassName = AsmWriter->getValueAsString("AsmWriterClassName");
 535   unsigned Variant = AsmWriter->getValueAsInt("Variant");
 536
 537   O <<
 538   "/// printInstruction - This method is automatically generated by tablegen\n"
 539   "/// from the instruction set description.  This method returns true if the\n"
 540   "/// machine instruction was sufficiently described to print it, otherwise\n"
 541   "/// it returns false.\n"
 542     "bool " << Target.getName() << ClassName
 543             << "::printInstruction(const MachineInstr *MI) {\n";
 544
 545   std::vector<AsmWriterInst> Instructions;
 546
 547   for (CodeGenTarget::inst_iterator I = Target.inst_begin(),
 548          E = Target.inst_end(); I != E; ++I)
 549     if (!I->second.AsmString.empty())
 550       Instructions.push_back(AsmWriterInst(I->second, Variant));
 551
 552   // Get the instruction numbering.
 553   Target.getInstructionsByEnumValue(NumberedInstructions);
 554
 555   // Compute the CodeGenInstruction -> AsmWriterInst mapping.  Note that not
 556   // all machine instructions are necessarily being printed, so there may be
 557   // target instructions not in this map.
 558   for (unsigned i = 0, e = Instructions.size(); i != e; ++i)
 559     CGIAWIMap.insert(std::make_pair(Instructions[i].CGI, &Instructions[i]));
 560
 561   // Build an aggregate string, and build a table of offsets into it.
 562   std::map<std::string, unsigned> StringOffset;
 563   std::string AggregateString;
 564   AggregateString.push_back(0);  // "\0"
 565   AggregateString.push_back(0);  // "\0"
 566
 567   /// OpcodeInfo - This encodes the index of the string to use for the first
 568   /// chunk of the output as well as indices used for operand printing.
 569   std::vector<unsigned> OpcodeInfo;
 570
 571   unsigned MaxStringIdx = 0;
 572   for (unsigned i = 0, e = NumberedInstructions.size(); i != e; ++i) {
 573     AsmWriterInst *AWI = CGIAWIMap[NumberedInstructions[i]];
 574     unsigned Idx;
 575     if (AWI == 0) {
 576       // Something not handled by the asmwriter printer.
 577       Idx = 0;
 578     } else if (AWI->Operands[0].OperandType !=
 579                         AsmWriterOperand::isLiteralTextOperand ||
 580                AWI->Operands[0].Str.empty()) {
 581       // Something handled by the asmwriter printer, but with no leading string.
 582       Idx = 1;
 583     } else {
 584       unsigned &Entry = StringOffset[AWI->Operands[0].Str];
 585       if (Entry == 0) {
 586         // Add the string to the aggregate if this is the first time found.
 587         MaxStringIdx = Entry = AggregateString.size();
 588         std::string Str = AWI->Operands[0].Str;
 589         UnescapeString(Str);
 590         AggregateString += Str;
 591         AggregateString += '\0';
 592       }
 593       Idx = Entry;
 594
 595       // Nuke the string from the operand list.  It is now handled!
 596       AWI->Operands.erase(AWI->Operands.begin());
 597     }
 598     OpcodeInfo.push_back(Idx);
 599   }
 600
 601   // Figure out how many bits we used for the string index.
 602   unsigned AsmStrBits = Log2_32_Ceil(MaxStringIdx+1);
 603
 604   // To reduce code size, we compactify common instructions into a few bits
 605   // in the opcode-indexed table.
 606   unsigned BitsLeft = 32-AsmStrBits;
 607
 608   std::vector<std::vector<std::string> > TableDrivenOperandPrinters;
 609
 610   bool isFirst = true;
 611   while (1) {
 612     std::vector<std::string> UniqueOperandCommands;
 613
 614     // For the first operand check, add a default value for instructions with
 615     // just opcode strings to use.
 616     if (isFirst) {
 617       UniqueOperandCommands.push_back("    return true;\n");
 618       isFirst = false;
 619     }
 620
 621     std::vector<unsigned> InstIdxs;
 622     std::vector<unsigned> NumInstOpsHandled;
 623     FindUniqueOperandCommands(UniqueOperandCommands, InstIdxs,
 624                               NumInstOpsHandled);
 625
 626     // If we ran out of operands to print, we're done.
 627     if (UniqueOperandCommands.empty()) break;
 628
 629     // Compute the number of bits we need to represent these cases, this is
 630     // ceil(log2(numentries)).
 631     unsigned NumBits = Log2_32_Ceil(UniqueOperandCommands.size());
 632
 633     // If we don't have enough bits for this operand, don't include it.
 634     if (NumBits > BitsLeft) {
 635       DOUT << "Not enough bits to densely encode " << NumBits
 636            << " more bits\n";
 637       break;
 638     }
 639
 640     // Otherwise, we can include this in the initial lookup table.  Add it in.
 641     BitsLeft -= NumBits;
 642     for (unsigned i = 0, e = InstIdxs.size(); i != e; ++i)
 643       if (InstIdxs[i] != ~0U)
 644         OpcodeInfo[i] |= InstIdxs[i] << (BitsLeft+AsmStrBits);
 645
 646     // Remove the info about this operand.
 647     for (unsigned i = 0, e = NumberedInstructions.size(); i != e; ++i) {
 648       if (AsmWriterInst *Inst = getAsmWriterInstByID(i))
 649         if (!Inst->Operands.empty()) {
 650           unsigned NumOps = NumInstOpsHandled[InstIdxs[i]];
 651           assert(NumOps <= Inst->Operands.size() &&
 652                  "Can't remove this many ops!");
 653           Inst->Operands.erase(Inst->Operands.begin(),
 654                                Inst->Operands.begin()+NumOps);
 655         }
 656     }
 657
 658     // Remember the handlers for this set of operands.
 659     TableDrivenOperandPrinters.push_back(UniqueOperandCommands);
 660   }
 661
 662
 663
 664   O<<"  static const unsigned OpInfo[] = {\n";
 665   for (unsigned i = 0, e = NumberedInstructions.size(); i != e; ++i) {
 666     O << "    " << OpcodeInfo[i] << "U,\t// "
 667       << NumberedInstructions[i]->TheDef->getName() << "\n";
 668   }
 669   // Add a dummy entry so the array init doesn't end with a comma.
 670   O << "    0U\n";
 671   O << "  };\n\n";
 672
 673   // Emit the string itself.
 674   O << "  const char *AsmStrs = \n    \"";
 675   unsigned CharsPrinted = 0;
 676   EscapeString(AggregateString);
 677   for (unsigned i = 0, e = AggregateString.size(); i != e; ++i) {
 678     if (CharsPrinted > 70) {
 679       O << "\"\n    \"";
 680       CharsPrinted = 0;
 681     }
 682     O << AggregateString[i];
 683     ++CharsPrinted;
 684
 685     // Print escape sequences all together.
 686     if (AggregateString[i] == '\\') {
 687       assert(i+1 < AggregateString.size() && "Incomplete escape sequence!");
 688       if (isdigit(AggregateString[i+1])) {
 689         assert(isdigit(AggregateString[i+2]) && isdigit(AggregateString[i+3]) &&
 690                "Expected 3 digit octal escape!");
 691         O << AggregateString[++i];
 692         O << AggregateString[++i];
 693         O << AggregateString[++i];
 694         CharsPrinted += 3;
 695       } else {
 696         O << AggregateString[++i];
 697         ++CharsPrinted;
 698       }
 699     }
 700   }
 701   O << "\";\n\n";
 702
 703   O << "  processDebugLoc(MI->getDebugLoc());\n\n";
 704
 705   O << "\n#ifndef NO_ASM_WRITER_BOILERPLATE\n";
 706
 707   O << "  if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {\n"
 708     << "    O << \"\\t\";\n"
 709     << "    printInlineAsm(MI);\n"
 710     << "    return true;\n"
 711     << "  } else if (MI->isLabel()) {\n"
 712     << "    printLabel(MI);\n"
 713     << "    return true;\n"
 714     << "  } else if (MI->getOpcode() == TargetInstrInfo::DECLARE) {\n"
 715     << "    printDeclare(MI);\n"
 716     << "    return true;\n"
 717     << "  } else if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {\n"
 718     << "    printImplicitDef(MI);\n"
 719     << "    return true;\n"
 720     << "  }\n\n";
 721
 722   O << "\n#endif\n";
 723
 724   O << "  O << \"\\t\";\n\n";
 725
 726   O << "  // Emit the opcode for the instruction.\n"
 727     << "  unsigned Bits = OpInfo[MI->getOpcode()];\n"
 728     << "  if (Bits == 0) return false;\n"
 729     << "  O << AsmStrs+(Bits & " << (1 << AsmStrBits)-1 << ");\n\n";
 730
 731   // This variable may be unused, suppress build warnings.
 732   O << "  unsigned OperandColumn = 1;\n";
 733   O << "  (void) OperandColumn;\n\n";
 734
 735   // Output the table driven operand information.
 736   BitsLeft = 32-AsmStrBits;
 737   for (unsigned i = 0, e = TableDrivenOperandPrinters.size(); i != e; ++i) {
 738     std::vector<std::string> &Commands = TableDrivenOperandPrinters[i];
 739
 740     // Compute the number of bits we need to represent these cases, this is
 741     // ceil(log2(numentries)).
 742     unsigned NumBits = Log2_32_Ceil(Commands.size());
 743     assert(NumBits <= BitsLeft && "consistency error");
 744
 745     // Emit code to extract this field from Bits.
 746     BitsLeft -= NumBits;
 747
 748     O << "\n  // Fragment " << i << " encoded into " << NumBits
 749       << " bits for " << Commands.size() << " unique commands.\n";
 750
 751     if (Commands.size() == 2) {
 752       // Emit two possibilitys with if/else.
 753       O << "  if ((Bits >> " << (BitsLeft+AsmStrBits) << ") & "
 754         << ((1 << NumBits)-1) << ") {\n"
 755         << Commands[1]
 756         << "  } else {\n"
 757         << Commands[0]
 758         << "  }\n\n";
 759     } else {
 760       O << "  switch ((Bits >> " << (BitsLeft+AsmStrBits) << ") & "
 761         << ((1 << NumBits)-1) << ") {\n"
 762         << "  default:   // unreachable.\n";
 763
 764       // Print out all the cases.
 765       for (unsigned i = 0, e = Commands.size(); i != e; ++i) {
 766         O << "  case " << i << ":\n";
 767         O << Commands[i];
 768         O << "    break;\n";
 769       }
 770       O << "  }\n\n";
 771     }
 772   }
 773
 774   // Okay, delete instructions with no operand info left.
 775   for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
 776     // Entire instruction has been emitted?
 777     AsmWriterInst &Inst = Instructions[i];
 778     if (Inst.Operands.empty()) {
 779       Instructions.erase(Instructions.begin()+i);
 780       --i; --e;
 781     }
 782   }
 783
 784
 785   // Because this is a vector, we want to emit from the end.  Reverse all of the
 786   // elements in the vector.
 787   std::reverse(Instructions.begin(), Instructions.end());
 788
 789   if (!Instructions.empty()) {
 790     // Find the opcode # of inline asm.
 791     O << "  switch (MI->getOpcode()) {\n";
 792     while (!Instructions.empty())
 793       EmitInstructions(Instructions, O);
 794
 795     O << "  }\n";
 796     O << "  return true;\n";
 797   }
 798
 799   O << "  return true;\n";
 800   O << "}\n";
 801 }