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
14#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
15#include "llvm/ADT/SmallBitVector.h"
16#include "llvm/CodeGen/MachineInstr.h"
17#include "llvm/CodeGen/MachineOperand.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
19#include "llvm/CodeGen/TargetOpcodes.h"
20#include "llvm/CodeGenTypes/LowLevelType.h"
21#include "llvm/MC/MCInstrDesc.h"
22#include "llvm/MC/MCInstrInfo.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/ErrorHandling.h"
25#include <algorithm>
26
27using namespace llvm;
28using namespace LegalizeActions;
29
30#define DEBUG_TYPE "legalizer-info"
31
32cl::opt<bool> llvm::DisableGISelLegalityCheck(
33 "disable-gisel-legality-check",
34 cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
35 cl::Hidden);
36
37cl::opt<bool> VerboseVerifyLegalizerInfo(
38 "verbose-gisel-verify-legalizer-info",
39 cl::desc("Print more information to dbgs about GlobalISel legalizer rules "
40 "being verified"),
41 cl::Hidden);
42
43raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) {
44 switch (Action) {
45 case Legal:
46 OS << "Legal";
47 break;
48 case NarrowScalar:
49 OS << "NarrowScalar";
50 break;
51 case WidenScalar:
52 OS << "WidenScalar";
53 break;
54 case FewerElements:
55 OS << "FewerElements";
56 break;
57 case MoreElements:
58 OS << "MoreElements";
59 break;
60 case Bitcast:
61 OS << "Bitcast";
62 break;
63 case Lower:
64 OS << "Lower";
65 break;
66 case Libcall:
67 OS << "Libcall";
68 break;
69 case Custom:
70 OS << "Custom";
71 break;
72 case Unsupported:
73 OS << "Unsupported";
74 break;
75 case NotFound:
76 OS << "NotFound";
77 break;
78 case UseLegacyRules:
79 OS << "UseLegacyRules";
80 break;
81 }
82 return OS;
83}
84
85raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
86 OS << "Opcode=" << Opcode << ", Tys={";
87 for (const auto &Type : Types) {
88 OS << Type << ", ";
89 }
90 OS << "}, MMOs={";
91 for (const auto &MMODescr : MMODescrs) {
92 OS << MMODescr.MemoryTy << ", ";
93 }
94 OS << "}";
95
96 return OS;
97}
98
99#ifndef NDEBUG
100// Make sure the rule won't (trivially) loop forever.
101static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
102 const std::pair<unsigned, LLT> &Mutation) {
103 switch (Rule.getAction()) {
104 case Legal:
105 case Custom:
106 case Lower:
107 case MoreElements:
108 case FewerElements:
109 case Libcall:
110 break;
111 default:
112 return Q.Types[Mutation.first] != Mutation.second;
113 }
114 return true;
115}
116
117// Make sure the returned mutation makes sense for the match type.
118static bool mutationIsSane(const LegalizeRule &Rule,
119 const LegalityQuery &Q,
120 std::pair<unsigned, LLT> Mutation) {
121 // If the user wants a custom mutation, then we can't really say much about
122 // it. Return true, and trust that they're doing the right thing.
123 if (Rule.getAction() == Custom || Rule.getAction() == Legal)
124 return true;
125
126 // Skip null mutation.
127 if (!Mutation.second.isValid())
128 return true;
129
130 const unsigned TypeIdx = Mutation.first;
131 const LLT OldTy = Q.Types[TypeIdx];
132 const LLT NewTy = Mutation.second;
133
134 switch (Rule.getAction()) {
135 case FewerElements:
136 if (!OldTy.isVector())
137 return false;
138 [[fallthrough]];
139 case MoreElements: {
140 // MoreElements can go from scalar to vector.
141 const ElementCount OldElts = OldTy.isVector() ?
142 OldTy.getElementCount() : ElementCount::getFixed(1);
143 if (NewTy.isVector()) {
144 if (Rule.getAction() == FewerElements) {
145 // Make sure the element count really decreased.
146 if (ElementCount::isKnownGE(NewTy.getElementCount(), OldElts))
147 return false;
148 } else {
149 // Make sure the element count really increased.
150 if (ElementCount::isKnownLE(NewTy.getElementCount(), OldElts))
151 return false;
152 }
153 } else if (Rule.getAction() == MoreElements)
154 return false;
155
156 // Make sure the element type didn't change.
157 return NewTy.getScalarType() == OldTy.getScalarType();
158 }
159 case NarrowScalar:
160 case WidenScalar: {
161 if (OldTy.isVector()) {
162 // Number of elements should not change.
163 if (!NewTy.isVector() ||
164 OldTy.getElementCount() != NewTy.getElementCount())
165 return false;
166 } else {
167 // Both types must be vectors
168 if (NewTy.isVector())
169 return false;
170 }
171
172 if (Rule.getAction() == NarrowScalar) {
173 // Make sure the size really decreased.
174 if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
175 return false;
176 } else {
177 // Make sure the size really increased.
178 if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
179 return false;
180 }
181
182 return true;
183 }
184 case Bitcast: {
185 return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
186 }
187 default:
188 return true;
189 }
190}
191#endif
192
193LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
194 LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
195 dbgs() << "\n");
196 if (Rules.empty()) {
197 LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
198 return {LegalizeAction::UseLegacyRules, 0, LLT{}};
199 }
200 for (const LegalizeRule &Rule : Rules) {
201 if (Rule.match(Query)) {
202 LLVM_DEBUG(dbgs() << ".. match\n");
203 std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
204 LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
205 << Mutation.first << ", " << Mutation.second << "\n");
206 assert(mutationIsSane(Rule, Query, Mutation) &&
207 "legality mutation invalid for match");
208 assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
209 return {Rule.getAction(), Mutation.first, Mutation.second};
210 } else
211 LLVM_DEBUG(dbgs() << ".. no match\n");
212 }
213 LLVM_DEBUG(dbgs() << ".. unsupported\n");
214 return {LegalizeAction::Unsupported, 0, LLT{}};
215}
216
217bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
218#ifndef NDEBUG
219 if (Rules.empty()) {
220 if (VerboseVerifyLegalizerInfo) {
221 LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED: "
222 << "no rules defined\n");
223 }
224 return true;
225 }
226 const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
227 if (FirstUncovered < 0) {
228 if (VerboseVerifyLegalizerInfo) {
229 LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
230 " user-defined predicate detected\n");
231 }
232 return true;
233 }
234 const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
235 if (NumTypeIdxs > 0) {
236 if (VerboseVerifyLegalizerInfo) {
237 LLVM_DEBUG(dbgs() << ".. the first uncovered type index: "
238 << FirstUncovered << ", "
239 << (AllCovered ? "OK" : "FAIL") << "\n");
240 }
241 }
242 return AllCovered;
243#else
244 return true;
245#endif
246}
247
248bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
249#ifndef NDEBUG
250 if (Rules.empty()) {
251 if (VerboseVerifyLegalizerInfo) {
252 LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED: "
253 << "no rules defined\n");
254 }
255 return true;
256 }
257 const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
258 if (FirstUncovered < 0) {
259 if (VerboseVerifyLegalizerInfo) {
260 LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
261 " user-defined predicate detected\n");
262 }
263 return true;
264 }
265 const bool AllCovered = (FirstUncovered >= NumImmIdxs);
266 if (VerboseVerifyLegalizerInfo) {
267 LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
268 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
269 }
270 return AllCovered;
271#else
272 return true;
273#endif
274}
275
276/// Helper function to get LLT for the given type index.
277static LLT getTypeFromTypeIdx(const MachineInstr &MI,
278 const MachineRegisterInfo &MRI, unsigned OpIdx,
279 unsigned TypeIdx) {
280 assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
281 // G_UNMERGE_VALUES has variable number of operands, but there is only
282 // one source type and one destination type as all destinations must be the
283 // same type. So, get the last operand if TypeIdx == 1.
284 if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
285 return MRI.getType(Reg: MI.getOperand(i: MI.getNumOperands() - 1).getReg());
286 return MRI.getType(Reg: MI.getOperand(i: OpIdx).getReg());
287}
288
289unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
290 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
291 return Opcode - FirstOp;
292}
293
294unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
295 unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
296 if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
297 if (VerboseVerifyLegalizerInfo) {
298 LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
299 << "\n");
300 }
301 OpcodeIdx = getOpcodeIdxForOpcode(Opcode: Alias);
302 assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
303 }
304
305 return OpcodeIdx;
306}
307
308const LegalizeRuleSet &
309LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
310 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
311 return RulesForOpcode[OpcodeIdx];
312}
313
314LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
315 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
316 auto &Result = RulesForOpcode[OpcodeIdx];
317 assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
318 return Result;
319}
320
321LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
322 std::initializer_list<unsigned> Opcodes) {
323 unsigned Representative = *Opcodes.begin();
324
325 assert(Opcodes.size() >= 2 &&
326 "Initializer list must have at least two opcodes");
327
328 for (unsigned Op : llvm::drop_begin(RangeOrContainer&: Opcodes))
329 aliasActionDefinitions(OpcodeTo: Representative, OpcodeFrom: Op);
330
331 auto &Return = getActionDefinitionsBuilder(Opcode: Representative);
332 Return.setIsAliasedByAnother();
333 return Return;
334}
335
336void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
337 unsigned OpcodeFrom) {
338 assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
339 assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
340 const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(Opcode: OpcodeFrom);
341 RulesForOpcode[OpcodeFromIdx].aliasTo(Opcode: OpcodeTo);
342}
343
344LegalizeActionStep
345LegalizerInfo::getAction(const LegalityQuery &Query) const {
346 LegalizeActionStep Step = getActionDefinitions(Opcode: Query.Opcode).apply(Query);
347 if (Step.Action != LegalizeAction::UseLegacyRules) {
348 return Step;
349 }
350
351 return getLegacyLegalizerInfo().getAction(Query);
352}
353
354LegalizeActionStep
355LegalizerInfo::getAction(const MachineInstr &MI,
356 const MachineRegisterInfo &MRI) const {
357 SmallVector<LLT, 8> Types;
358 SmallBitVector SeenTypes(8);
359 ArrayRef<MCOperandInfo> OpInfo = MI.getDesc().operands();
360 // FIXME: probably we'll need to cache the results here somehow?
361 for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
362 if (!OpInfo[i].isGenericType())
363 continue;
364
365 // We must only record actions once for each TypeIdx; otherwise we'd
366 // try to legalize operands multiple times down the line.
367 unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
368 if (SeenTypes[TypeIdx])
369 continue;
370
371 SeenTypes.set(TypeIdx);
372
373 LLT Ty = getTypeFromTypeIdx(MI, MRI, OpIdx: i, TypeIdx);
374 Types.push_back(Elt: Ty);
375 }
376
377 SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
378 for (const auto &MMO : MI.memoperands())
379 MemDescrs.push_back(Elt: {*MMO});
380
381 return getAction(Query: {MI.getOpcode(), Types, MemDescrs});
382}
383
384bool LegalizerInfo::isLegal(const MachineInstr &MI,
385 const MachineRegisterInfo &MRI) const {
386 return getAction(MI, MRI).Action == Legal;
387}
388
389bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI,
390 const MachineRegisterInfo &MRI) const {
391 auto Action = getAction(MI, MRI).Action;
392 // If the action is custom, it may not necessarily modify the instruction,
393 // so we have to assume it's legal.
394 return Action == Legal || Action == Custom;
395}
396
397unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const {
398 return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
399}
400
401/// \pre Type indices of every opcode form a dense set starting from 0.
402void LegalizerInfo::verify(const MCInstrInfo &MII) const {
403#ifndef NDEBUG
404 std::vector<unsigned> FailedOpcodes;
405 for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
406 const MCInstrDesc &MCID = MII.get(Opcode);
407 const unsigned NumTypeIdxs = std::accumulate(
408 MCID.operands().begin(), MCID.operands().end(), 0U,
409 [](unsigned Acc, const MCOperandInfo &OpInfo) {
410 return OpInfo.isGenericType()
411 ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
412 : Acc;
413 });
414 const unsigned NumImmIdxs = std::accumulate(
415 MCID.operands().begin(), MCID.operands().end(), 0U,
416 [](unsigned Acc, const MCOperandInfo &OpInfo) {
417 return OpInfo.isGenericImm()
418 ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
419 : Acc;
420 });
421 if (VerboseVerifyLegalizerInfo) {
422 LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
423 << "): " << NumTypeIdxs << " type ind"
424 << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
425 << NumImmIdxs << " imm ind"
426 << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
427 }
428 const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
429 if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
430 FailedOpcodes.push_back(Opcode);
431 else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
432 FailedOpcodes.push_back(Opcode);
433 }
434 if (!FailedOpcodes.empty()) {
435 errs() << "The following opcodes have ill-defined legalization rules:";
436 for (unsigned Opcode : FailedOpcodes)
437 errs() << " " << MII.getName(Opcode);
438 errs() << "\n";
439
440 report_fatal_error("ill-defined LegalizerInfo, try "
441 "-debug-only=legalizer-info and "
442 "-verbose-gisel-verify-legalizer-info for details");
443 }
444#endif
445}
446
447#ifndef NDEBUG
448// FIXME: This should be in the MachineVerifier, but it can't use the
449// LegalizerInfo as it's currently in the separate GlobalISel library.
450// Note that RegBankSelected property already checked in the verifier
451// has the same layering problem, but we only use inline methods so
452// end up not needing to link against the GlobalISel library.
453const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
454 if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
455 const MachineRegisterInfo &MRI = MF.getRegInfo();
456 for (const MachineBasicBlock &MBB : MF)
457 for (const MachineInstr &MI : MBB)
458 if (isPreISelGenericOpcode(MI.getOpcode()) &&
459 !MLI->isLegalOrCustom(MI, MRI))
460 return &MI;
461 }
462 return nullptr;
463}
464#endif
465