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