LegalizeDAG.cpp revision e89083a9300dc463e3b79eabe2b9913d85338d28
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/MachineConstantPool.h" 16#include "llvm/CodeGen/MachineFunction.h" 17#include "llvm/CodeGen/MachineFrameInfo.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> 24using namespace llvm; 25 26//===----------------------------------------------------------------------===// 27/// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and 28/// hacks on it until the target machine can handle it. This involves 29/// eliminating value sizes the machine cannot handle (promoting small sizes to 30/// large sizes or splitting up large values into small values) as well as 31/// eliminating operations the machine cannot handle. 32/// 33/// This code also does a small amount of optimization and recognition of idioms 34/// as part of its processing. For example, if a target does not support a 35/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this 36/// will attempt merge setcc and brc instructions into brcc's. 37/// 38namespace { 39class SelectionDAGLegalize { 40 TargetLowering &TLI; 41 SelectionDAG &DAG; 42 43 /// LegalizeAction - This enum indicates what action we should take for each 44 /// value type the can occur in the program. 45 enum LegalizeAction { 46 Legal, // The target natively supports this value type. 47 Promote, // This should be promoted to the next larger type. 48 Expand, // This integer type should be broken into smaller pieces. 49 }; 50 51 /// ValueTypeActions - This is a bitvector that contains two bits for each 52 /// value type, where the two bits correspond to the LegalizeAction enum. 53 /// This can be queried with "getTypeAction(VT)". 54 unsigned ValueTypeActions; 55 56 /// NeedsAnotherIteration - This is set when we expand a large integer 57 /// operation into smaller integer operations, but the smaller operations are 58 /// not set. This occurs only rarely in practice, for targets that don't have 59 /// 32-bit or larger integer registers. 60 bool NeedsAnotherIteration; 61 62 /// LegalizedNodes - For nodes that are of legal width, and that have more 63 /// than one use, this map indicates what regularized operand to use. This 64 /// allows us to avoid legalizing the same thing more than once. 65 std::map<SDOperand, SDOperand> LegalizedNodes; 66 67 /// PromotedNodes - For nodes that are below legal width, and that have more 68 /// than one use, this map indicates what promoted value to use. This allows 69 /// us to avoid promoting the same thing more than once. 70 std::map<SDOperand, SDOperand> PromotedNodes; 71 72 /// ExpandedNodes - For nodes that need to be expanded, and which have more 73 /// than one use, this map indicates which which operands are the expanded 74 /// version of the input. This allows us to avoid expanding the same node 75 /// more than once. 76 std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes; 77 78 void AddLegalizedOperand(SDOperand From, SDOperand To) { 79 bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second; 80 assert(isNew && "Got into the map somehow?"); 81 } 82 void AddPromotedOperand(SDOperand From, SDOperand To) { 83 bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second; 84 assert(isNew && "Got into the map somehow?"); 85 } 86 87public: 88 89 SelectionDAGLegalize(SelectionDAG &DAG); 90 91 /// Run - While there is still lowering to do, perform a pass over the DAG. 92 /// Most regularization can be done in a single pass, but targets that require 93 /// large values to be split into registers multiple times (e.g. i64 -> 4x 94 /// i16) require iteration for these values (the first iteration will demote 95 /// to i32, the second will demote to i16). 96 void Run() { 97 do { 98 NeedsAnotherIteration = false; 99 LegalizeDAG(); 100 } while (NeedsAnotherIteration); 101 } 102 103 /// getTypeAction - Return how we should legalize values of this type, either 104 /// it is already legal or we need to expand it into multiple registers of 105 /// smaller integer type, or we need to promote it to a larger type. 106 LegalizeAction getTypeAction(MVT::ValueType VT) const { 107 return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3); 108 } 109 110 /// isTypeLegal - Return true if this type is legal on this target. 111 /// 112 bool isTypeLegal(MVT::ValueType VT) const { 113 return getTypeAction(VT) == Legal; 114 } 115 116private: 117 void LegalizeDAG(); 118 119 SDOperand LegalizeOp(SDOperand O); 120 void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi); 121 SDOperand PromoteOp(SDOperand O); 122 123 SDOperand ExpandLibCall(const char *Name, SDNode *Node, 124 SDOperand &Hi); 125 SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, 126 SDOperand Source); 127 bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt, 128 SDOperand &Lo, SDOperand &Hi); 129 void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt, 130 SDOperand &Lo, SDOperand &Hi); 131 void ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS, 132 SDOperand &Lo, SDOperand &Hi); 133 134 void SpliceCallInto(const SDOperand &CallResult, SDNode *OutChain); 135 136 SDOperand getIntPtrConstant(uint64_t Val) { 137 return DAG.getConstant(Val, TLI.getPointerTy()); 138 } 139}; 140} 141 142 143SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag) 144 : TLI(dag.getTargetLoweringInfo()), DAG(dag), 145 ValueTypeActions(TLI.getValueTypeActions()) { 146 assert(MVT::LAST_VALUETYPE <= 16 && 147 "Too many value types for ValueTypeActions to hold!"); 148} 149 150void SelectionDAGLegalize::LegalizeDAG() { 151 SDOperand OldRoot = DAG.getRoot(); 152 SDOperand NewRoot = LegalizeOp(OldRoot); 153 DAG.setRoot(NewRoot); 154 155 ExpandedNodes.clear(); 156 LegalizedNodes.clear(); 157 PromotedNodes.clear(); 158 159 // Remove dead nodes now. 160 DAG.RemoveDeadNodes(OldRoot.Val); 161} 162 163SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { 164 assert(getTypeAction(Op.getValueType()) == Legal && 165 "Caller should expand or promote operands that are not legal!"); 166 SDNode *Node = Op.Val; 167 168 // If this operation defines any values that cannot be represented in a 169 // register on this target, make sure to expand or promote them. 170 if (Node->getNumValues() > 1) { 171 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 172 switch (getTypeAction(Node->getValueType(i))) { 173 case Legal: break; // Nothing to do. 174 case Expand: { 175 SDOperand T1, T2; 176 ExpandOp(Op.getValue(i), T1, T2); 177 assert(LegalizedNodes.count(Op) && 178 "Expansion didn't add legal operands!"); 179 return LegalizedNodes[Op]; 180 } 181 case Promote: 182 PromoteOp(Op.getValue(i)); 183 assert(LegalizedNodes.count(Op) && 184 "Expansion didn't add legal operands!"); 185 return LegalizedNodes[Op]; 186 } 187 } 188 189 // Note that LegalizeOp may be reentered even from single-use nodes, which 190 // means that we always must cache transformed nodes. 191 std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op); 192 if (I != LegalizedNodes.end()) return I->second; 193 194 SDOperand Tmp1, Tmp2, Tmp3; 195 196 SDOperand Result = Op; 197 198 switch (Node->getOpcode()) { 199 default: 200 if (Node->getOpcode() >= ISD::BUILTIN_OP_END) { 201 // If this is a target node, legalize it by legalizing the operands then 202 // passing it through. 203 std::vector<SDOperand> Ops; 204 bool Changed = false; 205 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 206 Ops.push_back(LegalizeOp(Node->getOperand(i))); 207 Changed = Changed || Node->getOperand(i) != Ops.back(); 208 } 209 if (Changed) 210 if (Node->getNumValues() == 1) 211 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops); 212 else { 213 std::vector<MVT::ValueType> VTs(Node->value_begin(), 214 Node->value_end()); 215 Result = DAG.getNode(Node->getOpcode(), VTs, Ops); 216 } 217 218 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 219 AddLegalizedOperand(Op.getValue(i), Result.getValue(i)); 220 return Result.getValue(Op.ResNo); 221 } 222 // Otherwise this is an unhandled builtin node. splat. 223 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 224 assert(0 && "Do not know how to legalize this operator!"); 225 abort(); 226 case ISD::EntryToken: 227 case ISD::FrameIndex: 228 case ISD::GlobalAddress: 229 case ISD::ExternalSymbol: 230 case ISD::ConstantPool: // Nothing to do. 231 assert(getTypeAction(Node->getValueType(0)) == Legal && 232 "This must be legal!"); 233 break; 234 case ISD::CopyFromReg: 235 Tmp1 = LegalizeOp(Node->getOperand(0)); 236 if (Tmp1 != Node->getOperand(0)) 237 Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), 238 Node->getValueType(0), Tmp1); 239 else 240 Result = Op.getValue(0); 241 242 // Since CopyFromReg produces two values, make sure to remember that we 243 // legalized both of them. 244 AddLegalizedOperand(Op.getValue(0), Result); 245 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 246 return Result.getValue(Op.ResNo); 247 case ISD::ImplicitDef: 248 Tmp1 = LegalizeOp(Node->getOperand(0)); 249 if (Tmp1 != Node->getOperand(0)) 250 Result = DAG.getImplicitDef(Tmp1, cast<RegSDNode>(Node)->getReg()); 251 break; 252 case ISD::UNDEF: { 253 MVT::ValueType VT = Op.getValueType(); 254 switch (TLI.getOperationAction(ISD::UNDEF, VT)) { 255 default: assert(0 && "This action is not supported yet!"); 256 case TargetLowering::Expand: 257 case TargetLowering::Promote: 258 if (MVT::isInteger(VT)) 259 Result = DAG.getConstant(0, VT); 260 else if (MVT::isFloatingPoint(VT)) 261 Result = DAG.getConstantFP(0, VT); 262 else 263 assert(0 && "Unknown value type!"); 264 break; 265 case TargetLowering::Legal: 266 break; 267 } 268 break; 269 } 270 case ISD::Constant: 271 // We know we don't need to expand constants here, constants only have one 272 // value and we check that it is fine above. 273 274 // FIXME: Maybe we should handle things like targets that don't support full 275 // 32-bit immediates? 276 break; 277 case ISD::ConstantFP: { 278 // Spill FP immediates to the constant pool if the target cannot directly 279 // codegen them. Targets often have some immediate values that can be 280 // efficiently generated into an FP register without a load. We explicitly 281 // leave these constants as ConstantFP nodes for the target to deal with. 282 283 ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node); 284 285 // Check to see if this FP immediate is already legal. 286 bool isLegal = false; 287 for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(), 288 E = TLI.legal_fpimm_end(); I != E; ++I) 289 if (CFP->isExactlyValue(*I)) { 290 isLegal = true; 291 break; 292 } 293 294 if (!isLegal) { 295 // Otherwise we need to spill the constant to memory. 296 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); 297 298 bool Extend = false; 299 300 // If a FP immediate is precise when represented as a float, we put it 301 // into the constant pool as a float, even if it's is statically typed 302 // as a double. 303 MVT::ValueType VT = CFP->getValueType(0); 304 bool isDouble = VT == MVT::f64; 305 ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy : 306 Type::FloatTy, CFP->getValue()); 307 if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) && 308 // Only do this if the target has a native EXTLOAD instruction from 309 // f32. 310 TLI.getOperationAction(ISD::EXTLOAD, 311 MVT::f32) == TargetLowering::Legal) { 312 LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy)); 313 VT = MVT::f32; 314 Extend = true; 315 } 316 317 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC), 318 TLI.getPointerTy()); 319 if (Extend) { 320 Result = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), CPIdx, 321 DAG.getSrcValue(NULL), MVT::f32); 322 } else { 323 Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx, 324 DAG.getSrcValue(NULL)); 325 } 326 } 327 break; 328 } 329 case ISD::TokenFactor: { 330 std::vector<SDOperand> Ops; 331 bool Changed = false; 332 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 333 SDOperand Op = Node->getOperand(i); 334 // Fold single-use TokenFactor nodes into this token factor as we go. 335 // FIXME: This is something that the DAGCombiner should do!! 336 if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) { 337 Changed = true; 338 for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j) 339 Ops.push_back(LegalizeOp(Op.getOperand(j))); 340 } else { 341 Ops.push_back(LegalizeOp(Op)); // Legalize the operands 342 Changed |= Ops[i] != Op; 343 } 344 } 345 if (Changed) 346 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops); 347 break; 348 } 349 350 case ISD::CALLSEQ_START: 351 case ISD::CALLSEQ_END: 352 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 353 // Do not try to legalize the target-specific arguments (#1+) 354 Tmp2 = Node->getOperand(0); 355 if (Tmp1 != Tmp2) { 356 Node->setAdjCallChain(Tmp1); 357 358 // If moving the operand from pointing to Tmp2 dropped its use count to 1, 359 // this will cause the maps used to memoize results to get confused. 360 // Create and add a dummy use, just to increase its use count. This will 361 // be removed at the end of legalize when dead nodes are removed. 362 if (Tmp2.Val->hasOneUse()) 363 DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp2, 364 DAG.getConstant(0, MVT::i32)); 365 } 366 // Note that we do not create new CALLSEQ_DOWN/UP nodes here. These 367 // nodes are treated specially and are mutated in place. This makes the dag 368 // legalization process more efficient and also makes libcall insertion 369 // easier. 370 break; 371 case ISD::DYNAMIC_STACKALLOC: 372 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 373 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the size. 374 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the alignment. 375 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 376 Tmp3 != Node->getOperand(2)) 377 Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0), 378 Tmp1, Tmp2, Tmp3); 379 else 380 Result = Op.getValue(0); 381 382 // Since this op produces two values, make sure to remember that we 383 // legalized both of them. 384 AddLegalizedOperand(SDOperand(Node, 0), Result); 385 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 386 return Result.getValue(Op.ResNo); 387 388 case ISD::TAILCALL: 389 case ISD::CALL: { 390 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 391 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 392 393 bool Changed = false; 394 std::vector<SDOperand> Ops; 395 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) { 396 Ops.push_back(LegalizeOp(Node->getOperand(i))); 397 Changed |= Ops.back() != Node->getOperand(i); 398 } 399 400 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) { 401 std::vector<MVT::ValueType> RetTyVTs; 402 RetTyVTs.reserve(Node->getNumValues()); 403 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 404 RetTyVTs.push_back(Node->getValueType(i)); 405 Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops, 406 Node->getOpcode() == ISD::TAILCALL), 0); 407 } else { 408 Result = Result.getValue(0); 409 } 410 // Since calls produce multiple values, make sure to remember that we 411 // legalized all of them. 412 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 413 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 414 return Result.getValue(Op.ResNo); 415 } 416 case ISD::BR: 417 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 418 if (Tmp1 != Node->getOperand(0)) 419 Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1)); 420 break; 421 422 case ISD::BRCOND: 423 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 424 425 switch (getTypeAction(Node->getOperand(1).getValueType())) { 426 case Expand: assert(0 && "It's impossible to expand bools"); 427 case Legal: 428 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 429 break; 430 case Promote: 431 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition. 432 break; 433 } 434 // Basic block destination (Op#2) is always legal. 435 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 436 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 437 Node->getOperand(2)); 438 break; 439 case ISD::BRCONDTWOWAY: 440 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 441 switch (getTypeAction(Node->getOperand(1).getValueType())) { 442 case Expand: assert(0 && "It's impossible to expand bools"); 443 case Legal: 444 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 445 break; 446 case Promote: 447 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition. 448 break; 449 } 450 // If this target does not support BRCONDTWOWAY, lower it to a BRCOND/BR 451 // pair. 452 switch (TLI.getOperationAction(ISD::BRCONDTWOWAY, MVT::Other)) { 453 case TargetLowering::Promote: 454 default: assert(0 && "This action is not supported yet!"); 455 case TargetLowering::Legal: 456 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 457 std::vector<SDOperand> Ops; 458 Ops.push_back(Tmp1); 459 Ops.push_back(Tmp2); 460 Ops.push_back(Node->getOperand(2)); 461 Ops.push_back(Node->getOperand(3)); 462 Result = DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops); 463 } 464 break; 465 case TargetLowering::Expand: 466 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 467 Node->getOperand(2)); 468 Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(3)); 469 break; 470 } 471 break; 472 473 case ISD::LOAD: 474 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 475 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 476 477 if (Tmp1 != Node->getOperand(0) || 478 Tmp2 != Node->getOperand(1)) 479 Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2, 480 Node->getOperand(2)); 481 else 482 Result = SDOperand(Node, 0); 483 484 // Since loads produce two values, make sure to remember that we legalized 485 // both of them. 486 AddLegalizedOperand(SDOperand(Node, 0), Result); 487 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 488 return Result.getValue(Op.ResNo); 489 490 case ISD::EXTLOAD: 491 case ISD::SEXTLOAD: 492 case ISD::ZEXTLOAD: { 493 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 494 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 495 496 MVT::ValueType SrcVT = cast<MVTSDNode>(Node)->getExtraValueType(); 497 switch (TLI.getOperationAction(Node->getOpcode(), SrcVT)) { 498 default: assert(0 && "This action is not supported yet!"); 499 case TargetLowering::Promote: 500 assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!"); 501 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), 502 Tmp1, Tmp2, Node->getOperand(2), MVT::i8); 503 // Since loads produce two values, make sure to remember that we legalized 504 // both of them. 505 AddLegalizedOperand(SDOperand(Node, 0), Result); 506 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 507 return Result.getValue(Op.ResNo); 508 509 case TargetLowering::Legal: 510 if (Tmp1 != Node->getOperand(0) || 511 Tmp2 != Node->getOperand(1)) 512 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), 513 Tmp1, Tmp2, Node->getOperand(2), SrcVT); 514 else 515 Result = SDOperand(Node, 0); 516 517 // Since loads produce two values, make sure to remember that we legalized 518 // both of them. 519 AddLegalizedOperand(SDOperand(Node, 0), Result); 520 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 521 return Result.getValue(Op.ResNo); 522 case TargetLowering::Expand: 523 assert(Node->getOpcode() != ISD::EXTLOAD && 524 "EXTLOAD should always be supported!"); 525 // Turn the unsupported load into an EXTLOAD followed by an explicit 526 // zero/sign extend inreg. 527 Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0), 528 Tmp1, Tmp2, Node->getOperand(2), SrcVT); 529 SDOperand ValRes; 530 if (Node->getOpcode() == ISD::SEXTLOAD) 531 ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 532 Result, SrcVT); 533 else 534 ValRes = DAG.getZeroExtendInReg(Result, SrcVT); 535 AddLegalizedOperand(SDOperand(Node, 0), ValRes); 536 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 537 if (Op.ResNo) 538 return Result.getValue(1); 539 return ValRes; 540 } 541 assert(0 && "Unreachable"); 542 } 543 case ISD::EXTRACT_ELEMENT: 544 // Get both the low and high parts. 545 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 546 if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) 547 Result = Tmp2; // 1 -> Hi 548 else 549 Result = Tmp1; // 0 -> Lo 550 break; 551 552 case ISD::CopyToReg: 553 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 554 555 switch (getTypeAction(Node->getOperand(1).getValueType())) { 556 case Legal: 557 // Legalize the incoming value (must be legal). 558 Tmp2 = LegalizeOp(Node->getOperand(1)); 559 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 560 Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg()); 561 break; 562 case Promote: 563 Tmp2 = PromoteOp(Node->getOperand(1)); 564 Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg()); 565 break; 566 case Expand: 567 SDOperand Lo, Hi; 568 ExpandOp(Node->getOperand(1), Lo, Hi); 569 unsigned Reg = cast<RegSDNode>(Node)->getReg(); 570 Lo = DAG.getCopyToReg(Tmp1, Lo, Reg); 571 Hi = DAG.getCopyToReg(Tmp1, Hi, Reg+1); 572 // Note that the copytoreg nodes are independent of each other. 573 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); 574 assert(isTypeLegal(Result.getValueType()) && 575 "Cannot expand multiple times yet (i64 -> i16)"); 576 break; 577 } 578 break; 579 580 case ISD::RET: 581 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 582 switch (Node->getNumOperands()) { 583 case 2: // ret val 584 switch (getTypeAction(Node->getOperand(1).getValueType())) { 585 case Legal: 586 Tmp2 = LegalizeOp(Node->getOperand(1)); 587 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 588 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 589 break; 590 case Expand: { 591 SDOperand Lo, Hi; 592 ExpandOp(Node->getOperand(1), Lo, Hi); 593 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi); 594 break; 595 } 596 case Promote: 597 Tmp2 = PromoteOp(Node->getOperand(1)); 598 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 599 break; 600 } 601 break; 602 case 1: // ret void 603 if (Tmp1 != Node->getOperand(0)) 604 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1); 605 break; 606 default: { // ret <values> 607 std::vector<SDOperand> NewValues; 608 NewValues.push_back(Tmp1); 609 for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) 610 switch (getTypeAction(Node->getOperand(i).getValueType())) { 611 case Legal: 612 NewValues.push_back(LegalizeOp(Node->getOperand(i))); 613 break; 614 case Expand: { 615 SDOperand Lo, Hi; 616 ExpandOp(Node->getOperand(i), Lo, Hi); 617 NewValues.push_back(Lo); 618 NewValues.push_back(Hi); 619 break; 620 } 621 case Promote: 622 assert(0 && "Can't promote multiple return value yet!"); 623 } 624 Result = DAG.getNode(ISD::RET, MVT::Other, NewValues); 625 break; 626 } 627 } 628 break; 629 case ISD::STORE: 630 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 631 Tmp2 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 632 633 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 634 if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){ 635 if (CFP->getValueType(0) == MVT::f32) { 636 union { 637 unsigned I; 638 float F; 639 } V; 640 V.F = CFP->getValue(); 641 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 642 DAG.getConstant(V.I, MVT::i32), Tmp2, 643 Node->getOperand(3)); 644 } else { 645 assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!"); 646 union { 647 uint64_t I; 648 double F; 649 } V; 650 V.F = CFP->getValue(); 651 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 652 DAG.getConstant(V.I, MVT::i64), Tmp2, 653 Node->getOperand(3)); 654 } 655 Node = Result.Val; 656 } 657 658 switch (getTypeAction(Node->getOperand(1).getValueType())) { 659 case Legal: { 660 SDOperand Val = LegalizeOp(Node->getOperand(1)); 661 if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) || 662 Tmp2 != Node->getOperand(2)) 663 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2, 664 Node->getOperand(3)); 665 break; 666 } 667 case Promote: 668 // Truncate the value and store the result. 669 Tmp3 = PromoteOp(Node->getOperand(1)); 670 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2, 671 Node->getOperand(3), 672 Node->getOperand(1).getValueType()); 673 break; 674 675 case Expand: 676 SDOperand Lo, Hi; 677 ExpandOp(Node->getOperand(1), Lo, Hi); 678 679 if (!TLI.isLittleEndian()) 680 std::swap(Lo, Hi); 681 682 Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2, 683 Node->getOperand(3)); 684 unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8; 685 Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2, 686 getIntPtrConstant(IncrementSize)); 687 assert(isTypeLegal(Tmp2.getValueType()) && 688 "Pointers must be legal!"); 689 //Again, claiming both parts of the store came form the same Instr 690 Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2, 691 Node->getOperand(3)); 692 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); 693 break; 694 } 695 break; 696 case ISD::PCMARKER: 697 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 698 if (Tmp1 != Node->getOperand(0)) 699 Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1,Node->getOperand(1)); 700 break; 701 case ISD::TRUNCSTORE: 702 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 703 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 704 705 switch (getTypeAction(Node->getOperand(1).getValueType())) { 706 case Legal: 707 Tmp2 = LegalizeOp(Node->getOperand(1)); 708 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 709 Tmp3 != Node->getOperand(2)) 710 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3, 711 Node->getOperand(3), 712 cast<MVTSDNode>(Node)->getExtraValueType()); 713 break; 714 case Promote: 715 case Expand: 716 assert(0 && "Cannot handle illegal TRUNCSTORE yet!"); 717 } 718 break; 719 case ISD::SELECT: 720 switch (getTypeAction(Node->getOperand(0).getValueType())) { 721 case Expand: assert(0 && "It's impossible to expand bools"); 722 case Legal: 723 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 724 break; 725 case Promote: 726 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 727 break; 728 } 729 Tmp2 = LegalizeOp(Node->getOperand(1)); // TrueVal 730 Tmp3 = LegalizeOp(Node->getOperand(2)); // FalseVal 731 732 switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) { 733 default: assert(0 && "This action is not supported yet!"); 734 case TargetLowering::Legal: 735 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 736 Tmp3 != Node->getOperand(2)) 737 Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), 738 Tmp1, Tmp2, Tmp3); 739 break; 740 case TargetLowering::Promote: { 741 MVT::ValueType NVT = 742 TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType()); 743 unsigned ExtOp, TruncOp; 744 if (MVT::isInteger(Tmp2.getValueType())) { 745 ExtOp = ISD::ZERO_EXTEND; 746 TruncOp = ISD::TRUNCATE; 747 } else { 748 ExtOp = ISD::FP_EXTEND; 749 TruncOp = ISD::FP_ROUND; 750 } 751 // Promote each of the values to the new type. 752 Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2); 753 Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3); 754 // Perform the larger operation, then round down. 755 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3); 756 Result = DAG.getNode(TruncOp, Node->getValueType(0), Result); 757 break; 758 } 759 } 760 break; 761 case ISD::SETCC: 762 switch (getTypeAction(Node->getOperand(0).getValueType())) { 763 case Legal: 764 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 765 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 766 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 767 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 768 Node->getValueType(0), Tmp1, Tmp2); 769 break; 770 case Promote: 771 Tmp1 = PromoteOp(Node->getOperand(0)); // LHS 772 Tmp2 = PromoteOp(Node->getOperand(1)); // RHS 773 774 // If this is an FP compare, the operands have already been extended. 775 if (MVT::isInteger(Node->getOperand(0).getValueType())) { 776 MVT::ValueType VT = Node->getOperand(0).getValueType(); 777 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 778 779 // Otherwise, we have to insert explicit sign or zero extends. Note 780 // that we could insert sign extends for ALL conditions, but zero extend 781 // is cheaper on many machines (an AND instead of two shifts), so prefer 782 // it. 783 switch (cast<SetCCSDNode>(Node)->getCondition()) { 784 default: assert(0 && "Unknown integer comparison!"); 785 case ISD::SETEQ: 786 case ISD::SETNE: 787 case ISD::SETUGE: 788 case ISD::SETUGT: 789 case ISD::SETULE: 790 case ISD::SETULT: 791 // ALL of these operations will work if we either sign or zero extend 792 // the operands (including the unsigned comparisons!). Zero extend is 793 // usually a simpler/cheaper operation, so prefer it. 794 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT); 795 Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT); 796 break; 797 case ISD::SETGE: 798 case ISD::SETGT: 799 case ISD::SETLT: 800 case ISD::SETLE: 801 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT); 802 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT); 803 break; 804 } 805 806 } 807 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 808 Node->getValueType(0), Tmp1, Tmp2); 809 break; 810 case Expand: 811 SDOperand LHSLo, LHSHi, RHSLo, RHSHi; 812 ExpandOp(Node->getOperand(0), LHSLo, LHSHi); 813 ExpandOp(Node->getOperand(1), RHSLo, RHSHi); 814 switch (cast<SetCCSDNode>(Node)->getCondition()) { 815 case ISD::SETEQ: 816 case ISD::SETNE: 817 if (RHSLo == RHSHi) 818 if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo)) 819 if (RHSCST->isAllOnesValue()) { 820 // Comparison to -1. 821 Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi); 822 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 823 Node->getValueType(0), Tmp1, RHSLo); 824 break; 825 } 826 827 Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo); 828 Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi); 829 Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2); 830 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 831 Node->getValueType(0), Tmp1, 832 DAG.getConstant(0, Tmp1.getValueType())); 833 break; 834 default: 835 // If this is a comparison of the sign bit, just look at the top part. 836 // X > -1, x < 0 837 if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(Node->getOperand(1))) 838 if ((cast<SetCCSDNode>(Node)->getCondition() == ISD::SETLT && 839 CST->getValue() == 0) || // X < 0 840 (cast<SetCCSDNode>(Node)->getCondition() == ISD::SETGT && 841 (CST->isAllOnesValue()))) // X > -1 842 return DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 843 Node->getValueType(0), LHSHi, RHSHi); 844 845 // FIXME: This generated code sucks. 846 ISD::CondCode LowCC; 847 switch (cast<SetCCSDNode>(Node)->getCondition()) { 848 default: assert(0 && "Unknown integer setcc!"); 849 case ISD::SETLT: 850 case ISD::SETULT: LowCC = ISD::SETULT; break; 851 case ISD::SETGT: 852 case ISD::SETUGT: LowCC = ISD::SETUGT; break; 853 case ISD::SETLE: 854 case ISD::SETULE: LowCC = ISD::SETULE; break; 855 case ISD::SETGE: 856 case ISD::SETUGE: LowCC = ISD::SETUGE; break; 857 } 858 859 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison 860 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands 861 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2; 862 863 // NOTE: on targets without efficient SELECT of bools, we can always use 864 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3) 865 Tmp1 = DAG.getSetCC(LowCC, Node->getValueType(0), LHSLo, RHSLo); 866 Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 867 Node->getValueType(0), LHSHi, RHSHi); 868 Result = DAG.getSetCC(ISD::SETEQ, Node->getValueType(0), LHSHi, RHSHi); 869 Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(), 870 Result, Tmp1, Tmp2); 871 break; 872 } 873 } 874 break; 875 876 case ISD::MEMSET: 877 case ISD::MEMCPY: 878 case ISD::MEMMOVE: { 879 Tmp1 = LegalizeOp(Node->getOperand(0)); // Chain 880 Tmp2 = LegalizeOp(Node->getOperand(1)); // Pointer 881 882 if (Node->getOpcode() == ISD::MEMSET) { // memset = ubyte 883 switch (getTypeAction(Node->getOperand(2).getValueType())) { 884 case Expand: assert(0 && "Cannot expand a byte!"); 885 case Legal: 886 Tmp3 = LegalizeOp(Node->getOperand(2)); 887 break; 888 case Promote: 889 Tmp3 = PromoteOp(Node->getOperand(2)); 890 break; 891 } 892 } else { 893 Tmp3 = LegalizeOp(Node->getOperand(2)); // memcpy/move = pointer, 894 } 895 896 SDOperand Tmp4; 897 switch (getTypeAction(Node->getOperand(3).getValueType())) { 898 case Expand: assert(0 && "Cannot expand this yet!"); 899 case Legal: 900 Tmp4 = LegalizeOp(Node->getOperand(3)); 901 break; 902 case Promote: 903 Tmp4 = PromoteOp(Node->getOperand(3)); 904 break; 905 } 906 907 SDOperand Tmp5; 908 switch (getTypeAction(Node->getOperand(4).getValueType())) { // uint 909 case Expand: assert(0 && "Cannot expand this yet!"); 910 case Legal: 911 Tmp5 = LegalizeOp(Node->getOperand(4)); 912 break; 913 case Promote: 914 Tmp5 = PromoteOp(Node->getOperand(4)); 915 break; 916 } 917 918 switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) { 919 default: assert(0 && "This action not implemented for this operation!"); 920 case TargetLowering::Legal: 921 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 922 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) || 923 Tmp5 != Node->getOperand(4)) { 924 std::vector<SDOperand> Ops; 925 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 926 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 927 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 928 } 929 break; 930 case TargetLowering::Expand: { 931 // Otherwise, the target does not support this operation. Lower the 932 // operation to an explicit libcall as appropriate. 933 MVT::ValueType IntPtr = TLI.getPointerTy(); 934 const Type *IntPtrTy = TLI.getTargetData().getIntPtrType(); 935 std::vector<std::pair<SDOperand, const Type*> > Args; 936 937 const char *FnName = 0; 938 if (Node->getOpcode() == ISD::MEMSET) { 939 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 940 // Extend the ubyte argument to be an int value for the call. 941 Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3); 942 Args.push_back(std::make_pair(Tmp3, Type::IntTy)); 943 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 944 945 FnName = "memset"; 946 } else if (Node->getOpcode() == ISD::MEMCPY || 947 Node->getOpcode() == ISD::MEMMOVE) { 948 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 949 Args.push_back(std::make_pair(Tmp3, IntPtrTy)); 950 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 951 FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy"; 952 } else { 953 assert(0 && "Unknown op!"); 954 } 955 956 std::pair<SDOperand,SDOperand> CallResult = 957 TLI.LowerCallTo(Tmp1, Type::VoidTy, false, CallingConv::C, false, 958 DAG.getExternalSymbol(FnName, IntPtr), Args, DAG); 959 Result = LegalizeOp(CallResult.second); 960 break; 961 } 962 case TargetLowering::Custom: 963 std::vector<SDOperand> Ops; 964 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 965 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 966 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 967 Result = TLI.LowerOperation(Result, DAG); 968 Result = LegalizeOp(Result); 969 break; 970 } 971 break; 972 } 973 974 case ISD::READPORT: 975 Tmp1 = LegalizeOp(Node->getOperand(0)); 976 Tmp2 = LegalizeOp(Node->getOperand(1)); 977 978 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 979 Result = DAG.getNode(ISD::READPORT, Node->getValueType(0), Tmp1, Tmp2); 980 else 981 Result = SDOperand(Node, 0); 982 // Since these produce two values, make sure to remember that we legalized 983 // both of them. 984 AddLegalizedOperand(SDOperand(Node, 0), Result); 985 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 986 return Result.getValue(Op.ResNo); 987 case ISD::WRITEPORT: 988 Tmp1 = LegalizeOp(Node->getOperand(0)); 989 Tmp2 = LegalizeOp(Node->getOperand(1)); 990 Tmp3 = LegalizeOp(Node->getOperand(2)); 991 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 992 Tmp3 != Node->getOperand(2)) 993 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3); 994 break; 995 996 case ISD::READIO: 997 Tmp1 = LegalizeOp(Node->getOperand(0)); 998 Tmp2 = LegalizeOp(Node->getOperand(1)); 999 1000 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 1001 case TargetLowering::Custom: 1002 default: assert(0 && "This action not implemented for this operation!"); 1003 case TargetLowering::Legal: 1004 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 1005 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), 1006 Tmp1, Tmp2); 1007 else 1008 Result = SDOperand(Node, 0); 1009 break; 1010 case TargetLowering::Expand: 1011 // Replace this with a load from memory. 1012 Result = DAG.getLoad(Node->getValueType(0), Node->getOperand(0), 1013 Node->getOperand(1), DAG.getSrcValue(NULL)); 1014 Result = LegalizeOp(Result); 1015 break; 1016 } 1017 1018 // Since these produce two values, make sure to remember that we legalized 1019 // both of them. 1020 AddLegalizedOperand(SDOperand(Node, 0), Result); 1021 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1022 return Result.getValue(Op.ResNo); 1023 1024 case ISD::WRITEIO: 1025 Tmp1 = LegalizeOp(Node->getOperand(0)); 1026 Tmp2 = LegalizeOp(Node->getOperand(1)); 1027 Tmp3 = LegalizeOp(Node->getOperand(2)); 1028 1029 switch (TLI.getOperationAction(Node->getOpcode(), 1030 Node->getOperand(1).getValueType())) { 1031 case TargetLowering::Custom: 1032 default: assert(0 && "This action not implemented for this operation!"); 1033 case TargetLowering::Legal: 1034 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1035 Tmp3 != Node->getOperand(2)) 1036 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3); 1037 break; 1038 case TargetLowering::Expand: 1039 // Replace this with a store to memory. 1040 Result = DAG.getNode(ISD::STORE, MVT::Other, Node->getOperand(0), 1041 Node->getOperand(1), Node->getOperand(2), 1042 DAG.getSrcValue(NULL)); 1043 Result = LegalizeOp(Result); 1044 break; 1045 } 1046 break; 1047 1048 case ISD::ADD_PARTS: 1049 case ISD::SUB_PARTS: 1050 case ISD::SHL_PARTS: 1051 case ISD::SRA_PARTS: 1052 case ISD::SRL_PARTS: { 1053 std::vector<SDOperand> Ops; 1054 bool Changed = false; 1055 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 1056 Ops.push_back(LegalizeOp(Node->getOperand(i))); 1057 Changed |= Ops.back() != Node->getOperand(i); 1058 } 1059 if (Changed) { 1060 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end()); 1061 Result = DAG.getNode(Node->getOpcode(), VTs, Ops); 1062 } 1063 1064 // Since these produce multiple values, make sure to remember that we 1065 // legalized all of them. 1066 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 1067 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 1068 return Result.getValue(Op.ResNo); 1069 } 1070 1071 // Binary operators 1072 case ISD::ADD: 1073 case ISD::SUB: 1074 case ISD::MUL: 1075 case ISD::MULHS: 1076 case ISD::MULHU: 1077 case ISD::UDIV: 1078 case ISD::SDIV: 1079 case ISD::AND: 1080 case ISD::OR: 1081 case ISD::XOR: 1082 case ISD::SHL: 1083 case ISD::SRL: 1084 case ISD::SRA: 1085 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 1086 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 1087 if (Tmp1 != Node->getOperand(0) || 1088 Tmp2 != Node->getOperand(1)) 1089 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2); 1090 break; 1091 1092 case ISD::UREM: 1093 case ISD::SREM: 1094 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 1095 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 1096 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 1097 case TargetLowering::Legal: 1098 if (Tmp1 != Node->getOperand(0) || 1099 Tmp2 != Node->getOperand(1)) 1100 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 1101 Tmp2); 1102 break; 1103 case TargetLowering::Promote: 1104 case TargetLowering::Custom: 1105 assert(0 && "Cannot promote/custom handle this yet!"); 1106 case TargetLowering::Expand: { 1107 MVT::ValueType VT = Node->getValueType(0); 1108 unsigned Opc = (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV; 1109 Result = DAG.getNode(Opc, VT, Tmp1, Tmp2); 1110 Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2); 1111 Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result); 1112 } 1113 break; 1114 } 1115 break; 1116 1117 case ISD::CTPOP: 1118 case ISD::CTTZ: 1119 case ISD::CTLZ: 1120 Tmp1 = LegalizeOp(Node->getOperand(0)); // Op 1121 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 1122 case TargetLowering::Legal: 1123 if (Tmp1 != Node->getOperand(0)) 1124 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1125 break; 1126 case TargetLowering::Promote: { 1127 MVT::ValueType OVT = Tmp1.getValueType(); 1128 MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT); 1129 1130 // Zero extend the argument. 1131 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); 1132 // Perform the larger operation, then subtract if needed. 1133 Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1134 switch(Node->getOpcode()) 1135 { 1136 case ISD::CTPOP: 1137 Result = Tmp1; 1138 break; 1139 case ISD::CTTZ: 1140 //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT) 1141 Tmp2 = DAG.getSetCC(ISD::SETEQ, TLI.getSetCCResultTy(), Tmp1, 1142 DAG.getConstant(getSizeInBits(NVT), NVT)); 1143 Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, 1144 DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1); 1145 break; 1146 case ISD::CTLZ: 1147 //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT)) 1148 Result = DAG.getNode(ISD::SUB, NVT, Tmp1, 1149 DAG.getConstant(getSizeInBits(NVT) - 1150 getSizeInBits(OVT), NVT)); 1151 break; 1152 } 1153 break; 1154 } 1155 case TargetLowering::Custom: 1156 assert(0 && "Cannot custom handle this yet!"); 1157 case TargetLowering::Expand: 1158 switch(Node->getOpcode()) 1159 { 1160 case ISD::CTPOP: { 1161 static const uint64_t mask[6] = { 1162 0x5555555555555555ULL, 0x3333333333333333ULL, 1163 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL, 1164 0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL 1165 }; 1166 MVT::ValueType VT = Tmp1.getValueType(); 1167 MVT::ValueType ShVT = TLI.getShiftAmountTy(); 1168 unsigned len = getSizeInBits(VT); 1169 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { 1170 //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8]) 1171 Tmp2 = DAG.getConstant(mask[i], VT); 1172 Tmp3 = DAG.getConstant(1ULL << i, ShVT); 1173 Tmp1 = DAG.getNode(ISD::ADD, VT, 1174 DAG.getNode(ISD::AND, VT, Tmp1, Tmp2), 1175 DAG.getNode(ISD::AND, VT, 1176 DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3), 1177 Tmp2)); 1178 } 1179 Result = Tmp1; 1180 break; 1181 } 1182 case ISD::CTLZ: { 1183 /* for now, we do this: 1184 x = x | (x >> 1); 1185 x = x | (x >> 2); 1186 ... 1187 x = x | (x >>16); 1188 x = x | (x >>32); // for 64-bit input 1189 return popcount(~x); 1190 1191 but see also: http://www.hackersdelight.org/HDcode/nlz.cc */ 1192 MVT::ValueType VT = Tmp1.getValueType(); 1193 MVT::ValueType ShVT = TLI.getShiftAmountTy(); 1194 unsigned len = getSizeInBits(VT); 1195 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { 1196 Tmp3 = DAG.getConstant(1ULL << i, ShVT); 1197 Tmp1 = DAG.getNode(ISD::OR, VT, Tmp1, 1198 DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3)); 1199 } 1200 Tmp3 = DAG.getNode(ISD::XOR, VT, Tmp1, DAG.getConstant(~0ULL, VT)); 1201 Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3)); 1202 break; 1203 } 1204 case ISD::CTTZ: { 1205 // for now, we use: { return popcount(~x & (x - 1)); } 1206 // unless the target has ctlz but not ctpop, in which case we use: 1207 // { return 32 - nlz(~x & (x-1)); } 1208 // see also http://www.hackersdelight.org/HDcode/ntz.cc 1209 MVT::ValueType VT = Tmp1.getValueType(); 1210 Tmp2 = DAG.getConstant(~0ULL, VT); 1211 Tmp3 = DAG.getNode(ISD::AND, VT, 1212 DAG.getNode(ISD::XOR, VT, Tmp1, Tmp2), 1213 DAG.getNode(ISD::SUB, VT, Tmp1, 1214 DAG.getConstant(1, VT))); 1215 // If ISD::CTLZ is legal and CTPOP isn't, then do that instead 1216 if (TLI.getOperationAction(ISD::CTPOP, VT) != TargetLowering::Legal && 1217 TLI.getOperationAction(ISD::CTLZ, VT) == TargetLowering::Legal) { 1218 Result = LegalizeOp(DAG.getNode(ISD::SUB, VT, 1219 DAG.getConstant(getSizeInBits(VT), VT), 1220 DAG.getNode(ISD::CTLZ, VT, Tmp3))); 1221 } else { 1222 Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3)); 1223 } 1224 break; 1225 } 1226 default: 1227 assert(0 && "Cannot expand this yet!"); 1228 break; 1229 } 1230 break; 1231 } 1232 break; 1233 1234 // Unary operators 1235 case ISD::FABS: 1236 case ISD::FNEG: 1237 case ISD::FSQRT: 1238 case ISD::FSIN: 1239 case ISD::FCOS: 1240 Tmp1 = LegalizeOp(Node->getOperand(0)); 1241 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 1242 case TargetLowering::Legal: 1243 if (Tmp1 != Node->getOperand(0)) 1244 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1245 break; 1246 case TargetLowering::Promote: 1247 case TargetLowering::Custom: 1248 assert(0 && "Cannot promote/custom handle this yet!"); 1249 case TargetLowering::Expand: 1250 switch(Node->getOpcode()) { 1251 case ISD::FNEG: { 1252 // Expand Y = FNEG(X) -> Y = SUB -0.0, X 1253 Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0)); 1254 Result = LegalizeOp(DAG.getNode(ISD::SUB, Node->getValueType(0), 1255 Tmp2, Tmp1)); 1256 break; 1257 } 1258 case ISD::FABS: { 1259 // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X). 1260 MVT::ValueType VT = Node->getValueType(0); 1261 Tmp2 = DAG.getConstantFP(0.0, VT); 1262 Tmp2 = DAG.getSetCC(ISD::SETUGT, TLI.getSetCCResultTy(), Tmp1, Tmp2); 1263 Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1); 1264 Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3); 1265 Result = LegalizeOp(Result); 1266 break; 1267 } 1268 case ISD::FSQRT: 1269 case ISD::FSIN: 1270 case ISD::FCOS: { 1271 MVT::ValueType VT = Node->getValueType(0); 1272 Type *T = VT == MVT::f32 ? Type::FloatTy : Type::DoubleTy; 1273 const char *FnName = 0; 1274 switch(Node->getOpcode()) { 1275 case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break; 1276 case ISD::FSIN: FnName = VT == MVT::f32 ? "sinf" : "sin"; break; 1277 case ISD::FCOS: FnName = VT == MVT::f32 ? "cosf" : "cos"; break; 1278 default: assert(0 && "Unreachable!"); 1279 } 1280 std::vector<std::pair<SDOperand, const Type*> > Args; 1281 Args.push_back(std::make_pair(Tmp1, T)); 1282 // FIXME: should use ExpandLibCall! 1283 std::pair<SDOperand,SDOperand> CallResult = 1284 TLI.LowerCallTo(DAG.getEntryNode(), T, false, CallingConv::C, true, 1285 DAG.getExternalSymbol(FnName, VT), Args, DAG); 1286 Result = LegalizeOp(CallResult.first); 1287 break; 1288 } 1289 default: 1290 assert(0 && "Unreachable!"); 1291 } 1292 break; 1293 } 1294 break; 1295 1296 // Conversion operators. The source and destination have different types. 1297 case ISD::ZERO_EXTEND: 1298 case ISD::SIGN_EXTEND: 1299 case ISD::TRUNCATE: 1300 case ISD::FP_EXTEND: 1301 case ISD::FP_ROUND: 1302 case ISD::FP_TO_SINT: 1303 case ISD::FP_TO_UINT: 1304 case ISD::SINT_TO_FP: 1305 case ISD::UINT_TO_FP: 1306 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1307 case Legal: 1308 Tmp1 = LegalizeOp(Node->getOperand(0)); 1309 if (Tmp1 != Node->getOperand(0)) 1310 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1311 break; 1312 case Expand: 1313 if (Node->getOpcode() == ISD::SINT_TO_FP || 1314 Node->getOpcode() == ISD::UINT_TO_FP) { 1315 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, 1316 Node->getValueType(0), Node->getOperand(0)); 1317 break; 1318 } else if (Node->getOpcode() == ISD::TRUNCATE) { 1319 // In the expand case, we must be dealing with a truncate, because 1320 // otherwise the result would be larger than the source. 1321 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 1322 1323 // Since the result is legal, we should just be able to truncate the low 1324 // part of the source. 1325 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1); 1326 break; 1327 } 1328 assert(0 && "Shouldn't need to expand other operators here!"); 1329 1330 case Promote: 1331 switch (Node->getOpcode()) { 1332 case ISD::ZERO_EXTEND: 1333 Result = PromoteOp(Node->getOperand(0)); 1334 // NOTE: Any extend would work here... 1335 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result); 1336 Result = DAG.getZeroExtendInReg(Result, 1337 Node->getOperand(0).getValueType()); 1338 break; 1339 case ISD::SIGN_EXTEND: 1340 Result = PromoteOp(Node->getOperand(0)); 1341 // NOTE: Any extend would work here... 1342 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result); 1343 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 1344 Result, Node->getOperand(0).getValueType()); 1345 break; 1346 case ISD::TRUNCATE: 1347 Result = PromoteOp(Node->getOperand(0)); 1348 Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result); 1349 break; 1350 case ISD::FP_EXTEND: 1351 Result = PromoteOp(Node->getOperand(0)); 1352 if (Result.getValueType() != Op.getValueType()) 1353 // Dynamically dead while we have only 2 FP types. 1354 Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result); 1355 break; 1356 case ISD::FP_ROUND: 1357 case ISD::FP_TO_SINT: 1358 case ISD::FP_TO_UINT: 1359 Result = PromoteOp(Node->getOperand(0)); 1360 Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result); 1361 break; 1362 case ISD::SINT_TO_FP: 1363 Result = PromoteOp(Node->getOperand(0)); 1364 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 1365 Result, Node->getOperand(0).getValueType()); 1366 Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result); 1367 break; 1368 case ISD::UINT_TO_FP: 1369 Result = PromoteOp(Node->getOperand(0)); 1370 Result = DAG.getZeroExtendInReg(Result, 1371 Node->getOperand(0).getValueType()); 1372 Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result); 1373 break; 1374 } 1375 } 1376 break; 1377 case ISD::FP_ROUND_INREG: 1378 case ISD::SIGN_EXTEND_INREG: { 1379 Tmp1 = LegalizeOp(Node->getOperand(0)); 1380 MVT::ValueType ExtraVT = cast<MVTSDNode>(Node)->getExtraValueType(); 1381 1382 // If this operation is not supported, convert it to a shl/shr or load/store 1383 // pair. 1384 switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) { 1385 default: assert(0 && "This action not supported for this op yet!"); 1386 case TargetLowering::Legal: 1387 if (Tmp1 != Node->getOperand(0)) 1388 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 1389 ExtraVT); 1390 break; 1391 case TargetLowering::Expand: 1392 // If this is an integer extend and shifts are supported, do that. 1393 if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) { 1394 // NOTE: we could fall back on load/store here too for targets without 1395 // SAR. However, it is doubtful that any exist. 1396 unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) - 1397 MVT::getSizeInBits(ExtraVT); 1398 SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy()); 1399 Result = DAG.getNode(ISD::SHL, Node->getValueType(0), 1400 Node->getOperand(0), ShiftCst); 1401 Result = DAG.getNode(ISD::SRA, Node->getValueType(0), 1402 Result, ShiftCst); 1403 } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) { 1404 // The only way we can lower this is to turn it into a STORETRUNC, 1405 // EXTLOAD pair, targetting a temporary location (a stack slot). 1406 1407 // NOTE: there is a choice here between constantly creating new stack 1408 // slots and always reusing the same one. We currently always create 1409 // new ones, as reuse may inhibit scheduling. 1410 const Type *Ty = MVT::getTypeForValueType(ExtraVT); 1411 unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty); 1412 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); 1413 MachineFunction &MF = DAG.getMachineFunction(); 1414 int SSFI = 1415 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 1416 SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); 1417 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(), 1418 Node->getOperand(0), StackSlot, 1419 DAG.getSrcValue(NULL), ExtraVT); 1420 Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0), 1421 Result, StackSlot, DAG.getSrcValue(NULL), ExtraVT); 1422 } else { 1423 assert(0 && "Unknown op"); 1424 } 1425 Result = LegalizeOp(Result); 1426 break; 1427 } 1428 break; 1429 } 1430 } 1431 1432 // Note that LegalizeOp may be reentered even from single-use nodes, which 1433 // means that we always must cache transformed nodes. 1434 AddLegalizedOperand(Op, Result); 1435 return Result; 1436} 1437 1438/// PromoteOp - Given an operation that produces a value in an invalid type, 1439/// promote it to compute the value into a larger type. The produced value will 1440/// have the correct bits for the low portion of the register, but no guarantee 1441/// is made about the top bits: it may be zero, sign-extended, or garbage. 1442SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { 1443 MVT::ValueType VT = Op.getValueType(); 1444 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 1445 assert(getTypeAction(VT) == Promote && 1446 "Caller should expand or legalize operands that are not promotable!"); 1447 assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) && 1448 "Cannot promote to smaller type!"); 1449 1450 SDOperand Tmp1, Tmp2, Tmp3; 1451 1452 SDOperand Result; 1453 SDNode *Node = Op.Val; 1454 1455 if (!Node->hasOneUse()) { 1456 std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op); 1457 if (I != PromotedNodes.end()) return I->second; 1458 } else { 1459 assert(!PromotedNodes.count(Op) && "Repromoted this node??"); 1460 } 1461 1462 // Promotion needs an optimization step to clean up after it, and is not 1463 // careful to avoid operations the target does not support. Make sure that 1464 // all generated operations are legalized in the next iteration. 1465 NeedsAnotherIteration = true; 1466 1467 switch (Node->getOpcode()) { 1468 default: 1469 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 1470 assert(0 && "Do not know how to promote this operator!"); 1471 abort(); 1472 case ISD::UNDEF: 1473 Result = DAG.getNode(ISD::UNDEF, NVT); 1474 break; 1475 case ISD::Constant: 1476 Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op); 1477 assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?"); 1478 break; 1479 case ISD::ConstantFP: 1480 Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op); 1481 assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?"); 1482 break; 1483 case ISD::CopyFromReg: 1484 Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), NVT, 1485 Node->getOperand(0)); 1486 // Remember that we legalized the chain. 1487 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 1488 break; 1489 1490 case ISD::SETCC: 1491 assert(getTypeAction(TLI.getSetCCResultTy()) == Legal && 1492 "SetCC type is not legal??"); 1493 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 1494 TLI.getSetCCResultTy(), Node->getOperand(0), 1495 Node->getOperand(1)); 1496 Result = LegalizeOp(Result); 1497 break; 1498 1499 case ISD::TRUNCATE: 1500 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1501 case Legal: 1502 Result = LegalizeOp(Node->getOperand(0)); 1503 assert(Result.getValueType() >= NVT && 1504 "This truncation doesn't make sense!"); 1505 if (Result.getValueType() > NVT) // Truncate to NVT instead of VT 1506 Result = DAG.getNode(ISD::TRUNCATE, NVT, Result); 1507 break; 1508 case Promote: 1509 // The truncation is not required, because we don't guarantee anything 1510 // about high bits anyway. 1511 Result = PromoteOp(Node->getOperand(0)); 1512 break; 1513 case Expand: 1514 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 1515 // Truncate the low part of the expanded value to the result type 1516 Result = DAG.getNode(ISD::TRUNCATE, VT, Tmp1); 1517 } 1518 break; 1519 case ISD::SIGN_EXTEND: 1520 case ISD::ZERO_EXTEND: 1521 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1522 case Expand: assert(0 && "BUG: Smaller reg should have been promoted!"); 1523 case Legal: 1524 // Input is legal? Just do extend all the way to the larger type. 1525 Result = LegalizeOp(Node->getOperand(0)); 1526 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 1527 break; 1528 case Promote: 1529 // Promote the reg if it's smaller. 1530 Result = PromoteOp(Node->getOperand(0)); 1531 // The high bits are not guaranteed to be anything. Insert an extend. 1532 if (Node->getOpcode() == ISD::SIGN_EXTEND) 1533 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result, 1534 Node->getOperand(0).getValueType()); 1535 else 1536 Result = DAG.getZeroExtendInReg(Result, 1537 Node->getOperand(0).getValueType()); 1538 break; 1539 } 1540 break; 1541 1542 case ISD::FP_EXTEND: 1543 assert(0 && "Case not implemented. Dynamically dead with 2 FP types!"); 1544 case ISD::FP_ROUND: 1545 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1546 case Expand: assert(0 && "BUG: Cannot expand FP regs!"); 1547 case Promote: assert(0 && "Unreachable with 2 FP types!"); 1548 case Legal: 1549 // Input is legal? Do an FP_ROUND_INREG. 1550 Result = LegalizeOp(Node->getOperand(0)); 1551 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1552 break; 1553 } 1554 break; 1555 1556 case ISD::SINT_TO_FP: 1557 case ISD::UINT_TO_FP: 1558 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1559 case Legal: 1560 Result = LegalizeOp(Node->getOperand(0)); 1561 // No extra round required here. 1562 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 1563 break; 1564 1565 case Promote: 1566 Result = PromoteOp(Node->getOperand(0)); 1567 if (Node->getOpcode() == ISD::SINT_TO_FP) 1568 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 1569 Result, Node->getOperand(0).getValueType()); 1570 else 1571 Result = DAG.getZeroExtendInReg(Result, 1572 Node->getOperand(0).getValueType()); 1573 // No extra round required here. 1574 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 1575 break; 1576 case Expand: 1577 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT, 1578 Node->getOperand(0)); 1579 // Round if we cannot tolerate excess precision. 1580 if (NoExcessFPPrecision) 1581 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1582 break; 1583 } 1584 break; 1585 1586 case ISD::FP_TO_SINT: 1587 case ISD::FP_TO_UINT: 1588 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1589 case Legal: 1590 Tmp1 = LegalizeOp(Node->getOperand(0)); 1591 break; 1592 case Promote: 1593 // The input result is prerounded, so we don't have to do anything 1594 // special. 1595 Tmp1 = PromoteOp(Node->getOperand(0)); 1596 break; 1597 case Expand: 1598 assert(0 && "not implemented"); 1599 } 1600 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 1601 break; 1602 1603 case ISD::FABS: 1604 case ISD::FNEG: 1605 Tmp1 = PromoteOp(Node->getOperand(0)); 1606 assert(Tmp1.getValueType() == NVT); 1607 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 1608 // NOTE: we do not have to do any extra rounding here for 1609 // NoExcessFPPrecision, because we know the input will have the appropriate 1610 // precision, and these operations don't modify precision at all. 1611 break; 1612 1613 case ISD::FSQRT: 1614 case ISD::FSIN: 1615 case ISD::FCOS: 1616 Tmp1 = PromoteOp(Node->getOperand(0)); 1617 assert(Tmp1.getValueType() == NVT); 1618 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 1619 if(NoExcessFPPrecision) 1620 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1621 break; 1622 1623 case ISD::AND: 1624 case ISD::OR: 1625 case ISD::XOR: 1626 case ISD::ADD: 1627 case ISD::SUB: 1628 case ISD::MUL: 1629 // The input may have strange things in the top bits of the registers, but 1630 // these operations don't care. They may have wierd bits going out, but 1631 // that too is okay if they are integer operations. 1632 Tmp1 = PromoteOp(Node->getOperand(0)); 1633 Tmp2 = PromoteOp(Node->getOperand(1)); 1634 assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT); 1635 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 1636 1637 // However, if this is a floating point operation, they will give excess 1638 // precision that we may not be able to tolerate. If we DO allow excess 1639 // precision, just leave it, otherwise excise it. 1640 // FIXME: Why would we need to round FP ops more than integer ones? 1641 // Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C)) 1642 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision) 1643 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1644 break; 1645 1646 case ISD::SDIV: 1647 case ISD::SREM: 1648 // These operators require that their input be sign extended. 1649 Tmp1 = PromoteOp(Node->getOperand(0)); 1650 Tmp2 = PromoteOp(Node->getOperand(1)); 1651 if (MVT::isInteger(NVT)) { 1652 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT); 1653 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT); 1654 } 1655 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 1656 1657 // Perform FP_ROUND: this is probably overly pessimistic. 1658 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision) 1659 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1660 break; 1661 1662 case ISD::UDIV: 1663 case ISD::UREM: 1664 // These operators require that their input be zero extended. 1665 Tmp1 = PromoteOp(Node->getOperand(0)); 1666 Tmp2 = PromoteOp(Node->getOperand(1)); 1667 assert(MVT::isInteger(NVT) && "Operators don't apply to FP!"); 1668 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT); 1669 Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT); 1670 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 1671 break; 1672 1673 case ISD::SHL: 1674 Tmp1 = PromoteOp(Node->getOperand(0)); 1675 Tmp2 = LegalizeOp(Node->getOperand(1)); 1676 Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2); 1677 break; 1678 case ISD::SRA: 1679 // The input value must be properly sign extended. 1680 Tmp1 = PromoteOp(Node->getOperand(0)); 1681 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT); 1682 Tmp2 = LegalizeOp(Node->getOperand(1)); 1683 Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2); 1684 break; 1685 case ISD::SRL: 1686 // The input value must be properly zero extended. 1687 Tmp1 = PromoteOp(Node->getOperand(0)); 1688 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT); 1689 Tmp2 = LegalizeOp(Node->getOperand(1)); 1690 Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2); 1691 break; 1692 case ISD::LOAD: 1693 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1694 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 1695 // FIXME: When the DAG combiner exists, change this to use EXTLOAD! 1696 if (MVT::isInteger(NVT)) 1697 Result = DAG.getNode(ISD::ZEXTLOAD, NVT, Tmp1, Tmp2, Node->getOperand(2), 1698 VT); 1699 else 1700 Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, Node->getOperand(2), 1701 VT); 1702 1703 // Remember that we legalized the chain. 1704 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 1705 break; 1706 case ISD::SELECT: 1707 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1708 case Expand: assert(0 && "It's impossible to expand bools"); 1709 case Legal: 1710 Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition. 1711 break; 1712 case Promote: 1713 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 1714 break; 1715 } 1716 Tmp2 = PromoteOp(Node->getOperand(1)); // Legalize the op0 1717 Tmp3 = PromoteOp(Node->getOperand(2)); // Legalize the op1 1718 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3); 1719 break; 1720 case ISD::TAILCALL: 1721 case ISD::CALL: { 1722 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1723 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 1724 1725 std::vector<SDOperand> Ops; 1726 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) 1727 Ops.push_back(LegalizeOp(Node->getOperand(i))); 1728 1729 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 1730 "Can only promote single result calls"); 1731 std::vector<MVT::ValueType> RetTyVTs; 1732 RetTyVTs.reserve(2); 1733 RetTyVTs.push_back(NVT); 1734 RetTyVTs.push_back(MVT::Other); 1735 SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops, 1736 Node->getOpcode() == ISD::TAILCALL); 1737 Result = SDOperand(NC, 0); 1738 1739 // Insert the new chain mapping. 1740 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 1741 break; 1742 } 1743 case ISD::CTPOP: 1744 case ISD::CTTZ: 1745 case ISD::CTLZ: 1746 Tmp1 = Node->getOperand(0); 1747 //Zero extend the argument 1748 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); 1749 // Perform the larger operation, then subtract if needed. 1750 Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 1751 switch(Node->getOpcode()) 1752 { 1753 case ISD::CTPOP: 1754 Result = Tmp1; 1755 break; 1756 case ISD::CTTZ: 1757 //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT) 1758 Tmp2 = DAG.getSetCC(ISD::SETEQ, MVT::i1, Tmp1, 1759 DAG.getConstant(getSizeInBits(NVT), NVT)); 1760 Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, 1761 DAG.getConstant(getSizeInBits(VT),NVT), Tmp1); 1762 break; 1763 case ISD::CTLZ: 1764 //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT)) 1765 Result = DAG.getNode(ISD::SUB, NVT, Tmp1, 1766 DAG.getConstant(getSizeInBits(NVT) - 1767 getSizeInBits(VT), NVT)); 1768 break; 1769 } 1770 break; 1771 } 1772 1773 assert(Result.Val && "Didn't set a result!"); 1774 AddPromotedOperand(Op, Result); 1775 return Result; 1776} 1777 1778/// ExpandAddSub - Find a clever way to expand this add operation into 1779/// subcomponents. 1780void SelectionDAGLegalize:: 1781ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS, 1782 SDOperand &Lo, SDOperand &Hi) { 1783 // Expand the subcomponents. 1784 SDOperand LHSL, LHSH, RHSL, RHSH; 1785 ExpandOp(LHS, LHSL, LHSH); 1786 ExpandOp(RHS, RHSL, RHSH); 1787 1788 // FIXME: this should be moved to the dag combiner someday. 1789 assert(NodeOp == ISD::ADD_PARTS || NodeOp == ISD::SUB_PARTS); 1790 if (LHSL.getValueType() == MVT::i32) { 1791 SDOperand LowEl; 1792 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(LHSL)) 1793 if (C->getValue() == 0) 1794 LowEl = RHSL; 1795 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHSL)) 1796 if (C->getValue() == 0) 1797 LowEl = LHSL; 1798 if (LowEl.Val) { 1799 // Turn this into an add/sub of the high part only. 1800 SDOperand HiEl = 1801 DAG.getNode(NodeOp == ISD::ADD_PARTS ? ISD::ADD : ISD::SUB, 1802 LowEl.getValueType(), LHSH, RHSH); 1803 Lo = LowEl; 1804 Hi = HiEl; 1805 return; 1806 } 1807 } 1808 1809 std::vector<SDOperand> Ops; 1810 Ops.push_back(LHSL); 1811 Ops.push_back(LHSH); 1812 Ops.push_back(RHSL); 1813 Ops.push_back(RHSH); 1814 1815 std::vector<MVT::ValueType> VTs(2, LHSL.getValueType()); 1816 Lo = DAG.getNode(NodeOp, VTs, Ops); 1817 Hi = Lo.getValue(1); 1818} 1819 1820void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp, 1821 SDOperand Op, SDOperand Amt, 1822 SDOperand &Lo, SDOperand &Hi) { 1823 // Expand the subcomponents. 1824 SDOperand LHSL, LHSH; 1825 ExpandOp(Op, LHSL, LHSH); 1826 1827 std::vector<SDOperand> Ops; 1828 Ops.push_back(LHSL); 1829 Ops.push_back(LHSH); 1830 Ops.push_back(Amt); 1831 std::vector<MVT::ValueType> VTs; 1832 VTs.push_back(LHSL.getValueType()); 1833 VTs.push_back(LHSH.getValueType()); 1834 VTs.push_back(Amt.getValueType()); 1835 Lo = DAG.getNode(NodeOp, VTs, Ops); 1836 Hi = Lo.getValue(1); 1837} 1838 1839 1840/// ExpandShift - Try to find a clever way to expand this shift operation out to 1841/// smaller elements. If we can't find a way that is more efficient than a 1842/// libcall on this target, return false. Otherwise, return true with the 1843/// low-parts expanded into Lo and Hi. 1844bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt, 1845 SDOperand &Lo, SDOperand &Hi) { 1846 assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) && 1847 "This is not a shift!"); 1848 1849 MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType()); 1850 SDOperand ShAmt = LegalizeOp(Amt); 1851 MVT::ValueType ShTy = ShAmt.getValueType(); 1852 unsigned VTBits = MVT::getSizeInBits(Op.getValueType()); 1853 unsigned NVTBits = MVT::getSizeInBits(NVT); 1854 1855 // Handle the case when Amt is an immediate. Other cases are currently broken 1856 // and are disabled. 1857 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) { 1858 unsigned Cst = CN->getValue(); 1859 // Expand the incoming operand to be shifted, so that we have its parts 1860 SDOperand InL, InH; 1861 ExpandOp(Op, InL, InH); 1862 switch(Opc) { 1863 case ISD::SHL: 1864 if (Cst > VTBits) { 1865 Lo = DAG.getConstant(0, NVT); 1866 Hi = DAG.getConstant(0, NVT); 1867 } else if (Cst > NVTBits) { 1868 Lo = DAG.getConstant(0, NVT); 1869 Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy)); 1870 } else if (Cst == NVTBits) { 1871 Lo = DAG.getConstant(0, NVT); 1872 Hi = InL; 1873 } else { 1874 Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy)); 1875 Hi = DAG.getNode(ISD::OR, NVT, 1876 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)), 1877 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy))); 1878 } 1879 return true; 1880 case ISD::SRL: 1881 if (Cst > VTBits) { 1882 Lo = DAG.getConstant(0, NVT); 1883 Hi = DAG.getConstant(0, NVT); 1884 } else if (Cst > NVTBits) { 1885 Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy)); 1886 Hi = DAG.getConstant(0, NVT); 1887 } else if (Cst == NVTBits) { 1888 Lo = InH; 1889 Hi = DAG.getConstant(0, NVT); 1890 } else { 1891 Lo = DAG.getNode(ISD::OR, NVT, 1892 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)), 1893 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy))); 1894 Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy)); 1895 } 1896 return true; 1897 case ISD::SRA: 1898 if (Cst > VTBits) { 1899 Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH, 1900 DAG.getConstant(NVTBits-1, ShTy)); 1901 } else if (Cst > NVTBits) { 1902 Lo = DAG.getNode(ISD::SRA, NVT, InH, 1903 DAG.getConstant(Cst-NVTBits, ShTy)); 1904 Hi = DAG.getNode(ISD::SRA, NVT, InH, 1905 DAG.getConstant(NVTBits-1, ShTy)); 1906 } else if (Cst == NVTBits) { 1907 Lo = InH; 1908 Hi = DAG.getNode(ISD::SRA, NVT, InH, 1909 DAG.getConstant(NVTBits-1, ShTy)); 1910 } else { 1911 Lo = DAG.getNode(ISD::OR, NVT, 1912 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)), 1913 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy))); 1914 Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy)); 1915 } 1916 return true; 1917 } 1918 } 1919 // FIXME: The following code for expanding shifts using ISD::SELECT is buggy, 1920 // so disable it for now. Currently targets are handling this via SHL_PARTS 1921 // and friends. 1922 return false; 1923 1924 // If we have an efficient select operation (or if the selects will all fold 1925 // away), lower to some complex code, otherwise just emit the libcall. 1926 if (TLI.getOperationAction(ISD::SELECT, NVT) != TargetLowering::Legal && 1927 !isa<ConstantSDNode>(Amt)) 1928 return false; 1929 1930 SDOperand InL, InH; 1931 ExpandOp(Op, InL, InH); 1932 SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy, // NAmt = 32-ShAmt 1933 DAG.getConstant(NVTBits, ShTy), ShAmt); 1934 1935 // Compare the unmasked shift amount against 32. 1936 SDOperand Cond = DAG.getSetCC(ISD::SETGE, TLI.getSetCCResultTy(), ShAmt, 1937 DAG.getConstant(NVTBits, ShTy)); 1938 1939 if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) { 1940 ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt, // ShAmt &= 31 1941 DAG.getConstant(NVTBits-1, ShTy)); 1942 NAmt = DAG.getNode(ISD::AND, ShTy, NAmt, // NAmt &= 31 1943 DAG.getConstant(NVTBits-1, ShTy)); 1944 } 1945 1946 if (Opc == ISD::SHL) { 1947 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt) 1948 DAG.getNode(ISD::SHL, NVT, InH, ShAmt), 1949 DAG.getNode(ISD::SRL, NVT, InL, NAmt)); 1950 SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31 1951 1952 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1); 1953 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2); 1954 } else { 1955 SDOperand HiLoPart = DAG.getNode(ISD::SELECT, NVT, 1956 DAG.getSetCC(ISD::SETEQ, 1957 TLI.getSetCCResultTy(), NAmt, 1958 DAG.getConstant(32, ShTy)), 1959 DAG.getConstant(0, NVT), 1960 DAG.getNode(ISD::SHL, NVT, InH, NAmt)); 1961 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt) 1962 HiLoPart, 1963 DAG.getNode(ISD::SRL, NVT, InL, ShAmt)); 1964 SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt); // T2 = InH >> ShAmt&31 1965 1966 SDOperand HiPart; 1967 if (Opc == ISD::SRA) 1968 HiPart = DAG.getNode(ISD::SRA, NVT, InH, 1969 DAG.getConstant(NVTBits-1, ShTy)); 1970 else 1971 HiPart = DAG.getConstant(0, NVT); 1972 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1); 1973 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart, T2); 1974 } 1975 return true; 1976} 1977 1978/// FindLatestCallSeqStart - Scan up the dag to find the latest (highest 1979/// NodeDepth) node that is an CallSeqStart operation and occurs later than 1980/// Found. 1981static void FindLatestCallSeqStart(SDNode *Node, SDNode *&Found) { 1982 if (Node->getNodeDepth() <= Found->getNodeDepth()) return; 1983 1984 // If we found an CALLSEQ_START, we already know this node occurs later 1985 // than the Found node. Just remember this node and return. 1986 if (Node->getOpcode() == ISD::CALLSEQ_START) { 1987 Found = Node; 1988 return; 1989 } 1990 1991 // Otherwise, scan the operands of Node to see if any of them is a call. 1992 assert(Node->getNumOperands() != 0 && 1993 "All leaves should have depth equal to the entry node!"); 1994 for (unsigned i = 0, e = Node->getNumOperands()-1; i != e; ++i) 1995 FindLatestCallSeqStart(Node->getOperand(i).Val, Found); 1996 1997 // Tail recurse for the last iteration. 1998 FindLatestCallSeqStart(Node->getOperand(Node->getNumOperands()-1).Val, 1999 Found); 2000} 2001 2002 2003/// FindEarliestCallSeqEnd - Scan down the dag to find the earliest (lowest 2004/// NodeDepth) node that is an CallSeqEnd operation and occurs more recent 2005/// than Found. 2006static void FindEarliestCallSeqEnd(SDNode *Node, SDNode *&Found) { 2007 if (Found && Node->getNodeDepth() >= Found->getNodeDepth()) return; 2008 2009 // If we found an CALLSEQ_END, we already know this node occurs earlier 2010 // than the Found node. Just remember this node and return. 2011 if (Node->getOpcode() == ISD::CALLSEQ_END) { 2012 Found = Node; 2013 return; 2014 } 2015 2016 // Otherwise, scan the operands of Node to see if any of them is a call. 2017 SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); 2018 if (UI == E) return; 2019 for (--E; UI != E; ++UI) 2020 FindEarliestCallSeqEnd(*UI, Found); 2021 2022 // Tail recurse for the last iteration. 2023 FindEarliestCallSeqEnd(*UI, Found); 2024} 2025 2026/// FindCallSeqEnd - Given a chained node that is part of a call sequence, 2027/// find the CALLSEQ_END node that terminates the call sequence. 2028static SDNode *FindCallSeqEnd(SDNode *Node) { 2029 if (Node->getOpcode() == ISD::CALLSEQ_END) 2030 return Node; 2031 if (Node->use_empty()) 2032 return 0; // No CallSeqEnd 2033 2034 if (Node->hasOneUse()) // Simple case, only has one user to check. 2035 return FindCallSeqEnd(*Node->use_begin()); 2036 2037 SDOperand TheChain(Node, Node->getNumValues()-1); 2038 assert(TheChain.getValueType() == MVT::Other && "Is not a token chain!"); 2039 2040 for (SDNode::use_iterator UI = Node->use_begin(), 2041 E = Node->use_end(); ; ++UI) { 2042 assert(UI != E && "Didn't find a user of the tokchain, no CALLSEQ_END!"); 2043 2044 // Make sure to only follow users of our token chain. 2045 SDNode *User = *UI; 2046 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 2047 if (User->getOperand(i) == TheChain) 2048 if (SDNode *Result = FindCallSeqEnd(User)) 2049 return Result; 2050 } 2051 assert(0 && "Unreachable"); 2052 abort(); 2053} 2054 2055/// FindCallSeqStart - Given a chained node that is part of a call sequence, 2056/// find the CALLSEQ_START node that initiates the call sequence. 2057static SDNode *FindCallSeqStart(SDNode *Node) { 2058 assert(Node && "Didn't find callseq_start for a call??"); 2059 if (Node->getOpcode() == ISD::CALLSEQ_START) return Node; 2060 2061 assert(Node->getOperand(0).getValueType() == MVT::Other && 2062 "Node doesn't have a token chain argument!"); 2063 return FindCallSeqStart(Node->getOperand(0).Val); 2064} 2065 2066 2067/// FindInputOutputChains - If we are replacing an operation with a call we need 2068/// to find the call that occurs before and the call that occurs after it to 2069/// properly serialize the calls in the block. The returned operand is the 2070/// input chain value for the new call (e.g. the entry node or the previous 2071/// call), and OutChain is set to be the chain node to update to point to the 2072/// end of the call chain. 2073static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain, 2074 SDOperand Entry) { 2075 SDNode *LatestCallSeqStart = Entry.Val; 2076 SDNode *LatestCallSeqEnd = 0; 2077 FindLatestCallSeqStart(OpNode, LatestCallSeqStart); 2078 //std::cerr<<"Found node: "; LatestCallSeqStart->dump(); std::cerr <<"\n"; 2079 2080 // It is possible that no ISD::CALLSEQ_START was found because there is no 2081 // previous call in the function. LatestCallStackDown may in that case be 2082 // the entry node itself. Do not attempt to find a matching CALLSEQ_END 2083 // unless LatestCallStackDown is an CALLSEQ_START. 2084 if (LatestCallSeqStart->getOpcode() == ISD::CALLSEQ_START) 2085 LatestCallSeqEnd = FindCallSeqEnd(LatestCallSeqStart); 2086 else 2087 LatestCallSeqEnd = Entry.Val; 2088 assert(LatestCallSeqEnd && "NULL return from FindCallSeqEnd"); 2089 2090 // Finally, find the first call that this must come before, first we find the 2091 // CallSeqEnd that ends the call. 2092 OutChain = 0; 2093 FindEarliestCallSeqEnd(OpNode, OutChain); 2094 2095 // If we found one, translate from the adj up to the callseq_start. 2096 if (OutChain) 2097 OutChain = FindCallSeqStart(OutChain); 2098 2099 return SDOperand(LatestCallSeqEnd, 0); 2100} 2101 2102/// SpliceCallInto - Given the result chain of a libcall (CallResult), and a 2103void SelectionDAGLegalize::SpliceCallInto(const SDOperand &CallResult, 2104 SDNode *OutChain) { 2105 // Nothing to splice it into? 2106 if (OutChain == 0) return; 2107 2108 assert(OutChain->getOperand(0).getValueType() == MVT::Other); 2109 //OutChain->dump(); 2110 2111 // Form a token factor node merging the old inval and the new inval. 2112 SDOperand InToken = DAG.getNode(ISD::TokenFactor, MVT::Other, CallResult, 2113 OutChain->getOperand(0)); 2114 // Change the node to refer to the new token. 2115 OutChain->setAdjCallChain(InToken); 2116} 2117 2118 2119// ExpandLibCall - Expand a node into a call to a libcall. If the result value 2120// does not fit into a register, return the lo part and set the hi part to the 2121// by-reg argument. If it does fit into a single register, return the result 2122// and leave the Hi part unset. 2123SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node, 2124 SDOperand &Hi) { 2125 SDNode *OutChain; 2126 SDOperand InChain = FindInputOutputChains(Node, OutChain, 2127 DAG.getEntryNode()); 2128 if (InChain.Val == 0) 2129 InChain = DAG.getEntryNode(); 2130 2131 TargetLowering::ArgListTy Args; 2132 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 2133 MVT::ValueType ArgVT = Node->getOperand(i).getValueType(); 2134 const Type *ArgTy = MVT::getTypeForValueType(ArgVT); 2135 Args.push_back(std::make_pair(Node->getOperand(i), ArgTy)); 2136 } 2137 SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy()); 2138 2139 // Splice the libcall in wherever FindInputOutputChains tells us to. 2140 const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0)); 2141 std::pair<SDOperand,SDOperand> CallInfo = 2142 TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, false, 2143 Callee, Args, DAG); 2144 SpliceCallInto(CallInfo.second, OutChain); 2145 2146 NeedsAnotherIteration = true; 2147 2148 switch (getTypeAction(CallInfo.first.getValueType())) { 2149 default: assert(0 && "Unknown thing"); 2150 case Legal: 2151 return CallInfo.first; 2152 case Promote: 2153 assert(0 && "Cannot promote this yet!"); 2154 case Expand: 2155 SDOperand Lo; 2156 ExpandOp(CallInfo.first, Lo, Hi); 2157 return Lo; 2158 } 2159} 2160 2161 2162/// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the 2163/// destination type is legal. 2164SDOperand SelectionDAGLegalize:: 2165ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) { 2166 assert(getTypeAction(DestTy) == Legal && "Destination type is not legal!"); 2167 assert(getTypeAction(Source.getValueType()) == Expand && 2168 "This is not an expansion!"); 2169 assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!"); 2170 2171 if (!isSigned) { 2172 assert(Source.getValueType() == MVT::i64 && 2173 "This only works for 64-bit -> FP"); 2174 // The 64-bit value loaded will be incorrectly if the 'sign bit' of the 2175 // incoming integer is set. To handle this, we dynamically test to see if 2176 // it is set, and, if so, add a fudge factor. 2177 SDOperand Lo, Hi; 2178 ExpandOp(Source, Lo, Hi); 2179 2180 // If this is unsigned, and not supported, first perform the conversion to 2181 // signed, then adjust the result if the sign bit is set. 2182 SDOperand SignedConv = ExpandIntToFP(true, DestTy, 2183 DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi)); 2184 2185 SDOperand SignSet = DAG.getSetCC(ISD::SETLT, TLI.getSetCCResultTy(), Hi, 2186 DAG.getConstant(0, Hi.getValueType())); 2187 SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4); 2188 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(), 2189 SignSet, Four, Zero); 2190 uint64_t FF = 0x5f800000ULL; 2191 if (TLI.isLittleEndian()) FF <<= 32; 2192 static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF); 2193 2194 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); 2195 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor), 2196 TLI.getPointerTy()); 2197 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset); 2198 SDOperand FudgeInReg; 2199 if (DestTy == MVT::f32) 2200 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, 2201 DAG.getSrcValue(NULL)); 2202 else { 2203 assert(DestTy == MVT::f64 && "Unexpected conversion"); 2204 FudgeInReg = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), 2205 CPIdx, DAG.getSrcValue(NULL), MVT::f32); 2206 } 2207 return DAG.getNode(ISD::ADD, DestTy, SignedConv, FudgeInReg); 2208 } 2209 2210 // Check to see if the target has a custom way to lower this. If so, use it. 2211 switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) { 2212 default: assert(0 && "This action not implemented for this operation!"); 2213 case TargetLowering::Legal: 2214 case TargetLowering::Expand: 2215 break; // This case is handled below. 2216 case TargetLowering::Custom: 2217 Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source); 2218 return LegalizeOp(TLI.LowerOperation(Source, DAG)); 2219 } 2220 2221 // Expand the source, then glue it back together for the call. We must expand 2222 // the source in case it is shared (this pass of legalize must traverse it). 2223 SDOperand SrcLo, SrcHi; 2224 ExpandOp(Source, SrcLo, SrcHi); 2225 Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi); 2226 2227 SDNode *OutChain = 0; 2228 SDOperand InChain = FindInputOutputChains(Source.Val, OutChain, 2229 DAG.getEntryNode()); 2230 const char *FnName = 0; 2231 if (DestTy == MVT::f32) 2232 FnName = "__floatdisf"; 2233 else { 2234 assert(DestTy == MVT::f64 && "Unknown fp value type!"); 2235 FnName = "__floatdidf"; 2236 } 2237 2238 SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy()); 2239 2240 TargetLowering::ArgListTy Args; 2241 const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType()); 2242 2243 Args.push_back(std::make_pair(Source, ArgTy)); 2244 2245 // We don't care about token chains for libcalls. We just use the entry 2246 // node as our input and ignore the output chain. This allows us to place 2247 // calls wherever we need them to satisfy data dependences. 2248 const Type *RetTy = MVT::getTypeForValueType(DestTy); 2249 2250 std::pair<SDOperand,SDOperand> CallResult = 2251 TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, true, 2252 Callee, Args, DAG); 2253 2254 SpliceCallInto(CallResult.second, OutChain); 2255 return CallResult.first; 2256} 2257 2258 2259 2260/// ExpandOp - Expand the specified SDOperand into its two component pieces 2261/// Lo&Hi. Note that the Op MUST be an expanded type. As a result of this, the 2262/// LegalizeNodes map is filled in for any results that are not expanded, the 2263/// ExpandedNodes map is filled in for any results that are expanded, and the 2264/// Lo/Hi values are returned. 2265void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ 2266 MVT::ValueType VT = Op.getValueType(); 2267 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 2268 SDNode *Node = Op.Val; 2269 assert(getTypeAction(VT) == Expand && "Not an expanded type!"); 2270 assert(MVT::isInteger(VT) && "Cannot expand FP values!"); 2271 assert(MVT::isInteger(NVT) && NVT < VT && 2272 "Cannot expand to FP value or to larger int value!"); 2273 2274 // If there is more than one use of this, see if we already expanded it. 2275 // There is no use remembering values that only have a single use, as the map 2276 // entries will never be reused. 2277 if (!Node->hasOneUse()) { 2278 std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I 2279 = ExpandedNodes.find(Op); 2280 if (I != ExpandedNodes.end()) { 2281 Lo = I->second.first; 2282 Hi = I->second.second; 2283 return; 2284 } 2285 } else { 2286 assert(!ExpandedNodes.count(Op) && "Re-expanding a node!"); 2287 } 2288 2289 // Expanding to multiple registers needs to perform an optimization step, and 2290 // is not careful to avoid operations the target does not support. Make sure 2291 // that all generated operations are legalized in the next iteration. 2292 NeedsAnotherIteration = true; 2293 2294 switch (Node->getOpcode()) { 2295 default: 2296 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 2297 assert(0 && "Do not know how to expand this operator!"); 2298 abort(); 2299 case ISD::UNDEF: 2300 Lo = DAG.getNode(ISD::UNDEF, NVT); 2301 Hi = DAG.getNode(ISD::UNDEF, NVT); 2302 break; 2303 case ISD::Constant: { 2304 uint64_t Cst = cast<ConstantSDNode>(Node)->getValue(); 2305 Lo = DAG.getConstant(Cst, NVT); 2306 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT); 2307 break; 2308 } 2309 2310 case ISD::CopyFromReg: { 2311 unsigned Reg = cast<RegSDNode>(Node)->getReg(); 2312 // Aggregate register values are always in consequtive pairs. 2313 Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0)); 2314 Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1)); 2315 2316 // Remember that we legalized the chain. 2317 AddLegalizedOperand(Op.getValue(1), Hi.getValue(1)); 2318 2319 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!"); 2320 break; 2321 } 2322 2323 case ISD::BUILD_PAIR: 2324 // Legalize both operands. FIXME: in the future we should handle the case 2325 // where the two elements are not legal. 2326 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!"); 2327 Lo = LegalizeOp(Node->getOperand(0)); 2328 Hi = LegalizeOp(Node->getOperand(1)); 2329 break; 2330 2331 case ISD::CTPOP: 2332 ExpandOp(Node->getOperand(0), Lo, Hi); 2333 Lo = DAG.getNode(ISD::ADD, NVT, // ctpop(HL) -> ctpop(H)+ctpop(L) 2334 DAG.getNode(ISD::CTPOP, NVT, Lo), 2335 DAG.getNode(ISD::CTPOP, NVT, Hi)); 2336 Hi = DAG.getConstant(0, NVT); 2337 break; 2338 2339 case ISD::CTLZ: { 2340 // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32) 2341 ExpandOp(Node->getOperand(0), Lo, Hi); 2342 SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT); 2343 SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi); 2344 SDOperand TopNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(), 2345 HLZ, BitsC); 2346 SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo); 2347 LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC); 2348 2349 Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart); 2350 Hi = DAG.getConstant(0, NVT); 2351 break; 2352 } 2353 2354 case ISD::CTTZ: { 2355 // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32) 2356 ExpandOp(Node->getOperand(0), Lo, Hi); 2357 SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT); 2358 SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo); 2359 SDOperand BotNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(), 2360 LTZ, BitsC); 2361 SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi); 2362 HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC); 2363 2364 Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart); 2365 Hi = DAG.getConstant(0, NVT); 2366 break; 2367 } 2368 2369 case ISD::LOAD: { 2370 SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 2371 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 2372 Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2)); 2373 2374 // Increment the pointer to the other half. 2375 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 2376 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 2377 getIntPtrConstant(IncrementSize)); 2378 //Is this safe? declaring that the two parts of the split load 2379 //are from the same instruction? 2380 Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2)); 2381 2382 // Build a factor node to remember that this load is independent of the 2383 // other one. 2384 SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), 2385 Hi.getValue(1)); 2386 2387 // Remember that we legalized the chain. 2388 AddLegalizedOperand(Op.getValue(1), TF); 2389 if (!TLI.isLittleEndian()) 2390 std::swap(Lo, Hi); 2391 break; 2392 } 2393 case ISD::TAILCALL: 2394 case ISD::CALL: { 2395 SDOperand Chain = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 2396 SDOperand Callee = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 2397 2398 bool Changed = false; 2399 std::vector<SDOperand> Ops; 2400 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) { 2401 Ops.push_back(LegalizeOp(Node->getOperand(i))); 2402 Changed |= Ops.back() != Node->getOperand(i); 2403 } 2404 2405 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 2406 "Can only expand a call once so far, not i64 -> i16!"); 2407 2408 std::vector<MVT::ValueType> RetTyVTs; 2409 RetTyVTs.reserve(3); 2410 RetTyVTs.push_back(NVT); 2411 RetTyVTs.push_back(NVT); 2412 RetTyVTs.push_back(MVT::Other); 2413 SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops, 2414 Node->getOpcode() == ISD::TAILCALL); 2415 Lo = SDOperand(NC, 0); 2416 Hi = SDOperand(NC, 1); 2417 2418 // Insert the new chain mapping. 2419 AddLegalizedOperand(Op.getValue(1), Hi.getValue(2)); 2420 break; 2421 } 2422 case ISD::AND: 2423 case ISD::OR: 2424 case ISD::XOR: { // Simple logical operators -> two trivial pieces. 2425 SDOperand LL, LH, RL, RH; 2426 ExpandOp(Node->getOperand(0), LL, LH); 2427 ExpandOp(Node->getOperand(1), RL, RH); 2428 Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL); 2429 Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH); 2430 break; 2431 } 2432 case ISD::SELECT: { 2433 SDOperand C, LL, LH, RL, RH; 2434 2435 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2436 case Expand: assert(0 && "It's impossible to expand bools"); 2437 case Legal: 2438 C = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 2439 break; 2440 case Promote: 2441 C = PromoteOp(Node->getOperand(0)); // Promote the condition. 2442 break; 2443 } 2444 ExpandOp(Node->getOperand(1), LL, LH); 2445 ExpandOp(Node->getOperand(2), RL, RH); 2446 Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL); 2447 Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH); 2448 break; 2449 } 2450 case ISD::SIGN_EXTEND: { 2451 SDOperand In; 2452 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2453 case Expand: assert(0 && "expand-expand not implemented yet!"); 2454 case Legal: In = LegalizeOp(Node->getOperand(0)); break; 2455 case Promote: 2456 In = PromoteOp(Node->getOperand(0)); 2457 // Emit the appropriate sign_extend_inreg to get the value we want. 2458 In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(), In, 2459 Node->getOperand(0).getValueType()); 2460 break; 2461 } 2462 2463 // The low part is just a sign extension of the input (which degenerates to 2464 // a copy). 2465 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, In); 2466 2467 // The high part is obtained by SRA'ing all but one of the bits of the lo 2468 // part. 2469 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); 2470 Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, 2471 TLI.getShiftAmountTy())); 2472 break; 2473 } 2474 case ISD::ZERO_EXTEND: { 2475 SDOperand In; 2476 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2477 case Expand: assert(0 && "expand-expand not implemented yet!"); 2478 case Legal: In = LegalizeOp(Node->getOperand(0)); break; 2479 case Promote: 2480 In = PromoteOp(Node->getOperand(0)); 2481 // Emit the appropriate zero_extend_inreg to get the value we want. 2482 In = DAG.getZeroExtendInReg(In, Node->getOperand(0).getValueType()); 2483 break; 2484 } 2485 2486 // The low part is just a zero extension of the input (which degenerates to 2487 // a copy). 2488 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, In); 2489 2490 // The high part is just a zero. 2491 Hi = DAG.getConstant(0, NVT); 2492 break; 2493 } 2494 // These operators cannot be expanded directly, emit them as calls to 2495 // library functions. 2496 case ISD::FP_TO_SINT: 2497 if (Node->getOperand(0).getValueType() == MVT::f32) 2498 Lo = ExpandLibCall("__fixsfdi", Node, Hi); 2499 else 2500 Lo = ExpandLibCall("__fixdfdi", Node, Hi); 2501 break; 2502 case ISD::FP_TO_UINT: 2503 if (Node->getOperand(0).getValueType() == MVT::f32) 2504 Lo = ExpandLibCall("__fixunssfdi", Node, Hi); 2505 else 2506 Lo = ExpandLibCall("__fixunsdfdi", Node, Hi); 2507 break; 2508 2509 case ISD::SHL: 2510 // If we can emit an efficient shift operation, do so now. 2511 if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 2512 break; 2513 2514 // If this target supports SHL_PARTS, use it. 2515 if (TLI.getOperationAction(ISD::SHL_PARTS, NVT) == TargetLowering::Legal) { 2516 ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), Node->getOperand(1), 2517 Lo, Hi); 2518 break; 2519 } 2520 2521 // Otherwise, emit a libcall. 2522 Lo = ExpandLibCall("__ashldi3", Node, Hi); 2523 break; 2524 2525 case ISD::SRA: 2526 // If we can emit an efficient shift operation, do so now. 2527 if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 2528 break; 2529 2530 // If this target supports SRA_PARTS, use it. 2531 if (TLI.getOperationAction(ISD::SRA_PARTS, NVT) == TargetLowering::Legal) { 2532 ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), Node->getOperand(1), 2533 Lo, Hi); 2534 break; 2535 } 2536 2537 // Otherwise, emit a libcall. 2538 Lo = ExpandLibCall("__ashrdi3", Node, Hi); 2539 break; 2540 case ISD::SRL: 2541 // If we can emit an efficient shift operation, do so now. 2542 if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 2543 break; 2544 2545 // If this target supports SRL_PARTS, use it. 2546 if (TLI.getOperationAction(ISD::SRL_PARTS, NVT) == TargetLowering::Legal) { 2547 ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), Node->getOperand(1), 2548 Lo, Hi); 2549 break; 2550 } 2551 2552 // Otherwise, emit a libcall. 2553 Lo = ExpandLibCall("__lshrdi3", Node, Hi); 2554 break; 2555 2556 case ISD::ADD: 2557 ExpandByParts(ISD::ADD_PARTS, Node->getOperand(0), Node->getOperand(1), 2558 Lo, Hi); 2559 break; 2560 case ISD::SUB: 2561 ExpandByParts(ISD::SUB_PARTS, Node->getOperand(0), Node->getOperand(1), 2562 Lo, Hi); 2563 break; 2564 case ISD::MUL: { 2565 if (TLI.getOperationAction(ISD::MULHU, NVT) == TargetLowering::Legal) { 2566 SDOperand LL, LH, RL, RH; 2567 ExpandOp(Node->getOperand(0), LL, LH); 2568 ExpandOp(Node->getOperand(1), RL, RH); 2569 Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL); 2570 RH = DAG.getNode(ISD::MUL, NVT, LL, RH); 2571 LH = DAG.getNode(ISD::MUL, NVT, LH, RL); 2572 Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH); 2573 Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH); 2574 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL); 2575 } else { 2576 Lo = ExpandLibCall("__muldi3" , Node, Hi); break; 2577 } 2578 break; 2579 } 2580 case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break; 2581 case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break; 2582 case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break; 2583 case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break; 2584 } 2585 2586 // Remember in a map if the values will be reused later. 2587 if (!Node->hasOneUse()) { 2588 bool isNew = ExpandedNodes.insert(std::make_pair(Op, 2589 std::make_pair(Lo, Hi))).second; 2590 assert(isNew && "Value already expanded?!?"); 2591 } 2592} 2593 2594 2595// SelectionDAG::Legalize - This is the entry point for the file. 2596// 2597void SelectionDAG::Legalize() { 2598 /// run - This is the main entry point to this class. 2599 /// 2600 SelectionDAGLegalize(*this).Run(); 2601} 2602 2603