Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
Line
Count
Source (jump to first uncovered line)
1
//===- SelectionDAGBuilder.h - Selection-DAG building -----------*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This implements routines for translating from LLVM IR into SelectionDAG IR.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#ifndef LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
14
#define LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
15
16
#include "StatepointLowering.h"
17
#include "llvm/ADT/APInt.h"
18
#include "llvm/ADT/ArrayRef.h"
19
#include "llvm/ADT/DenseMap.h"
20
#include "llvm/ADT/MapVector.h"
21
#include "llvm/ADT/SmallVector.h"
22
#include "llvm/Analysis/AliasAnalysis.h"
23
#include "llvm/CodeGen/ISDOpcodes.h"
24
#include "llvm/CodeGen/SelectionDAG.h"
25
#include "llvm/CodeGen/SelectionDAGNodes.h"
26
#include "llvm/CodeGen/SwitchLoweringUtils.h"
27
#include "llvm/CodeGen/TargetLowering.h"
28
#include "llvm/CodeGen/ValueTypes.h"
29
#include "llvm/IR/CallSite.h"
30
#include "llvm/IR/DebugLoc.h"
31
#include "llvm/IR/Instruction.h"
32
#include "llvm/IR/Statepoint.h"
33
#include "llvm/Support/BranchProbability.h"
34
#include "llvm/Support/CodeGen.h"
35
#include "llvm/Support/ErrorHandling.h"
36
#include "llvm/Support/MachineValueType.h"
37
#include <algorithm>
38
#include <cassert>
39
#include <cstdint>
40
#include <utility>
41
#include <vector>
42
43
namespace llvm {
44
45
class AllocaInst;
46
class AtomicCmpXchgInst;
47
class AtomicRMWInst;
48
class BasicBlock;
49
class BranchInst;
50
class CallInst;
51
class CallBrInst;
52
class CatchPadInst;
53
class CatchReturnInst;
54
class CatchSwitchInst;
55
class CleanupPadInst;
56
class CleanupReturnInst;
57
class Constant;
58
class ConstantInt;
59
class ConstrainedFPIntrinsic;
60
class DbgValueInst;
61
class DataLayout;
62
class DIExpression;
63
class DILocalVariable;
64
class DILocation;
65
class FenceInst;
66
class FunctionLoweringInfo;
67
class GCFunctionInfo;
68
class GCRelocateInst;
69
class GCResultInst;
70
class IndirectBrInst;
71
class InvokeInst;
72
class LandingPadInst;
73
class LLVMContext;
74
class LoadInst;
75
class MachineBasicBlock;
76
class PHINode;
77
class ResumeInst;
78
class ReturnInst;
79
class SDDbgValue;
80
class StoreInst;
81
class SwiftErrorValueTracking;
82
class SwitchInst;
83
class TargetLibraryInfo;
84
class TargetMachine;
85
class Type;
86
class VAArgInst;
87
class UnreachableInst;
88
class Use;
89
class User;
90
class Value;
91
92
//===----------------------------------------------------------------------===//
93
/// SelectionDAGBuilder - This is the common target-independent lowering
94
/// implementation that is parameterized by a TargetLowering object.
95
///
96
class SelectionDAGBuilder {
97
  /// The current instruction being visited.
98
  const Instruction *CurInst = nullptr;
99
100
  DenseMap<const Value*, SDValue> NodeMap;
101
102
  /// Maps argument value for unused arguments. This is used
103
  /// to preserve debug information for incoming arguments.
104
  DenseMap<const Value*, SDValue> UnusedArgNodeMap;
105
106
  /// Helper type for DanglingDebugInfoMap.
107
  class DanglingDebugInfo {
108
    const DbgValueInst* DI = nullptr;
109
    DebugLoc dl;
110
    unsigned SDNodeOrder = 0;
111
112
  public:
113
    DanglingDebugInfo() = default;
114
    DanglingDebugInfo(const DbgValueInst *di, DebugLoc DL, unsigned SDNO)
115
32
        : DI(di), dl(std::move(DL)), SDNodeOrder(SDNO) {}
116
117
127
    const DbgValueInst* getDI() { return DI; }
118
32
    DebugLoc getdl() { return dl; }
119
32
    unsigned getSDNodeOrder() { return SDNodeOrder; }
120
  };
121
122
  /// Helper type for DanglingDebugInfoMap.
123
  typedef std::vector<DanglingDebugInfo> DanglingDebugInfoVector;
124
125
  /// Keeps track of dbg_values for which we have not yet seen the referent.
126
  /// We defer handling these until we do see it.
127
  MapVector<const Value*, DanglingDebugInfoVector> DanglingDebugInfoMap;
128
129
public:
130
  /// Loads are not emitted to the program immediately.  We bunch them up and
131
  /// then emit token factor nodes when possible.  This allows us to get simple
132
  /// disambiguation between loads without worrying about alias analysis.
133
  SmallVector<SDValue, 8> PendingLoads;
134
135
  /// State used while lowering a statepoint sequence (gc_statepoint,
136
  /// gc_relocate, and gc_result).  See StatepointLowering.hpp/cpp for details.
137
  StatepointLoweringState StatepointLowering;
138
139
private:
140
  /// CopyToReg nodes that copy values to virtual registers for export to other
141
  /// blocks need to be emitted before any terminator instruction, but they have
142
  /// no other ordering requirements. We bunch them up and the emit a single
143
  /// tokenfactor for them just before terminator instructions.
144
  SmallVector<SDValue, 8> PendingExports;
145
146
  /// A unique monotonically increasing number used to order the SDNodes we
147
  /// create.
148
  unsigned SDNodeOrder;
149
150
  /// Determine the rank by weight of CC in [First,Last]. If CC has more weight
151
  /// than each cluster in the range, its rank is 0.
152
  unsigned caseClusterRank(const SwitchCG::CaseCluster &CC,
153
                           SwitchCG::CaseClusterIt First,
154
                           SwitchCG::CaseClusterIt Last);
155
156
  /// Emit comparison and split W into two subtrees.
157
  void splitWorkItem(SwitchCG::SwitchWorkList &WorkList,
158
                     const SwitchCG::SwitchWorkListItem &W, Value *Cond,
159
                     MachineBasicBlock *SwitchMBB);
160
161
  /// Lower W.
162
  void lowerWorkItem(SwitchCG::SwitchWorkListItem W, Value *Cond,
163
                     MachineBasicBlock *SwitchMBB,
164
                     MachineBasicBlock *DefaultMBB);
165
166
  /// Peel the top probability case if it exceeds the threshold
167
  MachineBasicBlock *
168
  peelDominantCaseCluster(const SwitchInst &SI,
169
                          SwitchCG::CaseClusterVector &Clusters,
170
                          BranchProbability &PeeledCaseProb);
171
172
  /// A class which encapsulates all of the information needed to generate a
173
  /// stack protector check and signals to isel via its state being initialized
174
  /// that a stack protector needs to be generated.
175
  ///
176
  /// *NOTE* The following is a high level documentation of SelectionDAG Stack
177
  /// Protector Generation. The reason that it is placed here is for a lack of
178
  /// other good places to stick it.
179
  ///
180
  /// High Level Overview of SelectionDAG Stack Protector Generation:
181
  ///
182
  /// Previously, generation of stack protectors was done exclusively in the
183
  /// pre-SelectionDAG Codegen LLVM IR Pass "Stack Protector". This necessitated
184
  /// splitting basic blocks at the IR level to create the success/failure basic
185
  /// blocks in the tail of the basic block in question. As a result of this,
186
  /// calls that would have qualified for the sibling call optimization were no
187
  /// longer eligible for optimization since said calls were no longer right in
188
  /// the "tail position" (i.e. the immediate predecessor of a ReturnInst
189
  /// instruction).
190
  ///
191
  /// Then it was noticed that since the sibling call optimization causes the
192
  /// callee to reuse the caller's stack, if we could delay the generation of
193
  /// the stack protector check until later in CodeGen after the sibling call
194
  /// decision was made, we get both the tail call optimization and the stack
195
  /// protector check!
196
  ///
197
  /// A few goals in solving this problem were:
198
  ///
199
  ///   1. Preserve the architecture independence of stack protector generation.
200
  ///
201
  ///   2. Preserve the normal IR level stack protector check for platforms like
202
  ///      OpenBSD for which we support platform-specific stack protector
203
  ///      generation.
204
  ///
205
  /// The main problem that guided the present solution is that one can not
206
  /// solve this problem in an architecture independent manner at the IR level
207
  /// only. This is because:
208
  ///
209
  ///   1. The decision on whether or not to perform a sibling call on certain
210
  ///      platforms (for instance i386) requires lower level information
211
  ///      related to available registers that can not be known at the IR level.
212
  ///
213
  ///   2. Even if the previous point were not true, the decision on whether to
214
  ///      perform a tail call is done in LowerCallTo in SelectionDAG which
215
  ///      occurs after the Stack Protector Pass. As a result, one would need to
216
  ///      put the relevant callinst into the stack protector check success
217
  ///      basic block (where the return inst is placed) and then move it back
218
  ///      later at SelectionDAG/MI time before the stack protector check if the
219
  ///      tail call optimization failed. The MI level option was nixed
220
  ///      immediately since it would require platform-specific pattern
221
  ///      matching. The SelectionDAG level option was nixed because
222
  ///      SelectionDAG only processes one IR level basic block at a time
223
  ///      implying one could not create a DAG Combine to move the callinst.
224
  ///
225
  /// To get around this problem a few things were realized:
226
  ///
227
  ///   1. While one can not handle multiple IR level basic blocks at the
228
  ///      SelectionDAG Level, one can generate multiple machine basic blocks
229
  ///      for one IR level basic block. This is how we handle bit tests and
230
  ///      switches.
231
  ///
232
  ///   2. At the MI level, tail calls are represented via a special return
233
  ///      MIInst called "tcreturn". Thus if we know the basic block in which we
234
  ///      wish to insert the stack protector check, we get the correct behavior
235
  ///      by always inserting the stack protector check right before the return
236
  ///      statement. This is a "magical transformation" since no matter where
237
  ///      the stack protector check intrinsic is, we always insert the stack
238
  ///      protector check code at the end of the BB.
239
  ///
240
  /// Given the aforementioned constraints, the following solution was devised:
241
  ///
242
  ///   1. On platforms that do not support SelectionDAG stack protector check
243
  ///      generation, allow for the normal IR level stack protector check
244
  ///      generation to continue.
245
  ///
246
  ///   2. On platforms that do support SelectionDAG stack protector check
247
  ///      generation:
248
  ///
249
  ///     a. Use the IR level stack protector pass to decide if a stack
250
  ///        protector is required/which BB we insert the stack protector check
251
  ///        in by reusing the logic already therein. If we wish to generate a
252
  ///        stack protector check in a basic block, we place a special IR
253
  ///        intrinsic called llvm.stackprotectorcheck right before the BB's
254
  ///        returninst or if there is a callinst that could potentially be
255
  ///        sibling call optimized, before the call inst.
256
  ///
257
  ///     b. Then when a BB with said intrinsic is processed, we codegen the BB
258
  ///        normally via SelectBasicBlock. In said process, when we visit the
259
  ///        stack protector check, we do not actually emit anything into the
260
  ///        BB. Instead, we just initialize the stack protector descriptor
261
  ///        class (which involves stashing information/creating the success
262
  ///        mbbb and the failure mbb if we have not created one for this
263
  ///        function yet) and export the guard variable that we are going to
264
  ///        compare.
265
  ///
266
  ///     c. After we finish selecting the basic block, in FinishBasicBlock if
267
  ///        the StackProtectorDescriptor attached to the SelectionDAGBuilder is
268
  ///        initialized, we produce the validation code with one of these
269
  ///        techniques:
270
  ///          1) with a call to a guard check function
271
  ///          2) with inlined instrumentation
272
  ///
273
  ///        1) We insert a call to the check function before the terminator.
274
  ///
275
  ///        2) We first find a splice point in the parent basic block
276
  ///        before the terminator and then splice the terminator of said basic
277
  ///        block into the success basic block. Then we code-gen a new tail for
278
  ///        the parent basic block consisting of the two loads, the comparison,
279
  ///        and finally two branches to the success/failure basic blocks. We
280
  ///        conclude by code-gening the failure basic block if we have not
281
  ///        code-gened it already (all stack protector checks we generate in
282
  ///        the same function, use the same failure basic block).
283
  class StackProtectorDescriptor {
284
  public:
285
38.1k
    StackProtectorDescriptor() = default;
286
287
    /// Returns true if all fields of the stack protector descriptor are
288
    /// initialized implying that we should/are ready to emit a stack protector.
289
1.20M
    bool shouldEmitStackProtector() const {
290
1.20M
      return ParentMBB && 
SuccessMBB402
&&
FailureMBB402
;
291
1.20M
    }
292
293
1.20M
    bool shouldEmitFunctionBasedCheckStackProtector() const {
294
1.20M
      return ParentMBB && 
!SuccessMBB486
&&
!FailureMBB84
;
295
1.20M
    }
296
297
    /// Initialize the stack protector descriptor structure for a new basic
298
    /// block.
299
    void initialize(const BasicBlock *BB, MachineBasicBlock *MBB,
300
486
                    bool FunctionBasedInstrumentation) {
301
486
      // Make sure we are not initialized yet.
302
486
      assert(!shouldEmitStackProtector() && "Stack Protector Descriptor is "
303
486
             "already initialized!");
304
486
      ParentMBB = MBB;
305
486
      if (!FunctionBasedInstrumentation) {
306
402
        SuccessMBB = AddSuccessorMBB(BB, MBB, /* IsLikely */ true);
307
402
        FailureMBB = AddSuccessorMBB(BB, MBB, /* IsLikely */ false, FailureMBB);
308
402
      }
309
486
    }
310
311
    /// Reset state that changes when we handle different basic blocks.
312
    ///
313
    /// This currently includes:
314
    ///
315
    /// 1. The specific basic block we are generating a
316
    /// stack protector for (ParentMBB).
317
    ///
318
    /// 2. The successor machine basic block that will contain the tail of
319
    /// parent mbb after we create the stack protector check (SuccessMBB). This
320
    /// BB is visited only on stack protector check success.
321
486
    void resetPerBBState() {
322
486
      ParentMBB = nullptr;
323
486
      SuccessMBB = nullptr;
324
486
    }
325
326
    /// Reset state that only changes when we switch functions.
327
    ///
328
    /// This currently includes:
329
    ///
330
    /// 1. FailureMBB since we reuse the failure code path for all stack
331
    /// protector checks created in an individual function.
332
    ///
333
    /// 2.The guard variable since the guard variable we are checking against is
334
    /// always the same.
335
277k
    void resetPerFunctionState() {
336
277k
      FailureMBB = nullptr;
337
277k
    }
338
339
486
    MachineBasicBlock *getParentMBB() { return ParentMBB; }
340
804
    MachineBasicBlock *getSuccessMBB() { return SuccessMBB; }
341
804
    MachineBasicBlock *getFailureMBB() { return FailureMBB; }
342
343
  private:
344
    /// The basic block for which we are generating the stack protector.
345
    ///
346
    /// As a result of stack protector generation, we will splice the
347
    /// terminators of this basic block into the successor mbb SuccessMBB and
348
    /// replace it with a compare/branch to the successor mbbs
349
    /// SuccessMBB/FailureMBB depending on whether or not the stack protector
350
    /// was violated.
351
    MachineBasicBlock *ParentMBB = nullptr;
352
353
    /// A basic block visited on stack protector check success that contains the
354
    /// terminators of ParentMBB.
355
    MachineBasicBlock *SuccessMBB = nullptr;
356
357
    /// This basic block visited on stack protector check failure that will
358
    /// contain a call to __stack_chk_fail().
359
    MachineBasicBlock *FailureMBB = nullptr;
360
361
    /// Add a successor machine basic block to ParentMBB. If the successor mbb
362
    /// has not been created yet (i.e. if SuccMBB = 0), then the machine basic
363
    /// block will be created. Assign a large weight if IsLikely is true.
364
    MachineBasicBlock *AddSuccessorMBB(const BasicBlock *BB,
365
                                       MachineBasicBlock *ParentMBB,
366
                                       bool IsLikely,
367
                                       MachineBasicBlock *SuccMBB = nullptr);
368
  };
369
370
private:
371
  const TargetMachine &TM;
372
373
public:
374
  /// Lowest valid SDNodeOrder. The special case 0 is reserved for scheduling
375
  /// nodes without a corresponding SDNode.
376
  static const unsigned LowestSDNodeOrder = 1;
377
378
  SelectionDAG &DAG;
379
  const DataLayout *DL = nullptr;
380
  AliasAnalysis *AA = nullptr;
381
  const TargetLibraryInfo *LibInfo;
382
383
  class SDAGSwitchLowering : public SwitchCG::SwitchLowering {
384
  public:
385
    SDAGSwitchLowering(SelectionDAGBuilder *sdb, FunctionLoweringInfo &funcinfo)
386
38.1k
        : SwitchCG::SwitchLowering(funcinfo), SDB(sdb) {}
387
388
    virtual void addSuccessorWithProb(
389
        MachineBasicBlock *Src, MachineBasicBlock *Dst,
390
12.6k
        BranchProbability Prob = BranchProbability::getUnknown()) override {
391
12.6k
      SDB->addSuccessorWithProb(Src, Dst, Prob);
392
12.6k
    }
393
394
  private:
395
    SelectionDAGBuilder *SDB;
396
  };
397
398
  std::unique_ptr<SDAGSwitchLowering> SL;
399
400
  /// A StackProtectorDescriptor structure used to communicate stack protector
401
  /// information in between SelectBasicBlock and FinishBasicBlock.
402
  StackProtectorDescriptor SPDescriptor;
403
404
  // Emit PHI-node-operand constants only once even if used by multiple
405
  // PHI nodes.
406
  DenseMap<const Constant *, unsigned> ConstantsOut;
407
408
  /// Information about the function as a whole.
409
  FunctionLoweringInfo &FuncInfo;
410
411
  /// Information about the swifterror values used throughout the function.
412
  SwiftErrorValueTracking &SwiftError;
413
414
  /// Garbage collection metadata for the function.
415
  GCFunctionInfo *GFI;
416
417
  /// Map a landing pad to the call site indexes.
418
  DenseMap<MachineBasicBlock *, SmallVector<unsigned, 4>> LPadToCallSiteMap;
419
420
  /// This is set to true if a call in the current block has been translated as
421
  /// a tail call. In this case, no subsequent DAG nodes should be created.
422
  bool HasTailCall = false;
423
424
  LLVMContext *Context;
425
426
  SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo,
427
                      SwiftErrorValueTracking &swifterror, CodeGenOpt::Level ol)
428
      : SDNodeOrder(LowestSDNodeOrder), TM(dag.getTarget()), DAG(dag),
429
        SL(make_unique<SDAGSwitchLowering>(this, funcinfo)), FuncInfo(funcinfo),
430
38.1k
        SwiftError(swifterror) {}
431
432
  void init(GCFunctionInfo *gfi, AliasAnalysis *AA,
433
            const TargetLibraryInfo *li);
434
435
  /// Clear out the current SelectionDAG and the associated state and prepare
436
  /// this SelectionDAGBuilder object to be used for a new block. This doesn't
437
  /// clear out information about additional blocks that are needed to complete
438
  /// switch lowering or PHI node updating; that information is cleared out as
439
  /// it is consumed.
440
  void clear();
441
442
  /// Clear the dangling debug information map. This function is separated from
443
  /// the clear so that debug information that is dangling in a basic block can
444
  /// be properly resolved in a different basic block. This allows the
445
  /// SelectionDAG to resolve dangling debug information attached to PHI nodes.
446
  void clearDanglingDebugInfo();
447
448
  /// Return the current virtual root of the Selection DAG, flushing any
449
  /// PendingLoad items. This must be done before emitting a store or any other
450
  /// node that may need to be ordered after any prior load instructions.
451
  SDValue getRoot();
452
453
  /// Similar to getRoot, but instead of flushing all the PendingLoad items,
454
  /// flush all the PendingExports items. It is necessary to do this before
455
  /// emitting a terminator instruction.
456
  SDValue getControlRoot();
457
458
14.3M
  SDLoc getCurSDLoc() const {
459
14.3M
    return SDLoc(CurInst, SDNodeOrder);
460
14.3M
  }
461
462
568k
  DebugLoc getCurDebugLoc() const {
463
568k
    return CurInst ? 
CurInst->getDebugLoc()286k
:
DebugLoc()281k
;
464
568k
  }
465
466
  void CopyValueToVirtualRegister(const Value *V, unsigned Reg);
467
468
  void visit(const Instruction &I);
469
470
  void visit(unsigned Opcode, const User &I);
471
472
  /// If there was virtual register allocated for the value V emit CopyFromReg
473
  /// of the specified type Ty. Return empty SDValue() otherwise.
474
  SDValue getCopyFromRegs(const Value *V, Type *Ty);
475
476
  /// If we have dangling debug info that describes \p Variable, or an
477
  /// overlapping part of variable considering the \p Expr, then this method
478
  /// will drop that debug info as it isn't valid any longer.
479
  void dropDanglingDebugInfo(const DILocalVariable *Variable,
480
                             const DIExpression *Expr);
481
482
  /// If we saw an earlier dbg_value referring to V, generate the debug data
483
  /// structures now that we've seen its definition.
484
  void resolveDanglingDebugInfo(const Value *V, SDValue Val);
485
486
  /// For the given dangling debuginfo record, perform last-ditch efforts to
487
  /// resolve the debuginfo to something that is represented in this DAG. If
488
  /// this cannot be done, produce an Undef debug value record.
489
  void salvageUnresolvedDbgValue(DanglingDebugInfo &DDI);
490
491
  /// For a given Value, attempt to create and record a SDDbgValue in the
492
  /// SelectionDAG.
493
  bool handleDebugValue(const Value *V, DILocalVariable *Var,
494
                        DIExpression *Expr, DebugLoc CurDL,
495
                        DebugLoc InstDL, unsigned Order);
496
497
  /// Evict any dangling debug information, attempting to salvage it first.
498
  void resolveOrClearDbgInfo();
499
500
  SDValue getValue(const Value *V);
501
  bool findValue(const Value *V) const;
502
503
  /// Return the SDNode for the specified IR value if it exists.
504
238k
  SDNode *getNodeForIRValue(const Value *V) {
505
238k
    if (NodeMap.find(V) == NodeMap.end())
506
261
      return nullptr;
507
237k
    return NodeMap[V].getNode();
508
237k
  }
509
510
  SDValue getNonRegisterValue(const Value *V);
511
  SDValue getValueImpl(const Value *V);
512
513
5.43M
  void setValue(const Value *V, SDValue NewN) {
514
5.43M
    SDValue &N = NodeMap[V];
515
5.43M
    assert(!N.getNode() && "Already set a value for this node!");
516
5.43M
    N = NewN;
517
5.43M
  }
518
519
64.5k
  void setUnusedArgValue(const Value *V, SDValue NewN) {
520
64.5k
    SDValue &N = UnusedArgNodeMap[V];
521
64.5k
    assert(!N.getNode() && "Already set a value for this node!");
522
64.5k
    N = NewN;
523
64.5k
  }
524
525
  void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB,
526
                            MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
527
                            MachineBasicBlock *SwitchBB,
528
                            Instruction::BinaryOps Opc, BranchProbability TProb,
529
                            BranchProbability FProb, bool InvertCond);
530
  void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB,
531
                                    MachineBasicBlock *FBB,
532
                                    MachineBasicBlock *CurBB,
533
                                    MachineBasicBlock *SwitchBB,
534
                                    BranchProbability TProb, BranchProbability FProb,
535
                                    bool InvertCond);
536
  bool ShouldEmitAsBranches(const std::vector<SwitchCG::CaseBlock> &Cases);
537
  bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB);
538
  void CopyToExportRegsIfNeeded(const Value *V);
539
  void ExportFromCurrentBlock(const Value *V);
540
  void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall,
541
                   const BasicBlock *EHPadBB = nullptr);
542
543
  // Lower range metadata from 0 to N to assert zext to an integer of nearest
544
  // floor power of two.
545
  SDValue lowerRangeToAssertZExt(SelectionDAG &DAG, const Instruction &I,
546
                                 SDValue Op);
547
548
  void populateCallLoweringInfo(TargetLowering::CallLoweringInfo &CLI,
549
                                const CallBase *Call, unsigned ArgIdx,
550
                                unsigned NumArgs, SDValue Callee,
551
                                Type *ReturnTy, bool IsPatchPoint);
552
553
  std::pair<SDValue, SDValue>
554
  lowerInvokable(TargetLowering::CallLoweringInfo &CLI,
555
                 const BasicBlock *EHPadBB = nullptr);
556
557
  /// When an MBB was split during scheduling, update the
558
  /// references that need to refer to the last resulting block.
559
  void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last);
560
561
  /// Describes a gc.statepoint or a gc.statepoint like thing for the purposes
562
  /// of lowering into a STATEPOINT node.
563
  struct StatepointLoweringInfo {
564
    /// Bases[i] is the base pointer for Ptrs[i].  Together they denote the set
565
    /// of gc pointers this STATEPOINT has to relocate.
566
    SmallVector<const Value *, 16> Bases;
567
    SmallVector<const Value *, 16> Ptrs;
568
569
    /// The set of gc.relocate calls associated with this gc.statepoint.
570
    SmallVector<const GCRelocateInst *, 16> GCRelocates;
571
572
    /// The full list of gc arguments to the gc.statepoint being lowered.
573
    ArrayRef<const Use> GCArgs;
574
575
    /// The gc.statepoint instruction.
576
    const Instruction *StatepointInstr = nullptr;
577
578
    /// The list of gc transition arguments present in the gc.statepoint being
579
    /// lowered.
580
    ArrayRef<const Use> GCTransitionArgs;
581
582
    /// The ID that the resulting STATEPOINT instruction has to report.
583
    unsigned ID = -1;
584
585
    /// Information regarding the underlying call instruction.
586
    TargetLowering::CallLoweringInfo CLI;
587
588
    /// The deoptimization state associated with this gc.statepoint call, if
589
    /// any.
590
    ArrayRef<const Use> DeoptState;
591
592
    /// Flags associated with the meta arguments being lowered.
593
    uint64_t StatepointFlags = -1;
594
595
    /// The number of patchable bytes the call needs to get lowered into.
596
    unsigned NumPatchBytes = -1;
597
598
    /// The exception handling unwind destination, in case this represents an
599
    /// invoke of gc.statepoint.
600
    const BasicBlock *EHPadBB = nullptr;
601
602
88
    explicit StatepointLoweringInfo(SelectionDAG &DAG) : CLI(DAG) {}
603
  };
604
605
  /// Lower \p SLI into a STATEPOINT instruction.
606
  SDValue LowerAsSTATEPOINT(StatepointLoweringInfo &SI);
607
608
  // This function is responsible for the whole statepoint lowering process.
609
  // It uniformly handles invoke and call statepoints.
610
  void LowerStatepoint(ImmutableStatepoint ISP,
611
                       const BasicBlock *EHPadBB = nullptr);
612
613
  void LowerCallSiteWithDeoptBundle(const CallBase *Call, SDValue Callee,
614
                                    const BasicBlock *EHPadBB);
615
616
  void LowerDeoptimizeCall(const CallInst *CI);
617
  void LowerDeoptimizingReturn();
618
619
  void LowerCallSiteWithDeoptBundleImpl(const CallBase *Call, SDValue Callee,
620
                                        const BasicBlock *EHPadBB,
621
                                        bool VarArgDisallowed,
622
                                        bool ForceVoidReturnTy);
623
624
  /// Returns the type of FrameIndex and TargetFrameIndex nodes.
625
151
  MVT getFrameIndexTy() {
626
151
    return DAG.getTargetLoweringInfo().getFrameIndexTy(DAG.getDataLayout());
627
151
  }
628
629
private:
630
  // Terminator instructions.
631
  void visitRet(const ReturnInst &I);
632
  void visitBr(const BranchInst &I);
633
  void visitSwitch(const SwitchInst &I);
634
  void visitIndirectBr(const IndirectBrInst &I);
635
  void visitUnreachable(const UnreachableInst &I);
636
  void visitCleanupRet(const CleanupReturnInst &I);
637
  void visitCatchSwitch(const CatchSwitchInst &I);
638
  void visitCatchRet(const CatchReturnInst &I);
639
  void visitCatchPad(const CatchPadInst &I);
640
  void visitCleanupPad(const CleanupPadInst &CPI);
641
642
  BranchProbability getEdgeProbability(const MachineBasicBlock *Src,
643
                                       const MachineBasicBlock *Dst) const;
644
  void addSuccessorWithProb(
645
      MachineBasicBlock *Src, MachineBasicBlock *Dst,
646
      BranchProbability Prob = BranchProbability::getUnknown());
647
648
public:
649
  void visitSwitchCase(SwitchCG::CaseBlock &CB, MachineBasicBlock *SwitchBB);
650
  void visitSPDescriptorParent(StackProtectorDescriptor &SPD,
651
                               MachineBasicBlock *ParentBB);
652
  void visitSPDescriptorFailure(StackProtectorDescriptor &SPD);
653
  void visitBitTestHeader(SwitchCG::BitTestBlock &B,
654
                          MachineBasicBlock *SwitchBB);
655
  void visitBitTestCase(SwitchCG::BitTestBlock &BB, MachineBasicBlock *NextMBB,
656
                        BranchProbability BranchProbToNext, unsigned Reg,
657
                        SwitchCG::BitTestCase &B, MachineBasicBlock *SwitchBB);
658
  void visitJumpTable(SwitchCG::JumpTable &JT);
659
  void visitJumpTableHeader(SwitchCG::JumpTable &JT,
660
                            SwitchCG::JumpTableHeader &JTH,
661
                            MachineBasicBlock *SwitchBB);
662
663
private:
664
  // These all get lowered before this pass.
665
  void visitInvoke(const InvokeInst &I);
666
  void visitCallBr(const CallBrInst &I);
667
  void visitResume(const ResumeInst &I);
668
669
  void visitUnary(const User &I, unsigned Opcode);
670
66
  void visitFNeg(const User &I) { visitUnary(I, ISD::FNEG); }
671
672
  void visitBinary(const User &I, unsigned Opcode);
673
  void visitShift(const User &I, unsigned Opcode);
674
241k
  void visitAdd(const User &I)  { visitBinary(I, ISD::ADD); }
675
30.6k
  void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); }
676
54.0k
  void visitSub(const User &I)  { visitBinary(I, ISD::SUB); }
677
  void visitFSub(const User &I);
678
40.6k
  void visitMul(const User &I)  { visitBinary(I, ISD::MUL); }
679
24.1k
  void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); }
680
2.51k
  void visitURem(const User &I) { visitBinary(I, ISD::UREM); }
681
2.66k
  void visitSRem(const User &I) { visitBinary(I, ISD::SREM); }
682
177
  void visitFRem(const User &I) { visitBinary(I, ISD::FREM); }
683
2.76k
  void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); }
684
  void visitSDiv(const User &I);
685
23.5k
  void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); }
686
118k
  void visitAnd (const User &I) { visitBinary(I, ISD::AND); }
687
38.1k
  void visitOr  (const User &I) { visitBinary(I, ISD::OR); }
688
24.1k
  void visitXor (const User &I) { visitBinary(I, ISD::XOR); }
689
61.4k
  void visitShl (const User &I) { visitShift(I, ISD::SHL); }
690
46.3k
  void visitLShr(const User &I) { visitShift(I, ISD::SRL); }
691
9.78k
  void visitAShr(const User &I) { visitShift(I, ISD::SRA); }
692
  void visitICmp(const User &I);
693
  void visitFCmp(const User &I);
694
  // Visit the conversion instructions
695
  void visitTrunc(const User &I);
696
  void visitZExt(const User &I);
697
  void visitSExt(const User &I);
698
  void visitFPTrunc(const User &I);
699
  void visitFPExt(const User &I);
700
  void visitFPToUI(const User &I);
701
  void visitFPToSI(const User &I);
702
  void visitUIToFP(const User &I);
703
  void visitSIToFP(const User &I);
704
  void visitPtrToInt(const User &I);
705
  void visitIntToPtr(const User &I);
706
  void visitBitCast(const User &I);
707
  void visitAddrSpaceCast(const User &I);
708
709
  void visitExtractElement(const User &I);
710
  void visitInsertElement(const User &I);
711
  void visitShuffleVector(const User &I);
712
713
  void visitExtractValue(const User &I);
714
  void visitInsertValue(const User &I);
715
  void visitLandingPad(const LandingPadInst &LP);
716
717
  void visitGetElementPtr(const User &I);
718
  void visitSelect(const User &I);
719
720
  void visitAlloca(const AllocaInst &I);
721
  void visitLoad(const LoadInst &I);
722
  void visitStore(const StoreInst &I);
723
  void visitMaskedLoad(const CallInst &I, bool IsExpanding = false);
724
  void visitMaskedStore(const CallInst &I, bool IsCompressing = false);
725
  void visitMaskedGather(const CallInst &I);
726
  void visitMaskedScatter(const CallInst &I);
727
  void visitAtomicCmpXchg(const AtomicCmpXchgInst &I);
728
  void visitAtomicRMW(const AtomicRMWInst &I);
729
  void visitFence(const FenceInst &I);
730
  void visitPHI(const PHINode &I);
731
  void visitCall(const CallInst &I);
732
  bool visitMemCmpCall(const CallInst &I);
733
  bool visitMemPCpyCall(const CallInst &I);
734
  bool visitMemChrCall(const CallInst &I);
735
  bool visitStrCpyCall(const CallInst &I, bool isStpcpy);
736
  bool visitStrCmpCall(const CallInst &I);
737
  bool visitStrLenCall(const CallInst &I);
738
  bool visitStrNLenCall(const CallInst &I);
739
  bool visitUnaryFloatCall(const CallInst &I, unsigned Opcode);
740
  bool visitBinaryFloatCall(const CallInst &I, unsigned Opcode);
741
  void visitAtomicLoad(const LoadInst &I);
742
  void visitAtomicStore(const StoreInst &I);
743
  void visitLoadFromSwiftError(const LoadInst &I);
744
  void visitStoreToSwiftError(const StoreInst &I);
745
746
  void visitInlineAsm(ImmutableCallSite CS);
747
  void visitIntrinsicCall(const CallInst &I, unsigned Intrinsic);
748
  void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic);
749
  void visitConstrainedFPIntrinsic(const ConstrainedFPIntrinsic &FPI);
750
751
  void visitVAStart(const CallInst &I);
752
  void visitVAArg(const VAArgInst &I);
753
  void visitVAEnd(const CallInst &I);
754
  void visitVACopy(const CallInst &I);
755
  void visitStackmap(const CallInst &I);
756
  void visitPatchpoint(ImmutableCallSite CS,
757
                       const BasicBlock *EHPadBB = nullptr);
758
759
  // These two are implemented in StatepointLowering.cpp
760
  void visitGCRelocate(const GCRelocateInst &Relocate);
761
  void visitGCResult(const GCResultInst &I);
762
763
  void visitVectorReduce(const CallInst &I, unsigned Intrinsic);
764
765
0
  void visitUserOp1(const Instruction &I) {
766
0
    llvm_unreachable("UserOp1 should not exist at instruction selection time!");
767
0
  }
768
0
  void visitUserOp2(const Instruction &I) {
769
0
    llvm_unreachable("UserOp2 should not exist at instruction selection time!");
770
0
  }
771
772
  void processIntegerCallValue(const Instruction &I,
773
                               SDValue Value, bool IsSigned);
774
775
  void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB);
776
777
  void emitInlineAsmError(ImmutableCallSite CS, const Twine &Message);
778
779
  /// If V is an function argument then create corresponding DBG_VALUE machine
780
  /// instruction for it now. At the end of instruction selection, they will be
781
  /// inserted to the entry BB.
782
  bool EmitFuncArgumentDbgValue(const Value *V, DILocalVariable *Variable,
783
                                DIExpression *Expr, DILocation *DL,
784
                                bool IsDbgDeclare, const SDValue &N);
785
786
  /// Return the next block after MBB, or nullptr if there is none.
787
  MachineBasicBlock *NextBlock(MachineBasicBlock *MBB);
788
789
  /// Update the DAG and DAG builder with the relevant information after
790
  /// a new root node has been created which could be a tail call.
791
  void updateDAGForMaybeTailCall(SDValue MaybeTC);
792
793
  /// Return the appropriate SDDbgValue based on N.
794
  SDDbgValue *getDbgValue(SDValue N, DILocalVariable *Variable,
795
                          DIExpression *Expr, const DebugLoc &dl,
796
                          unsigned DbgSDNodeOrder);
797
798
  /// Lowers CallInst to an external symbol.
799
  void lowerCallToExternalSymbol(const CallInst &I, const char *FunctionName);
800
};
801
802
/// This struct represents the registers (physical or virtual)
803
/// that a particular set of values is assigned, and the type information about
804
/// the value. The most common situation is to represent one value at a time,
805
/// but struct or array values are handled element-wise as multiple values.  The
806
/// splitting of aggregates is performed recursively, so that we never have
807
/// aggregate-typed registers. The values at this point do not necessarily have
808
/// legal types, so each value may require one or more registers of some legal
809
/// type.
810
///
811
struct RegsForValue {
812
  /// The value types of the values, which may not be legal, and
813
  /// may need be promoted or synthesized from one or more registers.
814
  SmallVector<EVT, 4> ValueVTs;
815
816
  /// The value types of the registers. This is the same size as ValueVTs and it
817
  /// records, for each value, what the type of the assigned register or
818
  /// registers are. (Individual values are never synthesized from more than one
819
  /// type of register.)
820
  ///
821
  /// With virtual registers, the contents of RegVTs is redundant with TLI's
822
  /// getRegisterType member function, however when with physical registers
823
  /// it is necessary to have a separate record of the types.
824
  SmallVector<MVT, 4> RegVTs;
825
826
  /// This list holds the registers assigned to the values.
827
  /// Each legal or promoted value requires one register, and each
828
  /// expanded value requires multiple registers.
829
  SmallVector<unsigned, 4> Regs;
830
831
  /// This list holds the number of registers for each value.
832
  SmallVector<unsigned, 4> RegCount;
833
834
  /// Records if this value needs to be treated in an ABI dependant manner,
835
  /// different to normal type legalization.
836
  Optional<CallingConv::ID> CallConv;
837
838
102k
  RegsForValue() = default;
839
  RegsForValue(const SmallVector<unsigned, 4> &regs, MVT regvt, EVT valuevt,
840
               Optional<CallingConv::ID> CC = None);
841
  RegsForValue(LLVMContext &Context, const TargetLowering &TLI,
842
               const DataLayout &DL, unsigned Reg, Type *Ty,
843
               Optional<CallingConv::ID> CC);
844
845
7.86M
  bool isABIMangled() const {
846
7.86M
    return CallConv.hasValue();
847
7.86M
  }
848
849
  /// Add the specified values to this one.
850
0
  void append(const RegsForValue &RHS) {
851
0
    ValueVTs.append(RHS.ValueVTs.begin(), RHS.ValueVTs.end());
852
0
    RegVTs.append(RHS.RegVTs.begin(), RHS.RegVTs.end());
853
0
    Regs.append(RHS.Regs.begin(), RHS.Regs.end());
854
0
    RegCount.push_back(RHS.Regs.size());
855
0
  }
856
857
  /// Emit a series of CopyFromReg nodes that copies from this value and returns
858
  /// the result as a ValueVTs value. This uses Chain/Flag as the input and
859
  /// updates them for the output Chain/Flag. If the Flag pointer is NULL, no
860
  /// flag is used.
861
  SDValue getCopyFromRegs(SelectionDAG &DAG, FunctionLoweringInfo &FuncInfo,
862
                          const SDLoc &dl, SDValue &Chain, SDValue *Flag,
863
                          const Value *V = nullptr) const;
864
865
  /// Emit a series of CopyToReg nodes that copies the specified value into the
866
  /// registers specified by this object. This uses Chain/Flag as the input and
867
  /// updates them for the output Chain/Flag. If the Flag pointer is nullptr, no
868
  /// flag is used. If V is not nullptr, then it is used in printing better
869
  /// diagnostic messages on error.
870
  void getCopyToRegs(SDValue Val, SelectionDAG &DAG, const SDLoc &dl,
871
                     SDValue &Chain, SDValue *Flag, const Value *V = nullptr,
872
                     ISD::NodeType PreferredExtendType = ISD::ANY_EXTEND) const;
873
874
  /// Add this value to the specified inlineasm node operand list. This adds the
875
  /// code marker, matching input operand index (if applicable), and includes
876
  /// the number of values added into it.
877
  void AddInlineAsmOperands(unsigned Code, bool HasMatching,
878
                            unsigned MatchingIdx, const SDLoc &dl,
879
                            SelectionDAG &DAG, std::vector<SDValue> &Ops) const;
880
881
  /// Check if the total RegCount is greater than one.
882
51
  bool occupiesMultipleRegs() const {
883
51
    return std::accumulate(RegCount.begin(), RegCount.end(), 0) > 1;
884
51
  }
885
886
  /// Return a list of registers and their sizes.
887
  SmallVector<std::pair<unsigned, unsigned>, 4> getRegsAndSizes() const;
888
};
889
890
} // end namespace llvm
891
892
#endif // LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H