LegalizeDAG.cpp revision d5d56825123665b60d4eada0a4ad7d0adc5cf3a3
1//===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the SelectionDAG::Legalize method. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/CodeGen/SelectionDAG.h" 15#include "llvm/CodeGen/MachineConstantPool.h" 16#include "llvm/CodeGen/MachineFunction.h" 17#include "llvm/CodeGen/MachineFrameInfo.h" 18#include "llvm/Target/TargetLowering.h" 19#include "llvm/Target/TargetData.h" 20#include "llvm/Target/TargetOptions.h" 21#include "llvm/Constants.h" 22#include <iostream> 23using namespace llvm; 24 25//===----------------------------------------------------------------------===// 26/// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and 27/// hacks on it until the target machine can handle it. This involves 28/// eliminating value sizes the machine cannot handle (promoting small sizes to 29/// large sizes or splitting up large values into small values) as well as 30/// eliminating operations the machine cannot handle. 31/// 32/// This code also does a small amount of optimization and recognition of idioms 33/// as part of its processing. For example, if a target does not support a 34/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this 35/// will attempt merge setcc and brc instructions into brcc's. 36/// 37namespace { 38class SelectionDAGLegalize { 39 TargetLowering &TLI; 40 SelectionDAG &DAG; 41 42 /// LegalizeAction - This enum indicates what action we should take for each 43 /// value type the can occur in the program. 44 enum LegalizeAction { 45 Legal, // The target natively supports this value type. 46 Promote, // This should be promoted to the next larger type. 47 Expand, // This integer type should be broken into smaller pieces. 48 }; 49 50 /// ValueTypeActions - This is a bitvector that contains two bits for each 51 /// value type, where the two bits correspond to the LegalizeAction enum. 52 /// This can be queried with "getTypeAction(VT)". 53 unsigned ValueTypeActions; 54 55 /// NeedsAnotherIteration - This is set when we expand a large integer 56 /// operation into smaller integer operations, but the smaller operations are 57 /// not set. This occurs only rarely in practice, for targets that don't have 58 /// 32-bit or larger integer registers. 59 bool NeedsAnotherIteration; 60 61 /// LegalizedNodes - For nodes that are of legal width, and that have more 62 /// than one use, this map indicates what regularized operand to use. This 63 /// allows us to avoid legalizing the same thing more than once. 64 std::map<SDOperand, SDOperand> LegalizedNodes; 65 66 /// PromotedNodes - For nodes that are below legal width, and that have more 67 /// than one use, this map indicates what promoted value to use. This allows 68 /// us to avoid promoting the same thing more than once. 69 std::map<SDOperand, SDOperand> PromotedNodes; 70 71 /// ExpandedNodes - For nodes that need to be expanded, and which have more 72 /// than one use, this map indicates which which operands are the expanded 73 /// version of the input. This allows us to avoid expanding the same node 74 /// more than once. 75 std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes; 76 77 void AddLegalizedOperand(SDOperand From, SDOperand To) { 78 bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second; 79 assert(isNew && "Got into the map somehow?"); 80 } 81 void AddPromotedOperand(SDOperand From, SDOperand To) { 82 bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second; 83 assert(isNew && "Got into the map somehow?"); 84 } 85 86public: 87 88 SelectionDAGLegalize(TargetLowering &TLI, SelectionDAG &DAG); 89 90 /// Run - While there is still lowering to do, perform a pass over the DAG. 91 /// Most regularization can be done in a single pass, but targets that require 92 /// large values to be split into registers multiple times (e.g. i64 -> 4x 93 /// i16) require iteration for these values (the first iteration will demote 94 /// to i32, the second will demote to i16). 95 void Run() { 96 do { 97 NeedsAnotherIteration = false; 98 LegalizeDAG(); 99 } while (NeedsAnotherIteration); 100 } 101 102 /// getTypeAction - Return how we should legalize values of this type, either 103 /// it is already legal or we need to expand it into multiple registers of 104 /// smaller integer type, or we need to promote it to a larger type. 105 LegalizeAction getTypeAction(MVT::ValueType VT) const { 106 return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3); 107 } 108 109 /// isTypeLegal - Return true if this type is legal on this target. 110 /// 111 bool isTypeLegal(MVT::ValueType VT) const { 112 return getTypeAction(VT) == Legal; 113 } 114 115private: 116 void LegalizeDAG(); 117 118 SDOperand LegalizeOp(SDOperand O); 119 void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi); 120 SDOperand PromoteOp(SDOperand O); 121 122 SDOperand getIntPtrConstant(uint64_t Val) { 123 return DAG.getConstant(Val, TLI.getPointerTy()); 124 } 125}; 126} 127 128 129SelectionDAGLegalize::SelectionDAGLegalize(TargetLowering &tli, 130 SelectionDAG &dag) 131 : TLI(tli), DAG(dag), ValueTypeActions(TLI.getValueTypeActions()) { 132 assert(MVT::LAST_VALUETYPE <= 16 && 133 "Too many value types for ValueTypeActions to hold!"); 134} 135 136void SelectionDAGLegalize::LegalizeDAG() { 137 SDOperand OldRoot = DAG.getRoot(); 138 SDOperand NewRoot = LegalizeOp(OldRoot); 139 DAG.setRoot(NewRoot); 140 141 ExpandedNodes.clear(); 142 LegalizedNodes.clear(); 143 PromotedNodes.clear(); 144 145 // Remove dead nodes now. 146 DAG.RemoveDeadNodes(OldRoot.Val); 147} 148 149SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { 150 assert(getTypeAction(Op.getValueType()) == Legal && 151 "Caller should expand or promote operands that are not legal!"); 152 153 // If this operation defines any values that cannot be represented in a 154 // register on this target, make sure to expand or promote them. 155 if (Op.Val->getNumValues() > 1) { 156 for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i) 157 switch (getTypeAction(Op.Val->getValueType(i))) { 158 case Legal: break; // Nothing to do. 159 case Expand: { 160 SDOperand T1, T2; 161 ExpandOp(Op.getValue(i), T1, T2); 162 assert(LegalizedNodes.count(Op) && 163 "Expansion didn't add legal operands!"); 164 return LegalizedNodes[Op]; 165 } 166 case Promote: 167 PromoteOp(Op.getValue(i)); 168 assert(LegalizedNodes.count(Op) && 169 "Expansion didn't add legal operands!"); 170 return LegalizedNodes[Op]; 171 } 172 } 173 174 std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op); 175 if (I != LegalizedNodes.end()) return I->second; 176 177 SDOperand Tmp1, Tmp2, Tmp3; 178 179 SDOperand Result = Op; 180 SDNode *Node = Op.Val; 181 182 switch (Node->getOpcode()) { 183 default: 184 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 185 assert(0 && "Do not know how to legalize this operator!"); 186 abort(); 187 case ISD::EntryToken: 188 case ISD::FrameIndex: 189 case ISD::GlobalAddress: 190 case ISD::ExternalSymbol: 191 case ISD::ConstantPool: // Nothing to do. 192 assert(getTypeAction(Node->getValueType(0)) == Legal && 193 "This must be legal!"); 194 break; 195 case ISD::CopyFromReg: 196 Tmp1 = LegalizeOp(Node->getOperand(0)); 197 if (Tmp1 != Node->getOperand(0)) 198 Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), 199 Node->getValueType(0), Tmp1); 200 break; 201 case ISD::ImplicitDef: 202 Tmp1 = LegalizeOp(Node->getOperand(0)); 203 if (Tmp1 != Node->getOperand(0)) 204 Result = DAG.getImplicitDef(Tmp1, cast<RegSDNode>(Node)->getReg()); 205 break; 206 case ISD::Constant: 207 // We know we don't need to expand constants here, constants only have one 208 // value and we check that it is fine above. 209 210 // FIXME: Maybe we should handle things like targets that don't support full 211 // 32-bit immediates? 212 break; 213 case ISD::ConstantFP: { 214 // Spill FP immediates to the constant pool if the target cannot directly 215 // codegen them. Targets often have some immediate values that can be 216 // efficiently generated into an FP register without a load. We explicitly 217 // leave these constants as ConstantFP nodes for the target to deal with. 218 219 ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node); 220 221 // Check to see if this FP immediate is already legal. 222 bool isLegal = false; 223 for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(), 224 E = TLI.legal_fpimm_end(); I != E; ++I) 225 if (CFP->isExactlyValue(*I)) { 226 isLegal = true; 227 break; 228 } 229 230 if (!isLegal) { 231 // Otherwise we need to spill the constant to memory. 232 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); 233 234 bool Extend = false; 235 236 // If a FP immediate is precise when represented as a float, we put it 237 // into the constant pool as a float, even if it's is statically typed 238 // as a double. 239 MVT::ValueType VT = CFP->getValueType(0); 240 bool isDouble = VT == MVT::f64; 241 ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy : 242 Type::FloatTy, CFP->getValue()); 243 if (isDouble && CFP->isExactlyValue((float)CFP->getValue())) { 244 LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy)); 245 VT = MVT::f32; 246 Extend = true; 247 } 248 249 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC), 250 TLI.getPointerTy()); 251 if (Extend) { 252 Result = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), CPIdx, 253 MVT::f32); 254 } else { 255 Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx); 256 } 257 } 258 break; 259 } 260 case ISD::TokenFactor: { 261 std::vector<SDOperand> Ops; 262 bool Changed = false; 263 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 264 Ops.push_back(LegalizeOp(Node->getOperand(i))); // Legalize the operands 265 Changed |= Ops[i] != Node->getOperand(i); 266 } 267 if (Changed) 268 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops); 269 break; 270 } 271 272 case ISD::ADJCALLSTACKDOWN: 273 case ISD::ADJCALLSTACKUP: 274 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 275 // There is no need to legalize the size argument (Operand #1) 276 if (Tmp1 != Node->getOperand(0)) 277 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, 278 Node->getOperand(1)); 279 break; 280 case ISD::DYNAMIC_STACKALLOC: 281 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 282 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the size. 283 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the alignment. 284 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 285 Tmp3 != Node->getOperand(2)) 286 Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0), 287 Tmp1, Tmp2, Tmp3); 288 else 289 Result = Op.getValue(0); 290 291 // Since this op produces two values, make sure to remember that we 292 // legalized both of them. 293 AddLegalizedOperand(SDOperand(Node, 0), Result); 294 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 295 return Result.getValue(Op.ResNo); 296 297 case ISD::CALL: 298 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 299 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 300 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 301 std::vector<MVT::ValueType> RetTyVTs; 302 RetTyVTs.reserve(Node->getNumValues()); 303 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 304 RetTyVTs.push_back(Node->getValueType(i)); 305 Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2), 0); 306 } else { 307 Result = Result.getValue(0); 308 } 309 // Since calls produce multiple values, make sure to remember that we 310 // legalized all of them. 311 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 312 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 313 return Result.getValue(Op.ResNo); 314 315 case ISD::BR: 316 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 317 if (Tmp1 != Node->getOperand(0)) 318 Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1)); 319 break; 320 321 case ISD::BRCOND: 322 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 323 324 switch (getTypeAction(Node->getOperand(1).getValueType())) { 325 case Expand: assert(0 && "It's impossible to expand bools"); 326 case Legal: 327 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 328 break; 329 case Promote: 330 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition. 331 break; 332 } 333 // Basic block destination (Op#2) is always legal. 334 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 335 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 336 Node->getOperand(2)); 337 break; 338 339 case ISD::LOAD: 340 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 341 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 342 if (Tmp1 != Node->getOperand(0) || 343 Tmp2 != Node->getOperand(1)) 344 Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2); 345 else 346 Result = SDOperand(Node, 0); 347 348 // Since loads produce two values, make sure to remember that we legalized 349 // both of them. 350 AddLegalizedOperand(SDOperand(Node, 0), Result); 351 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 352 return Result.getValue(Op.ResNo); 353 354 case ISD::EXTLOAD: 355 case ISD::SEXTLOAD: 356 case ISD::ZEXTLOAD: 357 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 358 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 359 if (Tmp1 != Node->getOperand(0) || 360 Tmp2 != Node->getOperand(1)) 361 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, Tmp2, 362 cast<MVTSDNode>(Node)->getExtraValueType()); 363 else 364 Result = SDOperand(Node, 0); 365 366 // Since loads produce two values, make sure to remember that we legalized 367 // both of them. 368 AddLegalizedOperand(SDOperand(Node, 0), Result); 369 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 370 return Result.getValue(Op.ResNo); 371 372 case ISD::EXTRACT_ELEMENT: 373 // Get both the low and high parts. 374 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 375 if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) 376 Result = Tmp2; // 1 -> Hi 377 else 378 Result = Tmp1; // 0 -> Lo 379 break; 380 381 case ISD::CopyToReg: 382 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 383 384 switch (getTypeAction(Node->getOperand(1).getValueType())) { 385 case Legal: 386 // Legalize the incoming value (must be legal). 387 Tmp2 = LegalizeOp(Node->getOperand(1)); 388 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 389 Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg()); 390 break; 391 case Promote: 392 Tmp2 = PromoteOp(Node->getOperand(1)); 393 Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg()); 394 break; 395 case Expand: 396 SDOperand Lo, Hi; 397 ExpandOp(Node->getOperand(1), Lo, Hi); 398 unsigned Reg = cast<RegSDNode>(Node)->getReg(); 399 Result = DAG.getCopyToReg(Tmp1, Lo, Reg); 400 Result = DAG.getCopyToReg(Result, Hi, Reg+1); 401 assert(isTypeLegal(Result.getValueType()) && 402 "Cannot expand multiple times yet (i64 -> i16)"); 403 break; 404 } 405 break; 406 407 case ISD::RET: 408 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 409 switch (Node->getNumOperands()) { 410 case 2: // ret val 411 switch (getTypeAction(Node->getOperand(1).getValueType())) { 412 case Legal: 413 Tmp2 = LegalizeOp(Node->getOperand(1)); 414 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 415 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 416 break; 417 case Expand: { 418 SDOperand Lo, Hi; 419 ExpandOp(Node->getOperand(1), Lo, Hi); 420 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi); 421 break; 422 } 423 case Promote: 424 Tmp2 = PromoteOp(Node->getOperand(1)); 425 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 426 break; 427 } 428 break; 429 case 1: // ret void 430 if (Tmp1 != Node->getOperand(0)) 431 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1); 432 break; 433 default: { // ret <values> 434 std::vector<SDOperand> NewValues; 435 NewValues.push_back(Tmp1); 436 for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) 437 switch (getTypeAction(Node->getOperand(i).getValueType())) { 438 case Legal: 439 NewValues.push_back(LegalizeOp(Node->getOperand(i))); 440 break; 441 case Expand: { 442 SDOperand Lo, Hi; 443 ExpandOp(Node->getOperand(i), Lo, Hi); 444 NewValues.push_back(Lo); 445 NewValues.push_back(Hi); 446 break; 447 } 448 case Promote: 449 assert(0 && "Can't promote multiple return value yet!"); 450 } 451 Result = DAG.getNode(ISD::RET, MVT::Other, NewValues); 452 break; 453 } 454 } 455 break; 456 case ISD::STORE: 457 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 458 Tmp2 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 459 460 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 461 if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){ 462 if (CFP->getValueType(0) == MVT::f32) { 463 union { 464 unsigned I; 465 float F; 466 } V; 467 V.F = CFP->getValue(); 468 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 469 DAG.getConstant(V.I, MVT::i32), Tmp2); 470 } else { 471 assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!"); 472 union { 473 uint64_t I; 474 double F; 475 } V; 476 V.F = CFP->getValue(); 477 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 478 DAG.getConstant(V.I, MVT::i64), Tmp2); 479 } 480 Op = Result; 481 Node = Op.Val; 482 } 483 484 switch (getTypeAction(Node->getOperand(1).getValueType())) { 485 case Legal: { 486 SDOperand Val = LegalizeOp(Node->getOperand(1)); 487 if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) || 488 Tmp2 != Node->getOperand(2)) 489 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2); 490 break; 491 } 492 case Promote: 493 // Truncate the value and store the result. 494 Tmp3 = PromoteOp(Node->getOperand(1)); 495 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2, 496 Node->getOperand(1).getValueType()); 497 break; 498 499 case Expand: 500 SDOperand Lo, Hi; 501 ExpandOp(Node->getOperand(1), Lo, Hi); 502 503 if (!TLI.isLittleEndian()) 504 std::swap(Lo, Hi); 505 506 // FIXME: These two stores are independent of each other! 507 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2); 508 509 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 510 Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2, 511 getIntPtrConstant(IncrementSize)); 512 assert(isTypeLegal(Tmp2.getValueType()) && 513 "Pointers must be legal!"); 514 Result = DAG.getNode(ISD::STORE, MVT::Other, Result, Hi, Tmp2); 515 } 516 break; 517 case ISD::TRUNCSTORE: 518 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 519 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 520 521 switch (getTypeAction(Node->getOperand(1).getValueType())) { 522 case Legal: 523 Tmp2 = LegalizeOp(Node->getOperand(1)); 524 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 525 Tmp3 != Node->getOperand(2)) 526 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3, 527 cast<MVTSDNode>(Node)->getExtraValueType()); 528 break; 529 case Promote: 530 case Expand: 531 assert(0 && "Cannot handle illegal TRUNCSTORE yet!"); 532 } 533 break; 534 case ISD::SELECT: 535 switch (getTypeAction(Node->getOperand(0).getValueType())) { 536 case Expand: assert(0 && "It's impossible to expand bools"); 537 case Legal: 538 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 539 break; 540 case Promote: 541 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 542 break; 543 } 544 Tmp2 = LegalizeOp(Node->getOperand(1)); // TrueVal 545 Tmp3 = LegalizeOp(Node->getOperand(2)); // FalseVal 546 547 switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) { 548 default: assert(0 && "This action is not supported yet!"); 549 case TargetLowering::Legal: 550 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 551 Tmp3 != Node->getOperand(2)) 552 Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), 553 Tmp1, Tmp2, Tmp3); 554 break; 555 case TargetLowering::Promote: { 556 MVT::ValueType NVT = 557 TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType()); 558 unsigned ExtOp, TruncOp; 559 if (MVT::isInteger(Tmp2.getValueType())) { 560 ExtOp = ISD::ZERO_EXTEND; 561 TruncOp = ISD::TRUNCATE; 562 } else { 563 ExtOp = ISD::FP_EXTEND; 564 TruncOp = ISD::FP_ROUND; 565 } 566 // Promote each of the values to the new type. 567 Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2); 568 Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3); 569 // Perform the larger operation, then round down. 570 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3); 571 Result = DAG.getNode(TruncOp, Node->getValueType(0), Result); 572 break; 573 } 574 } 575 break; 576 case ISD::SETCC: 577 switch (getTypeAction(Node->getOperand(0).getValueType())) { 578 case Legal: 579 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 580 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 581 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 582 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 583 Node->getValueType(0), Tmp1, Tmp2); 584 break; 585 case Promote: 586 Tmp1 = PromoteOp(Node->getOperand(0)); // LHS 587 Tmp2 = PromoteOp(Node->getOperand(1)); // RHS 588 589 // If this is an FP compare, the operands have already been extended. 590 if (MVT::isInteger(Node->getOperand(0).getValueType())) { 591 MVT::ValueType VT = Node->getOperand(0).getValueType(); 592 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 593 594 // Otherwise, we have to insert explicit sign or zero extends. Note 595 // that we could insert sign extends for ALL conditions, but zero extend 596 // is cheaper on many machines (an AND instead of two shifts), so prefer 597 // it. 598 switch (cast<SetCCSDNode>(Node)->getCondition()) { 599 default: assert(0 && "Unknown integer comparison!"); 600 case ISD::SETEQ: 601 case ISD::SETNE: 602 case ISD::SETUGE: 603 case ISD::SETUGT: 604 case ISD::SETULE: 605 case ISD::SETULT: 606 // ALL of these operations will work if we either sign or zero extend 607 // the operands (including the unsigned comparisons!). Zero extend is 608 // usually a simpler/cheaper operation, so prefer it. 609 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT); 610 Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT); 611 break; 612 case ISD::SETGE: 613 case ISD::SETGT: 614 case ISD::SETLT: 615 case ISD::SETLE: 616 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT); 617 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT); 618 break; 619 } 620 621 } 622 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 623 Node->getValueType(0), Tmp1, Tmp2); 624 break; 625 case Expand: 626 SDOperand LHSLo, LHSHi, RHSLo, RHSHi; 627 ExpandOp(Node->getOperand(0), LHSLo, LHSHi); 628 ExpandOp(Node->getOperand(1), RHSLo, RHSHi); 629 switch (cast<SetCCSDNode>(Node)->getCondition()) { 630 case ISD::SETEQ: 631 case ISD::SETNE: 632 Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo); 633 Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi); 634 Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2); 635 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 636 Node->getValueType(0), Tmp1, 637 DAG.getConstant(0, Tmp1.getValueType())); 638 break; 639 default: 640 // FIXME: This generated code sucks. 641 ISD::CondCode LowCC; 642 switch (cast<SetCCSDNode>(Node)->getCondition()) { 643 default: assert(0 && "Unknown integer setcc!"); 644 case ISD::SETLT: 645 case ISD::SETULT: LowCC = ISD::SETULT; break; 646 case ISD::SETGT: 647 case ISD::SETUGT: LowCC = ISD::SETUGT; break; 648 case ISD::SETLE: 649 case ISD::SETULE: LowCC = ISD::SETULE; break; 650 case ISD::SETGE: 651 case ISD::SETUGE: LowCC = ISD::SETUGE; break; 652 } 653 654 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison 655 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands 656 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2; 657 658 // NOTE: on targets without efficient SELECT of bools, we can always use 659 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3) 660 Tmp1 = DAG.getSetCC(LowCC, Node->getValueType(0), LHSLo, RHSLo); 661 Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 662 Node->getValueType(0), LHSHi, RHSHi); 663 Result = DAG.getSetCC(ISD::SETEQ, Node->getValueType(0), LHSHi, RHSHi); 664 Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(), 665 Result, Tmp1, Tmp2); 666 break; 667 } 668 } 669 break; 670 671 case ISD::MEMSET: 672 case ISD::MEMCPY: 673 case ISD::MEMMOVE: { 674 Tmp1 = LegalizeOp(Node->getOperand(0)); 675 Tmp2 = LegalizeOp(Node->getOperand(1)); 676 Tmp3 = LegalizeOp(Node->getOperand(2)); 677 SDOperand Tmp4 = LegalizeOp(Node->getOperand(3)); 678 SDOperand Tmp5 = LegalizeOp(Node->getOperand(4)); 679 680 switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) { 681 default: assert(0 && "This action not implemented for this operation!"); 682 case TargetLowering::Legal: 683 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 684 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) || 685 Tmp5 != Node->getOperand(4)) { 686 std::vector<SDOperand> Ops; 687 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 688 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 689 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 690 } 691 break; 692 case TargetLowering::Expand: { 693 // Otherwise, the target does not support this operation. Lower the 694 // operation to an explicit libcall as appropriate. 695 MVT::ValueType IntPtr = TLI.getPointerTy(); 696 const Type *IntPtrTy = TLI.getTargetData().getIntPtrType(); 697 std::vector<std::pair<SDOperand, const Type*> > Args; 698 699 const char *FnName = 0; 700 if (Node->getOpcode() == ISD::MEMSET) { 701 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 702 // Extend the ubyte argument to be an int value for the call. 703 Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3); 704 Args.push_back(std::make_pair(Tmp3, Type::IntTy)); 705 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 706 707 FnName = "memset"; 708 } else if (Node->getOpcode() == ISD::MEMCPY || 709 Node->getOpcode() == ISD::MEMMOVE) { 710 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 711 Args.push_back(std::make_pair(Tmp3, IntPtrTy)); 712 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 713 FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy"; 714 } else { 715 assert(0 && "Unknown op!"); 716 } 717 std::pair<SDOperand,SDOperand> CallResult = 718 TLI.LowerCallTo(Tmp1, Type::VoidTy, 719 DAG.getExternalSymbol(FnName, IntPtr), Args, DAG); 720 Result = LegalizeOp(CallResult.second); 721 break; 722 } 723 case TargetLowering::Custom: 724 std::vector<SDOperand> Ops; 725 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 726 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 727 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 728 Result = TLI.LowerOperation(Result); 729 Result = LegalizeOp(Result); 730 break; 731 } 732 break; 733 } 734 case ISD::ADD: 735 case ISD::SUB: 736 case ISD::MUL: 737 case ISD::UDIV: 738 case ISD::SDIV: 739 case ISD::UREM: 740 case ISD::SREM: 741 case ISD::AND: 742 case ISD::OR: 743 case ISD::XOR: 744 case ISD::SHL: 745 case ISD::SRL: 746 case ISD::SRA: 747 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 748 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 749 if (Tmp1 != Node->getOperand(0) || 750 Tmp2 != Node->getOperand(1)) 751 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2); 752 break; 753 case ISD::ZERO_EXTEND: 754 case ISD::SIGN_EXTEND: 755 case ISD::TRUNCATE: 756 case ISD::FP_EXTEND: 757 case ISD::FP_ROUND: 758 case ISD::FP_TO_SINT: 759 case ISD::FP_TO_UINT: 760 case ISD::SINT_TO_FP: 761 case ISD::UINT_TO_FP: 762 switch (getTypeAction(Node->getOperand(0).getValueType())) { 763 case Legal: 764 Tmp1 = LegalizeOp(Node->getOperand(0)); 765 if (Tmp1 != Node->getOperand(0)) 766 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 767 break; 768 case Expand: 769 assert(Node->getOpcode() != ISD::SINT_TO_FP && 770 Node->getOpcode() != ISD::UINT_TO_FP && 771 "Cannot lower Xint_to_fp to a call yet!"); 772 773 // In the expand case, we must be dealing with a truncate, because 774 // otherwise the result would be larger than the source. 775 assert(Node->getOpcode() == ISD::TRUNCATE && 776 "Shouldn't need to expand other operators here!"); 777 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 778 779 // Since the result is legal, we should just be able to truncate the low 780 // part of the source. 781 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1); 782 break; 783 784 case Promote: 785 switch (Node->getOpcode()) { 786 case ISD::ZERO_EXTEND: 787 Result = PromoteOp(Node->getOperand(0)); 788 // NOTE: Any extend would work here... 789 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result); 790 Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Op.getValueType(), 791 Result, Node->getOperand(0).getValueType()); 792 break; 793 case ISD::SIGN_EXTEND: 794 Result = PromoteOp(Node->getOperand(0)); 795 // NOTE: Any extend would work here... 796 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result); 797 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 798 Result, Node->getOperand(0).getValueType()); 799 break; 800 case ISD::TRUNCATE: 801 Result = PromoteOp(Node->getOperand(0)); 802 Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result); 803 break; 804 case ISD::FP_EXTEND: 805 Result = PromoteOp(Node->getOperand(0)); 806 if (Result.getValueType() != Op.getValueType()) 807 // Dynamically dead while we have only 2 FP types. 808 Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result); 809 break; 810 case ISD::FP_ROUND: 811 case ISD::FP_TO_SINT: 812 case ISD::FP_TO_UINT: 813 Result = PromoteOp(Node->getOperand(0)); 814 Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result); 815 break; 816 case ISD::SINT_TO_FP: 817 Result = PromoteOp(Node->getOperand(0)); 818 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 819 Result, Node->getOperand(0).getValueType()); 820 Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result); 821 break; 822 case ISD::UINT_TO_FP: 823 Result = PromoteOp(Node->getOperand(0)); 824 Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(), 825 Result, Node->getOperand(0).getValueType()); 826 Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result); 827 break; 828 } 829 } 830 break; 831 case ISD::FP_ROUND_INREG: 832 case ISD::SIGN_EXTEND_INREG: 833 case ISD::ZERO_EXTEND_INREG: { 834 Tmp1 = LegalizeOp(Node->getOperand(0)); 835 MVT::ValueType ExtraVT = cast<MVTSDNode>(Node)->getExtraValueType(); 836 837 // If this operation is not supported, convert it to a shl/shr or load/store 838 // pair. 839 switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) { 840 default: assert(0 && "This action not supported for this op yet!"); 841 case TargetLowering::Legal: 842 if (Tmp1 != Node->getOperand(0)) 843 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 844 ExtraVT); 845 break; 846 case TargetLowering::Expand: 847 // If this is an integer extend and shifts are supported, do that. 848 if (Node->getOpcode() == ISD::ZERO_EXTEND_INREG) { 849 // NOTE: we could fall back on load/store here too for targets without 850 // AND. However, it is doubtful that any exist. 851 // AND out the appropriate bits. 852 SDOperand Mask = 853 DAG.getConstant((1ULL << MVT::getSizeInBits(ExtraVT))-1, 854 Node->getValueType(0)); 855 Result = DAG.getNode(ISD::AND, Node->getValueType(0), 856 Node->getOperand(0), Mask); 857 } else if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) { 858 // NOTE: we could fall back on load/store here too for targets without 859 // SAR. However, it is doubtful that any exist. 860 unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) - 861 MVT::getSizeInBits(ExtraVT); 862 SDOperand ShiftCst = DAG.getConstant(BitsDiff, MVT::i8); 863 Result = DAG.getNode(ISD::SHL, Node->getValueType(0), 864 Node->getOperand(0), ShiftCst); 865 Result = DAG.getNode(ISD::SRA, Node->getValueType(0), 866 Result, ShiftCst); 867 } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) { 868 // The only way we can lower this is to turn it into a STORETRUNC, 869 // EXTLOAD pair, targetting a temporary location (a stack slot). 870 871 // NOTE: there is a choice here between constantly creating new stack 872 // slots and always reusing the same one. We currently always create 873 // new ones, as reuse may inhibit scheduling. 874 const Type *Ty = MVT::getTypeForValueType(ExtraVT); 875 unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty); 876 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); 877 MachineFunction &MF = DAG.getMachineFunction(); 878 int SSFI = 879 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 880 SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); 881 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(), 882 Node->getOperand(0), StackSlot, ExtraVT); 883 Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0), 884 Result, StackSlot, ExtraVT); 885 } else { 886 assert(0 && "Unknown op"); 887 } 888 Result = LegalizeOp(Result); 889 break; 890 } 891 break; 892 } 893 } 894 895 if (!Op.Val->hasOneUse()) 896 AddLegalizedOperand(Op, Result); 897 898 return Result; 899} 900 901/// PromoteOp - Given an operation that produces a value in an invalid type, 902/// promote it to compute the value into a larger type. The produced value will 903/// have the correct bits for the low portion of the register, but no guarantee 904/// is made about the top bits: it may be zero, sign-extended, or garbage. 905SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { 906 MVT::ValueType VT = Op.getValueType(); 907 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 908 assert(getTypeAction(VT) == Promote && 909 "Caller should expand or legalize operands that are not promotable!"); 910 assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) && 911 "Cannot promote to smaller type!"); 912 913 std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op); 914 if (I != PromotedNodes.end()) return I->second; 915 916 SDOperand Tmp1, Tmp2, Tmp3; 917 918 SDOperand Result; 919 SDNode *Node = Op.Val; 920 921 // Promotion needs an optimization step to clean up after it, and is not 922 // careful to avoid operations the target does not support. Make sure that 923 // all generated operations are legalized in the next iteration. 924 NeedsAnotherIteration = true; 925 926 switch (Node->getOpcode()) { 927 default: 928 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 929 assert(0 && "Do not know how to promote this operator!"); 930 abort(); 931 case ISD::Constant: 932 Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op); 933 assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?"); 934 break; 935 case ISD::ConstantFP: 936 Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op); 937 assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?"); 938 break; 939 case ISD::CopyFromReg: 940 Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), NVT, 941 Node->getOperand(0)); 942 // Remember that we legalized the chain. 943 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 944 break; 945 946 case ISD::SETCC: 947 assert(getTypeAction(TLI.getSetCCResultTy()) == Legal && 948 "SetCC type is not legal??"); 949 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 950 TLI.getSetCCResultTy(), Node->getOperand(0), 951 Node->getOperand(1)); 952 Result = LegalizeOp(Result); 953 break; 954 955 case ISD::TRUNCATE: 956 switch (getTypeAction(Node->getOperand(0).getValueType())) { 957 case Legal: 958 Result = LegalizeOp(Node->getOperand(0)); 959 assert(Result.getValueType() >= NVT && 960 "This truncation doesn't make sense!"); 961 if (Result.getValueType() > NVT) // Truncate to NVT instead of VT 962 Result = DAG.getNode(ISD::TRUNCATE, NVT, Result); 963 break; 964 case Expand: 965 assert(0 && "Cannot handle expand yet"); 966 case Promote: 967 assert(0 && "Cannot handle promote-promote yet"); 968 } 969 break; 970 case ISD::SIGN_EXTEND: 971 case ISD::ZERO_EXTEND: 972 switch (getTypeAction(Node->getOperand(0).getValueType())) { 973 case Expand: assert(0 && "BUG: Smaller reg should have been promoted!"); 974 case Legal: 975 // Input is legal? Just do extend all the way to the larger type. 976 Result = LegalizeOp(Node->getOperand(0)); 977 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 978 break; 979 case Promote: 980 // Promote the reg if it's smaller. 981 Result = PromoteOp(Node->getOperand(0)); 982 // The high bits are not guaranteed to be anything. Insert an extend. 983 if (Node->getOpcode() == ISD::SIGN_EXTEND) 984 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result, VT); 985 else 986 Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Result, VT); 987 break; 988 } 989 break; 990 991 case ISD::FP_EXTEND: 992 assert(0 && "Case not implemented. Dynamically dead with 2 FP types!"); 993 case ISD::FP_ROUND: 994 switch (getTypeAction(Node->getOperand(0).getValueType())) { 995 case Expand: assert(0 && "BUG: Cannot expand FP regs!"); 996 case Promote: assert(0 && "Unreachable with 2 FP types!"); 997 case Legal: 998 // Input is legal? Do an FP_ROUND_INREG. 999 Result = LegalizeOp(Node->getOperand(0)); 1000 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1001 break; 1002 } 1003 break; 1004 1005 case ISD::SINT_TO_FP: 1006 case ISD::UINT_TO_FP: 1007 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1008 case Legal: 1009 Result = LegalizeOp(Node->getOperand(0)); 1010 break; 1011 1012 case Promote: 1013 Result = PromoteOp(Node->getOperand(0)); 1014 if (Node->getOpcode() == ISD::SINT_TO_FP) 1015 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 1016 Result, Node->getOperand(0).getValueType()); 1017 else 1018 Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(), 1019 Result, Node->getOperand(0).getValueType()); 1020 break; 1021 case Expand: 1022 assert(0 && "Unimplemented"); 1023 } 1024 // No extra round required here. 1025 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 1026 break; 1027 1028 case ISD::FP_TO_SINT: 1029 case ISD::FP_TO_UINT: 1030 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1031 case Legal: 1032 Tmp1 = LegalizeOp(Node->getOperand(0)); 1033 break; 1034 case Promote: 1035 // The input result is prerounded, so we don't have to do anything 1036 // special. 1037 Tmp1 = PromoteOp(Node->getOperand(0)); 1038 break; 1039 case Expand: 1040 assert(0 && "not implemented"); 1041 } 1042 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 1043 break; 1044 1045 case ISD::AND: 1046 case ISD::OR: 1047 case ISD::XOR: 1048 case ISD::ADD: 1049 case ISD::SUB: 1050 case ISD::MUL: 1051 // The input may have strange things in the top bits of the registers, but 1052 // these operations don't care. They may have wierd bits going out, but 1053 // that too is okay if they are integer operations. 1054 Tmp1 = PromoteOp(Node->getOperand(0)); 1055 Tmp2 = PromoteOp(Node->getOperand(1)); 1056 assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT); 1057 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 1058 1059 // However, if this is a floating point operation, they will give excess 1060 // precision that we may not be able to tolerate. If we DO allow excess 1061 // precision, just leave it, otherwise excise it. 1062 // FIXME: Why would we need to round FP ops more than integer ones? 1063 // Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C)) 1064 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision) 1065 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1066 break; 1067 1068 case ISD::SDIV: 1069 case ISD::SREM: 1070 // These operators require that their input be sign extended. 1071 Tmp1 = PromoteOp(Node->getOperand(0)); 1072 Tmp2 = PromoteOp(Node->getOperand(1)); 1073 if (MVT::isInteger(NVT)) { 1074 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT); 1075 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT); 1076 } 1077 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 1078 1079 // Perform FP_ROUND: this is probably overly pessimistic. 1080 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision) 1081 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); 1082 break; 1083 1084 case ISD::UDIV: 1085 case ISD::UREM: 1086 // These operators require that their input be zero extended. 1087 Tmp1 = PromoteOp(Node->getOperand(0)); 1088 Tmp2 = PromoteOp(Node->getOperand(1)); 1089 assert(MVT::isInteger(NVT) && "Operators don't apply to FP!"); 1090 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT); 1091 Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT); 1092 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 1093 break; 1094 1095 case ISD::SHL: 1096 Tmp1 = PromoteOp(Node->getOperand(0)); 1097 Tmp2 = LegalizeOp(Node->getOperand(1)); 1098 Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2); 1099 break; 1100 case ISD::SRA: 1101 // The input value must be properly sign extended. 1102 Tmp1 = PromoteOp(Node->getOperand(0)); 1103 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT); 1104 Tmp2 = LegalizeOp(Node->getOperand(1)); 1105 Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2); 1106 break; 1107 case ISD::SRL: 1108 // The input value must be properly zero extended. 1109 Tmp1 = PromoteOp(Node->getOperand(0)); 1110 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT); 1111 Tmp2 = LegalizeOp(Node->getOperand(1)); 1112 Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2); 1113 break; 1114 case ISD::LOAD: 1115 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1116 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 1117 Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, VT); 1118 1119 // Remember that we legalized the chain. 1120 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 1121 break; 1122 case ISD::SELECT: 1123 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1124 case Expand: assert(0 && "It's impossible to expand bools"); 1125 case Legal: 1126 Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition. 1127 break; 1128 case Promote: 1129 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 1130 break; 1131 } 1132 Tmp2 = PromoteOp(Node->getOperand(1)); // Legalize the op0 1133 Tmp3 = PromoteOp(Node->getOperand(2)); // Legalize the op1 1134 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3); 1135 break; 1136 case ISD::CALL: { 1137 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1138 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 1139 1140 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 1141 "Can only promote single result calls"); 1142 std::vector<MVT::ValueType> RetTyVTs; 1143 RetTyVTs.reserve(2); 1144 RetTyVTs.push_back(NVT); 1145 RetTyVTs.push_back(MVT::Other); 1146 SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2); 1147 Result = SDOperand(NC, 0); 1148 1149 // Insert the new chain mapping. 1150 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 1151 break; 1152 } 1153 } 1154 1155 assert(Result.Val && "Didn't set a result!"); 1156 AddPromotedOperand(Op, Result); 1157 return Result; 1158} 1159 1160/// ExpandOp - Expand the specified SDOperand into its two component pieces 1161/// Lo&Hi. Note that the Op MUST be an expanded type. As a result of this, the 1162/// LegalizeNodes map is filled in for any results that are not expanded, the 1163/// ExpandedNodes map is filled in for any results that are expanded, and the 1164/// Lo/Hi values are returned. 1165void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ 1166 MVT::ValueType VT = Op.getValueType(); 1167 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 1168 SDNode *Node = Op.Val; 1169 assert(getTypeAction(VT) == Expand && "Not an expanded type!"); 1170 assert(MVT::isInteger(VT) && "Cannot expand FP values!"); 1171 assert(MVT::isInteger(NVT) && NVT < VT && 1172 "Cannot expand to FP value or to larger int value!"); 1173 1174 // If there is more than one use of this, see if we already expanded it. 1175 // There is no use remembering values that only have a single use, as the map 1176 // entries will never be reused. 1177 if (!Node->hasOneUse()) { 1178 std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I 1179 = ExpandedNodes.find(Op); 1180 if (I != ExpandedNodes.end()) { 1181 Lo = I->second.first; 1182 Hi = I->second.second; 1183 return; 1184 } 1185 } 1186 1187 // Expanding to multiple registers needs to perform an optimization step, and 1188 // is not careful to avoid operations the target does not support. Make sure 1189 // that all generated operations are legalized in the next iteration. 1190 NeedsAnotherIteration = true; 1191 const char *LibCallName = 0; 1192 1193 switch (Node->getOpcode()) { 1194 default: 1195 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 1196 assert(0 && "Do not know how to expand this operator!"); 1197 abort(); 1198 case ISD::Constant: { 1199 uint64_t Cst = cast<ConstantSDNode>(Node)->getValue(); 1200 Lo = DAG.getConstant(Cst, NVT); 1201 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT); 1202 break; 1203 } 1204 1205 case ISD::CopyFromReg: { 1206 unsigned Reg = cast<RegSDNode>(Node)->getReg(); 1207 // Aggregate register values are always in consequtive pairs. 1208 Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0)); 1209 Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1)); 1210 1211 // Remember that we legalized the chain. 1212 AddLegalizedOperand(Op.getValue(1), Hi.getValue(1)); 1213 1214 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!"); 1215 break; 1216 } 1217 1218 case ISD::LOAD: { 1219 SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1220 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 1221 Lo = DAG.getLoad(NVT, Ch, Ptr); 1222 1223 // Increment the pointer to the other half. 1224 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 1225 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 1226 getIntPtrConstant(IncrementSize)); 1227 // FIXME: This load is independent of the first one. 1228 Hi = DAG.getLoad(NVT, Lo.getValue(1), Ptr); 1229 1230 // Remember that we legalized the chain. 1231 AddLegalizedOperand(Op.getValue(1), Hi.getValue(1)); 1232 if (!TLI.isLittleEndian()) 1233 std::swap(Lo, Hi); 1234 break; 1235 } 1236 case ISD::CALL: { 1237 SDOperand Chain = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 1238 SDOperand Callee = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 1239 1240 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 1241 "Can only expand a call once so far, not i64 -> i16!"); 1242 1243 std::vector<MVT::ValueType> RetTyVTs; 1244 RetTyVTs.reserve(3); 1245 RetTyVTs.push_back(NVT); 1246 RetTyVTs.push_back(NVT); 1247 RetTyVTs.push_back(MVT::Other); 1248 SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee); 1249 Lo = SDOperand(NC, 0); 1250 Hi = SDOperand(NC, 1); 1251 1252 // Insert the new chain mapping. 1253 AddLegalizedOperand(Op.getValue(1), Hi.getValue(2)); 1254 break; 1255 } 1256 case ISD::AND: 1257 case ISD::OR: 1258 case ISD::XOR: { // Simple logical operators -> two trivial pieces. 1259 SDOperand LL, LH, RL, RH; 1260 ExpandOp(Node->getOperand(0), LL, LH); 1261 ExpandOp(Node->getOperand(1), RL, RH); 1262 Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL); 1263 Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH); 1264 break; 1265 } 1266 case ISD::SELECT: { 1267 SDOperand C, LL, LH, RL, RH; 1268 1269 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1270 case Expand: assert(0 && "It's impossible to expand bools"); 1271 case Legal: 1272 C = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 1273 break; 1274 case Promote: 1275 C = PromoteOp(Node->getOperand(0)); // Promote the condition. 1276 break; 1277 } 1278 ExpandOp(Node->getOperand(1), LL, LH); 1279 ExpandOp(Node->getOperand(2), RL, RH); 1280 Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL); 1281 Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH); 1282 break; 1283 } 1284 case ISD::SIGN_EXTEND: { 1285 // The low part is just a sign extension of the input (which degenerates to 1286 // a copy). 1287 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0))); 1288 1289 // The high part is obtained by SRA'ing all but one of the bits of the lo 1290 // part. 1291 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); 1292 Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, MVT::i8)); 1293 break; 1294 } 1295 case ISD::ZERO_EXTEND: 1296 // The low part is just a zero extension of the input (which degenerates to 1297 // a copy). 1298 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0))); 1299 1300 // The high part is just a zero. 1301 Hi = DAG.getConstant(0, NVT); 1302 break; 1303 1304 // These operators cannot be expanded directly, emit them as calls to 1305 // library functions. 1306 case ISD::FP_TO_SINT: 1307 if (Node->getOperand(0).getValueType() == MVT::f32) 1308 LibCallName = "__fixsfdi"; 1309 else 1310 LibCallName = "__fixdfdi"; 1311 break; 1312 case ISD::FP_TO_UINT: 1313 if (Node->getOperand(0).getValueType() == MVT::f32) 1314 LibCallName = "__fixunssfdi"; 1315 else 1316 LibCallName = "__fixunsdfdi"; 1317 break; 1318 1319 case ISD::ADD: LibCallName = "__adddi3"; break; 1320 case ISD::SUB: LibCallName = "__subdi3"; break; 1321 case ISD::MUL: LibCallName = "__muldi3"; break; 1322 case ISD::SDIV: LibCallName = "__divdi3"; break; 1323 case ISD::UDIV: LibCallName = "__udivdi3"; break; 1324 case ISD::SREM: LibCallName = "__moddi3"; break; 1325 case ISD::UREM: LibCallName = "__umoddi3"; break; 1326 case ISD::SHL: LibCallName = "__ashldi3"; break; 1327 case ISD::SRA: LibCallName = "__ashrdi3"; break; 1328 case ISD::SRL: LibCallName = "__lshrdi3"; break; 1329 } 1330 1331 // Int2FP -> __floatdisf/__floatdidf 1332 1333 // If this is to be expanded into a libcall... do so now. 1334 if (LibCallName) { 1335 TargetLowering::ArgListTy Args; 1336 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) 1337 Args.push_back(std::make_pair(Node->getOperand(i), 1338 MVT::getTypeForValueType(Node->getOperand(i).getValueType()))); 1339 SDOperand Callee = DAG.getExternalSymbol(LibCallName, TLI.getPointerTy()); 1340 1341 // We don't care about token chains for libcalls. We just use the entry 1342 // node as our input and ignore the output chain. This allows us to place 1343 // calls wherever we need them to satisfy data dependences. 1344 SDOperand Result = TLI.LowerCallTo(DAG.getEntryNode(), 1345 MVT::getTypeForValueType(Op.getValueType()), Callee, 1346 Args, DAG).first; 1347 ExpandOp(Result, Lo, Hi); 1348 } 1349 1350 // Remember in a map if the values will be reused later. 1351 if (!Node->hasOneUse()) { 1352 bool isNew = ExpandedNodes.insert(std::make_pair(Op, 1353 std::make_pair(Lo, Hi))).second; 1354 assert(isNew && "Value already expanded?!?"); 1355 } 1356} 1357 1358 1359// SelectionDAG::Legalize - This is the entry point for the file. 1360// 1361void SelectionDAG::Legalize(TargetLowering &TLI) { 1362 /// run - This is the main entry point to this class. 1363 /// 1364 SelectionDAGLegalize(TLI, *this).Run(); 1365} 1366 1367