LegalizeDAG.cpp revision fc1b1dad88a256ab5ab16dd548ad82df8efa2ca9
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/Constants.h" 22#include <iostream> 23using namespace llvm; 24 25//===----------------------------------------------------------------------===// 26/// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and 27/// hacks on it until the target machine can handle it. This involves 28/// eliminating value sizes the machine cannot handle (promoting small sizes to 29/// large sizes or splitting up large values into small values) as well as 30/// eliminating operations the machine cannot handle. 31/// 32/// This code also does a small amount of optimization and recognition of idioms 33/// as part of its processing. For example, if a target does not support a 34/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this 35/// will attempt merge setcc and brc instructions into brcc's. 36/// 37namespace { 38class SelectionDAGLegalize { 39 TargetLowering &TLI; 40 SelectionDAG &DAG; 41 42 /// LegalizeAction - This enum indicates what action we should take for each 43 /// value type the can occur in the program. 44 enum LegalizeAction { 45 Legal, // The target natively supports this value type. 46 Promote, // This should be promoted to the next larger type. 47 Expand, // This integer type should be broken into smaller pieces. 48 }; 49 50 /// ValueTypeActions - This is a bitvector that contains two bits for each 51 /// value type, where the two bits correspond to the LegalizeAction enum. 52 /// This can be queried with "getTypeAction(VT)". 53 unsigned ValueTypeActions; 54 55 /// NeedsAnotherIteration - This is set when we expand a large integer 56 /// operation into smaller integer operations, but the smaller operations are 57 /// not set. This occurs only rarely in practice, for targets that don't have 58 /// 32-bit or larger integer registers. 59 bool NeedsAnotherIteration; 60 61 /// LegalizedNodes - For nodes that are of legal width, and that have more 62 /// than one use, this map indicates what regularized operand to use. This 63 /// allows us to avoid legalizing the same thing more than once. 64 std::map<SDOperand, SDOperand> LegalizedNodes; 65 66 /// PromotedNodes - For nodes that are below legal width, and that have more 67 /// than one use, this map indicates what promoted value to use. This allows 68 /// us to avoid promoting the same thing more than once. 69 std::map<SDOperand, SDOperand> PromotedNodes; 70 71 /// ExpandedNodes - For nodes that need to be expanded, and which have more 72 /// than one use, this map indicates which which operands are the expanded 73 /// version of the input. This allows us to avoid expanding the same node 74 /// more than once. 75 std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes; 76 77 void AddLegalizedOperand(SDOperand From, SDOperand To) { 78 bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second; 79 assert(isNew && "Got into the map somehow?"); 80 } 81 void AddPromotedOperand(SDOperand From, SDOperand To) { 82 bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second; 83 assert(isNew && "Got into the map somehow?"); 84 } 85 86public: 87 88 SelectionDAGLegalize(SelectionDAG &DAG); 89 90 /// Run - While there is still lowering to do, perform a pass over the DAG. 91 /// Most regularization can be done in a single pass, but targets that require 92 /// large values to be split into registers multiple times (e.g. i64 -> 4x 93 /// i16) require iteration for these values (the first iteration will demote 94 /// to i32, the second will demote to i16). 95 void Run() { 96 do { 97 NeedsAnotherIteration = false; 98 LegalizeDAG(); 99 } while (NeedsAnotherIteration); 100 } 101 102 /// getTypeAction - Return how we should legalize values of this type, either 103 /// it is already legal or we need to expand it into multiple registers of 104 /// smaller integer type, or we need to promote it to a larger type. 105 LegalizeAction getTypeAction(MVT::ValueType VT) const { 106 return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3); 107 } 108 109 /// isTypeLegal - Return true if this type is legal on this target. 110 /// 111 bool isTypeLegal(MVT::ValueType VT) const { 112 return getTypeAction(VT) == Legal; 113 } 114 115private: 116 void LegalizeDAG(); 117 118 SDOperand LegalizeOp(SDOperand O); 119 void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi); 120 SDOperand PromoteOp(SDOperand O); 121 122 SDOperand ExpandLibCall(const char *Name, SDNode *Node, 123 SDOperand &Hi); 124 SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, 125 SDOperand Source); 126 bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt, 127 SDOperand &Lo, SDOperand &Hi); 128 void ExpandAddSub(bool isAdd, SDOperand Op, SDOperand Amt, 129 SDOperand &Lo, SDOperand &Hi); 130 131 SDOperand getIntPtrConstant(uint64_t Val) { 132 return DAG.getConstant(Val, TLI.getPointerTy()); 133 } 134}; 135} 136 137 138SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag) 139 : TLI(dag.getTargetLoweringInfo()), DAG(dag), 140 ValueTypeActions(TLI.getValueTypeActions()) { 141 assert(MVT::LAST_VALUETYPE <= 16 && 142 "Too many value types for ValueTypeActions to hold!"); 143} 144 145void SelectionDAGLegalize::LegalizeDAG() { 146 SDOperand OldRoot = DAG.getRoot(); 147 SDOperand NewRoot = LegalizeOp(OldRoot); 148 DAG.setRoot(NewRoot); 149 150 ExpandedNodes.clear(); 151 LegalizedNodes.clear(); 152 PromotedNodes.clear(); 153 154 // Remove dead nodes now. 155 DAG.RemoveDeadNodes(OldRoot.Val); 156} 157 158SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { 159 assert(getTypeAction(Op.getValueType()) == Legal && 160 "Caller should expand or promote operands that are not legal!"); 161 162 // If this operation defines any values that cannot be represented in a 163 // register on this target, make sure to expand or promote them. 164 if (Op.Val->getNumValues() > 1) { 165 for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i) 166 switch (getTypeAction(Op.Val->getValueType(i))) { 167 case Legal: break; // Nothing to do. 168 case Expand: { 169 SDOperand T1, T2; 170 ExpandOp(Op.getValue(i), T1, T2); 171 assert(LegalizedNodes.count(Op) && 172 "Expansion didn't add legal operands!"); 173 return LegalizedNodes[Op]; 174 } 175 case Promote: 176 PromoteOp(Op.getValue(i)); 177 assert(LegalizedNodes.count(Op) && 178 "Expansion didn't add legal operands!"); 179 return LegalizedNodes[Op]; 180 } 181 } 182 183 std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op); 184 if (I != LegalizedNodes.end()) return I->second; 185 186 SDOperand Tmp1, Tmp2, Tmp3; 187 188 SDOperand Result = Op; 189 SDNode *Node = Op.Val; 190 191 switch (Node->getOpcode()) { 192 default: 193 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 194 assert(0 && "Do not know how to legalize this operator!"); 195 abort(); 196 case ISD::EntryToken: 197 case ISD::FrameIndex: 198 case ISD::GlobalAddress: 199 case ISD::ExternalSymbol: 200 case ISD::ConstantPool: // Nothing to do. 201 assert(getTypeAction(Node->getValueType(0)) == Legal && 202 "This must be legal!"); 203 break; 204 case ISD::CopyFromReg: 205 Tmp1 = LegalizeOp(Node->getOperand(0)); 206 if (Tmp1 != Node->getOperand(0)) 207 Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), 208 Node->getValueType(0), Tmp1); 209 else 210 Result = Op.getValue(0); 211 212 // Since CopyFromReg produces two values, make sure to remember that we 213 // legalized both of them. 214 AddLegalizedOperand(Op.getValue(0), Result); 215 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 216 return Result.getValue(Op.ResNo); 217 case ISD::ImplicitDef: 218 Tmp1 = LegalizeOp(Node->getOperand(0)); 219 if (Tmp1 != Node->getOperand(0)) 220 Result = DAG.getImplicitDef(Tmp1, cast<RegSDNode>(Node)->getReg()); 221 break; 222 case ISD::UNDEF: { 223 MVT::ValueType VT = Op.getValueType(); 224 switch (TLI.getOperationAction(ISD::UNDEF, VT)) { 225 case Expand: 226 case Promote: 227 if (MVT::isInteger(VT)) 228 Result = DAG.getConstant(0, VT); 229 else if (MVT::isFloatingPoint(VT)) 230 Result = DAG.getConstantFP(0, VT); 231 else 232 assert(0 && "Unknown value type!"); 233 break; 234 case Legal: 235 break; 236 } 237 break; 238 } 239 case ISD::Constant: 240 // We know we don't need to expand constants here, constants only have one 241 // value and we check that it is fine above. 242 243 // FIXME: Maybe we should handle things like targets that don't support full 244 // 32-bit immediates? 245 break; 246 case ISD::ConstantFP: { 247 // Spill FP immediates to the constant pool if the target cannot directly 248 // codegen them. Targets often have some immediate values that can be 249 // efficiently generated into an FP register without a load. We explicitly 250 // leave these constants as ConstantFP nodes for the target to deal with. 251 252 ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node); 253 254 // Check to see if this FP immediate is already legal. 255 bool isLegal = false; 256 for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(), 257 E = TLI.legal_fpimm_end(); I != E; ++I) 258 if (CFP->isExactlyValue(*I)) { 259 isLegal = true; 260 break; 261 } 262 263 if (!isLegal) { 264 // Otherwise we need to spill the constant to memory. 265 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); 266 267 bool Extend = false; 268 269 // If a FP immediate is precise when represented as a float, we put it 270 // into the constant pool as a float, even if it's is statically typed 271 // as a double. 272 MVT::ValueType VT = CFP->getValueType(0); 273 bool isDouble = VT == MVT::f64; 274 ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy : 275 Type::FloatTy, CFP->getValue()); 276 if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) && 277 // Only do this if the target has a native EXTLOAD instruction from 278 // f32. 279 TLI.getOperationAction(ISD::EXTLOAD, 280 MVT::f32) == TargetLowering::Legal) { 281 LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy)); 282 VT = MVT::f32; 283 Extend = true; 284 } 285 286 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC), 287 TLI.getPointerTy()); 288 if (Extend) { 289 Result = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), CPIdx, 290 MVT::f32); 291 } else { 292 Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx); 293 } 294 } 295 break; 296 } 297 case ISD::TokenFactor: { 298 std::vector<SDOperand> Ops; 299 bool Changed = false; 300 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 301 SDOperand Op = Node->getOperand(i); 302 // Fold single-use TokenFactor nodes into this token factor as we go. 303 if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) { 304 Changed = true; 305 for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j) 306 Ops.push_back(LegalizeOp(Op.getOperand(j))); 307 } else { 308 Ops.push_back(LegalizeOp(Op)); // Legalize the operands 309 Changed |= Ops[i] != Op; 310 } 311 } 312 if (Changed) 313 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops); 314 break; 315 } 316 317 case ISD::ADJCALLSTACKDOWN: 318 case ISD::ADJCALLSTACKUP: 319 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 320 // There is no need to legalize the size argument (Operand #1) 321 if (Tmp1 != Node->getOperand(0)) 322 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, 323 Node->getOperand(1)); 324 break; 325 case ISD::DYNAMIC_STACKALLOC: 326 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 327 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the size. 328 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the alignment. 329 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 330 Tmp3 != Node->getOperand(2)) 331 Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0), 332 Tmp1, Tmp2, Tmp3); 333 else 334 Result = Op.getValue(0); 335 336 // Since this op produces two values, make sure to remember that we 337 // legalized both of them. 338 AddLegalizedOperand(SDOperand(Node, 0), Result); 339 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 340 return Result.getValue(Op.ResNo); 341 342 case ISD::CALL: { 343 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 344 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 345 346 bool Changed = false; 347 std::vector<SDOperand> Ops; 348 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) { 349 Ops.push_back(LegalizeOp(Node->getOperand(i))); 350 Changed |= Ops.back() != Node->getOperand(i); 351 } 352 353 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) { 354 std::vector<MVT::ValueType> RetTyVTs; 355 RetTyVTs.reserve(Node->getNumValues()); 356 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 357 RetTyVTs.push_back(Node->getValueType(i)); 358 Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops), 0); 359 } else { 360 Result = Result.getValue(0); 361 } 362 // Since calls produce multiple values, make sure to remember that we 363 // legalized all of them. 364 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 365 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 366 return Result.getValue(Op.ResNo); 367 } 368 case ISD::BR: 369 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 370 if (Tmp1 != Node->getOperand(0)) 371 Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1)); 372 break; 373 374 case ISD::BRCOND: 375 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 376 377 switch (getTypeAction(Node->getOperand(1).getValueType())) { 378 case Expand: assert(0 && "It's impossible to expand bools"); 379 case Legal: 380 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 381 break; 382 case Promote: 383 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition. 384 break; 385 } 386 // Basic block destination (Op#2) is always legal. 387 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 388 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 389 Node->getOperand(2)); 390 break; 391 392 case ISD::LOAD: 393 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 394 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 395 if (Tmp1 != Node->getOperand(0) || 396 Tmp2 != Node->getOperand(1)) 397 Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2); 398 else 399 Result = SDOperand(Node, 0); 400 401 // Since loads produce two values, make sure to remember that we legalized 402 // both of them. 403 AddLegalizedOperand(SDOperand(Node, 0), Result); 404 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 405 return Result.getValue(Op.ResNo); 406 407 case ISD::EXTLOAD: 408 case ISD::SEXTLOAD: 409 case ISD::ZEXTLOAD: 410 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 411 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 412 if (Tmp1 != Node->getOperand(0) || 413 Tmp2 != Node->getOperand(1)) 414 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, Tmp2, 415 cast<MVTSDNode>(Node)->getExtraValueType()); 416 else 417 Result = SDOperand(Node, 0); 418 419 // Since loads produce two values, make sure to remember that we legalized 420 // both of them. 421 AddLegalizedOperand(SDOperand(Node, 0), Result); 422 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 423 return Result.getValue(Op.ResNo); 424 425 case ISD::EXTRACT_ELEMENT: 426 // Get both the low and high parts. 427 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 428 if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) 429 Result = Tmp2; // 1 -> Hi 430 else 431 Result = Tmp1; // 0 -> Lo 432 break; 433 434 case ISD::CopyToReg: 435 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 436 437 switch (getTypeAction(Node->getOperand(1).getValueType())) { 438 case Legal: 439 // Legalize the incoming value (must be legal). 440 Tmp2 = LegalizeOp(Node->getOperand(1)); 441 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 442 Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg()); 443 break; 444 case Promote: 445 Tmp2 = PromoteOp(Node->getOperand(1)); 446 Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg()); 447 break; 448 case Expand: 449 SDOperand Lo, Hi; 450 ExpandOp(Node->getOperand(1), Lo, Hi); 451 unsigned Reg = cast<RegSDNode>(Node)->getReg(); 452 Lo = DAG.getCopyToReg(Tmp1, Lo, Reg); 453 Hi = DAG.getCopyToReg(Tmp1, Hi, Reg+1); 454 // Note that the copytoreg nodes are independent of each other. 455 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); 456 assert(isTypeLegal(Result.getValueType()) && 457 "Cannot expand multiple times yet (i64 -> i16)"); 458 break; 459 } 460 break; 461 462 case ISD::RET: 463 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 464 switch (Node->getNumOperands()) { 465 case 2: // ret val 466 switch (getTypeAction(Node->getOperand(1).getValueType())) { 467 case Legal: 468 Tmp2 = LegalizeOp(Node->getOperand(1)); 469 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 470 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 471 break; 472 case Expand: { 473 SDOperand Lo, Hi; 474 ExpandOp(Node->getOperand(1), Lo, Hi); 475 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi); 476 break; 477 } 478 case Promote: 479 Tmp2 = PromoteOp(Node->getOperand(1)); 480 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 481 break; 482 } 483 break; 484 case 1: // ret void 485 if (Tmp1 != Node->getOperand(0)) 486 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1); 487 break; 488 default: { // ret <values> 489 std::vector<SDOperand> NewValues; 490 NewValues.push_back(Tmp1); 491 for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) 492 switch (getTypeAction(Node->getOperand(i).getValueType())) { 493 case Legal: 494 NewValues.push_back(LegalizeOp(Node->getOperand(i))); 495 break; 496 case Expand: { 497 SDOperand Lo, Hi; 498 ExpandOp(Node->getOperand(i), Lo, Hi); 499 NewValues.push_back(Lo); 500 NewValues.push_back(Hi); 501 break; 502 } 503 case Promote: 504 assert(0 && "Can't promote multiple return value yet!"); 505 } 506 Result = DAG.getNode(ISD::RET, MVT::Other, NewValues); 507 break; 508 } 509 } 510 break; 511 case ISD::STORE: 512 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 513 Tmp2 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 514 515 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 516 if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){ 517 if (CFP->getValueType(0) == MVT::f32) { 518 union { 519 unsigned I; 520 float F; 521 } V; 522 V.F = CFP->getValue(); 523 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 524 DAG.getConstant(V.I, MVT::i32), Tmp2); 525 } else { 526 assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!"); 527 union { 528 uint64_t I; 529 double F; 530 } V; 531 V.F = CFP->getValue(); 532 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 533 DAG.getConstant(V.I, MVT::i64), Tmp2); 534 } 535 Node = Result.Val; 536 } 537 538 switch (getTypeAction(Node->getOperand(1).getValueType())) { 539 case Legal: { 540 SDOperand Val = LegalizeOp(Node->getOperand(1)); 541 if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) || 542 Tmp2 != Node->getOperand(2)) 543 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2); 544 break; 545 } 546 case Promote: 547 // Truncate the value and store the result. 548 Tmp3 = PromoteOp(Node->getOperand(1)); 549 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2, 550 Node->getOperand(1).getValueType()); 551 break; 552 553 case Expand: 554 SDOperand Lo, Hi; 555 ExpandOp(Node->getOperand(1), Lo, Hi); 556 557 if (!TLI.isLittleEndian()) 558 std::swap(Lo, Hi); 559 560 Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2); 561 562 unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8; 563 Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2, 564 getIntPtrConstant(IncrementSize)); 565 assert(isTypeLegal(Tmp2.getValueType()) && 566 "Pointers must be legal!"); 567 Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2); 568 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); 569 break; 570 } 571 break; 572 case ISD::PCMARKER: 573 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 574 Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1, Node->getOperand(1)); 575 break; 576 case ISD::TRUNCSTORE: 577 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 578 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 579 580 switch (getTypeAction(Node->getOperand(1).getValueType())) { 581 case Legal: 582 Tmp2 = LegalizeOp(Node->getOperand(1)); 583 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 584 Tmp3 != Node->getOperand(2)) 585 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3, 586 cast<MVTSDNode>(Node)->getExtraValueType()); 587 break; 588 case Promote: 589 case Expand: 590 assert(0 && "Cannot handle illegal TRUNCSTORE yet!"); 591 } 592 break; 593 case ISD::SELECT: 594 switch (getTypeAction(Node->getOperand(0).getValueType())) { 595 case Expand: assert(0 && "It's impossible to expand bools"); 596 case Legal: 597 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 598 break; 599 case Promote: 600 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 601 break; 602 } 603 Tmp2 = LegalizeOp(Node->getOperand(1)); // TrueVal 604 Tmp3 = LegalizeOp(Node->getOperand(2)); // FalseVal 605 606 switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) { 607 default: assert(0 && "This action is not supported yet!"); 608 case TargetLowering::Legal: 609 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 610 Tmp3 != Node->getOperand(2)) 611 Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), 612 Tmp1, Tmp2, Tmp3); 613 break; 614 case TargetLowering::Promote: { 615 MVT::ValueType NVT = 616 TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType()); 617 unsigned ExtOp, TruncOp; 618 if (MVT::isInteger(Tmp2.getValueType())) { 619 ExtOp = ISD::ZERO_EXTEND; 620 TruncOp = ISD::TRUNCATE; 621 } else { 622 ExtOp = ISD::FP_EXTEND; 623 TruncOp = ISD::FP_ROUND; 624 } 625 // Promote each of the values to the new type. 626 Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2); 627 Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3); 628 // Perform the larger operation, then round down. 629 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3); 630 Result = DAG.getNode(TruncOp, Node->getValueType(0), Result); 631 break; 632 } 633 } 634 break; 635 case ISD::SETCC: 636 switch (getTypeAction(Node->getOperand(0).getValueType())) { 637 case Legal: 638 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 639 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 640 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 641 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 642 Node->getValueType(0), Tmp1, Tmp2); 643 break; 644 case Promote: 645 Tmp1 = PromoteOp(Node->getOperand(0)); // LHS 646 Tmp2 = PromoteOp(Node->getOperand(1)); // RHS 647 648 // If this is an FP compare, the operands have already been extended. 649 if (MVT::isInteger(Node->getOperand(0).getValueType())) { 650 MVT::ValueType VT = Node->getOperand(0).getValueType(); 651 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 652 653 // Otherwise, we have to insert explicit sign or zero extends. Note 654 // that we could insert sign extends for ALL conditions, but zero extend 655 // is cheaper on many machines (an AND instead of two shifts), so prefer 656 // it. 657 switch (cast<SetCCSDNode>(Node)->getCondition()) { 658 default: assert(0 && "Unknown integer comparison!"); 659 case ISD::SETEQ: 660 case ISD::SETNE: 661 case ISD::SETUGE: 662 case ISD::SETUGT: 663 case ISD::SETULE: 664 case ISD::SETULT: 665 // ALL of these operations will work if we either sign or zero extend 666 // the operands (including the unsigned comparisons!). Zero extend is 667 // usually a simpler/cheaper operation, so prefer it. 668 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT); 669 Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT); 670 break; 671 case ISD::SETGE: 672 case ISD::SETGT: 673 case ISD::SETLT: 674 case ISD::SETLE: 675 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT); 676 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT); 677 break; 678 } 679 680 } 681 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 682 Node->getValueType(0), Tmp1, Tmp2); 683 break; 684 case Expand: 685 SDOperand LHSLo, LHSHi, RHSLo, RHSHi; 686 ExpandOp(Node->getOperand(0), LHSLo, LHSHi); 687 ExpandOp(Node->getOperand(1), RHSLo, RHSHi); 688 switch (cast<SetCCSDNode>(Node)->getCondition()) { 689 case ISD::SETEQ: 690 case ISD::SETNE: 691 Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo); 692 Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi); 693 Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2); 694 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 695 Node->getValueType(0), Tmp1, 696 DAG.getConstant(0, Tmp1.getValueType())); 697 break; 698 default: 699 // FIXME: This generated code sucks. 700 ISD::CondCode LowCC; 701 switch (cast<SetCCSDNode>(Node)->getCondition()) { 702 default: assert(0 && "Unknown integer setcc!"); 703 case ISD::SETLT: 704 case ISD::SETULT: LowCC = ISD::SETULT; break; 705 case ISD::SETGT: 706 case ISD::SETUGT: LowCC = ISD::SETUGT; break; 707 case ISD::SETLE: 708 case ISD::SETULE: LowCC = ISD::SETULE; break; 709 case ISD::SETGE: 710 case ISD::SETUGE: LowCC = ISD::SETUGE; break; 711 } 712 713 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison 714 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands 715 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2; 716 717 // NOTE: on targets without efficient SELECT of bools, we can always use 718 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3) 719 Tmp1 = DAG.getSetCC(LowCC, Node->getValueType(0), LHSLo, RHSLo); 720 Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 721 Node->getValueType(0), LHSHi, RHSHi); 722 Result = DAG.getSetCC(ISD::SETEQ, Node->getValueType(0), LHSHi, RHSHi); 723 Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(), 724 Result, Tmp1, Tmp2); 725 break; 726 } 727 } 728 break; 729 730 case ISD::MEMSET: 731 case ISD::MEMCPY: 732 case ISD::MEMMOVE: { 733 Tmp1 = LegalizeOp(Node->getOperand(0)); // Chain 734 Tmp2 = LegalizeOp(Node->getOperand(1)); // Pointer 735 736 if (Node->getOpcode() == ISD::MEMSET) { // memset = ubyte 737 switch (getTypeAction(Node->getOperand(2).getValueType())) { 738 case Expand: assert(0 && "Cannot expand a byte!"); 739 case Legal: 740 Tmp3 = LegalizeOp(Node->getOperand(2)); 741 break; 742 case Promote: 743 Tmp3 = PromoteOp(Node->getOperand(2)); 744 break; 745 } 746 } else { 747 Tmp3 = LegalizeOp(Node->getOperand(2)); // memcpy/move = pointer, 748 } 749 750 SDOperand Tmp4; 751 switch (getTypeAction(Node->getOperand(3).getValueType())) { 752 case Expand: assert(0 && "Cannot expand this yet!"); 753 case Legal: 754 Tmp4 = LegalizeOp(Node->getOperand(3)); 755 break; 756 case Promote: 757 Tmp4 = PromoteOp(Node->getOperand(3)); 758 break; 759 } 760 761 SDOperand Tmp5; 762 switch (getTypeAction(Node->getOperand(4).getValueType())) { // uint 763 case Expand: assert(0 && "Cannot expand this yet!"); 764 case Legal: 765 Tmp5 = LegalizeOp(Node->getOperand(4)); 766 break; 767 case Promote: 768 Tmp5 = PromoteOp(Node->getOperand(4)); 769 break; 770 } 771 772 switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) { 773 default: assert(0 && "This action not implemented for this operation!"); 774 case TargetLowering::Legal: 775 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 776 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) || 777 Tmp5 != Node->getOperand(4)) { 778 std::vector<SDOperand> Ops; 779 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 780 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 781 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 782 } 783 break; 784 case TargetLowering::Expand: { 785 // Otherwise, the target does not support this operation. Lower the 786 // operation to an explicit libcall as appropriate. 787 MVT::ValueType IntPtr = TLI.getPointerTy(); 788 const Type *IntPtrTy = TLI.getTargetData().getIntPtrType(); 789 std::vector<std::pair<SDOperand, const Type*> > Args; 790 791 const char *FnName = 0; 792 if (Node->getOpcode() == ISD::MEMSET) { 793 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 794 // Extend the ubyte argument to be an int value for the call. 795 Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3); 796 Args.push_back(std::make_pair(Tmp3, Type::IntTy)); 797 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 798 799 FnName = "memset"; 800 } else if (Node->getOpcode() == ISD::MEMCPY || 801 Node->getOpcode() == ISD::MEMMOVE) { 802 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 803 Args.push_back(std::make_pair(Tmp3, IntPtrTy)); 804 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 805 FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy"; 806 } else { 807 assert(0 && "Unknown op!"); 808 } 809 std::pair<SDOperand,SDOperand> CallResult = 810 TLI.LowerCallTo(Tmp1, Type::VoidTy, false, 811 DAG.getExternalSymbol(FnName, IntPtr), Args, DAG); 812 Result = LegalizeOp(CallResult.second); 813 break; 814 } 815 case TargetLowering::Custom: 816 std::vector<SDOperand> Ops; 817 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 818 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 819 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 820 Result = TLI.LowerOperation(Result); 821 Result = LegalizeOp(Result); 822 break; 823 } 824 break; 825 } 826 case ISD::ADD_PARTS: 827 case ISD::SUB_PARTS: { 828 std::vector<SDOperand> Ops; 829 bool Changed = false; 830 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 831 Ops.push_back(LegalizeOp(Node->getOperand(i))); 832 Changed |= Ops.back() != Node->getOperand(i); 833 } 834 if (Changed) 835 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops); 836 break; 837 } 838 case ISD::ADD: 839 case ISD::SUB: 840 case ISD::MUL: 841 case ISD::UDIV: 842 case ISD::SDIV: 843 case ISD::UREM: 844 case ISD::SREM: 845 case ISD::AND: 846 case ISD::OR: 847 case ISD::XOR: 848 case ISD::SHL: 849 case ISD::SRL: 850 case ISD::SRA: 851 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 852 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 853 if (Tmp1 != Node->getOperand(0) || 854 Tmp2 != Node->getOperand(1)) 855 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2); 856 break; 857 case ISD::ZERO_EXTEND: 858 case ISD::SIGN_EXTEND: 859 case ISD::TRUNCATE: 860 case ISD::FP_EXTEND: 861 case ISD::FP_ROUND: 862 case ISD::FP_TO_SINT: 863 case ISD::FP_TO_UINT: 864 case ISD::SINT_TO_FP: 865 case ISD::UINT_TO_FP: 866 switch (getTypeAction(Node->getOperand(0).getValueType())) { 867 case Legal: 868 Tmp1 = LegalizeOp(Node->getOperand(0)); 869 if (Tmp1 != Node->getOperand(0)) 870 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 871 break; 872 case Expand: 873 if (Node->getOpcode() == ISD::SINT_TO_FP || 874 Node->getOpcode() == ISD::UINT_TO_FP) { 875 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, 876 Node->getValueType(0), Node->getOperand(0)); 877 Result = LegalizeOp(Result); 878 break; 879 } 880 // In the expand case, we must be dealing with a truncate, because 881 // otherwise the result would be larger than the source. 882 assert(Node->getOpcode() == ISD::TRUNCATE && 883 "Shouldn't need to expand other operators here!"); 884 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 885 886 // Since the result is legal, we should just be able to truncate the low 887 // part of the source. 888 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1); 889 break; 890 891 case Promote: 892 switch (Node->getOpcode()) { 893 case ISD::ZERO_EXTEND: 894 Result = PromoteOp(Node->getOperand(0)); 895 // NOTE: Any extend would work here... 896 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result); 897 Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Op.getValueType(), 898 Result, Node->getOperand(0).getValueType()); 899 break; 900 case ISD::SIGN_EXTEND: 901 Result = PromoteOp(Node->getOperand(0)); 902 // NOTE: Any extend would work here... 903 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result); 904 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 905 Result, Node->getOperand(0).getValueType()); 906 break; 907 case ISD::TRUNCATE: 908 Result = PromoteOp(Node->getOperand(0)); 909 Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result); 910 break; 911 case ISD::FP_EXTEND: 912 Result = PromoteOp(Node->getOperand(0)); 913 if (Result.getValueType() != Op.getValueType()) 914 // Dynamically dead while we have only 2 FP types. 915 Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result); 916 break; 917 case ISD::FP_ROUND: 918 case ISD::FP_TO_SINT: 919 case ISD::FP_TO_UINT: 920 Result = PromoteOp(Node->getOperand(0)); 921 Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result); 922 break; 923 case ISD::SINT_TO_FP: 924 Result = PromoteOp(Node->getOperand(0)); 925 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 926 Result, Node->getOperand(0).getValueType()); 927 Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result); 928 break; 929 case ISD::UINT_TO_FP: 930 Result = PromoteOp(Node->getOperand(0)); 931 Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(), 932 Result, Node->getOperand(0).getValueType()); 933 Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result); 934 break; 935 } 936 } 937 break; 938 case ISD::FP_ROUND_INREG: 939 case ISD::SIGN_EXTEND_INREG: 940 case ISD::ZERO_EXTEND_INREG: { 941 Tmp1 = LegalizeOp(Node->getOperand(0)); 942 MVT::ValueType ExtraVT = cast<MVTSDNode>(Node)->getExtraValueType(); 943 944 // If this operation is not supported, convert it to a shl/shr or load/store 945 // pair. 946 switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) { 947 default: assert(0 && "This action not supported for this op yet!"); 948 case TargetLowering::Legal: 949 if (Tmp1 != Node->getOperand(0)) 950 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 951 ExtraVT); 952 break; 953 case TargetLowering::Expand: 954 // If this is an integer extend and shifts are supported, do that. 955 if (Node->getOpcode() == ISD::ZERO_EXTEND_INREG) { 956 // NOTE: we could fall back on load/store here too for targets without 957 // AND. However, it is doubtful that any exist. 958 // AND out the appropriate bits. 959 SDOperand Mask = 960 DAG.getConstant((1ULL << MVT::getSizeInBits(ExtraVT))-1, 961 Node->getValueType(0)); 962 Result = DAG.getNode(ISD::AND, Node->getValueType(0), 963 Node->getOperand(0), Mask); 964 } else if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) { 965 // NOTE: we could fall back on load/store here too for targets without 966 // SAR. However, it is doubtful that any exist. 967 unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) - 968 MVT::getSizeInBits(ExtraVT); 969 SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy()); 970 Result = DAG.getNode(ISD::SHL, Node->getValueType(0), 971 Node->getOperand(0), ShiftCst); 972 Result = DAG.getNode(ISD::SRA, Node->getValueType(0), 973 Result, ShiftCst); 974 } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) { 975 // The only way we can lower this is to turn it into a STORETRUNC, 976 // EXTLOAD pair, targetting a temporary location (a stack slot). 977 978 // NOTE: there is a choice here between constantly creating new stack 979 // slots and always reusing the same one. We currently always create 980 // new ones, as reuse may inhibit scheduling. 981 const Type *Ty = MVT::getTypeForValueType(ExtraVT); 982 unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty); 983 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); 984 MachineFunction &MF = DAG.getMachineFunction(); 985 int SSFI = 986 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 987 SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); 988 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(), 989 Node->getOperand(0), StackSlot, ExtraVT); 990 Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0), 991 Result, StackSlot, ExtraVT); 992 } else { 993 assert(0 && "Unknown op"); 994 } 995 Result = LegalizeOp(Result); 996 break; 997 } 998 break; 999 } 1000 } 1001 1002 if (!Op.Val->hasOneUse()) 1003 AddLegalizedOperand(Op, Result); 1004 1005 return Result; 1006} 1007 1008/// PromoteOp - Given an operation that produces a value in an invalid type, 1009/// promote it to compute the value into a larger type. The produced value will 1010/// have the correct bits for the low portion of the register, but no guarantee 1011/// is made about the top bits: it may be zero, sign-extended, or garbage. 1012SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { 1013 MVT::ValueType VT = Op.getValueType(); 1014 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 1015 assert(getTypeAction(VT) == Promote && 1016 "Caller should expand or legalize operands that are not promotable!"); 1017 assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) && 1018 "Cannot promote to smaller type!"); 1019 1020 std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op); 1021 if (I != PromotedNodes.end()) return I->second; 1022 1023 SDOperand Tmp1, Tmp2, Tmp3; 1024 1025 SDOperand Result; 1026 SDNode *Node = Op.Val; 1027 1028 // Promotion needs an optimization step to clean up after it, and is not 1029 // careful to avoid operations the target does not support. Make sure that 1030 // all generated operations are legalized in the next iteration. 1031 NeedsAnotherIteration = true; 1032 1033 switch (Node->getOpcode()) { 1034 default: 1035 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 1036 assert(0 && "Do not know how to promote this operator!"); 1037 abort(); 1038 case ISD::UNDEF: 1039 Result = DAG.getNode(ISD::UNDEF, NVT); 1040 break; 1041 case ISD::Constant: 1042 Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op); 1043 assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?"); 1044 break; 1045 case ISD::ConstantFP: 1046 Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op); 1047 assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?"); 1048 break; 1049 case ISD::CopyFromReg: 1050 Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), NVT, 1051 Node->getOperand(0)); 1052 // Remember that we legalized the chain. 1053 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 1054 break; 1055 1056 case ISD::SETCC: 1057 assert(getTypeAction(TLI.getSetCCResultTy()) == Legal && 1058 "SetCC type is not legal??"); 1059 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 1060 TLI.getSetCCResultTy(), Node->getOperand(0), 1061 Node->getOperand(1)); 1062 Result = LegalizeOp(Result); 1063 break; 1064 1065 case ISD::TRUNCATE: 1066 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1067 case Legal: 1068 Result = LegalizeOp(Node->getOperand(0)); 1069 assert(Result.getValueType() >= NVT && 1070 "This truncation doesn't make sense!"); 1071 if (Result.getValueType() > NVT) // Truncate to NVT instead of VT 1072 Result = DAG.getNode(ISD::TRUNCATE, NVT, Result); 1073 break; 1074 case Promote: 1075 // The truncation is not required, because we don't guarantee anything 1076 // about high bits anyway. 1077 Result = PromoteOp(Node->getOperand(0)); 1078 break; 1079 case Expand: 1080 assert(0 && "Cannot handle expand yet"); 1081 } 1082 break; 1083 case ISD::SIGN_EXTEND: 1084 case ISD::ZERO_EXTEND: 1085 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1086 case Expand: assert(0 && "BUG: Smaller reg should have been promoted!"); 1087 case Legal: 1088 // Input is legal? Just do extend all the way to the larger type. 1089 Result = LegalizeOp(Node->getOperand(0)); 1090 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 1091 break; 1092 case Promote: 1093 // Promote the reg if it's smaller. 1094 Result = PromoteOp(Node->getOperand(0)); 1095 // The high bits are not guaranteed to be anything. Insert an extend. 1096 if (Node->getOpcode() == ISD::SIGN_EXTEND) 1097 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result, 1098 Node->getOperand(0).getValueType()); 1099 else 1100 Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Result, 1101 Node->getOperand(0).getValueType()); 1102 break; 1103 } 1104 break; 1105 1106 case ISD::FP_EXTEND: 1107 assert(0 && "Case not implemented. Dynamically dead with 2 FP types!"); 1108 case ISD::FP_ROUND: 1109 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1110 case Expand: assert(0 && "BUG: Cannot expand FP regs!"); 1111 case Promote: assert(0 && "Unreachable with 2 FP types!"); 1112 case Legal: 1113 // Input is legal? Do an FP_ROUND_INREG. 1114 Result = LegalizeOp(Node->getOperand(0)); 1115 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1116 break; 1117 } 1118 break; 1119 1120 case ISD::SINT_TO_FP: 1121 case ISD::UINT_TO_FP: 1122 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1123 case Legal: 1124 Result = LegalizeOp(Node->getOperand(0)); 1125 // No extra round required here. 1126 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 1127 break; 1128 1129 case Promote: 1130 Result = PromoteOp(Node->getOperand(0)); 1131 if (Node->getOpcode() == ISD::SINT_TO_FP) 1132 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 1133 Result, Node->getOperand(0).getValueType()); 1134 else 1135 Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(), 1136 Result, Node->getOperand(0).getValueType()); 1137 // No extra round required here. 1138 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 1139 break; 1140 case Expand: 1141 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT, 1142 Node->getOperand(0)); 1143 Result = LegalizeOp(Result); 1144 1145 // Round if we cannot tolerate excess precision. 1146 if (NoExcessFPPrecision) 1147 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1148 break; 1149 } 1150 break; 1151 1152 case ISD::FP_TO_SINT: 1153 case ISD::FP_TO_UINT: 1154 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1155 case Legal: 1156 Tmp1 = LegalizeOp(Node->getOperand(0)); 1157 break; 1158 case Promote: 1159 // The input result is prerounded, so we don't have to do anything 1160 // special. 1161 Tmp1 = PromoteOp(Node->getOperand(0)); 1162 break; 1163 case Expand: 1164 assert(0 && "not implemented"); 1165 } 1166 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 1167 break; 1168 1169 case ISD::AND: 1170 case ISD::OR: 1171 case ISD::XOR: 1172 case ISD::ADD: 1173 case ISD::SUB: 1174 case ISD::MUL: 1175 // The input may have strange things in the top bits of the registers, but 1176 // these operations don't care. They may have wierd bits going out, but 1177 // that too is okay if they are integer operations. 1178 Tmp1 = PromoteOp(Node->getOperand(0)); 1179 Tmp2 = PromoteOp(Node->getOperand(1)); 1180 assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT); 1181 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 1182 1183 // However, if this is a floating point operation, they will give excess 1184 // precision that we may not be able to tolerate. If we DO allow excess 1185 // precision, just leave it, otherwise excise it. 1186 // FIXME: Why would we need to round FP ops more than integer ones? 1187 // Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C)) 1188 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision) 1189 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1190 break; 1191 1192 case ISD::SDIV: 1193 case ISD::SREM: 1194 // These operators require that their input be sign extended. 1195 Tmp1 = PromoteOp(Node->getOperand(0)); 1196 Tmp2 = PromoteOp(Node->getOperand(1)); 1197 if (MVT::isInteger(NVT)) { 1198 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT); 1199 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT); 1200 } 1201 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 1202 1203 // Perform FP_ROUND: this is probably overly pessimistic. 1204 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision) 1205 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1206 break; 1207 1208 case ISD::UDIV: 1209 case ISD::UREM: 1210 // These operators require that their input be zero extended. 1211 Tmp1 = PromoteOp(Node->getOperand(0)); 1212 Tmp2 = PromoteOp(Node->getOperand(1)); 1213 assert(MVT::isInteger(NVT) && "Operators don't apply to FP!"); 1214 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT); 1215 Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT); 1216 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 1217 break; 1218 1219 case ISD::SHL: 1220 Tmp1 = PromoteOp(Node->getOperand(0)); 1221 Tmp2 = LegalizeOp(Node->getOperand(1)); 1222 Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2); 1223 break; 1224 case ISD::SRA: 1225 // The input value must be properly sign extended. 1226 Tmp1 = PromoteOp(Node->getOperand(0)); 1227 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT); 1228 Tmp2 = LegalizeOp(Node->getOperand(1)); 1229 Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2); 1230 break; 1231 case ISD::SRL: 1232 // The input value must be properly zero extended. 1233 Tmp1 = PromoteOp(Node->getOperand(0)); 1234 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT); 1235 Tmp2 = LegalizeOp(Node->getOperand(1)); 1236 Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2); 1237 break; 1238 case ISD::LOAD: 1239 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1240 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 1241 Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, VT); 1242 1243 // Remember that we legalized the chain. 1244 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 1245 break; 1246 case ISD::SELECT: 1247 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1248 case Expand: assert(0 && "It's impossible to expand bools"); 1249 case Legal: 1250 Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition. 1251 break; 1252 case Promote: 1253 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 1254 break; 1255 } 1256 Tmp2 = PromoteOp(Node->getOperand(1)); // Legalize the op0 1257 Tmp3 = PromoteOp(Node->getOperand(2)); // Legalize the op1 1258 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3); 1259 break; 1260 case ISD::CALL: { 1261 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1262 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 1263 1264 std::vector<SDOperand> Ops; 1265 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) 1266 Ops.push_back(LegalizeOp(Node->getOperand(i))); 1267 1268 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 1269 "Can only promote single result calls"); 1270 std::vector<MVT::ValueType> RetTyVTs; 1271 RetTyVTs.reserve(2); 1272 RetTyVTs.push_back(NVT); 1273 RetTyVTs.push_back(MVT::Other); 1274 SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops); 1275 Result = SDOperand(NC, 0); 1276 1277 // Insert the new chain mapping. 1278 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 1279 break; 1280 } 1281 } 1282 1283 assert(Result.Val && "Didn't set a result!"); 1284 AddPromotedOperand(Op, Result); 1285 return Result; 1286} 1287 1288/// ExpandAddSub - Find a clever way to expand this add operation into 1289/// subcomponents. 1290void SelectionDAGLegalize::ExpandAddSub(bool isAdd, SDOperand LHS,SDOperand RHS, 1291 SDOperand &Lo, SDOperand &Hi) { 1292 // Expand the subcomponents. 1293 SDOperand LHSL, LHSH, RHSL, RHSH; 1294 ExpandOp(LHS, LHSL, LHSH); 1295 ExpandOp(RHS, RHSL, RHSH); 1296 1297 // Convert this add to the appropriate ADDC pair. The low part has no carry 1298 // in. 1299 unsigned Opc = isAdd ? ISD::ADD_PARTS : ISD::SUB_PARTS; 1300 std::vector<SDOperand> Ops; 1301 Ops.push_back(LHSL); 1302 Ops.push_back(LHSH); 1303 Ops.push_back(RHSL); 1304 Ops.push_back(RHSH); 1305 Lo = DAG.getNode(Opc, LHSL.getValueType(), Ops); 1306 Hi = Lo.getValue(1); 1307} 1308 1309/// ExpandShift - Try to find a clever way to expand this shift operation out to 1310/// smaller elements. If we can't find a way that is more efficient than a 1311/// libcall on this target, return false. Otherwise, return true with the 1312/// low-parts expanded into Lo and Hi. 1313bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt, 1314 SDOperand &Lo, SDOperand &Hi) { 1315 assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) && 1316 "This is not a shift!"); 1317 MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType()); 1318 1319 // If we have an efficient select operation (or if the selects will all fold 1320 // away), lower to some complex code, otherwise just emit the libcall. 1321 if (TLI.getOperationAction(ISD::SELECT, NVT) != TargetLowering::Legal && 1322 !isa<ConstantSDNode>(Amt)) 1323 return false; 1324 1325 SDOperand InL, InH; 1326 ExpandOp(Op, InL, InH); 1327 SDOperand ShAmt = LegalizeOp(Amt); 1328 MVT::ValueType ShTy = ShAmt.getValueType(); 1329 1330 unsigned NVTBits = MVT::getSizeInBits(NVT); 1331 SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy, // NAmt = 32-ShAmt 1332 DAG.getConstant(NVTBits, ShTy), ShAmt); 1333 1334 // Compare the unmasked shift amount against 32. 1335 SDOperand Cond = DAG.getSetCC(ISD::SETGE, TLI.getSetCCResultTy(), ShAmt, 1336 DAG.getConstant(NVTBits, ShTy)); 1337 1338 if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) { 1339 ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt, // ShAmt &= 31 1340 DAG.getConstant(NVTBits-1, ShTy)); 1341 NAmt = DAG.getNode(ISD::AND, ShTy, NAmt, // NAmt &= 31 1342 DAG.getConstant(NVTBits-1, ShTy)); 1343 } 1344 1345 if (Opc == ISD::SHL) { 1346 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt) 1347 DAG.getNode(ISD::SHL, NVT, InH, ShAmt), 1348 DAG.getNode(ISD::SRL, NVT, InL, NAmt)); 1349 SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31 1350 1351 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1); 1352 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2); 1353 } else { 1354 SDOperand HiLoPart = DAG.getNode(ISD::SELECT, NVT, 1355 DAG.getSetCC(ISD::SETEQ, 1356 TLI.getSetCCResultTy(), NAmt, 1357 DAG.getConstant(32, ShTy)), 1358 DAG.getConstant(0, NVT), 1359 DAG.getNode(ISD::SHL, NVT, InH, NAmt)); 1360 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt) 1361 HiLoPart, 1362 DAG.getNode(ISD::SRL, NVT, InL, ShAmt)); 1363 SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt); // T2 = InH >> ShAmt&31 1364 1365 SDOperand HiPart; 1366 if (Opc == ISD::SRA) 1367 HiPart = DAG.getNode(ISD::SRA, NVT, InH, 1368 DAG.getConstant(NVTBits-1, ShTy)); 1369 else 1370 HiPart = DAG.getConstant(0, NVT); 1371 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1); 1372 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart, T2); 1373 } 1374 return true; 1375} 1376 1377/// FindLatestAdjCallStackDown - Scan up the dag to find the latest (highest 1378/// NodeDepth) node that is an AdjCallStackDown operation and occurs later than 1379/// Found. 1380static void FindLatestAdjCallStackDown(SDNode *Node, SDNode *&Found) { 1381 if (Node->getNodeDepth() <= Found->getNodeDepth()) return; 1382 1383 // If we found an ADJCALLSTACKDOWN, we already know this node occurs later 1384 // than the Found node. Just remember this node and return. 1385 if (Node->getOpcode() == ISD::ADJCALLSTACKDOWN) { 1386 Found = Node; 1387 return; 1388 } 1389 1390 // Otherwise, scan the operands of Node to see if any of them is a call. 1391 assert(Node->getNumOperands() != 0 && 1392 "All leaves should have depth equal to the entry node!"); 1393 for (unsigned i = 0, e = Node->getNumOperands()-1; i != e; ++i) 1394 FindLatestAdjCallStackDown(Node->getOperand(i).Val, Found); 1395 1396 // Tail recurse for the last iteration. 1397 FindLatestAdjCallStackDown(Node->getOperand(Node->getNumOperands()-1).Val, 1398 Found); 1399} 1400 1401 1402/// FindEarliestAdjCallStackUp - Scan down the dag to find the earliest (lowest 1403/// NodeDepth) node that is an AdjCallStackUp operation and occurs more recent 1404/// than Found. 1405static void FindEarliestAdjCallStackUp(SDNode *Node, SDNode *&Found) { 1406 if (Found && Node->getNodeDepth() >= Found->getNodeDepth()) return; 1407 1408 // If we found an ADJCALLSTACKUP, we already know this node occurs earlier 1409 // than the Found node. Just remember this node and return. 1410 if (Node->getOpcode() == ISD::ADJCALLSTACKUP) { 1411 Found = Node; 1412 return; 1413 } 1414 1415 // Otherwise, scan the operands of Node to see if any of them is a call. 1416 SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); 1417 if (UI == E) return; 1418 for (--E; UI != E; ++UI) 1419 FindEarliestAdjCallStackUp(*UI, Found); 1420 1421 // Tail recurse for the last iteration. 1422 FindEarliestAdjCallStackUp(*UI, Found); 1423} 1424 1425/// FindAdjCallStackUp - Given a chained node that is part of a call sequence, 1426/// find the ADJCALLSTACKUP node that terminates the call sequence. 1427static SDNode *FindAdjCallStackUp(SDNode *Node) { 1428 if (Node->getOpcode() == ISD::ADJCALLSTACKUP) 1429 return Node; 1430 assert(!Node->use_empty() && "Could not find ADJCALLSTACKUP!"); 1431 1432 if (Node->hasOneUse()) // Simple case, only has one user to check. 1433 return FindAdjCallStackUp(*Node->use_begin()); 1434 1435 SDOperand TheChain(Node, Node->getNumValues()-1); 1436 assert(TheChain.getValueType() == MVT::Other && "Is not a token chain!"); 1437 1438 for (SDNode::use_iterator UI = Node->use_begin(), 1439 E = Node->use_end(); ; ++UI) { 1440 assert(UI != E && "Didn't find a user of the tokchain, no ADJCALLSTACKUP!"); 1441 1442 // Make sure to only follow users of our token chain. 1443 SDNode *User = *UI; 1444 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 1445 if (User->getOperand(i) == TheChain) 1446 return FindAdjCallStackUp(User); 1447 } 1448 assert(0 && "Unreachable"); 1449 abort(); 1450} 1451 1452/// FindInputOutputChains - If we are replacing an operation with a call we need 1453/// to find the call that occurs before and the call that occurs after it to 1454/// properly serialize the calls in the block. 1455static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain, 1456 SDOperand Entry) { 1457 SDNode *LatestAdjCallStackDown = Entry.Val; 1458 FindLatestAdjCallStackDown(OpNode, LatestAdjCallStackDown); 1459 //std::cerr << "Found node: "; LatestAdjCallStackDown->dump(); std::cerr <<"\n"; 1460 1461 SDNode *LatestAdjCallStackUp = FindAdjCallStackUp(LatestAdjCallStackDown); 1462 1463 1464 SDNode *EarliestAdjCallStackUp = 0; 1465 FindEarliestAdjCallStackUp(OpNode, EarliestAdjCallStackUp); 1466 1467 if (EarliestAdjCallStackUp) { 1468 //std::cerr << "Found node: "; 1469 //EarliestAdjCallStackUp->dump(); std::cerr <<"\n"; 1470 } 1471 1472 return SDOperand(LatestAdjCallStackUp, 0); 1473} 1474 1475 1476 1477// ExpandLibCall - Expand a node into a call to a libcall. If the result value 1478// does not fit into a register, return the lo part and set the hi part to the 1479// by-reg argument. If it does fit into a single register, return the result 1480// and leave the Hi part unset. 1481SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node, 1482 SDOperand &Hi) { 1483 SDNode *OutChain; 1484 SDOperand InChain = FindInputOutputChains(Node, OutChain, 1485 DAG.getEntryNode()); 1486 // TODO. Link in chains. 1487 1488 TargetLowering::ArgListTy Args; 1489 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 1490 MVT::ValueType ArgVT = Node->getOperand(i).getValueType(); 1491 const Type *ArgTy = MVT::getTypeForValueType(ArgVT); 1492 Args.push_back(std::make_pair(Node->getOperand(i), ArgTy)); 1493 } 1494 SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy()); 1495 1496 // We don't care about token chains for libcalls. We just use the entry 1497 // node as our input and ignore the output chain. This allows us to place 1498 // calls wherever we need them to satisfy data dependences. 1499 const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0)); 1500 SDOperand Result = TLI.LowerCallTo(InChain, RetTy, false, Callee, 1501 Args, DAG).first; 1502 switch (getTypeAction(Result.getValueType())) { 1503 default: assert(0 && "Unknown thing"); 1504 case Legal: 1505 return Result; 1506 case Promote: 1507 assert(0 && "Cannot promote this yet!"); 1508 case Expand: 1509 SDOperand Lo; 1510 ExpandOp(Result, Lo, Hi); 1511 return Lo; 1512 } 1513} 1514 1515 1516/// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the 1517/// destination type is legal. 1518SDOperand SelectionDAGLegalize:: 1519ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) { 1520 assert(getTypeAction(DestTy) == Legal && "Destination type is not legal!"); 1521 assert(getTypeAction(Source.getValueType()) == Expand && 1522 "This is not an expansion!"); 1523 assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!"); 1524 1525 SDNode *OutChain; 1526 SDOperand InChain = FindInputOutputChains(Source.Val, OutChain, 1527 DAG.getEntryNode()); 1528 1529 const char *FnName = 0; 1530 if (isSigned) { 1531 if (DestTy == MVT::f32) 1532 FnName = "__floatdisf"; 1533 else { 1534 assert(DestTy == MVT::f64 && "Unknown fp value type!"); 1535 FnName = "__floatdidf"; 1536 } 1537 } else { 1538 // If this is unsigned, and not supported, first perform the conversion to 1539 // signed, then adjust the result if the sign bit is set. 1540 SDOperand SignedConv = ExpandIntToFP(false, DestTy, Source); 1541 1542 assert(0 && "Unsigned casts not supported yet!"); 1543 } 1544 SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy()); 1545 1546 TargetLowering::ArgListTy Args; 1547 const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType()); 1548 Args.push_back(std::make_pair(Source, ArgTy)); 1549 1550 // We don't care about token chains for libcalls. We just use the entry 1551 // node as our input and ignore the output chain. This allows us to place 1552 // calls wherever we need them to satisfy data dependences. 1553 const Type *RetTy = MVT::getTypeForValueType(DestTy); 1554 return TLI.LowerCallTo(InChain, RetTy, false, Callee, Args, DAG).first; 1555 1556} 1557 1558 1559 1560/// ExpandOp - Expand the specified SDOperand into its two component pieces 1561/// Lo&Hi. Note that the Op MUST be an expanded type. As a result of this, the 1562/// LegalizeNodes map is filled in for any results that are not expanded, the 1563/// ExpandedNodes map is filled in for any results that are expanded, and the 1564/// Lo/Hi values are returned. 1565void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ 1566 MVT::ValueType VT = Op.getValueType(); 1567 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 1568 SDNode *Node = Op.Val; 1569 assert(getTypeAction(VT) == Expand && "Not an expanded type!"); 1570 assert(MVT::isInteger(VT) && "Cannot expand FP values!"); 1571 assert(MVT::isInteger(NVT) && NVT < VT && 1572 "Cannot expand to FP value or to larger int value!"); 1573 1574 // If there is more than one use of this, see if we already expanded it. 1575 // There is no use remembering values that only have a single use, as the map 1576 // entries will never be reused. 1577 if (!Node->hasOneUse()) { 1578 std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I 1579 = ExpandedNodes.find(Op); 1580 if (I != ExpandedNodes.end()) { 1581 Lo = I->second.first; 1582 Hi = I->second.second; 1583 return; 1584 } 1585 } 1586 1587 // Expanding to multiple registers needs to perform an optimization step, and 1588 // is not careful to avoid operations the target does not support. Make sure 1589 // that all generated operations are legalized in the next iteration. 1590 NeedsAnotherIteration = true; 1591 1592 switch (Node->getOpcode()) { 1593 default: 1594 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 1595 assert(0 && "Do not know how to expand this operator!"); 1596 abort(); 1597 case ISD::UNDEF: 1598 Lo = DAG.getNode(ISD::UNDEF, NVT); 1599 Hi = DAG.getNode(ISD::UNDEF, NVT); 1600 break; 1601 case ISD::Constant: { 1602 uint64_t Cst = cast<ConstantSDNode>(Node)->getValue(); 1603 Lo = DAG.getConstant(Cst, NVT); 1604 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT); 1605 break; 1606 } 1607 1608 case ISD::CopyFromReg: { 1609 unsigned Reg = cast<RegSDNode>(Node)->getReg(); 1610 // Aggregate register values are always in consequtive pairs. 1611 Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0)); 1612 Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1)); 1613 1614 // Remember that we legalized the chain. 1615 AddLegalizedOperand(Op.getValue(1), Hi.getValue(1)); 1616 1617 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!"); 1618 break; 1619 } 1620 1621 case ISD::BUILD_PAIR: 1622 // Legalize both operands. FIXME: in the future we should handle the case 1623 // where the two elements are not legal. 1624 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!"); 1625 Lo = LegalizeOp(Node->getOperand(0)); 1626 Hi = LegalizeOp(Node->getOperand(1)); 1627 break; 1628 1629 case ISD::LOAD: { 1630 SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1631 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 1632 Lo = DAG.getLoad(NVT, Ch, Ptr); 1633 1634 // Increment the pointer to the other half. 1635 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 1636 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 1637 getIntPtrConstant(IncrementSize)); 1638 Hi = DAG.getLoad(NVT, Ch, Ptr); 1639 1640 // Build a factor node to remember that this load is independent of the 1641 // other one. 1642 SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), 1643 Hi.getValue(1)); 1644 1645 // Remember that we legalized the chain. 1646 AddLegalizedOperand(Op.getValue(1), TF); 1647 if (!TLI.isLittleEndian()) 1648 std::swap(Lo, Hi); 1649 break; 1650 } 1651 case ISD::CALL: { 1652 SDOperand Chain = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1653 SDOperand Callee = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 1654 1655 bool Changed = false; 1656 std::vector<SDOperand> Ops; 1657 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) { 1658 Ops.push_back(LegalizeOp(Node->getOperand(i))); 1659 Changed |= Ops.back() != Node->getOperand(i); 1660 } 1661 1662 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 1663 "Can only expand a call once so far, not i64 -> i16!"); 1664 1665 std::vector<MVT::ValueType> RetTyVTs; 1666 RetTyVTs.reserve(3); 1667 RetTyVTs.push_back(NVT); 1668 RetTyVTs.push_back(NVT); 1669 RetTyVTs.push_back(MVT::Other); 1670 SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops); 1671 Lo = SDOperand(NC, 0); 1672 Hi = SDOperand(NC, 1); 1673 1674 // Insert the new chain mapping. 1675 AddLegalizedOperand(Op.getValue(1), Hi.getValue(2)); 1676 break; 1677 } 1678 case ISD::AND: 1679 case ISD::OR: 1680 case ISD::XOR: { // Simple logical operators -> two trivial pieces. 1681 SDOperand LL, LH, RL, RH; 1682 ExpandOp(Node->getOperand(0), LL, LH); 1683 ExpandOp(Node->getOperand(1), RL, RH); 1684 Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL); 1685 Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH); 1686 break; 1687 } 1688 case ISD::SELECT: { 1689 SDOperand C, LL, LH, RL, RH; 1690 1691 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1692 case Expand: assert(0 && "It's impossible to expand bools"); 1693 case Legal: 1694 C = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 1695 break; 1696 case Promote: 1697 C = PromoteOp(Node->getOperand(0)); // Promote the condition. 1698 break; 1699 } 1700 ExpandOp(Node->getOperand(1), LL, LH); 1701 ExpandOp(Node->getOperand(2), RL, RH); 1702 Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL); 1703 Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH); 1704 break; 1705 } 1706 case ISD::SIGN_EXTEND: { 1707 // The low part is just a sign extension of the input (which degenerates to 1708 // a copy). 1709 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0))); 1710 1711 // The high part is obtained by SRA'ing all but one of the bits of the lo 1712 // part. 1713 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); 1714 Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, 1715 TLI.getShiftAmountTy())); 1716 break; 1717 } 1718 case ISD::ZERO_EXTEND: 1719 // The low part is just a zero extension of the input (which degenerates to 1720 // a copy). 1721 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0))); 1722 1723 // The high part is just a zero. 1724 Hi = DAG.getConstant(0, NVT); 1725 break; 1726 1727 // These operators cannot be expanded directly, emit them as calls to 1728 // library functions. 1729 case ISD::FP_TO_SINT: 1730 if (Node->getOperand(0).getValueType() == MVT::f32) 1731 Lo = ExpandLibCall("__fixsfdi", Node, Hi); 1732 else 1733 Lo = ExpandLibCall("__fixdfdi", Node, Hi); 1734 break; 1735 case ISD::FP_TO_UINT: 1736 if (Node->getOperand(0).getValueType() == MVT::f32) 1737 Lo = ExpandLibCall("__fixunssfdi", Node, Hi); 1738 else 1739 Lo = ExpandLibCall("__fixunsdfdi", Node, Hi); 1740 break; 1741 1742 case ISD::SHL: 1743 // If we can emit an efficient shift operation, do so now. 1744 if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 1745 break; 1746 // Otherwise, emit a libcall. 1747 Lo = ExpandLibCall("__ashldi3", Node, Hi); 1748 break; 1749 1750 case ISD::SRA: 1751 // If we can emit an efficient shift operation, do so now. 1752 if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 1753 break; 1754 // Otherwise, emit a libcall. 1755 Lo = ExpandLibCall("__ashrdi3", Node, Hi); 1756 break; 1757 case ISD::SRL: 1758 // If we can emit an efficient shift operation, do so now. 1759 if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 1760 break; 1761 // Otherwise, emit a libcall. 1762 Lo = ExpandLibCall("__lshrdi3", Node, Hi); 1763 break; 1764 1765 case ISD::ADD: 1766 ExpandAddSub(true, Node->getOperand(0), Node->getOperand(1), Lo, Hi); 1767 break; 1768 case ISD::SUB: 1769 ExpandAddSub(false, Node->getOperand(0), Node->getOperand(1), Lo, Hi); 1770 break; 1771 case ISD::MUL: Lo = ExpandLibCall("__muldi3" , Node, Hi); break; 1772 case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break; 1773 case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break; 1774 case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break; 1775 case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break; 1776 } 1777 1778 // Remember in a map if the values will be reused later. 1779 if (!Node->hasOneUse()) { 1780 bool isNew = ExpandedNodes.insert(std::make_pair(Op, 1781 std::make_pair(Lo, Hi))).second; 1782 assert(isNew && "Value already expanded?!?"); 1783 } 1784} 1785 1786 1787// SelectionDAG::Legalize - This is the entry point for the file. 1788// 1789void SelectionDAG::Legalize() { 1790 /// run - This is the main entry point to this class. 1791 /// 1792 SelectionDAGLegalize(*this).Run(); 1793} 1794 1795