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

source code of llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp