LegalizeDAG.cpp revision 18c2f13e0f9d0e5d6227cf6d1881e9ee3d1b6109
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::ImplicitDef: 248 Tmp1 = LegalizeOp(Node->getOperand(0)); 249 if (Tmp1 != Node->getOperand(0)) 250 Result = DAG.getImplicitDef(cast<RegSDNode>(Node)->getReg()); 251 break; 252 case ISD::Constant: 253 // We know we don't need to expand constants here, constants only have one 254 // value and we check that it is fine above. 255 256 // FIXME: Maybe we should handle things like targets that don't support full 257 // 32-bit immediates? 258 break; 259 case ISD::ConstantFP: { 260 // Spill FP immediates to the constant pool if the target cannot directly 261 // codegen them. Targets often have some immediate values that can be 262 // efficiently generated into an FP register without a load. We explicitly 263 // leave these constants as ConstantFP nodes for the target to deal with. 264 265 ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node); 266 267 // Check to see if this FP immediate is already legal. 268 bool isLegal = false; 269 for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(), 270 E = TLI.legal_fpimm_end(); I != E; ++I) 271 if (CFP->isExactlyValue(*I)) { 272 isLegal = true; 273 break; 274 } 275 276 if (!isLegal) { 277 // Otherwise we need to spill the constant to memory. 278 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); 279 280 bool Extend = false; 281 282 // If a FP immediate is precise when represented as a float, we put it 283 // into the constant pool as a float, even if it's is statically typed 284 // as a double. 285 MVT::ValueType VT = CFP->getValueType(0); 286 bool isDouble = VT == MVT::f64; 287 ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy : 288 Type::FloatTy, CFP->getValue()); 289 if (isDouble && CFP->isExactlyValue((float)CFP->getValue())) { 290 LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy)); 291 VT = MVT::f32; 292 Extend = true; 293 } 294 295 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC), 296 TLI.getPointerTy()); 297 Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx); 298 299 if (Extend) Result = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Result); 300 } 301 break; 302 } 303 case ISD::TokenFactor: { 304 std::vector<SDOperand> Ops; 305 bool Changed = false; 306 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 307 Ops.push_back(LegalizeOp(Node->getOperand(i))); // Legalize the operands 308 Changed |= Ops[i] != Node->getOperand(i); 309 } 310 if (Changed) 311 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops); 312 break; 313 } 314 315 case ISD::ADJCALLSTACKDOWN: 316 case ISD::ADJCALLSTACKUP: 317 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 318 // There is no need to legalize the size argument (Operand #1) 319 if (Tmp1 != Node->getOperand(0)) 320 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, 321 Node->getOperand(1)); 322 break; 323 case ISD::DYNAMIC_STACKALLOC: 324 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 325 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the size. 326 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the alignment. 327 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 328 Tmp3 != Node->getOperand(2)) 329 Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0), 330 Tmp1, Tmp2, Tmp3); 331 else 332 Result = Op.getValue(0); 333 334 // Since this op produces two values, make sure to remember that we 335 // legalized both of them. 336 AddLegalizedOperand(SDOperand(Node, 0), Result); 337 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 338 return Result.getValue(Op.ResNo); 339 340 case ISD::CALL: 341 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 342 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 343 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 344 std::vector<MVT::ValueType> RetTyVTs; 345 RetTyVTs.reserve(Node->getNumValues()); 346 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 347 RetTyVTs.push_back(Node->getValueType(i)); 348 Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2), 0); 349 } else { 350 Result = Result.getValue(0); 351 } 352 // Since calls produce multiple values, make sure to remember that we 353 // legalized all of them. 354 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 355 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 356 return Result.getValue(Op.ResNo); 357 358 case ISD::BR: 359 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 360 if (Tmp1 != Node->getOperand(0)) 361 Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1)); 362 break; 363 364 case ISD::BRCOND: 365 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 366 // FIXME: booleans might not be legal! 367 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 368 // Basic block destination (Op#2) is always legal. 369 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 370 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 371 Node->getOperand(2)); 372 break; 373 374 case ISD::LOAD: 375 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 376 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 377 if (Tmp1 != Node->getOperand(0) || 378 Tmp2 != Node->getOperand(1)) 379 Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2); 380 else 381 Result = SDOperand(Node, 0); 382 383 // Since loads produce two values, make sure to remember that we legalized 384 // both of them. 385 AddLegalizedOperand(SDOperand(Node, 0), Result); 386 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 387 return Result.getValue(Op.ResNo); 388 389 case ISD::EXTRACT_ELEMENT: 390 // Get both the low and high parts. 391 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 392 if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) 393 Result = Tmp2; // 1 -> Hi 394 else 395 Result = Tmp1; // 0 -> Lo 396 break; 397 398 case ISD::CopyToReg: 399 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 400 401 switch (getTypeAction(Node->getOperand(1).getValueType())) { 402 case Legal: 403 // Legalize the incoming value (must be legal). 404 Tmp2 = LegalizeOp(Node->getOperand(1)); 405 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 406 Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg()); 407 break; 408 case Expand: { 409 SDOperand Lo, Hi; 410 ExpandOp(Node->getOperand(1), Lo, Hi); 411 unsigned Reg = cast<RegSDNode>(Node)->getReg(); 412 Result = DAG.getCopyToReg(Tmp1, Lo, Reg); 413 Result = DAG.getCopyToReg(Result, Hi, Reg+1); 414 assert(isTypeLegal(Result.getValueType()) && 415 "Cannot expand multiple times yet (i64 -> i16)"); 416 break; 417 } 418 case Promote: 419 assert(0 && "Don't know what it means to promote this!"); 420 abort(); 421 } 422 break; 423 424 case ISD::RET: 425 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 426 switch (Node->getNumOperands()) { 427 case 2: // ret val 428 switch (getTypeAction(Node->getOperand(1).getValueType())) { 429 case Legal: 430 Tmp2 = LegalizeOp(Node->getOperand(1)); 431 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 432 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 433 break; 434 case Expand: { 435 SDOperand Lo, Hi; 436 ExpandOp(Node->getOperand(1), Lo, Hi); 437 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi); 438 break; 439 } 440 case Promote: 441 assert(0 && "Can't promote return value!"); 442 } 443 break; 444 case 1: // ret void 445 if (Tmp1 != Node->getOperand(0)) 446 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1); 447 break; 448 default: { // ret <values> 449 std::vector<SDOperand> NewValues; 450 NewValues.push_back(Tmp1); 451 for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) 452 switch (getTypeAction(Node->getOperand(i).getValueType())) { 453 case Legal: 454 NewValues.push_back(LegalizeOp(Node->getOperand(i))); 455 break; 456 case Expand: { 457 SDOperand Lo, Hi; 458 ExpandOp(Node->getOperand(i), Lo, Hi); 459 NewValues.push_back(Lo); 460 NewValues.push_back(Hi); 461 break; 462 } 463 case Promote: 464 assert(0 && "Can't promote return value!"); 465 } 466 Result = DAG.getNode(ISD::RET, MVT::Other, NewValues); 467 break; 468 } 469 } 470 break; 471 case ISD::STORE: 472 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 473 Tmp2 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 474 475 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 476 if (ConstantFPSDNode *CFP = 477 dyn_cast<ConstantFPSDNode>(Node->getOperand(1))) { 478 if (CFP->getValueType(0) == MVT::f32) { 479 union { 480 unsigned I; 481 float F; 482 } V; 483 V.F = CFP->getValue(); 484 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 485 DAG.getConstant(V.I, MVT::i32), Tmp2); 486 } else { 487 assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!"); 488 union { 489 uint64_t I; 490 double F; 491 } V; 492 V.F = CFP->getValue(); 493 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 494 DAG.getConstant(V.I, MVT::i64), Tmp2); 495 } 496 Op = Result; 497 Node = Op.Val; 498 } 499 500 switch (getTypeAction(Node->getOperand(1).getValueType())) { 501 case Legal: { 502 SDOperand Val = LegalizeOp(Node->getOperand(1)); 503 if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) || 504 Tmp2 != Node->getOperand(2)) 505 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2); 506 break; 507 } 508 case Promote: 509 assert(0 && "FIXME: promote for stores not implemented!"); 510 case Expand: 511 SDOperand Lo, Hi; 512 ExpandOp(Node->getOperand(1), Lo, Hi); 513 514 if (!TLI.isLittleEndian()) 515 std::swap(Lo, Hi); 516 517 // FIXME: These two stores are independent of each other! 518 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2); 519 520 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 521 Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2, 522 getIntPtrConstant(IncrementSize)); 523 assert(isTypeLegal(Tmp2.getValueType()) && 524 "Pointers must be legal!"); 525 Result = DAG.getNode(ISD::STORE, MVT::Other, Result, Hi, Tmp2); 526 } 527 break; 528 case ISD::SELECT: { 529 // FIXME: BOOLS MAY REQUIRE PROMOTION! 530 Tmp1 = LegalizeOp(Node->getOperand(0)); // Cond 531 Tmp2 = LegalizeOp(Node->getOperand(1)); // TrueVal 532 SDOperand Tmp3 = LegalizeOp(Node->getOperand(2)); // FalseVal 533 534 if (Tmp1 != Node->getOperand(0) || 535 Tmp2 != Node->getOperand(1) || 536 Tmp3 != Node->getOperand(2)) 537 Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), Tmp1, Tmp2,Tmp3); 538 break; 539 } 540 case ISD::SETCC: 541 switch (getTypeAction(Node->getOperand(0).getValueType())) { 542 case Legal: 543 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 544 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 545 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 546 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 547 Tmp1, Tmp2); 548 break; 549 case Promote: 550 assert(0 && "Can't promote setcc operands yet!"); 551 break; 552 case Expand: 553 SDOperand LHSLo, LHSHi, RHSLo, RHSHi; 554 ExpandOp(Node->getOperand(0), LHSLo, LHSHi); 555 ExpandOp(Node->getOperand(1), RHSLo, RHSHi); 556 switch (cast<SetCCSDNode>(Node)->getCondition()) { 557 case ISD::SETEQ: 558 case ISD::SETNE: 559 Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo); 560 Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi); 561 Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2); 562 Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), Tmp1, 563 DAG.getConstant(0, Tmp1.getValueType())); 564 break; 565 default: 566 // FIXME: This generated code sucks. 567 ISD::CondCode LowCC; 568 switch (cast<SetCCSDNode>(Node)->getCondition()) { 569 default: assert(0 && "Unknown integer setcc!"); 570 case ISD::SETLT: 571 case ISD::SETULT: LowCC = ISD::SETULT; break; 572 case ISD::SETGT: 573 case ISD::SETUGT: LowCC = ISD::SETUGT; break; 574 case ISD::SETLE: 575 case ISD::SETULE: LowCC = ISD::SETULE; break; 576 case ISD::SETGE: 577 case ISD::SETUGE: LowCC = ISD::SETUGE; break; 578 } 579 580 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison 581 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands 582 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2; 583 584 // NOTE: on targets without efficient SELECT of bools, we can always use 585 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3) 586 Tmp1 = DAG.getSetCC(LowCC, LHSLo, RHSLo); 587 Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 588 LHSHi, RHSHi); 589 Result = DAG.getSetCC(ISD::SETEQ, LHSHi, RHSHi); 590 Result = DAG.getNode(ISD::SELECT, MVT::i1, Result, Tmp1, Tmp2); 591 break; 592 } 593 } 594 break; 595 596 case ISD::MEMSET: 597 case ISD::MEMCPY: 598 case ISD::MEMMOVE: { 599 Tmp1 = LegalizeOp(Node->getOperand(0)); 600 Tmp2 = LegalizeOp(Node->getOperand(1)); 601 Tmp3 = LegalizeOp(Node->getOperand(2)); 602 SDOperand Tmp4 = LegalizeOp(Node->getOperand(3)); 603 SDOperand Tmp5 = LegalizeOp(Node->getOperand(4)); 604 if (TLI.isOperationSupported(Node->getOpcode(), MVT::Other)) { 605 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 606 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) || 607 Tmp5 != Node->getOperand(4)) { 608 std::vector<SDOperand> Ops; 609 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 610 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 611 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 612 } 613 } else { 614 // Otherwise, the target does not support this operation. Lower the 615 // operation to an explicit libcall as appropriate. 616 MVT::ValueType IntPtr = TLI.getPointerTy(); 617 const Type *IntPtrTy = TLI.getTargetData().getIntPtrType(); 618 std::vector<std::pair<SDOperand, const Type*> > Args; 619 620 const char *FnName = 0; 621 if (Node->getOpcode() == ISD::MEMSET) { 622 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 623 // Extend the ubyte argument to be an int value for the call. 624 Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3); 625 Args.push_back(std::make_pair(Tmp3, Type::IntTy)); 626 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 627 628 FnName = "memset"; 629 } else if (Node->getOpcode() == ISD::MEMCPY || 630 Node->getOpcode() == ISD::MEMMOVE) { 631 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 632 Args.push_back(std::make_pair(Tmp3, IntPtrTy)); 633 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 634 FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy"; 635 } else { 636 assert(0 && "Unknown op!"); 637 } 638 std::pair<SDOperand,SDOperand> CallResult = 639 TLI.LowerCallTo(Tmp1, Type::VoidTy, 640 DAG.getExternalSymbol(FnName, IntPtr), Args, DAG); 641 Result = LegalizeOp(CallResult.second); 642 } 643 break; 644 } 645 case ISD::ADD: 646 case ISD::SUB: 647 case ISD::MUL: 648 case ISD::UDIV: 649 case ISD::SDIV: 650 case ISD::UREM: 651 case ISD::SREM: 652 case ISD::AND: 653 case ISD::OR: 654 case ISD::XOR: 655 case ISD::SHL: 656 case ISD::SRL: 657 case ISD::SRA: 658 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 659 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 660 if (Tmp1 != Node->getOperand(0) || 661 Tmp2 != Node->getOperand(1)) 662 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2); 663 break; 664 case ISD::ZERO_EXTEND: 665 case ISD::SIGN_EXTEND: 666 case ISD::TRUNCATE: 667 case ISD::FP_EXTEND: 668 case ISD::FP_ROUND: 669 case ISD::FP_TO_SINT: 670 case ISD::FP_TO_UINT: 671 case ISD::SINT_TO_FP: 672 case ISD::UINT_TO_FP: 673 674 switch (getTypeAction(Node->getOperand(0).getValueType())) { 675 case Legal: 676 Tmp1 = LegalizeOp(Node->getOperand(0)); 677 if (Tmp1 != Node->getOperand(0)) 678 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 679 break; 680 case Expand: 681 assert(Node->getOpcode() != ISD::SINT_TO_FP && 682 Node->getOpcode() != ISD::UINT_TO_FP && 683 "Cannot lower Xint_to_fp to a call yet!"); 684 685 // In the expand case, we must be dealing with a truncate, because 686 // otherwise the result would be larger than the source. 687 assert(Node->getOpcode() == ISD::TRUNCATE && 688 "Shouldn't need to expand other operators here!"); 689 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 690 691 // Since the result is legal, we should just be able to truncate the low 692 // part of the source. 693 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1); 694 break; 695 696 default: 697 assert(0 && "Do not know how to promote this yet!"); 698 } 699 break; 700 } 701 702 if (!Op.Val->hasOneUse()) 703 AddLegalizedOperand(Op, Result); 704 705 return Result; 706} 707 708 709/// ExpandOp - Expand the specified SDOperand into its two component pieces 710/// Lo&Hi. Note that the Op MUST be an expanded type. As a result of this, the 711/// LegalizeNodes map is filled in for any results that are not expanded, the 712/// ExpandedNodes map is filled in for any results that are expanded, and the 713/// Lo/Hi values are returned. 714void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ 715 MVT::ValueType VT = Op.getValueType(); 716 MVT::ValueType NVT = TransformToType[VT]; 717 SDNode *Node = Op.Val; 718 assert(getTypeAction(VT) == Expand && "Not an expanded type!"); 719 assert(MVT::isInteger(VT) && "Cannot expand FP values!"); 720 assert(MVT::isInteger(NVT) && NVT < VT && 721 "Cannot expand to FP value or to larger int value!"); 722 723 // If there is more than one use of this, see if we already expanded it. 724 // There is no use remembering values that only have a single use, as the map 725 // entries will never be reused. 726 if (!Node->hasOneUse()) { 727 std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I 728 = ExpandedNodes.find(Op); 729 if (I != ExpandedNodes.end()) { 730 Lo = I->second.first; 731 Hi = I->second.second; 732 return; 733 } 734 } 735 736 // Expanding to multiple registers needs to perform an optimization step, and 737 // is not careful to avoid operations the target does not support. Make sure 738 // that all generated operations are legalized in the next iteration. 739 NeedsAnotherIteration = true; 740 const char *LibCallName = 0; 741 742 switch (Node->getOpcode()) { 743 default: 744 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 745 assert(0 && "Do not know how to expand this operator!"); 746 abort(); 747 case ISD::Constant: { 748 uint64_t Cst = cast<ConstantSDNode>(Node)->getValue(); 749 Lo = DAG.getConstant(Cst, NVT); 750 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT); 751 break; 752 } 753 754 case ISD::CopyFromReg: { 755 unsigned Reg = cast<RegSDNode>(Node)->getReg(); 756 // Aggregate register values are always in consequtive pairs. 757 Lo = DAG.getCopyFromReg(Reg, NVT); 758 Hi = DAG.getCopyFromReg(Reg+1, NVT); 759 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!"); 760 break; 761 } 762 763 case ISD::LOAD: { 764 SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 765 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 766 Lo = DAG.getLoad(NVT, Ch, Ptr); 767 768 // Increment the pointer to the other half. 769 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 770 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 771 getIntPtrConstant(IncrementSize)); 772 // FIXME: This load is independent of the first one. 773 Hi = DAG.getLoad(NVT, Lo.getValue(1), Ptr); 774 775 // Remember that we legalized the chain. 776 AddLegalizedOperand(Op.getValue(1), Hi.getValue(1)); 777 if (!TLI.isLittleEndian()) 778 std::swap(Lo, Hi); 779 break; 780 } 781 case ISD::CALL: { 782 SDOperand Chain = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 783 SDOperand Callee = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 784 785 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 786 "Can only expand a call once so far, not i64 -> i16!"); 787 788 std::vector<MVT::ValueType> RetTyVTs; 789 RetTyVTs.reserve(3); 790 RetTyVTs.push_back(NVT); 791 RetTyVTs.push_back(NVT); 792 RetTyVTs.push_back(MVT::Other); 793 SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee); 794 Lo = SDOperand(NC, 0); 795 Hi = SDOperand(NC, 1); 796 797 // Insert the new chain mapping. 798 AddLegalizedOperand(Op.getValue(1), Hi.getValue(2)); 799 break; 800 } 801 case ISD::AND: 802 case ISD::OR: 803 case ISD::XOR: { // Simple logical operators -> two trivial pieces. 804 SDOperand LL, LH, RL, RH; 805 ExpandOp(Node->getOperand(0), LL, LH); 806 ExpandOp(Node->getOperand(1), RL, RH); 807 Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL); 808 Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH); 809 break; 810 } 811 case ISD::SELECT: { 812 SDOperand C, LL, LH, RL, RH; 813 // FIXME: BOOLS MAY REQUIRE PROMOTION! 814 C = LegalizeOp(Node->getOperand(0)); 815 ExpandOp(Node->getOperand(1), LL, LH); 816 ExpandOp(Node->getOperand(2), RL, RH); 817 Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL); 818 Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH); 819 break; 820 } 821 case ISD::SIGN_EXTEND: { 822 // The low part is just a sign extension of the input (which degenerates to 823 // a copy). 824 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0))); 825 826 // The high part is obtained by SRA'ing all but one of the bits of the lo 827 // part. 828 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); 829 Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, MVT::i8)); 830 break; 831 } 832 case ISD::ZERO_EXTEND: 833 // The low part is just a zero extension of the input (which degenerates to 834 // a copy). 835 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0))); 836 837 // The high part is just a zero. 838 Hi = DAG.getConstant(0, NVT); 839 break; 840 841 // These operators cannot be expanded directly, emit them as calls to 842 // library functions. 843 case ISD::FP_TO_SINT: 844 if (Node->getOperand(0).getValueType() == MVT::f32) 845 LibCallName = "__fixsfdi"; 846 else 847 LibCallName = "__fixdfdi"; 848 break; 849 case ISD::FP_TO_UINT: 850 if (Node->getOperand(0).getValueType() == MVT::f32) 851 LibCallName = "__fixunssfdi"; 852 else 853 LibCallName = "__fixunsdfdi"; 854 break; 855 856 case ISD::ADD: LibCallName = "__adddi3"; break; 857 case ISD::SUB: LibCallName = "__subdi3"; break; 858 case ISD::MUL: LibCallName = "__muldi3"; break; 859 case ISD::SDIV: LibCallName = "__divdi3"; break; 860 case ISD::UDIV: LibCallName = "__udivdi3"; break; 861 case ISD::SREM: LibCallName = "__moddi3"; break; 862 case ISD::UREM: LibCallName = "__umoddi3"; break; 863 case ISD::SHL: LibCallName = "__ashldi3"; break; 864 case ISD::SRA: LibCallName = "__ashrdi3"; break; 865 case ISD::SRL: LibCallName = "__lshrdi3"; break; 866 } 867 868 // Int2FP -> __floatdisf/__floatdidf 869 870 // If this is to be expanded into a libcall... do so now. 871 if (LibCallName) { 872 TargetLowering::ArgListTy Args; 873 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) 874 Args.push_back(std::make_pair(Node->getOperand(i), 875 getTypeFor(Node->getOperand(i).getValueType()))); 876 SDOperand Callee = DAG.getExternalSymbol(LibCallName, TLI.getPointerTy()); 877 878 // We don't care about token chains for libcalls. We just use the entry 879 // node as our input and ignore the output chain. This allows us to place 880 // calls wherever we need them to satisfy data dependences. 881 SDOperand Result = TLI.LowerCallTo(DAG.getEntryNode(), 882 getTypeFor(Op.getValueType()), Callee, 883 Args, DAG).first; 884 ExpandOp(Result, Lo, Hi); 885 } 886 887 // Remember in a map if the values will be reused later. 888 if (!Node->hasOneUse()) { 889 bool isNew = ExpandedNodes.insert(std::make_pair(Op, 890 std::make_pair(Lo, Hi))).second; 891 assert(isNew && "Value already expanded?!?"); 892 } 893} 894 895 896// SelectionDAG::Legalize - This is the entry point for the file. 897// 898void SelectionDAG::Legalize(TargetLowering &TLI) { 899 /// run - This is the main entry point to this class. 900 /// 901 SelectionDAGLegalize(TLI, *this).Run(); 902} 903 904