LegalizeDAG.cpp revision a385e9b20fa7d37d3842ce15afd412f617d83a27
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/Target/TargetLowering.h" 18#include "llvm/Target/TargetData.h" 19#include "llvm/Constants.h" 20#include <iostream> 21using namespace llvm; 22 23static const Type *getTypeFor(MVT::ValueType VT) { 24 switch (VT) { 25 default: assert(0 && "Unknown MVT!"); 26 case MVT::i1: return Type::BoolTy; 27 case MVT::i8: return Type::UByteTy; 28 case MVT::i16: return Type::UShortTy; 29 case MVT::i32: return Type::UIntTy; 30 case MVT::i64: return Type::ULongTy; 31 case MVT::f32: return Type::FloatTy; 32 case MVT::f64: return Type::DoubleTy; 33 } 34} 35 36 37//===----------------------------------------------------------------------===// 38/// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and 39/// hacks on it until the target machine can handle it. This involves 40/// eliminating value sizes the machine cannot handle (promoting small sizes to 41/// large sizes or splitting up large values into small values) as well as 42/// eliminating operations the machine cannot handle. 43/// 44/// This code also does a small amount of optimization and recognition of idioms 45/// as part of its processing. For example, if a target does not support a 46/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this 47/// will attempt merge setcc and brc instructions into brcc's. 48/// 49namespace { 50class SelectionDAGLegalize { 51 TargetLowering &TLI; 52 SelectionDAG &DAG; 53 54 /// LegalizeAction - This enum indicates what action we should take for each 55 /// value type the can occur in the program. 56 enum LegalizeAction { 57 Legal, // The target natively supports this value type. 58 Promote, // This should be promoted to the next larger type. 59 Expand, // This integer type should be broken into smaller pieces. 60 }; 61 62 /// TransformToType - For any value types we are promoting or expanding, this 63 /// contains the value type that we are changing to. For Expanded types, this 64 /// contains one step of the expand (e.g. i64 -> i32), even if there are 65 /// multiple steps required (e.g. i64 -> i16) 66 MVT::ValueType TransformToType[MVT::LAST_VALUETYPE]; 67 68 /// ValueTypeActions - This is a bitvector that contains two bits for each 69 /// value type, where the two bits correspond to the LegalizeAction enum. 70 /// This can be queried with "getTypeAction(VT)". 71 unsigned ValueTypeActions; 72 73 /// NeedsAnotherIteration - This is set when we expand a large integer 74 /// operation into smaller integer operations, but the smaller operations are 75 /// not set. This occurs only rarely in practice, for targets that don't have 76 /// 32-bit or larger integer registers. 77 bool NeedsAnotherIteration; 78 79 /// LegalizedNodes - For nodes that are of legal width, and that have more 80 /// than one use, this map indicates what regularized operand to use. This 81 /// allows us to avoid legalizing the same thing more than once. 82 std::map<SDOperand, SDOperand> LegalizedNodes; 83 84 /// ExpandedNodes - For nodes that need to be expanded, and which have more 85 /// than one use, this map indicates which which operands are the expanded 86 /// version of the input. This allows us to avoid expanding the same node 87 /// more than once. 88 std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes; 89 90 void AddLegalizedOperand(SDOperand From, SDOperand To) { 91 bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second; 92 assert(isNew && "Got into the map somehow?"); 93 } 94 95 /// setValueTypeAction - Set the action for a particular value type. This 96 /// assumes an action has not already been set for this value type. 97 void setValueTypeAction(MVT::ValueType VT, LegalizeAction A) { 98 ValueTypeActions |= A << (VT*2); 99 if (A == Promote) { 100 MVT::ValueType PromoteTo; 101 if (VT == MVT::f32) 102 PromoteTo = MVT::f64; 103 else { 104 unsigned LargerReg = VT+1; 105 while (!TLI.hasNativeSupportFor((MVT::ValueType)LargerReg)) { 106 ++LargerReg; 107 assert(MVT::isInteger((MVT::ValueType)LargerReg) && 108 "Nothing to promote to??"); 109 } 110 PromoteTo = (MVT::ValueType)LargerReg; 111 } 112 113 assert(MVT::isInteger(VT) == MVT::isInteger(PromoteTo) && 114 MVT::isFloatingPoint(VT) == MVT::isFloatingPoint(PromoteTo) && 115 "Can only promote from int->int or fp->fp!"); 116 assert(VT < PromoteTo && "Must promote to a larger type!"); 117 TransformToType[VT] = PromoteTo; 118 } else if (A == Expand) { 119 assert(MVT::isInteger(VT) && VT > MVT::i8 && 120 "Cannot expand this type: target must support SOME integer reg!"); 121 // Expand to the next smaller integer type! 122 TransformToType[VT] = (MVT::ValueType)(VT-1); 123 } 124 } 125 126public: 127 128 SelectionDAGLegalize(TargetLowering &TLI, SelectionDAG &DAG); 129 130 /// Run - While there is still lowering to do, perform a pass over the DAG. 131 /// Most regularization can be done in a single pass, but targets that require 132 /// large values to be split into registers multiple times (e.g. i64 -> 4x 133 /// i16) require iteration for these values (the first iteration will demote 134 /// to i32, the second will demote to i16). 135 void Run() { 136 do { 137 NeedsAnotherIteration = false; 138 LegalizeDAG(); 139 } while (NeedsAnotherIteration); 140 } 141 142 /// getTypeAction - Return how we should legalize values of this type, either 143 /// it is already legal or we need to expand it into multiple registers of 144 /// smaller integer type, or we need to promote it to a larger type. 145 LegalizeAction getTypeAction(MVT::ValueType VT) const { 146 return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3); 147 } 148 149 /// isTypeLegal - Return true if this type is legal on this target. 150 /// 151 bool isTypeLegal(MVT::ValueType VT) const { 152 return getTypeAction(VT) == Legal; 153 } 154 155private: 156 void LegalizeDAG(); 157 158 SDOperand LegalizeOp(SDOperand O); 159 void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi); 160 161 SDOperand getIntPtrConstant(uint64_t Val) { 162 return DAG.getConstant(Val, TLI.getPointerTy()); 163 } 164}; 165} 166 167 168SelectionDAGLegalize::SelectionDAGLegalize(TargetLowering &tli, 169 SelectionDAG &dag) 170 : TLI(tli), DAG(dag), ValueTypeActions(0) { 171 172 assert(MVT::LAST_VALUETYPE <= 16 && 173 "Too many value types for ValueTypeActions to hold!"); 174 175 // Inspect all of the ValueType's possible, deciding how to process them. 176 for (unsigned IntReg = MVT::i1; IntReg <= MVT::i128; ++IntReg) 177 // If TLI says we are expanding this type, expand it! 178 if (TLI.getNumElements((MVT::ValueType)IntReg) != 1) 179 setValueTypeAction((MVT::ValueType)IntReg, Expand); 180 else if (!TLI.hasNativeSupportFor((MVT::ValueType)IntReg)) 181 // Otherwise, if we don't have native support, we must promote to a 182 // larger type. 183 setValueTypeAction((MVT::ValueType)IntReg, Promote); 184 185 // If the target does not have native support for F32, promote it to F64. 186 if (!TLI.hasNativeSupportFor(MVT::f32)) 187 setValueTypeAction(MVT::f32, Promote); 188} 189 190void SelectionDAGLegalize::LegalizeDAG() { 191 SDOperand OldRoot = DAG.getRoot(); 192 SDOperand NewRoot = LegalizeOp(OldRoot); 193 DAG.setRoot(NewRoot); 194 195 ExpandedNodes.clear(); 196 LegalizedNodes.clear(); 197 198 // Remove dead nodes now. 199 DAG.RemoveDeadNodes(OldRoot.Val); 200} 201 202SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { 203 assert(getTypeAction(Op.getValueType()) == Legal && 204 "Caller should expand or promote operands that are not legal!"); 205 206 // If this operation defines any values that cannot be represented in a 207 // register on this target, make sure to expand or promote them. 208 if (Op.Val->getNumValues() > 1) { 209 for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i) 210 switch (getTypeAction(Op.Val->getValueType(i))) { 211 case Legal: break; // Nothing to do. 212 case Expand: { 213 SDOperand T1, T2; 214 ExpandOp(Op.getValue(i), T1, T2); 215 assert(LegalizedNodes.count(Op) && 216 "Expansion didn't add legal operands!"); 217 return LegalizedNodes[Op]; 218 } 219 case Promote: 220 // FIXME: Implement promotion! 221 assert(0 && "Promotion not implemented at all yet!"); 222 } 223 } 224 225 std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op); 226 if (I != LegalizedNodes.end()) return I->second; 227 228 SDOperand Tmp1, Tmp2, Tmp3; 229 230 SDOperand Result = Op; 231 SDNode *Node = Op.Val; 232 233 switch (Node->getOpcode()) { 234 default: 235 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 236 assert(0 && "Do not know how to legalize this operator!"); 237 abort(); 238 case ISD::EntryToken: 239 case ISD::FrameIndex: 240 case ISD::GlobalAddress: 241 case ISD::ExternalSymbol: 242 case ISD::ConstantPool: 243 case ISD::CopyFromReg: // Nothing to do. 244 assert(getTypeAction(Node->getValueType(0)) == Legal && 245 "This must be legal!"); 246 break; 247 case ISD::Constant: 248 // We know we don't need to expand constants here, constants only have one 249 // value and we check that it is fine above. 250 251 // FIXME: Maybe we should handle things like targets that don't support full 252 // 32-bit immediates? 253 break; 254 case ISD::ConstantFP: { 255 // Spill FP immediates to the constant pool if the target cannot directly 256 // codegen them. Targets often have some immediate values that can be 257 // efficiently generated into an FP register without a load. We explicitly 258 // leave these constants as ConstantFP nodes for the target to deal with. 259 260 ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node); 261 262 // Check to see if this FP immediate is already legal. 263 bool isLegal = false; 264 for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(), 265 E = TLI.legal_fpimm_end(); I != E; ++I) 266 if (CFP->isExactlyValue(*I)) { 267 isLegal = true; 268 break; 269 } 270 271 if (!isLegal) { 272 // Otherwise we need to spill the constant to memory. 273 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); 274 275 bool Extend = false; 276 277 // If a FP immediate is precise when represented as a float, we put it 278 // into the constant pool as a float, even if it's is statically typed 279 // as a double. 280 MVT::ValueType VT = CFP->getValueType(0); 281 bool isDouble = VT == MVT::f64; 282 ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy : 283 Type::FloatTy, CFP->getValue()); 284 if (isDouble && CFP->isExactlyValue((float)CFP->getValue())) { 285 LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy)); 286 VT = MVT::f32; 287 Extend = true; 288 } 289 290 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC), 291 TLI.getPointerTy()); 292 Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx); 293 294 if (Extend) Result = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Result); 295 } 296 break; 297 } 298 case ISD::TokenFactor: { 299 std::vector<SDOperand> Ops; 300 bool Changed = false; 301 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 302 Ops.push_back(LegalizeOp(Node->getOperand(i))); // Legalize the operands 303 Changed |= Ops[i] != Node->getOperand(i); 304 } 305 if (Changed) 306 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops); 307 break; 308 } 309 310 case ISD::ADJCALLSTACKDOWN: 311 case ISD::ADJCALLSTACKUP: 312 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 313 // There is no need to legalize the size argument (Operand #1) 314 if (Tmp1 != Node->getOperand(0)) 315 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, 316 Node->getOperand(1)); 317 break; 318 case ISD::DYNAMIC_STACKALLOC: 319 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 320 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the size. 321 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the alignment. 322 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 323 Tmp3 != Node->getOperand(2)) 324 Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0), 325 Tmp1, Tmp2, Tmp3); 326 else 327 Result = Op.getValue(0); 328 329 // Since this op produces two values, make sure to remember that we 330 // legalized both of them. 331 AddLegalizedOperand(SDOperand(Node, 0), Result); 332 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 333 return Result.getValue(Op.ResNo); 334 335 case ISD::CALL: 336 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 337 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 338 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 339 std::vector<MVT::ValueType> RetTyVTs; 340 RetTyVTs.reserve(Node->getNumValues()); 341 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 342 RetTyVTs.push_back(Node->getValueType(i)); 343 Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2), 0); 344 } else { 345 Result = Result.getValue(0); 346 } 347 // Since calls produce multiple values, make sure to remember that we 348 // legalized all of them. 349 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 350 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 351 return Result.getValue(Op.ResNo); 352 353 case ISD::BR: 354 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 355 if (Tmp1 != Node->getOperand(0)) 356 Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1)); 357 break; 358 359 case ISD::BRCOND: 360 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 361 // FIXME: booleans might not be legal! 362 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 363 // Basic block destination (Op#2) is always legal. 364 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 365 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 366 Node->getOperand(2)); 367 break; 368 369 case ISD::LOAD: 370 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 371 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 372 if (Tmp1 != Node->getOperand(0) || 373 Tmp2 != Node->getOperand(1)) 374 Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2); 375 else 376 Result = SDOperand(Node, 0); 377 378 // Since loads produce two values, make sure to remember that we legalized 379 // both of them. 380 AddLegalizedOperand(SDOperand(Node, 0), Result); 381 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 382 return Result.getValue(Op.ResNo); 383 384 case ISD::EXTRACT_ELEMENT: 385 // Get both the low and high parts. 386 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 387 if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) 388 Result = Tmp2; // 1 -> Hi 389 else 390 Result = Tmp1; // 0 -> Lo 391 break; 392 393 case ISD::CopyToReg: 394 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 395 396 switch (getTypeAction(Node->getOperand(1).getValueType())) { 397 case Legal: 398 // Legalize the incoming value (must be legal). 399 Tmp2 = LegalizeOp(Node->getOperand(1)); 400 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 401 Result = DAG.getCopyToReg(Tmp1, Tmp2, 402 cast<CopyRegSDNode>(Node)->getReg()); 403 break; 404 case Expand: { 405 SDOperand Lo, Hi; 406 ExpandOp(Node->getOperand(1), Lo, Hi); 407 unsigned Reg = cast<CopyRegSDNode>(Node)->getReg(); 408 Result = DAG.getCopyToReg(Tmp1, Lo, Reg); 409 Result = DAG.getCopyToReg(Result, Hi, Reg+1); 410 assert(isTypeLegal(Result.getValueType()) && 411 "Cannot expand multiple times yet (i64 -> i16)"); 412 break; 413 } 414 case Promote: 415 assert(0 && "Don't know what it means to promote this!"); 416 abort(); 417 } 418 break; 419 420 case ISD::RET: 421 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 422 switch (Node->getNumOperands()) { 423 case 2: // ret val 424 switch (getTypeAction(Node->getOperand(1).getValueType())) { 425 case Legal: 426 Tmp2 = LegalizeOp(Node->getOperand(1)); 427 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 428 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 429 break; 430 case Expand: { 431 SDOperand Lo, Hi; 432 ExpandOp(Node->getOperand(1), Lo, Hi); 433 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi); 434 break; 435 } 436 case Promote: 437 assert(0 && "Can't promote return value!"); 438 } 439 break; 440 case 1: // ret void 441 if (Tmp1 != Node->getOperand(0)) 442 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1); 443 break; 444 default: { // ret <values> 445 std::vector<SDOperand> NewValues; 446 NewValues.push_back(Tmp1); 447 for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) 448 switch (getTypeAction(Node->getOperand(i).getValueType())) { 449 case Legal: 450 NewValues.push_back(LegalizeOp(Node->getOperand(i))); 451 break; 452 case Expand: { 453 SDOperand Lo, Hi; 454 ExpandOp(Node->getOperand(i), Lo, Hi); 455 NewValues.push_back(Lo); 456 NewValues.push_back(Hi); 457 break; 458 } 459 case Promote: 460 assert(0 && "Can't promote return value!"); 461 } 462 Result = DAG.getNode(ISD::RET, MVT::Other, NewValues); 463 break; 464 } 465 } 466 break; 467 case ISD::STORE: 468 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 469 Tmp2 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 470 471 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 472 if (ConstantFPSDNode *CFP = 473 dyn_cast<ConstantFPSDNode>(Node->getOperand(1))) { 474 if (CFP->getValueType(0) == MVT::f32) { 475 union { 476 unsigned I; 477 float F; 478 } V; 479 V.F = CFP->getValue(); 480 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 481 DAG.getConstant(V.I, MVT::i32), Tmp2); 482 } else { 483 assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!"); 484 union { 485 uint64_t I; 486 double F; 487 } V; 488 V.F = CFP->getValue(); 489 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 490 DAG.getConstant(V.I, MVT::i64), Tmp2); 491 } 492 Op = Result; 493 Node = Op.Val; 494 } 495 496 switch (getTypeAction(Node->getOperand(1).getValueType())) { 497 case Legal: { 498 SDOperand Val = LegalizeOp(Node->getOperand(1)); 499 if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) || 500 Tmp2 != Node->getOperand(2)) 501 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2); 502 break; 503 } 504 case Promote: 505 assert(0 && "FIXME: promote for stores not implemented!"); 506 case Expand: 507 SDOperand Lo, Hi; 508 ExpandOp(Node->getOperand(1), Lo, Hi); 509 510 if (!TLI.isLittleEndian()) 511 std::swap(Lo, Hi); 512 513 // FIXME: These two stores are independent of each other! 514 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2); 515 516 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 517 Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2, 518 getIntPtrConstant(IncrementSize)); 519 assert(isTypeLegal(Tmp2.getValueType()) && 520 "Pointers must be legal!"); 521 Result = DAG.getNode(ISD::STORE, MVT::Other, Result, Hi, Tmp2); 522 } 523 break; 524 case ISD::SELECT: { 525 // FIXME: BOOLS MAY REQUIRE PROMOTION! 526 Tmp1 = LegalizeOp(Node->getOperand(0)); // Cond 527 Tmp2 = LegalizeOp(Node->getOperand(1)); // TrueVal 528 SDOperand Tmp3 = LegalizeOp(Node->getOperand(2)); // FalseVal 529 530 if (Tmp1 != Node->getOperand(0) || 531 Tmp2 != Node->getOperand(1) || 532 Tmp3 != Node->getOperand(2)) 533 Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), Tmp1, Tmp2,Tmp3); 534 break; 535 } 536 case ISD::SETCC: 537 switch (getTypeAction(Node->getOperand(0).getValueType())) { 538 case Legal: 539 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 540 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 541 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 542 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 543 Tmp1, Tmp2); 544 break; 545 case Promote: 546 assert(0 && "Can't promote setcc operands yet!"); 547 break; 548 case Expand: 549 SDOperand LHSLo, LHSHi, RHSLo, RHSHi; 550 ExpandOp(Node->getOperand(0), LHSLo, LHSHi); 551 ExpandOp(Node->getOperand(1), RHSLo, RHSHi); 552 switch (cast<SetCCSDNode>(Node)->getCondition()) { 553 case ISD::SETEQ: 554 case ISD::SETNE: 555 Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo); 556 Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi); 557 Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2); 558 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), Tmp1, 559 DAG.getConstant(0, Tmp1.getValueType())); 560 break; 561 default: 562 // FIXME: This generated code sucks. 563 ISD::CondCode LowCC; 564 switch (cast<SetCCSDNode>(Node)->getCondition()) { 565 default: assert(0 && "Unknown integer setcc!"); 566 case ISD::SETLT: 567 case ISD::SETULT: LowCC = ISD::SETULT; break; 568 case ISD::SETGT: 569 case ISD::SETUGT: LowCC = ISD::SETUGT; break; 570 case ISD::SETLE: 571 case ISD::SETULE: LowCC = ISD::SETULE; break; 572 case ISD::SETGE: 573 case ISD::SETUGE: LowCC = ISD::SETUGE; break; 574 } 575 576 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison 577 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands 578 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2; 579 580 // NOTE: on targets without efficient SELECT of bools, we can always use 581 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3) 582 Tmp1 = DAG.getSetCC(LowCC, LHSLo, RHSLo); 583 Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 584 LHSHi, RHSHi); 585 Result = DAG.getSetCC(ISD::SETEQ, LHSHi, RHSHi); 586 Result = DAG.getNode(ISD::SELECT, MVT::i1, Result, Tmp1, Tmp2); 587 break; 588 } 589 } 590 break; 591 592 case ISD::MEMSET: 593 case ISD::MEMCPY: 594 case ISD::MEMMOVE: { 595 Tmp1 = LegalizeOp(Node->getOperand(0)); 596 Tmp2 = LegalizeOp(Node->getOperand(1)); 597 Tmp3 = LegalizeOp(Node->getOperand(2)); 598 SDOperand Tmp4 = LegalizeOp(Node->getOperand(3)); 599 SDOperand Tmp5 = LegalizeOp(Node->getOperand(4)); 600 if (TLI.isOperationSupported(Node->getOpcode(), MVT::Other)) { 601 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 602 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) || 603 Tmp5 != Node->getOperand(4)) { 604 std::vector<SDOperand> Ops; 605 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 606 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 607 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 608 } 609 } else { 610 // Otherwise, the target does not support this operation. Lower the 611 // operation to an explicit libcall as appropriate. 612 MVT::ValueType IntPtr = TLI.getPointerTy(); 613 const Type *IntPtrTy = TLI.getTargetData().getIntPtrType(); 614 std::vector<std::pair<SDOperand, const Type*> > Args; 615 616 const char *FnName = 0; 617 if (Node->getOpcode() == ISD::MEMSET) { 618 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 619 // Extend the ubyte argument to be an int value for the call. 620 Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3); 621 Args.push_back(std::make_pair(Tmp3, Type::IntTy)); 622 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 623 624 FnName = "memset"; 625 } else if (Node->getOpcode() == ISD::MEMCPY || 626 Node->getOpcode() == ISD::MEMMOVE) { 627 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 628 Args.push_back(std::make_pair(Tmp3, IntPtrTy)); 629 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 630 FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy"; 631 } else { 632 assert(0 && "Unknown op!"); 633 } 634 std::pair<SDOperand,SDOperand> CallResult = 635 TLI.LowerCallTo(Tmp1, Type::VoidTy, 636 DAG.getExternalSymbol(FnName, IntPtr), Args, DAG); 637 Result = LegalizeOp(CallResult.second); 638 } 639 break; 640 } 641 case ISD::ADD: 642 case ISD::SUB: 643 case ISD::MUL: 644 case ISD::UDIV: 645 case ISD::SDIV: 646 case ISD::UREM: 647 case ISD::SREM: 648 case ISD::AND: 649 case ISD::OR: 650 case ISD::XOR: 651 case ISD::SHL: 652 case ISD::SRL: 653 case ISD::SRA: 654 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 655 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 656 if (Tmp1 != Node->getOperand(0) || 657 Tmp2 != Node->getOperand(1)) 658 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2); 659 break; 660 case ISD::ZERO_EXTEND: 661 case ISD::SIGN_EXTEND: 662 case ISD::TRUNCATE: 663 case ISD::FP_EXTEND: 664 case ISD::FP_ROUND: 665 case ISD::FP_TO_SINT: 666 case ISD::FP_TO_UINT: 667 case ISD::SINT_TO_FP: 668 case ISD::UINT_TO_FP: 669 670 switch (getTypeAction(Node->getOperand(0).getValueType())) { 671 case Legal: 672 Tmp1 = LegalizeOp(Node->getOperand(0)); 673 if (Tmp1 != Node->getOperand(0)) 674 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 675 break; 676 case Expand: 677 assert(Node->getOpcode() != ISD::SINT_TO_FP && 678 Node->getOpcode() != ISD::UINT_TO_FP && 679 "Cannot lower Xint_to_fp to a call yet!"); 680 681 // In the expand case, we must be dealing with a truncate, because 682 // otherwise the result would be larger than the source. 683 assert(Node->getOpcode() == ISD::TRUNCATE && 684 "Shouldn't need to expand other operators here!"); 685 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 686 687 // Since the result is legal, we should just be able to truncate the low 688 // part of the source. 689 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1); 690 break; 691 692 default: 693 assert(0 && "Do not know how to promote this yet!"); 694 } 695 break; 696 } 697 698 if (!Op.Val->hasOneUse()) 699 AddLegalizedOperand(Op, Result); 700 701 return Result; 702} 703 704 705/// ExpandOp - Expand the specified SDOperand into its two component pieces 706/// Lo&Hi. Note that the Op MUST be an expanded type. As a result of this, the 707/// LegalizeNodes map is filled in for any results that are not expanded, the 708/// ExpandedNodes map is filled in for any results that are expanded, and the 709/// Lo/Hi values are returned. 710void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ 711 MVT::ValueType VT = Op.getValueType(); 712 MVT::ValueType NVT = TransformToType[VT]; 713 SDNode *Node = Op.Val; 714 assert(getTypeAction(VT) == Expand && "Not an expanded type!"); 715 assert(MVT::isInteger(VT) && "Cannot expand FP values!"); 716 assert(MVT::isInteger(NVT) && NVT < VT && 717 "Cannot expand to FP value or to larger int value!"); 718 719 // If there is more than one use of this, see if we already expanded it. 720 // There is no use remembering values that only have a single use, as the map 721 // entries will never be reused. 722 if (!Node->hasOneUse()) { 723 std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I 724 = ExpandedNodes.find(Op); 725 if (I != ExpandedNodes.end()) { 726 Lo = I->second.first; 727 Hi = I->second.second; 728 return; 729 } 730 } 731 732 // Expanding to multiple registers needs to perform an optimization step, and 733 // is not careful to avoid operations the target does not support. Make sure 734 // that all generated operations are legalized in the next iteration. 735 NeedsAnotherIteration = true; 736 const char *LibCallName = 0; 737 738 switch (Node->getOpcode()) { 739 default: 740 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 741 assert(0 && "Do not know how to expand this operator!"); 742 abort(); 743 case ISD::Constant: { 744 uint64_t Cst = cast<ConstantSDNode>(Node)->getValue(); 745 Lo = DAG.getConstant(Cst, NVT); 746 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT); 747 break; 748 } 749 750 case ISD::CopyFromReg: { 751 unsigned Reg = cast<CopyRegSDNode>(Node)->getReg(); 752 // Aggregate register values are always in consequtive pairs. 753 Lo = DAG.getCopyFromReg(Reg, NVT); 754 Hi = DAG.getCopyFromReg(Reg+1, NVT); 755 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!"); 756 break; 757 } 758 759 case ISD::LOAD: { 760 SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 761 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 762 Lo = DAG.getLoad(NVT, Ch, Ptr); 763 764 // Increment the pointer to the other half. 765 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 766 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 767 getIntPtrConstant(IncrementSize)); 768 // FIXME: This load is independent of the first one. 769 Hi = DAG.getLoad(NVT, Lo.getValue(1), Ptr); 770 771 // Remember that we legalized the chain. 772 AddLegalizedOperand(Op.getValue(1), Hi.getValue(1)); 773 if (!TLI.isLittleEndian()) 774 std::swap(Lo, Hi); 775 break; 776 } 777 case ISD::CALL: { 778 SDOperand Chain = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 779 SDOperand Callee = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 780 781 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 782 "Can only expand a call once so far, not i64 -> i16!"); 783 784 std::vector<MVT::ValueType> RetTyVTs; 785 RetTyVTs.reserve(3); 786 RetTyVTs.push_back(NVT); 787 RetTyVTs.push_back(NVT); 788 RetTyVTs.push_back(MVT::Other); 789 SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee); 790 Lo = SDOperand(NC, 0); 791 Hi = SDOperand(NC, 1); 792 793 // Insert the new chain mapping. 794 AddLegalizedOperand(Op.getValue(1), Hi.getValue(2)); 795 break; 796 } 797 case ISD::AND: 798 case ISD::OR: 799 case ISD::XOR: { // Simple logical operators -> two trivial pieces. 800 SDOperand LL, LH, RL, RH; 801 ExpandOp(Node->getOperand(0), LL, LH); 802 ExpandOp(Node->getOperand(1), RL, RH); 803 Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL); 804 Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH); 805 break; 806 } 807 case ISD::SELECT: { 808 SDOperand C, LL, LH, RL, RH; 809 // FIXME: BOOLS MAY REQUIRE PROMOTION! 810 C = LegalizeOp(Node->getOperand(0)); 811 ExpandOp(Node->getOperand(1), LL, LH); 812 ExpandOp(Node->getOperand(2), RL, RH); 813 Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL); 814 Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH); 815 break; 816 } 817 case ISD::SIGN_EXTEND: { 818 // The low part is just a sign extension of the input (which degenerates to 819 // a copy). 820 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0))); 821 822 // The high part is obtained by SRA'ing all but one of the bits of the lo 823 // part. 824 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); 825 Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, MVT::i8)); 826 break; 827 } 828 case ISD::ZERO_EXTEND: 829 // The low part is just a zero extension of the input (which degenerates to 830 // a copy). 831 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0))); 832 833 // The high part is just a zero. 834 Hi = DAG.getConstant(0, NVT); 835 break; 836 837 // These operators cannot be expanded directly, emit them as calls to 838 // library functions. 839 case ISD::FP_TO_SINT: 840 if (Node->getOperand(0).getValueType() == MVT::f32) 841 LibCallName = "__fixsfdi"; 842 else 843 LibCallName = "__fixdfdi"; 844 break; 845 case ISD::FP_TO_UINT: 846 if (Node->getOperand(0).getValueType() == MVT::f32) 847 LibCallName = "__fixunssfdi"; 848 else 849 LibCallName = "__fixunsdfdi"; 850 break; 851 852 case ISD::ADD: LibCallName = "__adddi3"; break; 853 case ISD::SUB: LibCallName = "__subdi3"; break; 854 case ISD::MUL: LibCallName = "__muldi3"; break; 855 case ISD::SDIV: LibCallName = "__divdi3"; break; 856 case ISD::UDIV: LibCallName = "__udivdi3"; break; 857 case ISD::SREM: LibCallName = "__moddi3"; break; 858 case ISD::UREM: LibCallName = "__umoddi3"; break; 859 case ISD::SHL: LibCallName = "__ashldi3"; break; 860 case ISD::SRA: LibCallName = "__ashrdi3"; break; 861 case ISD::SRL: LibCallName = "__lshrdi3"; break; 862 } 863 864 // Int2FP -> __floatdisf/__floatdidf 865 866 // If this is to be expanded into a libcall... do so now. 867 if (LibCallName) { 868 TargetLowering::ArgListTy Args; 869 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) 870 Args.push_back(std::make_pair(Node->getOperand(i), 871 getTypeFor(Node->getOperand(i).getValueType()))); 872 SDOperand Callee = DAG.getExternalSymbol(LibCallName, TLI.getPointerTy()); 873 874 // We don't care about token chains for libcalls. We just use the entry 875 // node as our input and ignore the output chain. This allows us to place 876 // calls wherever we need them to satisfy data dependences. 877 SDOperand Result = TLI.LowerCallTo(DAG.getEntryNode(), 878 getTypeFor(Op.getValueType()), Callee, 879 Args, DAG).first; 880 ExpandOp(Result, Lo, Hi); 881 } 882 883 // Remember in a map if the values will be reused later. 884 if (!Node->hasOneUse()) { 885 bool isNew = ExpandedNodes.insert(std::make_pair(Op, 886 std::make_pair(Lo, Hi))).second; 887 assert(isNew && "Value already expanded?!?"); 888 } 889} 890 891 892// SelectionDAG::Legalize - This is the entry point for the file. 893// 894void SelectionDAG::Legalize(TargetLowering &TLI) { 895 /// run - This is the main entry point to this class. 896 /// 897 SelectionDAGLegalize(TLI, *this).Run(); 898} 899 900