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