1//===-- llvm/CodeGen/SelectionDAGISel.h - Common Base Class------*- 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 file implements the SelectionDAGISel class, which is used as the common
10// base class for SelectionDAG-based instruction selectors.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CODEGEN_SELECTIONDAGISEL_H
15#define LLVM_CODEGEN_SELECTIONDAGISEL_H
16
17#include "llvm/CodeGen/MachineFunctionPass.h"
18#include "llvm/CodeGen/SelectionDAG.h"
19#include "llvm/IR/BasicBlock.h"
20#include <memory>
21
22namespace llvm {
23class AAResults;
24class AssumptionCache;
25class TargetInstrInfo;
26class TargetMachine;
27class SelectionDAGBuilder;
28class SDValue;
29class MachineRegisterInfo;
30class MachineFunction;
31class OptimizationRemarkEmitter;
32class TargetLowering;
33class TargetLibraryInfo;
34class FunctionLoweringInfo;
35class SwiftErrorValueTracking;
36class GCFunctionInfo;
37class ScheduleDAGSDNodes;
38
39/// SelectionDAGISel - This is the common base class used for SelectionDAG-based
40/// pattern-matching instruction selectors.
41class SelectionDAGISel : public MachineFunctionPass {
42public:
43 TargetMachine &TM;
44 const TargetLibraryInfo *LibInfo;
45 std::unique_ptr<FunctionLoweringInfo> FuncInfo;
46 SwiftErrorValueTracking *SwiftError;
47 MachineFunction *MF;
48 MachineRegisterInfo *RegInfo;
49 SelectionDAG *CurDAG;
50 std::unique_ptr<SelectionDAGBuilder> SDB;
51 AAResults *AA = nullptr;
52 AssumptionCache *AC = nullptr;
53 GCFunctionInfo *GFI = nullptr;
54 CodeGenOptLevel OptLevel;
55 const TargetInstrInfo *TII;
56 const TargetLowering *TLI;
57 bool FastISelFailed;
58 SmallPtrSet<const Instruction *, 4> ElidedArgCopyInstrs;
59
60 /// Current optimization remark emitter.
61 /// Used to report things like combines and FastISel failures.
62 std::unique_ptr<OptimizationRemarkEmitter> ORE;
63
64 /// True if the function currently processing is in the function printing list
65 /// (i.e. `-filter-print-funcs`).
66 /// This is primarily used by ISEL_DUMP, which spans in multiple member
67 /// functions. Storing the filter result here so that we only need to do the
68 /// filtering once.
69 bool MatchFilterFuncName = false;
70
71 explicit SelectionDAGISel(char &ID, TargetMachine &tm,
72 CodeGenOptLevel OL = CodeGenOptLevel::Default);
73 ~SelectionDAGISel() override;
74
75 const TargetLowering *getTargetLowering() const { return TLI; }
76
77 void getAnalysisUsage(AnalysisUsage &AU) const override;
78
79 bool runOnMachineFunction(MachineFunction &MF) override;
80
81 virtual void emitFunctionEntryCode() {}
82
83 /// PreprocessISelDAG - This hook allows targets to hack on the graph before
84 /// instruction selection starts.
85 virtual void PreprocessISelDAG() {}
86
87 /// PostprocessISelDAG() - This hook allows the target to hack on the graph
88 /// right after selection.
89 virtual void PostprocessISelDAG() {}
90
91 /// Main hook for targets to transform nodes into machine nodes.
92 virtual void Select(SDNode *N) = 0;
93
94 /// SelectInlineAsmMemoryOperand - Select the specified address as a target
95 /// addressing mode, according to the specified constraint. If this does
96 /// not match or is not implemented, return true. The resultant operands
97 /// (which will appear in the machine instruction) should be added to the
98 /// OutOps vector.
99 virtual bool
100 SelectInlineAsmMemoryOperand(const SDValue &Op,
101 InlineAsm::ConstraintCode ConstraintID,
102 std::vector<SDValue> &OutOps) {
103 return true;
104 }
105
106 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
107 /// operand node N of U during instruction selection that starts at Root.
108 virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
109
110 /// IsLegalToFold - Returns true if the specific operand node N of
111 /// U can be folded during instruction selection that starts at Root.
112 /// FIXME: This is a static member function because the MSP430/X86
113 /// targets, which uses it during isel. This could become a proper member.
114 static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
115 CodeGenOptLevel OptLevel,
116 bool IgnoreChains = false);
117
118 static void InvalidateNodeId(SDNode *N);
119 static int getUninvalidatedNodeId(SDNode *N);
120
121 static void EnforceNodeIdInvariant(SDNode *N);
122
123 // Opcodes used by the DAG state machine:
124 enum BuiltinOpcodes {
125 OPC_Scope,
126 OPC_RecordNode,
127 OPC_RecordChild0,
128 OPC_RecordChild1,
129 OPC_RecordChild2,
130 OPC_RecordChild3,
131 OPC_RecordChild4,
132 OPC_RecordChild5,
133 OPC_RecordChild6,
134 OPC_RecordChild7,
135 OPC_RecordMemRef,
136 OPC_CaptureGlueInput,
137 OPC_MoveChild,
138 OPC_MoveChild0,
139 OPC_MoveChild1,
140 OPC_MoveChild2,
141 OPC_MoveChild3,
142 OPC_MoveChild4,
143 OPC_MoveChild5,
144 OPC_MoveChild6,
145 OPC_MoveChild7,
146 OPC_MoveSibling,
147 OPC_MoveSibling0,
148 OPC_MoveSibling1,
149 OPC_MoveSibling2,
150 OPC_MoveSibling3,
151 OPC_MoveSibling4,
152 OPC_MoveSibling5,
153 OPC_MoveSibling6,
154 OPC_MoveSibling7,
155 OPC_MoveParent,
156 OPC_CheckSame,
157 OPC_CheckChild0Same,
158 OPC_CheckChild1Same,
159 OPC_CheckChild2Same,
160 OPC_CheckChild3Same,
161 OPC_CheckPatternPredicate,
162 OPC_CheckPatternPredicate0,
163 OPC_CheckPatternPredicate1,
164 OPC_CheckPatternPredicate2,
165 OPC_CheckPatternPredicate3,
166 OPC_CheckPatternPredicate4,
167 OPC_CheckPatternPredicate5,
168 OPC_CheckPatternPredicate6,
169 OPC_CheckPatternPredicate7,
170 OPC_CheckPatternPredicateTwoByte,
171 OPC_CheckPredicate,
172 OPC_CheckPredicate0,
173 OPC_CheckPredicate1,
174 OPC_CheckPredicate2,
175 OPC_CheckPredicate3,
176 OPC_CheckPredicate4,
177 OPC_CheckPredicate5,
178 OPC_CheckPredicate6,
179 OPC_CheckPredicate7,
180 OPC_CheckPredicateWithOperands,
181 OPC_CheckOpcode,
182 OPC_SwitchOpcode,
183 OPC_CheckType,
184 // Space-optimized forms that implicitly encode VT.
185 OPC_CheckTypeI32,
186 OPC_CheckTypeI64,
187 OPC_CheckTypeRes,
188 OPC_SwitchType,
189 OPC_CheckChild0Type,
190 OPC_CheckChild1Type,
191 OPC_CheckChild2Type,
192 OPC_CheckChild3Type,
193 OPC_CheckChild4Type,
194 OPC_CheckChild5Type,
195 OPC_CheckChild6Type,
196 OPC_CheckChild7Type,
197
198 OPC_CheckChild0TypeI32,
199 OPC_CheckChild1TypeI32,
200 OPC_CheckChild2TypeI32,
201 OPC_CheckChild3TypeI32,
202 OPC_CheckChild4TypeI32,
203 OPC_CheckChild5TypeI32,
204 OPC_CheckChild6TypeI32,
205 OPC_CheckChild7TypeI32,
206
207 OPC_CheckChild0TypeI64,
208 OPC_CheckChild1TypeI64,
209 OPC_CheckChild2TypeI64,
210 OPC_CheckChild3TypeI64,
211 OPC_CheckChild4TypeI64,
212 OPC_CheckChild5TypeI64,
213 OPC_CheckChild6TypeI64,
214 OPC_CheckChild7TypeI64,
215
216 OPC_CheckInteger,
217 OPC_CheckChild0Integer,
218 OPC_CheckChild1Integer,
219 OPC_CheckChild2Integer,
220 OPC_CheckChild3Integer,
221 OPC_CheckChild4Integer,
222 OPC_CheckCondCode,
223 OPC_CheckChild2CondCode,
224 OPC_CheckValueType,
225 OPC_CheckComplexPat,
226 OPC_CheckComplexPat0,
227 OPC_CheckComplexPat1,
228 OPC_CheckComplexPat2,
229 OPC_CheckComplexPat3,
230 OPC_CheckComplexPat4,
231 OPC_CheckComplexPat5,
232 OPC_CheckComplexPat6,
233 OPC_CheckComplexPat7,
234 OPC_CheckAndImm,
235 OPC_CheckOrImm,
236 OPC_CheckImmAllOnesV,
237 OPC_CheckImmAllZerosV,
238 OPC_CheckFoldableChainNode,
239
240 OPC_EmitInteger,
241 // Space-optimized forms that implicitly encode integer VT.
242 OPC_EmitInteger8,
243 OPC_EmitInteger16,
244 OPC_EmitInteger32,
245 OPC_EmitInteger64,
246 OPC_EmitStringInteger,
247 // Space-optimized forms that implicitly encode integer VT.
248 OPC_EmitStringInteger32,
249 OPC_EmitRegister,
250 OPC_EmitRegisterI32,
251 OPC_EmitRegisterI64,
252 OPC_EmitRegister2,
253 OPC_EmitConvertToTarget,
254 OPC_EmitConvertToTarget0,
255 OPC_EmitConvertToTarget1,
256 OPC_EmitConvertToTarget2,
257 OPC_EmitConvertToTarget3,
258 OPC_EmitConvertToTarget4,
259 OPC_EmitConvertToTarget5,
260 OPC_EmitConvertToTarget6,
261 OPC_EmitConvertToTarget7,
262 OPC_EmitMergeInputChains,
263 OPC_EmitMergeInputChains1_0,
264 OPC_EmitMergeInputChains1_1,
265 OPC_EmitMergeInputChains1_2,
266 OPC_EmitCopyToReg,
267 OPC_EmitCopyToReg0,
268 OPC_EmitCopyToReg1,
269 OPC_EmitCopyToReg2,
270 OPC_EmitCopyToReg3,
271 OPC_EmitCopyToReg4,
272 OPC_EmitCopyToReg5,
273 OPC_EmitCopyToReg6,
274 OPC_EmitCopyToReg7,
275 OPC_EmitCopyToRegTwoByte,
276 OPC_EmitNodeXForm,
277 OPC_EmitNode,
278 // Space-optimized forms that implicitly encode number of result VTs.
279 OPC_EmitNode0,
280 OPC_EmitNode1,
281 OPC_EmitNode2,
282 // Space-optimized forms that implicitly encode EmitNodeInfo.
283 OPC_EmitNode0None,
284 OPC_EmitNode1None,
285 OPC_EmitNode2None,
286 OPC_EmitNode0Chain,
287 OPC_EmitNode1Chain,
288 OPC_EmitNode2Chain,
289 OPC_MorphNodeTo,
290 // Space-optimized forms that implicitly encode number of result VTs.
291 OPC_MorphNodeTo0,
292 OPC_MorphNodeTo1,
293 OPC_MorphNodeTo2,
294 // Space-optimized forms that implicitly encode EmitNodeInfo.
295 OPC_MorphNodeTo0None,
296 OPC_MorphNodeTo1None,
297 OPC_MorphNodeTo2None,
298 OPC_MorphNodeTo0Chain,
299 OPC_MorphNodeTo1Chain,
300 OPC_MorphNodeTo2Chain,
301 OPC_MorphNodeTo0GlueInput,
302 OPC_MorphNodeTo1GlueInput,
303 OPC_MorphNodeTo2GlueInput,
304 OPC_MorphNodeTo0GlueOutput,
305 OPC_MorphNodeTo1GlueOutput,
306 OPC_MorphNodeTo2GlueOutput,
307 OPC_CompleteMatch,
308 // Contains offset in table for pattern being selected
309 OPC_Coverage
310 };
311
312 enum {
313 OPFL_None = 0, // Node has no chain or glue input and isn't variadic.
314 OPFL_Chain = 1, // Node has a chain input.
315 OPFL_GlueInput = 2, // Node has a glue input.
316 OPFL_GlueOutput = 4, // Node has a glue output.
317 OPFL_MemRefs = 8, // Node gets accumulated MemRefs.
318 OPFL_Variadic0 = 1<<4, // Node is variadic, root has 0 fixed inputs.
319 OPFL_Variadic1 = 2<<4, // Node is variadic, root has 1 fixed inputs.
320 OPFL_Variadic2 = 3<<4, // Node is variadic, root has 2 fixed inputs.
321 OPFL_Variadic3 = 4<<4, // Node is variadic, root has 3 fixed inputs.
322 OPFL_Variadic4 = 5<<4, // Node is variadic, root has 4 fixed inputs.
323 OPFL_Variadic5 = 6<<4, // Node is variadic, root has 5 fixed inputs.
324 OPFL_Variadic6 = 7<<4, // Node is variadic, root has 6 fixed inputs.
325
326 OPFL_VariadicInfo = OPFL_Variadic6
327 };
328
329 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
330 /// number of fixed arity values that should be skipped when copying from the
331 /// root.
332 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
333 return ((Flags&OPFL_VariadicInfo) >> 4)-1;
334 }
335
336
337protected:
338 /// DAGSize - Size of DAG being instruction selected.
339 ///
340 unsigned DAGSize = 0;
341
342 /// ReplaceUses - replace all uses of the old node F with the use
343 /// of the new node T.
344 void ReplaceUses(SDValue F, SDValue T) {
345 CurDAG->ReplaceAllUsesOfValueWith(From: F, To: T);
346 EnforceNodeIdInvariant(N: T.getNode());
347 }
348
349 /// ReplaceUses - replace all uses of the old nodes F with the use
350 /// of the new nodes T.
351 void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
352 CurDAG->ReplaceAllUsesOfValuesWith(From: F, To: T, Num);
353 for (unsigned i = 0; i < Num; ++i)
354 EnforceNodeIdInvariant(N: T[i].getNode());
355 }
356
357 /// ReplaceUses - replace all uses of the old node F with the use
358 /// of the new node T.
359 void ReplaceUses(SDNode *F, SDNode *T) {
360 CurDAG->ReplaceAllUsesWith(From: F, To: T);
361 EnforceNodeIdInvariant(N: T);
362 }
363
364 /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
365 void ReplaceNode(SDNode *F, SDNode *T) {
366 CurDAG->ReplaceAllUsesWith(From: F, To: T);
367 EnforceNodeIdInvariant(N: T);
368 CurDAG->RemoveDeadNode(N: F);
369 }
370
371 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
372 /// by tblgen. Others should not call it.
373 void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
374 const SDLoc &DL);
375
376 /// getPatternForIndex - Patterns selected by tablegen during ISEL
377 virtual StringRef getPatternForIndex(unsigned index) {
378 llvm_unreachable("Tblgen should generate the implementation of this!");
379 }
380
381 /// getIncludePathForIndex - get the td source location of pattern instantiation
382 virtual StringRef getIncludePathForIndex(unsigned index) {
383 llvm_unreachable("Tblgen should generate the implementation of this!");
384 }
385
386 bool shouldOptForSize(const MachineFunction *MF) const {
387 return CurDAG->shouldOptForSize();
388 }
389
390public:
391 // Calls to these predicates are generated by tblgen.
392 bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
393 int64_t DesiredMaskS) const;
394 bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
395 int64_t DesiredMaskS) const;
396
397
398 /// CheckPatternPredicate - This function is generated by tblgen in the
399 /// target. It runs the specified pattern predicate and returns true if it
400 /// succeeds or false if it fails. The number is a private implementation
401 /// detail to the code tblgen produces.
402 virtual bool CheckPatternPredicate(unsigned PredNo) const {
403 llvm_unreachable("Tblgen should generate the implementation of this!");
404 }
405
406 /// CheckNodePredicate - This function is generated by tblgen in the target.
407 /// It runs node predicate number PredNo and returns true if it succeeds or
408 /// false if it fails. The number is a private implementation
409 /// detail to the code tblgen produces.
410 virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
411 llvm_unreachable("Tblgen should generate the implementation of this!");
412 }
413
414 /// CheckNodePredicateWithOperands - This function is generated by tblgen in
415 /// the target.
416 /// It runs node predicate number PredNo and returns true if it succeeds or
417 /// false if it fails. The number is a private implementation detail to the
418 /// code tblgen produces.
419 virtual bool CheckNodePredicateWithOperands(
420 SDNode *N, unsigned PredNo,
421 const SmallVectorImpl<SDValue> &Operands) const {
422 llvm_unreachable("Tblgen should generate the implementation of this!");
423 }
424
425 virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
426 unsigned PatternNo,
427 SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
428 llvm_unreachable("Tblgen should generate the implementation of this!");
429 }
430
431 virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
432 llvm_unreachable("Tblgen should generate this!");
433 }
434
435 void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
436 unsigned TableSize);
437
438 /// Return true if complex patterns for this target can mutate the
439 /// DAG.
440 virtual bool ComplexPatternFuncMutatesDAG() const {
441 return false;
442 }
443
444 /// Return whether the node may raise an FP exception.
445 bool mayRaiseFPException(SDNode *Node) const;
446
447 bool isOrEquivalentToAdd(const SDNode *N) const;
448
449private:
450
451 // Calls to these functions are generated by tblgen.
452 void Select_INLINEASM(SDNode *N);
453 void Select_READ_REGISTER(SDNode *Op);
454 void Select_WRITE_REGISTER(SDNode *Op);
455 void Select_UNDEF(SDNode *N);
456 void CannotYetSelect(SDNode *N);
457
458 void Select_FREEZE(SDNode *N);
459 void Select_ARITH_FENCE(SDNode *N);
460 void Select_MEMBARRIER(SDNode *N);
461
462 void pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops, SDValue Operand,
463 SDLoc DL);
464 void Select_STACKMAP(SDNode *N);
465 void Select_PATCHPOINT(SDNode *N);
466
467 void Select_JUMP_TABLE_DEBUG_INFO(SDNode *N);
468
469private:
470 void DoInstructionSelection();
471 SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
472 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
473
474 /// Prepares the landing pad to take incoming values or do other EH
475 /// personality specific tasks. Returns true if the block should be
476 /// instruction selected, false if no code should be emitted for it.
477 bool PrepareEHLandingPad();
478
479 // Mark and Report IPToState for each Block under AsynchEH
480 void reportIPToStateForBlocks(MachineFunction *Fn);
481
482 /// Perform instruction selection on all basic blocks in the function.
483 void SelectAllBasicBlocks(const Function &Fn);
484
485 /// Perform instruction selection on a single basic block, for
486 /// instructions between \p Begin and \p End. \p HadTailCall will be set
487 /// to true if a call in the block was translated as a tail call.
488 void SelectBasicBlock(BasicBlock::const_iterator Begin,
489 BasicBlock::const_iterator End,
490 bool &HadTailCall);
491 void FinishBasicBlock();
492
493 void CodeGenAndEmitDAG();
494
495 /// Generate instructions for lowering the incoming arguments of the
496 /// given function.
497 void LowerArguments(const Function &F);
498
499 void ComputeLiveOutVRegInfo();
500
501 /// Create the scheduler. If a specific scheduler was specified
502 /// via the SchedulerRegistry, use it, otherwise select the
503 /// one preferred by the target.
504 ///
505 ScheduleDAGSDNodes *CreateScheduler();
506
507 /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
508 /// state machines that start with a OPC_SwitchOpcode node.
509 std::vector<unsigned> OpcodeOffset;
510
511 void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
512 SmallVectorImpl<SDNode *> &ChainNodesMatched,
513 bool isMorphNodeTo);
514};
515
516}
517
518#endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
519

source code of llvm/include/llvm/CodeGen/SelectionDAGISel.h