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