LegalizeVectorOps.cpp revision cd6e725f21852e2f8cdf5fd0e65eb42c224776f8 
1//===-- LegalizeVectorOps.cpp - Implement SelectionDAG::LegalizeVectors ---===//
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// This file implements the SelectionDAG::LegalizeVectors method.
11//
12// The vector legalizer looks for vector operations which might need to be
13// scalarized and legalizes them. This is a separate step from Legalize because
14// scalarizing can introduce illegal types.  For example, suppose we have an
15// ISD::SDIV of type v2i64 on x86-32.  The type is legal (for example, addition
16// on a v2i64 is legal), but ISD::SDIV isn't legal, so we have to unroll the
17// operation, which introduces nodes with the illegal type i64 which must be
18// expanded.  Similarly, suppose we have an ISD::SRA of type v16i8 on PowerPC;
19// the operation must be unrolled, which introduces nodes with the illegal
20// type i8 which must be promoted.
21//
22// This does not legalize vector manipulations like ISD::BUILD_VECTOR,
23// or operations that happen to take a vector which are custom-lowered;
24// the legalization for such operations never produces nodes
25// with illegal types, so it's okay to put off legalizing them until
26// SelectionDAG::Legalize runs.
27//
28//===----------------------------------------------------------------------===//
29
30#include "llvm/CodeGen/SelectionDAG.h"
31#include "llvm/Target/TargetLowering.h"
32using namespace llvm;
33
34namespace {
35class VectorLegalizer {
36  SelectionDAG& DAG;
37  TargetLowering& TLI;
38  bool Changed; // Keep track of whether anything changed
39
40  /// LegalizedNodes - For nodes that are of legal width, and that have more
41  /// than one use, this map indicates what regularized operand to use.  This
42  /// allows us to avoid legalizing the same thing more than once.
43  DenseMap<SDValue, SDValue> LegalizedNodes;
44
45  // Adds a node to the translation cache
46  void AddLegalizedOperand(SDValue From, SDValue To) {
47    LegalizedNodes.insert(std::make_pair(From, To));
48    // If someone requests legalization of the new node, return itself.
49    if (From != To)
50      LegalizedNodes.insert(std::make_pair(To, To));
51  }
52
53  // Legalizes the given node
54  SDValue LegalizeOp(SDValue Op);
55  // Assuming the node is legal, "legalize" the results
56  SDValue TranslateLegalizeResults(SDValue Op, SDValue Result);
57  // Implements unrolling a VSETCC.
58  SDValue UnrollVSETCC(SDValue Op);
59  // Implements expansion for FNEG; falls back to UnrollVectorOp if FSUB
60  // isn't legal.
61  SDValue ExpandFNEG(SDValue Op);
62  // Implements vector promotion; this is essentially just bitcasting the
63  // operands to a different type and bitcasting the result back to the
64  // original type.
65  SDValue PromoteVectorOp(SDValue Op);
66
67  public:
68  bool Run();
69  VectorLegalizer(SelectionDAG& dag) :
70      DAG(dag), TLI(dag.getTargetLoweringInfo()), Changed(false) {}
71};
72
73bool VectorLegalizer::Run() {
74  // The legalize process is inherently a bottom-up recursive process (users
75  // legalize their uses before themselves).  Given infinite stack space, we
76  // could just start legalizing on the root and traverse the whole graph.  In
77  // practice however, this causes us to run out of stack space on large basic
78  // blocks.  To avoid this problem, compute an ordering of the nodes where each
79  // node is only legalized after all of its operands are legalized.
80  DAG.AssignTopologicalOrder();
81  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
82       E = prior(DAG.allnodes_end()); I != next(E); ++I)
83    LegalizeOp(SDValue(I, 0));
84
85  // Finally, it's possible the root changed.  Get the new root.
86  SDValue OldRoot = DAG.getRoot();
87  assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?");
88  DAG.setRoot(LegalizedNodes[OldRoot]);
89
90  LegalizedNodes.clear();
91
92  // Remove dead nodes now.
93  DAG.RemoveDeadNodes();
94
95  return Changed;
96}
97
98SDValue VectorLegalizer::TranslateLegalizeResults(SDValue Op, SDValue Result) {
99  // Generic legalization: just pass the operand through.
100  for (unsigned i = 0, e = Op.getNode()->getNumValues(); i != e; ++i)
101    AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
102  return Result.getValue(Op.getResNo());
103}
104
105SDValue VectorLegalizer::LegalizeOp(SDValue Op) {
106  // Note that LegalizeOp may be reentered even from single-use nodes, which
107  // means that we always must cache transformed nodes.
108  DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op);
109  if (I != LegalizedNodes.end()) return I->second;
110
111  SDNode* Node = Op.getNode();
112
113  // Legalize the operands
114  SmallVector<SDValue, 8> Ops;
115  for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
116    Ops.push_back(LegalizeOp(Node->getOperand(i)));
117
118  SDValue Result =
119      DAG.UpdateNodeOperands(Op.getValue(0), Ops.data(), Ops.size());
120
121  bool HasVectorValue = false;
122  for (SDNode::value_iterator J = Node->value_begin(), E = Node->value_end();
123       J != E;
124       ++J)
125    HasVectorValue |= J->isVector();
126  if (!HasVectorValue)
127    return TranslateLegalizeResults(Op, Result);
128
129  EVT QueryType;
130  switch (Op.getOpcode()) {
131  default:
132    return TranslateLegalizeResults(Op, Result);
133  case ISD::ADD:
134  case ISD::SUB:
135  case ISD::MUL:
136  case ISD::SDIV:
137  case ISD::UDIV:
138  case ISD::SREM:
139  case ISD::UREM:
140  case ISD::FADD:
141  case ISD::FSUB:
142  case ISD::FMUL:
143  case ISD::FDIV:
144  case ISD::FREM:
145  case ISD::AND:
146  case ISD::OR:
147  case ISD::XOR:
148  case ISD::SHL:
149  case ISD::SRA:
150  case ISD::SRL:
151  case ISD::ROTL:
152  case ISD::ROTR:
153  case ISD::CTTZ:
154  case ISD::CTLZ:
155  case ISD::CTPOP:
156  case ISD::SELECT:
157  case ISD::SELECT_CC:
158  case ISD::VSETCC:
159  case ISD::ZERO_EXTEND:
160  case ISD::ANY_EXTEND:
161  case ISD::TRUNCATE:
162  case ISD::SIGN_EXTEND:
163  case ISD::FP_TO_SINT:
164  case ISD::FP_TO_UINT:
165  case ISD::FNEG:
166  case ISD::FABS:
167  case ISD::FSQRT:
168  case ISD::FSIN:
169  case ISD::FCOS:
170  case ISD::FPOWI:
171  case ISD::FPOW:
172  case ISD::FLOG:
173  case ISD::FLOG2:
174  case ISD::FLOG10:
175  case ISD::FEXP:
176  case ISD::FEXP2:
177  case ISD::FCEIL:
178  case ISD::FTRUNC:
179  case ISD::FRINT:
180  case ISD::FNEARBYINT:
181  case ISD::FFLOOR:
182    QueryType = Node->getValueType(0);
183    break;
184  case ISD::SINT_TO_FP:
185  case ISD::UINT_TO_FP:
186    QueryType = Node->getOperand(0).getValueType();
187    break;
188  }
189
190  switch (TLI.getOperationAction(Node->getOpcode(), QueryType)) {
191  case TargetLowering::Promote:
192    // "Promote" the operation by bitcasting
193    Result = PromoteVectorOp(Op);
194    Changed = true;
195    break;
196  case TargetLowering::Legal: break;
197  case TargetLowering::Custom: {
198    SDValue Tmp1 = TLI.LowerOperation(Op, DAG);
199    if (Tmp1.getNode()) {
200      Result = Tmp1;
201      break;
202    }
203    // FALL THROUGH
204  }
205  case TargetLowering::Expand:
206    if (Node->getOpcode() == ISD::FNEG)
207      Result = ExpandFNEG(Op);
208    else if (Node->getOpcode() == ISD::VSETCC)
209      Result = UnrollVSETCC(Op);
210    else
211      Result = DAG.UnrollVectorOp(Op.getNode());
212    break;
213  }
214
215  // Make sure that the generated code is itself legal.
216  if (Result != Op) {
217    Result = LegalizeOp(Result);
218    Changed = true;
219  }
220
221  // Note that LegalizeOp may be reentered even from single-use nodes, which
222  // means that we always must cache transformed nodes.
223  AddLegalizedOperand(Op, Result);
224  return Result;
225}
226
227SDValue VectorLegalizer::PromoteVectorOp(SDValue Op) {
228  // Vector "promotion" is basically just bitcasting and doing the operation
229  // in a different type.  For example, x86 promotes ISD::AND on v2i32 to
230  // v1i64.
231  EVT VT = Op.getValueType();
232  assert(Op.getNode()->getNumValues() == 1 &&
233         "Can't promote a vector with multiple results!");
234  EVT NVT = TLI.getTypeToPromoteTo(Op.getOpcode(), VT);
235  DebugLoc dl = Op.getDebugLoc();
236  SmallVector<SDValue, 4> Operands(Op.getNumOperands());
237
238  for (unsigned j = 0; j != Op.getNumOperands(); ++j) {
239    if (Op.getOperand(j).getValueType().isVector())
240      Operands[j] = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Op.getOperand(j));
241    else
242      Operands[j] = Op.getOperand(j);
243  }
244
245  Op = DAG.getNode(Op.getOpcode(), dl, NVT, &Operands[0], Operands.size());
246
247  return DAG.getNode(ISD::BIT_CONVERT, dl, VT, Op);
248}
249
250SDValue VectorLegalizer::ExpandFNEG(SDValue Op) {
251  if (TLI.isOperationLegalOrCustom(ISD::FSUB, Op.getValueType())) {
252    SDValue Zero = DAG.getConstantFP(-0.0, Op.getValueType());
253    return DAG.getNode(ISD::FSUB, Op.getDebugLoc(), Op.getValueType(),
254                       Zero, Op.getOperand(0));
255  }
256  return DAG.UnrollVectorOp(Op.getNode());
257}
258
259SDValue VectorLegalizer::UnrollVSETCC(SDValue Op) {
260  EVT VT = Op.getValueType();
261  unsigned NumElems = VT.getVectorNumElements();
262  EVT EltVT = VT.getVectorElementType();
263  SDValue LHS = Op.getOperand(0), RHS = Op.getOperand(1), CC = Op.getOperand(2);
264  EVT TmpEltVT = LHS.getValueType().getVectorElementType();
265  DebugLoc dl = Op.getDebugLoc();
266  SmallVector<SDValue, 8> Ops(NumElems);
267  for (unsigned i = 0; i < NumElems; ++i) {
268    SDValue LHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, LHS,
269                                  DAG.getIntPtrConstant(i));
270    SDValue RHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, RHS,
271                                  DAG.getIntPtrConstant(i));
272    Ops[i] = DAG.getNode(ISD::SETCC, dl, TLI.getSetCCResultType(TmpEltVT),
273                         LHSElem, RHSElem, CC);
274    Ops[i] = DAG.getNode(ISD::SELECT, dl, EltVT, Ops[i],
275                         DAG.getConstant(APInt::getAllOnesValue
276                                         (EltVT.getSizeInBits()), EltVT),
277                         DAG.getConstant(0, EltVT));
278  }
279  return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], NumElems);
280}
281
282}
283
284bool SelectionDAG::LegalizeVectors() {
285  return VectorLegalizer(*this).Run();
286}
287