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/LowLevelType.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 <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=" << 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.
hasNoSimpleLoops(const LegalizeRule & Rule,const LegalityQuery & Q,const std::pair<unsigned,LLT> & Mutation)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.
mutationIsSane(const LegalizeRule & Rule,const LegalityQuery & Q,std::pair<unsigned,LLT> Mutation)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(1);
137     if (NewTy.isVector()) {
138       if (Rule.getAction() == FewerElements) {
139         // Make sure the element count really decreased.
140         if (ElementCount::isKnownGE(NewTy.getElementCount(), OldElts))
141           return false;
142       } else {
143         // Make sure the element count really increased.
144         if (ElementCount::isKnownLE(NewTy.getElementCount(), 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 
apply(const LegalityQuery & Query) const186 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 
verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const210 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 
verifyImmIdxsCoverage(unsigned NumImmIdxs) const233 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.
getTypeFromTypeIdx(const MachineInstr & MI,const MachineRegisterInfo & MRI,unsigned OpIdx,unsigned TypeIdx)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(MI.getOperand(MI.getNumOperands() - 1).getReg());
265   return MRI.getType(MI.getOperand(OpIdx).getReg());
266 }
267 
getOpcodeIdxForOpcode(unsigned Opcode) const268 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
269   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
270   return Opcode - FirstOp;
271 }
272 
getActionDefinitionsIdx(unsigned Opcode) const273 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(Alias);
279     assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
280   }
281 
282   return OpcodeIdx;
283 }
284 
285 const LegalizeRuleSet &
getActionDefinitions(unsigned Opcode) const286 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
287   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
288   return RulesForOpcode[OpcodeIdx];
289 }
290 
getActionDefinitionsBuilder(unsigned Opcode)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 
getActionDefinitionsBuilder(std::initializer_list<unsigned> Opcodes)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(Opcodes))
306     aliasActionDefinitions(Representative, Op);
307 
308   auto &Return = getActionDefinitionsBuilder(Representative);
309   Return.setIsAliasedByAnother();
310   return Return;
311 }
312 
aliasActionDefinitions(unsigned OpcodeTo,unsigned OpcodeFrom)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(OpcodeFrom);
318   RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
319 }
320 
321 LegalizeActionStep
getAction(const LegalityQuery & Query) const322 LegalizerInfo::getAction(const LegalityQuery &Query) const {
323   LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
324   if (Step.Action != LegalizeAction::UseLegacyRules) {
325     return Step;
326   }
327 
328   return getLegacyLegalizerInfo().getAction(Query);
329 }
330 
331 LegalizeActionStep
getAction(const MachineInstr & MI,const MachineRegisterInfo & MRI) const332 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, i, TypeIdx);
351     Types.push_back(Ty);
352   }
353 
354   SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
355   for (const auto &MMO : MI.memoperands())
356     MemDescrs.push_back({*MMO});
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.operands().begin(), MCID.operands().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.operands().begin(), MCID.operands().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