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