LLVM API Documentation
00001 //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===// 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::Legalize method. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/CodeGen/SelectionDAG.h" 00015 #include "llvm/CodeGen/MachineFunction.h" 00016 #include "llvm/CodeGen/MachineFrameInfo.h" 00017 #include "llvm/CodeGen/MachineJumpTableInfo.h" 00018 #include "llvm/CodeGen/MachineModuleInfo.h" 00019 #include "llvm/CodeGen/DwarfWriter.h" 00020 #include "llvm/Analysis/DebugInfo.h" 00021 #include "llvm/CodeGen/PseudoSourceValue.h" 00022 #include "llvm/Target/TargetFrameInfo.h" 00023 #include "llvm/Target/TargetLowering.h" 00024 #include "llvm/Target/TargetData.h" 00025 #include "llvm/Target/TargetMachine.h" 00026 #include "llvm/Target/TargetOptions.h" 00027 #include "llvm/Target/TargetSubtarget.h" 00028 #include "llvm/CallingConv.h" 00029 #include "llvm/Constants.h" 00030 #include "llvm/DerivedTypes.h" 00031 #include "llvm/Function.h" 00032 #include "llvm/GlobalVariable.h" 00033 #include "llvm/LLVMContext.h" 00034 #include "llvm/Support/CommandLine.h" 00035 #include "llvm/Support/Compiler.h" 00036 #include "llvm/Support/ErrorHandling.h" 00037 #include "llvm/Support/MathExtras.h" 00038 #include "llvm/ADT/DenseMap.h" 00039 #include "llvm/ADT/SmallVector.h" 00040 #include "llvm/ADT/SmallPtrSet.h" 00041 #include <map> 00042 using namespace llvm; 00043 00044 //===----------------------------------------------------------------------===// 00045 /// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and 00046 /// hacks on it until the target machine can handle it. This involves 00047 /// eliminating value sizes the machine cannot handle (promoting small sizes to 00048 /// large sizes or splitting up large values into small values) as well as 00049 /// eliminating operations the machine cannot handle. 00050 /// 00051 /// This code also does a small amount of optimization and recognition of idioms 00052 /// as part of its processing. For example, if a target does not support a 00053 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this 00054 /// will attempt merge setcc and brc instructions into brcc's. 00055 /// 00056 namespace { 00057 class VISIBILITY_HIDDEN SelectionDAGLegalize { 00058 TargetLowering &TLI; 00059 SelectionDAG &DAG; 00060 CodeGenOpt::Level OptLevel; 00061 00062 // Libcall insertion helpers. 00063 00064 /// LastCALLSEQ_END - This keeps track of the CALLSEQ_END node that has been 00065 /// legalized. We use this to ensure that calls are properly serialized 00066 /// against each other, including inserted libcalls. 00067 SDValue LastCALLSEQ_END; 00068 00069 /// IsLegalizingCall - This member is used *only* for purposes of providing 00070 /// helpful assertions that a libcall isn't created while another call is 00071 /// being legalized (which could lead to non-serialized call sequences). 00072 bool IsLegalizingCall; 00073 00074 enum LegalizeAction { 00075 Legal, // The target natively supports this operation. 00076 Promote, // This operation should be executed in a larger type. 00077 Expand // Try to expand this to other ops, otherwise use a libcall. 00078 }; 00079 00080 /// ValueTypeActions - This is a bitvector that contains two bits for each 00081 /// value type, where the two bits correspond to the LegalizeAction enum. 00082 /// This can be queried with "getTypeAction(VT)". 00083 TargetLowering::ValueTypeActionImpl ValueTypeActions; 00084 00085 /// LegalizedNodes - For nodes that are of legal width, and that have more 00086 /// than one use, this map indicates what regularized operand to use. This 00087 /// allows us to avoid legalizing the same thing more than once. 00088 DenseMap<SDValue, SDValue> LegalizedNodes; 00089 00090 void AddLegalizedOperand(SDValue From, SDValue To) { 00091 LegalizedNodes.insert(std::make_pair(From, To)); 00092 // If someone requests legalization of the new node, return itself. 00093 if (From != To) 00094 LegalizedNodes.insert(std::make_pair(To, To)); 00095 } 00096 00097 public: 00098 SelectionDAGLegalize(SelectionDAG &DAG, CodeGenOpt::Level ol); 00099 00100 /// getTypeAction - Return how we should legalize values of this type, either 00101 /// it is already legal or we need to expand it into multiple registers of 00102 /// smaller integer type, or we need to promote it to a larger type. 00103 LegalizeAction getTypeAction(EVT VT) const { 00104 return 00105 (LegalizeAction)ValueTypeActions.getTypeAction(*DAG.getContext(), VT); 00106 } 00107 00108 /// isTypeLegal - Return true if this type is legal on this target. 00109 /// 00110 bool isTypeLegal(EVT VT) const { 00111 return getTypeAction(VT) == Legal; 00112 } 00113 00114 void LegalizeDAG(); 00115 00116 private: 00117 /// LegalizeOp - We know that the specified value has a legal type. 00118 /// Recursively ensure that the operands have legal types, then return the 00119 /// result. 00120 SDValue LegalizeOp(SDValue O); 00121 00122 SDValue OptimizeFloatStore(StoreSDNode *ST); 00123 00124 /// PerformInsertVectorEltInMemory - Some target cannot handle a variable 00125 /// insertion index for the INSERT_VECTOR_ELT instruction. In this case, it 00126 /// is necessary to spill the vector being inserted into to memory, perform 00127 /// the insert there, and then read the result back. 00128 SDValue PerformInsertVectorEltInMemory(SDValue Vec, SDValue Val, 00129 SDValue Idx, DebugLoc dl); 00130 SDValue ExpandINSERT_VECTOR_ELT(SDValue Vec, SDValue Val, 00131 SDValue Idx, DebugLoc dl); 00132 00133 /// ShuffleWithNarrowerEltType - Return a vector shuffle operation which 00134 /// performs the same shuffe in terms of order or result bytes, but on a type 00135 /// whose vector element type is narrower than the original shuffle type. 00136 /// e.g. <v4i32> <0, 1, 0, 1> -> v8i16 <0, 1, 2, 3, 0, 1, 2, 3> 00137 SDValue ShuffleWithNarrowerEltType(EVT NVT, EVT VT, DebugLoc dl, 00138 SDValue N1, SDValue N2, 00139 SmallVectorImpl<int> &Mask) const; 00140 00141 bool LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest, 00142 SmallPtrSet<SDNode*, 32> &NodesLeadingTo); 00143 00144 void LegalizeSetCCCondCode(EVT VT, SDValue &LHS, SDValue &RHS, SDValue &CC, 00145 DebugLoc dl); 00146 00147 SDValue ExpandLibCall(RTLIB::Libcall LC, SDNode *Node, bool isSigned); 00148 SDValue ExpandFPLibCall(SDNode *Node, RTLIB::Libcall Call_F32, 00149 RTLIB::Libcall Call_F64, RTLIB::Libcall Call_F80, 00150 RTLIB::Libcall Call_PPCF128); 00151 SDValue ExpandIntLibCall(SDNode *Node, bool isSigned, RTLIB::Libcall Call_I16, 00152 RTLIB::Libcall Call_I32, RTLIB::Libcall Call_I64, 00153 RTLIB::Libcall Call_I128); 00154 00155 SDValue EmitStackConvert(SDValue SrcOp, EVT SlotVT, EVT DestVT, DebugLoc dl); 00156 SDValue ExpandBUILD_VECTOR(SDNode *Node); 00157 SDValue ExpandSCALAR_TO_VECTOR(SDNode *Node); 00158 SDValue ExpandDBG_STOPPOINT(SDNode *Node); 00159 void ExpandDYNAMIC_STACKALLOC(SDNode *Node, 00160 SmallVectorImpl<SDValue> &Results); 00161 SDValue ExpandFCOPYSIGN(SDNode *Node); 00162 SDValue ExpandLegalINT_TO_FP(bool isSigned, SDValue LegalOp, EVT DestVT, 00163 DebugLoc dl); 00164 SDValue PromoteLegalINT_TO_FP(SDValue LegalOp, EVT DestVT, bool isSigned, 00165 DebugLoc dl); 00166 SDValue PromoteLegalFP_TO_INT(SDValue LegalOp, EVT DestVT, bool isSigned, 00167 DebugLoc dl); 00168 00169 SDValue ExpandBSWAP(SDValue Op, DebugLoc dl); 00170 SDValue ExpandBitCount(unsigned Opc, SDValue Op, DebugLoc dl); 00171 00172 SDValue ExpandExtractFromVectorThroughStack(SDValue Op); 00173 SDValue ExpandVectorBuildThroughStack(SDNode* Node); 00174 00175 void ExpandNode(SDNode *Node, SmallVectorImpl<SDValue> &Results); 00176 void PromoteNode(SDNode *Node, SmallVectorImpl<SDValue> &Results); 00177 }; 00178 } 00179 00180 /// ShuffleWithNarrowerEltType - Return a vector shuffle operation which 00181 /// performs the same shuffe in terms of order or result bytes, but on a type 00182 /// whose vector element type is narrower than the original shuffle type. 00183 /// e.g. <v4i32> <0, 1, 0, 1> -> v8i16 <0, 1, 2, 3, 0, 1, 2, 3> 00184 SDValue 00185 SelectionDAGLegalize::ShuffleWithNarrowerEltType(EVT NVT, EVT VT, DebugLoc dl, 00186 SDValue N1, SDValue N2, 00187 SmallVectorImpl<int> &Mask) const { 00188 EVT EltVT = NVT.getVectorElementType(); 00189 unsigned NumMaskElts = VT.getVectorNumElements(); 00190 unsigned NumDestElts = NVT.getVectorNumElements(); 00191 unsigned NumEltsGrowth = NumDestElts / NumMaskElts; 00192 00193 assert(NumEltsGrowth && "Cannot promote to vector type with fewer elts!"); 00194 00195 if (NumEltsGrowth == 1) 00196 return DAG.getVectorShuffle(NVT, dl, N1, N2, &Mask[0]); 00197 00198 SmallVector<int, 8> NewMask; 00199 for (unsigned i = 0; i != NumMaskElts; ++i) { 00200 int Idx = Mask[i]; 00201 for (unsigned j = 0; j != NumEltsGrowth; ++j) { 00202 if (Idx < 0) 00203 NewMask.push_back(-1); 00204 else 00205 NewMask.push_back(Idx * NumEltsGrowth + j); 00206 } 00207 } 00208 assert(NewMask.size() == NumDestElts && "Non-integer NumEltsGrowth?"); 00209 assert(TLI.isShuffleMaskLegal(NewMask, NVT) && "Shuffle not legal?"); 00210 return DAG.getVectorShuffle(NVT, dl, N1, N2, &NewMask[0]); 00211 } 00212 00213 SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag, 00214 CodeGenOpt::Level ol) 00215 : TLI(dag.getTargetLoweringInfo()), DAG(dag), OptLevel(ol), 00216 ValueTypeActions(TLI.getValueTypeActions()) { 00217 assert(MVT::LAST_VALUETYPE <= MVT::MAX_ALLOWED_VALUETYPE && 00218 "Too many value types for ValueTypeActions to hold!"); 00219 } 00220 00221 void SelectionDAGLegalize::LegalizeDAG() { 00222 LastCALLSEQ_END = DAG.getEntryNode(); 00223 IsLegalizingCall = false; 00224 00225 // The legalize process is inherently a bottom-up recursive process (users 00226 // legalize their uses before themselves). Given infinite stack space, we 00227 // could just start legalizing on the root and traverse the whole graph. In 00228 // practice however, this causes us to run out of stack space on large basic 00229 // blocks. To avoid this problem, compute an ordering of the nodes where each 00230 // node is only legalized after all of its operands are legalized. 00231 DAG.AssignTopologicalOrder(); 00232 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 00233 E = prior(DAG.allnodes_end()); I != next(E); ++I) 00234 LegalizeOp(SDValue(I, 0)); 00235 00236 // Finally, it's possible the root changed. Get the new root. 00237 SDValue OldRoot = DAG.getRoot(); 00238 assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?"); 00239 DAG.setRoot(LegalizedNodes[OldRoot]); 00240 00241 LegalizedNodes.clear(); 00242 00243 // Remove dead nodes now. 00244 DAG.RemoveDeadNodes(); 00245 } 00246 00247 00248 /// FindCallEndFromCallStart - Given a chained node that is part of a call 00249 /// sequence, find the CALLSEQ_END node that terminates the call sequence. 00250 static SDNode *FindCallEndFromCallStart(SDNode *Node) { 00251 if (Node->getOpcode() == ISD::CALLSEQ_END) 00252 return Node; 00253 if (Node->use_empty()) 00254 return 0; // No CallSeqEnd 00255 00256 // The chain is usually at the end. 00257 SDValue TheChain(Node, Node->getNumValues()-1); 00258 if (TheChain.getValueType() != MVT::Other) { 00259 // Sometimes it's at the beginning. 00260 TheChain = SDValue(Node, 0); 00261 if (TheChain.getValueType() != MVT::Other) { 00262 // Otherwise, hunt for it. 00263 for (unsigned i = 1, e = Node->getNumValues(); i != e; ++i) 00264 if (Node->getValueType(i) == MVT::Other) { 00265 TheChain = SDValue(Node, i); 00266 break; 00267 } 00268 00269 // Otherwise, we walked into a node without a chain. 00270 if (TheChain.getValueType() != MVT::Other) 00271 return 0; 00272 } 00273 } 00274 00275 for (SDNode::use_iterator UI = Node->use_begin(), 00276 E = Node->use_end(); UI != E; ++UI) { 00277 00278 // Make sure to only follow users of our token chain. 00279 SDNode *User = *UI; 00280 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 00281 if (User->getOperand(i) == TheChain) 00282 if (SDNode *Result = FindCallEndFromCallStart(User)) 00283 return Result; 00284 } 00285 return 0; 00286 } 00287 00288 /// FindCallStartFromCallEnd - Given a chained node that is part of a call 00289 /// sequence, find the CALLSEQ_START node that initiates the call sequence. 00290 static SDNode *FindCallStartFromCallEnd(SDNode *Node) { 00291 assert(Node && "Didn't find callseq_start for a call??"); 00292 if (Node->getOpcode() == ISD::CALLSEQ_START) return Node; 00293 00294 assert(Node->getOperand(0).getValueType() == MVT::Other && 00295 "Node doesn't have a token chain argument!"); 00296 return FindCallStartFromCallEnd(Node->getOperand(0).getNode()); 00297 } 00298 00299 /// LegalizeAllNodesNotLeadingTo - Recursively walk the uses of N, looking to 00300 /// see if any uses can reach Dest. If no dest operands can get to dest, 00301 /// legalize them, legalize ourself, and return false, otherwise, return true. 00302 /// 00303 /// Keep track of the nodes we fine that actually do lead to Dest in 00304 /// NodesLeadingTo. This avoids retraversing them exponential number of times. 00305 /// 00306 bool SelectionDAGLegalize::LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest, 00307 SmallPtrSet<SDNode*, 32> &NodesLeadingTo) { 00308 if (N == Dest) return true; // N certainly leads to Dest :) 00309 00310 // If we've already processed this node and it does lead to Dest, there is no 00311 // need to reprocess it. 00312 if (NodesLeadingTo.count(N)) return true; 00313 00314 // If the first result of this node has been already legalized, then it cannot 00315 // reach N. 00316 if (LegalizedNodes.count(SDValue(N, 0))) return false; 00317 00318 // Okay, this node has not already been legalized. Check and legalize all 00319 // operands. If none lead to Dest, then we can legalize this node. 00320 bool OperandsLeadToDest = false; 00321 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 00322 OperandsLeadToDest |= // If an operand leads to Dest, so do we. 00323 LegalizeAllNodesNotLeadingTo(N->getOperand(i).getNode(), Dest, NodesLeadingTo); 00324 00325 if (OperandsLeadToDest) { 00326 NodesLeadingTo.insert(N); 00327 return true; 00328 } 00329 00330 // Okay, this node looks safe, legalize it and return false. 00331 LegalizeOp(SDValue(N, 0)); 00332 return false; 00333 } 00334 00335 /// ExpandConstantFP - Expands the ConstantFP node to an integer constant or 00336 /// a load from the constant pool. 00337 static SDValue ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP, 00338 SelectionDAG &DAG, const TargetLowering &TLI) { 00339 bool Extend = false; 00340 DebugLoc dl = CFP->getDebugLoc(); 00341 00342 // If a FP immediate is precise when represented as a float and if the 00343 // target can do an extending load from float to double, we put it into 00344 // the constant pool as a float, even if it's is statically typed as a 00345 // double. This shrinks FP constants and canonicalizes them for targets where 00346 // an FP extending load is the same cost as a normal load (such as on the x87 00347 // fp stack or PPC FP unit). 00348 EVT VT = CFP->getValueType(0); 00349 ConstantFP *LLVMC = const_cast<ConstantFP*>(CFP->getConstantFPValue()); 00350 if (!UseCP) { 00351 assert((VT == MVT::f64 || VT == MVT::f32) && "Invalid type expansion"); 00352 return DAG.getConstant(LLVMC->getValueAPF().bitcastToAPInt(), 00353 (VT == MVT::f64) ? MVT::i64 : MVT::i32); 00354 } 00355 00356 EVT OrigVT = VT; 00357 EVT SVT = VT; 00358 while (SVT != MVT::f32) { 00359 SVT = (MVT::SimpleValueType)(SVT.getSimpleVT().SimpleTy - 1); 00360 if (CFP->isValueValidForType(SVT, CFP->getValueAPF()) && 00361 // Only do this if the target has a native EXTLOAD instruction from 00362 // smaller type. 00363 TLI.isLoadExtLegal(ISD::EXTLOAD, SVT) && 00364 TLI.ShouldShrinkFPConstant(OrigVT)) { 00365 const Type *SType = SVT.getTypeForEVT(*DAG.getContext()); 00366 LLVMC = cast<ConstantFP>(ConstantExpr::getFPTrunc(LLVMC, SType)); 00367 VT = SVT; 00368 Extend = true; 00369 } 00370 } 00371 00372 SDValue CPIdx = DAG.getConstantPool(LLVMC, TLI.getPointerTy()); 00373 unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment(); 00374 if (Extend) 00375 return DAG.getExtLoad(ISD::EXTLOAD, dl, 00376 OrigVT, DAG.getEntryNode(), 00377 CPIdx, PseudoSourceValue::getConstantPool(), 00378 0, VT, false, Alignment); 00379 return DAG.getLoad(OrigVT, dl, DAG.getEntryNode(), CPIdx, 00380 PseudoSourceValue::getConstantPool(), 0, false, Alignment); 00381 } 00382 00383 /// ExpandUnalignedStore - Expands an unaligned store to 2 half-size stores. 00384 static 00385 SDValue ExpandUnalignedStore(StoreSDNode *ST, SelectionDAG &DAG, 00386 const TargetLowering &TLI) { 00387 SDValue Chain = ST->getChain(); 00388 SDValue Ptr = ST->getBasePtr(); 00389 SDValue Val = ST->getValue(); 00390 EVT VT = Val.getValueType(); 00391 int Alignment = ST->getAlignment(); 00392 int SVOffset = ST->getSrcValueOffset(); 00393 DebugLoc dl = ST->getDebugLoc(); 00394 if (ST->getMemoryVT().isFloatingPoint() || 00395 ST->getMemoryVT().isVector()) { 00396 EVT intVT = EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits()); 00397 if (TLI.isTypeLegal(intVT)) { 00398 // Expand to a bitconvert of the value to the integer type of the 00399 // same size, then a (misaligned) int store. 00400 // FIXME: Does not handle truncating floating point stores! 00401 SDValue Result = DAG.getNode(ISD::BIT_CONVERT, dl, intVT, Val); 00402 return DAG.getStore(Chain, dl, Result, Ptr, ST->getSrcValue(), 00403 SVOffset, ST->isVolatile(), Alignment); 00404 } else { 00405 // Do a (aligned) store to a stack slot, then copy from the stack slot 00406 // to the final destination using (unaligned) integer loads and stores. 00407 EVT StoredVT = ST->getMemoryVT(); 00408 EVT RegVT = 00409 TLI.getRegisterType(*DAG.getContext(), EVT::getIntegerVT(*DAG.getContext(), StoredVT.getSizeInBits())); 00410 unsigned StoredBytes = StoredVT.getSizeInBits() / 8; 00411 unsigned RegBytes = RegVT.getSizeInBits() / 8; 00412 unsigned NumRegs = (StoredBytes + RegBytes - 1) / RegBytes; 00413 00414 // Make sure the stack slot is also aligned for the register type. 00415 SDValue StackPtr = DAG.CreateStackTemporary(StoredVT, RegVT); 00416 00417 // Perform the original store, only redirected to the stack slot. 00418 SDValue Store = DAG.getTruncStore(Chain, dl, 00419 Val, StackPtr, NULL, 0, StoredVT); 00420 SDValue Increment = DAG.getConstant(RegBytes, TLI.getPointerTy()); 00421 SmallVector<SDValue, 8> Stores; 00422 unsigned Offset = 0; 00423 00424 // Do all but one copies using the full register width. 00425 for (unsigned i = 1; i < NumRegs; i++) { 00426 // Load one integer register's worth from the stack slot. 00427 SDValue Load = DAG.getLoad(RegVT, dl, Store, StackPtr, NULL, 0); 00428 // Store it to the final location. Remember the store. 00429 Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, Ptr, 00430 ST->getSrcValue(), SVOffset + Offset, 00431 ST->isVolatile(), 00432 MinAlign(ST->getAlignment(), Offset))); 00433 // Increment the pointers. 00434 Offset += RegBytes; 00435 StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr, 00436 Increment); 00437 Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr, Increment); 00438 } 00439 00440 // The last store may be partial. Do a truncating store. On big-endian 00441 // machines this requires an extending load from the stack slot to ensure 00442 // that the bits are in the right place. 00443 EVT MemVT = EVT::getIntegerVT(*DAG.getContext(), 8 * (StoredBytes - Offset)); 00444 00445 // Load from the stack slot. 00446 SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Store, StackPtr, 00447 NULL, 0, MemVT); 00448 00449 Stores.push_back(DAG.getTruncStore(Load.getValue(1), dl, Load, Ptr, 00450 ST->getSrcValue(), SVOffset + Offset, 00451 MemVT, ST->isVolatile(), 00452 MinAlign(ST->getAlignment(), Offset))); 00453 // The order of the stores doesn't matter - say it with a TokenFactor. 00454 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, &Stores[0], 00455 Stores.size()); 00456 } 00457 } 00458 assert(ST->getMemoryVT().isInteger() && 00459 !ST->getMemoryVT().isVector() && 00460 "Unaligned store of unknown type."); 00461 // Get the half-size VT 00462 EVT NewStoredVT = 00463 (MVT::SimpleValueType)(ST->getMemoryVT().getSimpleVT().SimpleTy - 1); 00464 int NumBits = NewStoredVT.getSizeInBits(); 00465 int IncrementSize = NumBits / 8; 00466 00467 // Divide the stored value in two parts. 00468 SDValue ShiftAmount = DAG.getConstant(NumBits, TLI.getShiftAmountTy()); 00469 SDValue Lo = Val; 00470 SDValue Hi = DAG.getNode(ISD::SRL, dl, VT, Val, ShiftAmount); 00471 00472 // Store the two parts 00473 SDValue Store1, Store2; 00474 Store1 = DAG.getTruncStore(Chain, dl, TLI.isLittleEndian()?Lo:Hi, Ptr, 00475 ST->getSrcValue(), SVOffset, NewStoredVT, 00476 ST->isVolatile(), Alignment); 00477 Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr, 00478 DAG.getConstant(IncrementSize, TLI.getPointerTy())); 00479 Alignment = MinAlign(Alignment, IncrementSize); 00480 Store2 = DAG.getTruncStore(Chain, dl, TLI.isLittleEndian()?Hi:Lo, Ptr, 00481 ST->getSrcValue(), SVOffset + IncrementSize, 00482 NewStoredVT, ST->isVolatile(), Alignment); 00483 00484 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Store1, Store2); 00485 } 00486 00487 /// ExpandUnalignedLoad - Expands an unaligned load to 2 half-size loads. 00488 static 00489 SDValue ExpandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG, 00490 const TargetLowering &TLI) { 00491 int SVOffset = LD->getSrcValueOffset(); 00492 SDValue Chain = LD->getChain(); 00493 SDValue Ptr = LD->getBasePtr(); 00494 EVT VT = LD->getValueType(0); 00495 EVT LoadedVT = LD->getMemoryVT(); 00496 DebugLoc dl = LD->getDebugLoc(); 00497 if (VT.isFloatingPoint() || VT.isVector()) { 00498 EVT intVT = EVT::getIntegerVT(*DAG.getContext(), LoadedVT.getSizeInBits()); 00499 if (TLI.isTypeLegal(intVT)) { 00500 // Expand to a (misaligned) integer load of the same size, 00501 // then bitconvert to floating point or vector. 00502 SDValue newLoad = DAG.getLoad(intVT, dl, Chain, Ptr, LD->getSrcValue(), 00503 SVOffset, LD->isVolatile(), 00504 LD->getAlignment()); 00505 SDValue Result = DAG.getNode(ISD::BIT_CONVERT, dl, LoadedVT, newLoad); 00506 if (VT.isFloatingPoint() && LoadedVT != VT) 00507 Result = DAG.getNode(ISD::FP_EXTEND, dl, VT, Result); 00508 00509 SDValue Ops[] = { Result, Chain }; 00510 return DAG.getMergeValues(Ops, 2, dl); 00511 } else { 00512 // Copy the value to a (aligned) stack slot using (unaligned) integer 00513 // loads and stores, then do a (aligned) load from the stack slot. 00514 EVT RegVT = TLI.getRegisterType(*DAG.getContext(), intVT); 00515 unsigned LoadedBytes = LoadedVT.getSizeInBits() / 8; 00516 unsigned RegBytes = RegVT.getSizeInBits() / 8; 00517 unsigned NumRegs = (LoadedBytes + RegBytes - 1) / RegBytes; 00518 00519 // Make sure the stack slot is also aligned for the register type. 00520 SDValue StackBase = DAG.CreateStackTemporary(LoadedVT, RegVT); 00521 00522 SDValue Increment = DAG.getConstant(RegBytes, TLI.getPointerTy()); 00523 SmallVector<SDValue, 8> Stores; 00524 SDValue StackPtr = StackBase; 00525 unsigned Offset = 0; 00526 00527 // Do all but one copies using the full register width. 00528 for (unsigned i = 1; i < NumRegs; i++) { 00529 // Load one integer register's worth from the original location. 00530 SDValue Load = DAG.getLoad(RegVT, dl, Chain, Ptr, LD->getSrcValue(), 00531 SVOffset + Offset, LD->isVolatile(), 00532 MinAlign(LD->getAlignment(), Offset)); 00533 // Follow the load with a store to the stack slot. Remember the store. 00534 Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, StackPtr, 00535 NULL, 0)); 00536 // Increment the pointers. 00537 Offset += RegBytes; 00538 Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr, Increment); 00539 StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr, 00540 Increment); 00541 } 00542 00543 // The last copy may be partial. Do an extending load. 00544 EVT MemVT = EVT::getIntegerVT(*DAG.getContext(), 8 * (LoadedBytes - Offset)); 00545 SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Chain, Ptr, 00546 LD->getSrcValue(), SVOffset + Offset, 00547 MemVT, LD->isVolatile(), 00548 MinAlign(LD->getAlignment(), Offset)); 00549 // Follow the load with a store to the stack slot. Remember the store. 00550 // On big-endian machines this requires a truncating store to ensure 00551 // that the bits end up in the right place. 00552 Stores.push_back(DAG.getTruncStore(Load.getValue(1), dl, Load, StackPtr, 00553 NULL, 0, MemVT)); 00554 00555 // The order of the stores doesn't matter - say it with a TokenFactor. 00556 SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, &Stores[0], 00557 Stores.size()); 00558 00559 // Finally, perform the original load only redirected to the stack slot. 00560 Load = DAG.getExtLoad(LD->getExtensionType(), dl, VT, TF, StackBase, 00561 NULL, 0, LoadedVT); 00562 00563 // Callers expect a MERGE_VALUES node. 00564 SDValue Ops[] = { Load, TF }; 00565 return DAG.getMergeValues(Ops, 2, dl); 00566 } 00567 } 00568 assert(LoadedVT.isInteger() && !LoadedVT.isVector() && 00569 "Unaligned load of unsupported type."); 00570 00571 // Compute the new VT that is half the size of the old one. This is an 00572 // integer MVT. 00573 unsigned NumBits = LoadedVT.getSizeInBits(); 00574 EVT NewLoadedVT; 00575 NewLoadedVT = EVT::getIntegerVT(*DAG.getContext(), NumBits/2); 00576 NumBits >>= 1; 00577 00578 unsigned Alignment = LD->getAlignment(); 00579 unsigned IncrementSize = NumBits / 8; 00580 ISD::LoadExtType HiExtType = LD->getExtensionType(); 00581 00582 // If the original load is NON_EXTLOAD, the hi part load must be ZEXTLOAD. 00583 if (HiExtType == ISD::NON_EXTLOAD) 00584 HiExtType = ISD::ZEXTLOAD; 00585 00586 // Load the value in two parts 00587 SDValue Lo, Hi; 00588 if (TLI.isLittleEndian()) { 00589 Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr, LD->getSrcValue(), 00590 SVOffset, NewLoadedVT, LD->isVolatile(), Alignment); 00591 Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr, 00592 DAG.getConstant(IncrementSize, TLI.getPointerTy())); 00593 Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr, LD->getSrcValue(), 00594 SVOffset + IncrementSize, NewLoadedVT, LD->isVolatile(), 00595 MinAlign(Alignment, IncrementSize)); 00596 } else { 00597 Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr, LD->getSrcValue(), 00598 SVOffset, NewLoadedVT, LD->isVolatile(), Alignment); 00599 Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr, 00600 DAG.getConstant(IncrementSize, TLI.getPointerTy())); 00601 Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr, LD->getSrcValue(), 00602 SVOffset + IncrementSize, NewLoadedVT, LD->isVolatile(), 00603 MinAlign(Alignment, IncrementSize)); 00604 } 00605 00606 // aggregate the two parts 00607 SDValue ShiftAmount = DAG.getConstant(NumBits, TLI.getShiftAmountTy()); 00608 SDValue Result = DAG.getNode(ISD::SHL, dl, VT, Hi, ShiftAmount); 00609 Result = DAG.getNode(ISD::OR, dl, VT, Result, Lo); 00610 00611 SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1), 00612 Hi.getValue(1)); 00613 00614 SDValue Ops[] = { Result, TF }; 00615 return DAG.getMergeValues(Ops, 2, dl); 00616 } 00617 00618 /// PerformInsertVectorEltInMemory - Some target cannot handle a variable 00619 /// insertion index for the INSERT_VECTOR_ELT instruction. In this case, it 00620 /// is necessary to spill the vector being inserted into to memory, perform 00621 /// the insert there, and then read the result back. 00622 SDValue SelectionDAGLegalize:: 00623 PerformInsertVectorEltInMemory(SDValue Vec, SDValue Val, SDValue Idx, 00624 DebugLoc dl) { 00625 SDValue Tmp1 = Vec; 00626 SDValue Tmp2 = Val; 00627 SDValue Tmp3 = Idx; 00628 00629 // If the target doesn't support this, we have to spill the input vector 00630 // to a temporary stack slot, update the element, then reload it. This is 00631 // badness. We could also load the value into a vector register (either 00632 // with a "move to register" or "extload into register" instruction, then 00633 // permute it into place, if the idx is a constant and if the idx is 00634 // supported by the target. 00635 EVT VT = Tmp1.getValueType(); 00636 EVT EltVT = VT.getVectorElementType(); 00637 EVT IdxVT = Tmp3.getValueType(); 00638 EVT PtrVT = TLI.getPointerTy(); 00639 SDValue StackPtr = DAG.CreateStackTemporary(VT); 00640 00641 int SPFI = cast<FrameIndexSDNode>(StackPtr.getNode())->getIndex(); 00642 00643 // Store the vector. 00644 SDValue Ch = DAG.getStore(DAG.getEntryNode(), dl, Tmp1, StackPtr, 00645 PseudoSourceValue::getFixedStack(SPFI), 0); 00646 00647 // Truncate or zero extend offset to target pointer type. 00648 unsigned CastOpc = IdxVT.bitsGT(PtrVT) ? ISD::TRUNCATE : ISD::ZERO_EXTEND; 00649 Tmp3 = DAG.getNode(CastOpc, dl, PtrVT, Tmp3); 00650 // Add the offset to the index. 00651 unsigned EltSize = EltVT.getSizeInBits()/8; 00652 Tmp3 = DAG.getNode(ISD::MUL, dl, IdxVT, Tmp3,DAG.getConstant(EltSize, IdxVT)); 00653 SDValue StackPtr2 = DAG.getNode(ISD::ADD, dl, IdxVT, Tmp3, StackPtr); 00654 // Store the scalar value. 00655 Ch = DAG.getTruncStore(Ch, dl, Tmp2, StackPtr2, 00656 PseudoSourceValue::getFixedStack(SPFI), 0, EltVT); 00657 // Load the updated vector. 00658 return DAG.getLoad(VT, dl, Ch, StackPtr, 00659 PseudoSourceValue::getFixedStack(SPFI), 0); 00660 } 00661 00662 00663 SDValue SelectionDAGLegalize:: 00664 ExpandINSERT_VECTOR_ELT(SDValue Vec, SDValue Val, SDValue Idx, DebugLoc dl) { 00665 if (ConstantSDNode *InsertPos = dyn_cast<ConstantSDNode>(Idx)) { 00666 // SCALAR_TO_VECTOR requires that the type of the value being inserted 00667 // match the element type of the vector being created, except for 00668 // integers in which case the inserted value can be over width. 00669 EVT EltVT = Vec.getValueType().getVectorElementType(); 00670 if (Val.getValueType() == EltVT || 00671 (EltVT.isInteger() && Val.getValueType().bitsGE(EltVT))) { 00672 SDValue ScVec = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, 00673 Vec.getValueType(), Val); 00674 00675 unsigned NumElts = Vec.getValueType().getVectorNumElements(); 00676 // We generate a shuffle of InVec and ScVec, so the shuffle mask 00677 // should be 0,1,2,3,4,5... with the appropriate element replaced with 00678 // elt 0 of the RHS. 00679 SmallVector<int, 8> ShufOps; 00680 for (unsigned i = 0; i != NumElts; ++i) 00681 ShufOps.push_back(i != InsertPos->getZExtValue() ? i : NumElts); 00682 00683 return DAG.getVectorShuffle(Vec.getValueType(), dl, Vec, ScVec, 00684 &ShufOps[0]); 00685 } 00686 } 00687 return PerformInsertVectorEltInMemory(Vec, Val, Idx, dl); 00688 } 00689 00690 SDValue SelectionDAGLegalize::OptimizeFloatStore(StoreSDNode* ST) { 00691 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 00692 // FIXME: We shouldn't do this for TargetConstantFP's. 00693 // FIXME: move this to the DAG Combiner! Note that we can't regress due 00694 // to phase ordering between legalized code and the dag combiner. This 00695 // probably means that we need to integrate dag combiner and legalizer 00696 // together. 00697 // We generally can't do this one for long doubles. 00698 SDValue Tmp1 = ST->getChain(); 00699 SDValue Tmp2 = ST->getBasePtr(); 00700 SDValue Tmp3; 00701 int SVOffset = ST->getSrcValueOffset(); 00702 unsigned Alignment = ST->getAlignment(); 00703 bool isVolatile = ST->isVolatile(); 00704 DebugLoc dl = ST->getDebugLoc(); 00705 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(ST->getValue())) { 00706 if (CFP->getValueType(0) == MVT::f32 && 00707 getTypeAction(MVT::i32) == Legal) { 00708 Tmp3 = DAG.getConstant(CFP->getValueAPF(). 00709 bitcastToAPInt().zextOrTrunc(32), 00710 MVT::i32); 00711 return DAG.getStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(), 00712 SVOffset, isVolatile, Alignment); 00713 } else if (CFP->getValueType(0) == MVT::f64) { 00714 // If this target supports 64-bit registers, do a single 64-bit store. 00715 if (getTypeAction(MVT::i64) == Legal) { 00716 Tmp3 = DAG.getConstant(CFP->getValueAPF().bitcastToAPInt(). 00717 zextOrTrunc(64), MVT::i64); 00718 return DAG.getStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(), 00719 SVOffset, isVolatile, Alignment); 00720 } else if (getTypeAction(MVT::i32) == Legal && !ST->isVolatile()) { 00721 // Otherwise, if the target supports 32-bit registers, use 2 32-bit 00722 // stores. If the target supports neither 32- nor 64-bits, this 00723 // xform is certainly not worth it. 00724 const APInt &IntVal =CFP->getValueAPF().bitcastToAPInt(); 00725 SDValue Lo = DAG.getConstant(APInt(IntVal).trunc(32), MVT::i32); 00726 SDValue Hi = DAG.getConstant(IntVal.lshr(32).trunc(32), MVT::i32); 00727 if (TLI.isBigEndian()) std::swap(Lo, Hi); 00728 00729 Lo = DAG.getStore(Tmp1, dl, Lo, Tmp2, ST->getSrcValue(), 00730 SVOffset, isVolatile, Alignment); 00731 Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2, 00732 DAG.getIntPtrConstant(4)); 00733 Hi = DAG.getStore(Tmp1, dl, Hi, Tmp2, ST->getSrcValue(), SVOffset+4, 00734 isVolatile, MinAlign(Alignment, 4U)); 00735 00736 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi); 00737 } 00738 } 00739 } 00740 return SDValue(); 00741 } 00742 00743 /// LegalizeOp - We know that the specified value has a legal type, and 00744 /// that its operands are legal. Now ensure that the operation itself 00745 /// is legal, recursively ensuring that the operands' operations remain 00746 /// legal. 00747 SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) { 00748 if (Op.getOpcode() == ISD::TargetConstant) // Allow illegal target nodes. 00749 return Op; 00750 00751 SDNode *Node = Op.getNode(); 00752 DebugLoc dl = Node->getDebugLoc(); 00753 00754 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 00755 assert(getTypeAction(Node->getValueType(i)) == Legal && 00756 "Unexpected illegal type!"); 00757 00758 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) 00759 assert((isTypeLegal(Node->getOperand(i).getValueType()) || 00760 Node->getOperand(i).getOpcode() == ISD::TargetConstant) && 00761 "Unexpected illegal type!"); 00762 00763 // Note that LegalizeOp may be reentered even from single-use nodes, which 00764 // means that we always must cache transformed nodes. 00765 DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op); 00766 if (I != LegalizedNodes.end()) return I->second; 00767 00768 SDValue Tmp1, Tmp2, Tmp3, Tmp4; 00769 SDValue Result = Op; 00770 bool isCustom = false; 00771 00772 // Figure out the correct action; the way to query this varies by opcode 00773 TargetLowering::LegalizeAction Action; 00774 bool SimpleFinishLegalizing = true; 00775 switch (Node->getOpcode()) { 00776 case ISD::INTRINSIC_W_CHAIN: 00777 case ISD::INTRINSIC_WO_CHAIN: 00778 case ISD::INTRINSIC_VOID: 00779 case ISD::VAARG: 00780 case ISD::STACKSAVE: 00781 Action = TLI.getOperationAction(Node->getOpcode(), MVT::Other); 00782 break; 00783 case ISD::SINT_TO_FP: 00784 case ISD::UINT_TO_FP: 00785 case ISD::EXTRACT_VECTOR_ELT: 00786 Action = TLI.getOperationAction(Node->getOpcode(), 00787 Node->getOperand(0).getValueType()); 00788 break; 00789 case ISD::FP_ROUND_INREG: 00790 case ISD::SIGN_EXTEND_INREG: { 00791 EVT InnerType = cast<VTSDNode>(Node->getOperand(1))->getVT(); 00792 Action = TLI.getOperationAction(Node->getOpcode(), InnerType); 00793 break; 00794 } 00795 case ISD::SELECT_CC: 00796 case ISD::SETCC: 00797 case ISD::BR_CC: { 00798 unsigned CCOperand = Node->getOpcode() == ISD::SELECT_CC ? 4 : 00799 Node->getOpcode() == ISD::SETCC ? 2 : 1; 00800 unsigned CompareOperand = Node->getOpcode() == ISD::BR_CC ? 2 : 0; 00801 EVT OpVT = Node->getOperand(CompareOperand).getValueType(); 00802 ISD::CondCode CCCode = 00803 cast<CondCodeSDNode>(Node->getOperand(CCOperand))->get(); 00804 Action = TLI.getCondCodeAction(CCCode, OpVT); 00805 if (Action == TargetLowering::Legal) { 00806 if (Node->getOpcode() == ISD::SELECT_CC) 00807 Action = TLI.getOperationAction(Node->getOpcode(), 00808 Node->getValueType(0)); 00809 else 00810 Action = TLI.getOperationAction(Node->getOpcode(), OpVT); 00811 } 00812 break; 00813 } 00814 case ISD::LOAD: 00815 case ISD::STORE: 00816 // FIXME: Model these properly. LOAD and STORE are complicated, and 00817 // STORE expects the unlegalized operand in some cases. 00818 SimpleFinishLegalizing = false; 00819 break; 00820 case ISD::CALLSEQ_START: 00821 case ISD::CALLSEQ_END: 00822 // FIXME: This shouldn't be necessary. These nodes have special properties 00823 // dealing with the recursive nature of legalization. Removing this 00824 // special case should be done as part of making LegalizeDAG non-recursive. 00825 SimpleFinishLegalizing = false; 00826 break; 00827 case ISD::EXTRACT_ELEMENT: 00828 case ISD::FLT_ROUNDS_: 00829 case ISD::SADDO: 00830 case ISD::SSUBO: 00831 case ISD::UADDO: 00832 case ISD::USUBO: 00833 case ISD::SMULO: 00834 case ISD::UMULO: 00835 case ISD::FPOWI: 00836 case ISD::MERGE_VALUES: 00837 case ISD::EH_RETURN: 00838 case ISD::FRAME_TO_ARGS_OFFSET: 00839 // These operations lie about being legal: when they claim to be legal, 00840 // they should actually be expanded. 00841 Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0)); 00842 if (Action == TargetLowering::Legal) 00843 Action = TargetLowering::Expand; 00844 break; 00845 case ISD::TRAMPOLINE: 00846 case ISD::FRAMEADDR: 00847 case ISD::RETURNADDR: 00848 // These operations lie about being legal: when they claim to be legal, 00849 // they should actually be custom-lowered. 00850 Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0)); 00851 if (Action == TargetLowering::Legal) 00852 Action = TargetLowering::Custom; 00853 break; 00854 case ISD::BUILD_VECTOR: 00855 // A weird case: legalization for BUILD_VECTOR never legalizes the 00856 // operands! 00857 // FIXME: This really sucks... changing it isn't semantically incorrect, 00858 // but it massively pessimizes the code for floating-point BUILD_VECTORs 00859 // because ConstantFP operands get legalized into constant pool loads 00860 // before the BUILD_VECTOR code can see them. It doesn't usually bite, 00861 // though, because BUILD_VECTORS usually get lowered into other nodes 00862 // which get legalized properly. 00863 SimpleFinishLegalizing = false; 00864 break; 00865 default: 00866 if (Node->getOpcode() >= ISD::BUILTIN_OP_END) { 00867 Action = TargetLowering::Legal; 00868 } else { 00869 Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0)); 00870 } 00871 break; 00872 } 00873 00874 if (SimpleFinishLegalizing) { 00875 SmallVector<SDValue, 8> Ops, ResultVals; 00876 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) 00877 Ops.push_back(LegalizeOp(Node->getOperand(i))); 00878 switch (Node->getOpcode()) { 00879 default: break; 00880 case ISD::BR: 00881 case ISD::BRIND: 00882 case ISD::BR_JT: 00883 case ISD::BR_CC: 00884 case ISD::BRCOND: 00885 // Branches tweak the chain to include LastCALLSEQ_END 00886 Ops[0] = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Ops[0], 00887 LastCALLSEQ_END); 00888 Ops[0] = LegalizeOp(Ops[0]); 00889 LastCALLSEQ_END = DAG.getEntryNode(); 00890 break; 00891 case ISD::SHL: 00892 case ISD::SRL: 00893 case ISD::SRA: 00894 case ISD::ROTL: 00895 case ISD::ROTR: 00896 // Legalizing shifts/rotates requires adjusting the shift amount 00897 // to the appropriate width. 00898 if (!Ops[1].getValueType().isVector()) 00899 Ops[1] = LegalizeOp(DAG.getShiftAmountOperand(Ops[1])); 00900 break; 00901 case ISD::SRL_PARTS: 00902 case ISD::SRA_PARTS: 00903 case ISD::SHL_PARTS: 00904 // Legalizing shifts/rotates requires adjusting the shift amount 00905 // to the appropriate width. 00906 if (!Ops[2].getValueType().isVector()) 00907 Ops[2] = LegalizeOp(DAG.getShiftAmountOperand(Ops[2])); 00908 break; 00909 } 00910 00911 Result = DAG.UpdateNodeOperands(Result.getValue(0), Ops.data(), 00912 Ops.size()); 00913 switch (Action) { 00914 case TargetLowering::Legal: 00915 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 00916 ResultVals.push_back(Result.getValue(i)); 00917 break; 00918 case TargetLowering::Custom: 00919 // FIXME: The handling for custom lowering with multiple results is 00920 // a complete mess. 00921 Tmp1 = TLI.LowerOperation(Result, DAG); 00922 if (Tmp1.getNode()) { 00923 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) { 00924 if (e == 1) 00925 ResultVals.push_back(Tmp1); 00926 else 00927 ResultVals.push_back(Tmp1.getValue(i)); 00928 } 00929 break; 00930 } 00931 00932 // FALL THROUGH 00933 case TargetLowering::Expand: 00934 ExpandNode(Result.getNode(), ResultVals); 00935 break; 00936 case TargetLowering::Promote: 00937 PromoteNode(Result.getNode(), ResultVals); 00938 break; 00939 } 00940 if (!ResultVals.empty()) { 00941 for (unsigned i = 0, e = ResultVals.size(); i != e; ++i) { 00942 if (ResultVals[i] != SDValue(Node, i)) 00943 ResultVals[i] = LegalizeOp(ResultVals[i]); 00944 AddLegalizedOperand(SDValue(Node, i), ResultVals[i]); 00945 } 00946 return ResultVals[Op.getResNo()]; 00947 } 00948 } 00949 00950 switch (Node->getOpcode()) { 00951 default: 00952 #ifndef NDEBUG 00953 cerr << "NODE: "; Node->dump(&DAG); cerr << "\n"; 00954 #endif 00955 llvm_unreachable("Do not know how to legalize this operator!"); 00956 00957 case ISD::BUILD_VECTOR: 00958 switch (TLI.getOperationAction(ISD::BUILD_VECTOR, Node->getValueType(0))) { 00959 default: llvm_unreachable("This action is not supported yet!"); 00960 case TargetLowering::Custom: 00961 Tmp3 = TLI.LowerOperation(Result, DAG); 00962 if (Tmp3.getNode()) { 00963 Result = Tmp3; 00964 break; 00965 } 00966 // FALLTHROUGH 00967 case TargetLowering::Expand: 00968 Result = ExpandBUILD_VECTOR(Result.getNode()); 00969 break; 00970 } 00971 break; 00972 case ISD::CALLSEQ_START: { 00973 SDNode *CallEnd = FindCallEndFromCallStart(Node); 00974 00975 // Recursively Legalize all of the inputs of the call end that do not lead 00976 // to this call start. This ensures that any libcalls that need be inserted 00977 // are inserted *before* the CALLSEQ_START. 00978 {SmallPtrSet<SDNode*, 32> NodesLeadingTo; 00979 for (unsigned i = 0, e = CallEnd->getNumOperands(); i != e; ++i) 00980 LegalizeAllNodesNotLeadingTo(CallEnd->getOperand(i).getNode(), Node, 00981 NodesLeadingTo); 00982 } 00983 00984 // Now that we legalized all of the inputs (which may have inserted 00985 // libcalls) create the new CALLSEQ_START node. 00986 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 00987 00988 // Merge in the last call, to ensure that this call start after the last 00989 // call ended. 00990 if (LastCALLSEQ_END.getOpcode() != ISD::EntryToken) { 00991 Tmp1 = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 00992 Tmp1, LastCALLSEQ_END); 00993 Tmp1 = LegalizeOp(Tmp1); 00994 } 00995 00996 // Do not try to legalize the target-specific arguments (#1+). 00997 if (Tmp1 != Node->getOperand(0)) { 00998 SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end()); 00999 Ops[0] = Tmp1; 01000 Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size()); 01001 } 01002 01003 // Remember that the CALLSEQ_START is legalized. 01004 AddLegalizedOperand(Op.getValue(0), Result); 01005 if (Node->getNumValues() == 2) // If this has a flag result, remember it. 01006 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 01007 01008 // Now that the callseq_start and all of the non-call nodes above this call 01009 // sequence have been legalized, legalize the call itself. During this 01010 // process, no libcalls can/will be inserted, guaranteeing that no calls 01011 // can overlap. 01012 assert(!IsLegalizingCall && "Inconsistent sequentialization of calls!"); 01013 // Note that we are selecting this call! 01014 LastCALLSEQ_END = SDValue(CallEnd, 0); 01015 IsLegalizingCall = true; 01016 01017 // Legalize the call, starting from the CALLSEQ_END. 01018 LegalizeOp(LastCALLSEQ_END); 01019 assert(!IsLegalizingCall && "CALLSEQ_END should have cleared this!"); 01020 return Result; 01021 } 01022 case ISD::CALLSEQ_END: 01023 // If the CALLSEQ_START node hasn't been legalized first, legalize it. This 01024 // will cause this node to be legalized as well as handling libcalls right. 01025 if (LastCALLSEQ_END.getNode() != Node) { 01026 LegalizeOp(SDValue(FindCallStartFromCallEnd(Node), 0)); 01027 DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op); 01028 assert(I != LegalizedNodes.end() && 01029 "Legalizing the call start should have legalized this node!"); 01030 return I->second; 01031 } 01032 01033 // Otherwise, the call start has been legalized and everything is going 01034 // according to plan. Just legalize ourselves normally here. 01035 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 01036 // Do not try to legalize the target-specific arguments (#1+), except for 01037 // an optional flag input. 01038 if (Node->getOperand(Node->getNumOperands()-1).getValueType() != MVT::Flag){ 01039 if (Tmp1 != Node->getOperand(0)) { 01040 SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end()); 01041 Ops[0] = Tmp1; 01042 Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size()); 01043 } 01044 } else { 01045 Tmp2 = LegalizeOp(Node->getOperand(Node->getNumOperands()-1)); 01046 if (Tmp1 != Node->getOperand(0) || 01047 Tmp2 != Node->getOperand(Node->getNumOperands()-1)) { 01048 SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end()); 01049 Ops[0] = Tmp1; 01050 Ops.back() = Tmp2; 01051 Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size()); 01052 } 01053 } 01054 assert(IsLegalizingCall && "Call sequence imbalance between start/end?"); 01055 // This finishes up call legalization. 01056 IsLegalizingCall = false; 01057 01058 // If the CALLSEQ_END node has a flag, remember that we legalized it. 01059 AddLegalizedOperand(SDValue(Node, 0), Result.getValue(0)); 01060 if (Node->getNumValues() == 2) 01061 AddLegalizedOperand(SDValue(Node, 1), Result.getValue(1)); 01062 return Result.getValue(Op.getResNo()); 01063 case ISD::LOAD: { 01064 LoadSDNode *LD = cast<LoadSDNode>(Node); 01065 Tmp1 = LegalizeOp(LD->getChain()); // Legalize the chain. 01066 Tmp2 = LegalizeOp(LD->getBasePtr()); // Legalize the base pointer. 01067 01068 ISD::LoadExtType ExtType = LD->getExtensionType(); 01069 if (ExtType == ISD::NON_EXTLOAD) { 01070 EVT VT = Node->getValueType(0); 01071 Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, LD->getOffset()); 01072 Tmp3 = Result.getValue(0); 01073 Tmp4 = Result.getValue(1); 01074 01075 switch (TLI.getOperationAction(Node->getOpcode(), VT)) { 01076 default: llvm_unreachable("This action is not supported yet!"); 01077 case TargetLowering::Legal: 01078 // If this is an unaligned load and the target doesn't support it, 01079 // expand it. 01080 if (!TLI.allowsUnalignedMemoryAccesses(LD->getMemoryVT())) { 01081 const Type *Ty = LD->getMemoryVT().getTypeForEVT(*DAG.getContext()); 01082 unsigned ABIAlignment = TLI.getTargetData()->getABITypeAlignment(Ty); 01083 if (LD->getAlignment() < ABIAlignment){ 01084 Result = ExpandUnalignedLoad(cast<LoadSDNode>(Result.getNode()), 01085 DAG, TLI); 01086 Tmp3 = Result.getOperand(0); 01087 Tmp4 = Result.getOperand(1); 01088 Tmp3 = LegalizeOp(Tmp3); 01089 Tmp4 = LegalizeOp(Tmp4); 01090 } 01091 } 01092 break; 01093 case TargetLowering::Custom: 01094 Tmp1 = TLI.LowerOperation(Tmp3, DAG); 01095 if (Tmp1.getNode()) { 01096 Tmp3 = LegalizeOp(Tmp1); 01097 Tmp4 = LegalizeOp(Tmp1.getValue(1)); 01098 } 01099 break; 01100 case TargetLowering::Promote: { 01101 // Only promote a load of vector type to another. 01102 assert(VT.isVector() && "Cannot promote this load!"); 01103 // Change base type to a different vector type. 01104 EVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), VT); 01105 01106 Tmp1 = DAG.getLoad(NVT, dl, Tmp1, Tmp2, LD->getSrcValue(), 01107 LD->getSrcValueOffset(), 01108 LD->isVolatile(), LD->getAlignment()); 01109 Tmp3 = LegalizeOp(DAG.getNode(ISD::BIT_CONVERT, dl, VT, Tmp1)); 01110 Tmp4 = LegalizeOp(Tmp1.getValue(1)); 01111 break; 01112 } 01113 } 01114 // Since loads produce two values, make sure to remember that we 01115 // legalized both of them. 01116 AddLegalizedOperand(SDValue(Node, 0), Tmp3); 01117 AddLegalizedOperand(SDValue(Node, 1), Tmp4); 01118 return Op.getResNo() ? Tmp4 : Tmp3; 01119 } else { 01120 EVT SrcVT = LD->getMemoryVT(); 01121 unsigned SrcWidth = SrcVT.getSizeInBits(); 01122 int SVOffset = LD->getSrcValueOffset(); 01123 unsigned Alignment = LD->getAlignment(); 01124 bool isVolatile = LD->isVolatile(); 01125 01126 if (SrcWidth != SrcVT.getStoreSizeInBits() && 01127 // Some targets pretend to have an i1 loading operation, and actually 01128 // load an i8. This trick is correct for ZEXTLOAD because the top 7 01129 // bits are guaranteed to be zero; it helps the optimizers understand 01130 // that these bits are zero. It is also useful for EXTLOAD, since it 01131 // tells the optimizers that those bits are undefined. It would be 01132 // nice to have an effective generic way of getting these benefits... 01133 // Until such a way is found, don't insist on promoting i1 here. 01134 (SrcVT != MVT::i1 || 01135 TLI.getLoadExtAction(ExtType, MVT::i1) == TargetLowering::Promote)) { 01136 // Promote to a byte-sized load if not loading an integral number of 01137 // bytes. For example, promote EXTLOAD:i20 -> EXTLOAD:i24. 01138 unsigned NewWidth = SrcVT.getStoreSizeInBits(); 01139 EVT NVT = EVT::getIntegerVT(*DAG.getContext(), NewWidth); 01140 SDValue Ch; 01141 01142 // The extra bits are guaranteed to be zero, since we stored them that 01143 // way. A zext load from NVT thus automatically gives zext from SrcVT. 01144 01145 ISD::LoadExtType NewExtType = 01146 ExtType == ISD::ZEXTLOAD ? ISD::ZEXTLOAD : ISD::EXTLOAD; 01147 01148 Result = DAG.getExtLoad(NewExtType, dl, Node->getValueType(0), 01149 Tmp1, Tmp2, LD->getSrcValue(), SVOffset, 01150 NVT, isVolatile, Alignment); 01151 01152 Ch = Result.getValue(1); // The chain. 01153 01154 if (ExtType == ISD::SEXTLOAD) 01155 // Having the top bits zero doesn't help when sign extending. 01156 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, 01157 Result.getValueType(), 01158 Result, DAG.getValueType(SrcVT)); 01159 else if (ExtType == ISD::ZEXTLOAD || NVT == Result.getValueType()) 01160 // All the top bits are guaranteed to be zero - inform the optimizers. 01161 Result = DAG.getNode(ISD::AssertZext, dl, 01162 Result.getValueType(), Result, 01163 DAG.getValueType(SrcVT)); 01164 01165 Tmp1 = LegalizeOp(Result); 01166 Tmp2 = LegalizeOp(Ch); 01167 } else if (SrcWidth & (SrcWidth - 1)) { 01168 // If not loading a power-of-2 number of bits, expand as two loads. 01169 assert(SrcVT.isExtended() && !SrcVT.isVector() && 01170 "Unsupported extload!"); 01171 unsigned RoundWidth = 1 << Log2_32(SrcWidth); 01172 assert(RoundWidth < SrcWidth); 01173 unsigned ExtraWidth = SrcWidth - RoundWidth; 01174 assert(ExtraWidth < RoundWidth); 01175 assert(!(RoundWidth % 8) && !(ExtraWidth % 8) && 01176 "Load size not an integral number of bytes!"); 01177 EVT RoundVT = EVT::getIntegerVT(*DAG.getContext(), RoundWidth); 01178 EVT ExtraVT = EVT::getIntegerVT(*DAG.getContext(), ExtraWidth); 01179 SDValue Lo, Hi, Ch; 01180 unsigned IncrementSize; 01181 01182 if (TLI.isLittleEndian()) { 01183 // EXTLOAD:i24 -> ZEXTLOAD:i16 | (shl EXTLOAD@+2:i8, 16) 01184 // Load the bottom RoundWidth bits. 01185 Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, 01186 Node->getValueType(0), Tmp1, Tmp2, 01187 LD->getSrcValue(), SVOffset, RoundVT, isVolatile, 01188 Alignment); 01189 01190 // Load the remaining ExtraWidth bits. 01191 IncrementSize = RoundWidth / 8; 01192 Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2, 01193 DAG.getIntPtrConstant(IncrementSize)); 01194 Hi = DAG.getExtLoad(ExtType, dl, Node->getValueType(0), Tmp1, Tmp2, 01195 LD->getSrcValue(), SVOffset + IncrementSize, 01196 ExtraVT, isVolatile, 01197 MinAlign(Alignment, IncrementSize)); 01198 01199 // Build a factor node to remember that this load is independent of the 01200 // other one. 01201 Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1), 01202 Hi.getValue(1)); 01203 01204 // Move the top bits to the right place. 01205 Hi = DAG.getNode(ISD::SHL, dl, Hi.getValueType(), Hi, 01206 DAG.getConstant(RoundWidth, TLI.getShiftAmountTy())); 01207 01208 // Join the hi and lo parts. 01209 Result = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi); 01210 } else { 01211 // Big endian - avoid unaligned loads. 01212 // EXTLOAD:i24 -> (shl EXTLOAD:i16, 8) | ZEXTLOAD@+2:i8 01213 // Load the top RoundWidth bits. 01214 Hi = DAG.getExtLoad(ExtType, dl, Node->getValueType(0), Tmp1, Tmp2, 01215 LD->getSrcValue(), SVOffset, RoundVT, isVolatile, 01216 Alignment); 01217 01218 // Load the remaining ExtraWidth bits. 01219 IncrementSize = RoundWidth / 8; 01220 Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2, 01221 DAG.getIntPtrConstant(IncrementSize)); 01222 Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, 01223 Node->getValueType(0), Tmp1, Tmp2, 01224 LD->getSrcValue(), SVOffset + IncrementSize, 01225 ExtraVT, isVolatile, 01226 MinAlign(Alignment, IncrementSize)); 01227 01228 // Build a factor node to remember that this load is independent of the 01229 // other one. 01230 Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1), 01231 Hi.getValue(1)); 01232 01233 // Move the top bits to the right place. 01234 Hi = DAG.getNode(ISD::SHL, dl, Hi.getValueType(), Hi, 01235 DAG.getConstant(ExtraWidth, TLI.getShiftAmountTy())); 01236 01237 // Join the hi and lo parts. 01238 Result = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi); 01239 } 01240 01241 Tmp1 = LegalizeOp(Result); 01242 Tmp2 = LegalizeOp(Ch); 01243 } else { 01244 switch (TLI.getLoadExtAction(ExtType, SrcVT)) { 01245 default: llvm_unreachable("This action is not supported yet!"); 01246 case TargetLowering::Custom: 01247 isCustom = true; 01248 // FALLTHROUGH 01249 case TargetLowering::Legal: 01250 Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, LD->getOffset()); 01251 Tmp1 = Result.getValue(0); 01252 Tmp2 = Result.getValue(1); 01253 01254 if (isCustom) { 01255 Tmp3 = TLI.LowerOperation(Result, DAG); 01256 if (Tmp3.getNode()) { 01257 Tmp1 = LegalizeOp(Tmp3); 01258 Tmp2 = LegalizeOp(Tmp3.getValue(1)); 01259 } 01260 } else { 01261 // If this is an unaligned load and the target doesn't support it, 01262 // expand it. 01263 if (!TLI.allowsUnalignedMemoryAccesses(LD->getMemoryVT())) { 01264 const Type *Ty = LD->getMemoryVT().getTypeForEVT(*DAG.getContext()); 01265 unsigned ABIAlignment = TLI.getTargetData()->getABITypeAlignment(Ty); 01266 if (LD->getAlignment() < ABIAlignment){ 01267 Result = ExpandUnalignedLoad(cast<LoadSDNode>(Result.getNode()), 01268 DAG, TLI); 01269 Tmp1 = Result.getOperand(0); 01270 Tmp2 = Result.getOperand(1); 01271 Tmp1 = LegalizeOp(Tmp1); 01272 Tmp2 = LegalizeOp(Tmp2); 01273 } 01274 } 01275 } 01276 break; 01277 case TargetLowering::Expand: 01278 // f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND 01279 if (SrcVT == MVT::f32 && Node->getValueType(0) == MVT::f64) { 01280 SDValue Load = DAG.getLoad(SrcVT, dl, Tmp1, Tmp2, LD->getSrcValue(), 01281 LD->getSrcValueOffset(), 01282 LD->isVolatile(), LD->getAlignment()); 01283 Result = DAG.getNode(ISD::FP_EXTEND, dl, 01284 Node->getValueType(0), Load); 01285 Tmp1 = LegalizeOp(Result); // Relegalize new nodes. 01286 Tmp2 = LegalizeOp(Load.getValue(1)); 01287 break; 01288 } 01289 assert(ExtType != ISD::EXTLOAD &&"EXTLOAD should always be supported!"); 01290 // Turn the unsupported load into an EXTLOAD followed by an explicit 01291 // zero/sign extend inreg. 01292 Result = DAG.getExtLoad(ISD::EXTLOAD, dl, Node->getValueType(0), 01293 Tmp1, Tmp2, LD->getSrcValue(), 01294 LD->getSrcValueOffset(), SrcVT, 01295 LD->isVolatile(), LD->getAlignment()); 01296 SDValue ValRes; 01297 if (ExtType == ISD::SEXTLOAD) 01298 ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, 01299 Result.getValueType(), 01300 Result, DAG.getValueType(SrcVT)); 01301 else 01302 ValRes = DAG.getZeroExtendInReg(Result, dl, SrcVT); 01303 Tmp1 = LegalizeOp(ValRes); // Relegalize new nodes. 01304 Tmp2 = LegalizeOp(Result.getValue(1)); // Relegalize new nodes. 01305 break; 01306 } 01307 } 01308 01309 // Since loads produce two values, make sure to remember that we legalized 01310 // both of them. 01311 AddLegalizedOperand(SDValue(Node, 0), Tmp1); 01312 AddLegalizedOperand(SDValue(Node, 1), Tmp2); 01313 return Op.getResNo() ? Tmp2 : Tmp1; 01314 } 01315 } 01316 case ISD::STORE: { 01317 StoreSDNode *ST = cast<StoreSDNode>(Node); 01318 Tmp1 = LegalizeOp(ST->getChain()); // Legalize the chain. 01319 Tmp2 = LegalizeOp(ST->getBasePtr()); // Legalize the pointer. 01320 int SVOffset = ST->getSrcValueOffset(); 01321 unsigned Alignment = ST->getAlignment(); 01322 bool isVolatile = ST->isVolatile(); 01323 01324 if (!ST->isTruncatingStore()) { 01325 if (SDNode *OptStore = OptimizeFloatStore(ST).getNode()) { 01326 Result = SDValue(OptStore, 0); 01327 break; 01328 } 01329 01330 { 01331 Tmp3 = LegalizeOp(ST->getValue()); 01332 Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2, 01333 ST->getOffset()); 01334 01335 EVT VT = Tmp3.getValueType(); 01336 switch (TLI.getOperationAction(ISD::STORE, VT)) { 01337 default: llvm_unreachable("This action is not supported yet!"); 01338 case TargetLowering::Legal: 01339 // If this is an unaligned store and the target doesn't support it, 01340 // expand it. 01341 if (!TLI.allowsUnalignedMemoryAccesses(ST->getMemoryVT())) { 01342 const Type *Ty = ST->getMemoryVT().getTypeForEVT(*DAG.getContext()); 01343 unsigned ABIAlignment = TLI.getTargetData()->getABITypeAlignment(Ty); 01344 if (ST->getAlignment() < ABIAlignment) 01345 Result = ExpandUnalignedStore(cast<StoreSDNode>(Result.getNode()), 01346 DAG, TLI); 01347 } 01348 break; 01349 case TargetLowering::Custom: 01350 Tmp1 = TLI.LowerOperation(Result, DAG); 01351 if (Tmp1.getNode()) Result = Tmp1; 01352 break; 01353 case TargetLowering::Promote: 01354 assert(VT.isVector() && "Unknown legal promote case!"); 01355 Tmp3 = DAG.getNode(ISD::BIT_CONVERT, dl, 01356 TLI.getTypeToPromoteTo(ISD::STORE, VT), Tmp3); 01357 Result = DAG.getStore(Tmp1, dl, Tmp3, Tmp2, 01358 ST->getSrcValue(), SVOffset, isVolatile, 01359 Alignment); 01360 break; 01361 } 01362 break; 01363 } 01364 } else { 01365 Tmp3 = LegalizeOp(ST->getValue()); 01366 01367 EVT StVT = ST->getMemoryVT(); 01368 unsigned StWidth = StVT.getSizeInBits(); 01369 01370 if (StWidth != StVT.getStoreSizeInBits()) { 01371 // Promote to a byte-sized store with upper bits zero if not 01372 // storing an integral number of bytes. For example, promote 01373 // TRUNCSTORE:i1 X -> TRUNCSTORE:i8 (and X, 1) 01374 EVT NVT = EVT::getIntegerVT(*DAG.getContext(), StVT.getStoreSizeInBits()); 01375 Tmp3 = DAG.getZeroExtendInReg(Tmp3, dl, StVT); 01376 Result = DAG.getTruncStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(), 01377 SVOffset, NVT, isVolatile, Alignment); 01378 } else if (StWidth & (StWidth - 1)) { 01379 // If not storing a power-of-2 number of bits, expand as two stores. 01380 assert(StVT.isExtended() && !StVT.isVector() && 01381 "Unsupported truncstore!"); 01382 unsigned RoundWidth = 1 << Log2_32(StWidth); 01383 assert(RoundWidth < StWidth); 01384 unsigned ExtraWidth = StWidth - RoundWidth; 01385 assert(ExtraWidth < RoundWidth); 01386 assert(!(RoundWidth % 8) && !(ExtraWidth % 8) && 01387 "Store size not an integral number of bytes!"); 01388 EVT RoundVT = EVT::getIntegerVT(*DAG.getContext(), RoundWidth); 01389 EVT ExtraVT = EVT::getIntegerVT(*DAG.getContext(), ExtraWidth); 01390 SDValue Lo, Hi; 01391 unsigned IncrementSize; 01392 01393 if (TLI.isLittleEndian()) { 01394 // TRUNCSTORE:i24 X -> TRUNCSTORE:i16 X, TRUNCSTORE@+2:i8 (srl X, 16) 01395 // Store the bottom RoundWidth bits. 01396 Lo = DAG.getTruncStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(), 01397 SVOffset, RoundVT, 01398 isVolatile, Alignment); 01399 01400 // Store the remaining ExtraWidth bits. 01401 IncrementSize = RoundWidth / 8; 01402 Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2, 01403 DAG.getIntPtrConstant(IncrementSize)); 01404 Hi = DAG.getNode(ISD::SRL, dl, Tmp3.getValueType(), Tmp3, 01405 DAG.getConstant(RoundWidth, TLI.getShiftAmountTy())); 01406 Hi = DAG.getTruncStore(Tmp1, dl, Hi, Tmp2, ST->getSrcValue(), 01407 SVOffset + IncrementSize, ExtraVT, isVolatile, 01408 MinAlign(Alignment, IncrementSize)); 01409 } else { 01410 // Big endian - avoid unaligned stores. 01411 // TRUNCSTORE:i24 X -> TRUNCSTORE:i16 (srl X, 8), TRUNCSTORE@+2:i8 X 01412 // Store the top RoundWidth bits. 01413 Hi = DAG.getNode(ISD::SRL, dl, Tmp3.getValueType(), Tmp3, 01414 DAG.getConstant(ExtraWidth, TLI.getShiftAmountTy())); 01415 Hi = DAG.getTruncStore(Tmp1, dl, Hi, Tmp2, ST->getSrcValue(), 01416 SVOffset, RoundVT, isVolatile, Alignment); 01417 01418 // Store the remaining ExtraWidth bits. 01419 IncrementSize = RoundWidth / 8; 01420 Tmp2 = DAG.getNode(ISD::ADD, dl, Tmp2.getValueType(), Tmp2, 01421 DAG.getIntPtrConstant(IncrementSize)); 01422 Lo = DAG.getTruncStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(), 01423 SVOffset + IncrementSize, ExtraVT, isVolatile, 01424 MinAlign(Alignment, IncrementSize)); 01425 } 01426 01427 // The order of the stores doesn't matter. 01428 Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi); 01429 } else { 01430 if (Tmp1 != ST->getChain() || Tmp3 != ST->getValue() || 01431 Tmp2 != ST->getBasePtr()) 01432 Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2, 01433 ST->getOffset()); 01434 01435 switch (TLI.getTruncStoreAction(ST->getValue().getValueType(), StVT)) { 01436 default: llvm_unreachable("This action is not supported yet!"); 01437 case TargetLowering::Legal: 01438 // If this is an unaligned store and the target doesn't support it, 01439 // expand it. 01440 if (!TLI.allowsUnalignedMemoryAccesses(ST->getMemoryVT())) { 01441 const Type *Ty = ST->getMemoryVT().getTypeForEVT(*DAG.getContext()); 01442 unsigned ABIAlignment = TLI.getTargetData()->getABITypeAlignment(Ty); 01443 if (ST->getAlignment() < ABIAlignment) 01444 Result = ExpandUnalignedStore(cast<StoreSDNode>(Result.getNode()), 01445 DAG, TLI); 01446 } 01447 break; 01448 case TargetLowering::Custom: 01449 Result = TLI.LowerOperation(Result, DAG); 01450 break; 01451 case Expand: 01452 // TRUNCSTORE:i16 i32 -> STORE i16 01453 assert(isTypeLegal(StVT) && "Do not know how to expand this store!"); 01454 Tmp3 = DAG.getNode(ISD::TRUNCATE, dl, StVT, Tmp3); 01455 Result = DAG.getStore(Tmp1, dl, Tmp3, Tmp2, ST->getSrcValue(), 01456 SVOffset, isVolatile, Alignment); 01457 break; 01458 } 01459 } 01460 } 01461 break; 01462 } 01463 } 01464 assert(Result.getValueType() == Op.getValueType() && 01465 "Bad legalization!"); 01466 01467 // Make sure that the generated code is itself legal. 01468 if (Result != Op) 01469 Result = LegalizeOp(Result); 01470 01471 // Note that LegalizeOp may be reentered even from single-use nodes, which 01472 // means that we always must cache transformed nodes. 01473 AddLegalizedOperand(Op, Result); 01474 return Result; 01475 } 01476 01477 SDValue SelectionDAGLegalize::ExpandExtractFromVectorThroughStack(SDValue Op) { 01478 SDValue Vec = Op.getOperand(0); 01479 SDValue Idx = Op.getOperand(1); 01480 DebugLoc dl = Op.getDebugLoc(); 01481 // Store the value to a temporary stack slot, then LOAD the returned part. 01482 SDValue StackPtr = DAG.CreateStackTemporary(Vec.getValueType()); 01483 SDValue Ch = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, NULL, 0); 01484 01485 // Add the offset to the index. 01486 unsigned EltSize = 01487 Vec.getValueType().getVectorElementType().getSizeInBits()/8; 01488 Idx = DAG.getNode(ISD::MUL, dl, Idx.getValueType(), Idx, 01489 DAG.getConstant(EltSize, Idx.getValueType())); 01490 01491 if (Idx.getValueType().bitsGT(TLI.getPointerTy())) 01492 Idx = DAG.getNode(ISD::TRUNCATE, dl, TLI.getPointerTy(), Idx); 01493 else 01494 Idx = DAG.getNode(ISD::ZERO_EXTEND, dl, TLI.getPointerTy(), Idx); 01495 01496 StackPtr = DAG.getNode(ISD::ADD, dl, Idx.getValueType(), Idx, StackPtr); 01497 01498 if (Op.getValueType().isVector()) 01499 return DAG.getLoad(Op.getValueType(), dl, Ch, StackPtr, NULL, 0); 01500 else 01501 return DAG.getExtLoad(ISD::EXTLOAD, dl, Op.getValueType(), Ch, StackPtr, 01502 NULL, 0, Vec.getValueType().getVectorElementType()); 01503 } 01504 01505 SDValue SelectionDAGLegalize::ExpandVectorBuildThroughStack(SDNode* Node) { 01506 // We can't handle this case efficiently. Allocate a sufficiently 01507 // aligned object on the stack, store each element into it, then load 01508 // the result as a vector. 01509 // Create the stack frame object. 01510 EVT VT = Node->getValueType(0); 01511 EVT OpVT = Node->getOperand(0).getValueType(); 01512 DebugLoc dl = Node->getDebugLoc(); 01513 SDValue FIPtr = DAG.CreateStackTemporary(VT); 01514 int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex(); 01515 const Value *SV = PseudoSourceValue::getFixedStack(FI); 01516 01517 // Emit a store of each element to the stack slot. 01518 SmallVector<SDValue, 8> Stores; 01519 unsigned TypeByteSize = OpVT.getSizeInBits() / 8; 01520 // Store (in the right endianness) the elements to memory. 01521 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 01522 // Ignore undef elements. 01523 if (Node->getOperand(i).getOpcode() == ISD::UNDEF) continue; 01524 01525 unsigned Offset = TypeByteSize*i; 01526 01527 SDValue Idx = DAG.getConstant(Offset, FIPtr.getValueType()); 01528 Idx = DAG.getNode(ISD::ADD, dl, FIPtr.getValueType(), FIPtr, Idx); 01529 01530 Stores.push_back(DAG.getStore(DAG.getEntryNode(), dl, Node->getOperand(i), 01531 Idx, SV, Offset)); 01532 } 01533 01534 SDValue StoreChain; 01535 if (!Stores.empty()) // Not all undef elements? 01536 StoreChain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 01537 &Stores[0], Stores.size()); 01538 else 01539 StoreChain = DAG.getEntryNode(); 01540 01541 // Result is a load from the stack slot. 01542 return DAG.getLoad(VT, dl, StoreChain, FIPtr, SV, 0); 01543 } 01544 01545 SDValue SelectionDAGLegalize::ExpandFCOPYSIGN(SDNode* Node) { 01546 DebugLoc dl = Node->getDebugLoc(); 01547 SDValue Tmp1 = Node->getOperand(0); 01548 SDValue Tmp2 = Node->getOperand(1); 01549 assert((Tmp2.getValueType() == MVT::f32 || 01550 Tmp2.getValueType() == MVT::f64) && 01551 "Ugly special-cased code!"); 01552 // Get the sign bit of the RHS. 01553 SDValue SignBit; 01554 EVT IVT = Tmp2.getValueType() == MVT::f64 ? MVT::i64 : MVT::i32; 01555 if (isTypeLegal(IVT)) { 01556 SignBit = DAG.getNode(ISD::BIT_CONVERT, dl, IVT, Tmp2); 01557 } else { 01558 assert(isTypeLegal(TLI.getPointerTy()) && 01559 (TLI.getPointerTy() == MVT::i32 || 01560 TLI.getPointerTy() == MVT::i64) && 01561 "Legal type for load?!"); 01562 SDValue StackPtr = DAG.CreateStackTemporary(Tmp2.getValueType()); 01563 SDValue StorePtr = StackPtr, LoadPtr = StackPtr; 01564 SDValue Ch = 01565 DAG.getStore(DAG.getEntryNode(), dl, Tmp2, StorePtr, NULL, 0); 01566 if (Tmp2.getValueType() == MVT::f64 && TLI.isLittleEndian()) 01567 LoadPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), 01568 LoadPtr, DAG.getIntPtrConstant(4)); 01569 SignBit = DAG.getExtLoad(ISD::SEXTLOAD, dl, TLI.getPointerTy(), 01570 Ch, LoadPtr, NULL, 0, MVT::i32); 01571 } 01572 SignBit = 01573 DAG.getSetCC(dl, TLI.getSetCCResultType(SignBit.getValueType()), 01574 SignBit, DAG.getConstant(0, SignBit.getValueType()), 01575 ISD::SETLT); 01576 // Get the absolute value of the result. 01577 SDValue AbsVal = DAG.getNode(ISD::FABS, dl, Tmp1.getValueType(), Tmp1); 01578 // Select between the nabs and abs value based on the sign bit of 01579 // the input. 01580 return DAG.getNode(ISD::SELECT, dl, AbsVal.getValueType(), SignBit, 01581 DAG.getNode(ISD::FNEG, dl, AbsVal.getValueType(), AbsVal), 01582 AbsVal); 01583 } 01584 01585 SDValue SelectionDAGLegalize::ExpandDBG_STOPPOINT(SDNode* Node) { 01586 DebugLoc dl = Node->getDebugLoc(); 01587 DwarfWriter *DW = DAG.getDwarfWriter(); 01588 bool useDEBUG_LOC = TLI.isOperationLegalOrCustom(ISD::DEBUG_LOC, 01589 MVT::Other); 01590 bool useLABEL = TLI.isOperationLegalOrCustom(ISD::DBG_LABEL, MVT::Other); 01591 01592 const DbgStopPointSDNode *DSP = cast<DbgStopPointSDNode>(Node); 01593 GlobalVariable *CU_GV = cast<GlobalVariable>(DSP->getCompileUnit()); 01594 if (DW && (useDEBUG_LOC || useLABEL) && !CU_GV->isDeclaration()) { 01595 DICompileUnit CU(cast<GlobalVariable>(DSP->getCompileUnit())); 01596 01597 unsigned Line = DSP->getLine(); 01598 unsigned Col = DSP->getColumn(); 01599 01600 if (OptLevel == CodeGenOpt::None) { 01601 // A bit self-referential to have DebugLoc on Debug_Loc nodes, but it 01602 // won't hurt anything. 01603 if (useDEBUG_LOC) { 01604 return DAG.getNode(ISD::DEBUG_LOC, dl, MVT::Other, Node->getOperand(0), 01605 DAG.getConstant(Line, MVT::i32), 01606 DAG.getConstant(Col, MVT::i32), 01607 DAG.getSrcValue(CU.getGV())); 01608 } else { 01609 unsigned ID = DW->RecordSourceLine(Line, Col, CU); 01610 return DAG.getLabel(ISD::DBG_LABEL, dl, Node->getOperand(0), ID); 01611 } 01612 } 01613 } 01614 return Node->getOperand(0); 01615 } 01616 01617 void SelectionDAGLegalize::ExpandDYNAMIC_STACKALLOC(SDNode* Node, 01618 SmallVectorImpl<SDValue> &Results) { 01619 unsigned SPReg = TLI.getStackPointerRegisterToSaveRestore(); 01620 assert(SPReg && "Target cannot require DYNAMIC_STACKALLOC expansion and" 01621 " not tell us which reg is the stack pointer!"); 01622 DebugLoc dl = Node->getDebugLoc(); 01623 EVT VT = Node->getValueType(0); 01624 SDValue Tmp1 = SDValue(Node, 0); 01625 SDValue Tmp2 = SDValue(Node, 1); 01626 SDValue Tmp3 = Node->getOperand(2); 01627 SDValue Chain = Tmp1.getOperand(0); 01628 01629 // Chain the dynamic stack allocation so that it doesn't modify the stack 01630 // pointer when other instructions are using the stack. 01631 Chain = DAG.getCALLSEQ_START(Chain, DAG.getIntPtrConstant(0, true)); 01632 01633 SDValue Size = Tmp2.getOperand(1); 01634 SDValue SP = DAG.getCopyFromReg(Chain, dl, SPReg, VT); 01635 Chain = SP.getValue(1); 01636 unsigned Align = cast<ConstantSDNode>(Tmp3)->getZExtValue(); 01637 unsigned StackAlign = 01638 TLI.getTargetMachine().getFrameInfo()->getStackAlignment(); 01639 if (Align > StackAlign) 01640 SP = DAG.getNode(ISD::AND, dl, VT, SP, 01641 DAG.getConstant(-(uint64_t)Align, VT)); 01642 Tmp1 = DAG.getNode(ISD::SUB, dl, VT, SP, Size); // Value 01643 Chain = DAG.getCopyToReg(Chain, dl, SPReg, Tmp1); // Output chain 01644 01645 Tmp2 = DAG.getCALLSEQ_END(Chain, DAG.getIntPtrConstant(0, true), 01646 DAG.getIntPtrConstant(0, true), SDValue()); 01647 01648 Results.push_back(Tmp1); 01649 Results.push_back(Tmp2); 01650 } 01651 01652 /// LegalizeSetCCCondCode - Legalize a SETCC with given LHS and RHS and 01653 /// condition code CC on the current target. This routine assumes LHS and rHS 01654 /// have already been legalized by LegalizeSetCCOperands. It expands SETCC with 01655 /// illegal condition code into AND / OR of multiple SETCC values. 01656 void SelectionDAGLegalize::LegalizeSetCCCondCode(EVT VT, 01657 SDValue &LHS, SDValue &RHS, 01658 SDValue &CC, 01659 DebugLoc dl) { 01660 EVT OpVT = LHS.getValueType(); 01661 ISD::CondCode CCCode = cast<CondCodeSDNode>(CC)->get(); 01662 switch (TLI.getCondCodeAction(CCCode, OpVT)) { 01663 default: llvm_unreachable("Unknown condition code action!"); 01664 case TargetLowering::Legal: 01665 // Nothing to do. 01666 break; 01667 case TargetLowering::Expand: { 01668 ISD::CondCode CC1 = ISD::SETCC_INVALID, CC2 = ISD::SETCC_INVALID; 01669 unsigned Opc = 0; 01670 switch (CCCode) { 01671 default: llvm_unreachable("Don't know how to expand this condition!"); 01672 case ISD::SETOEQ: CC1 = ISD::SETEQ; CC2 = ISD::SETO; Opc = ISD::AND; break; 01673 case ISD::SETOGT: CC1 = ISD::SETGT; CC2 = ISD::SETO; Opc = ISD::AND; break; 01674 case ISD::SETOGE: CC1 = ISD::SETGE; CC2 = ISD::SETO; Opc = ISD::AND; break; 01675 case ISD::SETOLT: CC1 = ISD::SETLT; CC2 = ISD::SETO; Opc = ISD::AND; break; 01676 case ISD::SETOLE: CC1 = ISD::SETLE; CC2 = ISD::SETO; Opc = ISD::AND; break; 01677 case ISD::SETONE: CC1 = ISD::SETNE; CC2 = ISD::SETO; Opc = ISD::AND; break; 01678 case ISD::SETUEQ: CC1 = ISD::SETEQ; CC2 = ISD::SETUO; Opc = ISD::OR; break; 01679 case ISD::SETUGT: CC1 = ISD::SETGT; CC2 = ISD::SETUO; Opc = ISD::OR; break; 01680 case ISD::SETUGE: CC1 = ISD::SETGE; CC2 = ISD::SETUO; Opc = ISD::OR; break; 01681 case ISD::SETULT: CC1 = ISD::SETLT; CC2 = ISD::SETUO; Opc = ISD::OR; break; 01682 case ISD::SETULE: CC1 = ISD::SETLE; CC2 = ISD::SETUO; Opc = ISD::OR; break; 01683 case ISD::SETUNE: CC1 = ISD::SETNE; CC2 = ISD::SETUO; Opc = ISD::OR; break; 01684 // FIXME: Implement more expansions. 01685 } 01686 01687 SDValue SetCC1 = DAG.getSetCC(dl, VT, LHS, RHS, CC1); 01688 SDValue SetCC2 = DAG.getSetCC(dl, VT, LHS, RHS, CC2); 01689 LHS = DAG.getNode(Opc, dl, VT, SetCC1, SetCC2); 01690 RHS = SDValue(); 01691 CC = SDValue(); 01692 break; 01693 } 01694 } 01695 } 01696 01697 /// EmitStackConvert - Emit a store/load combination to the stack. This stores 01698 /// SrcOp to a stack slot of type SlotVT, truncating it if needed. It then does 01699 /// a load from the stack slot to DestVT, extending it if needed. 01700 /// The resultant code need not be legal. 01701 SDValue SelectionDAGLegalize::EmitStackConvert(SDValue SrcOp, 01702 EVT SlotVT, 01703 EVT DestVT, 01704 DebugLoc dl) { 01705 // Create the stack frame object. 01706 unsigned SrcAlign = 01707 TLI.getTargetData()->getPrefTypeAlignment(SrcOp.getValueType(). 01708 getTypeForEVT(*DAG.getContext())); 01709 SDValue FIPtr = DAG.CreateStackTemporary(SlotVT, SrcAlign); 01710 01711 FrameIndexSDNode *StackPtrFI = cast<FrameIndexSDNode>(FIPtr); 01712 int SPFI = StackPtrFI->getIndex(); 01713 const Value *SV = PseudoSourceValue::getFixedStack(SPFI); 01714 01715 unsigned SrcSize = SrcOp.getValueType().getSizeInBits(); 01716 unsigned SlotSize = SlotVT.getSizeInBits(); 01717 unsigned DestSize = DestVT.getSizeInBits(); 01718 unsigned DestAlign = 01719 TLI.getTargetData()->getPrefTypeAlignment(DestVT.getTypeForEVT(*DAG.getContext())); 01720 01721 // Emit a store to the stack slot. Use a truncstore if the input value is 01722 // later than DestVT. 01723 SDValue Store; 01724 01725 if (SrcSize > SlotSize) 01726 Store = DAG.getTruncStore(DAG.getEntryNode(), dl, SrcOp, FIPtr, 01727 SV, 0, SlotVT, false, SrcAlign); 01728 else { 01729 assert(SrcSize == SlotSize && "Invalid store"); 01730 Store = DAG.getStore(DAG.getEntryNode(), dl, SrcOp, FIPtr, 01731 SV, 0, false, SrcAlign); 01732 } 01733 01734 // Result is a load from the stack slot. 01735 if (SlotSize == DestSize) 01736 return DAG.getLoad(DestVT, dl, Store, FIPtr, SV, 0, false, DestAlign); 01737 01738 assert(SlotSize < DestSize && "Unknown extension!"); 01739 return DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT, Store, FIPtr, SV, 0, SlotVT, 01740 false, DestAlign); 01741 } 01742 01743 SDValue SelectionDAGLegalize::ExpandSCALAR_TO_VECTOR(SDNode *Node) { 01744 DebugLoc dl = Node->getDebugLoc(); 01745 // Create a vector sized/aligned stack slot, store the value to element #0, 01746 // then load the whole vector back out. 01747 SDValue StackPtr = DAG.CreateStackTemporary(Node->getValueType(0)); 01748 01749 FrameIndexSDNode *StackPtrFI = cast<FrameIndexSDNode>(StackPtr); 01750 int SPFI = StackPtrFI->getIndex(); 01751 01752 SDValue Ch = DAG.getTruncStore(DAG.getEntryNode(), dl, Node->getOperand(0), 01753 StackPtr, 01754 PseudoSourceValue::getFixedStack(SPFI), 0, 01755 Node->getValueType(0).getVectorElementType()); 01756 return DAG.getLoad(Node->getValueType(0), dl, Ch, StackPtr, 01757 PseudoSourceValue::getFixedStack(SPFI), 0); 01758 } 01759 01760 01761 /// ExpandBUILD_VECTOR - Expand a BUILD_VECTOR node on targets that don't 01762 /// support the operation, but do support the resultant vector type. 01763 SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) { 01764 unsigned NumElems = Node->getNumOperands(); 01765 SDValue Value1, Value2; 01766 DebugLoc dl = Node->getDebugLoc(); 01767 EVT VT = Node->getValueType(0); 01768 EVT OpVT = Node->getOperand(0).getValueType(); 01769 EVT EltVT = VT.getVectorElementType(); 01770 01771 // If the only non-undef value is the low element, turn this into a 01772 // SCALAR_TO_VECTOR node. If this is { X, X, X, X }, determine X. 01773 bool isOnlyLowElement = true; 01774 bool MoreThanTwoValues = false; 01775 bool isConstant = true; 01776 for (unsigned i = 0; i < NumElems; ++i) { 01777 SDValue V = Node->getOperand(i); 01778 if (V.getOpcode() == ISD::UNDEF) 01779 continue; 01780 if (i > 0) 01781 isOnlyLowElement = false; 01782 if (!isa<ConstantFPSDNode>(V) && !isa<ConstantSDNode>(V)) 01783 isConstant = false; 01784 01785 if (!Value1.getNode()) { 01786 Value1 = V; 01787 } else if (!Value2.getNode()) { 01788 if (V != Value1) 01789 Value2 = V; 01790 } else if (V != Value1 && V != Value2) { 01791 MoreThanTwoValues = true; 01792 } 01793 } 01794 01795 if (!Value1.getNode()) 01796 return DAG.getUNDEF(VT); 01797 01798 if (isOnlyLowElement) 01799 return DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Node->getOperand(0)); 01800 01801 // If all elements are constants, create a load from the constant pool. 01802 if (isConstant) { 01803 std::vector<Constant*> CV; 01804 for (unsigned i = 0, e = NumElems; i != e; ++i) { 01805 if (ConstantFPSDNode *V = 01806 dyn_cast<ConstantFPSDNode>(Node->getOperand(i))) { 01807 CV.push_back(const_cast<ConstantFP *>(V->getConstantFPValue())); 01808 } else if (ConstantSDNode *V = 01809 dyn_cast<ConstantSDNode>(Node->getOperand(i))) { 01810 CV.push_back(const_cast<ConstantInt *>(V->getConstantIntValue())); 01811 } else { 01812 assert(Node->getOperand(i).getOpcode() == ISD::UNDEF); 01813 const Type *OpNTy = OpVT.getTypeForEVT(*DAG.getContext()); 01814 CV.push_back(UndefValue::get(OpNTy)); 01815 } 01816 } 01817 Constant *CP = ConstantVector::get(CV); 01818 SDValue CPIdx = DAG.getConstantPool(CP, TLI.getPointerTy()); 01819 unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment(); 01820 return DAG.getLoad(VT, dl, DAG.getEntryNode(), CPIdx, 01821 PseudoSourceValue::getConstantPool(), 0, 01822 false, Alignment); 01823 } 01824 01825 if (!MoreThanTwoValues) { 01826 SmallVector<int, 8> ShuffleVec(NumElems, -1); 01827 for (unsigned i = 0; i < NumElems; ++i) { 01828 SDValue V = Node->getOperand(i); 01829 if (V.getOpcode() == ISD::UNDEF) 01830 continue; 01831 ShuffleVec[i] = V == Value1 ? 0 : NumElems; 01832 } 01833 if (TLI.isShuffleMaskLegal(ShuffleVec, Node->getValueType(0))) { 01834 // Get the splatted value into the low element of a vector register. 01835 SDValue Vec1 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Value1); 01836 SDValue Vec2; 01837 if (Value2.getNode()) 01838 Vec2 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Value2); 01839 else 01840 Vec2 = DAG.getUNDEF(VT); 01841 01842 // Return shuffle(LowValVec, undef, <0,0,0,0>) 01843 return DAG.getVectorShuffle(VT, dl, Vec1, Vec2, ShuffleVec.data()); 01844 } 01845 } 01846 01847 // Otherwise, we can't handle this case efficiently. 01848 return ExpandVectorBuildThroughStack(Node); 01849 } 01850 01851 // ExpandLibCall - Expand a node into a call to a libcall. If the result value 01852 // does not fit into a register, return the lo part and set the hi part to the 01853 // by-reg argument. If it does fit into a single register, return the result 01854 // and leave the Hi part unset. 01855 SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, SDNode *Node, 01856 bool isSigned) { 01857 assert(!IsLegalizingCall && "Cannot overlap legalization of calls!"); 01858 // The input chain to this libcall is the entry node of the function. 01859 // Legalizing the call will automatically add the previous call to the 01860 // dependence. 01861 SDValue InChain = DAG.getEntryNode(); 01862 01863 TargetLowering::ArgListTy Args; 01864 TargetLowering::ArgListEntry Entry; 01865 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 01866 EVT ArgVT = Node->getOperand(i).getValueType(); 01867 const Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext()); 01868 Entry.Node = Node->getOperand(i); Entry.Ty = ArgTy; 01869 Entry.isSExt = isSigned; 01870 Entry.isZExt = !isSigned; 01871 Args.push_back(Entry); 01872 } 01873 SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC), 01874 TLI.getPointerTy()); 01875 01876 // Splice the libcall in wherever FindInputOutputChains tells us to. 01877 const Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext()); 01878 std::pair<SDValue, SDValue> CallInfo = 01879 TLI.LowerCallTo(InChain, RetTy, isSigned, !isSigned, false, false, 01880 0, TLI.getLibcallCallingConv(LC), false, 01881 /*isReturnValueUsed=*/true, 01882 Callee, Args, DAG, 01883 Node->getDebugLoc()); 01884 01885 // Legalize the call sequence, starting with the chain. This will advance 01886 // the LastCALLSEQ_END to the legalized version of the CALLSEQ_END node that 01887 // was added by LowerCallTo (guaranteeing proper serialization of calls). 01888 LegalizeOp(CallInfo.second); 01889 return CallInfo.first; 01890 } 01891 01892 SDValue SelectionDAGLegalize::ExpandFPLibCall(SDNode* Node, 01893 RTLIB::Libcall Call_F32, 01894 RTLIB::Libcall Call_F64, 01895 RTLIB::Libcall Call_F80, 01896 RTLIB::Libcall Call_PPCF128) { 01897 RTLIB::Libcall LC; 01898 switch (Node->getValueType(0).getSimpleVT().SimpleTy) { 01899 default: llvm_unreachable("Unexpected request for libcall!"); 01900 case MVT::f32: LC = Call_F32; break; 01901 case MVT::f64: LC = Call_F64; break; 01902 case MVT::f80: LC = Call_F80; break; 01903 case MVT::ppcf128: LC = Call_PPCF128; break; 01904 } 01905 return ExpandLibCall(LC, Node, false); 01906 } 01907 01908 SDValue SelectionDAGLegalize::ExpandIntLibCall(SDNode* Node, bool isSigned, 01909 RTLIB::Libcall Call_I16, 01910 RTLIB::Libcall Call_I32, 01911 RTLIB::Libcall Call_I64, 01912 RTLIB::Libcall Call_I128) { 01913 RTLIB::Libcall LC; 01914 switch (Node->getValueType(0).getSimpleVT().SimpleTy) { 01915 default: llvm_unreachable("Unexpected request for libcall!"); 01916 case MVT::i16: LC = Call_I16; break; 01917 case MVT::i32: LC = Call_I32; break; 01918 case MVT::i64: LC = Call_I64; break; 01919 case MVT::i128: LC = Call_I128; break; 01920 } 01921 return ExpandLibCall(LC, Node, isSigned); 01922 } 01923 01924 /// ExpandLegalINT_TO_FP - This function is responsible for legalizing a 01925 /// INT_TO_FP operation of the specified operand when the target requests that 01926 /// we expand it. At this point, we know that the result and operand types are 01927 /// legal for the target. 01928 SDValue SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned, 01929 SDValue Op0, 01930 EVT DestVT, 01931 DebugLoc dl) { 01932 if (Op0.getValueType() == MVT::i32) { 01933 // simple 32-bit [signed|unsigned] integer to float/double expansion 01934 01935 // Get the stack frame index of a 8 byte buffer. 01936 SDValue StackSlot = DAG.CreateStackTemporary(MVT::f64); 01937 01938 // word offset constant for Hi/Lo address computation 01939 SDValue WordOff = DAG.getConstant(sizeof(int), TLI.getPointerTy()); 01940 // set up Hi and Lo (into buffer) address based on endian 01941 SDValue Hi = StackSlot; 01942 SDValue Lo = DAG.getNode(ISD::ADD, dl, 01943 TLI.getPointerTy(), StackSlot, WordOff); 01944 if (TLI.isLittleEndian()) 01945 std::swap(Hi, Lo); 01946 01947 // if signed map to unsigned space 01948 SDValue Op0Mapped; 01949 if (isSigned) { 01950 // constant used to invert sign bit (signed to unsigned mapping) 01951 SDValue SignBit = DAG.getConstant(0x80000000u, MVT::i32); 01952 Op0Mapped = DAG.getNode(ISD::XOR, dl, MVT::i32, Op0, SignBit); 01953 } else { 01954 Op0Mapped = Op0; 01955 } 01956 // store the lo of the constructed double - based on integer input 01957 SDValue Store1 = DAG.getStore(DAG.getEntryNode(), dl, 01958 Op0Mapped, Lo, NULL, 0); 01959 // initial hi portion of constructed double 01960 SDValue InitialHi = DAG.getConstant(0x43300000u, MVT::i32); 01961 // store the hi of the constructed double - biased exponent 01962 SDValue Store2=DAG.getStore(Store1, dl, InitialHi, Hi, NULL, 0); 01963 // load the constructed double 01964 SDValue Load = DAG.getLoad(MVT::f64, dl, Store2, StackSlot, NULL, 0); 01965 // FP constant to bias correct the final result 01966 SDValue Bias = DAG.getConstantFP(isSigned ? 01967 BitsToDouble(0x4330000080000000ULL) : 01968 BitsToDouble(0x4330000000000000ULL), 01969 MVT::f64); 01970 // subtract the bias 01971 SDValue Sub = DAG.getNode(ISD::FSUB, dl, MVT::f64, Load, Bias); 01972 // final result 01973 SDValue Result; 01974 // handle final rounding 01975 if (DestVT == MVT::f64) { 01976 // do nothing 01977 Result = Sub; 01978 } else if (DestVT.bitsLT(MVT::f64)) { 01979 Result = DAG.getNode(ISD::FP_ROUND, dl, DestVT, Sub, 01980 DAG.getIntPtrConstant(0)); 01981 } else if (DestVT.bitsGT(MVT::f64)) { 01982 Result = DAG.getNode(ISD::FP_EXTEND, dl, DestVT, Sub); 01983 } 01984 return Result; 01985 } 01986 assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet"); 01987 SDValue Tmp1 = DAG.getNode(ISD::SINT_TO_FP, dl, DestVT, Op0); 01988 01989 SDValue SignSet = DAG.getSetCC(dl, TLI.getSetCCResultType(Op0.getValueType()), 01990 Op0, DAG.getConstant(0, Op0.getValueType()), 01991 ISD::SETLT); 01992 SDValue Zero = DAG.getIntPtrConstant(0), Four = DAG.getIntPtrConstant(4); 01993 SDValue CstOffset = DAG.getNode(ISD::SELECT, dl, Zero.getValueType(), 01994 SignSet, Four, Zero); 01995 01996 // If the sign bit of the integer is set, the large number will be treated 01997 // as a negative number. To counteract this, the dynamic code adds an 01998 // offset depending on the data type. 01999 uint64_t FF; 02000 switch (Op0.getValueType().getSimpleVT().SimpleTy) { 02001 default: llvm_unreachable("Unsupported integer type!"); 02002 case MVT::i8 : FF = 0x43800000ULL; break; // 2^8 (as a float) 02003 case MVT::i16: FF = 0x47800000ULL; break; // 2^16 (as a float) 02004 case MVT::i32: FF = 0x4F800000ULL; break; // 2^32 (as a float) 02005 case MVT::i64: FF = 0x5F800000ULL; break; // 2^64 (as a float) 02006 } 02007 if (TLI.isLittleEndian()) FF <<= 32; 02008 Constant *FudgeFactor = ConstantInt::get( 02009 Type::getInt64Ty(*DAG.getContext()), FF); 02010 02011 SDValue CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy()); 02012 unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment(); 02013 CPIdx = DAG.getNode(ISD::ADD, dl, TLI.getPointerTy(), CPIdx, CstOffset); 02014 Alignment = std::min(Alignment, 4u); 02015 SDValue FudgeInReg; 02016 if (DestVT == MVT::f32) 02017 FudgeInReg = DAG.getLoad(MVT::f32, dl, DAG.getEntryNode(), CPIdx, 02018 PseudoSourceValue::getConstantPool(), 0, 02019 false, Alignment); 02020 else { 02021 FudgeInReg = 02022 LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT, 02023 DAG.getEntryNode(), CPIdx, 02024 PseudoSourceValue::getConstantPool(), 0, 02025 MVT::f32, false, Alignment)); 02026 } 02027 02028 return DAG.getNode(ISD::FADD, dl, DestVT, Tmp1, FudgeInReg); 02029 } 02030 02031 /// PromoteLegalINT_TO_FP - This function is responsible for legalizing a 02032 /// *INT_TO_FP operation of the specified operand when the target requests that 02033 /// we promote it. At this point, we know that the result and operand types are 02034 /// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP 02035 /// operation that takes a larger input. 02036 SDValue SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDValue LegalOp, 02037 EVT DestVT, 02038 bool isSigned, 02039 DebugLoc dl) { 02040 // First step, figure out the appropriate *INT_TO_FP operation to use. 02041 EVT NewInTy = LegalOp.getValueType(); 02042 02043 unsigned OpToUse = 0; 02044 02045 // Scan for the appropriate larger type to use. 02046 while (1) { 02047 NewInTy = (MVT::SimpleValueType)(NewInTy.getSimpleVT().SimpleTy+1); 02048 assert(NewInTy.isInteger() && "Ran out of possibilities!"); 02049 02050 // If the target supports SINT_TO_FP of this type, use it. 02051 if (TLI.isOperationLegalOrCustom(ISD::SINT_TO_FP, NewInTy)) { 02052 OpToUse = ISD::SINT_TO_FP; 02053 break; 02054 } 02055 if (isSigned) continue; 02056 02057 // If the target supports UINT_TO_FP of this type, use it. 02058 if (TLI.isOperationLegalOrCustom(ISD::UINT_TO_FP, NewInTy)) { 02059 OpToUse = ISD::UINT_TO_FP; 02060 break; 02061 } 02062 02063 // Otherwise, try a larger type. 02064 } 02065 02066 // Okay, we found the operation and type to use. Zero extend our input to the 02067 // desired type then run the operation on it. 02068 return DAG.getNode(OpToUse, dl, DestVT, 02069 DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND, 02070 dl, NewInTy, LegalOp)); 02071 } 02072 02073 /// PromoteLegalFP_TO_INT - This function is responsible for legalizing a 02074 /// FP_TO_*INT operation of the specified operand when the target requests that 02075 /// we promote it. At this point, we know that the result and operand types are 02076 /// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT 02077 /// operation that returns a larger result. 02078 SDValue SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDValue LegalOp, 02079 EVT DestVT, 02080 bool isSigned, 02081 DebugLoc dl) { 02082 // First step, figure out the appropriate FP_TO*INT operation to use. 02083 EVT NewOutTy = DestVT; 02084 02085 unsigned OpToUse = 0; 02086 02087 // Scan for the appropriate larger type to use. 02088 while (1) { 02089 NewOutTy = (MVT::SimpleValueType)(NewOutTy.getSimpleVT().SimpleTy+1); 02090 assert(NewOutTy.isInteger() && "Ran out of possibilities!"); 02091 02092 if (TLI.isOperationLegalOrCustom(ISD::FP_TO_SINT, NewOutTy)) { 02093 OpToUse = ISD::FP_TO_SINT; 02094 break; 02095 } 02096 02097 if (TLI.isOperationLegalOrCustom(ISD::FP_TO_UINT, NewOutTy)) { 02098 OpToUse = ISD::FP_TO_UINT; 02099 break; 02100 } 02101 02102 // Otherwise, try a larger type. 02103 } 02104 02105 02106 // Okay, we found the operation and type to use. 02107 SDValue Operation = DAG.getNode(OpToUse, dl, NewOutTy, LegalOp); 02108 02109 // Truncate the result of the extended FP_TO_*INT operation to the desired 02110 // size. 02111 return DAG.getNode(ISD::TRUNCATE, dl, DestVT, Operation); 02112 } 02113 02114 /// ExpandBSWAP - Open code the operations for BSWAP of the specified operation. 02115 /// 02116 SDValue SelectionDAGLegalize::ExpandBSWAP(SDValue Op, DebugLoc dl) { 02117 EVT VT = Op.getValueType(); 02118 EVT SHVT = TLI.getShiftAmountTy(); 02119 SDValue Tmp1, Tmp2, Tmp3, Tmp4, Tmp5, Tmp6, Tmp7, Tmp8; 02120 switch (VT.getSimpleVT().SimpleTy) { 02121 default: llvm_unreachable("Unhandled Expand type in BSWAP!"); 02122 case MVT::i16: 02123 Tmp2 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, SHVT)); 02124 Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, SHVT)); 02125 return DAG.getNode(ISD::OR, dl, VT, Tmp1, Tmp2); 02126 case MVT::i32: 02127 Tmp4 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(24, SHVT)); 02128 Tmp3 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, SHVT)); 02129 Tmp2 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, SHVT)); 02130 Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(24, SHVT)); 02131 Tmp3 = DAG.getNode(ISD::AND, dl, VT, Tmp3, DAG.getConstant(0xFF0000, VT)); 02132 Tmp2 = DAG.getNode(ISD::AND, dl, VT, Tmp2, DAG.getConstant(0xFF00, VT)); 02133 Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp3); 02134 Tmp2 = DAG.getNode(ISD::OR, dl, VT, Tmp2, Tmp1); 02135 return DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp2); 02136 case MVT::i64: 02137 Tmp8 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(56, SHVT)); 02138 Tmp7 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(40, SHVT)); 02139 Tmp6 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(24, SHVT)); 02140 Tmp5 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, SHVT)); 02141 Tmp4 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, SHVT)); 02142 Tmp3 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(24, SHVT)); 02143 Tmp2 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(40, SHVT)); 02144 Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(56, SHVT)); 02145 Tmp7 = DAG.getNode(ISD::AND, dl, VT, Tmp7, DAG.getConstant(255ULL<<48, VT)); 02146 Tmp6 = DAG.getNode(ISD::AND, dl, VT, Tmp6, DAG.getConstant(255ULL<<40, VT)); 02147 Tmp5 = DAG.getNode(ISD::AND, dl, VT, Tmp5, DAG.getConstant(255ULL<<32, VT)); 02148 Tmp4 = DAG.getNode(ISD::AND, dl, VT, Tmp4, DAG.getConstant(255ULL<<24, VT)); 02149 Tmp3 = DAG.getNode(ISD::AND, dl, VT, Tmp3, DAG.getConstant(255ULL<<16, VT)); 02150 Tmp2 = DAG.getNode(ISD::AND, dl, VT, Tmp2, DAG.getConstant(255ULL<<8 , VT)); 02151 Tmp8 = DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp7); 02152 Tmp6 = DAG.getNode(ISD::OR, dl, VT, Tmp6, Tmp5); 02153 Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp3); 02154 Tmp2 = DAG.getNode(ISD::OR, dl, VT, Tmp2, Tmp1); 02155 Tmp8 = DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp6); 02156 Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp2); 02157 return DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp4); 02158 } 02159 } 02160 02161 /// ExpandBitCount - Expand the specified bitcount instruction into operations. 02162 /// 02163 SDValue SelectionDAGLegalize::ExpandBitCount(unsigned Opc, SDValue Op, 02164 DebugLoc dl) { 02165 switch (Opc) { 02166 default: llvm_unreachable("Cannot expand this yet!"); 02167 case ISD::CTPOP: { 02168 static const uint64_t mask[6] = { 02169 0x5555555555555555ULL, 0x3333333333333333ULL, 02170 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL, 02171 0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL 02172 }; 02173 EVT VT = Op.getValueType(); 02174 EVT ShVT = TLI.getShiftAmountTy(); 02175 unsigned len = VT.getSizeInBits(); 02176 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { 02177 //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8]) 02178 unsigned EltSize = VT.isVector() ? 02179 VT.getVectorElementType().getSizeInBits() : len; 02180 SDValue Tmp2 = DAG.getConstant(APInt(EltSize, mask[i]), VT); 02181 SDValue Tmp3 = DAG.getConstant(1ULL << i, ShVT); 02182 Op = DAG.getNode(ISD::ADD, dl, VT, 02183 DAG.getNode(ISD::AND, dl, VT, Op, Tmp2), 02184 DAG.getNode(ISD::AND, dl, VT, 02185 DAG.getNode(ISD::SRL, dl, VT, Op, Tmp3), 02186 Tmp2)); 02187 } 02188 return Op; 02189 } 02190 case ISD::CTLZ: { 02191 // for now, we do this: 02192 // x = x | (x >> 1); 02193 // x = x | (x >> 2); 02194 // ... 02195 // x = x | (x >>16); 02196 // x = x | (x >>32); // for 64-bit input 02197 // return popcount(~x); 02198 // 02199 // but see also: http://www.hackersdelight.org/HDcode/nlz.cc 02200 EVT VT = Op.getValueType(); 02201 EVT ShVT = TLI.getShiftAmountTy(); 02202 unsigned len = VT.getSizeInBits(); 02203 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { 02204 SDValue Tmp3 = DAG.getConstant(1ULL << i, ShVT); 02205 Op = DAG.getNode(ISD::OR, dl, VT, Op, 02206 DAG.getNode(ISD::SRL, dl, VT, Op, Tmp3)); 02207 } 02208 Op = DAG.getNOT(dl, Op, VT); 02209 return DAG.getNode(ISD::CTPOP, dl, VT, Op); 02210 } 02211 case ISD::CTTZ: { 02212 // for now, we use: { return popcount(~x & (x - 1)); } 02213 // unless the target has ctlz but not ctpop, in which case we use: 02214 // { return 32 - nlz(~x & (x-1)); } 02215 // see also http://www.hackersdelight.org/HDcode/ntz.cc 02216 EVT VT = Op.getValueType(); 02217 SDValue Tmp3 = DAG.getNode(ISD::AND, dl, VT, 02218 DAG.getNOT(dl, Op, VT), 02219 DAG.getNode(ISD::SUB, dl, VT, Op, 02220 DAG.getConstant(1, VT))); 02221 // If ISD::CTLZ is legal and CTPOP isn't, then do that instead. 02222 if (!TLI.isOperationLegalOrCustom(ISD::CTPOP, VT) && 02223 TLI.isOperationLegalOrCustom(ISD::CTLZ, VT)) 02224 return DAG.getNode(ISD::SUB, dl, VT, 02225 DAG.getConstant(VT.getSizeInBits(), VT), 02226 DAG.getNode(ISD::CTLZ, dl, VT, Tmp3)); 02227 return DAG.getNode(ISD::CTPOP, dl, VT, Tmp3); 02228 } 02229 } 02230 } 02231 02232 void SelectionDAGLegalize::ExpandNode(SDNode *Node, 02233 SmallVectorImpl<SDValue> &Results) { 02234 DebugLoc dl = Node->getDebugLoc(); 02235 SDValue Tmp1, Tmp2, Tmp3, Tmp4; 02236 switch (Node->getOpcode()) { 02237 case ISD::CTPOP: 02238 case ISD::CTLZ: 02239 case ISD::CTTZ: 02240 Tmp1 = ExpandBitCount(Node->getOpcode(), Node->getOperand(0), dl); 02241 Results.push_back(Tmp1); 02242 break; 02243 case ISD::BSWAP: 02244 Results.push_back(ExpandBSWAP(Node->getOperand(0), dl)); 02245 break; 02246 case ISD::FRAMEADDR: 02247 case ISD::RETURNADDR: 02248 case ISD::FRAME_TO_ARGS_OFFSET: 02249 Results.push_back(DAG.getConstant(0, Node->getValueType(0))); 02250 break; 02251 case ISD::FLT_ROUNDS_: 02252 Results.push_back(DAG.getConstant(1, Node->getValueType(0))); 02253 break; 02254 case ISD::EH_RETURN: 02255 case ISD::DECLARE: 02256 case ISD::DBG_LABEL: 02257 case ISD::EH_LABEL: 02258 case ISD::PREFETCH: 02259 case ISD::MEMBARRIER: 02260 case ISD::VAEND: 02261 Results.push_back(Node->getOperand(0)); 02262 break; 02263 case ISD::DBG_STOPPOINT: 02264 Results.push_back(ExpandDBG_STOPPOINT(Node)); 02265 break; 02266 case ISD::DYNAMIC_STACKALLOC: 02267 ExpandDYNAMIC_STACKALLOC(Node, Results); 02268 break; 02269 case ISD::MERGE_VALUES: 02270 for (unsigned i = 0; i < Node->getNumValues(); i++) 02271 Results.push_back(Node->getOperand(i)); 02272 break; 02273 case ISD::UNDEF: { 02274 EVT VT = Node->getValueType(0); 02275 if (VT.isInteger()) 02276 Results.push_back(DAG.getConstant(0, VT)); 02277 else if (VT.isFloatingPoint()) 02278 Results.push_back(DAG.getConstantFP(0, VT)); 02279 else 02280 llvm_unreachable("Unknown value type!"); 02281 break; 02282 } 02283 case ISD::TRAP: { 02284 // If this operation is not supported, lower it to 'abort()' call 02285 TargetLowering::ArgListTy Args; 02286 std::pair<SDValue, SDValue> CallResult = 02287 TLI.LowerCallTo(Node->getOperand(0), Type::getVoidTy(*DAG.getContext()), 02288 false, false, false, false, 0, CallingConv::C, false, 02289 /*isReturnValueUsed=*/true, 02290 DAG.getExternalSymbol("abort", TLI.getPointerTy()), 02291 Args, DAG, dl); 02292 Results.push_back(CallResult.second); 02293 break; 02294 } 02295 case ISD::FP_ROUND: 02296 case ISD::BIT_CONVERT: 02297 Tmp1 = EmitStackConvert(Node->getOperand(0), Node->getValueType(0), 02298 Node->getValueType(0), dl); 02299 Results.push_back(Tmp1); 02300 break; 02301 case ISD::FP_EXTEND: 02302 Tmp1 = EmitStackConvert(Node->getOperand(0), 02303 Node->getOperand(0).getValueType(), 02304 Node->getValueType(0), dl); 02305 Results.push_back(Tmp1); 02306 break; 02307 case ISD::SIGN_EXTEND_INREG: { 02308 // NOTE: we could fall back on load/store here too for targets without 02309 // SAR. However, it is doubtful that any exist. 02310 EVT ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT(); 02311 unsigned BitsDiff = Node->getValueType(0).getSizeInBits() - 02312 ExtraVT.getSizeInBits(); 02313 SDValue ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy()); 02314 Tmp1 = DAG.getNode(ISD::SHL, dl, Node->getValueType(0), 02315 Node->getOperand(0), ShiftCst); 02316 Tmp1 = DAG.getNode(ISD::SRA, dl, Node->getValueType(0), Tmp1, ShiftCst); 02317 Results.push_back(Tmp1); 02318 break; 02319 } 02320 case ISD::FP_ROUND_INREG: { 02321 // The only way we can lower this is to turn it into a TRUNCSTORE, 02322 // EXTLOAD pair, targetting a temporary location (a stack slot). 02323 02324 // NOTE: there is a choice here between constantly creating new stack 02325 // slots and always reusing the same one. We currently always create 02326 // new ones, as reuse may inhibit scheduling. 02327 EVT ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT(); 02328 Tmp1 = EmitStackConvert(Node->getOperand(0), ExtraVT, 02329 Node->getValueType(0), dl); 02330 Results.push_back(Tmp1); 02331 break; 02332 } 02333 case ISD::SINT_TO_FP: 02334 case ISD::UINT_TO_FP: 02335 Tmp1 = ExpandLegalINT_TO_FP(Node->getOpcode() == ISD::SINT_TO_FP, 02336 Node->getOperand(0), Node->getValueType(0), dl); 02337 Results.push_back(Tmp1); 02338 break; 02339 case ISD::FP_TO_UINT: { 02340 SDValue True, False; 02341 EVT VT = Node->getOperand(0).getValueType(); 02342 EVT NVT = Node->getValueType(0); 02343 const uint64_t zero[] = {0, 0}; 02344 APFloat apf = APFloat(APInt(VT.getSizeInBits(), 2, zero)); 02345 APInt x = APInt::getSignBit(NVT.getSizeInBits()); 02346 (void)apf.convertFromAPInt(x, false, APFloat::rmNearestTiesToEven); 02347 Tmp1 = DAG.getConstantFP(apf, VT); 02348 Tmp2 = DAG.getSetCC(dl, TLI.getSetCCResultType(VT), 02349 Node->getOperand(0), 02350 Tmp1, ISD::SETLT); 02351 True = DAG.getNode(ISD::FP_TO_SINT, dl, NVT, Node->getOperand(0)); 02352 False = DAG.getNode(ISD::FP_TO_SINT, dl, NVT, 02353 DAG.getNode(ISD::FSUB, dl, VT, 02354 Node->getOperand(0), Tmp1)); 02355 False = DAG.getNode(ISD::XOR, dl, NVT, False, 02356 DAG.getConstant(x, NVT)); 02357 Tmp1 = DAG.getNode(ISD::SELECT, dl, NVT, Tmp2, True, False); 02358 Results.push_back(Tmp1); 02359 break; 02360 } 02361 case ISD::VAARG: { 02362 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue(); 02363 EVT VT = Node->getValueType(0); 02364 Tmp1 = Node->getOperand(0); 02365 Tmp2 = Node->getOperand(1); 02366 SDValue VAList = DAG.getLoad(TLI.getPointerTy(), dl, Tmp1, Tmp2, V, 0); 02367 // Increment the pointer, VAList, to the next vaarg 02368 Tmp3 = DAG.getNode(ISD::ADD, dl, TLI.getPointerTy(), VAList, 02369 DAG.getConstant(TLI.getTargetData()-> 02370 getTypeAllocSize(VT.getTypeForEVT(*DAG.getContext())), 02371 TLI.getPointerTy())); 02372 // Store the incremented VAList to the legalized pointer 02373 Tmp3 = DAG.getStore(VAList.getValue(1), dl, Tmp3, Tmp2, V, 0); 02374 // Load the actual argument out of the pointer VAList 02375 Results.push_back(DAG.getLoad(VT, dl, Tmp3, VAList, NULL, 0)); 02376 Results.push_back(Results[0].getValue(1)); 02377 break; 02378 } 02379 case ISD::VACOPY: { 02380 // This defaults to loading a pointer from the input and storing it to the 02381 // output, returning the chain. 02382 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue(); 02383 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue(); 02384 Tmp1 = DAG.getLoad(TLI.getPointerTy(), dl, Node->getOperand(0), 02385 Node->getOperand(2), VS, 0); 02386 Tmp1 = DAG.getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1), VD, 0); 02387 Results.push_back(Tmp1); 02388 break; 02389 } 02390 case ISD::EXTRACT_VECTOR_ELT: 02391 if (Node->getOperand(0).getValueType().getVectorNumElements() == 1) 02392 // This must be an access of the only element. Return it. 02393 Tmp1 = DAG.getNode(ISD::BIT_CONVERT, dl, Node->getValueType(0), 02394 Node->getOperand(0)); 02395 else 02396 Tmp1 = ExpandExtractFromVectorThroughStack(SDValue(Node, 0)); 02397 Results.push_back(Tmp1); 02398 break; 02399 case ISD::EXTRACT_SUBVECTOR: 02400 Results.push_back(ExpandExtractFromVectorThroughStack(SDValue(Node, 0))); 02401 break; 02402 case ISD::CONCAT_VECTORS: { 02403 Results.push_back(ExpandVectorBuildThroughStack(Node)); 02404 break; 02405 } 02406 case ISD::SCALAR_TO_VECTOR: 02407 Results.push_back(ExpandSCALAR_TO_VECTOR(Node)); 02408 break; 02409 case ISD::INSERT_VECTOR_ELT: 02410 Results.push_back(ExpandINSERT_VECTOR_ELT(Node->getOperand(0), 02411 Node->getOperand(1), 02412 Node->getOperand(2), dl)); 02413 break; 02414 case ISD::VECTOR_SHUFFLE: { 02415 SmallVector<int, 8> Mask; 02416 cast<ShuffleVectorSDNode>(Node)->getMask(Mask); 02417 02418 EVT VT = Node->getValueType(0); 02419 EVT EltVT = VT.getVectorElementType(); 02420 unsigned NumElems = VT.getVectorNumElements(); 02421 SmallVector<SDValue, 8> Ops; 02422 for (unsigned i = 0; i != NumElems; ++i) { 02423 if (Mask[i] < 0) { 02424 Ops.push_back(DAG.getUNDEF(EltVT)); 02425 continue; 02426 } 02427 unsigned Idx = Mask[i]; 02428 if (Idx < NumElems) 02429 Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, 02430 Node->getOperand(0), 02431 DAG.getIntPtrConstant(Idx))); 02432 else 02433 Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, 02434 Node->getOperand(1), 02435 DAG.getIntPtrConstant(Idx - NumElems))); 02436 } 02437 Tmp1 = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], Ops.size()); 02438 Results.push_back(Tmp1); 02439 break; 02440 } 02441 case ISD::EXTRACT_ELEMENT: { 02442 EVT OpTy = Node->getOperand(0).getValueType(); 02443 if (cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue()) { 02444 // 1 -> Hi 02445 Tmp1 = DAG.getNode(ISD::SRL, dl, OpTy, Node->getOperand(0), 02446 DAG.getConstant(OpTy.getSizeInBits()/2, 02447 TLI.getShiftAmountTy())); 02448 Tmp1 = DAG.getNode(ISD::TRUNCATE, dl, Node->getValueType(0), Tmp1); 02449 } else { 02450 // 0 -> Lo 02451 Tmp1 = DAG.getNode(ISD::TRUNCATE, dl, Node->getValueType(0), 02452 Node->getOperand(0)); 02453 } 02454 Results.push_back(Tmp1); 02455 break; 02456 } 02457 case ISD::STACKSAVE: 02458 // Expand to CopyFromReg if the target set 02459 // StackPointerRegisterToSaveRestore. 02460 if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) { 02461 Results.push_back(DAG.getCopyFromReg(Node->getOperand(0), dl, SP, 02462 Node->getValueType(0))); 02463 Results.push_back(Results[0].getValue(1)); 02464 } else { 02465 Results.push_back(DAG.getUNDEF(Node->getValueType(0))); 02466 Results.push_back(Node->getOperand(0)); 02467 } 02468 break; 02469 case ISD::STACKRESTORE: 02470 // Expand to CopyToReg if the target set 02471 // StackPointerRegisterToSaveRestore. 02472 if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) { 02473 Results.push_back(DAG.getCopyToReg(Node->getOperand(0), dl, SP, 02474 Node->getOperand(1))); 02475 } else { 02476 Results.push_back(Node->getOperand(0)); 02477 } 02478 break; 02479 case ISD::FCOPYSIGN: 02480 Results.push_back(ExpandFCOPYSIGN(Node)); 02481 break; 02482 case ISD::FNEG: 02483 // Expand Y = FNEG(X) -> Y = SUB -0.0, X 02484 Tmp1 = DAG.getConstantFP(-0.0, Node->getValueType(0)); 02485 Tmp1 = DAG.getNode(ISD::FSUB, dl, Node->getValueType(0), Tmp1, 02486 Node->getOperand(0)); 02487 Results.push_back(Tmp1); 02488 break; 02489 case ISD::FABS: { 02490 // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X). 02491 EVT VT = Node->getValueType(0); 02492 Tmp1 = Node->getOperand(0); 02493 Tmp2 = DAG.getConstantFP(0.0, VT); 02494 Tmp2 = DAG.getSetCC(dl, TLI.getSetCCResultType(Tmp1.getValueType()), 02495 Tmp1, Tmp2, ISD::SETUGT); 02496 Tmp3 = DAG.getNode(ISD::FNEG, dl, VT, Tmp1); 02497 Tmp1 = DAG.getNode(ISD::SELECT, dl, VT, Tmp2, Tmp1, Tmp3); 02498 Results.push_back(Tmp1); 02499 break; 02500 } 02501 case ISD::FSQRT: 02502 Results.push_back(ExpandFPLibCall(Node, RTLIB::SQRT_F32, RTLIB::SQRT_F64, 02503 RTLIB::SQRT_F80, RTLIB::SQRT_PPCF128)); 02504 break; 02505 case ISD::FSIN: 02506 Results.push_back(ExpandFPLibCall(Node, RTLIB::SIN_F32, RTLIB::SIN_F64, 02507 RTLIB::SIN_F80, RTLIB::SIN_PPCF128)); 02508 break; 02509 case ISD::FCOS: 02510 Results.push_back(ExpandFPLibCall(Node, RTLIB::COS_F32, RTLIB::COS_F64, 02511 RTLIB::COS_F80, RTLIB::COS_PPCF128)); 02512 break; 02513 case ISD::FLOG: 02514 Results.push_back(ExpandFPLibCall(Node, RTLIB::LOG_F32, RTLIB::LOG_F64, 02515 RTLIB::LOG_F80, RTLIB::LOG_PPCF128)); 02516 break; 02517 case ISD::FLOG2: 02518 Results.push_back(ExpandFPLibCall(Node, RTLIB::LOG2_F32, RTLIB::LOG2_F64, 02519 RTLIB::LOG2_F80, RTLIB::LOG2_PPCF128)); 02520 break; 02521 case ISD::FLOG10: 02522 Results.push_back(ExpandFPLibCall(Node, RTLIB::LOG10_F32, RTLIB::LOG10_F64, 02523 RTLIB::LOG10_F80, RTLIB::LOG10_PPCF128)); 02524 break; 02525 case ISD::FEXP: 02526 Results.push_back(ExpandFPLibCall(Node, RTLIB::EXP_F32, RTLIB::EXP_F64, 02527 RTLIB::EXP_F80, RTLIB::EXP_PPCF128)); 02528 break; 02529 case ISD::FEXP2: 02530 Results.push_back(ExpandFPLibCall(Node, RTLIB::EXP2_F32, RTLIB::EXP2_F64, 02531 RTLIB::EXP2_F80, RTLIB::EXP2_PPCF128)); 02532 break; 02533 case ISD::FTRUNC: 02534 Results.push_back(ExpandFPLibCall(Node, RTLIB::TRUNC_F32, RTLIB::TRUNC_F64, 02535 RTLIB::TRUNC_F80, RTLIB::TRUNC_PPCF128)); 02536 break; 02537 case ISD::FFLOOR: 02538 Results.push_back(ExpandFPLibCall(Node, RTLIB::FLOOR_F32, RTLIB::FLOOR_F64, 02539 RTLIB::FLOOR_F80, RTLIB::FLOOR_PPCF128)); 02540 break; 02541 case ISD::FCEIL: 02542 Results.push_back(ExpandFPLibCall(Node, RTLIB::CEIL_F32, RTLIB::CEIL_F64, 02543 RTLIB::CEIL_F80, RTLIB::CEIL_PPCF128)); 02544 break; 02545 case ISD::FRINT: 02546 Results.push_back(ExpandFPLibCall(Node, RTLIB::RINT_F32, RTLIB::RINT_F64, 02547 RTLIB::RINT_F80, RTLIB::RINT_PPCF128)); 02548 break; 02549 case ISD::FNEARBYINT: 02550 Results.push_back(ExpandFPLibCall(Node, RTLIB::NEARBYINT_F32, 02551 RTLIB::NEARBYINT_F64, 02552 RTLIB::NEARBYINT_F80, 02553 RTLIB::NEARBYINT_PPCF128)); 02554 break; 02555 case ISD::FPOWI: 02556 Results.push_back(ExpandFPLibCall(Node, RTLIB::POWI_F32, RTLIB::POWI_F64, 02557 RTLIB::POWI_F80, RTLIB::POWI_PPCF128)); 02558 break; 02559 case ISD::FPOW: 02560 Results.push_back(ExpandFPLibCall(Node, RTLIB::POW_F32, RTLIB::POW_F64, 02561 RTLIB::POW_F80, RTLIB::POW_PPCF128)); 02562 break; 02563 case ISD::FDIV: 02564 Results.push_back(ExpandFPLibCall(Node, RTLIB::DIV_F32, RTLIB::DIV_F64, 02565 RTLIB::DIV_F80, RTLIB::DIV_PPCF128)); 02566 break; 02567 case ISD::FREM: 02568 Results.push_back(ExpandFPLibCall(Node, RTLIB::REM_F32, RTLIB::REM_F64, 02569 RTLIB::REM_F80, RTLIB::REM_PPCF128)); 02570 break; 02571 case ISD::ConstantFP: { 02572 ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node); 02573 // Check to see if this FP immediate is already legal. 02574 bool isLegal = false; 02575 for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(), 02576 E = TLI.legal_fpimm_end(); I != E; ++I) { 02577 if (CFP->isExactlyValue(*I)) { 02578 isLegal = true; 02579 break; 02580 } 02581 } 02582 // If this is a legal constant, turn it into a TargetConstantFP node. 02583 if (isLegal) 02584 Results.push_back(SDValue(Node, 0)); 02585 else 02586 Results.push_back(ExpandConstantFP(CFP, true, DAG, TLI)); 02587 break; 02588 } 02589 case ISD::EHSELECTION: { 02590 unsigned Reg = TLI.getExceptionSelectorRegister(); 02591 assert(Reg && "Can't expand to unknown register!"); 02592 Results.push_back(DAG.getCopyFromReg(Node->getOperand(1), dl, Reg, 02593 Node->getValueType(0))); 02594 Results.push_back(Results[0].getValue(1)); 02595 break; 02596 } 02597 case ISD::EXCEPTIONADDR: { 02598 unsigned Reg = TLI.getExceptionAddressRegister(); 02599 assert(Reg && "Can't expand to unknown register!"); 02600 Results.push_back(DAG.getCopyFromReg(Node->getOperand(0), dl, Reg, 02601 Node->getValueType(0))); 02602 Results.push_back(Results[0].getValue(1)); 02603 break; 02604 } 02605 case ISD::SUB: { 02606 EVT VT = Node->getValueType(0); 02607 assert(TLI.isOperationLegalOrCustom(ISD::ADD, VT) && 02608 TLI.isOperationLegalOrCustom(ISD::XOR, VT) && 02609 "Don't know how to expand this subtraction!"); 02610 Tmp1 = DAG.getNode(ISD::XOR, dl, VT, Node->getOperand(1), 02611 DAG.getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT)); 02612 Tmp1 = DAG.getNode(ISD::ADD, dl, VT, Tmp2, DAG.getConstant(1, VT)); 02613 Results.push_back(DAG.getNode(ISD::ADD, dl, VT, Node->getOperand(0), Tmp1)); 02614 break; 02615 } 02616 case ISD::UREM: 02617 case ISD::SREM: { 02618 EVT VT = Node->getValueType(0); 02619 SDVTList VTs = DAG.getVTList(VT, VT); 02620 bool isSigned = Node->getOpcode() == ISD::SREM; 02621 unsigned DivOpc = isSigned ? ISD::SDIV : ISD::UDIV; 02622 unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM; 02623 Tmp2 = Node->getOperand(0); 02624 Tmp3 = Node->getOperand(1); 02625 if (TLI.isOperationLegalOrCustom(DivRemOpc, VT)) { 02626 Tmp1 = DAG.getNode(DivRemOpc, dl, VTs, Tmp2, Tmp3).getValue(1); 02627 } else if (TLI.isOperationLegalOrCustom(DivOpc, VT)) { 02628 // X % Y -> X-X/Y*Y 02629 Tmp1 = DAG.getNode(DivOpc, dl, VT, Tmp2, Tmp3); 02630 Tmp1 = DAG.getNode(ISD::MUL, dl, VT, Tmp1, Tmp3); 02631 Tmp1 = DAG.getNode(ISD::SUB, dl, VT, Tmp2, Tmp1); 02632 } else if (isSigned) { 02633 Tmp1 = ExpandIntLibCall(Node, true, RTLIB::SREM_I16, RTLIB::SREM_I32, 02634 RTLIB::SREM_I64, RTLIB::SREM_I128); 02635 } else { 02636 Tmp1 = ExpandIntLibCall(Node, false, RTLIB::UREM_I16, RTLIB::UREM_I32, 02637 RTLIB::UREM_I64, RTLIB::UREM_I128); 02638 } 02639 Results.push_back(Tmp1); 02640 break; 02641 } 02642 case ISD::UDIV: 02643 case ISD::SDIV: { 02644 bool isSigned = Node->getOpcode() == ISD::SDIV; 02645 unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM; 02646 EVT VT = Node->getValueType(0); 02647 SDVTList VTs = DAG.getVTList(VT, VT); 02648 if (TLI.isOperationLegalOrCustom(DivRemOpc, VT)) 02649 Tmp1 = DAG.getNode(DivRemOpc, dl, VTs, Node->getOperand(0), 02650 Node->getOperand(1)); 02651 else if (isSigned) 02652 Tmp1 = ExpandIntLibCall(Node, true, RTLIB::SDIV_I16, RTLIB::SDIV_I32, 02653 RTLIB::SDIV_I64, RTLIB::SDIV_I128); 02654 else 02655 Tmp1 = ExpandIntLibCall(Node, false, RTLIB::UDIV_I16, RTLIB::UDIV_I32, 02656 RTLIB::UDIV_I64, RTLIB::UDIV_I128); 02657 Results.push_back(Tmp1); 02658 break; 02659 } 02660 case ISD::MULHU: 02661 case ISD::MULHS: { 02662 unsigned ExpandOpcode = Node->getOpcode() == ISD::MULHU ? ISD::UMUL_LOHI : 02663 ISD::SMUL_LOHI; 02664 EVT VT = Node->getValueType(0); 02665 SDVTList VTs = DAG.getVTList(VT, VT); 02666 assert(TLI.isOperationLegalOrCustom(ExpandOpcode, VT) && 02667 "If this wasn't legal, it shouldn't have been created!"); 02668 Tmp1 = DAG.getNode(ExpandOpcode, dl, VTs, Node->getOperand(0), 02669 Node->getOperand(1)); 02670 Results.push_back(Tmp1.getValue(1)); 02671 break; 02672 } 02673 case ISD::MUL: { 02674 EVT VT = Node->getValueType(0); 02675 SDVTList VTs = DAG.getVTList(VT, VT); 02676 // See if multiply or divide can be lowered using two-result operations. 02677 // We just need the low half of the multiply; try both the signed 02678 // and unsigned forms. If the target supports both SMUL_LOHI and 02679 // UMUL_LOHI, form a preference by checking which forms of plain 02680 // MULH it supports. 02681 bool HasSMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::SMUL_LOHI, VT); 02682 bool HasUMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::UMUL_LOHI, VT); 02683 bool HasMULHS = TLI.isOperationLegalOrCustom(ISD::MULHS, VT); 02684 bool HasMULHU = TLI.isOperationLegalOrCustom(ISD::MULHU, VT); 02685 unsigned OpToUse = 0; 02686 if (HasSMUL_LOHI && !HasMULHS) { 02687 OpToUse = ISD::SMUL_LOHI; 02688 } else if (HasUMUL_LOHI && !HasMULHU) { 02689 OpToUse = ISD::UMUL_LOHI; 02690 } else if (HasSMUL_LOHI) { 02691 OpToUse = ISD::SMUL_LOHI; 02692 } else if (HasUMUL_LOHI) { 02693 OpToUse = ISD::UMUL_LOHI; 02694 } 02695 if (OpToUse) { 02696 Results.push_back(DAG.getNode(OpToUse, dl, VTs, Node->getOperand(0), 02697 Node->getOperand(1))); 02698 break; 02699 } 02700 Tmp1 = ExpandIntLibCall(Node, false, RTLIB::MUL_I16, RTLIB::MUL_I32, 02701 RTLIB::MUL_I64, RTLIB::MUL_I128); 02702 Results.push_back(Tmp1); 02703 break; 02704 } 02705 case ISD::SADDO: 02706 case ISD::SSUBO: { 02707 SDValue LHS = Node->getOperand(0); 02708 SDValue RHS = Node->getOperand(1); 02709 SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::SADDO ? 02710 ISD::ADD : ISD::SUB, dl, LHS.getValueType(), 02711 LHS, RHS); 02712 Results.push_back(Sum); 02713 EVT OType = Node->getValueType(1); 02714 02715 SDValue Zero = DAG.getConstant(0, LHS.getValueType()); 02716 02717 // LHSSign -> LHS >= 0 02718 // RHSSign -> RHS >= 0 02719 // SumSign -> Sum >= 0 02720 // 02721 // Add: 02722 // Overflow -> (LHSSign == RHSSign) && (LHSSign != SumSign) 02723 // Sub: 02724 // Overflow -> (LHSSign != RHSSign) && (LHSSign != SumSign) 02725 // 02726 SDValue LHSSign = DAG.getSetCC(dl, OType, LHS, Zero, ISD::SETGE); 02727 SDValue RHSSign = DAG.getSetCC(dl, OType, RHS, Zero, ISD::SETGE); 02728 SDValue SignsMatch = DAG.getSetCC(dl, OType, LHSSign, RHSSign, 02729 Node->getOpcode() == ISD::SADDO ? 02730 ISD::SETEQ : ISD::SETNE); 02731 02732 SDValue SumSign = DAG.getSetCC(dl, OType, Sum, Zero, ISD::SETGE); 02733 SDValue SumSignNE = DAG.getSetCC(dl, OType, LHSSign, SumSign, ISD::SETNE); 02734 02735 SDValue Cmp = DAG.getNode(ISD::AND, dl, OType, SignsMatch, SumSignNE); 02736 Results.push_back(Cmp); 02737 break; 02738 } 02739 case ISD::UADDO: 02740 case ISD::USUBO: { 02741 SDValue LHS = Node->getOperand(0); 02742 SDValue RHS = Node->getOperand(1); 02743 SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::UADDO ? 02744 ISD::ADD : ISD::SUB, dl, LHS.getValueType(), 02745 LHS, RHS); 02746 Results.push_back(Sum); 02747 Results.push_back(DAG.getSetCC(dl, Node->getValueType(1), Sum, LHS, 02748 Node->getOpcode () == ISD::UADDO ? 02749 ISD::SETULT : ISD::SETUGT)); 02750 break; 02751 } 02752 case ISD::UMULO: 02753 case ISD::SMULO: { 02754 EVT VT = Node->getValueType(0); 02755 SDValue LHS = Node->getOperand(0); 02756 SDValue RHS = Node->getOperand(1); 02757 SDValue BottomHalf; 02758 SDValue TopHalf; 02759 static unsigned Ops[2][3] = 02760 { { ISD::MULHU, ISD::UMUL_LOHI, ISD::ZERO_EXTEND }, 02761 { ISD::MULHS, ISD::SMUL_LOHI, ISD::SIGN_EXTEND }}; 02762 bool isSigned = Node->getOpcode() == ISD::SMULO; 02763 if (TLI.isOperationLegalOrCustom(Ops[isSigned][0], VT)) { 02764 BottomHalf = DAG.getNode(ISD::MUL, dl, VT, LHS, RHS); 02765 TopHalf = DAG.getNode(Ops[isSigned][0], dl, VT, LHS, RHS); 02766 } else if (TLI.isOperationLegalOrCustom(Ops[isSigned][1], VT)) { 02767 BottomHalf = DAG.getNode(Ops[isSigned][1], dl, DAG.getVTList(VT, VT), LHS, 02768 RHS); 02769 TopHalf = BottomHalf.getValue(1); 02770 } else if (TLI.isTypeLegal(EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits() * 2))) { 02771 EVT WideVT = EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits() * 2); 02772 LHS = DAG.getNode(Ops[isSigned][2], dl, WideVT, LHS); 02773 RHS = DAG.getNode(Ops[isSigned][2], dl, WideVT, RHS); 02774 Tmp1 = DAG.getNode(ISD::MUL, dl, WideVT, LHS, RHS); 02775 BottomHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Tmp1, 02776 DAG.getIntPtrConstant(0)); 02777 TopHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Tmp1, 02778 DAG.getIntPtrConstant(1)); 02779 } else { 02780 // FIXME: We should be able to fall back to a libcall with an illegal 02781 // type in some cases cases. 02782 // Also, we can fall back to a division in some cases, but that's a big 02783 // performance hit in the general case. 02784 llvm_unreachable("Don't know how to expand this operation yet!"); 02785 } 02786 if (isSigned) { 02787 Tmp1 = DAG.getConstant(VT.getSizeInBits() - 1, TLI.getShiftAmountTy()); 02788 Tmp1 = DAG.getNode(ISD::SRA, dl, VT, BottomHalf, Tmp1); 02789 TopHalf = DAG.getSetCC(dl, TLI.getSetCCResultType(VT), TopHalf, Tmp1, 02790 ISD::SETNE); 02791 } else { 02792 TopHalf = DAG.getSetCC(dl, TLI.getSetCCResultType(VT), TopHalf, 02793 DAG.getConstant(0, VT), ISD::SETNE); 02794 } 02795 Results.push_back(BottomHalf); 02796 Results.push_back(TopHalf); 02797 break; 02798 } 02799 case ISD::BUILD_PAIR: { 02800 EVT PairTy = Node->getValueType(0); 02801 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, PairTy, Node->getOperand(0)); 02802 Tmp2 = DAG.getNode(ISD::ANY_EXTEND, dl, PairTy, Node->getOperand(1)); 02803 Tmp2 = DAG.getNode(ISD::SHL, dl, PairTy, Tmp2, 02804 DAG.getConstant(PairTy.getSizeInBits()/2, 02805 TLI.getShiftAmountTy())); 02806 Results.push_back(DAG.getNode(ISD::OR, dl, PairTy, Tmp1, Tmp2)); 02807 break; 02808 } 02809 case ISD::SELECT: 02810 Tmp1 = Node->getOperand(0); 02811 Tmp2 = Node->getOperand(1); 02812 Tmp3 = Node->getOperand(2); 02813 if (Tmp1.getOpcode() == ISD::SETCC) { 02814 Tmp1 = DAG.getSelectCC(dl, Tmp1.getOperand(0), Tmp1.getOperand(1), 02815 Tmp2, Tmp3, 02816 cast<CondCodeSDNode>(Tmp1.getOperand(2))->get()); 02817 } else { 02818 Tmp1 = DAG.getSelectCC(dl, Tmp1, 02819 DAG.getConstant(0, Tmp1.getValueType()), 02820 Tmp2, Tmp3, ISD::SETNE); 02821 } 02822 Results.push_back(Tmp1); 02823 break; 02824 case ISD::BR_JT: { 02825 SDValue Chain = Node->getOperand(0); 02826 SDValue Table = Node->getOperand(1); 02827 SDValue Index = Node->getOperand(2); 02828 02829 EVT PTy = TLI.getPointerTy(); 02830 MachineFunction &MF = DAG.getMachineFunction(); 02831 unsigned EntrySize = MF.getJumpTableInfo()->getEntrySize(); 02832 Index= DAG.getNode(ISD::MUL, dl, PTy, 02833 Index, DAG.getConstant(EntrySize, PTy)); 02834 SDValue Addr = DAG.getNode(ISD::ADD, dl, PTy, Index, Table); 02835 02836 EVT MemVT = EVT::getIntegerVT(*DAG.getContext(), EntrySize * 8); 02837 SDValue LD = DAG.getExtLoad(ISD::SEXTLOAD, dl, PTy, Chain, Addr, 02838 PseudoSourceValue::getJumpTable(), 0, MemVT); 02839 Addr = LD; 02840 if (TLI.getTargetMachine().getRelocationModel() == Reloc::PIC_) { 02841 // For PIC, the sequence is: 02842 // BRIND(load(Jumptable + index) + RelocBase) 02843 // RelocBase can be JumpTable, GOT or some sort of global base. 02844 Addr = DAG.getNode(ISD::ADD, dl, PTy, Addr, 02845 TLI.getPICJumpTableRelocBase(Table, DAG)); 02846 } 02847 Tmp1 = DAG.getNode(ISD::BRIND, dl, MVT::Other, LD.getValue(1), Addr); 02848 Results.push_back(Tmp1); 02849 break; 02850 } 02851 case ISD::BRCOND: 02852 // Expand brcond's setcc into its constituent parts and create a BR_CC 02853 // Node. 02854 Tmp1 = Node->getOperand(0); 02855 Tmp2 = Node->getOperand(1); 02856 if (Tmp2.getOpcode() == ISD::SETCC) { 02857 Tmp1 = DAG.getNode(ISD::BR_CC, dl, MVT::Other, 02858 Tmp1, Tmp2.getOperand(2), 02859 Tmp2.getOperand(0), Tmp2.getOperand(1), 02860 Node->getOperand(2)); 02861 } else { 02862 Tmp1 = DAG.getNode(ISD::BR_CC, dl, MVT::Other, Tmp1, 02863 DAG.getCondCode(ISD::SETNE), Tmp2, 02864 DAG.getConstant(0, Tmp2.getValueType()), 02865 Node->getOperand(2)); 02866 } 02867 Results.push_back(Tmp1); 02868 break; 02869 case ISD::SETCC: { 02870 Tmp1 = Node->getOperand(0); 02871 Tmp2 = Node->getOperand(1); 02872 Tmp3 = Node->getOperand(2); 02873 LegalizeSetCCCondCode(Node->getValueType(0), Tmp1, Tmp2, Tmp3, dl); 02874 02875 // If we expanded the SETCC into an AND/OR, return the new node 02876 if (Tmp2.getNode() == 0) { 02877 Results.push_back(Tmp1); 02878 break; 02879 } 02880 02881 // Otherwise, SETCC for the given comparison type must be completely 02882 // illegal; expand it into a SELECT_CC. 02883 EVT VT = Node->getValueType(0); 02884 Tmp1 = DAG.getNode(ISD::SELECT_CC, dl, VT, Tmp1, Tmp2, 02885 DAG.getConstant(1, VT), DAG.getConstant(0, VT), Tmp3); 02886 Results.push_back(Tmp1); 02887 break; 02888 } 02889 case ISD::SELECT_CC: { 02890 Tmp1 = Node->getOperand(0); // LHS 02891 Tmp2 = Node->getOperand(1); // RHS 02892 Tmp3 = Node->getOperand(2); // True 02893 Tmp4 = Node->getOperand(3); // False 02894 SDValue CC = Node->getOperand(4); 02895 02896 LegalizeSetCCCondCode(TLI.getSetCCResultType(Tmp1.getValueType()), 02897 Tmp1, Tmp2, CC, dl); 02898 02899 assert(!Tmp2.getNode() && "Can't legalize SELECT_CC with legal condition!"); 02900 Tmp2 = DAG.getConstant(0, Tmp1.getValueType()); 02901 CC = DAG.getCondCode(ISD::SETNE); 02902 Tmp1 = DAG.getNode(ISD::SELECT_CC, dl, Node->getValueType(0), Tmp1, Tmp2, 02903 Tmp3, Tmp4, CC); 02904 Results.push_back(Tmp1); 02905 break; 02906 } 02907 case ISD::BR_CC: { 02908 Tmp1 = Node->getOperand(0); // Chain 02909 Tmp2 = Node->getOperand(2); // LHS 02910 Tmp3 = Node->getOperand(3); // RHS 02911 Tmp4 = Node->getOperand(1); // CC 02912 02913 LegalizeSetCCCondCode(TLI.getSetCCResultType(Tmp2.getValueType()), 02914 Tmp2, Tmp3, Tmp4, dl); 02915 LastCALLSEQ_END = DAG.getEntryNode(); 02916 02917 assert(!Tmp3.getNode() && "Can't legalize BR_CC with legal condition!"); 02918 Tmp3 = DAG.getConstant(0, Tmp2.getValueType()); 02919 Tmp4 = DAG.getCondCode(ISD::SETNE); 02920 Tmp1 = DAG.getNode(ISD::BR_CC, dl, Node->getValueType(0), Tmp1, Tmp4, Tmp2, 02921 Tmp3, Node->getOperand(4)); 02922 Results.push_back(Tmp1); 02923 break; 02924 } 02925 case ISD::GLOBAL_OFFSET_TABLE: 02926 case ISD::GlobalAddress: 02927 case ISD::GlobalTLSAddress: 02928 case ISD::ExternalSymbol: 02929 case ISD::ConstantPool: 02930 case ISD::JumpTable: 02931 case ISD::INTRINSIC_W_CHAIN: 02932 case ISD::INTRINSIC_WO_CHAIN: 02933 case ISD::INTRINSIC_VOID: 02934 // FIXME: Custom lowering for these operations shouldn't return null! 02935 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 02936 Results.push_back(SDValue(Node, i)); 02937 break; 02938 } 02939 } 02940 void SelectionDAGLegalize::PromoteNode(SDNode *Node, 02941 SmallVectorImpl<SDValue> &Results) { 02942 EVT OVT = Node->getValueType(0); 02943 if (Node->getOpcode() == ISD::UINT_TO_FP || 02944 Node->getOpcode() == ISD::SINT_TO_FP || 02945 Node->getOpcode() == ISD::SETCC) { 02946 OVT = Node->getOperand(0).getValueType(); 02947 } 02948 EVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT); 02949 DebugLoc dl = Node->getDebugLoc(); 02950 SDValue Tmp1, Tmp2, Tmp3; 02951 switch (Node->getOpcode()) { 02952 case ISD::CTTZ: 02953 case ISD::CTLZ: 02954 case ISD::CTPOP: 02955 // Zero extend the argument. 02956 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Node->getOperand(0)); 02957 // Perform the larger operation. 02958 Tmp1 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1); 02959 if (Node->getOpcode() == ISD::CTTZ) { 02960 //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT) 02961 Tmp2 = DAG.getSetCC(dl, TLI.getSetCCResultType(NVT), 02962 Tmp1, DAG.getConstant(NVT.getSizeInBits(), NVT), 02963 ISD::SETEQ); 02964 Tmp1 = DAG.getNode(ISD::SELECT, dl, NVT, Tmp2, 02965 DAG.getConstant(OVT.getSizeInBits(), NVT), Tmp1); 02966 } else if (Node->getOpcode() == ISD::CTLZ) { 02967 // Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT)) 02968 Tmp1 = DAG.getNode(ISD::SUB, dl, NVT, Tmp1, 02969 DAG.getConstant(NVT.getSizeInBits() - 02970 OVT.getSizeInBits(), NVT)); 02971 } 02972 Results.push_back(DAG.getNode(ISD::TRUNCATE, dl, OVT, Tmp1)); 02973 break; 02974 case ISD::BSWAP: { 02975 unsigned DiffBits = NVT.getSizeInBits() - OVT.getSizeInBits(); 02976 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Tmp1); 02977 Tmp1 = DAG.getNode(ISD::BSWAP, dl, NVT, Tmp1); 02978 Tmp1 = DAG.getNode(ISD::SRL, dl, NVT, Tmp1, 02979 DAG.getConstant(DiffBits, TLI.getShiftAmountTy())); 02980 Results.push_back(Tmp1); 02981 break; 02982 } 02983 case ISD::FP_TO_UINT: 02984 case ISD::FP_TO_SINT: 02985 Tmp1 = PromoteLegalFP_TO_INT(Node->getOperand(0), Node->getValueType(0), 02986 Node->getOpcode() == ISD::FP_TO_SINT, dl); 02987 Results.push_back(Tmp1); 02988 break; 02989 case ISD::UINT_TO_FP: 02990 case ISD::SINT_TO_FP: 02991 Tmp1 = PromoteLegalINT_TO_FP(Node->getOperand(0), Node->getValueType(0), 02992 Node->getOpcode() == ISD::SINT_TO_FP, dl); 02993 Results.push_back(Tmp1); 02994 break; 02995 case ISD::AND: 02996 case ISD::OR: 02997 case ISD::XOR: { 02998 unsigned ExtOp, TruncOp; 02999 if (OVT.isVector()) { 03000 ExtOp = ISD::BIT_CONVERT; 03001 TruncOp = ISD::BIT_CONVERT; 03002 } else if (OVT.isInteger()) { 03003 ExtOp = ISD::ANY_EXTEND; 03004 TruncOp = ISD::TRUNCATE; 03005 } else { 03006 llvm_report_error("Cannot promote logic operation"); 03007 } 03008 // Promote each of the values to the new type. 03009 Tmp1 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(0)); 03010 Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(1)); 03011 // Perform the larger operation, then convert back 03012 Tmp1 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1, Tmp2); 03013 Results.push_back(DAG.getNode(TruncOp, dl, OVT, Tmp1)); 03014 break; 03015 } 03016 case ISD::SELECT: { 03017 unsigned ExtOp, TruncOp; 03018 if (Node->getValueType(0).isVector()) { 03019 ExtOp = ISD::BIT_CONVERT; 03020 TruncOp = ISD::BIT_CONVERT; 03021 } else if (Node->getValueType(0).isInteger()) { 03022 ExtOp = ISD::ANY_EXTEND; 03023 TruncOp = ISD::TRUNCATE; 03024 } else { 03025 ExtOp = ISD::FP_EXTEND; 03026 TruncOp = ISD::FP_ROUND; 03027 } 03028 Tmp1 = Node->getOperand(0); 03029 // Promote each of the values to the new type. 03030 Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(1)); 03031 Tmp3 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(2)); 03032 // Perform the larger operation, then round down. 03033 Tmp1 = DAG.getNode(ISD::SELECT, dl, NVT, Tmp1, Tmp2, Tmp3); 03034 if (TruncOp != ISD::FP_ROUND) 03035 Tmp1 = DAG.getNode(TruncOp, dl, Node->getValueType(0), Tmp1); 03036 else 03037 Tmp1 = DAG.getNode(TruncOp, dl, Node->getValueType(0), Tmp1, 03038 DAG.getIntPtrConstant(0)); 03039 Results.push_back(Tmp1); 03040 break; 03041 } 03042 case ISD::VECTOR_SHUFFLE: { 03043 SmallVector<int, 8> Mask; 03044 cast<ShuffleVectorSDNode>(Node)->getMask(Mask); 03045 03046 // Cast the two input vectors. 03047 Tmp1 = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Node->getOperand(0)); 03048 Tmp2 = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Node->getOperand(1)); 03049 03050 // Convert the shuffle mask to the right # elements. 03051 Tmp1 = ShuffleWithNarrowerEltType(NVT, OVT, dl, Tmp1, Tmp2, Mask); 03052 Tmp1 = DAG.getNode(ISD::BIT_CONVERT, dl, OVT, Tmp1); 03053 Results.push_back(Tmp1); 03054 break; 03055 } 03056 case ISD::SETCC: { 03057 unsigned ExtOp = ISD::FP_EXTEND; 03058 if (NVT.isInteger()) { 03059 ISD::CondCode CCCode = 03060 cast<CondCodeSDNode>(Node->getOperand(2))->get(); 03061 ExtOp = isSignedIntSetCC(CCCode) ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND; 03062 } 03063 Tmp1 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(0)); 03064 Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(1)); 03065 Results.push_back(DAG.getNode(ISD::SETCC, dl, Node->getValueType(0), 03066 Tmp1, Tmp2, Node->getOperand(2))); 03067 break; 03068 } 03069 } 03070 } 03071 03072 // SelectionDAG::Legalize - This is the entry point for the file. 03073 // 03074 void SelectionDAG::Legalize(bool TypesNeedLegalizing, 03075 CodeGenOpt::Level OptLevel) { 03076 /// run - This is the main entry point to this class. 03077 /// 03078 SelectionDAGLegalize(*this, OptLevel).LegalizeDAG(); 03079 } 03080