LLVM API Documentation
00001 //===-- LegalizeVectorOps.cpp - Implement SelectionDAG::LegalizeVectors ---===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the SelectionDAG::LegalizeVectors method. 00011 // 00012 // The vector legalizer looks for vector operations which might need to be 00013 // scalarized and legalizes them. This is a separate step from Legalize because 00014 // scalarizing can introduce illegal types. For example, suppose we have an 00015 // ISD::SDIV of type v2i64 on x86-32. The type is legal (for example, addition 00016 // on a v2i64 is legal), but ISD::SDIV isn't legal, so we have to unroll the 00017 // operation, which introduces nodes with the illegal type i64 which must be 00018 // expanded. Similarly, suppose we have an ISD::SRA of type v16i8 on PowerPC; 00019 // the operation must be unrolled, which introduces nodes with the illegal 00020 // type i8 which must be promoted. 00021 // 00022 // This does not legalize vector manipulations like ISD::BUILD_VECTOR, 00023 // or operations that happen to take a vector which are custom-lowered; 00024 // the legalization for such operations never produces nodes 00025 // with illegal types, so it's okay to put off legalizing them until 00026 // SelectionDAG::Legalize runs. 00027 // 00028 //===----------------------------------------------------------------------===// 00029 00030 #include "llvm/CodeGen/SelectionDAG.h" 00031 #include "llvm/Target/TargetLowering.h" 00032 using namespace llvm; 00033 00034 namespace { 00035 class VectorLegalizer { 00036 SelectionDAG& DAG; 00037 TargetLowering& TLI; 00038 bool Changed; // Keep track of whether anything changed 00039 00040 /// LegalizedNodes - For nodes that are of legal width, and that have more 00041 /// than one use, this map indicates what regularized operand to use. This 00042 /// allows us to avoid legalizing the same thing more than once. 00043 DenseMap<SDValue, SDValue> LegalizedNodes; 00044 00045 // Adds a node to the translation cache 00046 void AddLegalizedOperand(SDValue From, SDValue To) { 00047 LegalizedNodes.insert(std::make_pair(From, To)); 00048 // If someone requests legalization of the new node, return itself. 00049 if (From != To) 00050 LegalizedNodes.insert(std::make_pair(To, To)); 00051 } 00052 00053 // Legalizes the given node 00054 SDValue LegalizeOp(SDValue Op); 00055 // Assuming the node is legal, "legalize" the results 00056 SDValue TranslateLegalizeResults(SDValue Op, SDValue Result); 00057 // Implements unrolling a generic vector operation, i.e. turning it into 00058 // scalar operations. 00059 SDValue UnrollVectorOp(SDValue Op); 00060 // Implements unrolling a VSETCC. 00061 SDValue UnrollVSETCC(SDValue Op); 00062 // Implements expansion for FNEG; falls back to UnrollVectorOp if FSUB 00063 // isn't legal. 00064 SDValue ExpandFNEG(SDValue Op); 00065 // Implements vector promotion; this is essentially just bitcasting the 00066 // operands to a different type and bitcasting the result back to the 00067 // original type. 00068 SDValue PromoteVectorOp(SDValue Op); 00069 00070 public: 00071 bool Run(); 00072 VectorLegalizer(SelectionDAG& dag) : 00073 DAG(dag), TLI(dag.getTargetLoweringInfo()), Changed(false) {} 00074 }; 00075 00076 bool VectorLegalizer::Run() { 00077 // The legalize process is inherently a bottom-up recursive process (users 00078 // legalize their uses before themselves). Given infinite stack space, we 00079 // could just start legalizing on the root and traverse the whole graph. In 00080 // practice however, this causes us to run out of stack space on large basic 00081 // blocks. To avoid this problem, compute an ordering of the nodes where each 00082 // node is only legalized after all of its operands are legalized. 00083 DAG.AssignTopologicalOrder(); 00084 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 00085 E = prior(DAG.allnodes_end()); I != next(E); ++I) 00086 LegalizeOp(SDValue(I, 0)); 00087 00088 // Finally, it's possible the root changed. Get the new root. 00089 SDValue OldRoot = DAG.getRoot(); 00090 assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?"); 00091 DAG.setRoot(LegalizedNodes[OldRoot]); 00092 00093 LegalizedNodes.clear(); 00094 00095 // Remove dead nodes now. 00096 DAG.RemoveDeadNodes(); 00097 00098 return Changed; 00099 } 00100 00101 SDValue VectorLegalizer::TranslateLegalizeResults(SDValue Op, SDValue Result) { 00102 // Generic legalization: just pass the operand through. 00103 for (unsigned i = 0, e = Op.getNode()->getNumValues(); i != e; ++i) 00104 AddLegalizedOperand(Op.getValue(i), Result.getValue(i)); 00105 return Result.getValue(Op.getResNo()); 00106 } 00107 00108 SDValue VectorLegalizer::LegalizeOp(SDValue Op) { 00109 // Note that LegalizeOp may be reentered even from single-use nodes, which 00110 // means that we always must cache transformed nodes. 00111 DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op); 00112 if (I != LegalizedNodes.end()) return I->second; 00113 00114 SDNode* Node = Op.getNode(); 00115 00116 // Legalize the operands 00117 SmallVector<SDValue, 8> Ops; 00118 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) 00119 Ops.push_back(LegalizeOp(Node->getOperand(i))); 00120 00121 SDValue Result = 00122 DAG.UpdateNodeOperands(Op.getValue(0), Ops.data(), Ops.size()); 00123 00124 bool HasVectorValue = false; 00125 for (SDNode::value_iterator J = Node->value_begin(), E = Node->value_end(); 00126 J != E; 00127 ++J) 00128 HasVectorValue |= J->isVector(); 00129 if (!HasVectorValue) 00130 return TranslateLegalizeResults(Op, Result); 00131 00132 EVT QueryType; 00133 switch (Op.getOpcode()) { 00134 default: 00135 return TranslateLegalizeResults(Op, Result); 00136 case ISD::ADD: 00137 case ISD::SUB: 00138 case ISD::MUL: 00139 case ISD::SDIV: 00140 case ISD::UDIV: 00141 case ISD::SREM: 00142 case ISD::UREM: 00143 case ISD::FADD: 00144 case ISD::FSUB: 00145 case ISD::FMUL: 00146 case ISD::FDIV: 00147 case ISD::FREM: 00148 case ISD::AND: 00149 case ISD::OR: 00150 case ISD::XOR: 00151 case ISD::SHL: 00152 case ISD::SRA: 00153 case ISD::SRL: 00154 case ISD::ROTL: 00155 case ISD::ROTR: 00156 case ISD::CTTZ: 00157 case ISD::CTLZ: 00158 case ISD::CTPOP: 00159 case ISD::SELECT: 00160 case ISD::SELECT_CC: 00161 case ISD::VSETCC: 00162 case ISD::ZERO_EXTEND: 00163 case ISD::ANY_EXTEND: 00164 case ISD::TRUNCATE: 00165 case ISD::SIGN_EXTEND: 00166 case ISD::FP_TO_SINT: 00167 case ISD::FP_TO_UINT: 00168 case ISD::FNEG: 00169 case ISD::FABS: 00170 case ISD::FSQRT: 00171 case ISD::FSIN: 00172 case ISD::FCOS: 00173 case ISD::FPOWI: 00174 case ISD::FPOW: 00175 case ISD::FLOG: 00176 case ISD::FLOG2: 00177 case ISD::FLOG10: 00178 case ISD::FEXP: 00179 case ISD::FEXP2: 00180 case ISD::FCEIL: 00181 case ISD::FTRUNC: 00182 case ISD::FRINT: 00183 case ISD::FNEARBYINT: 00184 case ISD::FFLOOR: 00185 QueryType = Node->getValueType(0); 00186 break; 00187 case ISD::SINT_TO_FP: 00188 case ISD::UINT_TO_FP: 00189 QueryType = Node->getOperand(0).getValueType(); 00190 break; 00191 } 00192 00193 switch (TLI.getOperationAction(Node->getOpcode(), QueryType)) { 00194 case TargetLowering::Promote: 00195 // "Promote" the operation by bitcasting 00196 Result = PromoteVectorOp(Op); 00197 Changed = true; 00198 break; 00199 case TargetLowering::Legal: break; 00200 case TargetLowering::Custom: { 00201 SDValue Tmp1 = TLI.LowerOperation(Op, DAG); 00202 if (Tmp1.getNode()) { 00203 Result = Tmp1; 00204 break; 00205 } 00206 // FALL THROUGH 00207 } 00208 case TargetLowering::Expand: 00209 if (Node->getOpcode() == ISD::FNEG) 00210 Result = ExpandFNEG(Op); 00211 else if (Node->getOpcode() == ISD::VSETCC) 00212 Result = UnrollVSETCC(Op); 00213 else 00214 Result = UnrollVectorOp(Op); 00215 break; 00216 } 00217 00218 // Make sure that the generated code is itself legal. 00219 if (Result != Op) { 00220 Result = LegalizeOp(Result); 00221 Changed = true; 00222 } 00223 00224 // Note that LegalizeOp may be reentered even from single-use nodes, which 00225 // means that we always must cache transformed nodes. 00226 AddLegalizedOperand(Op, Result); 00227 return Result; 00228 } 00229 00230 SDValue VectorLegalizer::PromoteVectorOp(SDValue Op) { 00231 // Vector "promotion" is basically just bitcasting and doing the operation 00232 // in a different type. For example, x86 promotes ISD::AND on v2i32 to 00233 // v1i64. 00234 EVT VT = Op.getValueType(); 00235 assert(Op.getNode()->getNumValues() == 1 && 00236 "Can't promote a vector with multiple results!"); 00237 EVT NVT = TLI.getTypeToPromoteTo(Op.getOpcode(), VT); 00238 DebugLoc dl = Op.getDebugLoc(); 00239 SmallVector<SDValue, 4> Operands(Op.getNumOperands()); 00240 00241 for (unsigned j = 0; j != Op.getNumOperands(); ++j) { 00242 if (Op.getOperand(j).getValueType().isVector()) 00243 Operands[j] = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Op.getOperand(j)); 00244 else 00245 Operands[j] = Op.getOperand(j); 00246 } 00247 00248 Op = DAG.getNode(Op.getOpcode(), dl, NVT, &Operands[0], Operands.size()); 00249 00250 return DAG.getNode(ISD::BIT_CONVERT, dl, VT, Op); 00251 } 00252 00253 SDValue VectorLegalizer::ExpandFNEG(SDValue Op) { 00254 if (TLI.isOperationLegalOrCustom(ISD::FSUB, Op.getValueType())) { 00255 SDValue Zero = DAG.getConstantFP(-0.0, Op.getValueType()); 00256 return DAG.getNode(ISD::FSUB, Op.getDebugLoc(), Op.getValueType(), 00257 Zero, Op.getOperand(0)); 00258 } 00259 return UnrollVectorOp(Op); 00260 } 00261 00262 SDValue VectorLegalizer::UnrollVSETCC(SDValue Op) { 00263 EVT VT = Op.getValueType(); 00264 unsigned NumElems = VT.getVectorNumElements(); 00265 EVT EltVT = VT.getVectorElementType(); 00266 SDValue LHS = Op.getOperand(0), RHS = Op.getOperand(1), CC = Op.getOperand(2); 00267 EVT TmpEltVT = LHS.getValueType().getVectorElementType(); 00268 DebugLoc dl = Op.getDebugLoc(); 00269 SmallVector<SDValue, 8> Ops(NumElems); 00270 for (unsigned i = 0; i < NumElems; ++i) { 00271 SDValue LHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, LHS, 00272 DAG.getIntPtrConstant(i)); 00273 SDValue RHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, RHS, 00274 DAG.getIntPtrConstant(i)); 00275 Ops[i] = DAG.getNode(ISD::SETCC, dl, TLI.getSetCCResultType(TmpEltVT), 00276 LHSElem, RHSElem, CC); 00277 Ops[i] = DAG.getNode(ISD::SELECT, dl, EltVT, Ops[i], 00278 DAG.getConstant(APInt::getAllOnesValue 00279 (EltVT.getSizeInBits()), EltVT), 00280 DAG.getConstant(0, EltVT)); 00281 } 00282 return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], NumElems); 00283 } 00284 00285 /// UnrollVectorOp - We know that the given vector has a legal type, however 00286 /// the operation it performs is not legal, and the target has requested that 00287 /// the operation be expanded. "Unroll" the vector, splitting out the scalars 00288 /// and operating on each element individually. 00289 SDValue VectorLegalizer::UnrollVectorOp(SDValue Op) { 00290 EVT VT = Op.getValueType(); 00291 assert(Op.getNode()->getNumValues() == 1 && 00292 "Can't unroll a vector with multiple results!"); 00293 unsigned NE = VT.getVectorNumElements(); 00294 EVT EltVT = VT.getVectorElementType(); 00295 DebugLoc dl = Op.getDebugLoc(); 00296 00297 SmallVector<SDValue, 8> Scalars; 00298 SmallVector<SDValue, 4> Operands(Op.getNumOperands()); 00299 for (unsigned i = 0; i != NE; ++i) { 00300 for (unsigned j = 0; j != Op.getNumOperands(); ++j) { 00301 SDValue Operand = Op.getOperand(j); 00302 EVT OperandVT = Operand.getValueType(); 00303 if (OperandVT.isVector()) { 00304 // A vector operand; extract a single element. 00305 EVT OperandEltVT = OperandVT.getVectorElementType(); 00306 Operands[j] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, 00307 OperandEltVT, 00308 Operand, 00309 DAG.getConstant(i, MVT::i32)); 00310 } else { 00311 // A scalar operand; just use it as is. 00312 Operands[j] = Operand; 00313 } 00314 } 00315 00316 switch (Op.getOpcode()) { 00317 default: 00318 Scalars.push_back(DAG.getNode(Op.getOpcode(), dl, EltVT, 00319 &Operands[0], Operands.size())); 00320 break; 00321 case ISD::SHL: 00322 case ISD::SRA: 00323 case ISD::SRL: 00324 case ISD::ROTL: 00325 case ISD::ROTR: 00326 Scalars.push_back(DAG.getNode(Op.getOpcode(), dl, EltVT, Operands[0], 00327 DAG.getShiftAmountOperand(Operands[1]))); 00328 break; 00329 } 00330 } 00331 00332 return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Scalars[0], Scalars.size()); 00333 } 00334 00335 } 00336 00337 bool SelectionDAG::LegalizeVectors() { 00338 return VectorLegalizer(*this).Run(); 00339 }