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