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/GlobalISel/GISelChangeObserver.h"
17 #include "llvm/CodeGen/MachineInstr.h"
18 #include "llvm/CodeGen/MachineOperand.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/CodeGen/TargetOpcodes.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 "llvm/Support/LowLevelTypeImpl.h"
26 #include "llvm/Support/MathExtras.h"
27 #include <algorithm>
28 #include <map>
29
30 using namespace llvm;
31 using namespace LegalizeActions;
32
33 #define DEBUG_TYPE "legalizer-info"
34
35 cl::opt<bool> llvm::DisableGISelLegalityCheck(
36 "disable-gisel-legality-check",
37 cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
38 cl::Hidden);
39
operator <<(raw_ostream & OS,LegalizeAction Action)40 raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) {
41 switch (Action) {
42 case Legal:
43 OS << "Legal";
44 break;
45 case NarrowScalar:
46 OS << "NarrowScalar";
47 break;
48 case WidenScalar:
49 OS << "WidenScalar";
50 break;
51 case FewerElements:
52 OS << "FewerElements";
53 break;
54 case MoreElements:
55 OS << "MoreElements";
56 break;
57 case Bitcast:
58 OS << "Bitcast";
59 break;
60 case Lower:
61 OS << "Lower";
62 break;
63 case Libcall:
64 OS << "Libcall";
65 break;
66 case Custom:
67 OS << "Custom";
68 break;
69 case Unsupported:
70 OS << "Unsupported";
71 break;
72 case NotFound:
73 OS << "NotFound";
74 break;
75 case UseLegacyRules:
76 OS << "UseLegacyRules";
77 break;
78 }
79 return OS;
80 }
81
print(raw_ostream & OS) const82 raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
83 OS << Opcode << ", Tys={";
84 for (const auto &Type : Types) {
85 OS << Type << ", ";
86 }
87 OS << "}, Opcode=";
88
89 OS << Opcode << ", MMOs={";
90 for (const auto &MMODescr : MMODescrs) {
91 OS << MMODescr.MemoryTy << ", ";
92 }
93 OS << "}";
94
95 return OS;
96 }
97
98 #ifndef NDEBUG
99 // Make sure the rule won't (trivially) loop forever.
hasNoSimpleLoops(const LegalizeRule & Rule,const LegalityQuery & Q,const std::pair<unsigned,LLT> & Mutation)100 static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
101 const std::pair<unsigned, LLT> &Mutation) {
102 switch (Rule.getAction()) {
103 case Legal:
104 case Custom:
105 case Lower:
106 case MoreElements:
107 case FewerElements:
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.
mutationIsSane(const LegalizeRule & Rule,const LegalityQuery & Q,std::pair<unsigned,LLT> Mutation)116 static 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 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 LLVM_FALLTHROUGH;
133 case MoreElements: {
134 // MoreElements can go from scalar to vector.
135 const unsigned OldElts = OldTy.isVector() ? OldTy.getNumElements() : 1;
136 if (NewTy.isVector()) {
137 if (Rule.getAction() == FewerElements) {
138 // Make sure the element count really decreased.
139 if (NewTy.getNumElements() >= OldElts)
140 return false;
141 } else {
142 // Make sure the element count really increased.
143 if (NewTy.getNumElements() <= OldElts)
144 return false;
145 }
146 } else if (Rule.getAction() == MoreElements)
147 return false;
148
149 // Make sure the element type didn't change.
150 return NewTy.getScalarType() == OldTy.getScalarType();
151 }
152 case NarrowScalar:
153 case WidenScalar: {
154 if (OldTy.isVector()) {
155 // Number of elements should not change.
156 if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements())
157 return false;
158 } else {
159 // Both types must be vectors
160 if (NewTy.isVector())
161 return false;
162 }
163
164 if (Rule.getAction() == NarrowScalar) {
165 // Make sure the size really decreased.
166 if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
167 return false;
168 } else {
169 // Make sure the size really increased.
170 if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
171 return false;
172 }
173
174 return true;
175 }
176 case Bitcast: {
177 return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
178 }
179 default:
180 return true;
181 }
182 }
183 #endif
184
apply(const LegalityQuery & Query) const185 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
186 LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
187 dbgs() << "\n");
188 if (Rules.empty()) {
189 LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
190 return {LegalizeAction::UseLegacyRules, 0, LLT{}};
191 }
192 for (const LegalizeRule &Rule : Rules) {
193 if (Rule.match(Query)) {
194 LLVM_DEBUG(dbgs() << ".. match\n");
195 std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
196 LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
197 << Mutation.first << ", " << Mutation.second << "\n");
198 assert(mutationIsSane(Rule, Query, Mutation) &&
199 "legality mutation invalid for match");
200 assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
201 return {Rule.getAction(), Mutation.first, Mutation.second};
202 } else
203 LLVM_DEBUG(dbgs() << ".. no match\n");
204 }
205 LLVM_DEBUG(dbgs() << ".. unsupported\n");
206 return {LegalizeAction::Unsupported, 0, LLT{}};
207 }
208
verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const209 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
210 #ifndef NDEBUG
211 if (Rules.empty()) {
212 LLVM_DEBUG(
213 dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
214 return true;
215 }
216 const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
217 if (FirstUncovered < 0) {
218 LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
219 " user-defined predicate detected\n");
220 return true;
221 }
222 const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
223 if (NumTypeIdxs > 0)
224 LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
225 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
226 return AllCovered;
227 #else
228 return true;
229 #endif
230 }
231
verifyImmIdxsCoverage(unsigned NumImmIdxs) const232 bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
233 #ifndef NDEBUG
234 if (Rules.empty()) {
235 LLVM_DEBUG(
236 dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
237 return true;
238 }
239 const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
240 if (FirstUncovered < 0) {
241 LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
242 " user-defined predicate detected\n");
243 return true;
244 }
245 const bool AllCovered = (FirstUncovered >= NumImmIdxs);
246 LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
247 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
248 return AllCovered;
249 #else
250 return true;
251 #endif
252 }
253
254 /// Helper function to get LLT for the given type index.
getTypeFromTypeIdx(const MachineInstr & MI,const MachineRegisterInfo & MRI,unsigned OpIdx,unsigned TypeIdx)255 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
256 const MachineRegisterInfo &MRI, unsigned OpIdx,
257 unsigned TypeIdx) {
258 assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
259 // G_UNMERGE_VALUES has variable number of operands, but there is only
260 // one source type and one destination type as all destinations must be the
261 // same type. So, get the last operand if TypeIdx == 1.
262 if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
263 return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
264 return MRI.getType(MI.getOperand(OpIdx).getReg());
265 }
266
getOpcodeIdxForOpcode(unsigned Opcode) const267 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
268 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
269 return Opcode - FirstOp;
270 }
271
getActionDefinitionsIdx(unsigned Opcode) const272 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
273 unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
274 if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
275 LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
276 << "\n");
277 OpcodeIdx = getOpcodeIdxForOpcode(Alias);
278 assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
279 }
280
281 return OpcodeIdx;
282 }
283
284 const LegalizeRuleSet &
getActionDefinitions(unsigned Opcode) const285 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
286 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
287 return RulesForOpcode[OpcodeIdx];
288 }
289
getActionDefinitionsBuilder(unsigned Opcode)290 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
291 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
292 auto &Result = RulesForOpcode[OpcodeIdx];
293 assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
294 return Result;
295 }
296
getActionDefinitionsBuilder(std::initializer_list<unsigned> Opcodes)297 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
298 std::initializer_list<unsigned> Opcodes) {
299 unsigned Representative = *Opcodes.begin();
300
301 assert(!llvm::empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
302 "Initializer list must have at least two opcodes");
303
304 for (unsigned Op : llvm::drop_begin(Opcodes))
305 aliasActionDefinitions(Representative, Op);
306
307 auto &Return = getActionDefinitionsBuilder(Representative);
308 Return.setIsAliasedByAnother();
309 return Return;
310 }
311
aliasActionDefinitions(unsigned OpcodeTo,unsigned OpcodeFrom)312 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
313 unsigned OpcodeFrom) {
314 assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
315 assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
316 const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
317 RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
318 }
319
320 LegalizeActionStep
getAction(const LegalityQuery & Query) const321 LegalizerInfo::getAction(const LegalityQuery &Query) const {
322 LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
323 if (Step.Action != LegalizeAction::UseLegacyRules) {
324 return Step;
325 }
326
327 return getLegacyLegalizerInfo().getAction(Query);
328 }
329
330 LegalizeActionStep
getAction(const MachineInstr & MI,const MachineRegisterInfo & MRI) const331 LegalizerInfo::getAction(const MachineInstr &MI,
332 const MachineRegisterInfo &MRI) const {
333 SmallVector<LLT, 8> Types;
334 SmallBitVector SeenTypes(8);
335 const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
336 // FIXME: probably we'll need to cache the results here somehow?
337 for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
338 if (!OpInfo[i].isGenericType())
339 continue;
340
341 // We must only record actions once for each TypeIdx; otherwise we'd
342 // try to legalize operands multiple times down the line.
343 unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
344 if (SeenTypes[TypeIdx])
345 continue;
346
347 SeenTypes.set(TypeIdx);
348
349 LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
350 Types.push_back(Ty);
351 }
352
353 SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
354 for (const auto &MMO : MI.memoperands())
355 MemDescrs.push_back({MMO->getMemoryType(), 8 * MMO->getAlign().value(),
356 MMO->getSuccessOrdering()});
357
358 return getAction({MI.getOpcode(), Types, MemDescrs});
359 }
360
isLegal(const MachineInstr & MI,const MachineRegisterInfo & MRI) const361 bool LegalizerInfo::isLegal(const MachineInstr &MI,
362 const MachineRegisterInfo &MRI) const {
363 return getAction(MI, MRI).Action == Legal;
364 }
365
isLegalOrCustom(const MachineInstr & MI,const MachineRegisterInfo & MRI) const366 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
getExtOpcodeForWideningConstant(LLT SmallTy) const374 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.
verify(const MCInstrInfo & MII) const379 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 MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
386 [](unsigned Acc, const MCOperandInfo &OpInfo) {
387 return OpInfo.isGenericType()
388 ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
389 : Acc;
390 });
391 const unsigned NumImmIdxs = std::accumulate(
392 MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
393 [](unsigned Acc, const MCOperandInfo &OpInfo) {
394 return OpInfo.isGenericImm()
395 ? std::max(OpInfo.getGenericImmIndex() + 1U, 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(Opcode);
406 else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
407 FailedOpcodes.push_back(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("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.
machineFunctionIsIllegal(const MachineFunction & MF)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(MI.getOpcode()) &&
433 !MLI->isLegalOrCustom(MI, MRI))
434 return &MI;
435 }
436 return nullptr;
437 }
438 #endif
439