1
//===-- SelectionDAGBuilder.h - Selection-DAG building --------------------===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This implements routines for translating from LLVM IR into SelectionDAG IR.
12
//===----------------------------------------------------------------------===//
14
#ifndef SELECTIONDAGBUILDER_H
15
#define SELECTIONDAGBUILDER_H
17
#include "llvm/Constants.h"
18
#include "llvm/CodeGen/SelectionDAG.h"
19
#include "llvm/ADT/APInt.h"
20
#include "llvm/ADT/DenseMap.h"
21
#include "llvm/CodeGen/SelectionDAGNodes.h"
22
#include "llvm/CodeGen/ValueTypes.h"
23
#include "llvm/Support/CallSite.h"
24
#include "llvm/Support/ErrorHandling.h"
37
class ExtractElementInst;
38
class ExtractValueInst;
45
class FunctionLoweringInfo;
46
class GetElementPtrInst;
52
class InsertElementInst;
53
class InsertValueInst;
56
class MachineBasicBlock;
58
class MachineRegisterInfo;
63
class SDISelAsmOperandInfo;
67
class ShuffleVectorInst;
75
class UnreachableInst;
80
//===----------------------------------------------------------------------===//
81
/// SelectionDAGBuilder - This is the common target-independent lowering
82
/// implementation that is parameterized by a TargetLowering object.
84
class SelectionDAGBuilder {
85
/// CurDebugLoc - current file + line number. Changes as we build the DAG.
88
DenseMap<const Value*, SDValue> NodeMap;
90
/// UnusedArgNodeMap - Maps argument value for unused arguments. This is used
91
/// to preserve debug information for incoming arguments.
92
DenseMap<const Value*, SDValue> UnusedArgNodeMap;
94
/// DanglingDebugInfo - Helper type for DanglingDebugInfoMap.
95
class DanglingDebugInfo {
96
const DbgValueInst* DI;
100
DanglingDebugInfo() : DI(0), dl(DebugLoc()), SDNodeOrder(0) { }
101
DanglingDebugInfo(const DbgValueInst *di, DebugLoc DL, unsigned SDNO) :
102
DI(di), dl(DL), SDNodeOrder(SDNO) { }
103
const DbgValueInst* getDI() { return DI; }
104
DebugLoc getdl() { return dl; }
105
unsigned getSDNodeOrder() { return SDNodeOrder; }
108
/// DanglingDebugInfoMap - Keeps track of dbg_values for which we have not
109
/// yet seen the referent. We defer handling these until we do see it.
110
DenseMap<const Value*, DanglingDebugInfo> DanglingDebugInfoMap;
113
/// PendingLoads - Loads are not emitted to the program immediately. We bunch
114
/// them up and then emit token factor nodes when possible. This allows us to
115
/// get simple disambiguation between loads without worrying about alias
117
SmallVector<SDValue, 8> PendingLoads;
120
/// PendingExports - CopyToReg nodes that copy values to virtual registers
121
/// for export to other blocks need to be emitted before any terminator
122
/// instruction, but they have no other ordering requirements. We bunch them
123
/// up and the emit a single tokenfactor for them just before terminator
125
SmallVector<SDValue, 8> PendingExports;
127
/// SDNodeOrder - A unique monotonically increasing number used to order the
128
/// SDNodes we create.
129
unsigned SDNodeOrder;
131
/// Case - A struct to record the Value for a switch case, and the
132
/// case's target basic block.
136
MachineBasicBlock* BB;
138
Case() : Low(0), High(0), BB(0) { }
139
Case(Constant* low, Constant* high, MachineBasicBlock* bb) :
140
Low(low), High(high), BB(bb) { }
142
const APInt &rHigh = cast<ConstantInt>(High)->getValue();
143
const APInt &rLow = cast<ConstantInt>(Low)->getValue();
144
return (rHigh - rLow + 1ULL);
150
MachineBasicBlock* BB;
153
CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits):
154
Mask(mask), BB(bb), Bits(bits) { }
157
typedef std::vector<Case> CaseVector;
158
typedef std::vector<CaseBits> CaseBitsVector;
159
typedef CaseVector::iterator CaseItr;
160
typedef std::pair<CaseItr, CaseItr> CaseRange;
162
/// CaseRec - A struct with ctor used in lowering switches to a binary tree
163
/// of conditional branches.
165
CaseRec(MachineBasicBlock *bb, const Constant *lt, const Constant *ge,
167
CaseBB(bb), LT(lt), GE(ge), Range(r) {}
169
/// CaseBB - The MBB in which to emit the compare and branch
170
MachineBasicBlock *CaseBB;
171
/// LT, GE - If nonzero, we know the current case value must be less-than or
172
/// greater-than-or-equal-to these Constants.
175
/// Range - A pair of iterators representing the range of case values to be
176
/// processed at this point in the binary search tree.
180
typedef std::vector<CaseRec> CaseRecVector;
182
/// The comparison function for sorting the switch case values in the vector.
183
/// WARNING: Case ranges should be disjoint!
185
bool operator()(const Case &C1, const Case &C2) {
186
assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High));
187
const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
188
const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
189
return CI1->getValue().slt(CI2->getValue());
194
bool operator()(const CaseBits &C1, const CaseBits &C2) {
195
return C1.Bits > C2.Bits;
199
size_t Clusterify(CaseVector &Cases, const SwitchInst &SI);
201
/// CaseBlock - This structure is used to communicate between
202
/// SelectionDAGBuilder and SDISel for the code generation of additional basic
203
/// blocks needed by multi-case switch statements.
205
CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs,
206
const Value *cmpmiddle,
207
MachineBasicBlock *truebb, MachineBasicBlock *falsebb,
208
MachineBasicBlock *me)
209
: CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs),
210
TrueBB(truebb), FalseBB(falsebb), ThisBB(me) {}
211
// CC - the condition code to use for the case block's setcc node
213
// CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit.
214
// Emit by default LHS op RHS. MHS is used for range comparisons:
215
// If MHS is not null: (LHS <= MHS) and (MHS <= RHS).
216
const Value *CmpLHS, *CmpMHS, *CmpRHS;
217
// TrueBB/FalseBB - the block to branch to if the setcc is true/false.
218
MachineBasicBlock *TrueBB, *FalseBB;
219
// ThisBB - the block into which to emit the code for the setcc and branches
220
MachineBasicBlock *ThisBB;
223
JumpTable(unsigned R, unsigned J, MachineBasicBlock *M,
224
MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {}
226
/// Reg - the virtual register containing the index of the jump table entry
229
/// JTI - the JumpTableIndex for this jump table in the function.
231
/// MBB - the MBB into which to emit the code for the indirect jump.
232
MachineBasicBlock *MBB;
233
/// Default - the MBB of the default bb, which is a successor of the range
234
/// check MBB. This is when updating PHI nodes in successors.
235
MachineBasicBlock *Default;
237
struct JumpTableHeader {
238
JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H,
240
First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {}
244
MachineBasicBlock *HeaderBB;
247
typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock;
250
BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr):
251
Mask(M), ThisBB(T), TargetBB(Tr) { }
253
MachineBasicBlock *ThisBB;
254
MachineBasicBlock *TargetBB;
257
typedef SmallVector<BitTestCase, 3> BitTestInfo;
259
struct BitTestBlock {
260
BitTestBlock(APInt F, APInt R, const Value* SV,
262
MachineBasicBlock* P, MachineBasicBlock* D,
263
const BitTestInfo& C):
264
First(F), Range(R), SValue(SV), Reg(Rg), Emitted(E),
265
Parent(P), Default(D), Cases(C) { }
271
MachineBasicBlock *Parent;
272
MachineBasicBlock *Default;
277
// TLI - This is information that describes the available target features we
278
// need for lowering. This indicates when operations are unavailable,
279
// implemented with a libcall, etc.
280
const TargetMachine &TM;
281
const TargetLowering &TLI;
283
const TargetData *TD;
286
/// SwitchCases - Vector of CaseBlock structures used to communicate
287
/// SwitchInst code generation information.
288
std::vector<CaseBlock> SwitchCases;
289
/// JTCases - Vector of JumpTable structures used to communicate
290
/// SwitchInst code generation information.
291
std::vector<JumpTableBlock> JTCases;
292
/// BitTestCases - Vector of BitTestBlock structures used to communicate
293
/// SwitchInst code generation information.
294
std::vector<BitTestBlock> BitTestCases;
296
// Emit PHI-node-operand constants only once even if used by multiple
298
DenseMap<const Constant *, unsigned> ConstantsOut;
300
/// FuncInfo - Information about the function as a whole.
302
FunctionLoweringInfo &FuncInfo;
304
/// OptLevel - What optimization level we're generating code for.
306
CodeGenOpt::Level OptLevel;
308
/// GFI - Garbage collection metadata for the function.
311
/// HasTailCall - This is set to true if a call in the current
312
/// block has been translated as a tail call. In this case,
313
/// no subsequent DAG nodes should be created.
317
LLVMContext *Context;
319
SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo,
320
CodeGenOpt::Level ol)
321
: SDNodeOrder(0), TM(dag.getTarget()), TLI(dag.getTargetLoweringInfo()),
322
DAG(dag), FuncInfo(funcinfo), OptLevel(ol),
323
HasTailCall(false), Context(dag.getContext()) {
326
void init(GCFunctionInfo *gfi, AliasAnalysis &aa);
328
/// clear - Clear out the current SelectionDAG and the associated
329
/// state and prepare this SelectionDAGBuilder object to be used
330
/// for a new block. This doesn't clear out information about
331
/// additional blocks that are needed to complete switch lowering
332
/// or PHI node updating; that information is cleared out as it is
336
/// getRoot - Return the current virtual root of the Selection DAG,
337
/// flushing any PendingLoad items. This must be done before emitting
338
/// a store or any other node that may need to be ordered after any
339
/// prior load instructions.
343
/// getControlRoot - Similar to getRoot, but instead of flushing all the
344
/// PendingLoad items, flush all the PendingExports items. It is necessary
345
/// to do this before emitting a terminator instruction.
347
SDValue getControlRoot();
349
DebugLoc getCurDebugLoc() const { return CurDebugLoc; }
351
unsigned getSDNodeOrder() const { return SDNodeOrder; }
353
void CopyValueToVirtualRegister(const Value *V, unsigned Reg);
355
/// AssignOrderingToNode - Assign an ordering to the node. The order is gotten
356
/// from how the code appeared in the source. The ordering is used by the
357
/// scheduler to effectively turn off scheduling.
358
void AssignOrderingToNode(const SDNode *Node);
360
void visit(const Instruction &I);
362
void visit(unsigned Opcode, const User &I);
364
// resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V,
365
// generate the debug data structures now that we've seen its definition.
366
void resolveDanglingDebugInfo(const Value *V, SDValue Val);
367
SDValue getValue(const Value *V);
368
SDValue getNonRegisterValue(const Value *V);
369
SDValue getValueImpl(const Value *V);
371
void setValue(const Value *V, SDValue NewN) {
372
SDValue &N = NodeMap[V];
373
assert(N.getNode() == 0 && "Already set a value for this node!");
377
void setUnusedArgValue(const Value *V, SDValue NewN) {
378
SDValue &N = UnusedArgNodeMap[V];
379
assert(N.getNode() == 0 && "Already set a value for this node!");
383
void GetRegistersForValue(SDISelAsmOperandInfo &OpInfo,
384
std::set<unsigned> &OutputRegs,
385
std::set<unsigned> &InputRegs);
387
void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB,
388
MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
389
MachineBasicBlock *SwitchBB, unsigned Opc);
390
void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB,
391
MachineBasicBlock *FBB,
392
MachineBasicBlock *CurBB,
393
MachineBasicBlock *SwitchBB);
394
bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases);
395
bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB);
396
void CopyToExportRegsIfNeeded(const Value *V);
397
void ExportFromCurrentBlock(const Value *V);
398
void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall,
399
MachineBasicBlock *LandingPad = NULL);
402
// Terminator instructions.
403
void visitRet(const ReturnInst &I);
404
void visitBr(const BranchInst &I);
405
void visitSwitch(const SwitchInst &I);
406
void visitIndirectBr(const IndirectBrInst &I);
407
void visitUnreachable(const UnreachableInst &I) { /* noop */ }
409
// Helpers for visitSwitch
410
bool handleSmallSwitchRange(CaseRec& CR,
411
CaseRecVector& WorkList,
413
MachineBasicBlock* Default,
414
MachineBasicBlock *SwitchBB);
415
bool handleJTSwitchCase(CaseRec& CR,
416
CaseRecVector& WorkList,
418
MachineBasicBlock* Default,
419
MachineBasicBlock *SwitchBB);
420
bool handleBTSplitSwitchCase(CaseRec& CR,
421
CaseRecVector& WorkList,
423
MachineBasicBlock* Default,
424
MachineBasicBlock *SwitchBB);
425
bool handleBitTestsSwitchCase(CaseRec& CR,
426
CaseRecVector& WorkList,
428
MachineBasicBlock* Default,
429
MachineBasicBlock *SwitchBB);
431
void visitSwitchCase(CaseBlock &CB,
432
MachineBasicBlock *SwitchBB);
433
void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB);
434
void visitBitTestCase(MachineBasicBlock* NextMBB,
437
MachineBasicBlock *SwitchBB);
438
void visitJumpTable(JumpTable &JT);
439
void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH,
440
MachineBasicBlock *SwitchBB);
443
// These all get lowered before this pass.
444
void visitInvoke(const InvokeInst &I);
445
void visitUnwind(const UnwindInst &I);
447
void visitBinary(const User &I, unsigned OpCode);
448
void visitShift(const User &I, unsigned Opcode);
449
void visitAdd(const User &I) { visitBinary(I, ISD::ADD); }
450
void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); }
451
void visitSub(const User &I) { visitBinary(I, ISD::SUB); }
452
void visitFSub(const User &I);
453
void visitMul(const User &I) { visitBinary(I, ISD::MUL); }
454
void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); }
455
void visitURem(const User &I) { visitBinary(I, ISD::UREM); }
456
void visitSRem(const User &I) { visitBinary(I, ISD::SREM); }
457
void visitFRem(const User &I) { visitBinary(I, ISD::FREM); }
458
void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); }
459
void visitSDiv(const User &I) { visitBinary(I, ISD::SDIV); }
460
void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); }
461
void visitAnd (const User &I) { visitBinary(I, ISD::AND); }
462
void visitOr (const User &I) { visitBinary(I, ISD::OR); }
463
void visitXor (const User &I) { visitBinary(I, ISD::XOR); }
464
void visitShl (const User &I) { visitShift(I, ISD::SHL); }
465
void visitLShr(const User &I) { visitShift(I, ISD::SRL); }
466
void visitAShr(const User &I) { visitShift(I, ISD::SRA); }
467
void visitICmp(const User &I);
468
void visitFCmp(const User &I);
469
// Visit the conversion instructions
470
void visitTrunc(const User &I);
471
void visitZExt(const User &I);
472
void visitSExt(const User &I);
473
void visitFPTrunc(const User &I);
474
void visitFPExt(const User &I);
475
void visitFPToUI(const User &I);
476
void visitFPToSI(const User &I);
477
void visitUIToFP(const User &I);
478
void visitSIToFP(const User &I);
479
void visitPtrToInt(const User &I);
480
void visitIntToPtr(const User &I);
481
void visitBitCast(const User &I);
483
void visitExtractElement(const User &I);
484
void visitInsertElement(const User &I);
485
void visitShuffleVector(const User &I);
487
void visitExtractValue(const ExtractValueInst &I);
488
void visitInsertValue(const InsertValueInst &I);
490
void visitGetElementPtr(const User &I);
491
void visitSelect(const User &I);
493
void visitAlloca(const AllocaInst &I);
494
void visitLoad(const LoadInst &I);
495
void visitStore(const StoreInst &I);
496
void visitPHI(const PHINode &I);
497
void visitCall(const CallInst &I);
498
bool visitMemCmpCall(const CallInst &I);
500
void visitInlineAsm(ImmutableCallSite CS);
501
const char *visitIntrinsicCall(const CallInst &I, unsigned Intrinsic);
502
void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic);
504
void visitPow(const CallInst &I);
505
void visitExp2(const CallInst &I);
506
void visitExp(const CallInst &I);
507
void visitLog(const CallInst &I);
508
void visitLog2(const CallInst &I);
509
void visitLog10(const CallInst &I);
511
void visitVAStart(const CallInst &I);
512
void visitVAArg(const VAArgInst &I);
513
void visitVAEnd(const CallInst &I);
514
void visitVACopy(const CallInst &I);
516
void visitUserOp1(const Instruction &I) {
517
llvm_unreachable("UserOp1 should not exist at instruction selection time!");
519
void visitUserOp2(const Instruction &I) {
520
llvm_unreachable("UserOp2 should not exist at instruction selection time!");
523
const char *implVisitBinaryAtomic(const CallInst& I, ISD::NodeType Op);
524
const char *implVisitAluOverflow(const CallInst &I, ISD::NodeType Op);
526
void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB);
528
/// EmitFuncArgumentDbgValue - If V is an function argument then create
529
/// corresponding DBG_VALUE machine instruction for it now. At the end of
530
/// instruction selection, they will be inserted to the entry BB.
531
bool EmitFuncArgumentDbgValue(const Value *V, MDNode *Variable,
532
int64_t Offset, const SDValue &N);
535
} // end namespace llvm
added
removed
libclamav/c++/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
