LegalizeDAG.cpp revision c02d98e335703d8aa51b42d9b22a1fa2ac5d6c33
1//===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the SelectionDAG::Legalize method. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/CodeGen/SelectionDAG.h" 15#include "llvm/CodeGen/MachineFunction.h" 16#include "llvm/CodeGen/MachineFrameInfo.h" 17#include "llvm/Support/MathExtras.h" 18#include "llvm/Target/TargetLowering.h" 19#include "llvm/Target/TargetData.h" 20#include "llvm/Target/TargetOptions.h" 21#include "llvm/CallingConv.h" 22#include "llvm/Constants.h" 23#include <iostream> 24#include <set> 25using namespace llvm; 26 27//===----------------------------------------------------------------------===// 28/// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and 29/// hacks on it until the target machine can handle it. This involves 30/// eliminating value sizes the machine cannot handle (promoting small sizes to 31/// large sizes or splitting up large values into small values) as well as 32/// eliminating operations the machine cannot handle. 33/// 34/// This code also does a small amount of optimization and recognition of idioms 35/// as part of its processing. For example, if a target does not support a 36/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this 37/// will attempt merge setcc and brc instructions into brcc's. 38/// 39namespace { 40class SelectionDAGLegalize { 41 TargetLowering &TLI; 42 SelectionDAG &DAG; 43 44 /// LegalizeAction - This enum indicates what action we should take for each 45 /// value type the can occur in the program. 46 enum LegalizeAction { 47 Legal, // The target natively supports this value type. 48 Promote, // This should be promoted to the next larger type. 49 Expand, // This integer type should be broken into smaller pieces. 50 }; 51 52 /// ValueTypeActions - This is a bitvector that contains two bits for each 53 /// value type, where the two bits correspond to the LegalizeAction enum. 54 /// This can be queried with "getTypeAction(VT)". 55 unsigned long long ValueTypeActions; 56 57 /// NeedsAnotherIteration - This is set when we expand a large integer 58 /// operation into smaller integer operations, but the smaller operations are 59 /// not set. This occurs only rarely in practice, for targets that don't have 60 /// 32-bit or larger integer registers. 61 bool NeedsAnotherIteration; 62 63 /// LegalizedNodes - For nodes that are of legal width, and that have more 64 /// than one use, this map indicates what regularized operand to use. This 65 /// allows us to avoid legalizing the same thing more than once. 66 std::map<SDOperand, SDOperand> LegalizedNodes; 67 68 /// PromotedNodes - For nodes that are below legal width, and that have more 69 /// than one use, this map indicates what promoted value to use. This allows 70 /// us to avoid promoting the same thing more than once. 71 std::map<SDOperand, SDOperand> PromotedNodes; 72 73 /// ExpandedNodes - For nodes that need to be expanded, and which have more 74 /// than one use, this map indicates which which operands are the expanded 75 /// version of the input. This allows us to avoid expanding the same node 76 /// more than once. 77 std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes; 78 79 void AddLegalizedOperand(SDOperand From, SDOperand To) { 80 LegalizedNodes.insert(std::make_pair(From, To)); 81 // If someone requests legalization of the new node, return itself. 82 if (From != To) 83 LegalizedNodes.insert(std::make_pair(To, To)); 84 } 85 void AddPromotedOperand(SDOperand From, SDOperand To) { 86 bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second; 87 assert(isNew && "Got into the map somehow?"); 88 // If someone requests legalization of the new node, return itself. 89 LegalizedNodes.insert(std::make_pair(To, To)); 90 } 91 92public: 93 94 SelectionDAGLegalize(SelectionDAG &DAG); 95 96 /// Run - While there is still lowering to do, perform a pass over the DAG. 97 /// Most regularization can be done in a single pass, but targets that require 98 /// large values to be split into registers multiple times (e.g. i64 -> 4x 99 /// i16) require iteration for these values (the first iteration will demote 100 /// to i32, the second will demote to i16). 101 void Run() { 102 do { 103 NeedsAnotherIteration = false; 104 LegalizeDAG(); 105 } while (NeedsAnotherIteration); 106 } 107 108 /// getTypeAction - Return how we should legalize values of this type, either 109 /// it is already legal or we need to expand it into multiple registers of 110 /// smaller integer type, or we need to promote it to a larger type. 111 LegalizeAction getTypeAction(MVT::ValueType VT) const { 112 return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3); 113 } 114 115 /// isTypeLegal - Return true if this type is legal on this target. 116 /// 117 bool isTypeLegal(MVT::ValueType VT) const { 118 return getTypeAction(VT) == Legal; 119 } 120 121private: 122 void LegalizeDAG(); 123 124 SDOperand LegalizeOp(SDOperand O); 125 void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi); 126 SDOperand PromoteOp(SDOperand O); 127 128 SDOperand ExpandLibCall(const char *Name, SDNode *Node, 129 SDOperand &Hi); 130 SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, 131 SDOperand Source); 132 133 SDOperand ExpandBIT_CONVERT(MVT::ValueType DestVT, SDOperand SrcOp); 134 SDOperand ExpandLegalINT_TO_FP(bool isSigned, 135 SDOperand LegalOp, 136 MVT::ValueType DestVT); 137 SDOperand PromoteLegalINT_TO_FP(SDOperand LegalOp, MVT::ValueType DestVT, 138 bool isSigned); 139 SDOperand PromoteLegalFP_TO_INT(SDOperand LegalOp, MVT::ValueType DestVT, 140 bool isSigned); 141 142 bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt, 143 SDOperand &Lo, SDOperand &Hi); 144 void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt, 145 SDOperand &Lo, SDOperand &Hi); 146 void ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS, 147 SDOperand &Lo, SDOperand &Hi); 148 149 void SpliceCallInto(const SDOperand &CallResult, SDNode *OutChain); 150 151 SDOperand getIntPtrConstant(uint64_t Val) { 152 return DAG.getConstant(Val, TLI.getPointerTy()); 153 } 154}; 155} 156 157static unsigned getScalarizedOpcode(unsigned VecOp, MVT::ValueType VT) { 158 switch (VecOp) { 159 default: assert(0 && "Don't know how to scalarize this opcode!"); 160 case ISD::VADD: return MVT::isInteger(VT) ? ISD::ADD : ISD::FADD; 161 case ISD::VSUB: return MVT::isInteger(VT) ? ISD::SUB : ISD::FSUB; 162 case ISD::VMUL: return MVT::isInteger(VT) ? ISD::MUL : ISD::FMUL; 163 } 164} 165 166SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag) 167 : TLI(dag.getTargetLoweringInfo()), DAG(dag), 168 ValueTypeActions(TLI.getValueTypeActions()) { 169 assert(MVT::LAST_VALUETYPE <= 32 && 170 "Too many value types for ValueTypeActions to hold!"); 171} 172 173/// ExpandLegalINT_TO_FP - This function is responsible for legalizing a 174/// INT_TO_FP operation of the specified operand when the target requests that 175/// we expand it. At this point, we know that the result and operand types are 176/// legal for the target. 177SDOperand SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned, 178 SDOperand Op0, 179 MVT::ValueType DestVT) { 180 if (Op0.getValueType() == MVT::i32) { 181 // simple 32-bit [signed|unsigned] integer to float/double expansion 182 183 // get the stack frame index of a 8 byte buffer 184 MachineFunction &MF = DAG.getMachineFunction(); 185 int SSFI = MF.getFrameInfo()->CreateStackObject(8, 8); 186 // get address of 8 byte buffer 187 SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); 188 // word offset constant for Hi/Lo address computation 189 SDOperand WordOff = DAG.getConstant(sizeof(int), TLI.getPointerTy()); 190 // set up Hi and Lo (into buffer) address based on endian 191 SDOperand Hi, Lo; 192 if (TLI.isLittleEndian()) { 193 Hi = DAG.getNode(ISD::ADD, TLI.getPointerTy(), StackSlot, WordOff); 194 Lo = StackSlot; 195 } else { 196 Hi = StackSlot; 197 Lo = DAG.getNode(ISD::ADD, TLI.getPointerTy(), StackSlot, WordOff); 198 } 199 // if signed map to unsigned space 200 SDOperand Op0Mapped; 201 if (isSigned) { 202 // constant used to invert sign bit (signed to unsigned mapping) 203 SDOperand SignBit = DAG.getConstant(0x80000000u, MVT::i32); 204 Op0Mapped = DAG.getNode(ISD::XOR, MVT::i32, Op0, SignBit); 205 } else { 206 Op0Mapped = Op0; 207 } 208 // store the lo of the constructed double - based on integer input 209 SDOperand Store1 = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(), 210 Op0Mapped, Lo, DAG.getSrcValue(NULL)); 211 // initial hi portion of constructed double 212 SDOperand InitialHi = DAG.getConstant(0x43300000u, MVT::i32); 213 // store the hi of the constructed double - biased exponent 214 SDOperand Store2 = DAG.getNode(ISD::STORE, MVT::Other, Store1, 215 InitialHi, Hi, DAG.getSrcValue(NULL)); 216 // load the constructed double 217 SDOperand Load = DAG.getLoad(MVT::f64, Store2, StackSlot, 218 DAG.getSrcValue(NULL)); 219 // FP constant to bias correct the final result 220 SDOperand Bias = DAG.getConstantFP(isSigned ? 221 BitsToDouble(0x4330000080000000ULL) 222 : BitsToDouble(0x4330000000000000ULL), 223 MVT::f64); 224 // subtract the bias 225 SDOperand Sub = DAG.getNode(ISD::FSUB, MVT::f64, Load, Bias); 226 // final result 227 SDOperand Result; 228 // handle final rounding 229 if (DestVT == MVT::f64) { 230 // do nothing 231 Result = Sub; 232 } else { 233 // if f32 then cast to f32 234 Result = DAG.getNode(ISD::FP_ROUND, MVT::f32, Sub); 235 } 236 return LegalizeOp(Result); 237 } 238 assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet"); 239 SDOperand Tmp1 = DAG.getNode(ISD::SINT_TO_FP, DestVT, Op0); 240 241 SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Op0, 242 DAG.getConstant(0, Op0.getValueType()), 243 ISD::SETLT); 244 SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4); 245 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(), 246 SignSet, Four, Zero); 247 248 // If the sign bit of the integer is set, the large number will be treated 249 // as a negative number. To counteract this, the dynamic code adds an 250 // offset depending on the data type. 251 uint64_t FF; 252 switch (Op0.getValueType()) { 253 default: assert(0 && "Unsupported integer type!"); 254 case MVT::i8 : FF = 0x43800000ULL; break; // 2^8 (as a float) 255 case MVT::i16: FF = 0x47800000ULL; break; // 2^16 (as a float) 256 case MVT::i32: FF = 0x4F800000ULL; break; // 2^32 (as a float) 257 case MVT::i64: FF = 0x5F800000ULL; break; // 2^64 (as a float) 258 } 259 if (TLI.isLittleEndian()) FF <<= 32; 260 static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF); 261 262 SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy()); 263 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset); 264 SDOperand FudgeInReg; 265 if (DestVT == MVT::f32) 266 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, 267 DAG.getSrcValue(NULL)); 268 else { 269 assert(DestVT == MVT::f64 && "Unexpected conversion"); 270 FudgeInReg = LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, 271 DAG.getEntryNode(), CPIdx, 272 DAG.getSrcValue(NULL), MVT::f32)); 273 } 274 275 return LegalizeOp(DAG.getNode(ISD::FADD, DestVT, Tmp1, FudgeInReg)); 276} 277 278/// PromoteLegalINT_TO_FP - This function is responsible for legalizing a 279/// *INT_TO_FP operation of the specified operand when the target requests that 280/// we promote it. At this point, we know that the result and operand types are 281/// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP 282/// operation that takes a larger input. 283SDOperand SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDOperand LegalOp, 284 MVT::ValueType DestVT, 285 bool isSigned) { 286 // First step, figure out the appropriate *INT_TO_FP operation to use. 287 MVT::ValueType NewInTy = LegalOp.getValueType(); 288 289 unsigned OpToUse = 0; 290 291 // Scan for the appropriate larger type to use. 292 while (1) { 293 NewInTy = (MVT::ValueType)(NewInTy+1); 294 assert(MVT::isInteger(NewInTy) && "Ran out of possibilities!"); 295 296 // If the target supports SINT_TO_FP of this type, use it. 297 switch (TLI.getOperationAction(ISD::SINT_TO_FP, NewInTy)) { 298 default: break; 299 case TargetLowering::Legal: 300 if (!TLI.isTypeLegal(NewInTy)) 301 break; // Can't use this datatype. 302 // FALL THROUGH. 303 case TargetLowering::Custom: 304 OpToUse = ISD::SINT_TO_FP; 305 break; 306 } 307 if (OpToUse) break; 308 if (isSigned) continue; 309 310 // If the target supports UINT_TO_FP of this type, use it. 311 switch (TLI.getOperationAction(ISD::UINT_TO_FP, NewInTy)) { 312 default: break; 313 case TargetLowering::Legal: 314 if (!TLI.isTypeLegal(NewInTy)) 315 break; // Can't use this datatype. 316 // FALL THROUGH. 317 case TargetLowering::Custom: 318 OpToUse = ISD::UINT_TO_FP; 319 break; 320 } 321 if (OpToUse) break; 322 323 // Otherwise, try a larger type. 324 } 325 326 // Okay, we found the operation and type to use. Zero extend our input to the 327 // desired type then run the operation on it. 328 SDOperand N = DAG.getNode(OpToUse, DestVT, 329 DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND, 330 NewInTy, LegalOp)); 331 // Make sure to legalize any nodes we create here. 332 return LegalizeOp(N); 333} 334 335/// PromoteLegalFP_TO_INT - This function is responsible for legalizing a 336/// FP_TO_*INT operation of the specified operand when the target requests that 337/// we promote it. At this point, we know that the result and operand types are 338/// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT 339/// operation that returns a larger result. 340SDOperand SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDOperand LegalOp, 341 MVT::ValueType DestVT, 342 bool isSigned) { 343 // First step, figure out the appropriate FP_TO*INT operation to use. 344 MVT::ValueType NewOutTy = DestVT; 345 346 unsigned OpToUse = 0; 347 348 // Scan for the appropriate larger type to use. 349 while (1) { 350 NewOutTy = (MVT::ValueType)(NewOutTy+1); 351 assert(MVT::isInteger(NewOutTy) && "Ran out of possibilities!"); 352 353 // If the target supports FP_TO_SINT returning this type, use it. 354 switch (TLI.getOperationAction(ISD::FP_TO_SINT, NewOutTy)) { 355 default: break; 356 case TargetLowering::Legal: 357 if (!TLI.isTypeLegal(NewOutTy)) 358 break; // Can't use this datatype. 359 // FALL THROUGH. 360 case TargetLowering::Custom: 361 OpToUse = ISD::FP_TO_SINT; 362 break; 363 } 364 if (OpToUse) break; 365 366 // If the target supports FP_TO_UINT of this type, use it. 367 switch (TLI.getOperationAction(ISD::FP_TO_UINT, NewOutTy)) { 368 default: break; 369 case TargetLowering::Legal: 370 if (!TLI.isTypeLegal(NewOutTy)) 371 break; // Can't use this datatype. 372 // FALL THROUGH. 373 case TargetLowering::Custom: 374 OpToUse = ISD::FP_TO_UINT; 375 break; 376 } 377 if (OpToUse) break; 378 379 // Otherwise, try a larger type. 380 } 381 382 // Okay, we found the operation and type to use. Truncate the result of the 383 // extended FP_TO_*INT operation to the desired size. 384 SDOperand N = DAG.getNode(ISD::TRUNCATE, DestVT, 385 DAG.getNode(OpToUse, NewOutTy, LegalOp)); 386 // Make sure to legalize any nodes we create here in the next pass. 387 return LegalizeOp(N); 388} 389 390/// ComputeTopDownOrdering - Add the specified node to the Order list if it has 391/// not been visited yet and if all of its operands have already been visited. 392static void ComputeTopDownOrdering(SDNode *N, std::vector<SDNode*> &Order, 393 std::map<SDNode*, unsigned> &Visited) { 394 if (++Visited[N] != N->getNumOperands()) 395 return; // Haven't visited all operands yet 396 397 Order.push_back(N); 398 399 if (N->hasOneUse()) { // Tail recurse in common case. 400 ComputeTopDownOrdering(*N->use_begin(), Order, Visited); 401 return; 402 } 403 404 // Now that we have N in, add anything that uses it if all of their operands 405 // are now done. 406 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); UI != E;++UI) 407 ComputeTopDownOrdering(*UI, Order, Visited); 408} 409 410 411void SelectionDAGLegalize::LegalizeDAG() { 412 // The legalize process is inherently a bottom-up recursive process (users 413 // legalize their uses before themselves). Given infinite stack space, we 414 // could just start legalizing on the root and traverse the whole graph. In 415 // practice however, this causes us to run out of stack space on large basic 416 // blocks. To avoid this problem, compute an ordering of the nodes where each 417 // node is only legalized after all of its operands are legalized. 418 std::map<SDNode*, unsigned> Visited; 419 std::vector<SDNode*> Order; 420 421 // Compute ordering from all of the leaves in the graphs, those (like the 422 // entry node) that have no operands. 423 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 424 E = DAG.allnodes_end(); I != E; ++I) { 425 if (I->getNumOperands() == 0) { 426 Visited[I] = 0 - 1U; 427 ComputeTopDownOrdering(I, Order, Visited); 428 } 429 } 430 431 assert(Order.size() == Visited.size() && 432 Order.size() == 433 (unsigned)std::distance(DAG.allnodes_begin(), DAG.allnodes_end()) && 434 "Error: DAG is cyclic!"); 435 Visited.clear(); 436 437 for (unsigned i = 0, e = Order.size(); i != e; ++i) { 438 SDNode *N = Order[i]; 439 switch (getTypeAction(N->getValueType(0))) { 440 default: assert(0 && "Bad type action!"); 441 case Legal: 442 LegalizeOp(SDOperand(N, 0)); 443 break; 444 case Promote: 445 PromoteOp(SDOperand(N, 0)); 446 break; 447 case Expand: { 448 SDOperand X, Y; 449 ExpandOp(SDOperand(N, 0), X, Y); 450 break; 451 } 452 } 453 } 454 455 // Finally, it's possible the root changed. Get the new root. 456 SDOperand OldRoot = DAG.getRoot(); 457 assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?"); 458 DAG.setRoot(LegalizedNodes[OldRoot]); 459 460 ExpandedNodes.clear(); 461 LegalizedNodes.clear(); 462 PromotedNodes.clear(); 463 464 // Remove dead nodes now. 465 DAG.RemoveDeadNodes(OldRoot.Val); 466} 467 468SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { 469 assert(isTypeLegal(Op.getValueType()) && 470 "Caller should expand or promote operands that are not legal!"); 471 SDNode *Node = Op.Val; 472 473 // If this operation defines any values that cannot be represented in a 474 // register on this target, make sure to expand or promote them. 475 if (Node->getNumValues() > 1) { 476 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 477 switch (getTypeAction(Node->getValueType(i))) { 478 case Legal: break; // Nothing to do. 479 case Expand: { 480 SDOperand T1, T2; 481 ExpandOp(Op.getValue(i), T1, T2); 482 assert(LegalizedNodes.count(Op) && 483 "Expansion didn't add legal operands!"); 484 return LegalizedNodes[Op]; 485 } 486 case Promote: 487 PromoteOp(Op.getValue(i)); 488 assert(LegalizedNodes.count(Op) && 489 "Expansion didn't add legal operands!"); 490 return LegalizedNodes[Op]; 491 } 492 } 493 494 // Note that LegalizeOp may be reentered even from single-use nodes, which 495 // means that we always must cache transformed nodes. 496 std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op); 497 if (I != LegalizedNodes.end()) return I->second; 498 499 SDOperand Tmp1, Tmp2, Tmp3, Tmp4; 500 501 SDOperand Result = Op; 502 503 switch (Node->getOpcode()) { 504 default: 505 if (Node->getOpcode() >= ISD::BUILTIN_OP_END) { 506 // If this is a target node, legalize it by legalizing the operands then 507 // passing it through. 508 std::vector<SDOperand> Ops; 509 bool Changed = false; 510 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 511 Ops.push_back(LegalizeOp(Node->getOperand(i))); 512 Changed = Changed || Node->getOperand(i) != Ops.back(); 513 } 514 if (Changed) 515 if (Node->getNumValues() == 1) 516 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops); 517 else { 518 std::vector<MVT::ValueType> VTs(Node->value_begin(), 519 Node->value_end()); 520 Result = DAG.getNode(Node->getOpcode(), VTs, Ops); 521 } 522 523 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 524 AddLegalizedOperand(Op.getValue(i), Result.getValue(i)); 525 return Result.getValue(Op.ResNo); 526 } 527 // Otherwise this is an unhandled builtin node. splat. 528 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 529 assert(0 && "Do not know how to legalize this operator!"); 530 abort(); 531 case ISD::EntryToken: 532 case ISD::FrameIndex: 533 case ISD::TargetFrameIndex: 534 case ISD::Register: 535 case ISD::TargetConstant: 536 case ISD::TargetConstantPool: 537 case ISD::GlobalAddress: 538 case ISD::TargetGlobalAddress: 539 case ISD::ExternalSymbol: 540 case ISD::TargetExternalSymbol: 541 case ISD::ConstantPool: // Nothing to do. 542 case ISD::BasicBlock: 543 case ISD::CONDCODE: 544 case ISD::VALUETYPE: 545 case ISD::SRCVALUE: 546 case ISD::STRING: 547 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 548 default: assert(0 && "This action is not supported yet!"); 549 case TargetLowering::Custom: { 550 SDOperand Tmp = TLI.LowerOperation(Op, DAG); 551 if (Tmp.Val) { 552 Result = LegalizeOp(Tmp); 553 break; 554 } 555 } // FALLTHROUGH if the target doesn't want to lower this op after all. 556 case TargetLowering::Legal: 557 assert(isTypeLegal(Node->getValueType(0)) && "This must be legal!"); 558 break; 559 } 560 break; 561 case ISD::AssertSext: 562 case ISD::AssertZext: 563 Tmp1 = LegalizeOp(Node->getOperand(0)); 564 if (Tmp1 != Node->getOperand(0)) 565 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 566 Node->getOperand(1)); 567 break; 568 case ISD::MERGE_VALUES: 569 return LegalizeOp(Node->getOperand(Op.ResNo)); 570 case ISD::CopyFromReg: 571 Tmp1 = LegalizeOp(Node->getOperand(0)); 572 Result = Op.getValue(0); 573 if (Node->getNumValues() == 2) { 574 if (Tmp1 != Node->getOperand(0)) 575 Result = DAG.getCopyFromReg(Tmp1, 576 cast<RegisterSDNode>(Node->getOperand(1))->getReg(), 577 Node->getValueType(0)); 578 } else { 579 assert(Node->getNumValues() == 3 && "Invalid copyfromreg!"); 580 if (Node->getNumOperands() == 3) 581 Tmp2 = LegalizeOp(Node->getOperand(2)); 582 if (Tmp1 != Node->getOperand(0) || 583 (Node->getNumOperands() == 3 && Tmp2 != Node->getOperand(2))) 584 Result = DAG.getCopyFromReg(Tmp1, 585 cast<RegisterSDNode>(Node->getOperand(1))->getReg(), 586 Node->getValueType(0), Tmp2); 587 AddLegalizedOperand(Op.getValue(2), Result.getValue(2)); 588 } 589 // Since CopyFromReg produces two values, make sure to remember that we 590 // legalized both of them. 591 AddLegalizedOperand(Op.getValue(0), Result); 592 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 593 return Result.getValue(Op.ResNo); 594 case ISD::UNDEF: { 595 MVT::ValueType VT = Op.getValueType(); 596 switch (TLI.getOperationAction(ISD::UNDEF, VT)) { 597 default: assert(0 && "This action is not supported yet!"); 598 case TargetLowering::Expand: 599 case TargetLowering::Promote: 600 if (MVT::isInteger(VT)) 601 Result = DAG.getConstant(0, VT); 602 else if (MVT::isFloatingPoint(VT)) 603 Result = DAG.getConstantFP(0, VT); 604 else 605 assert(0 && "Unknown value type!"); 606 break; 607 case TargetLowering::Legal: 608 break; 609 } 610 break; 611 } 612 613 case ISD::LOCATION: 614 assert(Node->getNumOperands() == 5 && "Invalid LOCATION node!"); 615 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the input chain. 616 617 switch (TLI.getOperationAction(ISD::LOCATION, MVT::Other)) { 618 case TargetLowering::Promote: 619 default: assert(0 && "This action is not supported yet!"); 620 case TargetLowering::Expand: { 621 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 622 bool useDEBUG_LOC = TLI.isOperationLegal(ISD::DEBUG_LOC, MVT::Other); 623 bool useDEBUG_LABEL = TLI.isOperationLegal(ISD::DEBUG_LABEL, MVT::Other); 624 625 if (DebugInfo && (useDEBUG_LOC || useDEBUG_LABEL)) { 626 const std::string &FName = 627 cast<StringSDNode>(Node->getOperand(3))->getValue(); 628 const std::string &DirName = 629 cast<StringSDNode>(Node->getOperand(4))->getValue(); 630 unsigned SrcFile = DebugInfo->getUniqueSourceID(FName, DirName); 631 632 std::vector<SDOperand> Ops; 633 Ops.push_back(Tmp1); // chain 634 SDOperand LineOp = Node->getOperand(1); 635 SDOperand ColOp = Node->getOperand(2); 636 637 if (useDEBUG_LOC) { 638 Ops.push_back(LineOp); // line # 639 Ops.push_back(ColOp); // col # 640 Ops.push_back(DAG.getConstant(SrcFile, MVT::i32)); // source file id 641 Result = DAG.getNode(ISD::DEBUG_LOC, MVT::Other, Ops); 642 } else { 643 unsigned Line = dyn_cast<ConstantSDNode>(LineOp)->getValue(); 644 unsigned Col = dyn_cast<ConstantSDNode>(ColOp)->getValue(); 645 unsigned ID = DebugInfo->RecordLabel(Line, Col, SrcFile); 646 Ops.push_back(DAG.getConstant(ID, MVT::i32)); 647 Result = DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Ops); 648 } 649 } else { 650 Result = Tmp1; // chain 651 } 652 Result = LegalizeOp(Result); // Relegalize new nodes. 653 break; 654 } 655 case TargetLowering::Legal: 656 if (Tmp1 != Node->getOperand(0) || 657 getTypeAction(Node->getOperand(1).getValueType()) == Promote) { 658 std::vector<SDOperand> Ops; 659 Ops.push_back(Tmp1); 660 if (getTypeAction(Node->getOperand(1).getValueType()) == Legal) { 661 Ops.push_back(Node->getOperand(1)); // line # must be legal. 662 Ops.push_back(Node->getOperand(2)); // col # must be legal. 663 } else { 664 // Otherwise promote them. 665 Ops.push_back(PromoteOp(Node->getOperand(1))); 666 Ops.push_back(PromoteOp(Node->getOperand(2))); 667 } 668 Ops.push_back(Node->getOperand(3)); // filename must be legal. 669 Ops.push_back(Node->getOperand(4)); // working dir # must be legal. 670 Result = DAG.getNode(ISD::LOCATION, MVT::Other, Ops); 671 } 672 break; 673 } 674 break; 675 676 case ISD::DEBUG_LOC: 677 assert(Node->getNumOperands() == 4 && "Invalid DEBUG_LOC node!"); 678 switch (TLI.getOperationAction(ISD::DEBUG_LOC, MVT::Other)) { 679 case TargetLowering::Promote: 680 case TargetLowering::Expand: 681 default: assert(0 && "This action is not supported yet!"); 682 case TargetLowering::Legal: 683 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 684 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the line #. 685 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the col #. 686 Tmp4 = LegalizeOp(Node->getOperand(3)); // Legalize the source file id. 687 688 if (Tmp1 != Node->getOperand(0) || 689 Tmp2 != Node->getOperand(1) || 690 Tmp3 != Node->getOperand(2) || 691 Tmp4 != Node->getOperand(3)) { 692 Result = DAG.getNode(ISD::DEBUG_LOC,MVT::Other, Tmp1, Tmp2, Tmp3, Tmp4); 693 } 694 break; 695 } 696 break; 697 698 case ISD::DEBUG_LABEL: 699 assert(Node->getNumOperands() == 2 && "Invalid DEBUG_LABEL node!"); 700 switch (TLI.getOperationAction(ISD::DEBUG_LABEL, MVT::Other)) { 701 case TargetLowering::Promote: 702 case TargetLowering::Expand: 703 default: assert(0 && "This action is not supported yet!"); 704 case TargetLowering::Legal: 705 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 706 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the label id. 707 708 if (Tmp1 != Node->getOperand(0) || 709 Tmp2 != Node->getOperand(1)) { 710 Result = DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Tmp1, Tmp2); 711 } 712 break; 713 } 714 break; 715 716 case ISD::Constant: 717 // We know we don't need to expand constants here, constants only have one 718 // value and we check that it is fine above. 719 720 // FIXME: Maybe we should handle things like targets that don't support full 721 // 32-bit immediates? 722 break; 723 case ISD::ConstantFP: { 724 // Spill FP immediates to the constant pool if the target cannot directly 725 // codegen them. Targets often have some immediate values that can be 726 // efficiently generated into an FP register without a load. We explicitly 727 // leave these constants as ConstantFP nodes for the target to deal with. 728 729 ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node); 730 731 // Check to see if this FP immediate is already legal. 732 bool isLegal = false; 733 for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(), 734 E = TLI.legal_fpimm_end(); I != E; ++I) 735 if (CFP->isExactlyValue(*I)) { 736 isLegal = true; 737 break; 738 } 739 740 if (!isLegal) { 741 // Otherwise we need to spill the constant to memory. 742 bool Extend = false; 743 744 // If a FP immediate is precise when represented as a float, we put it 745 // into the constant pool as a float, even if it's is statically typed 746 // as a double. 747 MVT::ValueType VT = CFP->getValueType(0); 748 bool isDouble = VT == MVT::f64; 749 ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy : 750 Type::FloatTy, CFP->getValue()); 751 if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) && 752 // Only do this if the target has a native EXTLOAD instruction from 753 // f32. 754 TLI.isOperationLegal(ISD::EXTLOAD, MVT::f32)) { 755 LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy)); 756 VT = MVT::f32; 757 Extend = true; 758 } 759 760 SDOperand CPIdx = 761 LegalizeOp(DAG.getConstantPool(LLVMC, TLI.getPointerTy())); 762 if (Extend) { 763 Result = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), 764 CPIdx, DAG.getSrcValue(NULL), MVT::f32); 765 } else { 766 Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx, 767 DAG.getSrcValue(NULL)); 768 } 769 } 770 break; 771 } 772 case ISD::ConstantVec: { 773 // We assume that vector constants are not legal, and will be immediately 774 // spilled to the constant pool. 775 // 776 // FIXME: revisit this when we have some kind of mechanism by which targets 777 // can decided legality of vector constants, of which there may be very 778 // many. 779 // 780 // Create a ConstantPacked, and put it in the constant pool. 781 std::vector<Constant*> CV; 782 MVT::ValueType VT = Node->getValueType(0); 783 for (unsigned I = 0, E = Node->getNumOperands(); I < E; ++I) { 784 SDOperand OpN = Node->getOperand(I); 785 const Type* OpNTy = MVT::getTypeForValueType(OpN.getValueType()); 786 if (MVT::isFloatingPoint(VT)) 787 CV.push_back(ConstantFP::get(OpNTy, 788 cast<ConstantFPSDNode>(OpN)->getValue())); 789 else 790 CV.push_back(ConstantUInt::get(OpNTy, 791 cast<ConstantSDNode>(OpN)->getValue())); 792 } 793 Constant *CP = ConstantPacked::get(CV); 794 SDOperand CPIdx = LegalizeOp(DAG.getConstantPool(CP, TLI.getPointerTy())); 795 Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx, DAG.getSrcValue(NULL)); 796 break; 797 } 798 case ISD::TokenFactor: 799 if (Node->getNumOperands() == 2) { 800 bool Changed = false; 801 SDOperand Op0 = LegalizeOp(Node->getOperand(0)); 802 SDOperand Op1 = LegalizeOp(Node->getOperand(1)); 803 if (Op0 != Node->getOperand(0) || Op1 != Node->getOperand(1)) 804 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Op0, Op1); 805 } else { 806 std::vector<SDOperand> Ops; 807 bool Changed = false; 808 // Legalize the operands. 809 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 810 SDOperand Op = Node->getOperand(i); 811 Ops.push_back(LegalizeOp(Op)); 812 Changed |= Ops[i] != Op; 813 } 814 if (Changed) 815 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops); 816 } 817 break; 818 819 case ISD::CALLSEQ_START: 820 case ISD::CALLSEQ_END: 821 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 822 // Do not try to legalize the target-specific arguments (#1+) 823 Tmp2 = Node->getOperand(0); 824 if (Tmp1 != Tmp2) 825 Node->setAdjCallChain(Tmp1); 826 827 // Note that we do not create new CALLSEQ_DOWN/UP nodes here. These 828 // nodes are treated specially and are mutated in place. This makes the dag 829 // legalization process more efficient and also makes libcall insertion 830 // easier. 831 break; 832 case ISD::DYNAMIC_STACKALLOC: { 833 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 834 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the size. 835 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the alignment. 836 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 837 Tmp3 != Node->getOperand(2)) { 838 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end()); 839 std::vector<SDOperand> Ops; 840 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 841 Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops); 842 } else 843 Result = Op.getValue(0); 844 845 Tmp1 = Result; 846 Tmp2 = Result.getValue(1); 847 switch (TLI.getOperationAction(Node->getOpcode(), 848 Node->getValueType(0))) { 849 default: assert(0 && "This action is not supported yet!"); 850 case TargetLowering::Expand: { 851 unsigned SPReg = TLI.getStackPointerRegisterToSaveRestore(); 852 assert(SPReg && "Target cannot require DYNAMIC_STACKALLOC expansion and" 853 " not tell us which reg is the stack pointer!"); 854 SDOperand Chain = Tmp1.getOperand(0); 855 SDOperand Size = Tmp2.getOperand(1); 856 SDOperand SP = DAG.getCopyFromReg(Chain, SPReg, Node->getValueType(0)); 857 Tmp1 = DAG.getNode(ISD::SUB, Node->getValueType(0), SP, Size); // Value 858 Tmp2 = DAG.getCopyToReg(SP.getValue(1), SPReg, Tmp1); // Output chain 859 break; 860 } 861 case TargetLowering::Custom: 862 Tmp3 = TLI.LowerOperation(Tmp1, DAG); 863 if (Tmp3.Val) { 864 Tmp1 = LegalizeOp(Tmp3); 865 Tmp2 = LegalizeOp(Tmp3.getValue(1)); 866 } 867 break; 868 case TargetLowering::Legal: 869 break; 870 } 871 // Since this op produce two values, make sure to remember that we 872 // legalized both of them. 873 AddLegalizedOperand(SDOperand(Node, 0), Tmp1); 874 AddLegalizedOperand(SDOperand(Node, 1), Tmp2); 875 return Op.ResNo ? Tmp2 : Tmp1; 876 } 877 case ISD::TAILCALL: 878 case ISD::CALL: { 879 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 880 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 881 882 bool Changed = false; 883 std::vector<SDOperand> Ops; 884 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) { 885 Ops.push_back(LegalizeOp(Node->getOperand(i))); 886 Changed |= Ops.back() != Node->getOperand(i); 887 } 888 889 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) { 890 std::vector<MVT::ValueType> RetTyVTs; 891 RetTyVTs.reserve(Node->getNumValues()); 892 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 893 RetTyVTs.push_back(Node->getValueType(i)); 894 Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops, 895 Node->getOpcode() == ISD::TAILCALL), 0); 896 } else { 897 Result = Result.getValue(0); 898 } 899 // Since calls produce multiple values, make sure to remember that we 900 // legalized all of them. 901 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 902 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 903 return Result.getValue(Op.ResNo); 904 } 905 case ISD::BR: 906 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 907 if (Tmp1 != Node->getOperand(0)) 908 Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1)); 909 break; 910 911 case ISD::BRCOND: 912 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 913 914 switch (getTypeAction(Node->getOperand(1).getValueType())) { 915 case Expand: assert(0 && "It's impossible to expand bools"); 916 case Legal: 917 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 918 break; 919 case Promote: 920 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition. 921 break; 922 } 923 924 switch (TLI.getOperationAction(ISD::BRCOND, MVT::Other)) { 925 default: assert(0 && "This action is not supported yet!"); 926 case TargetLowering::Expand: 927 // Expand brcond's setcc into its constituent parts and create a BR_CC 928 // Node. 929 if (Tmp2.getOpcode() == ISD::SETCC) { 930 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Tmp2.getOperand(2), 931 Tmp2.getOperand(0), Tmp2.getOperand(1), 932 Node->getOperand(2)); 933 } else { 934 // Make sure the condition is either zero or one. It may have been 935 // promoted from something else. 936 Tmp2 = DAG.getZeroExtendInReg(Tmp2, MVT::i1); 937 938 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, 939 DAG.getCondCode(ISD::SETNE), Tmp2, 940 DAG.getConstant(0, Tmp2.getValueType()), 941 Node->getOperand(2)); 942 } 943 Result = LegalizeOp(Result); // Relegalize new nodes. 944 break; 945 case TargetLowering::Custom: { 946 SDOperand Tmp = 947 TLI.LowerOperation(DAG.getNode(ISD::BRCOND, Node->getValueType(0), 948 Tmp1, Tmp2, Node->getOperand(2)), DAG); 949 if (Tmp.Val) { 950 Result = LegalizeOp(Tmp); 951 break; 952 } 953 // FALLTHROUGH if the target thinks it is legal. 954 } 955 case TargetLowering::Legal: 956 // Basic block destination (Op#2) is always legal. 957 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 958 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 959 Node->getOperand(2)); 960 break; 961 } 962 break; 963 case ISD::BR_CC: 964 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 965 if (!isTypeLegal(Node->getOperand(2).getValueType())) { 966 Tmp2 = LegalizeOp(DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), 967 Node->getOperand(2), // LHS 968 Node->getOperand(3), // RHS 969 Node->getOperand(1))); 970 // If we get a SETCC back from legalizing the SETCC node we just 971 // created, then use its LHS, RHS, and CC directly in creating a new 972 // node. Otherwise, select between the true and false value based on 973 // comparing the result of the legalized with zero. 974 if (Tmp2.getOpcode() == ISD::SETCC) { 975 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Tmp2.getOperand(2), 976 Tmp2.getOperand(0), Tmp2.getOperand(1), 977 Node->getOperand(4)); 978 } else { 979 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, 980 DAG.getCondCode(ISD::SETNE), 981 Tmp2, DAG.getConstant(0, Tmp2.getValueType()), 982 Node->getOperand(4)); 983 } 984 break; 985 } 986 987 Tmp2 = LegalizeOp(Node->getOperand(2)); // LHS 988 Tmp3 = LegalizeOp(Node->getOperand(3)); // RHS 989 990 switch (TLI.getOperationAction(ISD::BR_CC, Tmp3.getValueType())) { 991 default: assert(0 && "Unexpected action for BR_CC!"); 992 case TargetLowering::Custom: { 993 Tmp4 = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Node->getOperand(1), 994 Tmp2, Tmp3, Node->getOperand(4)); 995 Tmp4 = TLI.LowerOperation(Tmp4, DAG); 996 if (Tmp4.Val) { 997 Result = LegalizeOp(Tmp4); 998 break; 999 } 1000 } // FALLTHROUGH if the target doesn't want to lower this op after all. 1001 case TargetLowering::Legal: 1002 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2) || 1003 Tmp3 != Node->getOperand(3)) { 1004 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Node->getOperand(1), 1005 Tmp2, Tmp3, Node->getOperand(4)); 1006 } 1007 break; 1008 } 1009 break; 1010 case ISD::BRCONDTWOWAY: 1011 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1012 switch (getTypeAction(Node->getOperand(1).getValueType())) { 1013 case Expand: assert(0 && "It's impossible to expand bools"); 1014 case Legal: 1015 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 1016 break; 1017 case Promote: 1018 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition. 1019 break; 1020 } 1021 // If this target does not support BRCONDTWOWAY, lower it to a BRCOND/BR 1022 // pair. 1023 switch (TLI.getOperationAction(ISD::BRCONDTWOWAY, MVT::Other)) { 1024 case TargetLowering::Promote: 1025 default: assert(0 && "This action is not supported yet!"); 1026 case TargetLowering::Legal: 1027 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 1028 std::vector<SDOperand> Ops; 1029 Ops.push_back(Tmp1); 1030 Ops.push_back(Tmp2); 1031 Ops.push_back(Node->getOperand(2)); 1032 Ops.push_back(Node->getOperand(3)); 1033 Result = DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops); 1034 } 1035 break; 1036 case TargetLowering::Expand: 1037 // If BRTWOWAY_CC is legal for this target, then simply expand this node 1038 // to that. Otherwise, skip BRTWOWAY_CC and expand directly to a 1039 // BRCOND/BR pair. 1040 if (TLI.isOperationLegal(ISD::BRTWOWAY_CC, MVT::Other)) { 1041 if (Tmp2.getOpcode() == ISD::SETCC) { 1042 Result = DAG.getBR2Way_CC(Tmp1, Tmp2.getOperand(2), 1043 Tmp2.getOperand(0), Tmp2.getOperand(1), 1044 Node->getOperand(2), Node->getOperand(3)); 1045 } else { 1046 Result = DAG.getBR2Way_CC(Tmp1, DAG.getCondCode(ISD::SETNE), Tmp2, 1047 DAG.getConstant(0, Tmp2.getValueType()), 1048 Node->getOperand(2), Node->getOperand(3)); 1049 } 1050 } else { 1051 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 1052 Node->getOperand(2)); 1053 Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(3)); 1054 } 1055 Result = LegalizeOp(Result); // Relegalize new nodes. 1056 break; 1057 } 1058 break; 1059 case ISD::BRTWOWAY_CC: 1060 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1061 if (isTypeLegal(Node->getOperand(2).getValueType())) { 1062 Tmp2 = LegalizeOp(Node->getOperand(2)); // LHS 1063 Tmp3 = LegalizeOp(Node->getOperand(3)); // RHS 1064 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2) || 1065 Tmp3 != Node->getOperand(3)) { 1066 Result = DAG.getBR2Way_CC(Tmp1, Node->getOperand(1), Tmp2, Tmp3, 1067 Node->getOperand(4), Node->getOperand(5)); 1068 } 1069 break; 1070 } else { 1071 Tmp2 = LegalizeOp(DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), 1072 Node->getOperand(2), // LHS 1073 Node->getOperand(3), // RHS 1074 Node->getOperand(1))); 1075 // If this target does not support BRTWOWAY_CC, lower it to a BRCOND/BR 1076 // pair. 1077 switch (TLI.getOperationAction(ISD::BRTWOWAY_CC, MVT::Other)) { 1078 default: assert(0 && "This action is not supported yet!"); 1079 case TargetLowering::Legal: 1080 // If we get a SETCC back from legalizing the SETCC node we just 1081 // created, then use its LHS, RHS, and CC directly in creating a new 1082 // node. Otherwise, select between the true and false value based on 1083 // comparing the result of the legalized with zero. 1084 if (Tmp2.getOpcode() == ISD::SETCC) { 1085 Result = DAG.getBR2Way_CC(Tmp1, Tmp2.getOperand(2), 1086 Tmp2.getOperand(0), Tmp2.getOperand(1), 1087 Node->getOperand(4), Node->getOperand(5)); 1088 } else { 1089 Result = DAG.getBR2Way_CC(Tmp1, DAG.getCondCode(ISD::SETNE), Tmp2, 1090 DAG.getConstant(0, Tmp2.getValueType()), 1091 Node->getOperand(4), Node->getOperand(5)); 1092 } 1093 break; 1094 case TargetLowering::Expand: 1095 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 1096 Node->getOperand(4)); 1097 Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(5)); 1098 break; 1099 } 1100 Result = LegalizeOp(Result); // Relegalize new nodes. 1101 } 1102 break; 1103 case ISD::LOAD: { 1104 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1105 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 1106 1107 MVT::ValueType VT = Node->getValueType(0); 1108 switch (TLI.getOperationAction(Node->getOpcode(), VT)) { 1109 default: assert(0 && "This action is not supported yet!"); 1110 case TargetLowering::Custom: { 1111 SDOperand Op = DAG.getLoad(Node->getValueType(0), 1112 Tmp1, Tmp2, Node->getOperand(2)); 1113 SDOperand Tmp = TLI.LowerOperation(Op, DAG); 1114 if (Tmp.Val) { 1115 Result = LegalizeOp(Tmp); 1116 // Since loads produce two values, make sure to remember that we legalized 1117 // both of them. 1118 AddLegalizedOperand(SDOperand(Node, 0), Result); 1119 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1120 return Result.getValue(Op.ResNo); 1121 } 1122 // FALLTHROUGH if the target thinks it is legal. 1123 } 1124 case TargetLowering::Legal: 1125 if (Tmp1 != Node->getOperand(0) || 1126 Tmp2 != Node->getOperand(1)) 1127 Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2, 1128 Node->getOperand(2)); 1129 else 1130 Result = SDOperand(Node, 0); 1131 1132 // Since loads produce two values, make sure to remember that we legalized 1133 // both of them. 1134 AddLegalizedOperand(SDOperand(Node, 0), Result); 1135 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1136 return Result.getValue(Op.ResNo); 1137 } 1138 assert(0 && "Unreachable"); 1139 } 1140 case ISD::EXTLOAD: 1141 case ISD::SEXTLOAD: 1142 case ISD::ZEXTLOAD: { 1143 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1144 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 1145 1146 MVT::ValueType SrcVT = cast<VTSDNode>(Node->getOperand(3))->getVT(); 1147 switch (TLI.getOperationAction(Node->getOpcode(), SrcVT)) { 1148 default: assert(0 && "This action is not supported yet!"); 1149 case TargetLowering::Promote: 1150 assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!"); 1151 Result = DAG.getExtLoad(Node->getOpcode(), Node->getValueType(0), 1152 Tmp1, Tmp2, Node->getOperand(2), MVT::i8); 1153 // Since loads produce two values, make sure to remember that we legalized 1154 // both of them. 1155 AddLegalizedOperand(SDOperand(Node, 0), Result); 1156 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1157 return Result.getValue(Op.ResNo); 1158 1159 case TargetLowering::Custom: { 1160 SDOperand Op = DAG.getExtLoad(Node->getOpcode(), Node->getValueType(0), 1161 Tmp1, Tmp2, Node->getOperand(2), 1162 SrcVT); 1163 SDOperand Tmp = TLI.LowerOperation(Op, DAG); 1164 if (Tmp.Val) { 1165 Result = LegalizeOp(Tmp); 1166 // Since loads produce two values, make sure to remember that we legalized 1167 // both of them. 1168 AddLegalizedOperand(SDOperand(Node, 0), Result); 1169 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1170 return Result.getValue(Op.ResNo); 1171 } 1172 // FALLTHROUGH if the target thinks it is legal. 1173 } 1174 case TargetLowering::Legal: 1175 if (Tmp1 != Node->getOperand(0) || 1176 Tmp2 != Node->getOperand(1)) 1177 Result = DAG.getExtLoad(Node->getOpcode(), Node->getValueType(0), 1178 Tmp1, Tmp2, Node->getOperand(2), SrcVT); 1179 else 1180 Result = SDOperand(Node, 0); 1181 1182 // Since loads produce two values, make sure to remember that we legalized 1183 // both of them. 1184 AddLegalizedOperand(SDOperand(Node, 0), Result); 1185 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1186 return Result.getValue(Op.ResNo); 1187 case TargetLowering::Expand: 1188 // f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND 1189 if (SrcVT == MVT::f32 && Node->getValueType(0) == MVT::f64) { 1190 SDOperand Load = DAG.getLoad(SrcVT, Tmp1, Tmp2, Node->getOperand(2)); 1191 Result = DAG.getNode(ISD::FP_EXTEND, Node->getValueType(0), Load); 1192 Result = LegalizeOp(Result); // Relegalize new nodes. 1193 Load = LegalizeOp(Load); 1194 AddLegalizedOperand(SDOperand(Node, 0), Result); 1195 AddLegalizedOperand(SDOperand(Node, 1), Load.getValue(1)); 1196 if (Op.ResNo) 1197 return Load.getValue(1); 1198 return Result; 1199 } 1200 assert(Node->getOpcode() != ISD::EXTLOAD && 1201 "EXTLOAD should always be supported!"); 1202 // Turn the unsupported load into an EXTLOAD followed by an explicit 1203 // zero/sign extend inreg. 1204 Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0), 1205 Tmp1, Tmp2, Node->getOperand(2), SrcVT); 1206 SDOperand ValRes; 1207 if (Node->getOpcode() == ISD::SEXTLOAD) 1208 ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 1209 Result, DAG.getValueType(SrcVT)); 1210 else 1211 ValRes = DAG.getZeroExtendInReg(Result, SrcVT); 1212 Result = LegalizeOp(Result); // Relegalize new nodes. 1213 ValRes = LegalizeOp(ValRes); // Relegalize new nodes. 1214 AddLegalizedOperand(SDOperand(Node, 0), ValRes); 1215 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1216 if (Op.ResNo) 1217 return Result.getValue(1); 1218 return ValRes; 1219 } 1220 assert(0 && "Unreachable"); 1221 } 1222 case ISD::EXTRACT_ELEMENT: { 1223 MVT::ValueType OpTy = Node->getOperand(0).getValueType(); 1224 switch (getTypeAction(OpTy)) { 1225 default: 1226 assert(0 && "EXTRACT_ELEMENT action for type unimplemented!"); 1227 break; 1228 case Legal: 1229 if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) { 1230 // 1 -> Hi 1231 Result = DAG.getNode(ISD::SRL, OpTy, Node->getOperand(0), 1232 DAG.getConstant(MVT::getSizeInBits(OpTy)/2, 1233 TLI.getShiftAmountTy())); 1234 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Result); 1235 } else { 1236 // 0 -> Lo 1237 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), 1238 Node->getOperand(0)); 1239 } 1240 Result = LegalizeOp(Result); 1241 break; 1242 case Expand: 1243 // Get both the low and high parts. 1244 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 1245 if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) 1246 Result = Tmp2; // 1 -> Hi 1247 else 1248 Result = Tmp1; // 0 -> Lo 1249 break; 1250 } 1251 break; 1252 } 1253 1254 case ISD::CopyToReg: 1255 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1256 1257 assert(isTypeLegal(Node->getOperand(2).getValueType()) && 1258 "Register type must be legal!"); 1259 // Legalize the incoming value (must be a legal type). 1260 Tmp2 = LegalizeOp(Node->getOperand(2)); 1261 if (Node->getNumValues() == 1) { 1262 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2)) 1263 Result = DAG.getNode(ISD::CopyToReg, MVT::Other, Tmp1, 1264 Node->getOperand(1), Tmp2); 1265 } else { 1266 assert(Node->getNumValues() == 2 && "Unknown CopyToReg"); 1267 if (Node->getNumOperands() == 4) 1268 Tmp3 = LegalizeOp(Node->getOperand(3)); 1269 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2) || 1270 (Node->getNumOperands() == 4 && Tmp3 != Node->getOperand(3))) { 1271 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg(); 1272 Result = DAG.getCopyToReg(Tmp1, Reg, Tmp2, Tmp3); 1273 } 1274 1275 // Since this produces two values, make sure to remember that we legalized 1276 // both of them. 1277 AddLegalizedOperand(SDOperand(Node, 0), Result); 1278 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1279 return Result.getValue(Op.ResNo); 1280 } 1281 break; 1282 1283 case ISD::RET: 1284 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1285 switch (Node->getNumOperands()) { 1286 case 2: // ret val 1287 switch (getTypeAction(Node->getOperand(1).getValueType())) { 1288 case Legal: 1289 Tmp2 = LegalizeOp(Node->getOperand(1)); 1290 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 1291 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 1292 break; 1293 case Expand: { 1294 SDOperand Lo, Hi; 1295 ExpandOp(Node->getOperand(1), Lo, Hi); 1296 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi); 1297 break; 1298 } 1299 case Promote: 1300 Tmp2 = PromoteOp(Node->getOperand(1)); 1301 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 1302 break; 1303 } 1304 break; 1305 case 1: // ret void 1306 if (Tmp1 != Node->getOperand(0)) 1307 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1); 1308 break; 1309 default: { // ret <values> 1310 std::vector<SDOperand> NewValues; 1311 NewValues.push_back(Tmp1); 1312 for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) 1313 switch (getTypeAction(Node->getOperand(i).getValueType())) { 1314 case Legal: 1315 NewValues.push_back(LegalizeOp(Node->getOperand(i))); 1316 break; 1317 case Expand: { 1318 SDOperand Lo, Hi; 1319 ExpandOp(Node->getOperand(i), Lo, Hi); 1320 NewValues.push_back(Lo); 1321 NewValues.push_back(Hi); 1322 break; 1323 } 1324 case Promote: 1325 assert(0 && "Can't promote multiple return value yet!"); 1326 } 1327 Result = DAG.getNode(ISD::RET, MVT::Other, NewValues); 1328 break; 1329 } 1330 } 1331 1332 switch (TLI.getOperationAction(Node->getOpcode(), 1333 Node->getValueType(0))) { 1334 default: assert(0 && "This action is not supported yet!"); 1335 case TargetLowering::Custom: { 1336 SDOperand Tmp = TLI.LowerOperation(Result, DAG); 1337 if (Tmp.Val) { 1338 Result = LegalizeOp(Tmp); 1339 break; 1340 } 1341 // FALLTHROUGH if the target thinks it is legal. 1342 } 1343 case TargetLowering::Legal: 1344 // Nothing to do. 1345 break; 1346 } 1347 break; 1348 case ISD::STORE: { 1349 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1350 Tmp2 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 1351 1352 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 1353 if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){ 1354 if (CFP->getValueType(0) == MVT::f32) { 1355 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 1356 DAG.getConstant(FloatToBits(CFP->getValue()), 1357 MVT::i32), 1358 Tmp2, 1359 Node->getOperand(3)); 1360 } else { 1361 assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!"); 1362 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 1363 DAG.getConstant(DoubleToBits(CFP->getValue()), 1364 MVT::i64), 1365 Tmp2, 1366 Node->getOperand(3)); 1367 } 1368 Node = Result.Val; 1369 } 1370 1371 switch (getTypeAction(Node->getOperand(1).getValueType())) { 1372 case Legal: { 1373 SDOperand Val = LegalizeOp(Node->getOperand(1)); 1374 if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) || 1375 Tmp2 != Node->getOperand(2)) 1376 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2, 1377 Node->getOperand(3)); 1378 1379 MVT::ValueType VT = Result.Val->getOperand(1).getValueType(); 1380 switch (TLI.getOperationAction(Result.Val->getOpcode(), VT)) { 1381 default: assert(0 && "This action is not supported yet!"); 1382 case TargetLowering::Custom: { 1383 SDOperand Tmp = TLI.LowerOperation(Result, DAG); 1384 if (Tmp.Val) { 1385 Result = LegalizeOp(Tmp); 1386 break; 1387 } 1388 // FALLTHROUGH if the target thinks it is legal. 1389 } 1390 case TargetLowering::Legal: 1391 // Nothing to do. 1392 break; 1393 } 1394 break; 1395 } 1396 case Promote: 1397 // Truncate the value and store the result. 1398 Tmp3 = PromoteOp(Node->getOperand(1)); 1399 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2, 1400 Node->getOperand(3), 1401 DAG.getValueType(Node->getOperand(1).getValueType())); 1402 break; 1403 1404 case Expand: 1405 SDOperand Lo, Hi; 1406 unsigned IncrementSize; 1407 ExpandOp(Node->getOperand(1), Lo, Hi); 1408 1409 if (!TLI.isLittleEndian()) 1410 std::swap(Lo, Hi); 1411 1412 Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2, 1413 Node->getOperand(3)); 1414 // If this is a vector type, then we have to calculate the increment as 1415 // the product of the element size in bytes, and the number of elements 1416 // in the high half of the vector. 1417 if (MVT::Vector == Hi.getValueType()) { 1418 unsigned NumElems = cast<ConstantSDNode>(Hi.getOperand(2))->getValue(); 1419 MVT::ValueType EVT = cast<VTSDNode>(Hi.getOperand(3))->getVT(); 1420 IncrementSize = NumElems * MVT::getSizeInBits(EVT)/8; 1421 } else { 1422 IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8; 1423 } 1424 Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2, 1425 getIntPtrConstant(IncrementSize)); 1426 assert(isTypeLegal(Tmp2.getValueType()) && 1427 "Pointers must be legal!"); 1428 //Again, claiming both parts of the store came form the same Instr 1429 Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2, 1430 Node->getOperand(3)); 1431 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); 1432 break; 1433 } 1434 break; 1435 } 1436 case ISD::PCMARKER: 1437 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1438 if (Tmp1 != Node->getOperand(0)) 1439 Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1,Node->getOperand(1)); 1440 break; 1441 case ISD::STACKSAVE: 1442 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1443 if (Tmp1 != Node->getOperand(0)) { 1444 std::vector<MVT::ValueType> VTs; 1445 VTs.push_back(Node->getValueType(0)); 1446 VTs.push_back(MVT::Other); 1447 std::vector<SDOperand> Ops; 1448 Ops.push_back(Tmp1); 1449 Result = DAG.getNode(ISD::STACKSAVE, VTs, Ops); 1450 } 1451 1452 switch (TLI.getOperationAction(ISD::STACKSAVE, MVT::Other)) { 1453 default: assert(0 && "This action is not supported yet!"); 1454 case TargetLowering::Custom: { 1455 SDOperand Tmp = TLI.LowerOperation(Result, DAG); 1456 if (Tmp.Val) { 1457 Result = LegalizeOp(Tmp); 1458 break; 1459 } 1460 // FALLTHROUGH if the target thinks it is legal. 1461 } 1462 case TargetLowering::Legal: 1463 // Since stacksave produce two values, make sure to remember that we 1464 // legalized both of them. 1465 AddLegalizedOperand(SDOperand(Node, 0), Result); 1466 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1467 return Result.getValue(Op.ResNo); 1468 case TargetLowering::Expand: 1469 // Expand to CopyFromReg if the target set 1470 // StackPointerRegisterToSaveRestore. 1471 if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) { 1472 Tmp1 = DAG.getCopyFromReg(Node->getOperand(0), SP, 1473 Node->getValueType(0)); 1474 AddLegalizedOperand(SDOperand(Node, 0), Tmp1); 1475 AddLegalizedOperand(SDOperand(Node, 1), Tmp1.getValue(1)); 1476 return Tmp1.getValue(Op.ResNo); 1477 } else { 1478 Tmp1 = DAG.getNode(ISD::UNDEF, Node->getValueType(0)); 1479 AddLegalizedOperand(SDOperand(Node, 0), Tmp1); 1480 AddLegalizedOperand(SDOperand(Node, 1), Node->getOperand(0)); 1481 return Op.ResNo ? Node->getOperand(0) : Tmp1; 1482 } 1483 } 1484 1485 case ISD::STACKRESTORE: 1486 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1487 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 1488 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 1489 Result = DAG.getNode(ISD::STACKRESTORE, MVT::Other, Tmp1, Tmp2); 1490 1491 switch (TLI.getOperationAction(ISD::STACKRESTORE, MVT::Other)) { 1492 default: assert(0 && "This action is not supported yet!"); 1493 case TargetLowering::Custom: { 1494 SDOperand Tmp = TLI.LowerOperation(Result, DAG); 1495 if (Tmp.Val) { 1496 Result = LegalizeOp(Tmp); 1497 break; 1498 } 1499 // FALLTHROUGH if the target thinks it is legal. 1500 } 1501 case TargetLowering::Legal: 1502 break; 1503 case TargetLowering::Expand: 1504 // Expand to CopyToReg if the target set 1505 // StackPointerRegisterToSaveRestore. 1506 if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) { 1507 Result = DAG.getCopyToReg(Tmp1, SP, Tmp2); 1508 } else { 1509 Result = Tmp1; 1510 } 1511 break; 1512 } 1513 break; 1514 1515 case ISD::READCYCLECOUNTER: 1516 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain 1517 if (Tmp1 != Node->getOperand(0)) { 1518 std::vector<MVT::ValueType> rtypes; 1519 std::vector<SDOperand> rvals; 1520 rtypes.push_back(MVT::i64); 1521 rtypes.push_back(MVT::Other); 1522 rvals.push_back(Tmp1); 1523 Result = DAG.getNode(ISD::READCYCLECOUNTER, rtypes, rvals); 1524 } 1525 1526 // Since rdcc produce two values, make sure to remember that we legalized 1527 // both of them. 1528 AddLegalizedOperand(SDOperand(Node, 0), Result); 1529 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1530 return Result.getValue(Op.ResNo); 1531 1532 case ISD::TRUNCSTORE: { 1533 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1534 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 1535 1536 switch (getTypeAction(Node->getOperand(1).getValueType())) { 1537 case Promote: 1538 case Expand: 1539 assert(0 && "Cannot handle illegal TRUNCSTORE yet!"); 1540 case Legal: 1541 Tmp2 = LegalizeOp(Node->getOperand(1)); 1542 1543 // The only promote case we handle is TRUNCSTORE:i1 X into 1544 // -> TRUNCSTORE:i8 (and X, 1) 1545 if (cast<VTSDNode>(Node->getOperand(4))->getVT() == MVT::i1 && 1546 TLI.getOperationAction(ISD::TRUNCSTORE, MVT::i1) == 1547 TargetLowering::Promote) { 1548 // Promote the bool to a mask then store. 1549 Tmp2 = DAG.getNode(ISD::AND, Tmp2.getValueType(), Tmp2, 1550 DAG.getConstant(1, Tmp2.getValueType())); 1551 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3, 1552 Node->getOperand(3), DAG.getValueType(MVT::i8)); 1553 1554 } else if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1555 Tmp3 != Node->getOperand(2)) { 1556 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3, 1557 Node->getOperand(3), Node->getOperand(4)); 1558 } 1559 1560 MVT::ValueType StVT = cast<VTSDNode>(Result.Val->getOperand(4))->getVT(); 1561 switch (TLI.getOperationAction(Result.Val->getOpcode(), StVT)) { 1562 default: assert(0 && "This action is not supported yet!"); 1563 case TargetLowering::Custom: { 1564 SDOperand Tmp = TLI.LowerOperation(Result, DAG); 1565 if (Tmp.Val) { 1566 Result = LegalizeOp(Tmp); 1567 break; 1568 } 1569 // FALLTHROUGH if the target thinks it is legal. 1570 } 1571 case TargetLowering::Legal: 1572 // Nothing to do. 1573 break; 1574 } 1575 break; 1576 } 1577 break; 1578 } 1579 case ISD::SELECT: 1580 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1581 case Expand: assert(0 && "It's impossible to expand bools"); 1582 case Legal: 1583 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 1584 break; 1585 case Promote: 1586 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 1587 break; 1588 } 1589 Tmp2 = LegalizeOp(Node->getOperand(1)); // TrueVal 1590 Tmp3 = LegalizeOp(Node->getOperand(2)); // FalseVal 1591 1592 switch (TLI.getOperationAction(ISD::SELECT, Tmp2.getValueType())) { 1593 default: assert(0 && "This action is not supported yet!"); 1594 case TargetLowering::Expand: 1595 if (Tmp1.getOpcode() == ISD::SETCC) { 1596 Result = DAG.getSelectCC(Tmp1.getOperand(0), Tmp1.getOperand(1), 1597 Tmp2, Tmp3, 1598 cast<CondCodeSDNode>(Tmp1.getOperand(2))->get()); 1599 } else { 1600 // Make sure the condition is either zero or one. It may have been 1601 // promoted from something else. 1602 Tmp1 = DAG.getZeroExtendInReg(Tmp1, MVT::i1); 1603 Result = DAG.getSelectCC(Tmp1, 1604 DAG.getConstant(0, Tmp1.getValueType()), 1605 Tmp2, Tmp3, ISD::SETNE); 1606 } 1607 Result = LegalizeOp(Result); // Relegalize new nodes. 1608 break; 1609 case TargetLowering::Custom: { 1610 SDOperand Tmp = 1611 TLI.LowerOperation(DAG.getNode(ISD::SELECT, Node->getValueType(0), 1612 Tmp1, Tmp2, Tmp3), DAG); 1613 if (Tmp.Val) { 1614 Result = LegalizeOp(Tmp); 1615 break; 1616 } 1617 // FALLTHROUGH if the target thinks it is legal. 1618 } 1619 case TargetLowering::Legal: 1620 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1621 Tmp3 != Node->getOperand(2)) 1622 Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), 1623 Tmp1, Tmp2, Tmp3); 1624 break; 1625 case TargetLowering::Promote: { 1626 MVT::ValueType NVT = 1627 TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType()); 1628 unsigned ExtOp, TruncOp; 1629 if (MVT::isInteger(Tmp2.getValueType())) { 1630 ExtOp = ISD::ANY_EXTEND; 1631 TruncOp = ISD::TRUNCATE; 1632 } else { 1633 ExtOp = ISD::FP_EXTEND; 1634 TruncOp = ISD::FP_ROUND; 1635 } 1636 // Promote each of the values to the new type. 1637 Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2); 1638 Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3); 1639 // Perform the larger operation, then round down. 1640 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3); 1641 Result = DAG.getNode(TruncOp, Node->getValueType(0), Result); 1642 break; 1643 } 1644 } 1645 break; 1646 case ISD::SELECT_CC: 1647 Tmp3 = LegalizeOp(Node->getOperand(2)); // True 1648 Tmp4 = LegalizeOp(Node->getOperand(3)); // False 1649 1650 if (isTypeLegal(Node->getOperand(0).getValueType())) { 1651 // Everything is legal, see if we should expand this op or something. 1652 switch (TLI.getOperationAction(ISD::SELECT_CC, 1653 Node->getOperand(0).getValueType())) { 1654 default: assert(0 && "This action is not supported yet!"); 1655 case TargetLowering::Custom: { 1656 SDOperand Tmp = 1657 TLI.LowerOperation(DAG.getNode(ISD::SELECT_CC, Node->getValueType(0), 1658 Node->getOperand(0), 1659 Node->getOperand(1), Tmp3, Tmp4, 1660 Node->getOperand(4)), DAG); 1661 if (Tmp.Val) { 1662 Result = LegalizeOp(Tmp); 1663 break; 1664 } 1665 } // FALLTHROUGH if the target can't lower this operation after all. 1666 case TargetLowering::Legal: 1667 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 1668 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 1669 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1670 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3)) { 1671 Result = DAG.getNode(ISD::SELECT_CC, Node->getValueType(0), Tmp1,Tmp2, 1672 Tmp3, Tmp4, Node->getOperand(4)); 1673 } 1674 break; 1675 } 1676 break; 1677 } else { 1678 Tmp1 = LegalizeOp(DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), 1679 Node->getOperand(0), // LHS 1680 Node->getOperand(1), // RHS 1681 Node->getOperand(4))); 1682 // If we get a SETCC back from legalizing the SETCC node we just 1683 // created, then use its LHS, RHS, and CC directly in creating a new 1684 // node. Otherwise, select between the true and false value based on 1685 // comparing the result of the legalized with zero. 1686 if (Tmp1.getOpcode() == ISD::SETCC) { 1687 Result = DAG.getNode(ISD::SELECT_CC, Tmp3.getValueType(), 1688 Tmp1.getOperand(0), Tmp1.getOperand(1), 1689 Tmp3, Tmp4, Tmp1.getOperand(2)); 1690 } else { 1691 Result = DAG.getSelectCC(Tmp1, 1692 DAG.getConstant(0, Tmp1.getValueType()), 1693 Tmp3, Tmp4, ISD::SETNE); 1694 } 1695 } 1696 break; 1697 case ISD::SETCC: 1698 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1699 case Legal: 1700 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 1701 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 1702 break; 1703 case Promote: 1704 Tmp1 = PromoteOp(Node->getOperand(0)); // LHS 1705 Tmp2 = PromoteOp(Node->getOperand(1)); // RHS 1706 1707 // If this is an FP compare, the operands have already been extended. 1708 if (MVT::isInteger(Node->getOperand(0).getValueType())) { 1709 MVT::ValueType VT = Node->getOperand(0).getValueType(); 1710 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 1711 1712 // Otherwise, we have to insert explicit sign or zero extends. Note 1713 // that we could insert sign extends for ALL conditions, but zero extend 1714 // is cheaper on many machines (an AND instead of two shifts), so prefer 1715 // it. 1716 switch (cast<CondCodeSDNode>(Node->getOperand(2))->get()) { 1717 default: assert(0 && "Unknown integer comparison!"); 1718 case ISD::SETEQ: 1719 case ISD::SETNE: 1720 case ISD::SETUGE: 1721 case ISD::SETUGT: 1722 case ISD::SETULE: 1723 case ISD::SETULT: 1724 // ALL of these operations will work if we either sign or zero extend 1725 // the operands (including the unsigned comparisons!). Zero extend is 1726 // usually a simpler/cheaper operation, so prefer it. 1727 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT); 1728 Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT); 1729 break; 1730 case ISD::SETGE: 1731 case ISD::SETGT: 1732 case ISD::SETLT: 1733 case ISD::SETLE: 1734 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, 1735 DAG.getValueType(VT)); 1736 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, 1737 DAG.getValueType(VT)); 1738 break; 1739 } 1740 } 1741 break; 1742 case Expand: 1743 SDOperand LHSLo, LHSHi, RHSLo, RHSHi; 1744 ExpandOp(Node->getOperand(0), LHSLo, LHSHi); 1745 ExpandOp(Node->getOperand(1), RHSLo, RHSHi); 1746 switch (cast<CondCodeSDNode>(Node->getOperand(2))->get()) { 1747 case ISD::SETEQ: 1748 case ISD::SETNE: 1749 if (RHSLo == RHSHi) 1750 if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo)) 1751 if (RHSCST->isAllOnesValue()) { 1752 // Comparison to -1. 1753 Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi); 1754 Tmp2 = RHSLo; 1755 break; 1756 } 1757 1758 Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo); 1759 Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi); 1760 Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2); 1761 Tmp2 = DAG.getConstant(0, Tmp1.getValueType()); 1762 break; 1763 default: 1764 // If this is a comparison of the sign bit, just look at the top part. 1765 // X > -1, x < 0 1766 if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(Node->getOperand(1))) 1767 if ((cast<CondCodeSDNode>(Node->getOperand(2))->get() == ISD::SETLT && 1768 CST->getValue() == 0) || // X < 0 1769 (cast<CondCodeSDNode>(Node->getOperand(2))->get() == ISD::SETGT && 1770 (CST->isAllOnesValue()))) { // X > -1 1771 Tmp1 = LHSHi; 1772 Tmp2 = RHSHi; 1773 break; 1774 } 1775 1776 // FIXME: This generated code sucks. 1777 ISD::CondCode LowCC; 1778 switch (cast<CondCodeSDNode>(Node->getOperand(2))->get()) { 1779 default: assert(0 && "Unknown integer setcc!"); 1780 case ISD::SETLT: 1781 case ISD::SETULT: LowCC = ISD::SETULT; break; 1782 case ISD::SETGT: 1783 case ISD::SETUGT: LowCC = ISD::SETUGT; break; 1784 case ISD::SETLE: 1785 case ISD::SETULE: LowCC = ISD::SETULE; break; 1786 case ISD::SETGE: 1787 case ISD::SETUGE: LowCC = ISD::SETUGE; break; 1788 } 1789 1790 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison 1791 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands 1792 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2; 1793 1794 // NOTE: on targets without efficient SELECT of bools, we can always use 1795 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3) 1796 Tmp1 = DAG.getSetCC(Node->getValueType(0), LHSLo, RHSLo, LowCC); 1797 Tmp2 = DAG.getNode(ISD::SETCC, Node->getValueType(0), LHSHi, RHSHi, 1798 Node->getOperand(2)); 1799 Result = DAG.getSetCC(Node->getValueType(0), LHSHi, RHSHi, ISD::SETEQ); 1800 Result = LegalizeOp(DAG.getNode(ISD::SELECT, Tmp1.getValueType(), 1801 Result, Tmp1, Tmp2)); 1802 AddLegalizedOperand(SDOperand(Node, 0), Result); 1803 return Result; 1804 } 1805 } 1806 1807 switch(TLI.getOperationAction(ISD::SETCC, 1808 Node->getOperand(0).getValueType())) { 1809 default: 1810 assert(0 && "Cannot handle this action for SETCC yet!"); 1811 break; 1812 case TargetLowering::Promote: { 1813 // First step, figure out the appropriate operation to use. 1814 // Allow SETCC to not be supported for all legal data types 1815 // Mostly this targets FP 1816 MVT::ValueType NewInTy = Node->getOperand(0).getValueType(); 1817 MVT::ValueType OldVT = NewInTy; 1818 1819 // Scan for the appropriate larger type to use. 1820 while (1) { 1821 NewInTy = (MVT::ValueType)(NewInTy+1); 1822 1823 assert(MVT::isInteger(NewInTy) == MVT::isInteger(OldVT) && 1824 "Fell off of the edge of the integer world"); 1825 assert(MVT::isFloatingPoint(NewInTy) == MVT::isFloatingPoint(OldVT) && 1826 "Fell off of the edge of the floating point world"); 1827 1828 // If the target supports SETCC of this type, use it. 1829 if (TLI.isOperationLegal(ISD::SETCC, NewInTy)) 1830 break; 1831 } 1832 if (MVT::isInteger(NewInTy)) 1833 assert(0 && "Cannot promote Legal Integer SETCC yet"); 1834 else { 1835 Tmp1 = DAG.getNode(ISD::FP_EXTEND, NewInTy, Tmp1); 1836 Tmp2 = DAG.getNode(ISD::FP_EXTEND, NewInTy, Tmp2); 1837 } 1838 1839 Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1, Tmp2, 1840 Node->getOperand(2)); 1841 break; 1842 } 1843 case TargetLowering::Custom: { 1844 SDOperand Tmp = 1845 TLI.LowerOperation(DAG.getNode(ISD::SETCC, Node->getValueType(0), 1846 Tmp1, Tmp2, Node->getOperand(2)), DAG); 1847 if (Tmp.Val) { 1848 Result = LegalizeOp(Tmp); 1849 break; 1850 } 1851 // FALLTHROUGH if the target thinks it is legal. 1852 } 1853 case TargetLowering::Legal: 1854 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 1855 Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1, Tmp2, 1856 Node->getOperand(2)); 1857 break; 1858 case TargetLowering::Expand: 1859 // Expand a setcc node into a select_cc of the same condition, lhs, and 1860 // rhs that selects between const 1 (true) and const 0 (false). 1861 MVT::ValueType VT = Node->getValueType(0); 1862 Result = DAG.getNode(ISD::SELECT_CC, VT, Tmp1, Tmp2, 1863 DAG.getConstant(1, VT), DAG.getConstant(0, VT), 1864 Node->getOperand(2)); 1865 Result = LegalizeOp(Result); 1866 break; 1867 } 1868 break; 1869 1870 case ISD::MEMSET: 1871 case ISD::MEMCPY: 1872 case ISD::MEMMOVE: { 1873 Tmp1 = LegalizeOp(Node->getOperand(0)); // Chain 1874 Tmp2 = LegalizeOp(Node->getOperand(1)); // Pointer 1875 1876 if (Node->getOpcode() == ISD::MEMSET) { // memset = ubyte 1877 switch (getTypeAction(Node->getOperand(2).getValueType())) { 1878 case Expand: assert(0 && "Cannot expand a byte!"); 1879 case Legal: 1880 Tmp3 = LegalizeOp(Node->getOperand(2)); 1881 break; 1882 case Promote: 1883 Tmp3 = PromoteOp(Node->getOperand(2)); 1884 break; 1885 } 1886 } else { 1887 Tmp3 = LegalizeOp(Node->getOperand(2)); // memcpy/move = pointer, 1888 } 1889 1890 SDOperand Tmp4; 1891 switch (getTypeAction(Node->getOperand(3).getValueType())) { 1892 case Expand: { 1893 // Length is too big, just take the lo-part of the length. 1894 SDOperand HiPart; 1895 ExpandOp(Node->getOperand(3), HiPart, Tmp4); 1896 break; 1897 } 1898 case Legal: 1899 Tmp4 = LegalizeOp(Node->getOperand(3)); 1900 break; 1901 case Promote: 1902 Tmp4 = PromoteOp(Node->getOperand(3)); 1903 break; 1904 } 1905 1906 SDOperand Tmp5; 1907 switch (getTypeAction(Node->getOperand(4).getValueType())) { // uint 1908 case Expand: assert(0 && "Cannot expand this yet!"); 1909 case Legal: 1910 Tmp5 = LegalizeOp(Node->getOperand(4)); 1911 break; 1912 case Promote: 1913 Tmp5 = PromoteOp(Node->getOperand(4)); 1914 break; 1915 } 1916 1917 switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) { 1918 default: assert(0 && "This action not implemented for this operation!"); 1919 case TargetLowering::Custom: { 1920 SDOperand Tmp = 1921 TLI.LowerOperation(DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, 1922 Tmp2, Tmp3, Tmp4, Tmp5), DAG); 1923 if (Tmp.Val) { 1924 Result = LegalizeOp(Tmp); 1925 break; 1926 } 1927 // FALLTHROUGH if the target thinks it is legal. 1928 } 1929 case TargetLowering::Legal: 1930 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1931 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) || 1932 Tmp5 != Node->getOperand(4)) { 1933 std::vector<SDOperand> Ops; 1934 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 1935 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 1936 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 1937 } 1938 break; 1939 case TargetLowering::Expand: { 1940 // Otherwise, the target does not support this operation. Lower the 1941 // operation to an explicit libcall as appropriate. 1942 MVT::ValueType IntPtr = TLI.getPointerTy(); 1943 const Type *IntPtrTy = TLI.getTargetData().getIntPtrType(); 1944 std::vector<std::pair<SDOperand, const Type*> > Args; 1945 1946 const char *FnName = 0; 1947 if (Node->getOpcode() == ISD::MEMSET) { 1948 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 1949 // Extend the ubyte argument to be an int value for the call. 1950 Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3); 1951 Args.push_back(std::make_pair(Tmp3, Type::IntTy)); 1952 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 1953 1954 FnName = "memset"; 1955 } else if (Node->getOpcode() == ISD::MEMCPY || 1956 Node->getOpcode() == ISD::MEMMOVE) { 1957 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 1958 Args.push_back(std::make_pair(Tmp3, IntPtrTy)); 1959 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 1960 FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy"; 1961 } else { 1962 assert(0 && "Unknown op!"); 1963 } 1964 1965 std::pair<SDOperand,SDOperand> CallResult = 1966 TLI.LowerCallTo(Tmp1, Type::VoidTy, false, CallingConv::C, false, 1967 DAG.getExternalSymbol(FnName, IntPtr), Args, DAG); 1968 Result = LegalizeOp(CallResult.second); 1969 break; 1970 } 1971 } 1972 break; 1973 } 1974 1975 case ISD::READPORT: 1976 Tmp1 = LegalizeOp(Node->getOperand(0)); 1977 Tmp2 = LegalizeOp(Node->getOperand(1)); 1978 1979 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 1980 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end()); 1981 std::vector<SDOperand> Ops; 1982 Ops.push_back(Tmp1); 1983 Ops.push_back(Tmp2); 1984 Result = DAG.getNode(ISD::READPORT, VTs, Ops); 1985 } else 1986 Result = SDOperand(Node, 0); 1987 // Since these produce two values, make sure to remember that we legalized 1988 // both of them. 1989 AddLegalizedOperand(SDOperand(Node, 0), Result); 1990 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1991 return Result.getValue(Op.ResNo); 1992 case ISD::WRITEPORT: 1993 Tmp1 = LegalizeOp(Node->getOperand(0)); 1994 Tmp2 = LegalizeOp(Node->getOperand(1)); 1995 Tmp3 = LegalizeOp(Node->getOperand(2)); 1996 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1997 Tmp3 != Node->getOperand(2)) 1998 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3); 1999 break; 2000 2001 case ISD::READIO: 2002 Tmp1 = LegalizeOp(Node->getOperand(0)); 2003 Tmp2 = LegalizeOp(Node->getOperand(1)); 2004 2005 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 2006 case TargetLowering::Custom: 2007 default: assert(0 && "This action not implemented for this operation!"); 2008 case TargetLowering::Legal: 2009 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 2010 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end()); 2011 std::vector<SDOperand> Ops; 2012 Ops.push_back(Tmp1); 2013 Ops.push_back(Tmp2); 2014 Result = DAG.getNode(ISD::READPORT, VTs, Ops); 2015 } else 2016 Result = SDOperand(Node, 0); 2017 break; 2018 case TargetLowering::Expand: 2019 // Replace this with a load from memory. 2020 Result = DAG.getLoad(Node->getValueType(0), Node->getOperand(0), 2021 Node->getOperand(1), DAG.getSrcValue(NULL)); 2022 Result = LegalizeOp(Result); 2023 break; 2024 } 2025 2026 // Since these produce two values, make sure to remember that we legalized 2027 // both of them. 2028 AddLegalizedOperand(SDOperand(Node, 0), Result); 2029 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 2030 return Result.getValue(Op.ResNo); 2031 2032 case ISD::WRITEIO: 2033 Tmp1 = LegalizeOp(Node->getOperand(0)); 2034 Tmp2 = LegalizeOp(Node->getOperand(1)); 2035 Tmp3 = LegalizeOp(Node->getOperand(2)); 2036 2037 switch (TLI.getOperationAction(Node->getOpcode(), 2038 Node->getOperand(1).getValueType())) { 2039 case TargetLowering::Custom: 2040 default: assert(0 && "This action not implemented for this operation!"); 2041 case TargetLowering::Legal: 2042 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 2043 Tmp3 != Node->getOperand(2)) 2044 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3); 2045 break; 2046 case TargetLowering::Expand: 2047 // Replace this with a store to memory. 2048 Result = DAG.getNode(ISD::STORE, MVT::Other, Node->getOperand(0), 2049 Node->getOperand(1), Node->getOperand(2), 2050 DAG.getSrcValue(NULL)); 2051 Result = LegalizeOp(Result); 2052 break; 2053 } 2054 break; 2055 2056 case ISD::ADD_PARTS: 2057 case ISD::SUB_PARTS: 2058 case ISD::SHL_PARTS: 2059 case ISD::SRA_PARTS: 2060 case ISD::SRL_PARTS: { 2061 std::vector<SDOperand> Ops; 2062 bool Changed = false; 2063 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 2064 Ops.push_back(LegalizeOp(Node->getOperand(i))); 2065 Changed |= Ops.back() != Node->getOperand(i); 2066 } 2067 if (Changed) { 2068 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end()); 2069 Result = DAG.getNode(Node->getOpcode(), VTs, Ops); 2070 } 2071 2072 switch (TLI.getOperationAction(Node->getOpcode(), 2073 Node->getValueType(0))) { 2074 default: assert(0 && "This action is not supported yet!"); 2075 case TargetLowering::Custom: { 2076 SDOperand Tmp = TLI.LowerOperation(Result, DAG); 2077 if (Tmp.Val) { 2078 SDOperand Tmp2, RetVal(0,0); 2079 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) { 2080 Tmp2 = LegalizeOp(Tmp.getValue(i)); 2081 AddLegalizedOperand(SDOperand(Node, i), Tmp2); 2082 if (i == Op.ResNo) 2083 RetVal = Tmp; 2084 } 2085 assert(RetVal.Val && "Illegal result number"); 2086 return RetVal; 2087 } 2088 // FALLTHROUGH if the target thinks it is legal. 2089 } 2090 case TargetLowering::Legal: 2091 // Nothing to do. 2092 break; 2093 } 2094 2095 // Since these produce multiple values, make sure to remember that we 2096 // legalized all of them. 2097 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 2098 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 2099 return Result.getValue(Op.ResNo); 2100 } 2101 2102 // Binary operators 2103 case ISD::ADD: 2104 case ISD::SUB: 2105 case ISD::MUL: 2106 case ISD::MULHS: 2107 case ISD::MULHU: 2108 case ISD::UDIV: 2109 case ISD::SDIV: 2110 case ISD::AND: 2111 case ISD::OR: 2112 case ISD::XOR: 2113 case ISD::SHL: 2114 case ISD::SRL: 2115 case ISD::SRA: 2116 case ISD::FADD: 2117 case ISD::FSUB: 2118 case ISD::FMUL: 2119 case ISD::FDIV: 2120 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 2121 switch (getTypeAction(Node->getOperand(1).getValueType())) { 2122 case Expand: assert(0 && "Not possible"); 2123 case Legal: 2124 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS. 2125 break; 2126 case Promote: 2127 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the RHS. 2128 break; 2129 } 2130 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 2131 case TargetLowering::Custom: { 2132 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, Tmp2); 2133 SDOperand Tmp = TLI.LowerOperation(Result, DAG); 2134 if (Tmp.Val) { 2135 Tmp = LegalizeOp(Tmp); // Relegalize input. 2136 AddLegalizedOperand(Op, Tmp); 2137 return Tmp; 2138 } //else it was considered legal and we fall through 2139 } 2140 case TargetLowering::Legal: 2141 if (Tmp1 != Node->getOperand(0) || 2142 Tmp2 != Node->getOperand(1)) 2143 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2); 2144 break; 2145 default: 2146 assert(0 && "Operation not supported"); 2147 } 2148 break; 2149 2150 case ISD::BUILD_PAIR: { 2151 MVT::ValueType PairTy = Node->getValueType(0); 2152 // TODO: handle the case where the Lo and Hi operands are not of legal type 2153 Tmp1 = LegalizeOp(Node->getOperand(0)); // Lo 2154 Tmp2 = LegalizeOp(Node->getOperand(1)); // Hi 2155 switch (TLI.getOperationAction(ISD::BUILD_PAIR, PairTy)) { 2156 case TargetLowering::Legal: 2157 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 2158 Result = DAG.getNode(ISD::BUILD_PAIR, PairTy, Tmp1, Tmp2); 2159 break; 2160 case TargetLowering::Promote: 2161 case TargetLowering::Custom: 2162 assert(0 && "Cannot promote/custom this yet!"); 2163 case TargetLowering::Expand: 2164 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, PairTy, Tmp1); 2165 Tmp2 = DAG.getNode(ISD::ANY_EXTEND, PairTy, Tmp2); 2166 Tmp2 = DAG.getNode(ISD::SHL, PairTy, Tmp2, 2167 DAG.getConstant(MVT::getSizeInBits(PairTy)/2, 2168 TLI.getShiftAmountTy())); 2169 Result = LegalizeOp(DAG.getNode(ISD::OR, PairTy, Tmp1, Tmp2)); 2170 break; 2171 } 2172 break; 2173 } 2174 2175 case ISD::UREM: 2176 case ISD::SREM: 2177 case ISD::FREM: 2178 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 2179 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 2180 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 2181 case TargetLowering::Custom: { 2182 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2); 2183 SDOperand Tmp = TLI.LowerOperation(Result, DAG); 2184 if (Tmp.Val) { 2185 Tmp = LegalizeOp(Tmp); // Relegalize input. 2186 AddLegalizedOperand(Op, Tmp); 2187 return Tmp; 2188 } //else it was considered legal and we fall through 2189 } 2190 case TargetLowering::Legal: 2191 if (Tmp1 != Node->getOperand(0) || 2192 Tmp2 != Node->getOperand(1)) 2193 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 2194 Tmp2); 2195 break; 2196 case TargetLowering::Promote: 2197 assert(0 && "Cannot promote handle this yet!"); 2198 case TargetLowering::Expand: 2199 if (MVT::isInteger(Node->getValueType(0))) { 2200 MVT::ValueType VT = Node->getValueType(0); 2201 unsigned Opc = (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV; 2202 Result = DAG.getNode(Opc, VT, Tmp1, Tmp2); 2203 Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2); 2204 Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result); 2205 } else { 2206 // Floating point mod -> fmod libcall. 2207 const char *FnName = Node->getValueType(0) == MVT::f32 ? "fmodf":"fmod"; 2208 SDOperand Dummy; 2209 Result = ExpandLibCall(FnName, Node, Dummy); 2210 } 2211 break; 2212 } 2213 break; 2214 2215 case ISD::ROTL: 2216 case ISD::ROTR: 2217 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 2218 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 2219 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 2220 case TargetLowering::Custom: 2221 case TargetLowering::Promote: 2222 case TargetLowering::Expand: 2223 assert(0 && "Cannot handle this yet!"); 2224 case TargetLowering::Legal: 2225 if (Tmp1 != Node->getOperand(0) || 2226 Tmp2 != Node->getOperand(1)) 2227 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 2228 Tmp2); 2229 break; 2230 } 2231 break; 2232 2233 case ISD::BSWAP: 2234 Tmp1 = LegalizeOp(Node->getOperand(0)); // Op 2235 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 2236 case TargetLowering::Legal: 2237 if (Tmp1 != Node->getOperand(0)) 2238 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2239 break; 2240 case TargetLowering::Promote: { 2241 MVT::ValueType OVT = Tmp1.getValueType(); 2242 MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT); 2243 unsigned DiffBits = getSizeInBits(NVT) - getSizeInBits(OVT); 2244 2245 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); 2246 Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1); 2247 Result = DAG.getNode(ISD::SRL, NVT, Tmp1, 2248 DAG.getConstant(DiffBits, TLI.getShiftAmountTy())); 2249 break; 2250 } 2251 case TargetLowering::Custom: 2252 assert(0 && "Cannot custom legalize this yet!"); 2253 case TargetLowering::Expand: { 2254 MVT::ValueType VT = Tmp1.getValueType(); 2255 switch (VT) { 2256 default: assert(0 && "Unhandled Expand type in BSWAP!"); abort(); 2257 case MVT::i16: 2258 Tmp2 = DAG.getNode(ISD::SHL, VT, Tmp1, 2259 DAG.getConstant(8, TLI.getShiftAmountTy())); 2260 Tmp1 = DAG.getNode(ISD::SRL, VT, Tmp1, 2261 DAG.getConstant(8, TLI.getShiftAmountTy())); 2262 Result = DAG.getNode(ISD::OR, VT, Tmp1, Tmp2); 2263 break; 2264 case MVT::i32: 2265 Tmp4 = DAG.getNode(ISD::SHL, VT, Tmp1, 2266 DAG.getConstant(24, TLI.getShiftAmountTy())); 2267 Tmp3 = DAG.getNode(ISD::SHL, VT, Tmp1, 2268 DAG.getConstant(8, TLI.getShiftAmountTy())); 2269 Tmp2 = DAG.getNode(ISD::SRL, VT, Tmp1, 2270 DAG.getConstant(8, TLI.getShiftAmountTy())); 2271 Tmp1 = DAG.getNode(ISD::SRL, VT, Tmp1, 2272 DAG.getConstant(24, TLI.getShiftAmountTy())); 2273 Tmp3 = DAG.getNode(ISD::AND, VT, Tmp3, DAG.getConstant(0xFF0000, VT)); 2274 Tmp2 = DAG.getNode(ISD::AND, VT, Tmp2, DAG.getConstant(0xFF00, VT)); 2275 Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3); 2276 Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1); 2277 Result = DAG.getNode(ISD::OR, VT, Tmp4, Tmp2); 2278 break; 2279 case MVT::i64: { 2280 SDOperand Tmp5, Tmp6, Tmp7, Tmp8; 2281 Tmp8 = DAG.getNode(ISD::SHL, VT, Tmp1, 2282 DAG.getConstant(56, TLI.getShiftAmountTy())); 2283 Tmp7 = DAG.getNode(ISD::SHL, VT, Tmp1, 2284 DAG.getConstant(40, TLI.getShiftAmountTy())); 2285 Tmp6 = DAG.getNode(ISD::SHL, VT, Tmp1, 2286 DAG.getConstant(24, TLI.getShiftAmountTy())); 2287 Tmp5 = DAG.getNode(ISD::SHL, VT, Tmp1, 2288 DAG.getConstant(8, TLI.getShiftAmountTy())); 2289 Tmp4 = DAG.getNode(ISD::SRL, VT, Tmp1, 2290 DAG.getConstant(8, TLI.getShiftAmountTy())); 2291 Tmp3 = DAG.getNode(ISD::SRL, VT, Tmp1, 2292 DAG.getConstant(24, TLI.getShiftAmountTy())); 2293 Tmp2 = DAG.getNode(ISD::SRL, VT, Tmp1, 2294 DAG.getConstant(40, TLI.getShiftAmountTy())); 2295 Tmp1 = DAG.getNode(ISD::SRL, VT, Tmp1, 2296 DAG.getConstant(56, TLI.getShiftAmountTy())); 2297 Tmp7 = DAG.getNode(ISD::AND, VT, Tmp7, 2298 DAG.getConstant(0x00FF000000000000ULL, VT)); 2299 Tmp6 = DAG.getNode(ISD::AND, VT, Tmp7, 2300 DAG.getConstant(0x0000FF0000000000ULL, VT)); 2301 Tmp5 = DAG.getNode(ISD::AND, VT, Tmp7, 2302 DAG.getConstant(0x000000FF00000000ULL, VT)); 2303 Tmp4 = DAG.getNode(ISD::AND, VT, Tmp7, 2304 DAG.getConstant(0x00000000FF000000ULL, VT)); 2305 Tmp3 = DAG.getNode(ISD::AND, VT, Tmp7, 2306 DAG.getConstant(0x0000000000FF0000ULL, VT)); 2307 Tmp2 = DAG.getNode(ISD::AND, VT, Tmp7, 2308 DAG.getConstant(0x000000000000FF00ULL, VT)); 2309 Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp7); 2310 Tmp6 = DAG.getNode(ISD::OR, VT, Tmp6, Tmp5); 2311 Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3); 2312 Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1); 2313 Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp6); 2314 Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp2); 2315 Result = DAG.getNode(ISD::OR, VT, Tmp8, Tmp4); 2316 break; 2317 } 2318 } 2319 break; 2320 } 2321 } 2322 break; 2323 2324 case ISD::CTPOP: 2325 case ISD::CTTZ: 2326 case ISD::CTLZ: 2327 Tmp1 = LegalizeOp(Node->getOperand(0)); // Op 2328 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 2329 case TargetLowering::Legal: 2330 if (Tmp1 != Node->getOperand(0)) 2331 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2332 break; 2333 case TargetLowering::Promote: { 2334 MVT::ValueType OVT = Tmp1.getValueType(); 2335 MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT); 2336 2337 // Zero extend the argument. 2338 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); 2339 // Perform the larger operation, then subtract if needed. 2340 Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2341 switch(Node->getOpcode()) 2342 { 2343 case ISD::CTPOP: 2344 Result = Tmp1; 2345 break; 2346 case ISD::CTTZ: 2347 //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT) 2348 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, 2349 DAG.getConstant(getSizeInBits(NVT), NVT), 2350 ISD::SETEQ); 2351 Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, 2352 DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1); 2353 break; 2354 case ISD::CTLZ: 2355 //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT)) 2356 Result = DAG.getNode(ISD::SUB, NVT, Tmp1, 2357 DAG.getConstant(getSizeInBits(NVT) - 2358 getSizeInBits(OVT), NVT)); 2359 break; 2360 } 2361 break; 2362 } 2363 case TargetLowering::Custom: 2364 assert(0 && "Cannot custom handle this yet!"); 2365 case TargetLowering::Expand: 2366 switch(Node->getOpcode()) 2367 { 2368 case ISD::CTPOP: { 2369 static const uint64_t mask[6] = { 2370 0x5555555555555555ULL, 0x3333333333333333ULL, 2371 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL, 2372 0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL 2373 }; 2374 MVT::ValueType VT = Tmp1.getValueType(); 2375 MVT::ValueType ShVT = TLI.getShiftAmountTy(); 2376 unsigned len = getSizeInBits(VT); 2377 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { 2378 //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8]) 2379 Tmp2 = DAG.getConstant(mask[i], VT); 2380 Tmp3 = DAG.getConstant(1ULL << i, ShVT); 2381 Tmp1 = DAG.getNode(ISD::ADD, VT, 2382 DAG.getNode(ISD::AND, VT, Tmp1, Tmp2), 2383 DAG.getNode(ISD::AND, VT, 2384 DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3), 2385 Tmp2)); 2386 } 2387 Result = Tmp1; 2388 break; 2389 } 2390 case ISD::CTLZ: { 2391 /* for now, we do this: 2392 x = x | (x >> 1); 2393 x = x | (x >> 2); 2394 ... 2395 x = x | (x >>16); 2396 x = x | (x >>32); // for 64-bit input 2397 return popcount(~x); 2398 2399 but see also: http://www.hackersdelight.org/HDcode/nlz.cc */ 2400 MVT::ValueType VT = Tmp1.getValueType(); 2401 MVT::ValueType ShVT = TLI.getShiftAmountTy(); 2402 unsigned len = getSizeInBits(VT); 2403 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { 2404 Tmp3 = DAG.getConstant(1ULL << i, ShVT); 2405 Tmp1 = DAG.getNode(ISD::OR, VT, Tmp1, 2406 DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3)); 2407 } 2408 Tmp3 = DAG.getNode(ISD::XOR, VT, Tmp1, DAG.getConstant(~0ULL, VT)); 2409 Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3)); 2410 break; 2411 } 2412 case ISD::CTTZ: { 2413 // for now, we use: { return popcount(~x & (x - 1)); } 2414 // unless the target has ctlz but not ctpop, in which case we use: 2415 // { return 32 - nlz(~x & (x-1)); } 2416 // see also http://www.hackersdelight.org/HDcode/ntz.cc 2417 MVT::ValueType VT = Tmp1.getValueType(); 2418 Tmp2 = DAG.getConstant(~0ULL, VT); 2419 Tmp3 = DAG.getNode(ISD::AND, VT, 2420 DAG.getNode(ISD::XOR, VT, Tmp1, Tmp2), 2421 DAG.getNode(ISD::SUB, VT, Tmp1, 2422 DAG.getConstant(1, VT))); 2423 // If ISD::CTLZ is legal and CTPOP isn't, then do that instead 2424 if (!TLI.isOperationLegal(ISD::CTPOP, VT) && 2425 TLI.isOperationLegal(ISD::CTLZ, VT)) { 2426 Result = LegalizeOp(DAG.getNode(ISD::SUB, VT, 2427 DAG.getConstant(getSizeInBits(VT), VT), 2428 DAG.getNode(ISD::CTLZ, VT, Tmp3))); 2429 } else { 2430 Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3)); 2431 } 2432 break; 2433 } 2434 default: 2435 assert(0 && "Cannot expand this yet!"); 2436 break; 2437 } 2438 break; 2439 } 2440 break; 2441 2442 // Unary operators 2443 case ISD::FABS: 2444 case ISD::FNEG: 2445 case ISD::FSQRT: 2446 case ISD::FSIN: 2447 case ISD::FCOS: 2448 Tmp1 = LegalizeOp(Node->getOperand(0)); 2449 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 2450 case TargetLowering::Legal: 2451 if (Tmp1 != Node->getOperand(0)) 2452 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2453 break; 2454 case TargetLowering::Promote: 2455 case TargetLowering::Custom: 2456 assert(0 && "Cannot promote/custom handle this yet!"); 2457 case TargetLowering::Expand: 2458 switch(Node->getOpcode()) { 2459 case ISD::FNEG: { 2460 // Expand Y = FNEG(X) -> Y = SUB -0.0, X 2461 Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0)); 2462 Result = LegalizeOp(DAG.getNode(ISD::FSUB, Node->getValueType(0), 2463 Tmp2, Tmp1)); 2464 break; 2465 } 2466 case ISD::FABS: { 2467 // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X). 2468 MVT::ValueType VT = Node->getValueType(0); 2469 Tmp2 = DAG.getConstantFP(0.0, VT); 2470 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, Tmp2, ISD::SETUGT); 2471 Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1); 2472 Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3); 2473 Result = LegalizeOp(Result); 2474 break; 2475 } 2476 case ISD::FSQRT: 2477 case ISD::FSIN: 2478 case ISD::FCOS: { 2479 MVT::ValueType VT = Node->getValueType(0); 2480 const char *FnName = 0; 2481 switch(Node->getOpcode()) { 2482 case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break; 2483 case ISD::FSIN: FnName = VT == MVT::f32 ? "sinf" : "sin"; break; 2484 case ISD::FCOS: FnName = VT == MVT::f32 ? "cosf" : "cos"; break; 2485 default: assert(0 && "Unreachable!"); 2486 } 2487 SDOperand Dummy; 2488 Result = ExpandLibCall(FnName, Node, Dummy); 2489 break; 2490 } 2491 default: 2492 assert(0 && "Unreachable!"); 2493 } 2494 break; 2495 } 2496 break; 2497 2498 case ISD::BIT_CONVERT: 2499 if (!isTypeLegal(Node->getOperand(0).getValueType())) 2500 Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0)); 2501 else { 2502 switch (TLI.getOperationAction(ISD::BIT_CONVERT, 2503 Node->getOperand(0).getValueType())) { 2504 default: assert(0 && "Unknown operation action!"); 2505 case TargetLowering::Expand: 2506 Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0)); 2507 break; 2508 case TargetLowering::Legal: 2509 Tmp1 = LegalizeOp(Node->getOperand(0)); 2510 if (Tmp1 != Node->getOperand(0)) 2511 Result = DAG.getNode(ISD::BIT_CONVERT, Node->getValueType(0), Tmp1); 2512 break; 2513 } 2514 } 2515 break; 2516 // Conversion operators. The source and destination have different types. 2517 case ISD::SINT_TO_FP: 2518 case ISD::UINT_TO_FP: { 2519 bool isSigned = Node->getOpcode() == ISD::SINT_TO_FP; 2520 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2521 case Legal: 2522 switch (TLI.getOperationAction(Node->getOpcode(), 2523 Node->getOperand(0).getValueType())) { 2524 default: assert(0 && "Unknown operation action!"); 2525 case TargetLowering::Expand: 2526 Result = ExpandLegalINT_TO_FP(isSigned, 2527 LegalizeOp(Node->getOperand(0)), 2528 Node->getValueType(0)); 2529 AddLegalizedOperand(Op, Result); 2530 return Result; 2531 case TargetLowering::Promote: 2532 Result = PromoteLegalINT_TO_FP(LegalizeOp(Node->getOperand(0)), 2533 Node->getValueType(0), 2534 isSigned); 2535 AddLegalizedOperand(Op, Result); 2536 return Result; 2537 case TargetLowering::Legal: 2538 break; 2539 case TargetLowering::Custom: { 2540 Tmp1 = LegalizeOp(Node->getOperand(0)); 2541 SDOperand Tmp = 2542 DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2543 Tmp = TLI.LowerOperation(Tmp, DAG); 2544 if (Tmp.Val) { 2545 Tmp = LegalizeOp(Tmp); // Relegalize input. 2546 AddLegalizedOperand(Op, Tmp); 2547 return Tmp; 2548 } else { 2549 assert(0 && "Target Must Lower this"); 2550 } 2551 } 2552 } 2553 2554 Tmp1 = LegalizeOp(Node->getOperand(0)); 2555 if (Tmp1 != Node->getOperand(0)) 2556 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2557 break; 2558 case Expand: 2559 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, 2560 Node->getValueType(0), Node->getOperand(0)); 2561 break; 2562 case Promote: 2563 if (isSigned) { 2564 Result = PromoteOp(Node->getOperand(0)); 2565 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 2566 Result, DAG.getValueType(Node->getOperand(0).getValueType())); 2567 Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result); 2568 } else { 2569 Result = PromoteOp(Node->getOperand(0)); 2570 Result = DAG.getZeroExtendInReg(Result, 2571 Node->getOperand(0).getValueType()); 2572 Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result); 2573 } 2574 break; 2575 } 2576 break; 2577 } 2578 case ISD::TRUNCATE: 2579 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2580 case Legal: 2581 Tmp1 = LegalizeOp(Node->getOperand(0)); 2582 if (Tmp1 != Node->getOperand(0)) 2583 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2584 break; 2585 case Expand: 2586 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 2587 2588 // Since the result is legal, we should just be able to truncate the low 2589 // part of the source. 2590 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1); 2591 break; 2592 case Promote: 2593 Result = PromoteOp(Node->getOperand(0)); 2594 Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result); 2595 break; 2596 } 2597 break; 2598 2599 case ISD::FP_TO_SINT: 2600 case ISD::FP_TO_UINT: 2601 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2602 case Legal: 2603 Tmp1 = LegalizeOp(Node->getOperand(0)); 2604 2605 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))){ 2606 default: assert(0 && "Unknown operation action!"); 2607 case TargetLowering::Expand: 2608 if (Node->getOpcode() == ISD::FP_TO_UINT) { 2609 SDOperand True, False; 2610 MVT::ValueType VT = Node->getOperand(0).getValueType(); 2611 MVT::ValueType NVT = Node->getValueType(0); 2612 unsigned ShiftAmt = MVT::getSizeInBits(Node->getValueType(0))-1; 2613 Tmp2 = DAG.getConstantFP((double)(1ULL << ShiftAmt), VT); 2614 Tmp3 = DAG.getSetCC(TLI.getSetCCResultTy(), 2615 Node->getOperand(0), Tmp2, ISD::SETLT); 2616 True = DAG.getNode(ISD::FP_TO_SINT, NVT, Node->getOperand(0)); 2617 False = DAG.getNode(ISD::FP_TO_SINT, NVT, 2618 DAG.getNode(ISD::FSUB, VT, Node->getOperand(0), 2619 Tmp2)); 2620 False = DAG.getNode(ISD::XOR, NVT, False, 2621 DAG.getConstant(1ULL << ShiftAmt, NVT)); 2622 Result = LegalizeOp(DAG.getNode(ISD::SELECT, NVT, Tmp3, True, False)); 2623 AddLegalizedOperand(SDOperand(Node, 0), Result); 2624 return Result; 2625 } else { 2626 assert(0 && "Do not know how to expand FP_TO_SINT yet!"); 2627 } 2628 break; 2629 case TargetLowering::Promote: 2630 Result = PromoteLegalFP_TO_INT(Tmp1, Node->getValueType(0), 2631 Node->getOpcode() == ISD::FP_TO_SINT); 2632 AddLegalizedOperand(Op, Result); 2633 return Result; 2634 case TargetLowering::Custom: { 2635 SDOperand Tmp = 2636 DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2637 Tmp = TLI.LowerOperation(Tmp, DAG); 2638 if (Tmp.Val) { 2639 Tmp = LegalizeOp(Tmp); 2640 AddLegalizedOperand(Op, Tmp); 2641 return Tmp; 2642 } else { 2643 // The target thinks this is legal afterall. 2644 break; 2645 } 2646 } 2647 case TargetLowering::Legal: 2648 break; 2649 } 2650 2651 if (Tmp1 != Node->getOperand(0)) 2652 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2653 break; 2654 case Expand: 2655 assert(0 && "Shouldn't need to expand other operators here!"); 2656 case Promote: 2657 Result = PromoteOp(Node->getOperand(0)); 2658 Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result); 2659 break; 2660 } 2661 break; 2662 2663 case ISD::ANY_EXTEND: 2664 case ISD::ZERO_EXTEND: 2665 case ISD::SIGN_EXTEND: 2666 case ISD::FP_EXTEND: 2667 case ISD::FP_ROUND: 2668 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2669 case Legal: 2670 Tmp1 = LegalizeOp(Node->getOperand(0)); 2671 if (Tmp1 != Node->getOperand(0)) 2672 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 2673 break; 2674 case Expand: 2675 assert(0 && "Shouldn't need to expand other operators here!"); 2676 2677 case Promote: 2678 switch (Node->getOpcode()) { 2679 case ISD::ANY_EXTEND: 2680 Result = PromoteOp(Node->getOperand(0)); 2681 Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result); 2682 break; 2683 case ISD::ZERO_EXTEND: 2684 Result = PromoteOp(Node->getOperand(0)); 2685 Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result); 2686 Result = DAG.getZeroExtendInReg(Result, 2687 Node->getOperand(0).getValueType()); 2688 break; 2689 case ISD::SIGN_EXTEND: 2690 Result = PromoteOp(Node->getOperand(0)); 2691 Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result); 2692 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 2693 Result, 2694 DAG.getValueType(Node->getOperand(0).getValueType())); 2695 break; 2696 case ISD::FP_EXTEND: 2697 Result = PromoteOp(Node->getOperand(0)); 2698 if (Result.getValueType() != Op.getValueType()) 2699 // Dynamically dead while we have only 2 FP types. 2700 Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result); 2701 break; 2702 case ISD::FP_ROUND: 2703 Result = PromoteOp(Node->getOperand(0)); 2704 Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result); 2705 break; 2706 } 2707 } 2708 break; 2709 case ISD::FP_ROUND_INREG: 2710 case ISD::SIGN_EXTEND_INREG: { 2711 Tmp1 = LegalizeOp(Node->getOperand(0)); 2712 MVT::ValueType ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT(); 2713 2714 // If this operation is not supported, convert it to a shl/shr or load/store 2715 // pair. 2716 switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) { 2717 default: assert(0 && "This action not supported for this op yet!"); 2718 case TargetLowering::Legal: 2719 if (Tmp1 != Node->getOperand(0)) 2720 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 2721 DAG.getValueType(ExtraVT)); 2722 break; 2723 case TargetLowering::Expand: 2724 // If this is an integer extend and shifts are supported, do that. 2725 if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) { 2726 // NOTE: we could fall back on load/store here too for targets without 2727 // SAR. However, it is doubtful that any exist. 2728 unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) - 2729 MVT::getSizeInBits(ExtraVT); 2730 SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy()); 2731 Result = DAG.getNode(ISD::SHL, Node->getValueType(0), 2732 Node->getOperand(0), ShiftCst); 2733 Result = DAG.getNode(ISD::SRA, Node->getValueType(0), 2734 Result, ShiftCst); 2735 } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) { 2736 // The only way we can lower this is to turn it into a STORETRUNC, 2737 // EXTLOAD pair, targetting a temporary location (a stack slot). 2738 2739 // NOTE: there is a choice here between constantly creating new stack 2740 // slots and always reusing the same one. We currently always create 2741 // new ones, as reuse may inhibit scheduling. 2742 const Type *Ty = MVT::getTypeForValueType(ExtraVT); 2743 unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty); 2744 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); 2745 MachineFunction &MF = DAG.getMachineFunction(); 2746 int SSFI = 2747 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 2748 SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); 2749 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(), 2750 Node->getOperand(0), StackSlot, 2751 DAG.getSrcValue(NULL), DAG.getValueType(ExtraVT)); 2752 Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0), 2753 Result, StackSlot, DAG.getSrcValue(NULL), 2754 ExtraVT); 2755 } else { 2756 assert(0 && "Unknown op"); 2757 } 2758 Result = LegalizeOp(Result); 2759 break; 2760 } 2761 break; 2762 } 2763 } 2764 2765 // Note that LegalizeOp may be reentered even from single-use nodes, which 2766 // means that we always must cache transformed nodes. 2767 AddLegalizedOperand(Op, Result); 2768 return Result; 2769} 2770 2771/// PromoteOp - Given an operation that produces a value in an invalid type, 2772/// promote it to compute the value into a larger type. The produced value will 2773/// have the correct bits for the low portion of the register, but no guarantee 2774/// is made about the top bits: it may be zero, sign-extended, or garbage. 2775SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { 2776 MVT::ValueType VT = Op.getValueType(); 2777 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 2778 assert(getTypeAction(VT) == Promote && 2779 "Caller should expand or legalize operands that are not promotable!"); 2780 assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) && 2781 "Cannot promote to smaller type!"); 2782 2783 SDOperand Tmp1, Tmp2, Tmp3; 2784 2785 SDOperand Result; 2786 SDNode *Node = Op.Val; 2787 2788 std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op); 2789 if (I != PromotedNodes.end()) return I->second; 2790 2791 // Promotion needs an optimization step to clean up after it, and is not 2792 // careful to avoid operations the target does not support. Make sure that 2793 // all generated operations are legalized in the next iteration. 2794 NeedsAnotherIteration = true; 2795 2796 switch (Node->getOpcode()) { 2797 case ISD::CopyFromReg: 2798 assert(0 && "CopyFromReg must be legal!"); 2799 default: 2800 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 2801 assert(0 && "Do not know how to promote this operator!"); 2802 abort(); 2803 case ISD::UNDEF: 2804 Result = DAG.getNode(ISD::UNDEF, NVT); 2805 break; 2806 case ISD::Constant: 2807 if (VT != MVT::i1) 2808 Result = DAG.getNode(ISD::SIGN_EXTEND, NVT, Op); 2809 else 2810 Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op); 2811 assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?"); 2812 break; 2813 case ISD::ConstantFP: 2814 Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op); 2815 assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?"); 2816 break; 2817 2818 case ISD::SETCC: 2819 assert(isTypeLegal(TLI.getSetCCResultTy()) && "SetCC type is not legal??"); 2820 Result = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),Node->getOperand(0), 2821 Node->getOperand(1), Node->getOperand(2)); 2822 Result = LegalizeOp(Result); 2823 break; 2824 2825 case ISD::TRUNCATE: 2826 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2827 case Legal: 2828 Result = LegalizeOp(Node->getOperand(0)); 2829 assert(Result.getValueType() >= NVT && 2830 "This truncation doesn't make sense!"); 2831 if (Result.getValueType() > NVT) // Truncate to NVT instead of VT 2832 Result = DAG.getNode(ISD::TRUNCATE, NVT, Result); 2833 break; 2834 case Promote: 2835 // The truncation is not required, because we don't guarantee anything 2836 // about high bits anyway. 2837 Result = PromoteOp(Node->getOperand(0)); 2838 break; 2839 case Expand: 2840 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 2841 // Truncate the low part of the expanded value to the result type 2842 Result = DAG.getNode(ISD::TRUNCATE, NVT, Tmp1); 2843 } 2844 break; 2845 case ISD::SIGN_EXTEND: 2846 case ISD::ZERO_EXTEND: 2847 case ISD::ANY_EXTEND: 2848 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2849 case Expand: assert(0 && "BUG: Smaller reg should have been promoted!"); 2850 case Legal: 2851 // Input is legal? Just do extend all the way to the larger type. 2852 Result = LegalizeOp(Node->getOperand(0)); 2853 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 2854 break; 2855 case Promote: 2856 // Promote the reg if it's smaller. 2857 Result = PromoteOp(Node->getOperand(0)); 2858 // The high bits are not guaranteed to be anything. Insert an extend. 2859 if (Node->getOpcode() == ISD::SIGN_EXTEND) 2860 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result, 2861 DAG.getValueType(Node->getOperand(0).getValueType())); 2862 else if (Node->getOpcode() == ISD::ZERO_EXTEND) 2863 Result = DAG.getZeroExtendInReg(Result, 2864 Node->getOperand(0).getValueType()); 2865 break; 2866 } 2867 break; 2868 case ISD::BIT_CONVERT: 2869 Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0)); 2870 Result = PromoteOp(Result); 2871 break; 2872 2873 case ISD::FP_EXTEND: 2874 assert(0 && "Case not implemented. Dynamically dead with 2 FP types!"); 2875 case ISD::FP_ROUND: 2876 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2877 case Expand: assert(0 && "BUG: Cannot expand FP regs!"); 2878 case Promote: assert(0 && "Unreachable with 2 FP types!"); 2879 case Legal: 2880 // Input is legal? Do an FP_ROUND_INREG. 2881 Result = LegalizeOp(Node->getOperand(0)); 2882 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 2883 DAG.getValueType(VT)); 2884 break; 2885 } 2886 break; 2887 2888 case ISD::SINT_TO_FP: 2889 case ISD::UINT_TO_FP: 2890 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2891 case Legal: 2892 Result = LegalizeOp(Node->getOperand(0)); 2893 // No extra round required here. 2894 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 2895 break; 2896 2897 case Promote: 2898 Result = PromoteOp(Node->getOperand(0)); 2899 if (Node->getOpcode() == ISD::SINT_TO_FP) 2900 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 2901 Result, 2902 DAG.getValueType(Node->getOperand(0).getValueType())); 2903 else 2904 Result = DAG.getZeroExtendInReg(Result, 2905 Node->getOperand(0).getValueType()); 2906 // No extra round required here. 2907 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 2908 break; 2909 case Expand: 2910 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT, 2911 Node->getOperand(0)); 2912 // Round if we cannot tolerate excess precision. 2913 if (NoExcessFPPrecision) 2914 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 2915 DAG.getValueType(VT)); 2916 break; 2917 } 2918 break; 2919 2920 case ISD::SIGN_EXTEND_INREG: 2921 Result = PromoteOp(Node->getOperand(0)); 2922 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result, 2923 Node->getOperand(1)); 2924 break; 2925 case ISD::FP_TO_SINT: 2926 case ISD::FP_TO_UINT: 2927 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2928 case Legal: 2929 Tmp1 = LegalizeOp(Node->getOperand(0)); 2930 break; 2931 case Promote: 2932 // The input result is prerounded, so we don't have to do anything 2933 // special. 2934 Tmp1 = PromoteOp(Node->getOperand(0)); 2935 break; 2936 case Expand: 2937 assert(0 && "not implemented"); 2938 } 2939 // If we're promoting a UINT to a larger size, check to see if the new node 2940 // will be legal. If it isn't, check to see if FP_TO_SINT is legal, since 2941 // we can use that instead. This allows us to generate better code for 2942 // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not 2943 // legal, such as PowerPC. 2944 if (Node->getOpcode() == ISD::FP_TO_UINT && 2945 !TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) && 2946 (TLI.isOperationLegal(ISD::FP_TO_SINT, NVT) || 2947 TLI.getOperationAction(ISD::FP_TO_SINT, NVT)==TargetLowering::Custom)){ 2948 Result = DAG.getNode(ISD::FP_TO_SINT, NVT, Tmp1); 2949 } else { 2950 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 2951 } 2952 break; 2953 2954 case ISD::FABS: 2955 case ISD::FNEG: 2956 Tmp1 = PromoteOp(Node->getOperand(0)); 2957 assert(Tmp1.getValueType() == NVT); 2958 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 2959 // NOTE: we do not have to do any extra rounding here for 2960 // NoExcessFPPrecision, because we know the input will have the appropriate 2961 // precision, and these operations don't modify precision at all. 2962 break; 2963 2964 case ISD::FSQRT: 2965 case ISD::FSIN: 2966 case ISD::FCOS: 2967 Tmp1 = PromoteOp(Node->getOperand(0)); 2968 assert(Tmp1.getValueType() == NVT); 2969 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 2970 if(NoExcessFPPrecision) 2971 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 2972 DAG.getValueType(VT)); 2973 break; 2974 2975 case ISD::AND: 2976 case ISD::OR: 2977 case ISD::XOR: 2978 case ISD::ADD: 2979 case ISD::SUB: 2980 case ISD::MUL: 2981 // The input may have strange things in the top bits of the registers, but 2982 // these operations don't care. They may have weird bits going out, but 2983 // that too is okay if they are integer operations. 2984 Tmp1 = PromoteOp(Node->getOperand(0)); 2985 Tmp2 = PromoteOp(Node->getOperand(1)); 2986 assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT); 2987 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 2988 break; 2989 case ISD::FADD: 2990 case ISD::FSUB: 2991 case ISD::FMUL: 2992 // The input may have strange things in the top bits of the registers, but 2993 // these operations don't care. 2994 Tmp1 = PromoteOp(Node->getOperand(0)); 2995 Tmp2 = PromoteOp(Node->getOperand(1)); 2996 assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT); 2997 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 2998 2999 // Floating point operations will give excess precision that we may not be 3000 // able to tolerate. If we DO allow excess precision, just leave it, 3001 // otherwise excise it. 3002 // FIXME: Why would we need to round FP ops more than integer ones? 3003 // Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C)) 3004 if (NoExcessFPPrecision) 3005 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 3006 DAG.getValueType(VT)); 3007 break; 3008 3009 case ISD::SDIV: 3010 case ISD::SREM: 3011 // These operators require that their input be sign extended. 3012 Tmp1 = PromoteOp(Node->getOperand(0)); 3013 Tmp2 = PromoteOp(Node->getOperand(1)); 3014 if (MVT::isInteger(NVT)) { 3015 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, 3016 DAG.getValueType(VT)); 3017 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, 3018 DAG.getValueType(VT)); 3019 } 3020 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 3021 3022 // Perform FP_ROUND: this is probably overly pessimistic. 3023 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision) 3024 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 3025 DAG.getValueType(VT)); 3026 break; 3027 case ISD::FDIV: 3028 case ISD::FREM: 3029 // These operators require that their input be fp extended. 3030 Tmp1 = PromoteOp(Node->getOperand(0)); 3031 Tmp2 = PromoteOp(Node->getOperand(1)); 3032 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 3033 3034 // Perform FP_ROUND: this is probably overly pessimistic. 3035 if (NoExcessFPPrecision) 3036 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 3037 DAG.getValueType(VT)); 3038 break; 3039 3040 case ISD::UDIV: 3041 case ISD::UREM: 3042 // These operators require that their input be zero extended. 3043 Tmp1 = PromoteOp(Node->getOperand(0)); 3044 Tmp2 = PromoteOp(Node->getOperand(1)); 3045 assert(MVT::isInteger(NVT) && "Operators don't apply to FP!"); 3046 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT); 3047 Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT); 3048 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 3049 break; 3050 3051 case ISD::SHL: 3052 Tmp1 = PromoteOp(Node->getOperand(0)); 3053 Tmp2 = LegalizeOp(Node->getOperand(1)); 3054 Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2); 3055 break; 3056 case ISD::SRA: 3057 // The input value must be properly sign extended. 3058 Tmp1 = PromoteOp(Node->getOperand(0)); 3059 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, 3060 DAG.getValueType(VT)); 3061 Tmp2 = LegalizeOp(Node->getOperand(1)); 3062 Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2); 3063 break; 3064 case ISD::SRL: 3065 // The input value must be properly zero extended. 3066 Tmp1 = PromoteOp(Node->getOperand(0)); 3067 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT); 3068 Tmp2 = LegalizeOp(Node->getOperand(1)); 3069 Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2); 3070 break; 3071 3072 case ISD::LOAD: 3073 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 3074 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 3075 Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Tmp1, Tmp2, 3076 Node->getOperand(2), VT); 3077 // Remember that we legalized the chain. 3078 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 3079 break; 3080 case ISD::SEXTLOAD: 3081 case ISD::ZEXTLOAD: 3082 case ISD::EXTLOAD: 3083 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 3084 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 3085 Result = DAG.getExtLoad(Node->getOpcode(), NVT, Tmp1, Tmp2, 3086 Node->getOperand(2), 3087 cast<VTSDNode>(Node->getOperand(3))->getVT()); 3088 // Remember that we legalized the chain. 3089 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 3090 break; 3091 case ISD::SELECT: 3092 switch (getTypeAction(Node->getOperand(0).getValueType())) { 3093 case Expand: assert(0 && "It's impossible to expand bools"); 3094 case Legal: 3095 Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition. 3096 break; 3097 case Promote: 3098 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 3099 break; 3100 } 3101 Tmp2 = PromoteOp(Node->getOperand(1)); // Legalize the op0 3102 Tmp3 = PromoteOp(Node->getOperand(2)); // Legalize the op1 3103 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3); 3104 break; 3105 case ISD::SELECT_CC: 3106 Tmp2 = PromoteOp(Node->getOperand(2)); // True 3107 Tmp3 = PromoteOp(Node->getOperand(3)); // False 3108 Result = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0), 3109 Node->getOperand(1), Tmp2, Tmp3, 3110 Node->getOperand(4)); 3111 break; 3112 case ISD::TAILCALL: 3113 case ISD::CALL: { 3114 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 3115 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 3116 3117 std::vector<SDOperand> Ops; 3118 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) 3119 Ops.push_back(LegalizeOp(Node->getOperand(i))); 3120 3121 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 3122 "Can only promote single result calls"); 3123 std::vector<MVT::ValueType> RetTyVTs; 3124 RetTyVTs.reserve(2); 3125 RetTyVTs.push_back(NVT); 3126 RetTyVTs.push_back(MVT::Other); 3127 SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops, 3128 Node->getOpcode() == ISD::TAILCALL); 3129 Result = SDOperand(NC, 0); 3130 3131 // Insert the new chain mapping. 3132 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 3133 break; 3134 } 3135 case ISD::BSWAP: 3136 Tmp1 = Node->getOperand(0); 3137 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); 3138 Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1); 3139 Result = DAG.getNode(ISD::SRL, NVT, Tmp1, 3140 DAG.getConstant(getSizeInBits(NVT) - getSizeInBits(VT), 3141 TLI.getShiftAmountTy())); 3142 break; 3143 case ISD::CTPOP: 3144 case ISD::CTTZ: 3145 case ISD::CTLZ: 3146 Tmp1 = Node->getOperand(0); 3147 //Zero extend the argument 3148 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); 3149 // Perform the larger operation, then subtract if needed. 3150 Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 3151 switch(Node->getOpcode()) 3152 { 3153 case ISD::CTPOP: 3154 Result = Tmp1; 3155 break; 3156 case ISD::CTTZ: 3157 //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT) 3158 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, 3159 DAG.getConstant(getSizeInBits(NVT), NVT), ISD::SETEQ); 3160 Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, 3161 DAG.getConstant(getSizeInBits(VT),NVT), Tmp1); 3162 break; 3163 case ISD::CTLZ: 3164 //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT)) 3165 Result = DAG.getNode(ISD::SUB, NVT, Tmp1, 3166 DAG.getConstant(getSizeInBits(NVT) - 3167 getSizeInBits(VT), NVT)); 3168 break; 3169 } 3170 break; 3171 } 3172 3173 assert(Result.Val && "Didn't set a result!"); 3174 AddPromotedOperand(Op, Result); 3175 return Result; 3176} 3177 3178/// ExpandBIT_CONVERT - Expand a BIT_CONVERT node into a store/load combination. 3179/// The resultant code need not be legal. Note that SrcOp is the input operand 3180/// to the BIT_CONVERT, not the BIT_CONVERT node itself. 3181SDOperand SelectionDAGLegalize::ExpandBIT_CONVERT(MVT::ValueType DestVT, 3182 SDOperand SrcOp) { 3183 // Create the stack frame object. 3184 MachineFrameInfo *FrameInfo = DAG.getMachineFunction().getFrameInfo(); 3185 unsigned ByteSize = MVT::getSizeInBits(DestVT)/8; 3186 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, ByteSize); 3187 SDOperand FIPtr = DAG.getFrameIndex(FrameIdx, TLI.getPointerTy()); 3188 3189 // Emit a store to the stack slot. 3190 SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(), 3191 SrcOp, FIPtr, DAG.getSrcValue(NULL)); 3192 // Result is a load from the stack slot. 3193 return DAG.getLoad(DestVT, Store, FIPtr, DAG.getSrcValue(0)); 3194} 3195 3196/// ExpandAddSub - Find a clever way to expand this add operation into 3197/// subcomponents. 3198void SelectionDAGLegalize:: 3199ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS, 3200 SDOperand &Lo, SDOperand &Hi) { 3201 // Expand the subcomponents. 3202 SDOperand LHSL, LHSH, RHSL, RHSH; 3203 ExpandOp(LHS, LHSL, LHSH); 3204 ExpandOp(RHS, RHSL, RHSH); 3205 3206 std::vector<SDOperand> Ops; 3207 Ops.push_back(LHSL); 3208 Ops.push_back(LHSH); 3209 Ops.push_back(RHSL); 3210 Ops.push_back(RHSH); 3211 std::vector<MVT::ValueType> VTs(2, LHSL.getValueType()); 3212 Lo = DAG.getNode(NodeOp, VTs, Ops); 3213 Hi = Lo.getValue(1); 3214} 3215 3216void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp, 3217 SDOperand Op, SDOperand Amt, 3218 SDOperand &Lo, SDOperand &Hi) { 3219 // Expand the subcomponents. 3220 SDOperand LHSL, LHSH; 3221 ExpandOp(Op, LHSL, LHSH); 3222 3223 std::vector<SDOperand> Ops; 3224 Ops.push_back(LHSL); 3225 Ops.push_back(LHSH); 3226 Ops.push_back(Amt); 3227 std::vector<MVT::ValueType> VTs(2, LHSL.getValueType()); 3228 Lo = DAG.getNode(NodeOp, VTs, Ops); 3229 Hi = Lo.getValue(1); 3230} 3231 3232 3233/// ExpandShift - Try to find a clever way to expand this shift operation out to 3234/// smaller elements. If we can't find a way that is more efficient than a 3235/// libcall on this target, return false. Otherwise, return true with the 3236/// low-parts expanded into Lo and Hi. 3237bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt, 3238 SDOperand &Lo, SDOperand &Hi) { 3239 assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) && 3240 "This is not a shift!"); 3241 3242 MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType()); 3243 SDOperand ShAmt = LegalizeOp(Amt); 3244 MVT::ValueType ShTy = ShAmt.getValueType(); 3245 unsigned VTBits = MVT::getSizeInBits(Op.getValueType()); 3246 unsigned NVTBits = MVT::getSizeInBits(NVT); 3247 3248 // Handle the case when Amt is an immediate. Other cases are currently broken 3249 // and are disabled. 3250 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) { 3251 unsigned Cst = CN->getValue(); 3252 // Expand the incoming operand to be shifted, so that we have its parts 3253 SDOperand InL, InH; 3254 ExpandOp(Op, InL, InH); 3255 switch(Opc) { 3256 case ISD::SHL: 3257 if (Cst > VTBits) { 3258 Lo = DAG.getConstant(0, NVT); 3259 Hi = DAG.getConstant(0, NVT); 3260 } else if (Cst > NVTBits) { 3261 Lo = DAG.getConstant(0, NVT); 3262 Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy)); 3263 } else if (Cst == NVTBits) { 3264 Lo = DAG.getConstant(0, NVT); 3265 Hi = InL; 3266 } else { 3267 Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy)); 3268 Hi = DAG.getNode(ISD::OR, NVT, 3269 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)), 3270 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy))); 3271 } 3272 return true; 3273 case ISD::SRL: 3274 if (Cst > VTBits) { 3275 Lo = DAG.getConstant(0, NVT); 3276 Hi = DAG.getConstant(0, NVT); 3277 } else if (Cst > NVTBits) { 3278 Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy)); 3279 Hi = DAG.getConstant(0, NVT); 3280 } else if (Cst == NVTBits) { 3281 Lo = InH; 3282 Hi = DAG.getConstant(0, NVT); 3283 } else { 3284 Lo = DAG.getNode(ISD::OR, NVT, 3285 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)), 3286 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy))); 3287 Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy)); 3288 } 3289 return true; 3290 case ISD::SRA: 3291 if (Cst > VTBits) { 3292 Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH, 3293 DAG.getConstant(NVTBits-1, ShTy)); 3294 } else if (Cst > NVTBits) { 3295 Lo = DAG.getNode(ISD::SRA, NVT, InH, 3296 DAG.getConstant(Cst-NVTBits, ShTy)); 3297 Hi = DAG.getNode(ISD::SRA, NVT, InH, 3298 DAG.getConstant(NVTBits-1, ShTy)); 3299 } else if (Cst == NVTBits) { 3300 Lo = InH; 3301 Hi = DAG.getNode(ISD::SRA, NVT, InH, 3302 DAG.getConstant(NVTBits-1, ShTy)); 3303 } else { 3304 Lo = DAG.getNode(ISD::OR, NVT, 3305 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)), 3306 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy))); 3307 Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy)); 3308 } 3309 return true; 3310 } 3311 } 3312 // FIXME: The following code for expanding shifts using ISD::SELECT is buggy, 3313 // so disable it for now. Currently targets are handling this via SHL_PARTS 3314 // and friends. 3315 return false; 3316 3317 // If we have an efficient select operation (or if the selects will all fold 3318 // away), lower to some complex code, otherwise just emit the libcall. 3319 if (!TLI.isOperationLegal(ISD::SELECT, NVT) && !isa<ConstantSDNode>(Amt)) 3320 return false; 3321 3322 SDOperand InL, InH; 3323 ExpandOp(Op, InL, InH); 3324 SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy, // NAmt = 32-ShAmt 3325 DAG.getConstant(NVTBits, ShTy), ShAmt); 3326 3327 // Compare the unmasked shift amount against 32. 3328 SDOperand Cond = DAG.getSetCC(TLI.getSetCCResultTy(), ShAmt, 3329 DAG.getConstant(NVTBits, ShTy), ISD::SETGE); 3330 3331 if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) { 3332 ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt, // ShAmt &= 31 3333 DAG.getConstant(NVTBits-1, ShTy)); 3334 NAmt = DAG.getNode(ISD::AND, ShTy, NAmt, // NAmt &= 31 3335 DAG.getConstant(NVTBits-1, ShTy)); 3336 } 3337 3338 if (Opc == ISD::SHL) { 3339 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt) 3340 DAG.getNode(ISD::SHL, NVT, InH, ShAmt), 3341 DAG.getNode(ISD::SRL, NVT, InL, NAmt)); 3342 SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31 3343 3344 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1); 3345 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2); 3346 } else { 3347 SDOperand HiLoPart = DAG.getNode(ISD::SELECT, NVT, 3348 DAG.getSetCC(TLI.getSetCCResultTy(), NAmt, 3349 DAG.getConstant(32, ShTy), 3350 ISD::SETEQ), 3351 DAG.getConstant(0, NVT), 3352 DAG.getNode(ISD::SHL, NVT, InH, NAmt)); 3353 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt) 3354 HiLoPart, 3355 DAG.getNode(ISD::SRL, NVT, InL, ShAmt)); 3356 SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt); // T2 = InH >> ShAmt&31 3357 3358 SDOperand HiPart; 3359 if (Opc == ISD::SRA) 3360 HiPart = DAG.getNode(ISD::SRA, NVT, InH, 3361 DAG.getConstant(NVTBits-1, ShTy)); 3362 else 3363 HiPart = DAG.getConstant(0, NVT); 3364 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1); 3365 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart, T2); 3366 } 3367 return true; 3368} 3369 3370/// FindLatestCallSeqStart - Scan up the dag to find the latest (highest 3371/// NodeDepth) node that is an CallSeqStart operation and occurs later than 3372/// Found. 3373static void FindLatestCallSeqStart(SDNode *Node, SDNode *&Found, 3374 std::set<SDNode*> &Visited) { 3375 if (Node->getNodeDepth() <= Found->getNodeDepth() || 3376 !Visited.insert(Node).second) return; 3377 3378 // If we found an CALLSEQ_START, we already know this node occurs later 3379 // than the Found node. Just remember this node and return. 3380 if (Node->getOpcode() == ISD::CALLSEQ_START) { 3381 Found = Node; 3382 return; 3383 } 3384 3385 // Otherwise, scan the operands of Node to see if any of them is a call. 3386 assert(Node->getNumOperands() != 0 && 3387 "All leaves should have depth equal to the entry node!"); 3388 for (unsigned i = 0, e = Node->getNumOperands()-1; i != e; ++i) 3389 FindLatestCallSeqStart(Node->getOperand(i).Val, Found, Visited); 3390 3391 // Tail recurse for the last iteration. 3392 FindLatestCallSeqStart(Node->getOperand(Node->getNumOperands()-1).Val, 3393 Found, Visited); 3394} 3395 3396 3397/// FindEarliestCallSeqEnd - Scan down the dag to find the earliest (lowest 3398/// NodeDepth) node that is an CallSeqEnd operation and occurs more recent 3399/// than Found. 3400static void FindEarliestCallSeqEnd(SDNode *Node, SDNode *&Found, 3401 std::set<SDNode*> &Visited) { 3402 if ((Found && Node->getNodeDepth() >= Found->getNodeDepth()) || 3403 !Visited.insert(Node).second) return; 3404 3405 // If we found an CALLSEQ_END, we already know this node occurs earlier 3406 // than the Found node. Just remember this node and return. 3407 if (Node->getOpcode() == ISD::CALLSEQ_END) { 3408 Found = Node; 3409 return; 3410 } 3411 3412 // Otherwise, scan the operands of Node to see if any of them is a call. 3413 SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); 3414 if (UI == E) return; 3415 for (--E; UI != E; ++UI) 3416 FindEarliestCallSeqEnd(*UI, Found, Visited); 3417 3418 // Tail recurse for the last iteration. 3419 FindEarliestCallSeqEnd(*UI, Found, Visited); 3420} 3421 3422/// FindCallSeqEnd - Given a chained node that is part of a call sequence, 3423/// find the CALLSEQ_END node that terminates the call sequence. 3424static SDNode *FindCallSeqEnd(SDNode *Node) { 3425 if (Node->getOpcode() == ISD::CALLSEQ_END) 3426 return Node; 3427 if (Node->use_empty()) 3428 return 0; // No CallSeqEnd 3429 3430 // The chain is usually at the end. 3431 SDOperand TheChain(Node, Node->getNumValues()-1); 3432 if (TheChain.getValueType() != MVT::Other) { 3433 // Sometimes it's at the beginning. 3434 TheChain = SDOperand(Node, 0); 3435 if (TheChain.getValueType() != MVT::Other) { 3436 // Otherwise, hunt for it. 3437 for (unsigned i = 1, e = Node->getNumValues(); i != e; ++i) 3438 if (Node->getValueType(i) == MVT::Other) { 3439 TheChain = SDOperand(Node, i); 3440 break; 3441 } 3442 3443 // Otherwise, we walked into a node without a chain. 3444 if (TheChain.getValueType() != MVT::Other) 3445 return 0; 3446 } 3447 } 3448 3449 for (SDNode::use_iterator UI = Node->use_begin(), 3450 E = Node->use_end(); UI != E; ++UI) { 3451 3452 // Make sure to only follow users of our token chain. 3453 SDNode *User = *UI; 3454 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 3455 if (User->getOperand(i) == TheChain) 3456 if (SDNode *Result = FindCallSeqEnd(User)) 3457 return Result; 3458 } 3459 return 0; 3460} 3461 3462/// FindCallSeqStart - Given a chained node that is part of a call sequence, 3463/// find the CALLSEQ_START node that initiates the call sequence. 3464static SDNode *FindCallSeqStart(SDNode *Node) { 3465 assert(Node && "Didn't find callseq_start for a call??"); 3466 if (Node->getOpcode() == ISD::CALLSEQ_START) return Node; 3467 3468 assert(Node->getOperand(0).getValueType() == MVT::Other && 3469 "Node doesn't have a token chain argument!"); 3470 return FindCallSeqStart(Node->getOperand(0).Val); 3471} 3472 3473 3474/// FindInputOutputChains - If we are replacing an operation with a call we need 3475/// to find the call that occurs before and the call that occurs after it to 3476/// properly serialize the calls in the block. The returned operand is the 3477/// input chain value for the new call (e.g. the entry node or the previous 3478/// call), and OutChain is set to be the chain node to update to point to the 3479/// end of the call chain. 3480static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain, 3481 SDOperand Entry) { 3482 SDNode *LatestCallSeqStart = Entry.Val; 3483 SDNode *LatestCallSeqEnd = 0; 3484 std::set<SDNode*> Visited; 3485 FindLatestCallSeqStart(OpNode, LatestCallSeqStart, Visited); 3486 Visited.clear(); 3487 //std::cerr<<"Found node: "; LatestCallSeqStart->dump(); std::cerr <<"\n"; 3488 3489 // It is possible that no ISD::CALLSEQ_START was found because there is no 3490 // previous call in the function. LatestCallStackDown may in that case be 3491 // the entry node itself. Do not attempt to find a matching CALLSEQ_END 3492 // unless LatestCallStackDown is an CALLSEQ_START. 3493 if (LatestCallSeqStart->getOpcode() == ISD::CALLSEQ_START) { 3494 LatestCallSeqEnd = FindCallSeqEnd(LatestCallSeqStart); 3495 //std::cerr<<"Found end node: "; LatestCallSeqEnd->dump(); std::cerr <<"\n"; 3496 } else { 3497 LatestCallSeqEnd = Entry.Val; 3498 } 3499 assert(LatestCallSeqEnd && "NULL return from FindCallSeqEnd"); 3500 3501 // Finally, find the first call that this must come before, first we find the 3502 // CallSeqEnd that ends the call. 3503 OutChain = 0; 3504 FindEarliestCallSeqEnd(OpNode, OutChain, Visited); 3505 Visited.clear(); 3506 3507 // If we found one, translate from the adj up to the callseq_start. 3508 if (OutChain) 3509 OutChain = FindCallSeqStart(OutChain); 3510 3511 return SDOperand(LatestCallSeqEnd, 0); 3512} 3513 3514/// SpliceCallInto - Given the result chain of a libcall (CallResult), and a 3515void SelectionDAGLegalize::SpliceCallInto(const SDOperand &CallResult, 3516 SDNode *OutChain) { 3517 // Nothing to splice it into? 3518 if (OutChain == 0) return; 3519 3520 assert(OutChain->getOperand(0).getValueType() == MVT::Other); 3521 //OutChain->dump(); 3522 3523 // Form a token factor node merging the old inval and the new inval. 3524 SDOperand InToken = DAG.getNode(ISD::TokenFactor, MVT::Other, CallResult, 3525 OutChain->getOperand(0)); 3526 // Change the node to refer to the new token. 3527 OutChain->setAdjCallChain(InToken); 3528} 3529 3530 3531// ExpandLibCall - Expand a node into a call to a libcall. If the result value 3532// does not fit into a register, return the lo part and set the hi part to the 3533// by-reg argument. If it does fit into a single register, return the result 3534// and leave the Hi part unset. 3535SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node, 3536 SDOperand &Hi) { 3537 SDNode *OutChain; 3538 SDOperand InChain = FindInputOutputChains(Node, OutChain, 3539 DAG.getEntryNode()); 3540 if (InChain.Val == 0) 3541 InChain = DAG.getEntryNode(); 3542 3543 TargetLowering::ArgListTy Args; 3544 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 3545 MVT::ValueType ArgVT = Node->getOperand(i).getValueType(); 3546 const Type *ArgTy = MVT::getTypeForValueType(ArgVT); 3547 Args.push_back(std::make_pair(Node->getOperand(i), ArgTy)); 3548 } 3549 SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy()); 3550 3551 // Splice the libcall in wherever FindInputOutputChains tells us to. 3552 const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0)); 3553 std::pair<SDOperand,SDOperand> CallInfo = 3554 TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, false, 3555 Callee, Args, DAG); 3556 3557 SDOperand Result; 3558 switch (getTypeAction(CallInfo.first.getValueType())) { 3559 default: assert(0 && "Unknown thing"); 3560 case Legal: 3561 Result = CallInfo.first; 3562 break; 3563 case Promote: 3564 assert(0 && "Cannot promote this yet!"); 3565 case Expand: 3566 ExpandOp(CallInfo.first, Result, Hi); 3567 CallInfo.second = LegalizeOp(CallInfo.second); 3568 break; 3569 } 3570 3571 SpliceCallInto(CallInfo.second, OutChain); 3572 NeedsAnotherIteration = true; 3573 return Result; 3574} 3575 3576 3577/// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the 3578/// destination type is legal. 3579SDOperand SelectionDAGLegalize:: 3580ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) { 3581 assert(isTypeLegal(DestTy) && "Destination type is not legal!"); 3582 assert(getTypeAction(Source.getValueType()) == Expand && 3583 "This is not an expansion!"); 3584 assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!"); 3585 3586 if (!isSigned) { 3587 assert(Source.getValueType() == MVT::i64 && 3588 "This only works for 64-bit -> FP"); 3589 // The 64-bit value loaded will be incorrectly if the 'sign bit' of the 3590 // incoming integer is set. To handle this, we dynamically test to see if 3591 // it is set, and, if so, add a fudge factor. 3592 SDOperand Lo, Hi; 3593 ExpandOp(Source, Lo, Hi); 3594 3595 // If this is unsigned, and not supported, first perform the conversion to 3596 // signed, then adjust the result if the sign bit is set. 3597 SDOperand SignedConv = ExpandIntToFP(true, DestTy, 3598 DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi)); 3599 3600 SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi, 3601 DAG.getConstant(0, Hi.getValueType()), 3602 ISD::SETLT); 3603 SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4); 3604 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(), 3605 SignSet, Four, Zero); 3606 uint64_t FF = 0x5f800000ULL; 3607 if (TLI.isLittleEndian()) FF <<= 32; 3608 static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF); 3609 3610 SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy()); 3611 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset); 3612 SDOperand FudgeInReg; 3613 if (DestTy == MVT::f32) 3614 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, 3615 DAG.getSrcValue(NULL)); 3616 else { 3617 assert(DestTy == MVT::f64 && "Unexpected conversion"); 3618 FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), 3619 CPIdx, DAG.getSrcValue(NULL), MVT::f32); 3620 } 3621 return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg); 3622 } 3623 3624 // Check to see if the target has a custom way to lower this. If so, use it. 3625 switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) { 3626 default: assert(0 && "This action not implemented for this operation!"); 3627 case TargetLowering::Legal: 3628 case TargetLowering::Expand: 3629 break; // This case is handled below. 3630 case TargetLowering::Custom: { 3631 SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy, 3632 Source), DAG); 3633 if (NV.Val) 3634 return LegalizeOp(NV); 3635 break; // The target decided this was legal after all 3636 } 3637 } 3638 3639 // Expand the source, then glue it back together for the call. We must expand 3640 // the source in case it is shared (this pass of legalize must traverse it). 3641 SDOperand SrcLo, SrcHi; 3642 ExpandOp(Source, SrcLo, SrcHi); 3643 Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi); 3644 3645 SDNode *OutChain = 0; 3646 SDOperand InChain = FindInputOutputChains(Source.Val, OutChain, 3647 DAG.getEntryNode()); 3648 const char *FnName = 0; 3649 if (DestTy == MVT::f32) 3650 FnName = "__floatdisf"; 3651 else { 3652 assert(DestTy == MVT::f64 && "Unknown fp value type!"); 3653 FnName = "__floatdidf"; 3654 } 3655 3656 SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy()); 3657 3658 TargetLowering::ArgListTy Args; 3659 const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType()); 3660 3661 Args.push_back(std::make_pair(Source, ArgTy)); 3662 3663 // We don't care about token chains for libcalls. We just use the entry 3664 // node as our input and ignore the output chain. This allows us to place 3665 // calls wherever we need them to satisfy data dependences. 3666 const Type *RetTy = MVT::getTypeForValueType(DestTy); 3667 3668 std::pair<SDOperand,SDOperand> CallResult = 3669 TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, true, 3670 Callee, Args, DAG); 3671 3672 SpliceCallInto(CallResult.second, OutChain); 3673 return CallResult.first; 3674} 3675 3676 3677 3678/// ExpandOp - Expand the specified SDOperand into its two component pieces 3679/// Lo&Hi. Note that the Op MUST be an expanded type. As a result of this, the 3680/// LegalizeNodes map is filled in for any results that are not expanded, the 3681/// ExpandedNodes map is filled in for any results that are expanded, and the 3682/// Lo/Hi values are returned. 3683void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ 3684 MVT::ValueType VT = Op.getValueType(); 3685 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 3686 SDNode *Node = Op.Val; 3687 assert(getTypeAction(VT) == Expand && "Not an expanded type!"); 3688 assert((MVT::isInteger(VT) || VT == MVT::Vector) && 3689 "Cannot expand FP values!"); 3690 assert(((MVT::isInteger(NVT) && NVT < VT) || VT == MVT::Vector) && 3691 "Cannot expand to FP value or to larger int value!"); 3692 3693 // See if we already expanded it. 3694 std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I 3695 = ExpandedNodes.find(Op); 3696 if (I != ExpandedNodes.end()) { 3697 Lo = I->second.first; 3698 Hi = I->second.second; 3699 return; 3700 } 3701 3702 // Expanding to multiple registers needs to perform an optimization step, and 3703 // is not careful to avoid operations the target does not support. Make sure 3704 // that all generated operations are legalized in the next iteration. 3705 NeedsAnotherIteration = true; 3706 3707 switch (Node->getOpcode()) { 3708 case ISD::CopyFromReg: 3709 assert(0 && "CopyFromReg must be legal!"); 3710 default: 3711 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 3712 assert(0 && "Do not know how to expand this operator!"); 3713 abort(); 3714 case ISD::UNDEF: 3715 Lo = DAG.getNode(ISD::UNDEF, NVT); 3716 Hi = DAG.getNode(ISD::UNDEF, NVT); 3717 break; 3718 case ISD::Constant: { 3719 uint64_t Cst = cast<ConstantSDNode>(Node)->getValue(); 3720 Lo = DAG.getConstant(Cst, NVT); 3721 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT); 3722 break; 3723 } 3724 case ISD::ConstantVec: { 3725 unsigned NumElements = Node->getNumOperands(); 3726 // If we only have two elements left in the constant vector, just break it 3727 // apart into the two scalar constants it contains. Otherwise, bisect the 3728 // ConstantVec, and return each half as a new ConstantVec. 3729 // FIXME: this is hard coded as big endian, it may have to change to support 3730 // SSE and Alpha MVI 3731 if (NumElements == 2) { 3732 Hi = Node->getOperand(0); 3733 Lo = Node->getOperand(1); 3734 } else { 3735 NumElements /= 2; 3736 std::vector<SDOperand> LoOps, HiOps; 3737 for (unsigned I = 0, E = NumElements; I < E; ++I) { 3738 HiOps.push_back(Node->getOperand(I)); 3739 LoOps.push_back(Node->getOperand(I+NumElements)); 3740 } 3741 Lo = DAG.getNode(ISD::ConstantVec, MVT::Vector, LoOps); 3742 Hi = DAG.getNode(ISD::ConstantVec, MVT::Vector, HiOps); 3743 } 3744 break; 3745 } 3746 3747 case ISD::BUILD_PAIR: 3748 // Legalize both operands. FIXME: in the future we should handle the case 3749 // where the two elements are not legal. 3750 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!"); 3751 Lo = LegalizeOp(Node->getOperand(0)); 3752 Hi = LegalizeOp(Node->getOperand(1)); 3753 break; 3754 3755 case ISD::SIGN_EXTEND_INREG: 3756 ExpandOp(Node->getOperand(0), Lo, Hi); 3757 // Sign extend the lo-part. 3758 Hi = DAG.getNode(ISD::SRA, NVT, Lo, 3759 DAG.getConstant(MVT::getSizeInBits(NVT)-1, 3760 TLI.getShiftAmountTy())); 3761 // sext_inreg the low part if needed. 3762 Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Lo, Node->getOperand(1)); 3763 break; 3764 3765 case ISD::BSWAP: { 3766 ExpandOp(Node->getOperand(0), Lo, Hi); 3767 SDOperand TempLo = DAG.getNode(ISD::BSWAP, NVT, Hi); 3768 Hi = DAG.getNode(ISD::BSWAP, NVT, Lo); 3769 Lo = TempLo; 3770 break; 3771 } 3772 3773 case ISD::CTPOP: 3774 ExpandOp(Node->getOperand(0), Lo, Hi); 3775 Lo = DAG.getNode(ISD::ADD, NVT, // ctpop(HL) -> ctpop(H)+ctpop(L) 3776 DAG.getNode(ISD::CTPOP, NVT, Lo), 3777 DAG.getNode(ISD::CTPOP, NVT, Hi)); 3778 Hi = DAG.getConstant(0, NVT); 3779 break; 3780 3781 case ISD::CTLZ: { 3782 // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32) 3783 ExpandOp(Node->getOperand(0), Lo, Hi); 3784 SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT); 3785 SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi); 3786 SDOperand TopNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), HLZ, BitsC, 3787 ISD::SETNE); 3788 SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo); 3789 LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC); 3790 3791 Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart); 3792 Hi = DAG.getConstant(0, NVT); 3793 break; 3794 } 3795 3796 case ISD::CTTZ: { 3797 // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32) 3798 ExpandOp(Node->getOperand(0), Lo, Hi); 3799 SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT); 3800 SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo); 3801 SDOperand BotNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), LTZ, BitsC, 3802 ISD::SETNE); 3803 SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi); 3804 HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC); 3805 3806 Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart); 3807 Hi = DAG.getConstant(0, NVT); 3808 break; 3809 } 3810 3811 case ISD::LOAD: { 3812 SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 3813 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 3814 Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2)); 3815 3816 // Increment the pointer to the other half. 3817 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 3818 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 3819 getIntPtrConstant(IncrementSize)); 3820 //Is this safe? declaring that the two parts of the split load 3821 //are from the same instruction? 3822 Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2)); 3823 3824 // Build a factor node to remember that this load is independent of the 3825 // other one. 3826 SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), 3827 Hi.getValue(1)); 3828 3829 // Remember that we legalized the chain. 3830 AddLegalizedOperand(Op.getValue(1), TF); 3831 if (!TLI.isLittleEndian()) 3832 std::swap(Lo, Hi); 3833 break; 3834 } 3835 case ISD::VLOAD: { 3836 SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 3837 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 3838 unsigned NumElements =cast<ConstantSDNode>(Node->getOperand(2))->getValue(); 3839 MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT(); 3840 3841 // If we only have two elements, turn into a pair of scalar loads. 3842 // FIXME: handle case where a vector of two elements is fine, such as 3843 // 2 x double on SSE2. 3844 if (NumElements == 2) { 3845 Lo = DAG.getLoad(EVT, Ch, Ptr, Node->getOperand(4)); 3846 // Increment the pointer to the other half. 3847 unsigned IncrementSize = MVT::getSizeInBits(EVT)/8; 3848 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 3849 getIntPtrConstant(IncrementSize)); 3850 //Is this safe? declaring that the two parts of the split load 3851 //are from the same instruction? 3852 Hi = DAG.getLoad(EVT, Ch, Ptr, Node->getOperand(4)); 3853 } else { 3854 NumElements /= 2; // Split the vector in half 3855 Lo = DAG.getVecLoad(NumElements, EVT, Ch, Ptr, Node->getOperand(4)); 3856 unsigned IncrementSize = NumElements * MVT::getSizeInBits(EVT)/8; 3857 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 3858 getIntPtrConstant(IncrementSize)); 3859 //Is this safe? declaring that the two parts of the split load 3860 //are from the same instruction? 3861 Hi = DAG.getVecLoad(NumElements, EVT, Ch, Ptr, Node->getOperand(4)); 3862 } 3863 3864 // Build a factor node to remember that this load is independent of the 3865 // other one. 3866 SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), 3867 Hi.getValue(1)); 3868 3869 // Remember that we legalized the chain. 3870 AddLegalizedOperand(Op.getValue(1), TF); 3871 if (!TLI.isLittleEndian()) 3872 std::swap(Lo, Hi); 3873 break; 3874 } 3875 case ISD::VADD: 3876 case ISD::VSUB: 3877 case ISD::VMUL: { 3878 unsigned NumElements =cast<ConstantSDNode>(Node->getOperand(2))->getValue(); 3879 MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT(); 3880 SDOperand LL, LH, RL, RH; 3881 3882 ExpandOp(Node->getOperand(0), LL, LH); 3883 ExpandOp(Node->getOperand(1), RL, RH); 3884 3885 // If we only have two elements, turn into a pair of scalar loads. 3886 // FIXME: handle case where a vector of two elements is fine, such as 3887 // 2 x double on SSE2. 3888 if (NumElements == 2) { 3889 unsigned Opc = getScalarizedOpcode(Node->getOpcode(), EVT); 3890 Lo = DAG.getNode(Opc, EVT, LL, RL); 3891 Hi = DAG.getNode(Opc, EVT, LH, RH); 3892 } else { 3893 Lo = DAG.getNode(Node->getOpcode(), MVT::Vector, LL, RL, LL.getOperand(2), 3894 LL.getOperand(3)); 3895 Hi = DAG.getNode(Node->getOpcode(), MVT::Vector, LH, RH, LH.getOperand(2), 3896 LH.getOperand(3)); 3897 } 3898 break; 3899 } 3900 case ISD::TAILCALL: 3901 case ISD::CALL: { 3902 SDOperand Chain = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 3903 SDOperand Callee = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 3904 3905 bool Changed = false; 3906 std::vector<SDOperand> Ops; 3907 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) { 3908 Ops.push_back(LegalizeOp(Node->getOperand(i))); 3909 Changed |= Ops.back() != Node->getOperand(i); 3910 } 3911 3912 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 3913 "Can only expand a call once so far, not i64 -> i16!"); 3914 3915 std::vector<MVT::ValueType> RetTyVTs; 3916 RetTyVTs.reserve(3); 3917 RetTyVTs.push_back(NVT); 3918 RetTyVTs.push_back(NVT); 3919 RetTyVTs.push_back(MVT::Other); 3920 SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops, 3921 Node->getOpcode() == ISD::TAILCALL); 3922 Lo = SDOperand(NC, 0); 3923 Hi = SDOperand(NC, 1); 3924 3925 // Insert the new chain mapping. 3926 AddLegalizedOperand(Op.getValue(1), Hi.getValue(2)); 3927 break; 3928 } 3929 case ISD::AND: 3930 case ISD::OR: 3931 case ISD::XOR: { // Simple logical operators -> two trivial pieces. 3932 SDOperand LL, LH, RL, RH; 3933 ExpandOp(Node->getOperand(0), LL, LH); 3934 ExpandOp(Node->getOperand(1), RL, RH); 3935 Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL); 3936 Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH); 3937 break; 3938 } 3939 case ISD::SELECT: { 3940 SDOperand C, LL, LH, RL, RH; 3941 3942 switch (getTypeAction(Node->getOperand(0).getValueType())) { 3943 case Expand: assert(0 && "It's impossible to expand bools"); 3944 case Legal: 3945 C = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 3946 break; 3947 case Promote: 3948 C = PromoteOp(Node->getOperand(0)); // Promote the condition. 3949 break; 3950 } 3951 ExpandOp(Node->getOperand(1), LL, LH); 3952 ExpandOp(Node->getOperand(2), RL, RH); 3953 Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL); 3954 Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH); 3955 break; 3956 } 3957 case ISD::SELECT_CC: { 3958 SDOperand TL, TH, FL, FH; 3959 ExpandOp(Node->getOperand(2), TL, TH); 3960 ExpandOp(Node->getOperand(3), FL, FH); 3961 Lo = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0), 3962 Node->getOperand(1), TL, FL, Node->getOperand(4)); 3963 Hi = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0), 3964 Node->getOperand(1), TH, FH, Node->getOperand(4)); 3965 Lo = LegalizeOp(Lo); 3966 Hi = LegalizeOp(Hi); 3967 break; 3968 } 3969 case ISD::SEXTLOAD: { 3970 SDOperand Chain = LegalizeOp(Node->getOperand(0)); 3971 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); 3972 MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT(); 3973 3974 if (EVT == NVT) 3975 Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2)); 3976 else 3977 Lo = DAG.getExtLoad(ISD::SEXTLOAD, NVT, Chain, Ptr, Node->getOperand(2), 3978 EVT); 3979 3980 // Remember that we legalized the chain. 3981 AddLegalizedOperand(SDOperand(Node, 1), Lo.getValue(1)); 3982 3983 // The high part is obtained by SRA'ing all but one of the bits of the lo 3984 // part. 3985 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); 3986 Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, 3987 TLI.getShiftAmountTy())); 3988 Lo = LegalizeOp(Lo); 3989 Hi = LegalizeOp(Hi); 3990 break; 3991 } 3992 case ISD::ZEXTLOAD: { 3993 SDOperand Chain = LegalizeOp(Node->getOperand(0)); 3994 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); 3995 MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT(); 3996 3997 if (EVT == NVT) 3998 Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2)); 3999 else 4000 Lo = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Chain, Ptr, Node->getOperand(2), 4001 EVT); 4002 4003 // Remember that we legalized the chain. 4004 AddLegalizedOperand(SDOperand(Node, 1), Lo.getValue(1)); 4005 4006 // The high part is just a zero. 4007 Hi = LegalizeOp(DAG.getConstant(0, NVT)); 4008 Lo = LegalizeOp(Lo); 4009 break; 4010 } 4011 case ISD::EXTLOAD: { 4012 SDOperand Chain = LegalizeOp(Node->getOperand(0)); 4013 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); 4014 MVT::ValueType EVT = cast<VTSDNode>(Node->getOperand(3))->getVT(); 4015 4016 if (EVT == NVT) 4017 Lo = DAG.getLoad(NVT, Chain, Ptr, Node->getOperand(2)); 4018 else 4019 Lo = DAG.getExtLoad(ISD::EXTLOAD, NVT, Chain, Ptr, Node->getOperand(2), 4020 EVT); 4021 4022 // Remember that we legalized the chain. 4023 AddLegalizedOperand(SDOperand(Node, 1), Lo.getValue(1)); 4024 4025 // The high part is undefined. 4026 Hi = LegalizeOp(DAG.getNode(ISD::UNDEF, NVT)); 4027 Lo = LegalizeOp(Lo); 4028 break; 4029 } 4030 case ISD::ANY_EXTEND: { 4031 SDOperand In; 4032 switch (getTypeAction(Node->getOperand(0).getValueType())) { 4033 case Expand: assert(0 && "expand-expand not implemented yet!"); 4034 case Legal: In = LegalizeOp(Node->getOperand(0)); break; 4035 case Promote: 4036 In = PromoteOp(Node->getOperand(0)); 4037 break; 4038 } 4039 4040 // The low part is any extension of the input (which degenerates to a copy). 4041 Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, In); 4042 // The high part is undefined. 4043 Hi = DAG.getNode(ISD::UNDEF, NVT); 4044 break; 4045 } 4046 case ISD::SIGN_EXTEND: { 4047 SDOperand In; 4048 switch (getTypeAction(Node->getOperand(0).getValueType())) { 4049 case Expand: assert(0 && "expand-expand not implemented yet!"); 4050 case Legal: In = LegalizeOp(Node->getOperand(0)); break; 4051 case Promote: 4052 In = PromoteOp(Node->getOperand(0)); 4053 // Emit the appropriate sign_extend_inreg to get the value we want. 4054 In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(), In, 4055 DAG.getValueType(Node->getOperand(0).getValueType())); 4056 break; 4057 } 4058 4059 // The low part is just a sign extension of the input (which degenerates to 4060 // a copy). 4061 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, In); 4062 4063 // The high part is obtained by SRA'ing all but one of the bits of the lo 4064 // part. 4065 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); 4066 Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, 4067 TLI.getShiftAmountTy())); 4068 break; 4069 } 4070 case ISD::ZERO_EXTEND: { 4071 SDOperand In; 4072 switch (getTypeAction(Node->getOperand(0).getValueType())) { 4073 case Expand: assert(0 && "expand-expand not implemented yet!"); 4074 case Legal: In = LegalizeOp(Node->getOperand(0)); break; 4075 case Promote: 4076 In = PromoteOp(Node->getOperand(0)); 4077 // Emit the appropriate zero_extend_inreg to get the value we want. 4078 In = DAG.getZeroExtendInReg(In, Node->getOperand(0).getValueType()); 4079 break; 4080 } 4081 4082 // The low part is just a zero extension of the input (which degenerates to 4083 // a copy). 4084 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, In); 4085 4086 // The high part is just a zero. 4087 Hi = DAG.getConstant(0, NVT); 4088 break; 4089 } 4090 4091 case ISD::BIT_CONVERT: { 4092 SDOperand Tmp = ExpandBIT_CONVERT(Node->getValueType(0), 4093 Node->getOperand(0)); 4094 ExpandOp(Tmp, Lo, Hi); 4095 break; 4096 } 4097 4098 case ISD::READCYCLECOUNTER: { 4099 assert(TLI.getOperationAction(ISD::READCYCLECOUNTER, VT) == 4100 TargetLowering::Custom && 4101 "Must custom expand ReadCycleCounter"); 4102 SDOperand T = TLI.LowerOperation(Op, DAG); 4103 assert(T.Val && "Node must be custom expanded!"); 4104 Lo = LegalizeOp(T.getValue(0)); 4105 Hi = LegalizeOp(T.getValue(1)); 4106 AddLegalizedOperand(SDOperand(Node, 1), // Remember we legalized the chain. 4107 LegalizeOp(T.getValue(2))); 4108 break; 4109 } 4110 4111 // These operators cannot be expanded directly, emit them as calls to 4112 // library functions. 4113 case ISD::FP_TO_SINT: 4114 if (TLI.getOperationAction(ISD::FP_TO_SINT, VT) == TargetLowering::Custom) { 4115 SDOperand Op; 4116 switch (getTypeAction(Node->getOperand(0).getValueType())) { 4117 case Expand: assert(0 && "cannot expand FP!"); 4118 case Legal: Op = LegalizeOp(Node->getOperand(0)); break; 4119 case Promote: Op = PromoteOp(Node->getOperand(0)); break; 4120 } 4121 4122 Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_SINT, VT, Op), DAG); 4123 4124 // Now that the custom expander is done, expand the result, which is still 4125 // VT. 4126 if (Op.Val) { 4127 ExpandOp(Op, Lo, Hi); 4128 break; 4129 } 4130 } 4131 4132 if (Node->getOperand(0).getValueType() == MVT::f32) 4133 Lo = ExpandLibCall("__fixsfdi", Node, Hi); 4134 else 4135 Lo = ExpandLibCall("__fixdfdi", Node, Hi); 4136 break; 4137 4138 case ISD::FP_TO_UINT: 4139 if (TLI.getOperationAction(ISD::FP_TO_UINT, VT) == TargetLowering::Custom) { 4140 SDOperand Op = DAG.getNode(ISD::FP_TO_UINT, VT, 4141 LegalizeOp(Node->getOperand(0))); 4142 // Now that the custom expander is done, expand the result, which is still 4143 // VT. 4144 Op = TLI.LowerOperation(Op, DAG); 4145 if (Op.Val) { 4146 ExpandOp(Op, Lo, Hi); 4147 break; 4148 } 4149 } 4150 4151 if (Node->getOperand(0).getValueType() == MVT::f32) 4152 Lo = ExpandLibCall("__fixunssfdi", Node, Hi); 4153 else 4154 Lo = ExpandLibCall("__fixunsdfdi", Node, Hi); 4155 break; 4156 4157 case ISD::SHL: { 4158 // If the target wants custom lowering, do so. 4159 if (TLI.getOperationAction(ISD::SHL, VT) == TargetLowering::Custom) { 4160 SDOperand Op = DAG.getNode(ISD::SHL, VT, Node->getOperand(0), 4161 LegalizeOp(Node->getOperand(1))); 4162 Op = TLI.LowerOperation(Op, DAG); 4163 if (Op.Val) { 4164 // Now that the custom expander is done, expand the result, which is 4165 // still VT. 4166 ExpandOp(Op, Lo, Hi); 4167 break; 4168 } 4169 } 4170 4171 // If we can emit an efficient shift operation, do so now. 4172 if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 4173 break; 4174 4175 // If this target supports SHL_PARTS, use it. 4176 TargetLowering::LegalizeAction Action = 4177 TLI.getOperationAction(ISD::SHL_PARTS, NVT); 4178 if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) || 4179 Action == TargetLowering::Custom) { 4180 ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), Node->getOperand(1), 4181 Lo, Hi); 4182 break; 4183 } 4184 4185 // Otherwise, emit a libcall. 4186 Lo = ExpandLibCall("__ashldi3", Node, Hi); 4187 break; 4188 } 4189 4190 case ISD::SRA: { 4191 // If the target wants custom lowering, do so. 4192 if (TLI.getOperationAction(ISD::SRA, VT) == TargetLowering::Custom) { 4193 SDOperand Op = DAG.getNode(ISD::SRA, VT, Node->getOperand(0), 4194 LegalizeOp(Node->getOperand(1))); 4195 Op = TLI.LowerOperation(Op, DAG); 4196 if (Op.Val) { 4197 // Now that the custom expander is done, expand the result, which is 4198 // still VT. 4199 ExpandOp(Op, Lo, Hi); 4200 break; 4201 } 4202 } 4203 4204 // If we can emit an efficient shift operation, do so now. 4205 if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 4206 break; 4207 4208 // If this target supports SRA_PARTS, use it. 4209 TargetLowering::LegalizeAction Action = 4210 TLI.getOperationAction(ISD::SRA_PARTS, NVT); 4211 if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) || 4212 Action == TargetLowering::Custom) { 4213 ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), Node->getOperand(1), 4214 Lo, Hi); 4215 break; 4216 } 4217 4218 // Otherwise, emit a libcall. 4219 Lo = ExpandLibCall("__ashrdi3", Node, Hi); 4220 break; 4221 } 4222 4223 case ISD::SRL: { 4224 // If the target wants custom lowering, do so. 4225 if (TLI.getOperationAction(ISD::SRL, VT) == TargetLowering::Custom) { 4226 SDOperand Op = DAG.getNode(ISD::SRL, VT, Node->getOperand(0), 4227 LegalizeOp(Node->getOperand(1))); 4228 Op = TLI.LowerOperation(Op, DAG); 4229 if (Op.Val) { 4230 // Now that the custom expander is done, expand the result, which is 4231 // still VT. 4232 ExpandOp(Op, Lo, Hi); 4233 break; 4234 } 4235 } 4236 4237 // If we can emit an efficient shift operation, do so now. 4238 if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 4239 break; 4240 4241 // If this target supports SRL_PARTS, use it. 4242 TargetLowering::LegalizeAction Action = 4243 TLI.getOperationAction(ISD::SRL_PARTS, NVT); 4244 if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) || 4245 Action == TargetLowering::Custom) { 4246 ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), Node->getOperand(1), 4247 Lo, Hi); 4248 break; 4249 } 4250 4251 // Otherwise, emit a libcall. 4252 Lo = ExpandLibCall("__lshrdi3", Node, Hi); 4253 break; 4254 } 4255 4256 case ISD::ADD: 4257 ExpandByParts(ISD::ADD_PARTS, Node->getOperand(0), Node->getOperand(1), 4258 Lo, Hi); 4259 break; 4260 case ISD::SUB: 4261 ExpandByParts(ISD::SUB_PARTS, Node->getOperand(0), Node->getOperand(1), 4262 Lo, Hi); 4263 break; 4264 case ISD::MUL: { 4265 if (TLI.isOperationLegal(ISD::MULHU, NVT)) { 4266 SDOperand LL, LH, RL, RH; 4267 ExpandOp(Node->getOperand(0), LL, LH); 4268 ExpandOp(Node->getOperand(1), RL, RH); 4269 unsigned SH = MVT::getSizeInBits(RH.getValueType())-1; 4270 // MULHS implicitly sign extends its inputs. Check to see if ExpandOp 4271 // extended the sign bit of the low half through the upper half, and if so 4272 // emit a MULHS instead of the alternate sequence that is valid for any 4273 // i64 x i64 multiply. 4274 if (TLI.isOperationLegal(ISD::MULHS, NVT) && 4275 // is RH an extension of the sign bit of RL? 4276 RH.getOpcode() == ISD::SRA && RH.getOperand(0) == RL && 4277 RH.getOperand(1).getOpcode() == ISD::Constant && 4278 cast<ConstantSDNode>(RH.getOperand(1))->getValue() == SH && 4279 // is LH an extension of the sign bit of LL? 4280 LH.getOpcode() == ISD::SRA && LH.getOperand(0) == LL && 4281 LH.getOperand(1).getOpcode() == ISD::Constant && 4282 cast<ConstantSDNode>(LH.getOperand(1))->getValue() == SH) { 4283 Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL); 4284 } else { 4285 Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL); 4286 RH = DAG.getNode(ISD::MUL, NVT, LL, RH); 4287 LH = DAG.getNode(ISD::MUL, NVT, LH, RL); 4288 Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH); 4289 Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH); 4290 } 4291 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL); 4292 } else { 4293 Lo = ExpandLibCall("__muldi3" , Node, Hi); break; 4294 } 4295 break; 4296 } 4297 case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break; 4298 case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break; 4299 case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break; 4300 case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break; 4301 } 4302 4303 // Make sure the resultant values have been legalized themselves, unless this 4304 // is a type that requires multi-step expansion. 4305 if (getTypeAction(NVT) != Expand && NVT != MVT::isVoid) { 4306 Lo = LegalizeOp(Lo); 4307 Hi = LegalizeOp(Hi); 4308 } 4309 4310 // Remember in a map if the values will be reused later. 4311 bool isNew = 4312 ExpandedNodes.insert(std::make_pair(Op, std::make_pair(Lo, Hi))).second; 4313 assert(isNew && "Value already expanded?!?"); 4314} 4315 4316 4317// SelectionDAG::Legalize - This is the entry point for the file. 4318// 4319void SelectionDAG::Legalize() { 4320 /// run - This is the main entry point to this class. 4321 /// 4322 SelectionDAGLegalize(*this).Run(); 4323} 4324 4325