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 case Libcall:
106 break;
107 default:
108 return Q.Types[Mutation.first] != Mutation.second;
109 }
110 return true;
111}
112
113// Make sure the returned mutation makes sense for the match type.
114static bool mutationIsSane(const LegalizeRule &Rule,
115 const LegalityQuery &Q,
116 std::pair<unsigned, LLT> Mutation) {
117 // If the user wants a custom mutation, then we can't really say much about
118 // it. Return true, and trust that they're doing the right thing.
119 if (Rule.getAction() == Custom || Rule.getAction() == Legal)
120 return true;
121
122 // Skip null mutation.
123 if (!Mutation.second.isValid())
124 return true;
125
126 const unsigned TypeIdx = Mutation.first;
127 const LLT OldTy = Q.Types[TypeIdx];
128 const LLT NewTy = Mutation.second;
129
130 switch (Rule.getAction()) {
131 case FewerElements:
132 if (!OldTy.isVector())
133 return false;
134 [[fallthrough]];
135 case MoreElements: {
136 // MoreElements can go from scalar to vector.
137 const ElementCount OldElts = OldTy.isVector() ?
139 if (NewTy.isVector()) {
140 if (Rule.getAction() == FewerElements) {
141 // Make sure the element count really decreased.
142 if (ElementCount::isKnownGE(NewTy.getElementCount(), OldElts))
143 return false;
144 } else {
145 // Make sure the element count really increased.
146 if (ElementCount::isKnownLE(NewTy.getElementCount(), OldElts))
147 return false;
148 }
149 } else if (Rule.getAction() == MoreElements)
150 return false;
151
152 // Make sure the element type didn't change.
153 return NewTy.getScalarType() == OldTy.getScalarType();
154 }
155 case NarrowScalar:
156 case WidenScalar: {
157 if (OldTy.isVector()) {
158 // Number of elements should not change.
159 if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements())
160 return false;
161 } else {
162 // Both types must be vectors
163 if (NewTy.isVector())
164 return false;
165 }
166
167 if (Rule.getAction() == NarrowScalar) {
168 // Make sure the size really decreased.
169 if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
170 return false;
171 } else {
172 // Make sure the size really increased.
173 if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
174 return false;
175 }
176
177 return true;
178 }
179 case Bitcast: {
180 return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
181 }
182 default:
183 return true;
184 }
185}
186#endif
187
189 LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
190 dbgs() << "\n");
191 if (Rules.empty()) {
192 LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
193 return {LegalizeAction::UseLegacyRules, 0, LLT{}};
194 }
195 for (const LegalizeRule &Rule : Rules) {
196 if (Rule.match(Query)) {
197 LLVM_DEBUG(dbgs() << ".. match\n");
198 std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
199 LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
200 << Mutation.first << ", " << Mutation.second << "\n");
201 assert(mutationIsSane(Rule, Query, Mutation) &&
202 "legality mutation invalid for match");
203 assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
204 return {Rule.getAction(), Mutation.first, Mutation.second};
205 } else
206 LLVM_DEBUG(dbgs() << ".. no match\n");
207 }
208 LLVM_DEBUG(dbgs() << ".. unsupported\n");
209 return {LegalizeAction::Unsupported, 0, LLT{}};
210}
211
212bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
213#ifndef NDEBUG
214 if (Rules.empty()) {
216 dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
217 return true;
218 }
219 const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
220 if (FirstUncovered < 0) {
221 LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
222 " user-defined predicate detected\n");
223 return true;
224 }
225 const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
226 if (NumTypeIdxs > 0)
227 LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
228 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
229 return AllCovered;
230#else
231 return true;
232#endif
233}
234
235bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
236#ifndef NDEBUG
237 if (Rules.empty()) {
239 dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
240 return true;
241 }
242 const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
243 if (FirstUncovered < 0) {
244 LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
245 " user-defined predicate detected\n");
246 return true;
247 }
248 const bool AllCovered = (FirstUncovered >= NumImmIdxs);
249 LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
250 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
251 return AllCovered;
252#else
253 return true;
254#endif
255}
256
257/// Helper function to get LLT for the given type index.
259 const MachineRegisterInfo &MRI, unsigned OpIdx,
260 unsigned TypeIdx) {
261 assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
262 // G_UNMERGE_VALUES has variable number of operands, but there is only
263 // one source type and one destination type as all destinations must be the
264 // same type. So, get the last operand if TypeIdx == 1.
265 if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
266 return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
267 return MRI.getType(MI.getOperand(OpIdx).getReg());
268}
269
271 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
272 return Opcode - FirstOp;
273}
274
276 unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
277 if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
278 LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
279 << "\n");
280 OpcodeIdx = getOpcodeIdxForOpcode(Alias);
281 assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
282 }
283
284 return OpcodeIdx;
285}
286
287const LegalizeRuleSet &
289 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
290 return RulesForOpcode[OpcodeIdx];
291}
292
294 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
295 auto &Result = RulesForOpcode[OpcodeIdx];
296 assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
297 return Result;
298}
299
301 std::initializer_list<unsigned> Opcodes) {
302 unsigned Representative = *Opcodes.begin();
303
304 assert(Opcodes.size() >= 2 &&
305 "Initializer list must have at least two opcodes");
306
307 for (unsigned Op : llvm::drop_begin(Opcodes))
308 aliasActionDefinitions(Representative, Op);
309
310 auto &Return = getActionDefinitionsBuilder(Representative);
311 Return.setIsAliasedByAnother();
312 return Return;
313}
314
316 unsigned OpcodeFrom) {
317 assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
318 assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
319 const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
320 RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
321}
322
326 if (Step.Action != LegalizeAction::UseLegacyRules) {
327 return Step;
328 }
329
330 return getLegacyLegalizerInfo().getAction(Query);
331}
332
335 const MachineRegisterInfo &MRI) const {
337 SmallBitVector SeenTypes(8);
338 ArrayRef<MCOperandInfo> OpInfo = MI.getDesc().operands();
339 // FIXME: probably we'll need to cache the results here somehow?
340 for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
341 if (!OpInfo[i].isGenericType())
342 continue;
343
344 // We must only record actions once for each TypeIdx; otherwise we'd
345 // try to legalize operands multiple times down the line.
346 unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
347 if (SeenTypes[TypeIdx])
348 continue;
349
350 SeenTypes.set(TypeIdx);
351
352 LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
353 Types.push_back(Ty);
354 }
355
357 for (const auto &MMO : MI.memoperands())
358 MemDescrs.push_back({*MMO});
359
360 return getAction({MI.getOpcode(), Types, MemDescrs});
361}
362
364 const MachineRegisterInfo &MRI) const {
365 return getAction(MI, MRI).Action == Legal;
366}
367
369 const MachineRegisterInfo &MRI) const {
370 auto Action = getAction(MI, MRI).Action;
371 // If the action is custom, it may not necessarily modify the instruction,
372 // so we have to assume it's legal.
373 return Action == Legal || Action == Custom;
374}
375
377 return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
378}
379
380/// \pre Type indices of every opcode form a dense set starting from 0.
381void LegalizerInfo::verify(const MCInstrInfo &MII) const {
382#ifndef NDEBUG
383 std::vector<unsigned> FailedOpcodes;
384 for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
385 const MCInstrDesc &MCID = MII.get(Opcode);
386 const unsigned NumTypeIdxs = std::accumulate(
387 MCID.operands().begin(), MCID.operands().end(), 0U,
388 [](unsigned Acc, const MCOperandInfo &OpInfo) {
389 return OpInfo.isGenericType()
390 ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
391 : Acc;
392 });
393 const unsigned NumImmIdxs = std::accumulate(
394 MCID.operands().begin(), MCID.operands().end(), 0U,
395 [](unsigned Acc, const MCOperandInfo &OpInfo) {
396 return OpInfo.isGenericImm()
397 ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
398 : Acc;
399 });
400 LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
401 << "): " << NumTypeIdxs << " type ind"
402 << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
403 << NumImmIdxs << " imm ind"
404 << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
406 if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
407 FailedOpcodes.push_back(Opcode);
408 else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
409 FailedOpcodes.push_back(Opcode);
410 }
411 if (!FailedOpcodes.empty()) {
412 errs() << "The following opcodes have ill-defined legalization rules:";
413 for (unsigned Opcode : FailedOpcodes)
414 errs() << " " << MII.getName(Opcode);
415 errs() << "\n";
416
417 report_fatal_error("ill-defined LegalizerInfo"
418 ", try -debug-only=legalizer-info for details");
419 }
420#endif
421}
422
423#ifndef NDEBUG
424// FIXME: This should be in the MachineVerifier, but it can't use the
425// LegalizerInfo as it's currently in the separate GlobalISel library.
426// Note that RegBankSelected property already checked in the verifier
427// has the same layering problem, but we only use inline methods so
428// end up not needing to link against the GlobalISel library.
430 if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
431 const MachineRegisterInfo &MRI = MF.getRegInfo();
432 for (const MachineBasicBlock &MBB : MF)
433 for (const MachineInstr &MI : MBB)
434 if (isPreISelGenericOpcode(MI.getOpcode()) &&
435 !MLI->isLegalOrCustom(MI, MRI))
436 return &MI;
437 }
438 return nullptr;
439}
440#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.
static constexpr uint32_t Opcode
Definition: aarch32.h:200
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:297
constexpr unsigned getScalarSizeInBits() const
Definition: LowLevelType.h:257
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:253
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelType.h:183
constexpr ElementCount getElementCount() const
Definition: LowLevelType.h:174
constexpr LLT getScalarType() const
Definition: LowLevelType.h:198
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:218
static constexpr bool isKnownGE(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
Definition: TypeSize.h:225
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:329
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.