Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/CodeGen/GlobalISel/LegalizerInfo.h ------------------*- C++ -*-===//
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
/// Interface for Targets to specify which operations they can successfully
11
/// select and how the others should be expanded most efficiently.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
16
#define LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
17
18
#include "llvm/ADT/DenseMap.h"
19
#include "llvm/ADT/None.h"
20
#include "llvm/ADT/Optional.h"
21
#include "llvm/ADT/STLExtras.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/Support/LowLevelTypeImpl.h"
24
#include "llvm/Target/TargetOpcodes.h"
25
#include <cstdint>
26
#include <cassert>
27
#include <tuple>
28
#include <utility>
29
30
namespace llvm {
31
32
class MachineInstr;
33
class MachineIRBuilder;
34
class MachineRegisterInfo;
35
36
/// Legalization is decided based on an instruction's opcode, which type slot
37
/// we're considering, and what the existing type is. These aspects are gathered
38
/// together for convenience in the InstrAspect class.
39
struct InstrAspect {
40
  unsigned Opcode;
41
  unsigned Idx = 0;
42
  LLT Type;
43
44
4.49M
  InstrAspect(unsigned Opcode, LLT Type) : Opcode(Opcode), Type(Type) {}
45
  InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
46
12.5M
      : Opcode(Opcode), Idx(Idx), Type(Type) {}
47
48
0
  bool operator==(const InstrAspect &RHS) const {
49
0
    return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
50
0
  }
51
};
52
53
class LegalizerInfo {
54
public:
55
  enum LegalizeAction : std::uint8_t {
56
    /// The operation is expected to be selectable directly by the target, and
57
    /// no transformation is necessary.
58
    Legal,
59
60
    /// The operation should be synthesized from multiple instructions acting on
61
    /// a narrower scalar base-type. For example a 64-bit add might be
62
    /// implemented in terms of 32-bit add-with-carry.
63
    NarrowScalar,
64
65
    /// The operation should be implemented in terms of a wider scalar
66
    /// base-type. For example a <2 x s8> add could be implemented as a <2
67
    /// x s32> add (ignoring the high bits).
68
    WidenScalar,
69
70
    /// The (vector) operation should be implemented by splitting it into
71
    /// sub-vectors where the operation is legal. For example a <8 x s64> add
72
    /// might be implemented as 4 separate <2 x s64> adds.
73
    FewerElements,
74
75
    /// The (vector) operation should be implemented by widening the input
76
    /// vector and ignoring the lanes added by doing so. For example <2 x i8> is
77
    /// rarely legal, but you might perform an <8 x i8> and then only look at
78
    /// the first two results.
79
    MoreElements,
80
81
    /// The operation itself must be expressed in terms of simpler actions on
82
    /// this target. E.g. a SREM replaced by an SDIV and subtraction.
83
    Lower,
84
85
    /// The operation should be implemented as a call to some kind of runtime
86
    /// support library. For example this usually happens on machines that don't
87
    /// support floating-point operations natively.
88
    Libcall,
89
90
    /// The target wants to do something special with this combination of
91
    /// operand and type. A callback will be issued when it is needed.
92
    Custom,
93
94
    /// This operation is completely unsupported on the target. A programming
95
    /// error has occurred.
96
    Unsupported,
97
98
    /// Sentinel value for when no action was found in the specified table.
99
    NotFound,
100
  };
101
102
  LegalizerInfo();
103
15.1k
  virtual ~LegalizerInfo() = default;
104
105
  /// Compute any ancillary tables needed to quickly decide how an operation
106
  /// should be handled. This must be called after all "set*Action"methods but
107
  /// before any query is made or incorrect results may be returned.
108
  void computeTables();
109
110
1.99M
  static bool needsLegalizingToDifferentSize(const LegalizeAction Action) {
111
1.99M
    switch (Action) {
112
1.22M
    case NarrowScalar:
113
1.22M
    case WidenScalar:
114
1.22M
    case FewerElements:
115
1.22M
    case MoreElements:
116
1.22M
    case Unsupported:
117
1.22M
      return true;
118
768k
    default:
119
768k
      return false;
120
1.99M
    }
121
1.99M
  }
122
123
  /// More friendly way to set an action for common types that have an LLT
124
  /// representation.
125
6.47M
  void setAction(const InstrAspect &Aspect, LegalizeAction Action) {
126
6.47M
    TablesInitialized = false;
127
6.47M
    unsigned Opcode = Aspect.Opcode - FirstOp;
128
6.47M
    if (Actions[Opcode].size() <= Aspect.Idx)
129
1.74M
      Actions[Opcode].resize(Aspect.Idx + 1);
130
6.47M
    Actions[Aspect.Opcode - FirstOp][Aspect.Idx][Aspect.Type] = Action;
131
6.47M
  }
132
133
  /// If an operation on a given vector type (say <M x iN>) isn't explicitly
134
  /// specified, we proceed in 2 stages. First we legalize the underlying scalar
135
  /// (so that there's at least one legal vector with that scalar), then we
136
  /// adjust the number of elements in the vector so that it is legal. The
137
  /// desired action in the first step is controlled by this function.
138
  void setScalarInVectorAction(unsigned Opcode, LLT ScalarTy,
139
0
                               LegalizeAction Action) {
140
0
    assert(!ScalarTy.isVector());
141
0
    ScalarInVectorActions[std::make_pair(Opcode, ScalarTy)] = Action;
142
0
  }
143
144
  /// Determine what action should be taken to legalize the given generic
145
  /// instruction opcode, type-index and type. Requires computeTables to have
146
  /// been called.
147
  ///
148
  /// \returns a pair consisting of the kind of legalization that should be
149
  /// performed and the destination type.
150
  std::pair<LegalizeAction, LLT> getAction(const InstrAspect &Aspect) const;
151
152
  /// Determine what action should be taken to legalize the given generic
153
  /// instruction.
154
  ///
155
  /// \returns a tuple consisting of the LegalizeAction that should be
156
  /// performed, the type-index it should be performed on and the destination
157
  /// type.
158
  std::tuple<LegalizeAction, unsigned, LLT>
159
  getAction(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
160
161
  /// Iterate the given function (typically something like doubling the width)
162
  /// on Ty until we find a legal type for this operation.
163
  Optional<LLT> findLegalizableSize(const InstrAspect &Aspect,
164
768k
                                    function_ref<LLT(LLT)> NextType) const {
165
768k
    if (Aspect.Idx >= Actions[Aspect.Opcode - FirstOp].size())
166
0
      return None;
167
768k
168
768k
    LegalizeAction Action;
169
768k
    const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx];
170
768k
    LLT Ty = Aspect.Type;
171
1.99M
    do {
172
1.99M
      Ty = NextType(Ty);
173
1.99M
      auto ActionIt = Map.find(Ty);
174
1.99M
      if (
ActionIt == Map.end()1.99M
) {
175
125
        auto DefaultIt = DefaultActions.find(Aspect.Opcode);
176
125
        if (DefaultIt == DefaultActions.end())
177
0
          return None;
178
125
        Action = DefaultIt->second;
179
125
      } else
180
1.99M
        Action = ActionIt->second;
181
1.99M
    } while (needsLegalizingToDifferentSize(Action));
182
768k
    return Ty;
183
768k
  }
184
185
  /// Find what type it's actually OK to perform the given operation on, given
186
  /// the general approach we've decided to take.
187
  Optional<LLT> findLegalType(const InstrAspect &Aspect, LegalizeAction Action) const;
188
189
  std::pair<LegalizeAction, LLT> findLegalAction(const InstrAspect &Aspect,
190
10.5M
                                                 LegalizeAction Action) const {
191
10.5M
    auto LegalType = findLegalType(Aspect, Action);
192
10.5M
    if (!LegalType)
193
0
      return std::make_pair(LegalizeAction::Unsupported, LLT());
194
10.5M
    return std::make_pair(Action, *LegalType);
195
10.5M
  }
196
197
  /// Find the specified \p Aspect in the primary (explicitly set) Actions
198
  /// table. Returns either the action the target requested or NotFound if there
199
  /// was no setAction call.
200
10.5M
  LegalizeAction findInActions(const InstrAspect &Aspect) const {
201
10.5M
    if (
Aspect.Opcode < FirstOp || 10.5M
Aspect.Opcode > LastOp10.5M
)
202
0
      return NotFound;
203
10.5M
    
if (10.5M
Aspect.Idx >= Actions[Aspect.Opcode - FirstOp].size()10.5M
)
204
2.74k
      return NotFound;
205
10.5M
    const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx];
206
10.5M
    auto ActionIt =  Map.find(Aspect.Type);
207
10.5M
    if (ActionIt == Map.end())
208
53.0k
      return NotFound;
209
10.5M
210
10.4M
    return ActionIt->second;
211
10.5M
  }
212
213
  bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
214
215
  virtual bool legalizeCustom(MachineInstr &MI,
216
                              MachineRegisterInfo &MRI,
217
                              MachineIRBuilder &MIRBuilder) const;
218
219
private:
220
  static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
221
  static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
222
223
  using TypeMap = DenseMap<LLT, LegalizeAction>;
224
  using SIVActionMap = DenseMap<std::pair<unsigned, LLT>, LegalizeAction>;
225
226
  SmallVector<TypeMap, 1> Actions[LastOp - FirstOp + 1];
227
  SIVActionMap ScalarInVectorActions;
228
  DenseMap<std::pair<unsigned, LLT>, uint16_t> MaxLegalVectorElts;
229
  DenseMap<unsigned, LegalizeAction> DefaultActions;
230
231
  bool TablesInitialized = false;
232
};
233
234
} // end namespace llvm
235
236
#endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H