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 
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 
82 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.
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.
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 
185 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 
209 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 
232 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.
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 
267 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
268   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
269   return Opcode - FirstOp;
270 }
271 
272 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 &
285 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
286   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
287   return RulesForOpcode[OpcodeIdx];
288 }
289 
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 
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 
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
321 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
331 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});
356 
357   return getAction({MI.getOpcode(), Types, MemDescrs});
358 }
359 
360 bool LegalizerInfo::isLegal(const MachineInstr &MI,
361                             const MachineRegisterInfo &MRI) const {
362   return getAction(MI, MRI).Action == Legal;
363 }
364 
365 bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI,
366                                     const MachineRegisterInfo &MRI) const {
367   auto Action = getAction(MI, MRI).Action;
368   // If the action is custom, it may not necessarily modify the instruction,
369   // so we have to assume it's legal.
370   return Action == Legal || Action == Custom;
371 }
372 
373 unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const {
374   return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
375 }
376 
377 /// \pre Type indices of every opcode form a dense set starting from 0.
378 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
379 #ifndef NDEBUG
380   std::vector<unsigned> FailedOpcodes;
381   for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
382     const MCInstrDesc &MCID = MII.get(Opcode);
383     const unsigned NumTypeIdxs = std::accumulate(
384         MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
385         [](unsigned Acc, const MCOperandInfo &OpInfo) {
386           return OpInfo.isGenericType()
387                      ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
388                      : Acc;
389         });
390     const unsigned NumImmIdxs = std::accumulate(
391         MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
392         [](unsigned Acc, const MCOperandInfo &OpInfo) {
393           return OpInfo.isGenericImm()
394                      ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
395                      : Acc;
396         });
397     LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
398                       << "): " << NumTypeIdxs << " type ind"
399                       << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
400                       << NumImmIdxs << " imm ind"
401                       << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
402     const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
403     if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
404       FailedOpcodes.push_back(Opcode);
405     else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
406       FailedOpcodes.push_back(Opcode);
407   }
408   if (!FailedOpcodes.empty()) {
409     errs() << "The following opcodes have ill-defined legalization rules:";
410     for (unsigned Opcode : FailedOpcodes)
411       errs() << " " << MII.getName(Opcode);
412     errs() << "\n";
413 
414     report_fatal_error("ill-defined LegalizerInfo"
415                        ", try -debug-only=legalizer-info for details");
416   }
417 #endif
418 }
419 
420 #ifndef NDEBUG
421 // FIXME: This should be in the MachineVerifier, but it can't use the
422 // LegalizerInfo as it's currently in the separate GlobalISel library.
423 // Note that RegBankSelected property already checked in the verifier
424 // has the same layering problem, but we only use inline methods so
425 // end up not needing to link against the GlobalISel library.
426 const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
427   if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
428     const MachineRegisterInfo &MRI = MF.getRegInfo();
429     for (const MachineBasicBlock &MBB : MF)
430       for (const MachineInstr &MI : MBB)
431         if (isPreISelGenericOpcode(MI.getOpcode()) &&
432             !MLI->isLegalOrCustom(MI, MRI))
433           return &MI;
434   }
435   return nullptr;
436 }
437 #endif
438