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