1 //===- CodeEmitterGen.cpp - Code Emitter Generator ------------------------===//
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 // CodeEmitterGen uses the descriptions of instructions and their fields to
11 // construct an automated code emitter: a function that, given a MachineInstr,
12 // returns the (currently, 32-bit unsigned) value of the instruction.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "CodeGenTarget.h"
17 #include "SubtargetFeatureInfo.h"
18 #include "Types.h"
19 #include "llvm/ADT/StringExtras.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/TableGen/Record.h"
22 #include "llvm/TableGen/TableGenBackend.h"
23 #include <map>
24 #include <string>
25 #include <vector>
26 using namespace llvm;
27 
28 namespace {
29 
30 class CodeEmitterGen {
31   RecordKeeper &Records;
32 public:
33   CodeEmitterGen(RecordKeeper &R) : Records(R) {}
34 
35   void run(raw_ostream &o);
36 private:
37   int getVariableBit(const std::string &VarName, BitsInit *BI, int bit);
38   std::string getInstructionCase(Record *R, CodeGenTarget &Target);
39   void AddCodeToMergeInOperand(Record *R, BitsInit *BI,
40                                const std::string &VarName,
41                                unsigned &NumberedOp,
42                                std::set<unsigned> &NamedOpIndices,
43                                std::string &Case, CodeGenTarget &Target);
44 
45 };
46 
47 // If the VarBitInit at position 'bit' matches the specified variable then
48 // return the variable bit position.  Otherwise return -1.
49 int CodeEmitterGen::getVariableBit(const std::string &VarName,
50                                    BitsInit *BI, int bit) {
51   if (VarBitInit *VBI = dyn_cast<VarBitInit>(BI->getBit(bit))) {
52     if (VarInit *VI = dyn_cast<VarInit>(VBI->getBitVar()))
53       if (VI->getName() == VarName)
54         return VBI->getBitNum();
55   } else if (VarInit *VI = dyn_cast<VarInit>(BI->getBit(bit))) {
56     if (VI->getName() == VarName)
57       return 0;
58   }
59 
60   return -1;
61 }
62 
63 void CodeEmitterGen::
64 AddCodeToMergeInOperand(Record *R, BitsInit *BI, const std::string &VarName,
65                         unsigned &NumberedOp,
66                         std::set<unsigned> &NamedOpIndices,
67                         std::string &Case, CodeGenTarget &Target) {
68   CodeGenInstruction &CGI = Target.getInstruction(R);
69 
70   // Determine if VarName actually contributes to the Inst encoding.
71   int bit = BI->getNumBits()-1;
72 
73   // Scan for a bit that this contributed to.
74   for (; bit >= 0; ) {
75     if (getVariableBit(VarName, BI, bit) != -1)
76       break;
77 
78     --bit;
79   }
80 
81   // If we found no bits, ignore this value, otherwise emit the call to get the
82   // operand encoding.
83   if (bit < 0) return;
84 
85   // If the operand matches by name, reference according to that
86   // operand number. Non-matching operands are assumed to be in
87   // order.
88   unsigned OpIdx;
89   if (CGI.Operands.hasOperandNamed(VarName, OpIdx)) {
90     // Get the machine operand number for the indicated operand.
91     OpIdx = CGI.Operands[OpIdx].MIOperandNo;
92     assert(!CGI.Operands.isFlatOperandNotEmitted(OpIdx) &&
93            "Explicitly used operand also marked as not emitted!");
94   } else {
95     unsigned NumberOps = CGI.Operands.size();
96     /// If this operand is not supposed to be emitted by the
97     /// generated emitter, skip it.
98     while (NumberedOp < NumberOps &&
99            (CGI.Operands.isFlatOperandNotEmitted(NumberedOp) ||
100               (!NamedOpIndices.empty() && NamedOpIndices.count(
101                 CGI.Operands.getSubOperandNumber(NumberedOp).first)))) {
102       ++NumberedOp;
103 
104       if (NumberedOp >= CGI.Operands.back().MIOperandNo +
105                         CGI.Operands.back().MINumOperands) {
106         errs() << "Too few operands in record " << R->getName() <<
107                   " (no match for variable " << VarName << "):\n";
108         errs() << *R;
109         errs() << '\n';
110 
111         return;
112       }
113     }
114 
115     OpIdx = NumberedOp++;
116   }
117 
118   std::pair<unsigned, unsigned> SO = CGI.Operands.getSubOperandNumber(OpIdx);
119   std::string &EncoderMethodName = CGI.Operands[SO.first].EncoderMethodName;
120 
121   // If the source operand has a custom encoder, use it. This will
122   // get the encoding for all of the suboperands.
123   if (!EncoderMethodName.empty()) {
124     // A custom encoder has all of the information for the
125     // sub-operands, if there are more than one, so only
126     // query the encoder once per source operand.
127     if (SO.second == 0) {
128       Case += "      // op: " + VarName + "\n" +
129               "      op = " + EncoderMethodName + "(MI, " + utostr(OpIdx);
130       Case += ", Fixups, STI";
131       Case += ");\n";
132     }
133   } else {
134     Case += "      // op: " + VarName + "\n" +
135       "      op = getMachineOpValue(MI, MI.getOperand(" + utostr(OpIdx) + ")";
136     Case += ", Fixups, STI";
137     Case += ");\n";
138   }
139 
140   for (; bit >= 0; ) {
141     int varBit = getVariableBit(VarName, BI, bit);
142 
143     // If this bit isn't from a variable, skip it.
144     if (varBit == -1) {
145       --bit;
146       continue;
147     }
148 
149     // Figure out the consecutive range of bits covered by this operand, in
150     // order to generate better encoding code.
151     int beginInstBit = bit;
152     int beginVarBit = varBit;
153     int N = 1;
154     for (--bit; bit >= 0;) {
155       varBit = getVariableBit(VarName, BI, bit);
156       if (varBit == -1 || varBit != (beginVarBit - N)) break;
157       ++N;
158       --bit;
159     }
160 
161     uint64_t opMask = ~(uint64_t)0 >> (64-N);
162     int opShift = beginVarBit - N + 1;
163     opMask <<= opShift;
164     opShift = beginInstBit - beginVarBit;
165 
166     if (opShift > 0) {
167       Case += "      Value |= (op & UINT64_C(" + utostr(opMask) + ")) << " +
168               itostr(opShift) + ";\n";
169     } else if (opShift < 0) {
170       Case += "      Value |= (op & UINT64_C(" + utostr(opMask) + ")) >> " +
171               itostr(-opShift) + ";\n";
172     } else {
173       Case += "      Value |= op & UINT64_C(" + utostr(opMask) + ");\n";
174     }
175   }
176 }
177 
178 
179 std::string CodeEmitterGen::getInstructionCase(Record *R,
180                                                CodeGenTarget &Target) {
181   std::string Case;
182 
183   BitsInit *BI = R->getValueAsBitsInit("Inst");
184   const std::vector<RecordVal> &Vals = R->getValues();
185   unsigned NumberedOp = 0;
186 
187   std::set<unsigned> NamedOpIndices;
188   // Collect the set of operand indices that might correspond to named
189   // operand, and skip these when assigning operands based on position.
190   if (Target.getInstructionSet()->
191        getValueAsBit("noNamedPositionallyEncodedOperands")) {
192     CodeGenInstruction &CGI = Target.getInstruction(R);
193     for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
194       unsigned OpIdx;
195       if (!CGI.Operands.hasOperandNamed(Vals[i].getName(), OpIdx))
196         continue;
197 
198       NamedOpIndices.insert(OpIdx);
199     }
200   }
201 
202   // Loop over all of the fields in the instruction, determining which are the
203   // operands to the instruction.
204   for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
205     // Ignore fixed fields in the record, we're looking for values like:
206     //    bits<5> RST = { ?, ?, ?, ?, ? };
207     if (Vals[i].getPrefix() || Vals[i].getValue()->isComplete())
208       continue;
209 
210     AddCodeToMergeInOperand(R, BI, Vals[i].getName(), NumberedOp,
211                             NamedOpIndices, Case, Target);
212   }
213 
214   std::string PostEmitter = R->getValueAsString("PostEncoderMethod");
215   if (!PostEmitter.empty()) {
216     Case += "      Value = " + PostEmitter + "(MI, Value";
217     Case += ", STI";
218     Case += ");\n";
219   }
220 
221   return Case;
222 }
223 
224 void CodeEmitterGen::run(raw_ostream &o) {
225   CodeGenTarget Target(Records);
226   std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
227 
228   // For little-endian instruction bit encodings, reverse the bit order
229   Target.reverseBitsForLittleEndianEncoding();
230 
231   ArrayRef<const CodeGenInstruction*> NumberedInstructions =
232     Target.getInstructionsByEnumValue();
233 
234   // Emit function declaration
235   o << "uint64_t " << Target.getName();
236   o << "MCCodeEmitter::getBinaryCodeForInstr(const MCInst &MI,\n"
237     << "    SmallVectorImpl<MCFixup> &Fixups,\n"
238     << "    const MCSubtargetInfo &STI) const {\n";
239 
240   // Emit instruction base values
241   o << "  static const uint64_t InstBits[] = {\n";
242   for (const CodeGenInstruction *CGI : NumberedInstructions) {
243     Record *R = CGI->TheDef;
244 
245     if (R->getValueAsString("Namespace") == "TargetOpcode" ||
246         R->getValueAsBit("isPseudo")) {
247       o << "    UINT64_C(0),\n";
248       continue;
249     }
250 
251     BitsInit *BI = R->getValueAsBitsInit("Inst");
252 
253     // Start by filling in fixed values.
254     uint64_t Value = 0;
255     for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i) {
256       if (BitInit *B = dyn_cast<BitInit>(BI->getBit(e-i-1)))
257         Value |= (uint64_t)B->getValue() << (e-i-1);
258     }
259     o << "    UINT64_C(" << Value << ")," << '\t' << "// " << R->getName() << "\n";
260   }
261   o << "    UINT64_C(0)\n  };\n";
262 
263   // Map to accumulate all the cases.
264   std::map<std::string, std::vector<std::string> > CaseMap;
265 
266   // Construct all cases statement for each opcode
267   for (std::vector<Record*>::iterator IC = Insts.begin(), EC = Insts.end();
268         IC != EC; ++IC) {
269     Record *R = *IC;
270     if (R->getValueAsString("Namespace") == "TargetOpcode" ||
271         R->getValueAsBit("isPseudo"))
272       continue;
273     const std::string &InstName = R->getValueAsString("Namespace") + "::"
274       + R->getName();
275     std::string Case = getInstructionCase(R, Target);
276 
277     CaseMap[Case].push_back(InstName);
278   }
279 
280   // Emit initial function code
281   o << "  const unsigned opcode = MI.getOpcode();\n"
282     << "  uint64_t Value = InstBits[opcode];\n"
283     << "  uint64_t op = 0;\n"
284     << "  (void)op;  // suppress warning\n"
285     << "  switch (opcode) {\n";
286 
287   // Emit each case statement
288   std::map<std::string, std::vector<std::string> >::iterator IE, EE;
289   for (IE = CaseMap.begin(), EE = CaseMap.end(); IE != EE; ++IE) {
290     const std::string &Case = IE->first;
291     std::vector<std::string> &InstList = IE->second;
292 
293     for (int i = 0, N = InstList.size(); i < N; i++) {
294       if (i) o << "\n";
295       o << "    case " << InstList[i]  << ":";
296     }
297     o << " {\n";
298     o << Case;
299     o << "      break;\n"
300       << "    }\n";
301   }
302 
303   // Default case: unhandled opcode
304   o << "  default:\n"
305     << "    std::string msg;\n"
306     << "    raw_string_ostream Msg(msg);\n"
307     << "    Msg << \"Not supported instr: \" << MI;\n"
308     << "    report_fatal_error(Msg.str());\n"
309     << "  }\n"
310     << "  return Value;\n"
311     << "}\n\n";
312 
313   const auto &All = SubtargetFeatureInfo::getAll(Records);
314   std::map<Record *, SubtargetFeatureInfo, LessRecordByID> SubtargetFeatures;
315   SubtargetFeatures.insert(All.begin(), All.end());
316 
317   o << "#ifdef ENABLE_INSTR_PREDICATE_VERIFIER\n"
318     << "#undef ENABLE_INSTR_PREDICATE_VERIFIER\n"
319     << "#include <sstream>\n\n";
320 
321   // Emit the subtarget feature enumeration.
322   SubtargetFeatureInfo::emitSubtargetFeatureFlagEnumeration(SubtargetFeatures,
323                                                             o);
324 
325   // Emit the name table for error messages.
326   o << "#ifndef NDEBUG\n";
327   SubtargetFeatureInfo::emitNameTable(SubtargetFeatures, o);
328   o << "#endif // NDEBUG\n";
329 
330   // Emit the available features compute function.
331   SubtargetFeatureInfo::emitComputeAvailableFeatures(
332       Target.getName(), "MCCodeEmitter", "computeAvailableFeatures",
333       SubtargetFeatures, o);
334 
335   // Emit the predicate verifier.
336   o << "void " << Target.getName()
337     << "MCCodeEmitter::verifyInstructionPredicates(\n"
338     << "    const MCInst &Inst, uint64_t AvailableFeatures) const {\n"
339     << "#ifndef NDEBUG\n"
340     << "  static uint64_t RequiredFeatures[] = {\n";
341   unsigned InstIdx = 0;
342   for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
343     o << "    ";
344     for (Record *Predicate : Inst->TheDef->getValueAsListOfDefs("Predicates")) {
345       const auto &I = SubtargetFeatures.find(Predicate);
346       if (I != SubtargetFeatures.end())
347         o << I->second.getEnumName() << " | ";
348     }
349     o << "0, // " << Inst->TheDef->getName() << " = " << InstIdx << "\n";
350     InstIdx++;
351   }
352   o << "  };\n\n";
353   o << "  assert(Inst.getOpcode() < " << InstIdx << ");\n";
354   o << "  uint64_t MissingFeatures =\n"
355     << "      (AvailableFeatures & RequiredFeatures[Inst.getOpcode()]) ^\n"
356     << "      RequiredFeatures[Inst.getOpcode()];\n"
357     << "  if (MissingFeatures) {\n"
358     << "    std::ostringstream Msg;\n"
359     << "    Msg << \"Attempting to emit \" << "
360        "MCII.getName(Inst.getOpcode()).str()\n"
361     << "        << \" instruction but the \";\n"
362     << "    for (unsigned i = 0; i < 8 * sizeof(MissingFeatures); ++i)\n"
363     << "      if (MissingFeatures & (1ULL << i))\n"
364     << "        Msg << SubtargetFeatureNames[i] << \" \";\n"
365     << "    Msg << \"predicate(s) are not met\";\n"
366     << "    report_fatal_error(Msg.str());\n"
367     << "  }\n"
368     << "#else\n"
369     << "// Silence unused variable warning on targets that don't use MCII for "
370        "other purposes (e.g. BPF).\n"
371     << "(void)MCII;\n"
372     << "#endif // NDEBUG\n";
373   o << "}\n";
374   o << "#endif\n";
375 }
376 
377 } // End anonymous namespace
378 
379 namespace llvm {
380 
381 void EmitCodeEmitter(RecordKeeper &RK, raw_ostream &OS) {
382   emitSourceFileHeader("Machine Code Emitter", OS);
383   CodeEmitterGen(RK).run(OS);
384 }
385 
386 } // End llvm namespace
387