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