LLVM 18.0.0git
LegalizerInfo.cpp
Go to the documentation of this file.
1//===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
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// Implement an interface to specify and query how an illegal operation on a
10// given type should be expanded.
11//
12//===----------------------------------------------------------------------===//
13
21#include "llvm/MC/MCInstrDesc.h"
22#include "llvm/MC/MCInstrInfo.h"
23#include "llvm/Support/Debug.h"
25#include <algorithm>
26
27using namespace llvm;
28using namespace LegalizeActions;
29
30#define DEBUG_TYPE "legalizer-info"
31
33 "disable-gisel-legality-check",
34 cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
36
38 switch (Action) {
39 case Legal:
40 OS << "Legal";
41 break;
42 case NarrowScalar:
43 OS << "NarrowScalar";
44 break;
45 case WidenScalar:
46 OS << "WidenScalar";
47 break;
48 case FewerElements:
49 OS << "FewerElements";
50 break;
51 case MoreElements:
52 OS << "MoreElements";
53 break;
54 case Bitcast:
55 OS << "Bitcast";
56 break;
57 case Lower:
58 OS << "Lower";
59 break;
60 case Libcall:
61 OS << "Libcall";
62 break;
63 case Custom:
64 OS << "Custom";
65 break;
66 case Unsupported:
67 OS << "Unsupported";
68 break;
69 case NotFound:
70 OS << "NotFound";
71 break;
72 case UseLegacyRules:
73 OS << "UseLegacyRules";
74 break;
75 }
76 return OS;
77}
78
80 OS << Opcode << ", Tys={";
81 for (const auto &Type : Types) {
82 OS << Type << ", ";
83 }
84 OS << "}, Opcode=";
85
86 OS << Opcode << ", MMOs={";
87 for (const auto &MMODescr : MMODescrs) {
88 OS << MMODescr.MemoryTy << ", ";
89 }
90 OS << "}";
91
92 return OS;
93}
94
95#ifndef NDEBUG
96// Make sure the rule won't (trivially) loop forever.
97static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
98 const std::pair<unsigned, LLT> &Mutation) {
99 switch (Rule.getAction()) {
100 case Legal:
101 case Custom:
102 case Lower:
103 case MoreElements:
104 case FewerElements:
105 break;
106 default:
107 return Q.Types[Mutation.first] != Mutation.second;
108 }
109 return true;
110}
111
112// Make sure the returned mutation makes sense for the match type.
113static bool mutationIsSane(const LegalizeRule &Rule,
114 const LegalityQuery &Q,
115 std::pair<unsigned, LLT> Mutation) {
116 // If the user wants a custom mutation, then we can't really say much about
117 // it. Return true, and trust that they're doing the right thing.
118 if (Rule.getAction() == Custom || Rule.getAction() == Legal)
119 return true;
120
121 const unsigned TypeIdx = Mutation.first;
122 const LLT OldTy = Q.Types[TypeIdx];
123 const LLT NewTy = Mutation.second;
124
125 switch (Rule.getAction()) {
126 case FewerElements:
127 if (!OldTy.isVector())
128 return false;
129 [[fallthrough]];
130 case MoreElements: {
131 // MoreElements can go from scalar to vector.
132 const ElementCount OldElts = OldTy.isVector() ?
134 if (NewTy.isVector()) {
135 if (Rule.getAction() == FewerElements) {
136 // Make sure the element count really decreased.
137 if (ElementCount::isKnownGE(NewTy.getElementCount(), OldElts))
138 return false;
139 } else {
140 // Make sure the element count really increased.
141 if (ElementCount::isKnownLE(NewTy.getElementCount(), OldElts))
142 return false;
143 }
144 } else if (Rule.getAction() == MoreElements)
145 return false;
146
147 // Make sure the element type didn't change.
148 return NewTy.getScalarType() == OldTy.getScalarType();
149 }
150 case NarrowScalar:
151 case WidenScalar: {
152 if (OldTy.isVector()) {
153 // Number of elements should not change.
154 if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements())
155 return false;
156 } else {
157 // Both types must be vectors
158 if (NewTy.isVector())
159 return false;
160 }
161
162 if (Rule.getAction() == NarrowScalar) {
163 // Make sure the size really decreased.
164 if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
165 return false;
166 } else {
167 // Make sure the size really increased.
168 if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
169 return false;
170 }
171
172 return true;
173 }
174 case Bitcast: {
175 return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
176 }
177 default:
178 return true;
179 }
180}
181#endif
182
184 LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
185 dbgs() << "\n");
186 if (Rules.empty()) {
187 LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
188 return {LegalizeAction::UseLegacyRules, 0, LLT{}};
189 }
190 for (const LegalizeRule &Rule : Rules) {
191 if (Rule.match(Query)) {
192 LLVM_DEBUG(dbgs() << ".. match\n");
193 std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
194 LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
195 << Mutation.first << ", " << Mutation.second << "\n");
196 assert(mutationIsSane(Rule, Query, Mutation) &&
197 "legality mutation invalid for match");
198 assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
199 return {Rule.getAction(), Mutation.first, Mutation.second};
200 } else
201 LLVM_DEBUG(dbgs() << ".. no match\n");
202 }
203 LLVM_DEBUG(dbgs() << ".. unsupported\n");
204 return {LegalizeAction::Unsupported, 0, LLT{}};
205}
206
207bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
208#ifndef NDEBUG
209 if (Rules.empty()) {
211 dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
212 return true;
213 }
214 const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
215 if (FirstUncovered < 0) {
216 LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
217 " user-defined predicate detected\n");
218 return true;
219 }
220 const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
221 if (NumTypeIdxs > 0)
222 LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
223 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
224 return AllCovered;
225#else
226 return true;
227#endif
228}
229
230bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
231#ifndef NDEBUG
232 if (Rules.empty()) {
234 dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
235 return true;
236 }
237 const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
238 if (FirstUncovered < 0) {
239 LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
240 " user-defined predicate detected\n");
241 return true;
242 }
243 const bool AllCovered = (FirstUncovered >= NumImmIdxs);
244 LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
245 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
246 return AllCovered;
247#else
248 return true;
249#endif
250}
251
252/// Helper function to get LLT for the given type index.
254 const MachineRegisterInfo &MRI, unsigned OpIdx,
255 unsigned TypeIdx) {
256 assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
257 // G_UNMERGE_VALUES has variable number of operands, but there is only
258 // one source type and one destination type as all destinations must be the
259 // same type. So, get the last operand if TypeIdx == 1.
260 if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
261 return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
262 return MRI.getType(MI.getOperand(OpIdx).getReg());
263}
264
265unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
266 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
267 return Opcode - FirstOp;
268}
269
270unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
271 unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
272 if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
273 LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
274 << "\n");
275 OpcodeIdx = getOpcodeIdxForOpcode(Alias);
276 assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
277 }
278
279 return OpcodeIdx;
280}
281
282const LegalizeRuleSet &
284 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
285 return RulesForOpcode[OpcodeIdx];
286}
287
289 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
290 auto &Result = RulesForOpcode[OpcodeIdx];
291 assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
292 return Result;
293}
294
296 std::initializer_list<unsigned> Opcodes) {
297 unsigned Representative = *Opcodes.begin();
298
299 assert(Opcodes.size() >= 2 &&
300 "Initializer list must have at least two opcodes");
301
302 for (unsigned Op : llvm::drop_begin(Opcodes))
303 aliasActionDefinitions(Representative, Op);
304
305 auto &Return = getActionDefinitionsBuilder(Representative);
306 Return.setIsAliasedByAnother();
307 return Return;
308}
309
311 unsigned OpcodeFrom) {
312 assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
313 assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
314 const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
315 RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
316}
317
321 if (Step.Action != LegalizeAction::UseLegacyRules) {
322 return Step;
323 }
324
325 return getLegacyLegalizerInfo().getAction(Query);
326}
327
330 const MachineRegisterInfo &MRI) const {
332 SmallBitVector SeenTypes(8);
333 ArrayRef<MCOperandInfo> OpInfo = MI.getDesc().operands();
334 // FIXME: probably we'll need to cache the results here somehow?
335 for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
336 if (!OpInfo[i].isGenericType())
337 continue;
338
339 // We must only record actions once for each TypeIdx; otherwise we'd
340 // try to legalize operands multiple times down the line.
341 unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
342 if (SeenTypes[TypeIdx])
343 continue;
344
345 SeenTypes.set(TypeIdx);
346
347 LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
348 Types.push_back(Ty);
349 }
350
352 for (const auto &MMO : MI.memoperands())
353 MemDescrs.push_back({*MMO});
354
355 return getAction({MI.getOpcode(), Types, MemDescrs});
356}
357
359 const MachineRegisterInfo &MRI) const {
360 return getAction(MI, MRI).Action == Legal;
361}
362
364 const MachineRegisterInfo &MRI) const {
365 auto Action = getAction(MI, MRI).Action;
366 // If the action is custom, it may not necessarily modify the instruction,
367 // so we have to assume it's legal.
368 return Action == Legal || Action == Custom;
369}
370
372 return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
373}
374
375/// \pre Type indices of every opcode form a dense set starting from 0.
376void LegalizerInfo::verify(const MCInstrInfo &MII) const {
377#ifndef NDEBUG
378 std::vector<unsigned> FailedOpcodes;
379 for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
380 const MCInstrDesc &MCID = MII.get(Opcode);
381 const unsigned NumTypeIdxs = std::accumulate(
382 MCID.operands().begin(), MCID.operands().end(), 0U,
383 [](unsigned Acc, const MCOperandInfo &OpInfo) {
384 return OpInfo.isGenericType()
385 ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
386 : Acc;
387 });
388 const unsigned NumImmIdxs = std::accumulate(
389 MCID.operands().begin(), MCID.operands().end(), 0U,
390 [](unsigned Acc, const MCOperandInfo &OpInfo) {
391 return OpInfo.isGenericImm()
392 ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
393 : Acc;
394 });
395 LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
396 << "): " << NumTypeIdxs << " type ind"
397 << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
398 << NumImmIdxs << " imm ind"
399 << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
400 const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
401 if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
402 FailedOpcodes.push_back(Opcode);
403 else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
404 FailedOpcodes.push_back(Opcode);
405 }
406 if (!FailedOpcodes.empty()) {
407 errs() << "The following opcodes have ill-defined legalization rules:";
408 for (unsigned Opcode : FailedOpcodes)
409 errs() << " " << MII.getName(Opcode);
410 errs() << "\n";
411
412 report_fatal_error("ill-defined LegalizerInfo"
413 ", try -debug-only=legalizer-info for details");
414 }
415#endif
416}
417
418#ifndef NDEBUG
419// FIXME: This should be in the MachineVerifier, but it can't use the
420// LegalizerInfo as it's currently in the separate GlobalISel library.
421// Note that RegBankSelected property already checked in the verifier
422// has the same layering problem, but we only use inline methods so
423// end up not needing to link against the GlobalISel library.
425 if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
426 const MachineRegisterInfo &MRI = MF.getRegInfo();
427 for (const MachineBasicBlock &MBB : MF)
428 for (const MachineInstr &MI : MBB)
429 if (isPreISelGenericOpcode(MI.getOpcode()) &&
430 !MLI->isLegalOrCustom(MI, MRI))
431 return &MI;
432 }
433 return nullptr;
434}
435#endif
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
#define LLVM_DEBUG(X)
Definition: Debug.h:101
IRTranslator LLVM IR MI
static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q, const std::pair< unsigned, LLT > &Mutation)
static LLT getTypeFromTypeIdx(const MachineInstr &MI, const MachineRegisterInfo &MRI, unsigned OpIdx, unsigned TypeIdx)
Helper function to get LLT for the given type index.
static bool mutationIsSane(const LegalizeRule &Rule, const LegalityQuery &Q, std::pair< unsigned, LLT > Mutation)
Interface for Targets to specify which operations they can successfully select and how the others sho...
Implement a low-level type suitable for MachineInstr level instruction selection.
PowerPC VSX FMA Mutation
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file implements the SmallBitVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
This class represents an Operation in the Expression.
static constexpr ElementCount getFixed(ScalarTy MinVal)
Definition: TypeSize.h:291
constexpr unsigned getScalarSizeInBits() const
Definition: LowLevelType.h:249
constexpr uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
Definition: LowLevelType.h:149
constexpr bool isVector() const
Definition: LowLevelType.h:145
constexpr bool isByteSized() const
Definition: LowLevelType.h:245
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelType.h:175
constexpr ElementCount getElementCount() const
Definition: LowLevelType.h:166
constexpr LLT getScalarType() const
Definition: LowLevelType.h:190
LegacyLegalizeActionStep getAction(const LegalityQuery &Query) const
void aliasTo(unsigned Opcode)
bool verifyImmIdxsCoverage(unsigned NumImmIdxs) const
Check if there is no imm index which is obviously not handled by the LegalizeRuleSet in any way at al...
bool verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const
Check if there is no type index which is obviously not handled by the LegalizeRuleSet in any way at a...
LegalizeActionStep apply(const LegalityQuery &Query) const
Apply the ruleset to the given LegalityQuery.
A single rule in a legalizer info ruleset.
LegalizeAction getAction() const
const LegalizeRuleSet & getActionDefinitions(unsigned Opcode) const
Get the action definitions for the given opcode.
LegalizeRuleSet & getActionDefinitionsBuilder(unsigned Opcode)
Get the action definition builder for the given opcode.
const LegacyLegalizerInfo & getLegacyLegalizerInfo() const
virtual unsigned getExtOpcodeForWideningConstant(LLT SmallTy) const
Return the opcode (SEXT/ZEXT/ANYEXT) that should be performed while widening a constant of type Small...
bool isLegalOrCustom(const LegalityQuery &Query) const
void aliasActionDefinitions(unsigned OpcodeTo, unsigned OpcodeFrom)
void verify(const MCInstrInfo &MII) const
Perform simple self-diagnostic and assert if there is anything obviously wrong with the actions set u...
unsigned getOpcodeIdxForOpcode(unsigned Opcode) const
bool isLegal(const LegalityQuery &Query) const
unsigned getActionDefinitionsIdx(unsigned Opcode) const
LegalizeActionStep getAction(const LegalityQuery &Query) const
Determine what action should be taken to legalize the described instruction.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
ArrayRef< MCOperandInfo > operands() const
Definition: MCInstrDesc.h:239
Interface to description of machine instruction set.
Definition: MCInstrInfo.h:26
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Definition: MCInstrInfo.h:63
StringRef getName(unsigned Opcode) const
Returns the name for the instructions with the given opcode.
Definition: MCInstrInfo.h:70
This holds information about one operand of a machine instruction, indicating the register class for ...
Definition: MCInstrDesc.h:85
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
Definition: MachineInstr.h:68
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
SmallBitVector & set()
int find_first_unset() const
Returns the index of the first unset bit, -1 if all of the bits are set.
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
virtual const LegalizerInfo * getLegalizerInfo() const
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static constexpr bool isKnownLE(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
Definition: TypeSize.h:212
static constexpr bool isKnownGE(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
Definition: TypeSize.h:219
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ FewerElements
The (vector) operation should be implemented by splitting it into sub-vectors where the operation is ...
Definition: LegalizerInfo.h:64
@ Libcall
The operation should be implemented as a call to some kind of runtime support library.
Definition: LegalizerInfo.h:82
@ Unsupported
This operation is completely unsupported on the target.
Definition: LegalizerInfo.h:90
@ Lower
The operation itself must be expressed in terms of simpler actions on this target.
Definition: LegalizerInfo.h:77
@ UseLegacyRules
Fall back onto the old rules.
Definition: LegalizerInfo.h:97
@ WidenScalar
The operation should be implemented in terms of a wider scalar base-type.
Definition: LegalizerInfo.h:56
@ Bitcast
Perform the operation on a different, but equivalently sized type.
Definition: LegalizerInfo.h:73
@ NarrowScalar
The operation should be synthesized from multiple instructions acting on a narrower scalar base-type.
Definition: LegalizerInfo.h:51
@ Custom
The target wants to do something special with this combination of operand and type.
Definition: LegalizerInfo.h:86
@ NotFound
Sentinel value for when no action was found in the specified table.
Definition: LegalizerInfo.h:93
@ MoreElements
The (vector) operation should be implemented by widening the input vector and ignoring the lanes adde...
Definition: LegalizerInfo.h:70
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:330
bool isPreISelGenericOpcode(unsigned Opcode)
Check whether the given Opcode is a generic opcode that is not supposed to appear after ISel.
Definition: TargetOpcodes.h:30
cl::opt< bool > DisableGISelLegalityCheck
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:156
const MachineInstr * machineFunctionIsIllegal(const MachineFunction &MF)
Checks that MIR is fully legal, returns an illegal instruction if it's not, nullptr otherwise.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
The LegalityQuery object bundles together all the information that's needed to decide whether a given...
ArrayRef< MemDesc > MMODescrs
Operations which require memory can use this to place requirements on the memory type for each MMO.
ArrayRef< LLT > Types
raw_ostream & print(raw_ostream &OS) const
The result of a query.
LegalizeAction Action
The action to take or the final answer.