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