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