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