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 
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 << ", 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.
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.
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 
183 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 
207 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 
230 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.
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 
265 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
266   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
267   return Opcode - FirstOp;
268 }
269 
270 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 &
283 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
284   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
285   return RulesForOpcode[OpcodeIdx];
286 }
287 
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 
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 
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
319 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
329 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 
358 bool LegalizerInfo::isLegal(const MachineInstr &MI,
359                             const MachineRegisterInfo &MRI) const {
360   return getAction(MI, MRI).Action == Legal;
361 }
362 
363 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 
371 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.
376 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.
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