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 | |
27 | using namespace llvm; |
28 | using namespace LegalizeActions; |
29 | |
30 | #define DEBUG_TYPE "legalizer-info" |
31 | |
32 | cl::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 | |
37 | raw_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 | |
79 | raw_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. |
95 | static 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. |
112 | static 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 | |
186 | LegalizeActionStep 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 | |
210 | bool 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 | |
233 | bool 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. |
256 | static 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 | |
268 | unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const { |
269 | assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode" ); |
270 | return Opcode - FirstOp; |
271 | } |
272 | |
273 | unsigned 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 | |
285 | const LegalizeRuleSet & |
286 | LegalizerInfo::getActionDefinitions(unsigned Opcode) const { |
287 | unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode); |
288 | return RulesForOpcode[OpcodeIdx]; |
289 | } |
290 | |
291 | LegalizeRuleSet &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 | |
298 | LegalizeRuleSet &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 | |
313 | void 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 | |
321 | LegalizeActionStep |
322 | LegalizerInfo::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 | |
331 | LegalizeActionStep |
332 | LegalizerInfo::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 | |
361 | bool LegalizerInfo::isLegal(const MachineInstr &MI, |
362 | const MachineRegisterInfo &MRI) const { |
363 | return getAction(MI, MRI).Action == Legal; |
364 | } |
365 | |
366 | bool 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 | |
374 | unsigned 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. |
379 | void 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. |
427 | const 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 | |