← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to utils/TableGen/FastISelEmitter.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
utils/TableGen/FastISelEmitter.cpp
 
1
//===- FastISelEmitter.cpp - Generate an instruction selector -------------===//
 
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 emits code for use by the "fast" instruction
 
11
// selection algorithm. See the comments at the top of
 
12
// lib/CodeGen/SelectionDAG/FastISel.cpp for background.
 
13
//
 
14
// This file scans through the target's tablegen instruction-info files
 
15
// and extracts instructions with obvious-looking patterns, and it emits
 
16
// code to look up these instructions by type and operator.
 
17
//
 
18
//===----------------------------------------------------------------------===//
 
19
 
 
20
#include "CodeGenDAGPatterns.h"
 
21
#include "llvm/ADT/SmallString.h"
 
22
#include "llvm/ADT/StringSwitch.h"
 
23
#include "llvm/Support/Debug.h"
 
24
#include "llvm/Support/ErrorHandling.h"
 
25
#include "llvm/TableGen/Error.h"
 
26
#include "llvm/TableGen/Record.h"
 
27
#include "llvm/TableGen/TableGenBackend.h"
 
28
using namespace llvm;
 
29
 
 
30
 
 
31
/// InstructionMemo - This class holds additional information about an
 
32
/// instruction needed to emit code for it.
 
33
///
 
34
namespace {
 
35
struct InstructionMemo {
 
36
  std::string Name;
 
37
  const CodeGenRegisterClass *RC;
 
38
  std::string SubRegNo;
 
39
  std::vector<std::string>* PhysRegs;
 
40
  std::string PredicateCheck;
 
41
};
 
42
} // End anonymous namespace
 
43
 
 
44
/// ImmPredicateSet - This uniques predicates (represented as a string) and
 
45
/// gives them unique (small) integer ID's that start at 0.
 
46
namespace {
 
47
class ImmPredicateSet {
 
48
  DenseMap<TreePattern *, unsigned> ImmIDs;
 
49
  std::vector<TreePredicateFn> PredsByName;
 
50
public:
 
51
 
 
52
  unsigned getIDFor(TreePredicateFn Pred) {
 
53
    unsigned &Entry = ImmIDs[Pred.getOrigPatFragRecord()];
 
54
    if (Entry == 0) {
 
55
      PredsByName.push_back(Pred);
 
56
      Entry = PredsByName.size();
 
57
    }
 
58
    return Entry-1;
 
59
  }
 
60
 
 
61
  const TreePredicateFn &getPredicate(unsigned i) {
 
62
    assert(i < PredsByName.size());
 
63
    return PredsByName[i];
 
64
  }
 
65
 
 
66
  typedef std::vector<TreePredicateFn>::const_iterator iterator;
 
67
  iterator begin() const { return PredsByName.begin(); }
 
68
  iterator end() const { return PredsByName.end(); }
 
69
 
 
70
};
 
71
} // End anonymous namespace
 
72
 
 
73
/// OperandsSignature - This class holds a description of a list of operand
 
74
/// types. It has utility methods for emitting text based on the operands.
 
75
///
 
76
namespace {
 
77
struct OperandsSignature {
 
78
  class OpKind {
 
79
    enum { OK_Reg, OK_FP, OK_Imm, OK_Invalid = -1 };
 
80
    char Repr;
 
81
  public:
 
82
 
 
83
    OpKind() : Repr(OK_Invalid) {}
 
84
 
 
85
    bool operator<(OpKind RHS) const { return Repr < RHS.Repr; }
 
86
    bool operator==(OpKind RHS) const { return Repr == RHS.Repr; }
 
87
 
 
88
    static OpKind getReg() { OpKind K; K.Repr = OK_Reg; return K; }
 
89
    static OpKind getFP()  { OpKind K; K.Repr = OK_FP; return K; }
 
90
    static OpKind getImm(unsigned V) {
 
91
      assert((unsigned)OK_Imm+V < 128 &&
 
92
             "Too many integer predicates for the 'Repr' char");
 
93
      OpKind K; K.Repr = OK_Imm+V; return K;
 
94
    }
 
95
 
 
96
    bool isReg() const { return Repr == OK_Reg; }
 
97
    bool isFP() const  { return Repr == OK_FP; }
 
98
    bool isImm() const { return Repr >= OK_Imm; }
 
99
 
 
100
    unsigned getImmCode() const { assert(isImm()); return Repr-OK_Imm; }
 
101
 
 
102
    void printManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates,
 
103
                             bool StripImmCodes) const {
 
104
      if (isReg())
 
105
        OS << 'r';
 
106
      else if (isFP())
 
107
        OS << 'f';
 
108
      else {
 
109
        OS << 'i';
 
110
        if (!StripImmCodes)
 
111
          if (unsigned Code = getImmCode())
 
112
            OS << "_" << ImmPredicates.getPredicate(Code-1).getFnName();
 
113
      }
 
114
    }
 
115
  };
 
116
 
 
117
 
 
118
  SmallVector<OpKind, 3> Operands;
 
119
 
 
120
  bool operator<(const OperandsSignature &O) const {
 
121
    return Operands < O.Operands;
 
122
  }
 
123
  bool operator==(const OperandsSignature &O) const {
 
124
    return Operands == O.Operands;
 
125
  }
 
126
 
 
127
  bool empty() const { return Operands.empty(); }
 
128
 
 
129
  bool hasAnyImmediateCodes() const {
 
130
    for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 
131
      if (Operands[i].isImm() && Operands[i].getImmCode() != 0)
 
132
        return true;
 
133
    return false;
 
134
  }
 
135
 
 
136
  /// getWithoutImmCodes - Return a copy of this with any immediate codes forced
 
137
  /// to zero.
 
138
  OperandsSignature getWithoutImmCodes() const {
 
139
    OperandsSignature Result;
 
140
    for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 
141
      if (!Operands[i].isImm())
 
142
        Result.Operands.push_back(Operands[i]);
 
143
      else
 
144
        Result.Operands.push_back(OpKind::getImm(0));
 
145
    return Result;
 
146
  }
 
147
 
 
148
  void emitImmediatePredicate(raw_ostream &OS, ImmPredicateSet &ImmPredicates) {
 
149
    bool EmittedAnything = false;
 
150
    for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 
151
      if (!Operands[i].isImm()) continue;
 
152
 
 
153
      unsigned Code = Operands[i].getImmCode();
 
154
      if (Code == 0) continue;
 
155
 
 
156
      if (EmittedAnything)
 
157
        OS << " &&\n        ";
 
158
 
 
159
      TreePredicateFn PredFn = ImmPredicates.getPredicate(Code-1);
 
160
 
 
161
      // Emit the type check.
 
162
      OS << "VT == "
 
163
         << getEnumName(PredFn.getOrigPatFragRecord()->getTree(0)->getType(0))
 
164
         << " && ";
 
165
 
 
166
 
 
167
      OS << PredFn.getFnName() << "(imm" << i <<')';
 
168
      EmittedAnything = true;
 
169
    }
 
170
  }
 
171
 
 
172
  /// initialize - Examine the given pattern and initialize the contents
 
173
  /// of the Operands array accordingly. Return true if all the operands
 
174
  /// are supported, false otherwise.
 
175
  ///
 
176
  bool initialize(TreePatternNode *InstPatNode, const CodeGenTarget &Target,
 
177
                  MVT::SimpleValueType VT,
 
178
                  ImmPredicateSet &ImmediatePredicates,
 
179
                  const CodeGenRegisterClass *OrigDstRC) {
 
180
    if (InstPatNode->isLeaf())
 
181
      return false;
 
182
 
 
183
    if (InstPatNode->getOperator()->getName() == "imm") {
 
184
      Operands.push_back(OpKind::getImm(0));
 
185
      return true;
 
186
    }
 
187
 
 
188
    if (InstPatNode->getOperator()->getName() == "fpimm") {
 
189
      Operands.push_back(OpKind::getFP());
 
190
      return true;
 
191
    }
 
192
 
 
193
    const CodeGenRegisterClass *DstRC = nullptr;
 
194
 
 
195
    for (unsigned i = 0, e = InstPatNode->getNumChildren(); i != e; ++i) {
 
196
      TreePatternNode *Op = InstPatNode->getChild(i);
 
197
 
 
198
      // Handle imm operands specially.
 
199
      if (!Op->isLeaf() && Op->getOperator()->getName() == "imm") {
 
200
        unsigned PredNo = 0;
 
201
        if (!Op->getPredicateFns().empty()) {
 
202
          TreePredicateFn PredFn = Op->getPredicateFns()[0];
 
203
          // If there is more than one predicate weighing in on this operand
 
204
          // then we don't handle it.  This doesn't typically happen for
 
205
          // immediates anyway.
 
206
          if (Op->getPredicateFns().size() > 1 ||
 
207
              !PredFn.isImmediatePattern())
 
208
            return false;
 
209
          // Ignore any instruction with 'FastIselShouldIgnore', these are
 
210
          // not needed and just bloat the fast instruction selector.  For
 
211
          // example, X86 doesn't need to generate code to match ADD16ri8 since
 
212
          // ADD16ri will do just fine.
 
213
          Record *Rec = PredFn.getOrigPatFragRecord()->getRecord();
 
214
          if (Rec->getValueAsBit("FastIselShouldIgnore"))
 
215
            return false;
 
216
 
 
217
          PredNo = ImmediatePredicates.getIDFor(PredFn)+1;
 
218
        }
 
219
 
 
220
        // Handle unmatched immediate sizes here.
 
221
        //if (Op->getType(0) != VT)
 
222
        //  return false;
 
223
 
 
224
        Operands.push_back(OpKind::getImm(PredNo));
 
225
        continue;
 
226
      }
 
227
 
 
228
 
 
229
      // For now, filter out any operand with a predicate.
 
230
      // For now, filter out any operand with multiple values.
 
231
      if (!Op->getPredicateFns().empty() || Op->getNumTypes() != 1)
 
232
        return false;
 
233
 
 
234
      if (!Op->isLeaf()) {
 
235
         if (Op->getOperator()->getName() == "fpimm") {
 
236
          Operands.push_back(OpKind::getFP());
 
237
          continue;
 
238
        }
 
239
        // For now, ignore other non-leaf nodes.
 
240
        return false;
 
241
      }
 
242
 
 
243
      assert(Op->hasTypeSet(0) && "Type infererence not done?");
 
244
 
 
245
      // For now, all the operands must have the same type (if they aren't
 
246
      // immediates).  Note that this causes us to reject variable sized shifts
 
247
      // on X86.
 
248
      if (Op->getType(0) != VT)
 
249
        return false;
 
250
 
 
251
      DefInit *OpDI = dyn_cast<DefInit>(Op->getLeafValue());
 
252
      if (!OpDI)
 
253
        return false;
 
254
      Record *OpLeafRec = OpDI->getDef();
 
255
 
 
256
      // For now, the only other thing we accept is register operands.
 
257
      const CodeGenRegisterClass *RC = nullptr;
 
258
      if (OpLeafRec->isSubClassOf("RegisterOperand"))
 
259
        OpLeafRec = OpLeafRec->getValueAsDef("RegClass");
 
260
      if (OpLeafRec->isSubClassOf("RegisterClass"))
 
261
        RC = &Target.getRegisterClass(OpLeafRec);
 
262
      else if (OpLeafRec->isSubClassOf("Register"))
 
263
        RC = Target.getRegBank().getRegClassForRegister(OpLeafRec);
 
264
      else if (OpLeafRec->isSubClassOf("ValueType")) {
 
265
        RC = OrigDstRC;
 
266
      } else
 
267
        return false;
 
268
 
 
269
      // For now, this needs to be a register class of some sort.
 
270
      if (!RC)
 
271
        return false;
 
272
 
 
273
      // For now, all the operands must have the same register class or be
 
274
      // a strict subclass of the destination.
 
275
      if (DstRC) {
 
276
        if (DstRC != RC && !DstRC->hasSubClass(RC))
 
277
          return false;
 
278
      } else
 
279
        DstRC = RC;
 
280
      Operands.push_back(OpKind::getReg());
 
281
    }
 
282
    return true;
 
283
  }
 
284
 
 
285
  void PrintParameters(raw_ostream &OS) const {
 
286
    for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 
287
      if (Operands[i].isReg()) {
 
288
        OS << "unsigned Op" << i << ", bool Op" << i << "IsKill";
 
289
      } else if (Operands[i].isImm()) {
 
290
        OS << "uint64_t imm" << i;
 
291
      } else if (Operands[i].isFP()) {
 
292
        OS << "const ConstantFP *f" << i;
 
293
      } else {
 
294
        llvm_unreachable("Unknown operand kind!");
 
295
      }
 
296
      if (i + 1 != e)
 
297
        OS << ", ";
 
298
    }
 
299
  }
 
300
 
 
301
  void PrintArguments(raw_ostream &OS,
 
302
                      const std::vector<std::string> &PR) const {
 
303
    assert(PR.size() == Operands.size());
 
304
    bool PrintedArg = false;
 
305
    for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 
306
      if (PR[i] != "")
 
307
        // Implicit physical register operand.
 
308
        continue;
 
309
 
 
310
      if (PrintedArg)
 
311
        OS << ", ";
 
312
      if (Operands[i].isReg()) {
 
313
        OS << "Op" << i << ", Op" << i << "IsKill";
 
314
        PrintedArg = true;
 
315
      } else if (Operands[i].isImm()) {
 
316
        OS << "imm" << i;
 
317
        PrintedArg = true;
 
318
      } else if (Operands[i].isFP()) {
 
319
        OS << "f" << i;
 
320
        PrintedArg = true;
 
321
      } else {
 
322
        llvm_unreachable("Unknown operand kind!");
 
323
      }
 
324
    }
 
325
  }
 
326
 
 
327
  void PrintArguments(raw_ostream &OS) const {
 
328
    for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 
329
      if (Operands[i].isReg()) {
 
330
        OS << "Op" << i << ", Op" << i << "IsKill";
 
331
      } else if (Operands[i].isImm()) {
 
332
        OS << "imm" << i;
 
333
      } else if (Operands[i].isFP()) {
 
334
        OS << "f" << i;
 
335
      } else {
 
336
        llvm_unreachable("Unknown operand kind!");
 
337
      }
 
338
      if (i + 1 != e)
 
339
        OS << ", ";
 
340
    }
 
341
  }
 
342
 
 
343
 
 
344
  void PrintManglingSuffix(raw_ostream &OS, const std::vector<std::string> &PR,
 
345
                           ImmPredicateSet &ImmPredicates,
 
346
                           bool StripImmCodes = false) const {
 
347
    for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
 
348
      if (PR[i] != "")
 
349
        // Implicit physical register operand. e.g. Instruction::Mul expect to
 
350
        // select to a binary op. On x86, mul may take a single operand with
 
351
        // the other operand being implicit. We must emit something that looks
 
352
        // like a binary instruction except for the very inner fastEmitInst_*
 
353
        // call.
 
354
        continue;
 
355
      Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes);
 
356
    }
 
357
  }
 
358
 
 
359
  void PrintManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates,
 
360
                           bool StripImmCodes = false) const {
 
361
    for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 
362
      Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes);
 
363
  }
 
364
};
 
365
} // End anonymous namespace
 
366
 
 
367
namespace {
 
368
class FastISelMap {
 
369
  // A multimap is needed instead of a "plain" map because the key is 
 
370
  // the instruction's complexity (an int) and they are not unique.
 
371
  typedef std::multimap<int, InstructionMemo> PredMap;
 
372
  typedef std::map<MVT::SimpleValueType, PredMap> RetPredMap;
 
373
  typedef std::map<MVT::SimpleValueType, RetPredMap> TypeRetPredMap;
 
374
  typedef std::map<std::string, TypeRetPredMap> OpcodeTypeRetPredMap;
 
375
  typedef std::map<OperandsSignature, OpcodeTypeRetPredMap>
 
376
            OperandsOpcodeTypeRetPredMap;
 
377
 
 
378
  OperandsOpcodeTypeRetPredMap SimplePatterns;
 
379
 
 
380
  // This is used to check that there are no duplicate predicates            
 
381
  typedef std::multimap<std::string, bool> PredCheckMap;
 
382
  typedef std::map<MVT::SimpleValueType, PredCheckMap> RetPredCheckMap;
 
383
  typedef std::map<MVT::SimpleValueType, RetPredCheckMap> TypeRetPredCheckMap;
 
384
  typedef std::map<std::string, TypeRetPredCheckMap> OpcodeTypeRetPredCheckMap;
 
385
  typedef std::map<OperandsSignature, OpcodeTypeRetPredCheckMap>
 
386
            OperandsOpcodeTypeRetPredCheckMap;
 
387
 
 
388
  OperandsOpcodeTypeRetPredCheckMap SimplePatternsCheck;
 
389
 
 
390
  std::map<OperandsSignature, std::vector<OperandsSignature> >
 
391
    SignaturesWithConstantForms;
 
392
 
 
393
  std::string InstNS;
 
394
  ImmPredicateSet ImmediatePredicates;
 
395
public:
 
396
  explicit FastISelMap(std::string InstNS);
 
397
 
 
398
  void collectPatterns(CodeGenDAGPatterns &CGP);
 
399
  void printImmediatePredicates(raw_ostream &OS);
 
400
  void printFunctionDefinitions(raw_ostream &OS);
 
401
private:  
 
402
  void emitInstructionCode(raw_ostream &OS, 
 
403
                           const OperandsSignature &Operands,
 
404
                           const PredMap &PM, 
 
405
                           const std::string &RetVTName);
 
406
};
 
407
} // End anonymous namespace
 
408
 
 
409
static std::string getOpcodeName(Record *Op, CodeGenDAGPatterns &CGP) {
 
410
  return CGP.getSDNodeInfo(Op).getEnumName();
 
411
}
 
412
 
 
413
static std::string getLegalCName(std::string OpName) {
 
414
  std::string::size_type pos = OpName.find("::");
 
415
  if (pos != std::string::npos)
 
416
    OpName.replace(pos, 2, "_");
 
417
  return OpName;
 
418
}
 
419
 
 
420
FastISelMap::FastISelMap(std::string instns)
 
421
  : InstNS(instns) {
 
422
}
 
423
 
 
424
static std::string PhyRegForNode(TreePatternNode *Op,
 
425
                                 const CodeGenTarget &Target) {
 
426
  std::string PhysReg;
 
427
 
 
428
  if (!Op->isLeaf())
 
429
    return PhysReg;
 
430
 
 
431
  Record *OpLeafRec = cast<DefInit>(Op->getLeafValue())->getDef();
 
432
  if (!OpLeafRec->isSubClassOf("Register"))
 
433
    return PhysReg;
 
434
 
 
435
  PhysReg += cast<StringInit>(OpLeafRec->getValue("Namespace")->getValue())
 
436
               ->getValue();
 
437
  PhysReg += "::";
 
438
  PhysReg += Target.getRegBank().getReg(OpLeafRec)->getName();
 
439
  return PhysReg;
 
440
}
 
441
 
 
442
void FastISelMap::collectPatterns(CodeGenDAGPatterns &CGP) {
 
443
  const CodeGenTarget &Target = CGP.getTargetInfo();
 
444
 
 
445
  // Determine the target's namespace name.
 
446
  InstNS = Target.getInstNamespace() + "::";
 
447
  assert(InstNS.size() > 2 && "Can't determine target-specific namespace!");
 
448
 
 
449
  // Scan through all the patterns and record the simple ones.
 
450
  for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
 
451
       E = CGP.ptm_end(); I != E; ++I) {
 
452
    const PatternToMatch &Pattern = *I;
 
453
 
 
454
    // For now, just look at Instructions, so that we don't have to worry
 
455
    // about emitting multiple instructions for a pattern.
 
456
    TreePatternNode *Dst = Pattern.getDstPattern();
 
457
    if (Dst->isLeaf()) continue;
 
458
    Record *Op = Dst->getOperator();
 
459
    if (!Op->isSubClassOf("Instruction"))
 
460
      continue;
 
461
    CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op);
 
462
    if (II.Operands.empty())
 
463
      continue;
 
464
 
 
465
    // For now, ignore multi-instruction patterns.
 
466
    bool MultiInsts = false;
 
467
    for (unsigned i = 0, e = Dst->getNumChildren(); i != e; ++i) {
 
468
      TreePatternNode *ChildOp = Dst->getChild(i);
 
469
      if (ChildOp->isLeaf())
 
470
        continue;
 
471
      if (ChildOp->getOperator()->isSubClassOf("Instruction")) {
 
472
        MultiInsts = true;
 
473
        break;
 
474
      }
 
475
    }
 
476
    if (MultiInsts)
 
477
      continue;
 
478
 
 
479
    // For now, ignore instructions where the first operand is not an
 
480
    // output register.
 
481
    const CodeGenRegisterClass *DstRC = nullptr;
 
482
    std::string SubRegNo;
 
483
    if (Op->getName() != "EXTRACT_SUBREG") {
 
484
      Record *Op0Rec = II.Operands[0].Rec;
 
485
      if (Op0Rec->isSubClassOf("RegisterOperand"))
 
486
        Op0Rec = Op0Rec->getValueAsDef("RegClass");
 
487
      if (!Op0Rec->isSubClassOf("RegisterClass"))
 
488
        continue;
 
489
      DstRC = &Target.getRegisterClass(Op0Rec);
 
490
      if (!DstRC)
 
491
        continue;
 
492
    } else {
 
493
      // If this isn't a leaf, then continue since the register classes are
 
494
      // a bit too complicated for now.
 
495
      if (!Dst->getChild(1)->isLeaf()) continue;
 
496
 
 
497
      DefInit *SR = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
 
498
      if (SR)
 
499
        SubRegNo = getQualifiedName(SR->getDef());
 
500
      else
 
501
        SubRegNo = Dst->getChild(1)->getLeafValue()->getAsString();
 
502
    }
 
503
 
 
504
    // Inspect the pattern.
 
505
    TreePatternNode *InstPatNode = Pattern.getSrcPattern();
 
506
    if (!InstPatNode) continue;
 
507
    if (InstPatNode->isLeaf()) continue;
 
508
 
 
509
    // Ignore multiple result nodes for now.
 
510
    if (InstPatNode->getNumTypes() > 1) continue;
 
511
 
 
512
    Record *InstPatOp = InstPatNode->getOperator();
 
513
    std::string OpcodeName = getOpcodeName(InstPatOp, CGP);
 
514
    MVT::SimpleValueType RetVT = MVT::isVoid;
 
515
    if (InstPatNode->getNumTypes()) RetVT = InstPatNode->getType(0);
 
516
    MVT::SimpleValueType VT = RetVT;
 
517
    if (InstPatNode->getNumChildren()) {
 
518
      assert(InstPatNode->getChild(0)->getNumTypes() == 1);
 
519
      VT = InstPatNode->getChild(0)->getType(0);
 
520
    }
 
521
 
 
522
    // For now, filter out any instructions with predicates.
 
523
    if (!InstPatNode->getPredicateFns().empty())
 
524
      continue;
 
525
 
 
526
    // Check all the operands.
 
527
    OperandsSignature Operands;
 
528
    if (!Operands.initialize(InstPatNode, Target, VT, ImmediatePredicates,
 
529
                             DstRC))
 
530
      continue;
 
531
 
 
532
    std::vector<std::string>* PhysRegInputs = new std::vector<std::string>();
 
533
    if (InstPatNode->getOperator()->getName() == "imm" ||
 
534
        InstPatNode->getOperator()->getName() == "fpimm")
 
535
      PhysRegInputs->push_back("");
 
536
    else {
 
537
      // Compute the PhysRegs used by the given pattern, and check that
 
538
      // the mapping from the src to dst patterns is simple.
 
539
      bool FoundNonSimplePattern = false;
 
540
      unsigned DstIndex = 0;
 
541
      for (unsigned i = 0, e = InstPatNode->getNumChildren(); i != e; ++i) {
 
542
        std::string PhysReg = PhyRegForNode(InstPatNode->getChild(i), Target);
 
543
        if (PhysReg.empty()) {
 
544
          if (DstIndex >= Dst->getNumChildren() ||
 
545
              Dst->getChild(DstIndex)->getName() !=
 
546
              InstPatNode->getChild(i)->getName()) {
 
547
            FoundNonSimplePattern = true;
 
548
            break;
 
549
          }
 
550
          ++DstIndex;
 
551
        }
 
552
 
 
553
        PhysRegInputs->push_back(PhysReg);
 
554
      }
 
555
 
 
556
      if (Op->getName() != "EXTRACT_SUBREG" && DstIndex < Dst->getNumChildren())
 
557
        FoundNonSimplePattern = true;
 
558
 
 
559
      if (FoundNonSimplePattern)
 
560
        continue;
 
561
    }
 
562
 
 
563
    // Check if the operands match one of the patterns handled by FastISel.
 
564
    std::string ManglingSuffix;
 
565
    raw_string_ostream SuffixOS(ManglingSuffix);
 
566
    Operands.PrintManglingSuffix(SuffixOS, ImmediatePredicates, true);
 
567
    SuffixOS.flush();
 
568
    if (!StringSwitch<bool>(ManglingSuffix)
 
569
        .Cases("", "r", "rr", "ri", "rf", true)
 
570
        .Cases("rri", "i", "f", true)
 
571
        .Default(false))
 
572
      continue;
 
573
 
 
574
    // Get the predicate that guards this pattern.
 
575
    std::string PredicateCheck = Pattern.getPredicateCheck();
 
576
 
 
577
    // Ok, we found a pattern that we can handle. Remember it.
 
578
    InstructionMemo Memo = {
 
579
      Pattern.getDstPattern()->getOperator()->getName(),
 
580
      DstRC,
 
581
      SubRegNo,
 
582
      PhysRegInputs,
 
583
      PredicateCheck
 
584
    };
 
585
    
 
586
    int complexity = Pattern.getPatternComplexity(CGP);
 
587
 
 
588
    if (SimplePatternsCheck[Operands][OpcodeName][VT]
 
589
         [RetVT].count(PredicateCheck)) {
 
590
      PrintFatalError(Pattern.getSrcRecord()->getLoc(),
 
591
                    "Duplicate predicate in FastISel table!");
 
592
    }
 
593
    SimplePatternsCheck[Operands][OpcodeName][VT][RetVT].insert(
 
594
            std::make_pair(PredicateCheck, true));
 
595
 
 
596
       // Note: Instructions with the same complexity will appear in the order
 
597
          // that they are encountered.
 
598
    SimplePatterns[Operands][OpcodeName][VT][RetVT].insert(
 
599
      std::make_pair(complexity, Memo));
 
600
 
 
601
    // If any of the operands were immediates with predicates on them, strip
 
602
    // them down to a signature that doesn't have predicates so that we can
 
603
    // associate them with the stripped predicate version.
 
604
    if (Operands.hasAnyImmediateCodes()) {
 
605
      SignaturesWithConstantForms[Operands.getWithoutImmCodes()]
 
606
        .push_back(Operands);
 
607
    }
 
608
  }
 
609
}
 
610
 
 
611
void FastISelMap::printImmediatePredicates(raw_ostream &OS) {
 
612
  if (ImmediatePredicates.begin() == ImmediatePredicates.end())
 
613
    return;
 
614
 
 
615
  OS << "\n// FastEmit Immediate Predicate functions.\n";
 
616
  for (ImmPredicateSet::iterator I = ImmediatePredicates.begin(),
 
617
       E = ImmediatePredicates.end(); I != E; ++I) {
 
618
    OS << "static bool " << I->getFnName() << "(int64_t Imm) {\n";
 
619
    OS << I->getImmediatePredicateCode() << "\n}\n";
 
620
  }
 
621
 
 
622
  OS << "\n\n";
 
623
}
 
624
 
 
625
void FastISelMap::emitInstructionCode(raw_ostream &OS, 
 
626
                                      const OperandsSignature &Operands,
 
627
                                      const PredMap &PM, 
 
628
                                      const std::string &RetVTName) {
 
629
  // Emit code for each possible instruction. There may be
 
630
  // multiple if there are subtarget concerns.  A reverse iterator
 
631
  // is used to produce the ones with highest complexity first.
 
632
 
 
633
  bool OneHadNoPredicate = false;
 
634
  for (PredMap::const_reverse_iterator PI = PM.rbegin(), PE = PM.rend();
 
635
       PI != PE; ++PI) {
 
636
    const InstructionMemo &Memo = PI->second;
 
637
    std::string PredicateCheck = Memo.PredicateCheck;
 
638
 
 
639
    if (PredicateCheck.empty()) {
 
640
      assert(!OneHadNoPredicate &&
 
641
             "Multiple instructions match and more than one had "
 
642
             "no predicate!");
 
643
      OneHadNoPredicate = true;
 
644
    } else {
 
645
      if (OneHadNoPredicate) {
 
646
        // FIXME: This should be a PrintError once the x86 target
 
647
        // fixes PR21575.
 
648
        PrintWarning("Multiple instructions match and one with no "
 
649
                     "predicate came before one with a predicate!  "
 
650
                     "name:" + Memo.Name + "  predicate: " + 
 
651
                     PredicateCheck);
 
652
      }
 
653
      OS << "  if (" + PredicateCheck + ") {\n";
 
654
      OS << "  ";
 
655
    }
 
656
 
 
657
    for (unsigned i = 0; i < Memo.PhysRegs->size(); ++i) {
 
658
      if ((*Memo.PhysRegs)[i] != "")
 
659
        OS << "  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, "
 
660
           << "TII.get(TargetOpcode::COPY), "
 
661
           << (*Memo.PhysRegs)[i] << ").addReg(Op" << i << ");\n";
 
662
    }
 
663
 
 
664
    OS << "  return fastEmitInst_";
 
665
    if (Memo.SubRegNo.empty()) {
 
666
      Operands.PrintManglingSuffix(OS, *Memo.PhysRegs,
 
667
     ImmediatePredicates, true);
 
668
      OS << "(" << InstNS << Memo.Name << ", ";
 
669
      OS << "&" << InstNS << Memo.RC->getName() << "RegClass";
 
670
      if (!Operands.empty())
 
671
        OS << ", ";
 
672
      Operands.PrintArguments(OS, *Memo.PhysRegs);
 
673
      OS << ");\n";
 
674
    } else {
 
675
      OS << "extractsubreg(" << RetVTName
 
676
         << ", Op0, Op0IsKill, " << Memo.SubRegNo << ");\n";
 
677
    }
 
678
 
 
679
    if (!PredicateCheck.empty()) {
 
680
      OS << "  }\n";
 
681
    }
 
682
  }
 
683
  // Return 0 if all of the possibilities had predicates but none
 
684
  // were satisfied.
 
685
  if (!OneHadNoPredicate)
 
686
    OS << "  return 0;\n";
 
687
  OS << "}\n";
 
688
  OS << "\n";
 
689
}
 
690
 
 
691
 
 
692
void FastISelMap::printFunctionDefinitions(raw_ostream &OS) {
 
693
  // Now emit code for all the patterns that we collected.
 
694
  for (OperandsOpcodeTypeRetPredMap::const_iterator OI = SimplePatterns.begin(),
 
695
       OE = SimplePatterns.end(); OI != OE; ++OI) {
 
696
    const OperandsSignature &Operands = OI->first;
 
697
    const OpcodeTypeRetPredMap &OTM = OI->second;
 
698
 
 
699
    for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end();
 
700
         I != E; ++I) {
 
701
      const std::string &Opcode = I->first;
 
702
      const TypeRetPredMap &TM = I->second;
 
703
 
 
704
      OS << "// FastEmit functions for " << Opcode << ".\n";
 
705
      OS << "\n";
 
706
 
 
707
      // Emit one function for each opcode,type pair.
 
708
      for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end();
 
709
           TI != TE; ++TI) {
 
710
        MVT::SimpleValueType VT = TI->first;
 
711
        const RetPredMap &RM = TI->second;
 
712
        if (RM.size() != 1) {
 
713
          for (RetPredMap::const_iterator RI = RM.begin(), RE = RM.end();
 
714
               RI != RE; ++RI) {
 
715
            MVT::SimpleValueType RetVT = RI->first;
 
716
            const PredMap &PM = RI->second;
 
717
 
 
718
            OS << "unsigned fastEmit_"
 
719
               << getLegalCName(Opcode)
 
720
               << "_" << getLegalCName(getName(VT))
 
721
               << "_" << getLegalCName(getName(RetVT)) << "_";
 
722
            Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 
723
            OS << "(";
 
724
            Operands.PrintParameters(OS);
 
725
            OS << ") {\n";
 
726
 
 
727
            emitInstructionCode(OS, Operands, PM, getName(RetVT));
 
728
          }
 
729
 
 
730
          // Emit one function for the type that demultiplexes on return type.
 
731
          OS << "unsigned fastEmit_"
 
732
             << getLegalCName(Opcode) << "_"
 
733
             << getLegalCName(getName(VT)) << "_";
 
734
          Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 
735
          OS << "(MVT RetVT";
 
736
          if (!Operands.empty())
 
737
            OS << ", ";
 
738
          Operands.PrintParameters(OS);
 
739
          OS << ") {\nswitch (RetVT.SimpleTy) {\n";
 
740
          for (RetPredMap::const_iterator RI = RM.begin(), RE = RM.end();
 
741
               RI != RE; ++RI) {
 
742
            MVT::SimpleValueType RetVT = RI->first;
 
743
            OS << "  case " << getName(RetVT) << ": return fastEmit_"
 
744
               << getLegalCName(Opcode) << "_" << getLegalCName(getName(VT))
 
745
               << "_" << getLegalCName(getName(RetVT)) << "_";
 
746
            Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 
747
            OS << "(";
 
748
            Operands.PrintArguments(OS);
 
749
            OS << ");\n";
 
750
          }
 
751
          OS << "  default: return 0;\n}\n}\n\n";
 
752
 
 
753
        } else {
 
754
          // Non-variadic return type.
 
755
          OS << "unsigned fastEmit_"
 
756
             << getLegalCName(Opcode) << "_"
 
757
             << getLegalCName(getName(VT)) << "_";
 
758
          Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 
759
          OS << "(MVT RetVT";
 
760
          if (!Operands.empty())
 
761
            OS << ", ";
 
762
          Operands.PrintParameters(OS);
 
763
          OS << ") {\n";
 
764
 
 
765
          OS << "  if (RetVT.SimpleTy != " << getName(RM.begin()->first)
 
766
             << ")\n    return 0;\n";
 
767
 
 
768
          const PredMap &PM = RM.begin()->second;
 
769
 
 
770
          emitInstructionCode(OS, Operands, PM, "RetVT");
 
771
        }
 
772
      }
 
773
 
 
774
      // Emit one function for the opcode that demultiplexes based on the type.
 
775
      OS << "unsigned fastEmit_"
 
776
         << getLegalCName(Opcode) << "_";
 
777
      Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 
778
      OS << "(MVT VT, MVT RetVT";
 
779
      if (!Operands.empty())
 
780
        OS << ", ";
 
781
      Operands.PrintParameters(OS);
 
782
      OS << ") {\n";
 
783
      OS << "  switch (VT.SimpleTy) {\n";
 
784
      for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end();
 
785
           TI != TE; ++TI) {
 
786
        MVT::SimpleValueType VT = TI->first;
 
787
        std::string TypeName = getName(VT);
 
788
        OS << "  case " << TypeName << ": return fastEmit_"
 
789
           << getLegalCName(Opcode) << "_" << getLegalCName(TypeName) << "_";
 
790
        Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 
791
        OS << "(RetVT";
 
792
        if (!Operands.empty())
 
793
          OS << ", ";
 
794
        Operands.PrintArguments(OS);
 
795
        OS << ");\n";
 
796
      }
 
797
      OS << "  default: return 0;\n";
 
798
      OS << "  }\n";
 
799
      OS << "}\n";
 
800
      OS << "\n";
 
801
    }
 
802
 
 
803
    OS << "// Top-level FastEmit function.\n";
 
804
    OS << "\n";
 
805
 
 
806
    // Emit one function for the operand signature that demultiplexes based
 
807
    // on opcode and type.
 
808
    OS << "unsigned fastEmit_";
 
809
    Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 
810
    OS << "(MVT VT, MVT RetVT, unsigned Opcode";
 
811
    if (!Operands.empty())
 
812
      OS << ", ";
 
813
    Operands.PrintParameters(OS);
 
814
    OS << ") ";
 
815
    if (!Operands.hasAnyImmediateCodes())
 
816
      OS << "override ";
 
817
    OS << "{\n";
 
818
 
 
819
    // If there are any forms of this signature available that operate on
 
820
    // constrained forms of the immediate (e.g., 32-bit sext immediate in a
 
821
    // 64-bit operand), check them first.
 
822
 
 
823
    std::map<OperandsSignature, std::vector<OperandsSignature> >::iterator MI
 
824
      = SignaturesWithConstantForms.find(Operands);
 
825
    if (MI != SignaturesWithConstantForms.end()) {
 
826
      // Unique any duplicates out of the list.
 
827
      std::sort(MI->second.begin(), MI->second.end());
 
828
      MI->second.erase(std::unique(MI->second.begin(), MI->second.end()),
 
829
                       MI->second.end());
 
830
 
 
831
      // Check each in order it was seen.  It would be nice to have a good
 
832
      // relative ordering between them, but we're not going for optimality
 
833
      // here.
 
834
      for (unsigned i = 0, e = MI->second.size(); i != e; ++i) {
 
835
        OS << "  if (";
 
836
        MI->second[i].emitImmediatePredicate(OS, ImmediatePredicates);
 
837
        OS << ")\n    if (unsigned Reg = fastEmit_";
 
838
        MI->second[i].PrintManglingSuffix(OS, ImmediatePredicates);
 
839
        OS << "(VT, RetVT, Opcode";
 
840
        if (!MI->second[i].empty())
 
841
          OS << ", ";
 
842
        MI->second[i].PrintArguments(OS);
 
843
        OS << "))\n      return Reg;\n\n";
 
844
      }
 
845
 
 
846
      // Done with this, remove it.
 
847
      SignaturesWithConstantForms.erase(MI);
 
848
    }
 
849
 
 
850
    OS << "  switch (Opcode) {\n";
 
851
    for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end();
 
852
         I != E; ++I) {
 
853
      const std::string &Opcode = I->first;
 
854
 
 
855
      OS << "  case " << Opcode << ": return fastEmit_"
 
856
         << getLegalCName(Opcode) << "_";
 
857
      Operands.PrintManglingSuffix(OS, ImmediatePredicates);
 
858
      OS << "(VT, RetVT";
 
859
      if (!Operands.empty())
 
860
        OS << ", ";
 
861
      Operands.PrintArguments(OS);
 
862
      OS << ");\n";
 
863
    }
 
864
    OS << "  default: return 0;\n";
 
865
    OS << "  }\n";
 
866
    OS << "}\n";
 
867
    OS << "\n";
 
868
  }
 
869
 
 
870
  // TODO: SignaturesWithConstantForms should be empty here.
 
871
}
 
872
 
 
873
namespace llvm {
 
874
 
 
875
void EmitFastISel(RecordKeeper &RK, raw_ostream &OS) {
 
876
  CodeGenDAGPatterns CGP(RK);
 
877
  const CodeGenTarget &Target = CGP.getTargetInfo();
 
878
  emitSourceFileHeader("\"Fast\" Instruction Selector for the " +
 
879
                       Target.getName() + " target", OS);
 
880
 
 
881
  // Determine the target's namespace name.
 
882
  std::string InstNS = Target.getInstNamespace() + "::";
 
883
  assert(InstNS.size() > 2 && "Can't determine target-specific namespace!");
 
884
 
 
885
  FastISelMap F(InstNS);
 
886
  F.collectPatterns(CGP);
 
887
  F.printImmediatePredicates(OS);
 
888
  F.printFunctionDefinitions(OS);
 
889
}
 
890
 
 
891
} // End llvm namespace