X86ISelDAGToDAG.cpp revision 8d13f8f1043d8b47940ecab7bac838ff1e8166f8
1//===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines a DAG pattern matching instruction selector for X86, 11// converting from a legalized dag to a X86 dag. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "x86-isel" 16#include "X86.h" 17#include "X86InstrBuilder.h" 18#include "X86ISelLowering.h" 19#include "X86MachineFunctionInfo.h" 20#include "X86RegisterInfo.h" 21#include "X86Subtarget.h" 22#include "X86TargetMachine.h" 23#include "llvm/GlobalValue.h" 24#include "llvm/Instructions.h" 25#include "llvm/Intrinsics.h" 26#include "llvm/Support/CFG.h" 27#include "llvm/Type.h" 28#include "llvm/CodeGen/MachineConstantPool.h" 29#include "llvm/CodeGen/MachineFunction.h" 30#include "llvm/CodeGen/MachineFrameInfo.h" 31#include "llvm/CodeGen/MachineInstrBuilder.h" 32#include "llvm/CodeGen/MachineRegisterInfo.h" 33#include "llvm/CodeGen/SelectionDAGISel.h" 34#include "llvm/Target/TargetMachine.h" 35#include "llvm/Target/TargetOptions.h" 36#include "llvm/Support/Compiler.h" 37#include "llvm/Support/Debug.h" 38#include "llvm/Support/MathExtras.h" 39#include "llvm/Support/Streams.h" 40#include "llvm/ADT/SmallPtrSet.h" 41#include "llvm/ADT/Statistic.h" 42using namespace llvm; 43 44STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor"); 45 46//===----------------------------------------------------------------------===// 47// Pattern Matcher Implementation 48//===----------------------------------------------------------------------===// 49 50namespace { 51 /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses 52 /// SDValue's instead of register numbers for the leaves of the matched 53 /// tree. 54 struct X86ISelAddressMode { 55 enum { 56 RegBase, 57 FrameIndexBase 58 } BaseType; 59 60 struct { // This is really a union, discriminated by BaseType! 61 SDValue Reg; 62 int FrameIndex; 63 } Base; 64 65 bool isRIPRel; // RIP as base? 66 unsigned Scale; 67 SDValue IndexReg; 68 int32_t Disp; 69 GlobalValue *GV; 70 Constant *CP; 71 const char *ES; 72 int JT; 73 unsigned Align; // CP alignment. 74 75 X86ISelAddressMode() 76 : BaseType(RegBase), isRIPRel(false), Scale(1), IndexReg(), Disp(0), 77 GV(0), CP(0), ES(0), JT(-1), Align(0) { 78 } 79 80 bool hasSymbolicDisplacement() const { 81 return GV != 0 || CP != 0 || ES != 0 || JT != -1; 82 } 83 84 void dump() { 85 cerr << "X86ISelAddressMode " << this << "\n"; 86 cerr << "Base.Reg "; 87 if (Base.Reg.getNode() != 0) Base.Reg.getNode()->dump(); 88 else cerr << "nul"; 89 cerr << " Base.FrameIndex " << Base.FrameIndex << "\n"; 90 cerr << "isRIPRel " << isRIPRel << " Scale" << Scale << "\n"; 91 cerr << "IndexReg "; 92 if (IndexReg.getNode() != 0) IndexReg.getNode()->dump(); 93 else cerr << "nul"; 94 cerr << " Disp " << Disp << "\n"; 95 cerr << "GV "; if (GV) GV->dump(); 96 else cerr << "nul"; 97 cerr << " CP "; if (CP) CP->dump(); 98 else cerr << "nul"; 99 cerr << "\n"; 100 cerr << "ES "; if (ES) cerr << ES; else cerr << "nul"; 101 cerr << " JT" << JT << " Align" << Align << "\n"; 102 } 103 }; 104} 105 106namespace { 107 //===--------------------------------------------------------------------===// 108 /// ISel - X86 specific code to select X86 machine instructions for 109 /// SelectionDAG operations. 110 /// 111 class VISIBILITY_HIDDEN X86DAGToDAGISel : public SelectionDAGISel { 112 /// TM - Keep a reference to X86TargetMachine. 113 /// 114 X86TargetMachine &TM; 115 116 /// X86Lowering - This object fully describes how to lower LLVM code to an 117 /// X86-specific SelectionDAG. 118 X86TargetLowering &X86Lowering; 119 120 /// Subtarget - Keep a pointer to the X86Subtarget around so that we can 121 /// make the right decision when generating code for different targets. 122 const X86Subtarget *Subtarget; 123 124 /// CurBB - Current BB being isel'd. 125 /// 126 MachineBasicBlock *CurBB; 127 128 /// OptForSize - If true, selector should try to optimize for code size 129 /// instead of performance. 130 bool OptForSize; 131 132 public: 133 X86DAGToDAGISel(X86TargetMachine &tm, bool fast) 134 : SelectionDAGISel(tm, fast), 135 TM(tm), X86Lowering(*TM.getTargetLowering()), 136 Subtarget(&TM.getSubtarget<X86Subtarget>()), 137 OptForSize(false) {} 138 139 virtual const char *getPassName() const { 140 return "X86 DAG->DAG Instruction Selection"; 141 } 142 143 /// InstructionSelect - This callback is invoked by 144 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen. 145 virtual void InstructionSelect(); 146 147 virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF); 148 149 virtual 150 bool IsLegalAndProfitableToFold(SDNode *N, SDNode *U, SDNode *Root) const; 151 152// Include the pieces autogenerated from the target description. 153#include "X86GenDAGISel.inc" 154 155 private: 156 SDNode *Select(SDValue N); 157 SDNode *SelectAtomic64(SDNode *Node, unsigned Opc); 158 159 bool MatchAddress(SDValue N, X86ISelAddressMode &AM, 160 bool isRoot = true, unsigned Depth = 0); 161 bool MatchAddressBase(SDValue N, X86ISelAddressMode &AM, 162 bool isRoot, unsigned Depth); 163 bool SelectAddr(SDValue Op, SDValue N, SDValue &Base, 164 SDValue &Scale, SDValue &Index, SDValue &Disp); 165 bool SelectLEAAddr(SDValue Op, SDValue N, SDValue &Base, 166 SDValue &Scale, SDValue &Index, SDValue &Disp); 167 bool SelectScalarSSELoad(SDValue Op, SDValue Pred, 168 SDValue N, SDValue &Base, SDValue &Scale, 169 SDValue &Index, SDValue &Disp, 170 SDValue &InChain, SDValue &OutChain); 171 bool TryFoldLoad(SDValue P, SDValue N, 172 SDValue &Base, SDValue &Scale, 173 SDValue &Index, SDValue &Disp); 174 void PreprocessForRMW(); 175 void PreprocessForFPConvert(); 176 177 /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for 178 /// inline asm expressions. 179 virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op, 180 char ConstraintCode, 181 std::vector<SDValue> &OutOps); 182 183 void EmitSpecialCodeForMain(MachineBasicBlock *BB, MachineFrameInfo *MFI); 184 185 inline void getAddressOperands(X86ISelAddressMode &AM, SDValue &Base, 186 SDValue &Scale, SDValue &Index, 187 SDValue &Disp) { 188 Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ? 189 CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, TLI.getPointerTy()) : 190 AM.Base.Reg; 191 Scale = getI8Imm(AM.Scale); 192 Index = AM.IndexReg; 193 // These are 32-bit even in 64-bit mode since RIP relative offset 194 // is 32-bit. 195 if (AM.GV) 196 Disp = CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp); 197 else if (AM.CP) 198 Disp = CurDAG->getTargetConstantPool(AM.CP, MVT::i32, 199 AM.Align, AM.Disp); 200 else if (AM.ES) 201 Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i32); 202 else if (AM.JT != -1) 203 Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i32); 204 else 205 Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i32); 206 } 207 208 /// getI8Imm - Return a target constant with the specified value, of type 209 /// i8. 210 inline SDValue getI8Imm(unsigned Imm) { 211 return CurDAG->getTargetConstant(Imm, MVT::i8); 212 } 213 214 /// getI16Imm - Return a target constant with the specified value, of type 215 /// i16. 216 inline SDValue getI16Imm(unsigned Imm) { 217 return CurDAG->getTargetConstant(Imm, MVT::i16); 218 } 219 220 /// getI32Imm - Return a target constant with the specified value, of type 221 /// i32. 222 inline SDValue getI32Imm(unsigned Imm) { 223 return CurDAG->getTargetConstant(Imm, MVT::i32); 224 } 225 226 /// getGlobalBaseReg - Return an SDNode that returns the value of 227 /// the global base register. Output instructions required to 228 /// initialize the global base register, if necessary. 229 /// 230 SDNode *getGlobalBaseReg(); 231 232 /// getTruncateTo8Bit - return an SDNode that implements a subreg based 233 /// truncate of the specified operand to i8. This can be done with tablegen, 234 /// except that this code uses MVT::Flag in a tricky way that happens to 235 /// improve scheduling in some cases. 236 SDNode *getTruncateTo8Bit(SDValue N0); 237 238#ifndef NDEBUG 239 unsigned Indent; 240#endif 241 }; 242} 243 244/// findFlagUse - Return use of MVT::Flag value produced by the specified 245/// SDNode. 246/// 247static SDNode *findFlagUse(SDNode *N) { 248 unsigned FlagResNo = N->getNumValues()-1; 249 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 250 SDUse &Use = I.getUse(); 251 if (Use.getResNo() == FlagResNo) 252 return Use.getUser(); 253 } 254 return NULL; 255} 256 257/// findNonImmUse - Return true if "Use" is a non-immediate use of "Def". 258/// This function recursively traverses up the operand chain, ignoring 259/// certain nodes. 260static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse, 261 SDNode *Root, 262 SmallPtrSet<SDNode*, 16> &Visited) { 263 if (Use->getNodeId() < Def->getNodeId() || 264 !Visited.insert(Use)) 265 return false; 266 267 for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) { 268 SDNode *N = Use->getOperand(i).getNode(); 269 if (N == Def) { 270 if (Use == ImmedUse || Use == Root) 271 continue; // We are not looking for immediate use. 272 assert(N != Root); 273 return true; 274 } 275 276 // Traverse up the operand chain. 277 if (findNonImmUse(N, Def, ImmedUse, Root, Visited)) 278 return true; 279 } 280 return false; 281} 282 283/// isNonImmUse - Start searching from Root up the DAG to check is Def can 284/// be reached. Return true if that's the case. However, ignore direct uses 285/// by ImmedUse (which would be U in the example illustrated in 286/// IsLegalAndProfitableToFold) and by Root (which can happen in the store 287/// case). 288/// FIXME: to be really generic, we should allow direct use by any node 289/// that is being folded. But realisticly since we only fold loads which 290/// have one non-chain use, we only need to watch out for load/op/store 291/// and load/op/cmp case where the root (store / cmp) may reach the load via 292/// its chain operand. 293static inline bool isNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse) { 294 SmallPtrSet<SDNode*, 16> Visited; 295 return findNonImmUse(Root, Def, ImmedUse, Root, Visited); 296} 297 298 299bool X86DAGToDAGISel::IsLegalAndProfitableToFold(SDNode *N, SDNode *U, 300 SDNode *Root) const { 301 if (Fast) return false; 302 303 if (U == Root) 304 switch (U->getOpcode()) { 305 default: break; 306 case ISD::ADD: 307 case ISD::ADDC: 308 case ISD::ADDE: 309 case ISD::AND: 310 case ISD::OR: 311 case ISD::XOR: { 312 // If the other operand is a 8-bit immediate we should fold the immediate 313 // instead. This reduces code size. 314 // e.g. 315 // movl 4(%esp), %eax 316 // addl $4, %eax 317 // vs. 318 // movl $4, %eax 319 // addl 4(%esp), %eax 320 // The former is 2 bytes shorter. In case where the increment is 1, then 321 // the saving can be 4 bytes (by using incl %eax). 322 ConstantSDNode *Imm = dyn_cast<ConstantSDNode>(U->getOperand(1)); 323 if (Imm) { 324 if (U->getValueType(0) == MVT::i64) { 325 if ((int32_t)Imm->getZExtValue() == (int64_t)Imm->getZExtValue()) 326 return false; 327 } else { 328 if ((int8_t)Imm->getZExtValue() == (int64_t)Imm->getZExtValue()) 329 return false; 330 } 331 } 332 } 333 } 334 335 // If Root use can somehow reach N through a path that that doesn't contain 336 // U then folding N would create a cycle. e.g. In the following 337 // diagram, Root can reach N through X. If N is folded into into Root, then 338 // X is both a predecessor and a successor of U. 339 // 340 // [N*] // 341 // ^ ^ // 342 // / \ // 343 // [U*] [X]? // 344 // ^ ^ // 345 // \ / // 346 // \ / // 347 // [Root*] // 348 // 349 // * indicates nodes to be folded together. 350 // 351 // If Root produces a flag, then it gets (even more) interesting. Since it 352 // will be "glued" together with its flag use in the scheduler, we need to 353 // check if it might reach N. 354 // 355 // [N*] // 356 // ^ ^ // 357 // / \ // 358 // [U*] [X]? // 359 // ^ ^ // 360 // \ \ // 361 // \ | // 362 // [Root*] | // 363 // ^ | // 364 // f | // 365 // | / // 366 // [Y] / // 367 // ^ / // 368 // f / // 369 // | / // 370 // [FU] // 371 // 372 // If FU (flag use) indirectly reaches N (the load), and Root folds N 373 // (call it Fold), then X is a predecessor of FU and a successor of 374 // Fold. But since Fold and FU are flagged together, this will create 375 // a cycle in the scheduling graph. 376 377 MVT VT = Root->getValueType(Root->getNumValues()-1); 378 while (VT == MVT::Flag) { 379 SDNode *FU = findFlagUse(Root); 380 if (FU == NULL) 381 break; 382 Root = FU; 383 VT = Root->getValueType(Root->getNumValues()-1); 384 } 385 386 return !isNonImmUse(Root, N, U); 387} 388 389/// MoveBelowTokenFactor - Replace TokenFactor operand with load's chain operand 390/// and move load below the TokenFactor. Replace store's chain operand with 391/// load's chain result. 392static void MoveBelowTokenFactor(SelectionDAG *CurDAG, SDValue Load, 393 SDValue Store, SDValue TF) { 394 SmallVector<SDValue, 4> Ops; 395 for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i) 396 if (Load.getNode() == TF.getOperand(i).getNode()) 397 Ops.push_back(Load.getOperand(0)); 398 else 399 Ops.push_back(TF.getOperand(i)); 400 CurDAG->UpdateNodeOperands(TF, &Ops[0], Ops.size()); 401 CurDAG->UpdateNodeOperands(Load, TF, Load.getOperand(1), Load.getOperand(2)); 402 CurDAG->UpdateNodeOperands(Store, Load.getValue(1), Store.getOperand(1), 403 Store.getOperand(2), Store.getOperand(3)); 404} 405 406/// isRMWLoad - Return true if N is a load that's part of RMW sub-DAG. 407/// 408static bool isRMWLoad(SDValue N, SDValue Chain, SDValue Address, 409 SDValue &Load) { 410 if (N.getOpcode() == ISD::BIT_CONVERT) 411 N = N.getOperand(0); 412 413 LoadSDNode *LD = dyn_cast<LoadSDNode>(N); 414 if (!LD || LD->isVolatile()) 415 return false; 416 if (LD->getAddressingMode() != ISD::UNINDEXED) 417 return false; 418 419 ISD::LoadExtType ExtType = LD->getExtensionType(); 420 if (ExtType != ISD::NON_EXTLOAD && ExtType != ISD::EXTLOAD) 421 return false; 422 423 if (N.hasOneUse() && 424 N.getOperand(1) == Address && 425 N.getNode()->isOperandOf(Chain.getNode())) { 426 Load = N; 427 return true; 428 } 429 return false; 430} 431 432/// MoveBelowCallSeqStart - Replace CALLSEQ_START operand with load's chain 433/// operand and move load below the call's chain operand. 434static void MoveBelowCallSeqStart(SelectionDAG *CurDAG, SDValue Load, 435 SDValue Call, SDValue CallSeqStart) { 436 SmallVector<SDValue, 8> Ops; 437 SDValue Chain = CallSeqStart.getOperand(0); 438 if (Chain.getNode() == Load.getNode()) 439 Ops.push_back(Load.getOperand(0)); 440 else { 441 assert(Chain.getOpcode() == ISD::TokenFactor && 442 "Unexpected CallSeqStart chain operand"); 443 for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i) 444 if (Chain.getOperand(i).getNode() == Load.getNode()) 445 Ops.push_back(Load.getOperand(0)); 446 else 447 Ops.push_back(Chain.getOperand(i)); 448 SDValue NewChain = 449 CurDAG->getNode(ISD::TokenFactor, Load.getDebugLoc(), 450 MVT::Other, &Ops[0], Ops.size()); 451 Ops.clear(); 452 Ops.push_back(NewChain); 453 } 454 for (unsigned i = 1, e = CallSeqStart.getNumOperands(); i != e; ++i) 455 Ops.push_back(CallSeqStart.getOperand(i)); 456 CurDAG->UpdateNodeOperands(CallSeqStart, &Ops[0], Ops.size()); 457 CurDAG->UpdateNodeOperands(Load, Call.getOperand(0), 458 Load.getOperand(1), Load.getOperand(2)); 459 Ops.clear(); 460 Ops.push_back(SDValue(Load.getNode(), 1)); 461 for (unsigned i = 1, e = Call.getNode()->getNumOperands(); i != e; ++i) 462 Ops.push_back(Call.getOperand(i)); 463 CurDAG->UpdateNodeOperands(Call, &Ops[0], Ops.size()); 464} 465 466/// isCalleeLoad - Return true if call address is a load and it can be 467/// moved below CALLSEQ_START and the chains leading up to the call. 468/// Return the CALLSEQ_START by reference as a second output. 469static bool isCalleeLoad(SDValue Callee, SDValue &Chain) { 470 if (Callee.getNode() == Chain.getNode() || !Callee.hasOneUse()) 471 return false; 472 LoadSDNode *LD = dyn_cast<LoadSDNode>(Callee.getNode()); 473 if (!LD || 474 LD->isVolatile() || 475 LD->getAddressingMode() != ISD::UNINDEXED || 476 LD->getExtensionType() != ISD::NON_EXTLOAD) 477 return false; 478 479 // Now let's find the callseq_start. 480 while (Chain.getOpcode() != ISD::CALLSEQ_START) { 481 if (!Chain.hasOneUse()) 482 return false; 483 Chain = Chain.getOperand(0); 484 } 485 486 if (Chain.getOperand(0).getNode() == Callee.getNode()) 487 return true; 488 if (Chain.getOperand(0).getOpcode() == ISD::TokenFactor && 489 Callee.getValue(1).isOperandOf(Chain.getOperand(0).getNode())) 490 return true; 491 return false; 492} 493 494 495/// PreprocessForRMW - Preprocess the DAG to make instruction selection better. 496/// This is only run if not in -fast mode (aka -O0). 497/// This allows the instruction selector to pick more read-modify-write 498/// instructions. This is a common case: 499/// 500/// [Load chain] 501/// ^ 502/// | 503/// [Load] 504/// ^ ^ 505/// | | 506/// / \- 507/// / | 508/// [TokenFactor] [Op] 509/// ^ ^ 510/// | | 511/// \ / 512/// \ / 513/// [Store] 514/// 515/// The fact the store's chain operand != load's chain will prevent the 516/// (store (op (load))) instruction from being selected. We can transform it to: 517/// 518/// [Load chain] 519/// ^ 520/// | 521/// [TokenFactor] 522/// ^ 523/// | 524/// [Load] 525/// ^ ^ 526/// | | 527/// | \- 528/// | | 529/// | [Op] 530/// | ^ 531/// | | 532/// \ / 533/// \ / 534/// [Store] 535void X86DAGToDAGISel::PreprocessForRMW() { 536 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(), 537 E = CurDAG->allnodes_end(); I != E; ++I) { 538 if (I->getOpcode() == X86ISD::CALL) { 539 /// Also try moving call address load from outside callseq_start to just 540 /// before the call to allow it to be folded. 541 /// 542 /// [Load chain] 543 /// ^ 544 /// | 545 /// [Load] 546 /// ^ ^ 547 /// | | 548 /// / \-- 549 /// / | 550 ///[CALLSEQ_START] | 551 /// ^ | 552 /// | | 553 /// [LOAD/C2Reg] | 554 /// | | 555 /// \ / 556 /// \ / 557 /// [CALL] 558 SDValue Chain = I->getOperand(0); 559 SDValue Load = I->getOperand(1); 560 if (!isCalleeLoad(Load, Chain)) 561 continue; 562 MoveBelowCallSeqStart(CurDAG, Load, SDValue(I, 0), Chain); 563 ++NumLoadMoved; 564 continue; 565 } 566 567 if (!ISD::isNON_TRUNCStore(I)) 568 continue; 569 SDValue Chain = I->getOperand(0); 570 571 if (Chain.getNode()->getOpcode() != ISD::TokenFactor) 572 continue; 573 574 SDValue N1 = I->getOperand(1); 575 SDValue N2 = I->getOperand(2); 576 if ((N1.getValueType().isFloatingPoint() && 577 !N1.getValueType().isVector()) || 578 !N1.hasOneUse()) 579 continue; 580 581 bool RModW = false; 582 SDValue Load; 583 unsigned Opcode = N1.getNode()->getOpcode(); 584 switch (Opcode) { 585 case ISD::ADD: 586 case ISD::MUL: 587 case ISD::AND: 588 case ISD::OR: 589 case ISD::XOR: 590 case ISD::ADDC: 591 case ISD::ADDE: 592 case ISD::VECTOR_SHUFFLE: { 593 SDValue N10 = N1.getOperand(0); 594 SDValue N11 = N1.getOperand(1); 595 RModW = isRMWLoad(N10, Chain, N2, Load); 596 if (!RModW) 597 RModW = isRMWLoad(N11, Chain, N2, Load); 598 break; 599 } 600 case ISD::SUB: 601 case ISD::SHL: 602 case ISD::SRA: 603 case ISD::SRL: 604 case ISD::ROTL: 605 case ISD::ROTR: 606 case ISD::SUBC: 607 case ISD::SUBE: 608 case X86ISD::SHLD: 609 case X86ISD::SHRD: { 610 SDValue N10 = N1.getOperand(0); 611 RModW = isRMWLoad(N10, Chain, N2, Load); 612 break; 613 } 614 } 615 616 if (RModW) { 617 MoveBelowTokenFactor(CurDAG, Load, SDValue(I, 0), Chain); 618 ++NumLoadMoved; 619 } 620 } 621} 622 623 624/// PreprocessForFPConvert - Walk over the dag lowering fpround and fpextend 625/// nodes that target the FP stack to be store and load to the stack. This is a 626/// gross hack. We would like to simply mark these as being illegal, but when 627/// we do that, legalize produces these when it expands calls, then expands 628/// these in the same legalize pass. We would like dag combine to be able to 629/// hack on these between the call expansion and the node legalization. As such 630/// this pass basically does "really late" legalization of these inline with the 631/// X86 isel pass. 632void X86DAGToDAGISel::PreprocessForFPConvert() { 633 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(), 634 E = CurDAG->allnodes_end(); I != E; ) { 635 SDNode *N = I++; // Preincrement iterator to avoid invalidation issues. 636 if (N->getOpcode() != ISD::FP_ROUND && N->getOpcode() != ISD::FP_EXTEND) 637 continue; 638 639 // If the source and destination are SSE registers, then this is a legal 640 // conversion that should not be lowered. 641 MVT SrcVT = N->getOperand(0).getValueType(); 642 MVT DstVT = N->getValueType(0); 643 bool SrcIsSSE = X86Lowering.isScalarFPTypeInSSEReg(SrcVT); 644 bool DstIsSSE = X86Lowering.isScalarFPTypeInSSEReg(DstVT); 645 if (SrcIsSSE && DstIsSSE) 646 continue; 647 648 if (!SrcIsSSE && !DstIsSSE) { 649 // If this is an FPStack extension, it is a noop. 650 if (N->getOpcode() == ISD::FP_EXTEND) 651 continue; 652 // If this is a value-preserving FPStack truncation, it is a noop. 653 if (N->getConstantOperandVal(1)) 654 continue; 655 } 656 657 // Here we could have an FP stack truncation or an FPStack <-> SSE convert. 658 // FPStack has extload and truncstore. SSE can fold direct loads into other 659 // operations. Based on this, decide what we want to do. 660 MVT MemVT; 661 if (N->getOpcode() == ISD::FP_ROUND) 662 MemVT = DstVT; // FP_ROUND must use DstVT, we can't do a 'trunc load'. 663 else 664 MemVT = SrcIsSSE ? SrcVT : DstVT; 665 666 SDValue MemTmp = CurDAG->CreateStackTemporary(MemVT); 667 DebugLoc dl = N->getDebugLoc(); 668 669 // FIXME: optimize the case where the src/dest is a load or store? 670 SDValue Store = CurDAG->getTruncStore(CurDAG->getEntryNode(), dl, 671 N->getOperand(0), 672 MemTmp, NULL, 0, MemVT); 673 SDValue Result = CurDAG->getExtLoad(ISD::EXTLOAD, dl, DstVT, Store, MemTmp, 674 NULL, 0, MemVT); 675 676 // We're about to replace all uses of the FP_ROUND/FP_EXTEND with the 677 // extload we created. This will cause general havok on the dag because 678 // anything below the conversion could be folded into other existing nodes. 679 // To avoid invalidating 'I', back it up to the convert node. 680 --I; 681 CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Result); 682 683 // Now that we did that, the node is dead. Increment the iterator to the 684 // next node to process, then delete N. 685 ++I; 686 CurDAG->DeleteNode(N); 687 } 688} 689 690/// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel 691/// when it has created a SelectionDAG for us to codegen. 692void X86DAGToDAGISel::InstructionSelect() { 693 CurBB = BB; // BB can change as result of isel. 694 const Function *F = CurDAG->getMachineFunction().getFunction(); 695 OptForSize = F->hasFnAttr(Attribute::OptimizeForSize); 696 697 DEBUG(BB->dump()); 698 if (!Fast) 699 PreprocessForRMW(); 700 701 // FIXME: This should only happen when not -fast. 702 PreprocessForFPConvert(); 703 704 // Codegen the basic block. 705#ifndef NDEBUG 706 DOUT << "===== Instruction selection begins:\n"; 707 Indent = 0; 708#endif 709 SelectRoot(*CurDAG); 710#ifndef NDEBUG 711 DOUT << "===== Instruction selection ends:\n"; 712#endif 713 714 CurDAG->RemoveDeadNodes(); 715} 716 717/// EmitSpecialCodeForMain - Emit any code that needs to be executed only in 718/// the main function. 719void X86DAGToDAGISel::EmitSpecialCodeForMain(MachineBasicBlock *BB, 720 MachineFrameInfo *MFI) { 721 const TargetInstrInfo *TII = TM.getInstrInfo(); 722 if (Subtarget->isTargetCygMing()) 723 BuildMI(BB, DebugLoc::getUnknownLoc(), 724 TII->get(X86::CALLpcrel32)).addExternalSymbol("__main"); 725} 726 727void X86DAGToDAGISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) { 728 // If this is main, emit special code for main. 729 MachineBasicBlock *BB = MF.begin(); 730 if (Fn.hasExternalLinkage() && Fn.getName() == "main") 731 EmitSpecialCodeForMain(BB, MF.getFrameInfo()); 732} 733 734/// MatchAddress - Add the specified node to the specified addressing mode, 735/// returning true if it cannot be done. This just pattern matches for the 736/// addressing mode. 737bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM, 738 bool isRoot, unsigned Depth) { 739 bool is64Bit = Subtarget->is64Bit(); 740 DebugLoc dl = N.getDebugLoc(); 741 DOUT << "MatchAddress: "; DEBUG(AM.dump()); 742 // Limit recursion. 743 if (Depth > 5) 744 return MatchAddressBase(N, AM, isRoot, Depth); 745 746 // RIP relative addressing: %rip + 32-bit displacement! 747 if (AM.isRIPRel) { 748 if (!AM.ES && AM.JT != -1 && N.getOpcode() == ISD::Constant) { 749 uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue(); 750 if (!is64Bit || isInt32(AM.Disp + Val)) { 751 AM.Disp += Val; 752 return false; 753 } 754 } 755 return true; 756 } 757 758 switch (N.getOpcode()) { 759 default: break; 760 case ISD::Constant: { 761 uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue(); 762 if (!is64Bit || isInt32(AM.Disp + Val)) { 763 AM.Disp += Val; 764 return false; 765 } 766 break; 767 } 768 769 case X86ISD::Wrapper: { 770 DOUT << "Wrapper: 64bit " << is64Bit; 771 DOUT << " AM "; DEBUG(AM.dump()); DOUT << "\n"; 772 // Under X86-64 non-small code model, GV (and friends) are 64-bits. 773 // Also, base and index reg must be 0 in order to use rip as base. 774 if (is64Bit && (TM.getCodeModel() != CodeModel::Small || 775 AM.Base.Reg.getNode() || AM.IndexReg.getNode())) 776 break; 777 if (AM.hasSymbolicDisplacement()) 778 break; 779 // If value is available in a register both base and index components have 780 // been picked, we can't fit the result available in the register in the 781 // addressing mode. Duplicate GlobalAddress or ConstantPool as displacement. 782 { 783 SDValue N0 = N.getOperand(0); 784 if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) { 785 uint64_t Offset = G->getOffset(); 786 if (!is64Bit || isInt32(AM.Disp + Offset)) { 787 GlobalValue *GV = G->getGlobal(); 788 AM.GV = GV; 789 AM.Disp += Offset; 790 AM.isRIPRel = TM.symbolicAddressesAreRIPRel(); 791 return false; 792 } 793 } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) { 794 uint64_t Offset = CP->getOffset(); 795 if (!is64Bit || isInt32(AM.Disp + Offset)) { 796 AM.CP = CP->getConstVal(); 797 AM.Align = CP->getAlignment(); 798 AM.Disp += Offset; 799 AM.isRIPRel = TM.symbolicAddressesAreRIPRel(); 800 return false; 801 } 802 } else if (ExternalSymbolSDNode *S =dyn_cast<ExternalSymbolSDNode>(N0)) { 803 AM.ES = S->getSymbol(); 804 AM.isRIPRel = TM.symbolicAddressesAreRIPRel(); 805 return false; 806 } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) { 807 AM.JT = J->getIndex(); 808 AM.isRIPRel = TM.symbolicAddressesAreRIPRel(); 809 return false; 810 } 811 } 812 break; 813 } 814 815 case ISD::FrameIndex: 816 if (AM.BaseType == X86ISelAddressMode::RegBase 817 && AM.Base.Reg.getNode() == 0) { 818 AM.BaseType = X86ISelAddressMode::FrameIndexBase; 819 AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex(); 820 return false; 821 } 822 break; 823 824 case ISD::SHL: 825 if (AM.IndexReg.getNode() != 0 || AM.Scale != 1 || AM.isRIPRel) 826 break; 827 828 if (ConstantSDNode 829 *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1))) { 830 unsigned Val = CN->getZExtValue(); 831 if (Val == 1 || Val == 2 || Val == 3) { 832 AM.Scale = 1 << Val; 833 SDValue ShVal = N.getNode()->getOperand(0); 834 835 // Okay, we know that we have a scale by now. However, if the scaled 836 // value is an add of something and a constant, we can fold the 837 // constant into the disp field here. 838 if (ShVal.getNode()->getOpcode() == ISD::ADD && ShVal.hasOneUse() && 839 isa<ConstantSDNode>(ShVal.getNode()->getOperand(1))) { 840 AM.IndexReg = ShVal.getNode()->getOperand(0); 841 ConstantSDNode *AddVal = 842 cast<ConstantSDNode>(ShVal.getNode()->getOperand(1)); 843 uint64_t Disp = AM.Disp + (AddVal->getSExtValue() << Val); 844 if (!is64Bit || isInt32(Disp)) 845 AM.Disp = Disp; 846 else 847 AM.IndexReg = ShVal; 848 } else { 849 AM.IndexReg = ShVal; 850 } 851 return false; 852 } 853 break; 854 } 855 856 case ISD::SMUL_LOHI: 857 case ISD::UMUL_LOHI: 858 // A mul_lohi where we need the low part can be folded as a plain multiply. 859 if (N.getResNo() != 0) break; 860 // FALL THROUGH 861 case ISD::MUL: 862 // X*[3,5,9] -> X+X*[2,4,8] 863 if (AM.BaseType == X86ISelAddressMode::RegBase && 864 AM.Base.Reg.getNode() == 0 && 865 AM.IndexReg.getNode() == 0 && 866 !AM.isRIPRel) { 867 if (ConstantSDNode 868 *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1))) 869 if (CN->getZExtValue() == 3 || CN->getZExtValue() == 5 || 870 CN->getZExtValue() == 9) { 871 AM.Scale = unsigned(CN->getZExtValue())-1; 872 873 SDValue MulVal = N.getNode()->getOperand(0); 874 SDValue Reg; 875 876 // Okay, we know that we have a scale by now. However, if the scaled 877 // value is an add of something and a constant, we can fold the 878 // constant into the disp field here. 879 if (MulVal.getNode()->getOpcode() == ISD::ADD && MulVal.hasOneUse() && 880 isa<ConstantSDNode>(MulVal.getNode()->getOperand(1))) { 881 Reg = MulVal.getNode()->getOperand(0); 882 ConstantSDNode *AddVal = 883 cast<ConstantSDNode>(MulVal.getNode()->getOperand(1)); 884 uint64_t Disp = AM.Disp + AddVal->getSExtValue() * 885 CN->getZExtValue(); 886 if (!is64Bit || isInt32(Disp)) 887 AM.Disp = Disp; 888 else 889 Reg = N.getNode()->getOperand(0); 890 } else { 891 Reg = N.getNode()->getOperand(0); 892 } 893 894 AM.IndexReg = AM.Base.Reg = Reg; 895 return false; 896 } 897 } 898 break; 899 900 case ISD::ADD: { 901 X86ISelAddressMode Backup = AM; 902 if (!MatchAddress(N.getNode()->getOperand(0), AM, false, Depth+1) && 903 !MatchAddress(N.getNode()->getOperand(1), AM, false, Depth+1)) 904 return false; 905 AM = Backup; 906 if (!MatchAddress(N.getNode()->getOperand(1), AM, false, Depth+1) && 907 !MatchAddress(N.getNode()->getOperand(0), AM, false, Depth+1)) 908 return false; 909 AM = Backup; 910 break; 911 } 912 913 case ISD::OR: 914 // Handle "X | C" as "X + C" iff X is known to have C bits clear. 915 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) { 916 X86ISelAddressMode Backup = AM; 917 uint64_t Offset = CN->getSExtValue(); 918 // Start with the LHS as an addr mode. 919 if (!MatchAddress(N.getOperand(0), AM, false) && 920 // Address could not have picked a GV address for the displacement. 921 AM.GV == NULL && 922 // On x86-64, the resultant disp must fit in 32-bits. 923 (!is64Bit || isInt32(AM.Disp + Offset)) && 924 // Check to see if the LHS & C is zero. 925 CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getAPIntValue())) { 926 AM.Disp += Offset; 927 return false; 928 } 929 AM = Backup; 930 } 931 break; 932 933 case ISD::AND: { 934 // Handle "(x << C1) & C2" as "(X & (C2>>C1)) << C1" if safe and if this 935 // allows us to fold the shift into this addressing mode. 936 SDValue Shift = N.getOperand(0); 937 if (Shift.getOpcode() != ISD::SHL) break; 938 939 // Scale must not be used already. 940 if (AM.IndexReg.getNode() != 0 || AM.Scale != 1) break; 941 942 // Not when RIP is used as the base. 943 if (AM.isRIPRel) break; 944 945 ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(N.getOperand(1)); 946 ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Shift.getOperand(1)); 947 if (!C1 || !C2) break; 948 949 // Not likely to be profitable if either the AND or SHIFT node has more 950 // than one use (unless all uses are for address computation). Besides, 951 // isel mechanism requires their node ids to be reused. 952 if (!N.hasOneUse() || !Shift.hasOneUse()) 953 break; 954 955 // Verify that the shift amount is something we can fold. 956 unsigned ShiftCst = C1->getZExtValue(); 957 if (ShiftCst != 1 && ShiftCst != 2 && ShiftCst != 3) 958 break; 959 960 // Get the new AND mask, this folds to a constant. 961 SDValue X = Shift.getOperand(0); 962 SDValue NewANDMask = CurDAG->getNode(ISD::SRL, dl, N.getValueType(), 963 SDValue(C2, 0), SDValue(C1, 0)); 964 SDValue NewAND = CurDAG->getNode(ISD::AND, dl, N.getValueType(), X, 965 NewANDMask); 966 SDValue NewSHIFT = CurDAG->getNode(ISD::SHL, dl, N.getValueType(), 967 NewAND, SDValue(C1, 0)); 968 969 // Insert the new nodes into the topological ordering. 970 if (C1->getNodeId() > X.getNode()->getNodeId()) { 971 CurDAG->RepositionNode(X.getNode(), C1); 972 C1->setNodeId(X.getNode()->getNodeId()); 973 } 974 if (NewANDMask.getNode()->getNodeId() == -1 || 975 NewANDMask.getNode()->getNodeId() > X.getNode()->getNodeId()) { 976 CurDAG->RepositionNode(X.getNode(), NewANDMask.getNode()); 977 NewANDMask.getNode()->setNodeId(X.getNode()->getNodeId()); 978 } 979 if (NewAND.getNode()->getNodeId() == -1 || 980 NewAND.getNode()->getNodeId() > Shift.getNode()->getNodeId()) { 981 CurDAG->RepositionNode(Shift.getNode(), NewAND.getNode()); 982 NewAND.getNode()->setNodeId(Shift.getNode()->getNodeId()); 983 } 984 if (NewSHIFT.getNode()->getNodeId() == -1 || 985 NewSHIFT.getNode()->getNodeId() > N.getNode()->getNodeId()) { 986 CurDAG->RepositionNode(N.getNode(), NewSHIFT.getNode()); 987 NewSHIFT.getNode()->setNodeId(N.getNode()->getNodeId()); 988 } 989 990 CurDAG->ReplaceAllUsesWith(N, NewSHIFT); 991 992 AM.Scale = 1 << ShiftCst; 993 AM.IndexReg = NewAND; 994 return false; 995 } 996 } 997 998 return MatchAddressBase(N, AM, isRoot, Depth); 999} 1000 1001/// MatchAddressBase - Helper for MatchAddress. Add the specified node to the 1002/// specified addressing mode without any further recursion. 1003bool X86DAGToDAGISel::MatchAddressBase(SDValue N, X86ISelAddressMode &AM, 1004 bool isRoot, unsigned Depth) { 1005 // Is the base register already occupied? 1006 if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.getNode()) { 1007 // If so, check to see if the scale index register is set. 1008 if (AM.IndexReg.getNode() == 0 && !AM.isRIPRel) { 1009 AM.IndexReg = N; 1010 AM.Scale = 1; 1011 return false; 1012 } 1013 1014 // Otherwise, we cannot select it. 1015 return true; 1016 } 1017 1018 // Default, generate it as a register. 1019 AM.BaseType = X86ISelAddressMode::RegBase; 1020 AM.Base.Reg = N; 1021 return false; 1022} 1023 1024/// SelectAddr - returns true if it is able pattern match an addressing mode. 1025/// It returns the operands which make up the maximal addressing mode it can 1026/// match by reference. 1027bool X86DAGToDAGISel::SelectAddr(SDValue Op, SDValue N, SDValue &Base, 1028 SDValue &Scale, SDValue &Index, 1029 SDValue &Disp) { 1030 X86ISelAddressMode AM; 1031 if (MatchAddress(N, AM)) 1032 return false; 1033 1034 MVT VT = N.getValueType(); 1035 if (AM.BaseType == X86ISelAddressMode::RegBase) { 1036 if (!AM.Base.Reg.getNode()) 1037 AM.Base.Reg = CurDAG->getRegister(0, VT); 1038 } 1039 1040 if (!AM.IndexReg.getNode()) 1041 AM.IndexReg = CurDAG->getRegister(0, VT); 1042 1043 getAddressOperands(AM, Base, Scale, Index, Disp); 1044 return true; 1045} 1046 1047/// SelectScalarSSELoad - Match a scalar SSE load. In particular, we want to 1048/// match a load whose top elements are either undef or zeros. The load flavor 1049/// is derived from the type of N, which is either v4f32 or v2f64. 1050bool X86DAGToDAGISel::SelectScalarSSELoad(SDValue Op, SDValue Pred, 1051 SDValue N, SDValue &Base, 1052 SDValue &Scale, SDValue &Index, 1053 SDValue &Disp, SDValue &InChain, 1054 SDValue &OutChain) { 1055 if (N.getOpcode() == ISD::SCALAR_TO_VECTOR) { 1056 InChain = N.getOperand(0).getValue(1); 1057 if (ISD::isNON_EXTLoad(InChain.getNode()) && 1058 InChain.getValue(0).hasOneUse() && 1059 N.hasOneUse() && 1060 IsLegalAndProfitableToFold(N.getNode(), Pred.getNode(), Op.getNode())) { 1061 LoadSDNode *LD = cast<LoadSDNode>(InChain); 1062 if (!SelectAddr(Op, LD->getBasePtr(), Base, Scale, Index, Disp)) 1063 return false; 1064 OutChain = LD->getChain(); 1065 return true; 1066 } 1067 } 1068 1069 // Also handle the case where we explicitly require zeros in the top 1070 // elements. This is a vector shuffle from the zero vector. 1071 if (N.getOpcode() == X86ISD::VZEXT_MOVL && N.getNode()->hasOneUse() && 1072 // Check to see if the top elements are all zeros (or bitcast of zeros). 1073 N.getOperand(0).getOpcode() == ISD::SCALAR_TO_VECTOR && 1074 N.getOperand(0).getNode()->hasOneUse() && 1075 ISD::isNON_EXTLoad(N.getOperand(0).getOperand(0).getNode()) && 1076 N.getOperand(0).getOperand(0).hasOneUse()) { 1077 // Okay, this is a zero extending load. Fold it. 1078 LoadSDNode *LD = cast<LoadSDNode>(N.getOperand(0).getOperand(0)); 1079 if (!SelectAddr(Op, LD->getBasePtr(), Base, Scale, Index, Disp)) 1080 return false; 1081 OutChain = LD->getChain(); 1082 InChain = SDValue(LD, 1); 1083 return true; 1084 } 1085 return false; 1086} 1087 1088 1089/// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing 1090/// mode it matches can be cost effectively emitted as an LEA instruction. 1091bool X86DAGToDAGISel::SelectLEAAddr(SDValue Op, SDValue N, 1092 SDValue &Base, SDValue &Scale, 1093 SDValue &Index, SDValue &Disp) { 1094 X86ISelAddressMode AM; 1095 if (MatchAddress(N, AM)) 1096 return false; 1097 1098 MVT VT = N.getValueType(); 1099 unsigned Complexity = 0; 1100 if (AM.BaseType == X86ISelAddressMode::RegBase) 1101 if (AM.Base.Reg.getNode()) 1102 Complexity = 1; 1103 else 1104 AM.Base.Reg = CurDAG->getRegister(0, VT); 1105 else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase) 1106 Complexity = 4; 1107 1108 if (AM.IndexReg.getNode()) 1109 Complexity++; 1110 else 1111 AM.IndexReg = CurDAG->getRegister(0, VT); 1112 1113 // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg, or with 1114 // a simple shift. 1115 if (AM.Scale > 1) 1116 Complexity++; 1117 1118 // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA 1119 // to a LEA. This is determined with some expermentation but is by no means 1120 // optimal (especially for code size consideration). LEA is nice because of 1121 // its three-address nature. Tweak the cost function again when we can run 1122 // convertToThreeAddress() at register allocation time. 1123 if (AM.hasSymbolicDisplacement()) { 1124 // For X86-64, we should always use lea to materialize RIP relative 1125 // addresses. 1126 if (Subtarget->is64Bit()) 1127 Complexity = 4; 1128 else 1129 Complexity += 2; 1130 } 1131 1132 if (AM.Disp && (AM.Base.Reg.getNode() || AM.IndexReg.getNode())) 1133 Complexity++; 1134 1135 if (Complexity > 2) { 1136 getAddressOperands(AM, Base, Scale, Index, Disp); 1137 return true; 1138 } 1139 return false; 1140} 1141 1142bool X86DAGToDAGISel::TryFoldLoad(SDValue P, SDValue N, 1143 SDValue &Base, SDValue &Scale, 1144 SDValue &Index, SDValue &Disp) { 1145 if (ISD::isNON_EXTLoad(N.getNode()) && 1146 N.hasOneUse() && 1147 IsLegalAndProfitableToFold(N.getNode(), P.getNode(), P.getNode())) 1148 return SelectAddr(P, N.getOperand(1), Base, Scale, Index, Disp); 1149 return false; 1150} 1151 1152/// getGlobalBaseReg - Return an SDNode that returns the value of 1153/// the global base register. Output instructions required to 1154/// initialize the global base register, if necessary. 1155/// 1156SDNode *X86DAGToDAGISel::getGlobalBaseReg() { 1157 MachineFunction *MF = CurBB->getParent(); 1158 unsigned GlobalBaseReg = TM.getInstrInfo()->getGlobalBaseReg(MF); 1159 return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode(); 1160} 1161 1162static SDNode *FindCallStartFromCall(SDNode *Node) { 1163 if (Node->getOpcode() == ISD::CALLSEQ_START) return Node; 1164 assert(Node->getOperand(0).getValueType() == MVT::Other && 1165 "Node doesn't have a token chain argument!"); 1166 return FindCallStartFromCall(Node->getOperand(0).getNode()); 1167} 1168 1169/// getTruncateTo8Bit - return an SDNode that implements a subreg based 1170/// truncate of the specified operand to i8. This can be done with tablegen, 1171/// except that this code uses MVT::Flag in a tricky way that happens to 1172/// improve scheduling in some cases. 1173SDNode *X86DAGToDAGISel::getTruncateTo8Bit(SDValue N0) { 1174 assert(!Subtarget->is64Bit() && 1175 "getTruncateTo8Bit is only needed on x86-32!"); 1176 SDValue SRIdx = CurDAG->getTargetConstant(1, MVT::i32); // SubRegSet 1 1177 DebugLoc dl = N0.getDebugLoc(); 1178 1179 // Ensure that the source register has an 8-bit subreg on 32-bit targets 1180 unsigned Opc; 1181 MVT N0VT = N0.getValueType(); 1182 switch (N0VT.getSimpleVT()) { 1183 default: assert(0 && "Unknown truncate!"); 1184 case MVT::i16: 1185 Opc = X86::MOV16to16_; 1186 break; 1187 case MVT::i32: 1188 Opc = X86::MOV32to32_; 1189 break; 1190 } 1191 1192 // The use of MVT::Flag here is not strictly accurate, but it helps 1193 // scheduling in some cases. 1194 N0 = SDValue(CurDAG->getTargetNode(Opc, dl, N0VT, MVT::Flag, N0), 0); 1195 return CurDAG->getTargetNode(X86::EXTRACT_SUBREG, dl, 1196 MVT::i8, N0, SRIdx, N0.getValue(1)); 1197} 1198 1199SDNode *X86DAGToDAGISel::SelectAtomic64(SDNode *Node, unsigned Opc) { 1200 SDValue Chain = Node->getOperand(0); 1201 SDValue In1 = Node->getOperand(1); 1202 SDValue In2L = Node->getOperand(2); 1203 SDValue In2H = Node->getOperand(3); 1204 SDValue Tmp0, Tmp1, Tmp2, Tmp3; 1205 if (!SelectAddr(In1, In1, Tmp0, Tmp1, Tmp2, Tmp3)) 1206 return NULL; 1207 SDValue LSI = Node->getOperand(4); // MemOperand 1208 const SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, In2L, In2H, LSI, Chain }; 1209 return CurDAG->getTargetNode(Opc, Node->getDebugLoc(), 1210 MVT::i32, MVT::i32, MVT::Other, Ops, 8); 1211} 1212 1213SDNode *X86DAGToDAGISel::Select(SDValue N) { 1214 SDNode *Node = N.getNode(); 1215 MVT NVT = Node->getValueType(0); 1216 unsigned Opc, MOpc; 1217 unsigned Opcode = Node->getOpcode(); 1218 DebugLoc dl = Node->getDebugLoc(); 1219 1220#ifndef NDEBUG 1221 DOUT << std::string(Indent, ' ') << "Selecting: "; 1222 DEBUG(Node->dump(CurDAG)); 1223 DOUT << "\n"; 1224 Indent += 2; 1225#endif 1226 1227 if (Node->isMachineOpcode()) { 1228#ifndef NDEBUG 1229 DOUT << std::string(Indent-2, ' ') << "== "; 1230 DEBUG(Node->dump(CurDAG)); 1231 DOUT << "\n"; 1232 Indent -= 2; 1233#endif 1234 return NULL; // Already selected. 1235 } 1236 1237 switch (Opcode) { 1238 default: break; 1239 case X86ISD::GlobalBaseReg: 1240 return getGlobalBaseReg(); 1241 1242 case X86ISD::ATOMOR64_DAG: 1243 return SelectAtomic64(Node, X86::ATOMOR6432); 1244 case X86ISD::ATOMXOR64_DAG: 1245 return SelectAtomic64(Node, X86::ATOMXOR6432); 1246 case X86ISD::ATOMADD64_DAG: 1247 return SelectAtomic64(Node, X86::ATOMADD6432); 1248 case X86ISD::ATOMSUB64_DAG: 1249 return SelectAtomic64(Node, X86::ATOMSUB6432); 1250 case X86ISD::ATOMNAND64_DAG: 1251 return SelectAtomic64(Node, X86::ATOMNAND6432); 1252 case X86ISD::ATOMAND64_DAG: 1253 return SelectAtomic64(Node, X86::ATOMAND6432); 1254 case X86ISD::ATOMSWAP64_DAG: 1255 return SelectAtomic64(Node, X86::ATOMSWAP6432); 1256 1257 case ISD::SMUL_LOHI: 1258 case ISD::UMUL_LOHI: { 1259 SDValue N0 = Node->getOperand(0); 1260 SDValue N1 = Node->getOperand(1); 1261 1262 bool isSigned = Opcode == ISD::SMUL_LOHI; 1263 if (!isSigned) 1264 switch (NVT.getSimpleVT()) { 1265 default: assert(0 && "Unsupported VT!"); 1266 case MVT::i8: Opc = X86::MUL8r; MOpc = X86::MUL8m; break; 1267 case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break; 1268 case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break; 1269 case MVT::i64: Opc = X86::MUL64r; MOpc = X86::MUL64m; break; 1270 } 1271 else 1272 switch (NVT.getSimpleVT()) { 1273 default: assert(0 && "Unsupported VT!"); 1274 case MVT::i8: Opc = X86::IMUL8r; MOpc = X86::IMUL8m; break; 1275 case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break; 1276 case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break; 1277 case MVT::i64: Opc = X86::IMUL64r; MOpc = X86::IMUL64m; break; 1278 } 1279 1280 unsigned LoReg, HiReg; 1281 switch (NVT.getSimpleVT()) { 1282 default: assert(0 && "Unsupported VT!"); 1283 case MVT::i8: LoReg = X86::AL; HiReg = X86::AH; break; 1284 case MVT::i16: LoReg = X86::AX; HiReg = X86::DX; break; 1285 case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break; 1286 case MVT::i64: LoReg = X86::RAX; HiReg = X86::RDX; break; 1287 } 1288 1289 SDValue Tmp0, Tmp1, Tmp2, Tmp3; 1290 bool foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 1291 // multiplty is commmutative 1292 if (!foldedLoad) { 1293 foldedLoad = TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3); 1294 if (foldedLoad) 1295 std::swap(N0, N1); 1296 } 1297 1298 SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, LoReg, 1299 N0, SDValue()).getValue(1); 1300 1301 if (foldedLoad) { 1302 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, N1.getOperand(0), InFlag }; 1303 SDNode *CNode = 1304 CurDAG->getTargetNode(MOpc, dl, MVT::Other, MVT::Flag, Ops, 6); 1305 InFlag = SDValue(CNode, 1); 1306 // Update the chain. 1307 ReplaceUses(N1.getValue(1), SDValue(CNode, 0)); 1308 } else { 1309 InFlag = 1310 SDValue(CurDAG->getTargetNode(Opc, dl, MVT::Flag, N1, InFlag), 0); 1311 } 1312 1313 // Copy the low half of the result, if it is needed. 1314 if (!N.getValue(0).use_empty()) { 1315 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1316 LoReg, NVT, InFlag); 1317 InFlag = Result.getValue(2); 1318 ReplaceUses(N.getValue(0), Result); 1319#ifndef NDEBUG 1320 DOUT << std::string(Indent-2, ' ') << "=> "; 1321 DEBUG(Result.getNode()->dump(CurDAG)); 1322 DOUT << "\n"; 1323#endif 1324 } 1325 // Copy the high half of the result, if it is needed. 1326 if (!N.getValue(1).use_empty()) { 1327 SDValue Result; 1328 if (HiReg == X86::AH && Subtarget->is64Bit()) { 1329 // Prevent use of AH in a REX instruction by referencing AX instead. 1330 // Shift it down 8 bits. 1331 Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1332 X86::AX, MVT::i16, InFlag); 1333 InFlag = Result.getValue(2); 1334 Result = SDValue(CurDAG->getTargetNode(X86::SHR16ri, dl, MVT::i16, 1335 Result, 1336 CurDAG->getTargetConstant(8, MVT::i8)), 0); 1337 // Then truncate it down to i8. 1338 SDValue SRIdx = CurDAG->getTargetConstant(1, MVT::i32); // SubRegSet 1 1339 Result = SDValue(CurDAG->getTargetNode(X86::EXTRACT_SUBREG, dl, 1340 MVT::i8, Result, SRIdx), 0); 1341 } else { 1342 Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1343 HiReg, NVT, InFlag); 1344 InFlag = Result.getValue(2); 1345 } 1346 ReplaceUses(N.getValue(1), Result); 1347#ifndef NDEBUG 1348 DOUT << std::string(Indent-2, ' ') << "=> "; 1349 DEBUG(Result.getNode()->dump(CurDAG)); 1350 DOUT << "\n"; 1351#endif 1352 } 1353 1354#ifndef NDEBUG 1355 Indent -= 2; 1356#endif 1357 1358 return NULL; 1359 } 1360 1361 case ISD::SDIVREM: 1362 case ISD::UDIVREM: { 1363 SDValue N0 = Node->getOperand(0); 1364 SDValue N1 = Node->getOperand(1); 1365 1366 bool isSigned = Opcode == ISD::SDIVREM; 1367 if (!isSigned) 1368 switch (NVT.getSimpleVT()) { 1369 default: assert(0 && "Unsupported VT!"); 1370 case MVT::i8: Opc = X86::DIV8r; MOpc = X86::DIV8m; break; 1371 case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break; 1372 case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break; 1373 case MVT::i64: Opc = X86::DIV64r; MOpc = X86::DIV64m; break; 1374 } 1375 else 1376 switch (NVT.getSimpleVT()) { 1377 default: assert(0 && "Unsupported VT!"); 1378 case MVT::i8: Opc = X86::IDIV8r; MOpc = X86::IDIV8m; break; 1379 case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break; 1380 case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break; 1381 case MVT::i64: Opc = X86::IDIV64r; MOpc = X86::IDIV64m; break; 1382 } 1383 1384 unsigned LoReg, HiReg; 1385 unsigned ClrOpcode, SExtOpcode; 1386 switch (NVT.getSimpleVT()) { 1387 default: assert(0 && "Unsupported VT!"); 1388 case MVT::i8: 1389 LoReg = X86::AL; HiReg = X86::AH; 1390 ClrOpcode = 0; 1391 SExtOpcode = X86::CBW; 1392 break; 1393 case MVT::i16: 1394 LoReg = X86::AX; HiReg = X86::DX; 1395 ClrOpcode = X86::MOV16r0; 1396 SExtOpcode = X86::CWD; 1397 break; 1398 case MVT::i32: 1399 LoReg = X86::EAX; HiReg = X86::EDX; 1400 ClrOpcode = X86::MOV32r0; 1401 SExtOpcode = X86::CDQ; 1402 break; 1403 case MVT::i64: 1404 LoReg = X86::RAX; HiReg = X86::RDX; 1405 ClrOpcode = X86::MOV64r0; 1406 SExtOpcode = X86::CQO; 1407 break; 1408 } 1409 1410 SDValue Tmp0, Tmp1, Tmp2, Tmp3; 1411 bool foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 1412 bool signBitIsZero = CurDAG->SignBitIsZero(N0); 1413 1414 SDValue InFlag; 1415 if (NVT == MVT::i8 && (!isSigned || signBitIsZero)) { 1416 // Special case for div8, just use a move with zero extension to AX to 1417 // clear the upper 8 bits (AH). 1418 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Move, Chain; 1419 if (TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3)) { 1420 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, N0.getOperand(0) }; 1421 Move = 1422 SDValue(CurDAG->getTargetNode(X86::MOVZX16rm8, dl, MVT::i16, 1423 MVT::Other, Ops, 5), 0); 1424 Chain = Move.getValue(1); 1425 ReplaceUses(N0.getValue(1), Chain); 1426 } else { 1427 Move = 1428 SDValue(CurDAG->getTargetNode(X86::MOVZX16rr8, dl, MVT::i16, N0),0); 1429 Chain = CurDAG->getEntryNode(); 1430 } 1431 Chain = CurDAG->getCopyToReg(Chain, dl, X86::AX, Move, SDValue()); 1432 InFlag = Chain.getValue(1); 1433 } else { 1434 InFlag = 1435 CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, 1436 LoReg, N0, SDValue()).getValue(1); 1437 if (isSigned && !signBitIsZero) { 1438 // Sign extend the low part into the high part. 1439 InFlag = 1440 SDValue(CurDAG->getTargetNode(SExtOpcode, dl, MVT::Flag, InFlag),0); 1441 } else { 1442 // Zero out the high part, effectively zero extending the input. 1443 SDValue ClrNode = SDValue(CurDAG->getTargetNode(ClrOpcode, dl, NVT), 1444 0); 1445 InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, HiReg, 1446 ClrNode, InFlag).getValue(1); 1447 } 1448 } 1449 1450 if (foldedLoad) { 1451 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, N1.getOperand(0), InFlag }; 1452 SDNode *CNode = 1453 CurDAG->getTargetNode(MOpc, dl, MVT::Other, MVT::Flag, Ops, 6); 1454 InFlag = SDValue(CNode, 1); 1455 // Update the chain. 1456 ReplaceUses(N1.getValue(1), SDValue(CNode, 0)); 1457 } else { 1458 InFlag = 1459 SDValue(CurDAG->getTargetNode(Opc, dl, MVT::Flag, N1, InFlag), 0); 1460 } 1461 1462 // Copy the division (low) result, if it is needed. 1463 if (!N.getValue(0).use_empty()) { 1464 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1465 LoReg, NVT, InFlag); 1466 InFlag = Result.getValue(2); 1467 ReplaceUses(N.getValue(0), Result); 1468#ifndef NDEBUG 1469 DOUT << std::string(Indent-2, ' ') << "=> "; 1470 DEBUG(Result.getNode()->dump(CurDAG)); 1471 DOUT << "\n"; 1472#endif 1473 } 1474 // Copy the remainder (high) result, if it is needed. 1475 if (!N.getValue(1).use_empty()) { 1476 SDValue Result; 1477 if (HiReg == X86::AH && Subtarget->is64Bit()) { 1478 // Prevent use of AH in a REX instruction by referencing AX instead. 1479 // Shift it down 8 bits. 1480 Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1481 X86::AX, MVT::i16, InFlag); 1482 InFlag = Result.getValue(2); 1483 Result = SDValue(CurDAG->getTargetNode(X86::SHR16ri, dl, MVT::i16, 1484 Result, 1485 CurDAG->getTargetConstant(8, MVT::i8)), 1486 0); 1487 // Then truncate it down to i8. 1488 SDValue SRIdx = CurDAG->getTargetConstant(1, MVT::i32); // SubRegSet 1 1489 Result = SDValue(CurDAG->getTargetNode(X86::EXTRACT_SUBREG, dl, 1490 MVT::i8, Result, SRIdx), 0); 1491 } else { 1492 Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1493 HiReg, NVT, InFlag); 1494 InFlag = Result.getValue(2); 1495 } 1496 ReplaceUses(N.getValue(1), Result); 1497#ifndef NDEBUG 1498 DOUT << std::string(Indent-2, ' ') << "=> "; 1499 DEBUG(Result.getNode()->dump(CurDAG)); 1500 DOUT << "\n"; 1501#endif 1502 } 1503 1504#ifndef NDEBUG 1505 Indent -= 2; 1506#endif 1507 1508 return NULL; 1509 } 1510 1511 case ISD::SIGN_EXTEND_INREG: { 1512 MVT SVT = cast<VTSDNode>(Node->getOperand(1))->getVT(); 1513 if (SVT == MVT::i8 && !Subtarget->is64Bit()) { 1514 SDValue N0 = Node->getOperand(0); 1515 1516 SDValue TruncOp = SDValue(getTruncateTo8Bit(N0), 0); 1517 unsigned Opc = 0; 1518 switch (NVT.getSimpleVT()) { 1519 default: assert(0 && "Unknown sign_extend_inreg!"); 1520 case MVT::i16: 1521 Opc = X86::MOVSX16rr8; 1522 break; 1523 case MVT::i32: 1524 Opc = X86::MOVSX32rr8; 1525 break; 1526 } 1527 1528 SDNode *ResNode = CurDAG->getTargetNode(Opc, dl, NVT, TruncOp); 1529 1530#ifndef NDEBUG 1531 DOUT << std::string(Indent-2, ' ') << "=> "; 1532 DEBUG(TruncOp.getNode()->dump(CurDAG)); 1533 DOUT << "\n"; 1534 DOUT << std::string(Indent-2, ' ') << "=> "; 1535 DEBUG(ResNode->dump(CurDAG)); 1536 DOUT << "\n"; 1537 Indent -= 2; 1538#endif 1539 return ResNode; 1540 } 1541 break; 1542 } 1543 1544 case ISD::TRUNCATE: { 1545 if (NVT == MVT::i8 && !Subtarget->is64Bit()) { 1546 SDValue Input = Node->getOperand(0); 1547 SDNode *ResNode = getTruncateTo8Bit(Input); 1548 1549#ifndef NDEBUG 1550 DOUT << std::string(Indent-2, ' ') << "=> "; 1551 DEBUG(ResNode->dump(CurDAG)); 1552 DOUT << "\n"; 1553 Indent -= 2; 1554#endif 1555 return ResNode; 1556 } 1557 break; 1558 } 1559 1560 case ISD::DECLARE: { 1561 // Handle DECLARE nodes here because the second operand may have been 1562 // wrapped in X86ISD::Wrapper. 1563 SDValue Chain = Node->getOperand(0); 1564 SDValue N1 = Node->getOperand(1); 1565 SDValue N2 = Node->getOperand(2); 1566 FrameIndexSDNode *FINode = dyn_cast<FrameIndexSDNode>(N1); 1567 1568 // FIXME: We need to handle this for VLAs. 1569 if (!FINode) { 1570 ReplaceUses(N.getValue(0), Chain); 1571 return NULL; 1572 } 1573 1574 if (N2.getOpcode() == ISD::ADD && 1575 N2.getOperand(0).getOpcode() == X86ISD::GlobalBaseReg) 1576 N2 = N2.getOperand(1); 1577 1578 // If N2 is not Wrapper(decriptor) then the llvm.declare is mangled 1579 // somehow, just ignore it. 1580 if (N2.getOpcode() != X86ISD::Wrapper) { 1581 ReplaceUses(N.getValue(0), Chain); 1582 return NULL; 1583 } 1584 GlobalAddressSDNode *GVNode = 1585 dyn_cast<GlobalAddressSDNode>(N2.getOperand(0)); 1586 if (GVNode == 0) { 1587 ReplaceUses(N.getValue(0), Chain); 1588 return NULL; 1589 } 1590 SDValue Tmp1 = CurDAG->getTargetFrameIndex(FINode->getIndex(), 1591 TLI.getPointerTy()); 1592 SDValue Tmp2 = CurDAG->getTargetGlobalAddress(GVNode->getGlobal(), 1593 TLI.getPointerTy()); 1594 SDValue Ops[] = { Tmp1, Tmp2, Chain }; 1595 return CurDAG->getTargetNode(TargetInstrInfo::DECLARE, dl, 1596 MVT::Other, Ops, 3); 1597 } 1598 } 1599 1600 SDNode *ResNode = SelectCode(N); 1601 1602#ifndef NDEBUG 1603 DOUT << std::string(Indent-2, ' ') << "=> "; 1604 if (ResNode == NULL || ResNode == N.getNode()) 1605 DEBUG(N.getNode()->dump(CurDAG)); 1606 else 1607 DEBUG(ResNode->dump(CurDAG)); 1608 DOUT << "\n"; 1609 Indent -= 2; 1610#endif 1611 1612 return ResNode; 1613} 1614 1615bool X86DAGToDAGISel:: 1616SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode, 1617 std::vector<SDValue> &OutOps) { 1618 SDValue Op0, Op1, Op2, Op3; 1619 switch (ConstraintCode) { 1620 case 'o': // offsetable ?? 1621 case 'v': // not offsetable ?? 1622 default: return true; 1623 case 'm': // memory 1624 if (!SelectAddr(Op, Op, Op0, Op1, Op2, Op3)) 1625 return true; 1626 break; 1627 } 1628 1629 OutOps.push_back(Op0); 1630 OutOps.push_back(Op1); 1631 OutOps.push_back(Op2); 1632 OutOps.push_back(Op3); 1633 return false; 1634} 1635 1636/// createX86ISelDag - This pass converts a legalized DAG into a 1637/// X86-specific DAG, ready for instruction scheduling. 1638/// 1639FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM, bool Fast) { 1640 return new X86DAGToDAGISel(TM, Fast); 1641} 1642