1 //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Implement an interface to specify and query how an illegal operation on a
11 // given type should be expanded.
12 //
13 // Issues to be resolved:
14 //   + Make it fast.
15 //   + Support weird types like i3, <7 x i3>, ...
16 //   + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
21 #include "llvm/ADT/SmallBitVector.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/CodeGen/MachineOperand.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/MC/MCInstrDesc.h"
26 #include "llvm/Support/ErrorHandling.h"
27 #include "llvm/Support/LowLevelTypeImpl.h"
28 #include "llvm/Support/MathExtras.h"
29 #include "llvm/Target/TargetOpcodes.h"
30 #include <algorithm>
31 #include <cassert>
32 #include <tuple>
33 #include <utility>
34 
35 using namespace llvm;
36 
37 LegalizerInfo::LegalizerInfo() {
38   DefaultActions[TargetOpcode::G_IMPLICIT_DEF] = NarrowScalar;
39 
40   // FIXME: these two can be legalized to the fundamental load/store Jakob
41   // proposed. Once loads & stores are supported.
42   DefaultActions[TargetOpcode::G_ANYEXT] = Legal;
43   DefaultActions[TargetOpcode::G_TRUNC] = Legal;
44 
45   DefaultActions[TargetOpcode::G_INTRINSIC] = Legal;
46   DefaultActions[TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS] = Legal;
47 
48   DefaultActions[TargetOpcode::G_ADD] = NarrowScalar;
49   DefaultActions[TargetOpcode::G_LOAD] = NarrowScalar;
50   DefaultActions[TargetOpcode::G_STORE] = NarrowScalar;
51   DefaultActions[TargetOpcode::G_OR] = NarrowScalar;
52 
53   DefaultActions[TargetOpcode::G_BRCOND] = WidenScalar;
54   DefaultActions[TargetOpcode::G_INSERT] = NarrowScalar;
55   DefaultActions[TargetOpcode::G_EXTRACT] = NarrowScalar;
56   DefaultActions[TargetOpcode::G_FNEG] = Lower;
57 }
58 
59 void LegalizerInfo::computeTables() {
60   for (unsigned Opcode = 0; Opcode <= LastOp - FirstOp; ++Opcode) {
61     for (unsigned Idx = 0, End = Actions[Opcode].size(); Idx != End; ++Idx) {
62       for (auto &Action : Actions[Opcode][Idx]) {
63         LLT Ty = Action.first;
64         if (!Ty.isVector())
65           continue;
66 
67         auto &Entry = MaxLegalVectorElts[std::make_pair(Opcode + FirstOp,
68                                                         Ty.getElementType())];
69         Entry = std::max(Entry, Ty.getNumElements());
70       }
71     }
72   }
73 
74   TablesInitialized = true;
75 }
76 
77 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
78 // probably going to need specialized lookup structures for various types before
79 // we have any hope of doing well with something like <13 x i3>. Even the common
80 // cases should do better than what we have now.
81 std::pair<LegalizerInfo::LegalizeAction, LLT>
82 LegalizerInfo::getAction(const InstrAspect &Aspect) const {
83   assert(TablesInitialized && "backend forgot to call computeTables");
84   // These *have* to be implemented for now, they're the fundamental basis of
85   // how everything else is transformed.
86 
87   // FIXME: the long-term plan calls for expansion in terms of load/store (if
88   // they're not legal).
89   if (Aspect.Opcode == TargetOpcode::G_MERGE_VALUES ||
90       Aspect.Opcode == TargetOpcode::G_UNMERGE_VALUES)
91     return std::make_pair(Legal, Aspect.Type);
92 
93   LLT Ty = Aspect.Type;
94   LegalizeAction Action = findInActions(Aspect);
95   // LegalizerHelper is not able to handle non-power-of-2 types right now, so do
96   // not try to legalize them unless they are marked as Legal or Custom.
97   // FIXME: This is a temporary hack until the general non-power-of-2
98   // legalization works.
99   if (!isPowerOf2_64(Ty.getSizeInBits()) &&
100       !(Action == Legal || Action == Custom))
101     return std::make_pair(Unsupported, LLT());
102 
103   if (Action != NotFound)
104     return findLegalAction(Aspect, Action);
105 
106   unsigned Opcode = Aspect.Opcode;
107   if (!Ty.isVector()) {
108     auto DefaultAction = DefaultActions.find(Aspect.Opcode);
109     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal)
110       return std::make_pair(Legal, Ty);
111 
112     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Lower)
113       return std::make_pair(Lower, Ty);
114 
115     if (DefaultAction == DefaultActions.end() ||
116         DefaultAction->second != NarrowScalar)
117       return std::make_pair(Unsupported, LLT());
118     return findLegalAction(Aspect, NarrowScalar);
119   }
120 
121   LLT EltTy = Ty.getElementType();
122   int NumElts = Ty.getNumElements();
123 
124   auto ScalarAction = ScalarInVectorActions.find(std::make_pair(Opcode, EltTy));
125   if (ScalarAction != ScalarInVectorActions.end() &&
126       ScalarAction->second != Legal)
127     return findLegalAction(Aspect, ScalarAction->second);
128 
129   // The element type is legal in principle, but the number of elements is
130   // wrong.
131   auto MaxLegalElts = MaxLegalVectorElts.lookup(std::make_pair(Opcode, EltTy));
132   if (MaxLegalElts > NumElts)
133     return findLegalAction(Aspect, MoreElements);
134 
135   if (MaxLegalElts == 0) {
136     // Scalarize if there's no legal vector type, which is just a special case
137     // of FewerElements.
138     return std::make_pair(FewerElements, EltTy);
139   }
140 
141   return findLegalAction(Aspect, FewerElements);
142 }
143 
144 std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
145 LegalizerInfo::getAction(const MachineInstr &MI,
146                          const MachineRegisterInfo &MRI) const {
147   SmallBitVector SeenTypes(8);
148   const MCInstrDesc &MCID = MI.getDesc();
149   const MCOperandInfo *OpInfo = MCID.OpInfo;
150   for (unsigned i = 0, e = MCID.getNumOperands(); i != e; ++i) {
151     if (!OpInfo[i].isGenericType())
152       continue;
153 
154     // We don't want to repeatedly check the same operand index, that
155     // could get expensive.
156     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
157     if (SeenTypes[TypeIdx])
158       continue;
159 
160     SeenTypes.set(TypeIdx);
161 
162     LLT Ty = MRI.getType(MI.getOperand(i).getReg());
163     auto Action = getAction({MI.getOpcode(), TypeIdx, Ty});
164     if (Action.first != Legal)
165       return std::make_tuple(Action.first, TypeIdx, Action.second);
166   }
167   return std::make_tuple(Legal, 0, LLT{});
168 }
169 
170 bool LegalizerInfo::isLegal(const MachineInstr &MI,
171                             const MachineRegisterInfo &MRI) const {
172   return std::get<0>(getAction(MI, MRI)) == Legal;
173 }
174 
175 Optional<LLT> LegalizerInfo::findLegalType(const InstrAspect &Aspect,
176                                  LegalizeAction Action) const {
177   switch(Action) {
178   default:
179     llvm_unreachable("Cannot find legal type");
180   case Legal:
181   case Lower:
182   case Libcall:
183   case Custom:
184     return Aspect.Type;
185   case NarrowScalar: {
186     return findLegalizableSize(
187         Aspect, [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
188   }
189   case WidenScalar: {
190     return findLegalizableSize(Aspect, [&](LLT Ty) -> LLT {
191       return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize();
192     });
193   }
194   case FewerElements: {
195     return findLegalizableSize(
196         Aspect, [&](LLT Ty) -> LLT { return Ty.halfElements(); });
197   }
198   case MoreElements: {
199     return findLegalizableSize(
200         Aspect, [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
201   }
202   }
203 }
204 
205 bool LegalizerInfo::legalizeCustom(MachineInstr &MI,
206                                    MachineRegisterInfo &MRI,
207                                    MachineIRBuilder &MIRBuilder) const {
208   return false;
209 }
210