LegalizeVectorOps.cpp revision 193323
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 like 24// ISD::CALL; 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 generic vector operation, i.e. turning it into 58 // scalar operations. 59 SDValue UnrollVectorOp(SDValue Op); 60 // Implements unrolling a VSETCC. 61 SDValue UnrollVSETCC(SDValue Op); 62 // Implements expansion for FNEG; falls back to UnrollVectorOp if FSUB 63 // isn't legal. 64 SDValue ExpandFNEG(SDValue Op); 65 // Implements vector promotion; this is essentially just bitcasting the 66 // operands to a different type and bitcasting the result back to the 67 // original type. 68 SDValue PromoteVectorOp(SDValue Op); 69 70 public: 71 bool Run(); 72 VectorLegalizer(SelectionDAG& dag) : 73 DAG(dag), TLI(dag.getTargetLoweringInfo()), Changed(false) {} 74}; 75 76bool VectorLegalizer::Run() { 77 // The legalize process is inherently a bottom-up recursive process (users 78 // legalize their uses before themselves). Given infinite stack space, we 79 // could just start legalizing on the root and traverse the whole graph. In 80 // practice however, this causes us to run out of stack space on large basic 81 // blocks. To avoid this problem, compute an ordering of the nodes where each 82 // node is only legalized after all of its operands are legalized. 83 DAG.AssignTopologicalOrder(); 84 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 85 E = prior(DAG.allnodes_end()); I != next(E); ++I) 86 LegalizeOp(SDValue(I, 0)); 87 88 // Finally, it's possible the root changed. Get the new root. 89 SDValue OldRoot = DAG.getRoot(); 90 assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?"); 91 DAG.setRoot(LegalizedNodes[OldRoot]); 92 93 LegalizedNodes.clear(); 94 95 // Remove dead nodes now. 96 DAG.RemoveDeadNodes(); 97 98 return Changed; 99} 100 101SDValue VectorLegalizer::TranslateLegalizeResults(SDValue Op, SDValue Result) { 102 // Generic legalization: just pass the operand through. 103 for (unsigned i = 0, e = Op.getNode()->getNumValues(); i != e; ++i) 104 AddLegalizedOperand(Op.getValue(i), Result.getValue(i)); 105 return Result.getValue(Op.getResNo()); 106} 107 108SDValue VectorLegalizer::LegalizeOp(SDValue Op) { 109 // Note that LegalizeOp may be reentered even from single-use nodes, which 110 // means that we always must cache transformed nodes. 111 DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op); 112 if (I != LegalizedNodes.end()) return I->second; 113 114 SDNode* Node = Op.getNode(); 115 116 // Legalize the operands 117 SmallVector<SDValue, 8> Ops; 118 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) 119 Ops.push_back(LegalizeOp(Node->getOperand(i))); 120 121 SDValue Result = 122 DAG.UpdateNodeOperands(Op.getValue(0), Ops.data(), Ops.size()); 123 124 bool HasVectorValue = false; 125 for (SDNode::value_iterator J = Node->value_begin(), E = Node->value_end(); 126 J != E; 127 ++J) 128 HasVectorValue |= J->isVector(); 129 if (!HasVectorValue) 130 return TranslateLegalizeResults(Op, Result); 131 132 switch (Op.getOpcode()) { 133 default: 134 return TranslateLegalizeResults(Op, Result); 135 case ISD::ADD: 136 case ISD::SUB: 137 case ISD::MUL: 138 case ISD::SDIV: 139 case ISD::UDIV: 140 case ISD::SREM: 141 case ISD::UREM: 142 case ISD::FADD: 143 case ISD::FSUB: 144 case ISD::FMUL: 145 case ISD::FDIV: 146 case ISD::FREM: 147 case ISD::AND: 148 case ISD::OR: 149 case ISD::XOR: 150 case ISD::SHL: 151 case ISD::SRA: 152 case ISD::SRL: 153 case ISD::ROTL: 154 case ISD::ROTR: 155 case ISD::CTTZ: 156 case ISD::CTLZ: 157 case ISD::CTPOP: 158 case ISD::SELECT: 159 case ISD::SELECT_CC: 160 case ISD::VSETCC: 161 case ISD::ZERO_EXTEND: 162 case ISD::ANY_EXTEND: 163 case ISD::TRUNCATE: 164 case ISD::SIGN_EXTEND: 165 case ISD::SINT_TO_FP: 166 case ISD::UINT_TO_FP: 167 case ISD::FP_TO_SINT: 168 case ISD::FP_TO_UINT: 169 case ISD::FNEG: 170 case ISD::FABS: 171 case ISD::FSQRT: 172 case ISD::FSIN: 173 case ISD::FCOS: 174 case ISD::FPOWI: 175 case ISD::FPOW: 176 case ISD::FLOG: 177 case ISD::FLOG2: 178 case ISD::FLOG10: 179 case ISD::FEXP: 180 case ISD::FEXP2: 181 case ISD::FCEIL: 182 case ISD::FTRUNC: 183 case ISD::FRINT: 184 case ISD::FNEARBYINT: 185 case ISD::FFLOOR: 186 break; 187 } 188 189 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 190 case TargetLowering::Promote: 191 // "Promote" the operation by bitcasting 192 Result = PromoteVectorOp(Op); 193 Changed = true; 194 break; 195 case TargetLowering::Legal: break; 196 case TargetLowering::Custom: { 197 SDValue Tmp1 = TLI.LowerOperation(Op, DAG); 198 if (Tmp1.getNode()) { 199 Result = Tmp1; 200 break; 201 } 202 // FALL THROUGH 203 } 204 case TargetLowering::Expand: 205 if (Node->getOpcode() == ISD::FNEG) 206 Result = ExpandFNEG(Op); 207 else if (Node->getOpcode() == ISD::VSETCC) 208 Result = UnrollVSETCC(Op); 209 else 210 Result = UnrollVectorOp(Op); 211 break; 212 } 213 214 // Make sure that the generated code is itself legal. 215 if (Result != Op) { 216 Result = LegalizeOp(Result); 217 Changed = true; 218 } 219 220 // Note that LegalizeOp may be reentered even from single-use nodes, which 221 // means that we always must cache transformed nodes. 222 AddLegalizedOperand(Op, Result); 223 return Result; 224} 225 226SDValue VectorLegalizer::PromoteVectorOp(SDValue Op) { 227 // Vector "promotion" is basically just bitcasting and doing the operation 228 // in a different type. For example, x86 promotes ISD::AND on v2i32 to 229 // v1i64. 230 MVT VT = Op.getValueType(); 231 assert(Op.getNode()->getNumValues() == 1 && 232 "Can't promote a vector with multiple results!"); 233 MVT NVT = TLI.getTypeToPromoteTo(Op.getOpcode(), VT); 234 DebugLoc dl = Op.getDebugLoc(); 235 SmallVector<SDValue, 4> Operands(Op.getNumOperands()); 236 237 for (unsigned j = 0; j != Op.getNumOperands(); ++j) { 238 if (Op.getOperand(j).getValueType().isVector()) 239 Operands[j] = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Op.getOperand(j)); 240 else 241 Operands[j] = Op.getOperand(j); 242 } 243 244 Op = DAG.getNode(Op.getOpcode(), dl, NVT, &Operands[0], Operands.size()); 245 246 return DAG.getNode(ISD::BIT_CONVERT, dl, VT, Op); 247} 248 249SDValue VectorLegalizer::ExpandFNEG(SDValue Op) { 250 if (TLI.isOperationLegalOrCustom(ISD::FSUB, Op.getValueType())) { 251 SDValue Zero = DAG.getConstantFP(-0.0, Op.getValueType()); 252 return DAG.getNode(ISD::FSUB, Op.getDebugLoc(), Op.getValueType(), 253 Zero, Op.getOperand(0)); 254 } 255 return UnrollVectorOp(Op); 256} 257 258SDValue VectorLegalizer::UnrollVSETCC(SDValue Op) { 259 MVT VT = Op.getValueType(); 260 unsigned NumElems = VT.getVectorNumElements(); 261 MVT EltVT = VT.getVectorElementType(); 262 SDValue LHS = Op.getOperand(0), RHS = Op.getOperand(1), CC = Op.getOperand(2); 263 MVT TmpEltVT = LHS.getValueType().getVectorElementType(); 264 DebugLoc dl = Op.getDebugLoc(); 265 SmallVector<SDValue, 8> Ops(NumElems); 266 for (unsigned i = 0; i < NumElems; ++i) { 267 SDValue LHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, LHS, 268 DAG.getIntPtrConstant(i)); 269 SDValue RHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, RHS, 270 DAG.getIntPtrConstant(i)); 271 Ops[i] = DAG.getNode(ISD::SETCC, dl, TLI.getSetCCResultType(TmpEltVT), 272 LHSElem, RHSElem, CC); 273 Ops[i] = DAG.getNode(ISD::SELECT, dl, EltVT, Ops[i], 274 DAG.getConstant(APInt::getAllOnesValue 275 (EltVT.getSizeInBits()), EltVT), 276 DAG.getConstant(0, EltVT)); 277 } 278 return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], NumElems); 279} 280 281/// UnrollVectorOp - We know that the given vector has a legal type, however 282/// the operation it performs is not legal, and the target has requested that 283/// the operation be expanded. "Unroll" the vector, splitting out the scalars 284/// and operating on each element individually. 285SDValue VectorLegalizer::UnrollVectorOp(SDValue Op) { 286 MVT VT = Op.getValueType(); 287 assert(Op.getNode()->getNumValues() == 1 && 288 "Can't unroll a vector with multiple results!"); 289 unsigned NE = VT.getVectorNumElements(); 290 MVT EltVT = VT.getVectorElementType(); 291 DebugLoc dl = Op.getDebugLoc(); 292 293 SmallVector<SDValue, 8> Scalars; 294 SmallVector<SDValue, 4> Operands(Op.getNumOperands()); 295 for (unsigned i = 0; i != NE; ++i) { 296 for (unsigned j = 0; j != Op.getNumOperands(); ++j) { 297 SDValue Operand = Op.getOperand(j); 298 MVT OperandVT = Operand.getValueType(); 299 if (OperandVT.isVector()) { 300 // A vector operand; extract a single element. 301 MVT OperandEltVT = OperandVT.getVectorElementType(); 302 Operands[j] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, 303 OperandEltVT, 304 Operand, 305 DAG.getConstant(i, MVT::i32)); 306 } else { 307 // A scalar operand; just use it as is. 308 Operands[j] = Operand; 309 } 310 } 311 312 switch (Op.getOpcode()) { 313 default: 314 Scalars.push_back(DAG.getNode(Op.getOpcode(), dl, EltVT, 315 &Operands[0], Operands.size())); 316 break; 317 case ISD::SHL: 318 case ISD::SRA: 319 case ISD::SRL: 320 case ISD::ROTL: 321 case ISD::ROTR: 322 Scalars.push_back(DAG.getNode(Op.getOpcode(), dl, EltVT, Operands[0], 323 DAG.getShiftAmountOperand(Operands[1]))); 324 break; 325 } 326 } 327 328 return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Scalars[0], Scalars.size()); 329} 330 331} 332 333bool SelectionDAG::LegalizeVectors() { 334 return VectorLegalizer(*this).Run(); 335} 336