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 | |
22 | namespace llvm { |
23 | class AAResults; |
24 | class AssumptionCache; |
25 | class TargetInstrInfo; |
26 | class TargetMachine; |
27 | class SelectionDAGBuilder; |
28 | class SDValue; |
29 | class MachineRegisterInfo; |
30 | class MachineFunction; |
31 | class ; |
32 | class TargetLowering; |
33 | class TargetLibraryInfo; |
34 | class FunctionLoweringInfo; |
35 | class SwiftErrorValueTracking; |
36 | class GCFunctionInfo; |
37 | class ScheduleDAGSDNodes; |
38 | |
39 | /// SelectionDAGISel - This is the common base class used for SelectionDAG-based |
40 | /// pattern-matching instruction selectors. |
41 | class SelectionDAGISel : public MachineFunctionPass { |
42 | public: |
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 | |
337 | protected: |
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 | |
390 | public: |
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 | |
449 | private: |
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 | |
469 | private: |
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 | |