X86ISelDAGToDAG.cpp revision b20a8fc8a6bf57dbde0e9238cf535abb4326dc80
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 "X86MachineFunctionInfo.h" 19#include "X86RegisterInfo.h" 20#include "X86Subtarget.h" 21#include "X86TargetMachine.h" 22#include "llvm/Instructions.h" 23#include "llvm/Intrinsics.h" 24#include "llvm/Support/CFG.h" 25#include "llvm/Type.h" 26#include "llvm/CodeGen/MachineConstantPool.h" 27#include "llvm/CodeGen/MachineFunction.h" 28#include "llvm/CodeGen/MachineFrameInfo.h" 29#include "llvm/CodeGen/MachineInstrBuilder.h" 30#include "llvm/CodeGen/MachineRegisterInfo.h" 31#include "llvm/CodeGen/SelectionDAGISel.h" 32#include "llvm/Target/TargetMachine.h" 33#include "llvm/Target/TargetOptions.h" 34#include "llvm/Support/Debug.h" 35#include "llvm/Support/ErrorHandling.h" 36#include "llvm/Support/MathExtras.h" 37#include "llvm/Support/raw_ostream.h" 38#include "llvm/ADT/SmallPtrSet.h" 39#include "llvm/ADT/Statistic.h" 40using namespace llvm; 41 42STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor"); 43 44//===----------------------------------------------------------------------===// 45// Pattern Matcher Implementation 46//===----------------------------------------------------------------------===// 47 48namespace { 49 /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses 50 /// SDValue's instead of register numbers for the leaves of the matched 51 /// tree. 52 struct X86ISelAddressMode { 53 enum { 54 RegBase, 55 FrameIndexBase 56 } BaseType; 57 58 // This is really a union, discriminated by BaseType! 59 SDValue Base_Reg; 60 int Base_FrameIndex; 61 62 unsigned Scale; 63 SDValue IndexReg; 64 int32_t Disp; 65 SDValue Segment; 66 const GlobalValue *GV; 67 const Constant *CP; 68 const BlockAddress *BlockAddr; 69 const char *ES; 70 int JT; 71 unsigned Align; // CP alignment. 72 unsigned char SymbolFlags; // X86II::MO_* 73 74 X86ISelAddressMode() 75 : BaseType(RegBase), Base_FrameIndex(0), Scale(1), IndexReg(), Disp(0), 76 Segment(), GV(0), CP(0), BlockAddr(0), ES(0), JT(-1), Align(0), 77 SymbolFlags(X86II::MO_NO_FLAG) { 78 } 79 80 bool hasSymbolicDisplacement() const { 81 return GV != 0 || CP != 0 || ES != 0 || JT != -1 || BlockAddr != 0; 82 } 83 84 bool hasBaseOrIndexReg() const { 85 return IndexReg.getNode() != 0 || Base_Reg.getNode() != 0; 86 } 87 88 /// isRIPRelative - Return true if this addressing mode is already RIP 89 /// relative. 90 bool isRIPRelative() const { 91 if (BaseType != RegBase) return false; 92 if (RegisterSDNode *RegNode = 93 dyn_cast_or_null<RegisterSDNode>(Base_Reg.getNode())) 94 return RegNode->getReg() == X86::RIP; 95 return false; 96 } 97 98 void setBaseReg(SDValue Reg) { 99 BaseType = RegBase; 100 Base_Reg = Reg; 101 } 102 103 void dump() { 104 dbgs() << "X86ISelAddressMode " << this << '\n'; 105 dbgs() << "Base_Reg "; 106 if (Base_Reg.getNode() != 0) 107 Base_Reg.getNode()->dump(); 108 else 109 dbgs() << "nul"; 110 dbgs() << " Base.FrameIndex " << Base_FrameIndex << '\n' 111 << " Scale" << Scale << '\n' 112 << "IndexReg "; 113 if (IndexReg.getNode() != 0) 114 IndexReg.getNode()->dump(); 115 else 116 dbgs() << "nul"; 117 dbgs() << " Disp " << Disp << '\n' 118 << "GV "; 119 if (GV) 120 GV->dump(); 121 else 122 dbgs() << "nul"; 123 dbgs() << " CP "; 124 if (CP) 125 CP->dump(); 126 else 127 dbgs() << "nul"; 128 dbgs() << '\n' 129 << "ES "; 130 if (ES) 131 dbgs() << ES; 132 else 133 dbgs() << "nul"; 134 dbgs() << " JT" << JT << " Align" << Align << '\n'; 135 } 136 }; 137} 138 139namespace { 140 //===--------------------------------------------------------------------===// 141 /// ISel - X86 specific code to select X86 machine instructions for 142 /// SelectionDAG operations. 143 /// 144 class X86DAGToDAGISel : public SelectionDAGISel { 145 /// X86Lowering - This object fully describes how to lower LLVM code to an 146 /// X86-specific SelectionDAG. 147 const X86TargetLowering &X86Lowering; 148 149 /// Subtarget - Keep a pointer to the X86Subtarget around so that we can 150 /// make the right decision when generating code for different targets. 151 const X86Subtarget *Subtarget; 152 153 /// OptForSize - If true, selector should try to optimize for code size 154 /// instead of performance. 155 bool OptForSize; 156 157 public: 158 explicit X86DAGToDAGISel(X86TargetMachine &tm, CodeGenOpt::Level OptLevel) 159 : SelectionDAGISel(tm, OptLevel), 160 X86Lowering(*tm.getTargetLowering()), 161 Subtarget(&tm.getSubtarget<X86Subtarget>()), 162 OptForSize(false) {} 163 164 virtual const char *getPassName() const { 165 return "X86 DAG->DAG Instruction Selection"; 166 } 167 168 virtual void EmitFunctionEntryCode(); 169 170 virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const; 171 172 virtual void PreprocessISelDAG(); 173 174 inline bool immSext8(SDNode *N) const { 175 return isInt<8>(cast<ConstantSDNode>(N)->getSExtValue()); 176 } 177 178 // i64immSExt32 predicate - True if the 64-bit immediate fits in a 32-bit 179 // sign extended field. 180 inline bool i64immSExt32(SDNode *N) const { 181 uint64_t v = cast<ConstantSDNode>(N)->getZExtValue(); 182 return (int64_t)v == (int32_t)v; 183 } 184 185// Include the pieces autogenerated from the target description. 186#include "X86GenDAGISel.inc" 187 188 private: 189 SDNode *Select(SDNode *N); 190 SDNode *SelectAtomic64(SDNode *Node, unsigned Opc); 191 SDNode *SelectAtomicLoadAdd(SDNode *Node, EVT NVT); 192 193 bool MatchLoadInAddress(LoadSDNode *N, X86ISelAddressMode &AM); 194 bool MatchWrapper(SDValue N, X86ISelAddressMode &AM); 195 bool MatchAddress(SDValue N, X86ISelAddressMode &AM); 196 bool MatchAddressRecursively(SDValue N, X86ISelAddressMode &AM, 197 unsigned Depth); 198 bool MatchAddressBase(SDValue N, X86ISelAddressMode &AM); 199 bool SelectAddr(SDNode *Parent, SDValue N, SDValue &Base, 200 SDValue &Scale, SDValue &Index, SDValue &Disp, 201 SDValue &Segment); 202 bool SelectLEAAddr(SDValue N, SDValue &Base, 203 SDValue &Scale, SDValue &Index, SDValue &Disp, 204 SDValue &Segment); 205 bool SelectTLSADDRAddr(SDValue N, SDValue &Base, 206 SDValue &Scale, SDValue &Index, SDValue &Disp, 207 SDValue &Segment); 208 bool SelectScalarSSELoad(SDNode *Root, SDValue N, 209 SDValue &Base, SDValue &Scale, 210 SDValue &Index, SDValue &Disp, 211 SDValue &Segment, 212 SDValue &NodeWithChain); 213 214 bool TryFoldLoad(SDNode *P, SDValue N, 215 SDValue &Base, SDValue &Scale, 216 SDValue &Index, SDValue &Disp, 217 SDValue &Segment); 218 219 /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for 220 /// inline asm expressions. 221 virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op, 222 char ConstraintCode, 223 std::vector<SDValue> &OutOps); 224 225 void EmitSpecialCodeForMain(MachineBasicBlock *BB, MachineFrameInfo *MFI); 226 227 inline void getAddressOperands(X86ISelAddressMode &AM, SDValue &Base, 228 SDValue &Scale, SDValue &Index, 229 SDValue &Disp, SDValue &Segment) { 230 Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ? 231 CurDAG->getTargetFrameIndex(AM.Base_FrameIndex, TLI.getPointerTy()) : 232 AM.Base_Reg; 233 Scale = getI8Imm(AM.Scale); 234 Index = AM.IndexReg; 235 // These are 32-bit even in 64-bit mode since RIP relative offset 236 // is 32-bit. 237 if (AM.GV) 238 Disp = CurDAG->getTargetGlobalAddress(AM.GV, DebugLoc(), 239 MVT::i32, AM.Disp, 240 AM.SymbolFlags); 241 else if (AM.CP) 242 Disp = CurDAG->getTargetConstantPool(AM.CP, MVT::i32, 243 AM.Align, AM.Disp, AM.SymbolFlags); 244 else if (AM.ES) 245 Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i32, AM.SymbolFlags); 246 else if (AM.JT != -1) 247 Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i32, AM.SymbolFlags); 248 else if (AM.BlockAddr) 249 Disp = CurDAG->getBlockAddress(AM.BlockAddr, MVT::i32, 250 true, AM.SymbolFlags); 251 else 252 Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i32); 253 254 if (AM.Segment.getNode()) 255 Segment = AM.Segment; 256 else 257 Segment = CurDAG->getRegister(0, MVT::i32); 258 } 259 260 /// getI8Imm - Return a target constant with the specified value, of type 261 /// i8. 262 inline SDValue getI8Imm(unsigned Imm) { 263 return CurDAG->getTargetConstant(Imm, MVT::i8); 264 } 265 266 /// getI32Imm - Return a target constant with the specified value, of type 267 /// i32. 268 inline SDValue getI32Imm(unsigned Imm) { 269 return CurDAG->getTargetConstant(Imm, MVT::i32); 270 } 271 272 /// getGlobalBaseReg - Return an SDNode that returns the value of 273 /// the global base register. Output instructions required to 274 /// initialize the global base register, if necessary. 275 /// 276 SDNode *getGlobalBaseReg(); 277 278 /// getTargetMachine - Return a reference to the TargetMachine, casted 279 /// to the target-specific type. 280 const X86TargetMachine &getTargetMachine() { 281 return static_cast<const X86TargetMachine &>(TM); 282 } 283 284 /// getInstrInfo - Return a reference to the TargetInstrInfo, casted 285 /// to the target-specific type. 286 const X86InstrInfo *getInstrInfo() { 287 return getTargetMachine().getInstrInfo(); 288 } 289 }; 290} 291 292 293bool 294X86DAGToDAGISel::IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const { 295 if (OptLevel == CodeGenOpt::None) return false; 296 297 if (!N.hasOneUse()) 298 return false; 299 300 if (N.getOpcode() != ISD::LOAD) 301 return true; 302 303 // If N is a load, do additional profitability checks. 304 if (U == Root) { 305 switch (U->getOpcode()) { 306 default: break; 307 case X86ISD::ADD: 308 case X86ISD::SUB: 309 case X86ISD::AND: 310 case X86ISD::XOR: 311 case X86ISD::OR: 312 case ISD::ADD: 313 case ISD::ADDC: 314 case ISD::ADDE: 315 case ISD::AND: 316 case ISD::OR: 317 case ISD::XOR: { 318 SDValue Op1 = U->getOperand(1); 319 320 // If the other operand is a 8-bit immediate we should fold the immediate 321 // instead. This reduces code size. 322 // e.g. 323 // movl 4(%esp), %eax 324 // addl $4, %eax 325 // vs. 326 // movl $4, %eax 327 // addl 4(%esp), %eax 328 // The former is 2 bytes shorter. In case where the increment is 1, then 329 // the saving can be 4 bytes (by using incl %eax). 330 if (ConstantSDNode *Imm = dyn_cast<ConstantSDNode>(Op1)) 331 if (Imm->getAPIntValue().isSignedIntN(8)) 332 return false; 333 334 // If the other operand is a TLS address, we should fold it instead. 335 // This produces 336 // movl %gs:0, %eax 337 // leal i@NTPOFF(%eax), %eax 338 // instead of 339 // movl $i@NTPOFF, %eax 340 // addl %gs:0, %eax 341 // if the block also has an access to a second TLS address this will save 342 // a load. 343 // FIXME: This is probably also true for non TLS addresses. 344 if (Op1.getOpcode() == X86ISD::Wrapper) { 345 SDValue Val = Op1.getOperand(0); 346 if (Val.getOpcode() == ISD::TargetGlobalTLSAddress) 347 return false; 348 } 349 } 350 } 351 } 352 353 return true; 354} 355 356/// MoveBelowCallOrigChain - Replace the original chain operand of the call with 357/// load's chain operand and move load below the call's chain operand. 358static void MoveBelowOrigChain(SelectionDAG *CurDAG, SDValue Load, 359 SDValue Call, SDValue OrigChain) { 360 SmallVector<SDValue, 8> Ops; 361 SDValue Chain = OrigChain.getOperand(0); 362 if (Chain.getNode() == Load.getNode()) 363 Ops.push_back(Load.getOperand(0)); 364 else { 365 assert(Chain.getOpcode() == ISD::TokenFactor && 366 "Unexpected chain operand"); 367 for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i) 368 if (Chain.getOperand(i).getNode() == Load.getNode()) 369 Ops.push_back(Load.getOperand(0)); 370 else 371 Ops.push_back(Chain.getOperand(i)); 372 SDValue NewChain = 373 CurDAG->getNode(ISD::TokenFactor, Load.getDebugLoc(), 374 MVT::Other, &Ops[0], Ops.size()); 375 Ops.clear(); 376 Ops.push_back(NewChain); 377 } 378 for (unsigned i = 1, e = OrigChain.getNumOperands(); i != e; ++i) 379 Ops.push_back(OrigChain.getOperand(i)); 380 CurDAG->UpdateNodeOperands(OrigChain.getNode(), &Ops[0], Ops.size()); 381 CurDAG->UpdateNodeOperands(Load.getNode(), Call.getOperand(0), 382 Load.getOperand(1), Load.getOperand(2)); 383 Ops.clear(); 384 Ops.push_back(SDValue(Load.getNode(), 1)); 385 for (unsigned i = 1, e = Call.getNode()->getNumOperands(); i != e; ++i) 386 Ops.push_back(Call.getOperand(i)); 387 CurDAG->UpdateNodeOperands(Call.getNode(), &Ops[0], Ops.size()); 388} 389 390/// isCalleeLoad - Return true if call address is a load and it can be 391/// moved below CALLSEQ_START and the chains leading up to the call. 392/// Return the CALLSEQ_START by reference as a second output. 393/// In the case of a tail call, there isn't a callseq node between the call 394/// chain and the load. 395static bool isCalleeLoad(SDValue Callee, SDValue &Chain, bool HasCallSeq) { 396 if (Callee.getNode() == Chain.getNode() || !Callee.hasOneUse()) 397 return false; 398 LoadSDNode *LD = dyn_cast<LoadSDNode>(Callee.getNode()); 399 if (!LD || 400 LD->isVolatile() || 401 LD->getAddressingMode() != ISD::UNINDEXED || 402 LD->getExtensionType() != ISD::NON_EXTLOAD) 403 return false; 404 405 // Now let's find the callseq_start. 406 while (HasCallSeq && Chain.getOpcode() != ISD::CALLSEQ_START) { 407 if (!Chain.hasOneUse()) 408 return false; 409 Chain = Chain.getOperand(0); 410 } 411 412 if (!Chain.getNumOperands()) 413 return false; 414 if (Chain.getOperand(0).getNode() == Callee.getNode()) 415 return true; 416 if (Chain.getOperand(0).getOpcode() == ISD::TokenFactor && 417 Callee.getValue(1).isOperandOf(Chain.getOperand(0).getNode()) && 418 Callee.getValue(1).hasOneUse()) 419 return true; 420 return false; 421} 422 423void X86DAGToDAGISel::PreprocessISelDAG() { 424 // OptForSize is used in pattern predicates that isel is matching. 425 OptForSize = MF->getFunction()->hasFnAttr(Attribute::OptimizeForSize); 426 427 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(), 428 E = CurDAG->allnodes_end(); I != E; ) { 429 SDNode *N = I++; // Preincrement iterator to avoid invalidation issues. 430 431 if (OptLevel != CodeGenOpt::None && 432 (N->getOpcode() == X86ISD::CALL || 433 N->getOpcode() == X86ISD::TC_RETURN)) { 434 /// Also try moving call address load from outside callseq_start to just 435 /// before the call to allow it to be folded. 436 /// 437 /// [Load chain] 438 /// ^ 439 /// | 440 /// [Load] 441 /// ^ ^ 442 /// | | 443 /// / \-- 444 /// / | 445 ///[CALLSEQ_START] | 446 /// ^ | 447 /// | | 448 /// [LOAD/C2Reg] | 449 /// | | 450 /// \ / 451 /// \ / 452 /// [CALL] 453 bool HasCallSeq = N->getOpcode() == X86ISD::CALL; 454 SDValue Chain = N->getOperand(0); 455 SDValue Load = N->getOperand(1); 456 if (!isCalleeLoad(Load, Chain, HasCallSeq)) 457 continue; 458 MoveBelowOrigChain(CurDAG, Load, SDValue(N, 0), Chain); 459 ++NumLoadMoved; 460 continue; 461 } 462 463 // Lower fpround and fpextend nodes that target the FP stack to be store and 464 // load to the stack. This is a gross hack. We would like to simply mark 465 // these as being illegal, but when we do that, legalize produces these when 466 // it expands calls, then expands these in the same legalize pass. We would 467 // like dag combine to be able to hack on these between the call expansion 468 // and the node legalization. As such this pass basically does "really 469 // late" legalization of these inline with the X86 isel pass. 470 // FIXME: This should only happen when not compiled with -O0. 471 if (N->getOpcode() != ISD::FP_ROUND && N->getOpcode() != ISD::FP_EXTEND) 472 continue; 473 474 // If the source and destination are SSE registers, then this is a legal 475 // conversion that should not be lowered. 476 EVT SrcVT = N->getOperand(0).getValueType(); 477 EVT DstVT = N->getValueType(0); 478 bool SrcIsSSE = X86Lowering.isScalarFPTypeInSSEReg(SrcVT); 479 bool DstIsSSE = X86Lowering.isScalarFPTypeInSSEReg(DstVT); 480 if (SrcIsSSE && DstIsSSE) 481 continue; 482 483 if (!SrcIsSSE && !DstIsSSE) { 484 // If this is an FPStack extension, it is a noop. 485 if (N->getOpcode() == ISD::FP_EXTEND) 486 continue; 487 // If this is a value-preserving FPStack truncation, it is a noop. 488 if (N->getConstantOperandVal(1)) 489 continue; 490 } 491 492 // Here we could have an FP stack truncation or an FPStack <-> SSE convert. 493 // FPStack has extload and truncstore. SSE can fold direct loads into other 494 // operations. Based on this, decide what we want to do. 495 EVT MemVT; 496 if (N->getOpcode() == ISD::FP_ROUND) 497 MemVT = DstVT; // FP_ROUND must use DstVT, we can't do a 'trunc load'. 498 else 499 MemVT = SrcIsSSE ? SrcVT : DstVT; 500 501 SDValue MemTmp = CurDAG->CreateStackTemporary(MemVT); 502 DebugLoc dl = N->getDebugLoc(); 503 504 // FIXME: optimize the case where the src/dest is a load or store? 505 SDValue Store = CurDAG->getTruncStore(CurDAG->getEntryNode(), dl, 506 N->getOperand(0), 507 MemTmp, MachinePointerInfo(), MemVT, 508 false, false, 0); 509 SDValue Result = CurDAG->getExtLoad(ISD::EXTLOAD, dl, DstVT, Store, MemTmp, 510 MachinePointerInfo(), 511 MemVT, false, false, 0); 512 513 // We're about to replace all uses of the FP_ROUND/FP_EXTEND with the 514 // extload we created. This will cause general havok on the dag because 515 // anything below the conversion could be folded into other existing nodes. 516 // To avoid invalidating 'I', back it up to the convert node. 517 --I; 518 CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Result); 519 520 // Now that we did that, the node is dead. Increment the iterator to the 521 // next node to process, then delete N. 522 ++I; 523 CurDAG->DeleteNode(N); 524 } 525} 526 527 528/// EmitSpecialCodeForMain - Emit any code that needs to be executed only in 529/// the main function. 530void X86DAGToDAGISel::EmitSpecialCodeForMain(MachineBasicBlock *BB, 531 MachineFrameInfo *MFI) { 532 const TargetInstrInfo *TII = TM.getInstrInfo(); 533 if (Subtarget->isTargetCygMing()) { 534 unsigned CallOp = 535 Subtarget->is64Bit() ? X86::WINCALL64pcrel32 : X86::CALLpcrel32; 536 BuildMI(BB, DebugLoc(), 537 TII->get(CallOp)).addExternalSymbol("__main"); 538 } 539} 540 541void X86DAGToDAGISel::EmitFunctionEntryCode() { 542 // If this is main, emit special code for main. 543 if (const Function *Fn = MF->getFunction()) 544 if (Fn->hasExternalLinkage() && Fn->getName() == "main") 545 EmitSpecialCodeForMain(MF->begin(), MF->getFrameInfo()); 546} 547 548 549bool X86DAGToDAGISel::MatchLoadInAddress(LoadSDNode *N, X86ISelAddressMode &AM){ 550 SDValue Address = N->getOperand(1); 551 552 // load gs:0 -> GS segment register. 553 // load fs:0 -> FS segment register. 554 // 555 // This optimization is valid because the GNU TLS model defines that 556 // gs:0 (or fs:0 on X86-64) contains its own address. 557 // For more information see http://people.redhat.com/drepper/tls.pdf 558 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Address)) 559 if (C->getSExtValue() == 0 && AM.Segment.getNode() == 0 && 560 Subtarget->isTargetELF()) 561 switch (N->getPointerInfo().getAddrSpace()) { 562 case 256: 563 AM.Segment = CurDAG->getRegister(X86::GS, MVT::i16); 564 return false; 565 case 257: 566 AM.Segment = CurDAG->getRegister(X86::FS, MVT::i16); 567 return false; 568 } 569 570 return true; 571} 572 573/// MatchWrapper - Try to match X86ISD::Wrapper and X86ISD::WrapperRIP nodes 574/// into an addressing mode. These wrap things that will resolve down into a 575/// symbol reference. If no match is possible, this returns true, otherwise it 576/// returns false. 577bool X86DAGToDAGISel::MatchWrapper(SDValue N, X86ISelAddressMode &AM) { 578 // If the addressing mode already has a symbol as the displacement, we can 579 // never match another symbol. 580 if (AM.hasSymbolicDisplacement()) 581 return true; 582 583 SDValue N0 = N.getOperand(0); 584 CodeModel::Model M = TM.getCodeModel(); 585 586 // Handle X86-64 rip-relative addresses. We check this before checking direct 587 // folding because RIP is preferable to non-RIP accesses. 588 if (Subtarget->is64Bit() && 589 // Under X86-64 non-small code model, GV (and friends) are 64-bits, so 590 // they cannot be folded into immediate fields. 591 // FIXME: This can be improved for kernel and other models? 592 (M == CodeModel::Small || M == CodeModel::Kernel) && 593 // Base and index reg must be 0 in order to use %rip as base and lowering 594 // must allow RIP. 595 !AM.hasBaseOrIndexReg() && N.getOpcode() == X86ISD::WrapperRIP) { 596 if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) { 597 int64_t Offset = AM.Disp + G->getOffset(); 598 if (!X86::isOffsetSuitableForCodeModel(Offset, M)) return true; 599 AM.GV = G->getGlobal(); 600 AM.Disp = Offset; 601 AM.SymbolFlags = G->getTargetFlags(); 602 } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) { 603 int64_t Offset = AM.Disp + CP->getOffset(); 604 if (!X86::isOffsetSuitableForCodeModel(Offset, M)) return true; 605 AM.CP = CP->getConstVal(); 606 AM.Align = CP->getAlignment(); 607 AM.Disp = Offset; 608 AM.SymbolFlags = CP->getTargetFlags(); 609 } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) { 610 AM.ES = S->getSymbol(); 611 AM.SymbolFlags = S->getTargetFlags(); 612 } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) { 613 AM.JT = J->getIndex(); 614 AM.SymbolFlags = J->getTargetFlags(); 615 } else { 616 AM.BlockAddr = cast<BlockAddressSDNode>(N0)->getBlockAddress(); 617 AM.SymbolFlags = cast<BlockAddressSDNode>(N0)->getTargetFlags(); 618 } 619 620 if (N.getOpcode() == X86ISD::WrapperRIP) 621 AM.setBaseReg(CurDAG->getRegister(X86::RIP, MVT::i64)); 622 return false; 623 } 624 625 // Handle the case when globals fit in our immediate field: This is true for 626 // X86-32 always and X86-64 when in -static -mcmodel=small mode. In 64-bit 627 // mode, this results in a non-RIP-relative computation. 628 if (!Subtarget->is64Bit() || 629 ((M == CodeModel::Small || M == CodeModel::Kernel) && 630 TM.getRelocationModel() == Reloc::Static)) { 631 if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) { 632 AM.GV = G->getGlobal(); 633 AM.Disp += G->getOffset(); 634 AM.SymbolFlags = G->getTargetFlags(); 635 } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) { 636 AM.CP = CP->getConstVal(); 637 AM.Align = CP->getAlignment(); 638 AM.Disp += CP->getOffset(); 639 AM.SymbolFlags = CP->getTargetFlags(); 640 } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) { 641 AM.ES = S->getSymbol(); 642 AM.SymbolFlags = S->getTargetFlags(); 643 } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) { 644 AM.JT = J->getIndex(); 645 AM.SymbolFlags = J->getTargetFlags(); 646 } else { 647 AM.BlockAddr = cast<BlockAddressSDNode>(N0)->getBlockAddress(); 648 AM.SymbolFlags = cast<BlockAddressSDNode>(N0)->getTargetFlags(); 649 } 650 return false; 651 } 652 653 return true; 654} 655 656/// MatchAddress - Add the specified node to the specified addressing mode, 657/// returning true if it cannot be done. This just pattern matches for the 658/// addressing mode. 659bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM) { 660 if (MatchAddressRecursively(N, AM, 0)) 661 return true; 662 663 // Post-processing: Convert lea(,%reg,2) to lea(%reg,%reg), which has 664 // a smaller encoding and avoids a scaled-index. 665 if (AM.Scale == 2 && 666 AM.BaseType == X86ISelAddressMode::RegBase && 667 AM.Base_Reg.getNode() == 0) { 668 AM.Base_Reg = AM.IndexReg; 669 AM.Scale = 1; 670 } 671 672 // Post-processing: Convert foo to foo(%rip), even in non-PIC mode, 673 // because it has a smaller encoding. 674 // TODO: Which other code models can use this? 675 if (TM.getCodeModel() == CodeModel::Small && 676 Subtarget->is64Bit() && 677 AM.Scale == 1 && 678 AM.BaseType == X86ISelAddressMode::RegBase && 679 AM.Base_Reg.getNode() == 0 && 680 AM.IndexReg.getNode() == 0 && 681 AM.SymbolFlags == X86II::MO_NO_FLAG && 682 AM.hasSymbolicDisplacement()) 683 AM.Base_Reg = CurDAG->getRegister(X86::RIP, MVT::i64); 684 685 return false; 686} 687 688bool X86DAGToDAGISel::MatchAddressRecursively(SDValue N, X86ISelAddressMode &AM, 689 unsigned Depth) { 690 bool is64Bit = Subtarget->is64Bit(); 691 DebugLoc dl = N.getDebugLoc(); 692 DEBUG({ 693 dbgs() << "MatchAddress: "; 694 AM.dump(); 695 }); 696 // Limit recursion. 697 if (Depth > 5) 698 return MatchAddressBase(N, AM); 699 700 CodeModel::Model M = TM.getCodeModel(); 701 702 // If this is already a %rip relative address, we can only merge immediates 703 // into it. Instead of handling this in every case, we handle it here. 704 // RIP relative addressing: %rip + 32-bit displacement! 705 if (AM.isRIPRelative()) { 706 // FIXME: JumpTable and ExternalSymbol address currently don't like 707 // displacements. It isn't very important, but this should be fixed for 708 // consistency. 709 if (!AM.ES && AM.JT != -1) return true; 710 711 if (ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N)) { 712 int64_t Val = AM.Disp + Cst->getSExtValue(); 713 if (X86::isOffsetSuitableForCodeModel(Val, M, 714 AM.hasSymbolicDisplacement())) { 715 AM.Disp = Val; 716 return false; 717 } 718 } 719 return true; 720 } 721 722 switch (N.getOpcode()) { 723 default: break; 724 case ISD::Constant: { 725 uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue(); 726 if (!is64Bit || 727 X86::isOffsetSuitableForCodeModel(AM.Disp + Val, M, 728 AM.hasSymbolicDisplacement())) { 729 AM.Disp += Val; 730 return false; 731 } 732 break; 733 } 734 735 case X86ISD::Wrapper: 736 case X86ISD::WrapperRIP: 737 if (!MatchWrapper(N, AM)) 738 return false; 739 break; 740 741 case ISD::LOAD: 742 if (!MatchLoadInAddress(cast<LoadSDNode>(N), AM)) 743 return false; 744 break; 745 746 case ISD::FrameIndex: 747 if (AM.BaseType == X86ISelAddressMode::RegBase 748 && AM.Base_Reg.getNode() == 0) { 749 AM.BaseType = X86ISelAddressMode::FrameIndexBase; 750 AM.Base_FrameIndex = cast<FrameIndexSDNode>(N)->getIndex(); 751 return false; 752 } 753 break; 754 755 case ISD::SHL: 756 if (AM.IndexReg.getNode() != 0 || AM.Scale != 1) 757 break; 758 759 if (ConstantSDNode 760 *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1))) { 761 unsigned Val = CN->getZExtValue(); 762 // Note that we handle x<<1 as (,x,2) rather than (x,x) here so 763 // that the base operand remains free for further matching. If 764 // the base doesn't end up getting used, a post-processing step 765 // in MatchAddress turns (,x,2) into (x,x), which is cheaper. 766 if (Val == 1 || Val == 2 || Val == 3) { 767 AM.Scale = 1 << Val; 768 SDValue ShVal = N.getNode()->getOperand(0); 769 770 // Okay, we know that we have a scale by now. However, if the scaled 771 // value is an add of something and a constant, we can fold the 772 // constant into the disp field here. 773 if (CurDAG->isBaseWithConstantOffset(ShVal)) { 774 AM.IndexReg = ShVal.getNode()->getOperand(0); 775 ConstantSDNode *AddVal = 776 cast<ConstantSDNode>(ShVal.getNode()->getOperand(1)); 777 uint64_t Disp = AM.Disp + (AddVal->getSExtValue() << Val); 778 if (!is64Bit || 779 X86::isOffsetSuitableForCodeModel(Disp, M, 780 AM.hasSymbolicDisplacement())) 781 AM.Disp = Disp; 782 else 783 AM.IndexReg = ShVal; 784 } else { 785 AM.IndexReg = ShVal; 786 } 787 return false; 788 } 789 break; 790 } 791 792 case ISD::SMUL_LOHI: 793 case ISD::UMUL_LOHI: 794 // A mul_lohi where we need the low part can be folded as a plain multiply. 795 if (N.getResNo() != 0) break; 796 // FALL THROUGH 797 case ISD::MUL: 798 case X86ISD::MUL_IMM: 799 // X*[3,5,9] -> X+X*[2,4,8] 800 if (AM.BaseType == X86ISelAddressMode::RegBase && 801 AM.Base_Reg.getNode() == 0 && 802 AM.IndexReg.getNode() == 0) { 803 if (ConstantSDNode 804 *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1))) 805 if (CN->getZExtValue() == 3 || CN->getZExtValue() == 5 || 806 CN->getZExtValue() == 9) { 807 AM.Scale = unsigned(CN->getZExtValue())-1; 808 809 SDValue MulVal = N.getNode()->getOperand(0); 810 SDValue Reg; 811 812 // Okay, we know that we have a scale by now. However, if the scaled 813 // value is an add of something and a constant, we can fold the 814 // constant into the disp field here. 815 if (MulVal.getNode()->getOpcode() == ISD::ADD && MulVal.hasOneUse() && 816 isa<ConstantSDNode>(MulVal.getNode()->getOperand(1))) { 817 Reg = MulVal.getNode()->getOperand(0); 818 ConstantSDNode *AddVal = 819 cast<ConstantSDNode>(MulVal.getNode()->getOperand(1)); 820 uint64_t Disp = AM.Disp + AddVal->getSExtValue() * 821 CN->getZExtValue(); 822 if (!is64Bit || 823 X86::isOffsetSuitableForCodeModel(Disp, M, 824 AM.hasSymbolicDisplacement())) 825 AM.Disp = Disp; 826 else 827 Reg = N.getNode()->getOperand(0); 828 } else { 829 Reg = N.getNode()->getOperand(0); 830 } 831 832 AM.IndexReg = AM.Base_Reg = Reg; 833 return false; 834 } 835 } 836 break; 837 838 case ISD::SUB: { 839 // Given A-B, if A can be completely folded into the address and 840 // the index field with the index field unused, use -B as the index. 841 // This is a win if a has multiple parts that can be folded into 842 // the address. Also, this saves a mov if the base register has 843 // other uses, since it avoids a two-address sub instruction, however 844 // it costs an additional mov if the index register has other uses. 845 846 // Add an artificial use to this node so that we can keep track of 847 // it if it gets CSE'd with a different node. 848 HandleSDNode Handle(N); 849 850 // Test if the LHS of the sub can be folded. 851 X86ISelAddressMode Backup = AM; 852 if (MatchAddressRecursively(N.getNode()->getOperand(0), AM, Depth+1)) { 853 AM = Backup; 854 break; 855 } 856 // Test if the index field is free for use. 857 if (AM.IndexReg.getNode() || AM.isRIPRelative()) { 858 AM = Backup; 859 break; 860 } 861 862 int Cost = 0; 863 SDValue RHS = Handle.getValue().getNode()->getOperand(1); 864 // If the RHS involves a register with multiple uses, this 865 // transformation incurs an extra mov, due to the neg instruction 866 // clobbering its operand. 867 if (!RHS.getNode()->hasOneUse() || 868 RHS.getNode()->getOpcode() == ISD::CopyFromReg || 869 RHS.getNode()->getOpcode() == ISD::TRUNCATE || 870 RHS.getNode()->getOpcode() == ISD::ANY_EXTEND || 871 (RHS.getNode()->getOpcode() == ISD::ZERO_EXTEND && 872 RHS.getNode()->getOperand(0).getValueType() == MVT::i32)) 873 ++Cost; 874 // If the base is a register with multiple uses, this 875 // transformation may save a mov. 876 if ((AM.BaseType == X86ISelAddressMode::RegBase && 877 AM.Base_Reg.getNode() && 878 !AM.Base_Reg.getNode()->hasOneUse()) || 879 AM.BaseType == X86ISelAddressMode::FrameIndexBase) 880 --Cost; 881 // If the folded LHS was interesting, this transformation saves 882 // address arithmetic. 883 if ((AM.hasSymbolicDisplacement() && !Backup.hasSymbolicDisplacement()) + 884 ((AM.Disp != 0) && (Backup.Disp == 0)) + 885 (AM.Segment.getNode() && !Backup.Segment.getNode()) >= 2) 886 --Cost; 887 // If it doesn't look like it may be an overall win, don't do it. 888 if (Cost >= 0) { 889 AM = Backup; 890 break; 891 } 892 893 // Ok, the transformation is legal and appears profitable. Go for it. 894 SDValue Zero = CurDAG->getConstant(0, N.getValueType()); 895 SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS); 896 AM.IndexReg = Neg; 897 AM.Scale = 1; 898 899 // Insert the new nodes into the topological ordering. 900 if (Zero.getNode()->getNodeId() == -1 || 901 Zero.getNode()->getNodeId() > N.getNode()->getNodeId()) { 902 CurDAG->RepositionNode(N.getNode(), Zero.getNode()); 903 Zero.getNode()->setNodeId(N.getNode()->getNodeId()); 904 } 905 if (Neg.getNode()->getNodeId() == -1 || 906 Neg.getNode()->getNodeId() > N.getNode()->getNodeId()) { 907 CurDAG->RepositionNode(N.getNode(), Neg.getNode()); 908 Neg.getNode()->setNodeId(N.getNode()->getNodeId()); 909 } 910 return false; 911 } 912 913 case ISD::ADD: { 914 // Add an artificial use to this node so that we can keep track of 915 // it if it gets CSE'd with a different node. 916 HandleSDNode Handle(N); 917 918 X86ISelAddressMode Backup = AM; 919 if (!MatchAddressRecursively(N.getOperand(0), AM, Depth+1) && 920 !MatchAddressRecursively(Handle.getValue().getOperand(1), AM, Depth+1)) 921 return false; 922 AM = Backup; 923 924 // Try again after commuting the operands. 925 if (!MatchAddressRecursively(Handle.getValue().getOperand(1), AM, Depth+1)&& 926 !MatchAddressRecursively(Handle.getValue().getOperand(0), AM, Depth+1)) 927 return false; 928 AM = Backup; 929 930 // If we couldn't fold both operands into the address at the same time, 931 // see if we can just put each operand into a register and fold at least 932 // the add. 933 if (AM.BaseType == X86ISelAddressMode::RegBase && 934 !AM.Base_Reg.getNode() && 935 !AM.IndexReg.getNode()) { 936 N = Handle.getValue(); 937 AM.Base_Reg = N.getOperand(0); 938 AM.IndexReg = N.getOperand(1); 939 AM.Scale = 1; 940 return false; 941 } 942 N = Handle.getValue(); 943 break; 944 } 945 946 case ISD::OR: 947 // Handle "X | C" as "X + C" iff X is known to have C bits clear. 948 if (CurDAG->isBaseWithConstantOffset(N)) { 949 X86ISelAddressMode Backup = AM; 950 ConstantSDNode *CN = cast<ConstantSDNode>(N.getOperand(1)); 951 uint64_t Offset = CN->getSExtValue(); 952 953 // Start with the LHS as an addr mode. 954 if (!MatchAddressRecursively(N.getOperand(0), AM, Depth+1) && 955 // Address could not have picked a GV address for the displacement. 956 AM.GV == NULL && 957 // On x86-64, the resultant disp must fit in 32-bits. 958 (!is64Bit || 959 X86::isOffsetSuitableForCodeModel(AM.Disp + Offset, M, 960 AM.hasSymbolicDisplacement()))) { 961 AM.Disp += Offset; 962 return false; 963 } 964 AM = Backup; 965 } 966 break; 967 968 case ISD::AND: { 969 // Perform some heroic transforms on an and of a constant-count shift 970 // with a constant to enable use of the scaled offset field. 971 972 SDValue Shift = N.getOperand(0); 973 if (Shift.getNumOperands() != 2) break; 974 975 // Scale must not be used already. 976 if (AM.IndexReg.getNode() != 0 || AM.Scale != 1) break; 977 978 SDValue X = Shift.getOperand(0); 979 ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(N.getOperand(1)); 980 ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Shift.getOperand(1)); 981 if (!C1 || !C2) break; 982 983 // Handle "(X >> (8-C1)) & C2" as "(X >> 8) & 0xff)" if safe. This 984 // allows us to convert the shift and and into an h-register extract and 985 // a scaled index. 986 if (Shift.getOpcode() == ISD::SRL && Shift.hasOneUse()) { 987 unsigned ScaleLog = 8 - C1->getZExtValue(); 988 if (ScaleLog > 0 && ScaleLog < 4 && 989 C2->getZExtValue() == (UINT64_C(0xff) << ScaleLog)) { 990 SDValue Eight = CurDAG->getConstant(8, MVT::i8); 991 SDValue Mask = CurDAG->getConstant(0xff, N.getValueType()); 992 SDValue Srl = CurDAG->getNode(ISD::SRL, dl, N.getValueType(), 993 X, Eight); 994 SDValue And = CurDAG->getNode(ISD::AND, dl, N.getValueType(), 995 Srl, Mask); 996 SDValue ShlCount = CurDAG->getConstant(ScaleLog, MVT::i8); 997 SDValue Shl = CurDAG->getNode(ISD::SHL, dl, N.getValueType(), 998 And, ShlCount); 999 1000 // Insert the new nodes into the topological ordering. 1001 if (Eight.getNode()->getNodeId() == -1 || 1002 Eight.getNode()->getNodeId() > X.getNode()->getNodeId()) { 1003 CurDAG->RepositionNode(X.getNode(), Eight.getNode()); 1004 Eight.getNode()->setNodeId(X.getNode()->getNodeId()); 1005 } 1006 if (Mask.getNode()->getNodeId() == -1 || 1007 Mask.getNode()->getNodeId() > X.getNode()->getNodeId()) { 1008 CurDAG->RepositionNode(X.getNode(), Mask.getNode()); 1009 Mask.getNode()->setNodeId(X.getNode()->getNodeId()); 1010 } 1011 if (Srl.getNode()->getNodeId() == -1 || 1012 Srl.getNode()->getNodeId() > Shift.getNode()->getNodeId()) { 1013 CurDAG->RepositionNode(Shift.getNode(), Srl.getNode()); 1014 Srl.getNode()->setNodeId(Shift.getNode()->getNodeId()); 1015 } 1016 if (And.getNode()->getNodeId() == -1 || 1017 And.getNode()->getNodeId() > N.getNode()->getNodeId()) { 1018 CurDAG->RepositionNode(N.getNode(), And.getNode()); 1019 And.getNode()->setNodeId(N.getNode()->getNodeId()); 1020 } 1021 if (ShlCount.getNode()->getNodeId() == -1 || 1022 ShlCount.getNode()->getNodeId() > X.getNode()->getNodeId()) { 1023 CurDAG->RepositionNode(X.getNode(), ShlCount.getNode()); 1024 ShlCount.getNode()->setNodeId(N.getNode()->getNodeId()); 1025 } 1026 if (Shl.getNode()->getNodeId() == -1 || 1027 Shl.getNode()->getNodeId() > N.getNode()->getNodeId()) { 1028 CurDAG->RepositionNode(N.getNode(), Shl.getNode()); 1029 Shl.getNode()->setNodeId(N.getNode()->getNodeId()); 1030 } 1031 CurDAG->ReplaceAllUsesWith(N, Shl); 1032 AM.IndexReg = And; 1033 AM.Scale = (1 << ScaleLog); 1034 return false; 1035 } 1036 } 1037 1038 // Handle "(X << C1) & C2" as "(X & (C2>>C1)) << C1" if safe and if this 1039 // allows us to fold the shift into this addressing mode. 1040 if (Shift.getOpcode() != ISD::SHL) break; 1041 1042 // Not likely to be profitable if either the AND or SHIFT node has more 1043 // than one use (unless all uses are for address computation). Besides, 1044 // isel mechanism requires their node ids to be reused. 1045 if (!N.hasOneUse() || !Shift.hasOneUse()) 1046 break; 1047 1048 // Verify that the shift amount is something we can fold. 1049 unsigned ShiftCst = C1->getZExtValue(); 1050 if (ShiftCst != 1 && ShiftCst != 2 && ShiftCst != 3) 1051 break; 1052 1053 // Get the new AND mask, this folds to a constant. 1054 SDValue NewANDMask = CurDAG->getNode(ISD::SRL, dl, N.getValueType(), 1055 SDValue(C2, 0), SDValue(C1, 0)); 1056 SDValue NewAND = CurDAG->getNode(ISD::AND, dl, N.getValueType(), X, 1057 NewANDMask); 1058 SDValue NewSHIFT = CurDAG->getNode(ISD::SHL, dl, N.getValueType(), 1059 NewAND, SDValue(C1, 0)); 1060 1061 // Insert the new nodes into the topological ordering. 1062 if (C1->getNodeId() > X.getNode()->getNodeId()) { 1063 CurDAG->RepositionNode(X.getNode(), C1); 1064 C1->setNodeId(X.getNode()->getNodeId()); 1065 } 1066 if (NewANDMask.getNode()->getNodeId() == -1 || 1067 NewANDMask.getNode()->getNodeId() > X.getNode()->getNodeId()) { 1068 CurDAG->RepositionNode(X.getNode(), NewANDMask.getNode()); 1069 NewANDMask.getNode()->setNodeId(X.getNode()->getNodeId()); 1070 } 1071 if (NewAND.getNode()->getNodeId() == -1 || 1072 NewAND.getNode()->getNodeId() > Shift.getNode()->getNodeId()) { 1073 CurDAG->RepositionNode(Shift.getNode(), NewAND.getNode()); 1074 NewAND.getNode()->setNodeId(Shift.getNode()->getNodeId()); 1075 } 1076 if (NewSHIFT.getNode()->getNodeId() == -1 || 1077 NewSHIFT.getNode()->getNodeId() > N.getNode()->getNodeId()) { 1078 CurDAG->RepositionNode(N.getNode(), NewSHIFT.getNode()); 1079 NewSHIFT.getNode()->setNodeId(N.getNode()->getNodeId()); 1080 } 1081 1082 CurDAG->ReplaceAllUsesWith(N, NewSHIFT); 1083 1084 AM.Scale = 1 << ShiftCst; 1085 AM.IndexReg = NewAND; 1086 return false; 1087 } 1088 } 1089 1090 return MatchAddressBase(N, AM); 1091} 1092 1093/// MatchAddressBase - Helper for MatchAddress. Add the specified node to the 1094/// specified addressing mode without any further recursion. 1095bool X86DAGToDAGISel::MatchAddressBase(SDValue N, X86ISelAddressMode &AM) { 1096 // Is the base register already occupied? 1097 if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base_Reg.getNode()) { 1098 // If so, check to see if the scale index register is set. 1099 if (AM.IndexReg.getNode() == 0) { 1100 AM.IndexReg = N; 1101 AM.Scale = 1; 1102 return false; 1103 } 1104 1105 // Otherwise, we cannot select it. 1106 return true; 1107 } 1108 1109 // Default, generate it as a register. 1110 AM.BaseType = X86ISelAddressMode::RegBase; 1111 AM.Base_Reg = N; 1112 return false; 1113} 1114 1115/// SelectAddr - returns true if it is able pattern match an addressing mode. 1116/// It returns the operands which make up the maximal addressing mode it can 1117/// match by reference. 1118/// 1119/// Parent is the parent node of the addr operand that is being matched. It 1120/// is always a load, store, atomic node, or null. It is only null when 1121/// checking memory operands for inline asm nodes. 1122bool X86DAGToDAGISel::SelectAddr(SDNode *Parent, SDValue N, SDValue &Base, 1123 SDValue &Scale, SDValue &Index, 1124 SDValue &Disp, SDValue &Segment) { 1125 X86ISelAddressMode AM; 1126 1127 if (Parent && 1128 // This list of opcodes are all the nodes that have an "addr:$ptr" operand 1129 // that are not a MemSDNode, and thus don't have proper addrspace info. 1130 Parent->getOpcode() != ISD::INTRINSIC_W_CHAIN && // unaligned loads, fixme 1131 Parent->getOpcode() != ISD::INTRINSIC_VOID && // nontemporal stores 1132 Parent->getOpcode() != X86ISD::TLSCALL) { // Fixme 1133 unsigned AddrSpace = 1134 cast<MemSDNode>(Parent)->getPointerInfo().getAddrSpace(); 1135 // AddrSpace 256 -> GS, 257 -> FS. 1136 if (AddrSpace == 256) 1137 AM.Segment = CurDAG->getRegister(X86::GS, MVT::i16); 1138 if (AddrSpace == 257) 1139 AM.Segment = CurDAG->getRegister(X86::FS, MVT::i16); 1140 } 1141 1142 if (MatchAddress(N, AM)) 1143 return false; 1144 1145 EVT VT = N.getValueType(); 1146 if (AM.BaseType == X86ISelAddressMode::RegBase) { 1147 if (!AM.Base_Reg.getNode()) 1148 AM.Base_Reg = CurDAG->getRegister(0, VT); 1149 } 1150 1151 if (!AM.IndexReg.getNode()) 1152 AM.IndexReg = CurDAG->getRegister(0, VT); 1153 1154 getAddressOperands(AM, Base, Scale, Index, Disp, Segment); 1155 return true; 1156} 1157 1158/// SelectScalarSSELoad - Match a scalar SSE load. In particular, we want to 1159/// match a load whose top elements are either undef or zeros. The load flavor 1160/// is derived from the type of N, which is either v4f32 or v2f64. 1161/// 1162/// We also return: 1163/// PatternChainNode: this is the matched node that has a chain input and 1164/// output. 1165bool X86DAGToDAGISel::SelectScalarSSELoad(SDNode *Root, 1166 SDValue N, SDValue &Base, 1167 SDValue &Scale, SDValue &Index, 1168 SDValue &Disp, SDValue &Segment, 1169 SDValue &PatternNodeWithChain) { 1170 if (N.getOpcode() == ISD::SCALAR_TO_VECTOR) { 1171 PatternNodeWithChain = N.getOperand(0); 1172 if (ISD::isNON_EXTLoad(PatternNodeWithChain.getNode()) && 1173 PatternNodeWithChain.hasOneUse() && 1174 IsProfitableToFold(N.getOperand(0), N.getNode(), Root) && 1175 IsLegalToFold(N.getOperand(0), N.getNode(), Root, OptLevel)) { 1176 LoadSDNode *LD = cast<LoadSDNode>(PatternNodeWithChain); 1177 if (!SelectAddr(LD, LD->getBasePtr(), Base, Scale, Index, Disp, Segment)) 1178 return false; 1179 return true; 1180 } 1181 } 1182 1183 // Also handle the case where we explicitly require zeros in the top 1184 // elements. This is a vector shuffle from the zero vector. 1185 if (N.getOpcode() == X86ISD::VZEXT_MOVL && N.getNode()->hasOneUse() && 1186 // Check to see if the top elements are all zeros (or bitcast of zeros). 1187 N.getOperand(0).getOpcode() == ISD::SCALAR_TO_VECTOR && 1188 N.getOperand(0).getNode()->hasOneUse() && 1189 ISD::isNON_EXTLoad(N.getOperand(0).getOperand(0).getNode()) && 1190 N.getOperand(0).getOperand(0).hasOneUse() && 1191 IsProfitableToFold(N.getOperand(0), N.getNode(), Root) && 1192 IsLegalToFold(N.getOperand(0), N.getNode(), Root, OptLevel)) { 1193 // Okay, this is a zero extending load. Fold it. 1194 LoadSDNode *LD = cast<LoadSDNode>(N.getOperand(0).getOperand(0)); 1195 if (!SelectAddr(LD, LD->getBasePtr(), Base, Scale, Index, Disp, Segment)) 1196 return false; 1197 PatternNodeWithChain = SDValue(LD, 0); 1198 return true; 1199 } 1200 return false; 1201} 1202 1203 1204/// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing 1205/// mode it matches can be cost effectively emitted as an LEA instruction. 1206bool X86DAGToDAGISel::SelectLEAAddr(SDValue N, 1207 SDValue &Base, SDValue &Scale, 1208 SDValue &Index, SDValue &Disp, 1209 SDValue &Segment) { 1210 X86ISelAddressMode AM; 1211 1212 // Set AM.Segment to prevent MatchAddress from using one. LEA doesn't support 1213 // segments. 1214 SDValue Copy = AM.Segment; 1215 SDValue T = CurDAG->getRegister(0, MVT::i32); 1216 AM.Segment = T; 1217 if (MatchAddress(N, AM)) 1218 return false; 1219 assert (T == AM.Segment); 1220 AM.Segment = Copy; 1221 1222 EVT VT = N.getValueType(); 1223 unsigned Complexity = 0; 1224 if (AM.BaseType == X86ISelAddressMode::RegBase) 1225 if (AM.Base_Reg.getNode()) 1226 Complexity = 1; 1227 else 1228 AM.Base_Reg = CurDAG->getRegister(0, VT); 1229 else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase) 1230 Complexity = 4; 1231 1232 if (AM.IndexReg.getNode()) 1233 Complexity++; 1234 else 1235 AM.IndexReg = CurDAG->getRegister(0, VT); 1236 1237 // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg, or with 1238 // a simple shift. 1239 if (AM.Scale > 1) 1240 Complexity++; 1241 1242 // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA 1243 // to a LEA. This is determined with some expermentation but is by no means 1244 // optimal (especially for code size consideration). LEA is nice because of 1245 // its three-address nature. Tweak the cost function again when we can run 1246 // convertToThreeAddress() at register allocation time. 1247 if (AM.hasSymbolicDisplacement()) { 1248 // For X86-64, we should always use lea to materialize RIP relative 1249 // addresses. 1250 if (Subtarget->is64Bit()) 1251 Complexity = 4; 1252 else 1253 Complexity += 2; 1254 } 1255 1256 if (AM.Disp && (AM.Base_Reg.getNode() || AM.IndexReg.getNode())) 1257 Complexity++; 1258 1259 // If it isn't worth using an LEA, reject it. 1260 if (Complexity <= 2) 1261 return false; 1262 1263 getAddressOperands(AM, Base, Scale, Index, Disp, Segment); 1264 return true; 1265} 1266 1267/// SelectTLSADDRAddr - This is only run on TargetGlobalTLSAddress nodes. 1268bool X86DAGToDAGISel::SelectTLSADDRAddr(SDValue N, SDValue &Base, 1269 SDValue &Scale, SDValue &Index, 1270 SDValue &Disp, SDValue &Segment) { 1271 assert(N.getOpcode() == ISD::TargetGlobalTLSAddress); 1272 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N); 1273 1274 X86ISelAddressMode AM; 1275 AM.GV = GA->getGlobal(); 1276 AM.Disp += GA->getOffset(); 1277 AM.Base_Reg = CurDAG->getRegister(0, N.getValueType()); 1278 AM.SymbolFlags = GA->getTargetFlags(); 1279 1280 if (N.getValueType() == MVT::i32) { 1281 AM.Scale = 1; 1282 AM.IndexReg = CurDAG->getRegister(X86::EBX, MVT::i32); 1283 } else { 1284 AM.IndexReg = CurDAG->getRegister(0, MVT::i64); 1285 } 1286 1287 getAddressOperands(AM, Base, Scale, Index, Disp, Segment); 1288 return true; 1289} 1290 1291 1292bool X86DAGToDAGISel::TryFoldLoad(SDNode *P, SDValue N, 1293 SDValue &Base, SDValue &Scale, 1294 SDValue &Index, SDValue &Disp, 1295 SDValue &Segment) { 1296 if (!ISD::isNON_EXTLoad(N.getNode()) || 1297 !IsProfitableToFold(N, P, P) || 1298 !IsLegalToFold(N, P, P, OptLevel)) 1299 return false; 1300 1301 return SelectAddr(N.getNode(), 1302 N.getOperand(1), Base, Scale, Index, Disp, Segment); 1303} 1304 1305/// getGlobalBaseReg - Return an SDNode that returns the value of 1306/// the global base register. Output instructions required to 1307/// initialize the global base register, if necessary. 1308/// 1309SDNode *X86DAGToDAGISel::getGlobalBaseReg() { 1310 unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF); 1311 return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode(); 1312} 1313 1314SDNode *X86DAGToDAGISel::SelectAtomic64(SDNode *Node, unsigned Opc) { 1315 SDValue Chain = Node->getOperand(0); 1316 SDValue In1 = Node->getOperand(1); 1317 SDValue In2L = Node->getOperand(2); 1318 SDValue In2H = Node->getOperand(3); 1319 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4; 1320 if (!SelectAddr(Node, In1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) 1321 return NULL; 1322 MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1); 1323 MemOp[0] = cast<MemSDNode>(Node)->getMemOperand(); 1324 const SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, In2L, In2H, Chain}; 1325 SDNode *ResNode = CurDAG->getMachineNode(Opc, Node->getDebugLoc(), 1326 MVT::i32, MVT::i32, MVT::Other, Ops, 1327 array_lengthof(Ops)); 1328 cast<MachineSDNode>(ResNode)->setMemRefs(MemOp, MemOp + 1); 1329 return ResNode; 1330} 1331 1332SDNode *X86DAGToDAGISel::SelectAtomicLoadAdd(SDNode *Node, EVT NVT) { 1333 if (Node->hasAnyUseOfValue(0)) 1334 return 0; 1335 1336 // Optimize common patterns for __sync_add_and_fetch and 1337 // __sync_sub_and_fetch where the result is not used. This allows us 1338 // to use "lock" version of add, sub, inc, dec instructions. 1339 // FIXME: Do not use special instructions but instead add the "lock" 1340 // prefix to the target node somehow. The extra information will then be 1341 // transferred to machine instruction and it denotes the prefix. 1342 SDValue Chain = Node->getOperand(0); 1343 SDValue Ptr = Node->getOperand(1); 1344 SDValue Val = Node->getOperand(2); 1345 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4; 1346 if (!SelectAddr(Node, Ptr, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) 1347 return 0; 1348 1349 bool isInc = false, isDec = false, isSub = false, isCN = false; 1350 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val); 1351 if (CN) { 1352 isCN = true; 1353 int64_t CNVal = CN->getSExtValue(); 1354 if (CNVal == 1) 1355 isInc = true; 1356 else if (CNVal == -1) 1357 isDec = true; 1358 else if (CNVal >= 0) 1359 Val = CurDAG->getTargetConstant(CNVal, NVT); 1360 else { 1361 isSub = true; 1362 Val = CurDAG->getTargetConstant(-CNVal, NVT); 1363 } 1364 } else if (Val.hasOneUse() && 1365 Val.getOpcode() == ISD::SUB && 1366 X86::isZeroNode(Val.getOperand(0))) { 1367 isSub = true; 1368 Val = Val.getOperand(1); 1369 } 1370 1371 unsigned Opc = 0; 1372 switch (NVT.getSimpleVT().SimpleTy) { 1373 default: return 0; 1374 case MVT::i8: 1375 if (isInc) 1376 Opc = X86::LOCK_INC8m; 1377 else if (isDec) 1378 Opc = X86::LOCK_DEC8m; 1379 else if (isSub) { 1380 if (isCN) 1381 Opc = X86::LOCK_SUB8mi; 1382 else 1383 Opc = X86::LOCK_SUB8mr; 1384 } else { 1385 if (isCN) 1386 Opc = X86::LOCK_ADD8mi; 1387 else 1388 Opc = X86::LOCK_ADD8mr; 1389 } 1390 break; 1391 case MVT::i16: 1392 if (isInc) 1393 Opc = X86::LOCK_INC16m; 1394 else if (isDec) 1395 Opc = X86::LOCK_DEC16m; 1396 else if (isSub) { 1397 if (isCN) { 1398 if (immSext8(Val.getNode())) 1399 Opc = X86::LOCK_SUB16mi8; 1400 else 1401 Opc = X86::LOCK_SUB16mi; 1402 } else 1403 Opc = X86::LOCK_SUB16mr; 1404 } else { 1405 if (isCN) { 1406 if (immSext8(Val.getNode())) 1407 Opc = X86::LOCK_ADD16mi8; 1408 else 1409 Opc = X86::LOCK_ADD16mi; 1410 } else 1411 Opc = X86::LOCK_ADD16mr; 1412 } 1413 break; 1414 case MVT::i32: 1415 if (isInc) 1416 Opc = X86::LOCK_INC32m; 1417 else if (isDec) 1418 Opc = X86::LOCK_DEC32m; 1419 else if (isSub) { 1420 if (isCN) { 1421 if (immSext8(Val.getNode())) 1422 Opc = X86::LOCK_SUB32mi8; 1423 else 1424 Opc = X86::LOCK_SUB32mi; 1425 } else 1426 Opc = X86::LOCK_SUB32mr; 1427 } else { 1428 if (isCN) { 1429 if (immSext8(Val.getNode())) 1430 Opc = X86::LOCK_ADD32mi8; 1431 else 1432 Opc = X86::LOCK_ADD32mi; 1433 } else 1434 Opc = X86::LOCK_ADD32mr; 1435 } 1436 break; 1437 case MVT::i64: 1438 if (isInc) 1439 Opc = X86::LOCK_INC64m; 1440 else if (isDec) 1441 Opc = X86::LOCK_DEC64m; 1442 else if (isSub) { 1443 Opc = X86::LOCK_SUB64mr; 1444 if (isCN) { 1445 if (immSext8(Val.getNode())) 1446 Opc = X86::LOCK_SUB64mi8; 1447 else if (i64immSExt32(Val.getNode())) 1448 Opc = X86::LOCK_SUB64mi32; 1449 } 1450 } else { 1451 Opc = X86::LOCK_ADD64mr; 1452 if (isCN) { 1453 if (immSext8(Val.getNode())) 1454 Opc = X86::LOCK_ADD64mi8; 1455 else if (i64immSExt32(Val.getNode())) 1456 Opc = X86::LOCK_ADD64mi32; 1457 } 1458 } 1459 break; 1460 } 1461 1462 DebugLoc dl = Node->getDebugLoc(); 1463 SDValue Undef = SDValue(CurDAG->getMachineNode(TargetOpcode::IMPLICIT_DEF, 1464 dl, NVT), 0); 1465 MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1); 1466 MemOp[0] = cast<MemSDNode>(Node)->getMemOperand(); 1467 if (isInc || isDec) { 1468 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Chain }; 1469 SDValue Ret = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Other, Ops, 6), 0); 1470 cast<MachineSDNode>(Ret)->setMemRefs(MemOp, MemOp + 1); 1471 SDValue RetVals[] = { Undef, Ret }; 1472 return CurDAG->getMergeValues(RetVals, 2, dl).getNode(); 1473 } else { 1474 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Val, Chain }; 1475 SDValue Ret = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Other, Ops, 7), 0); 1476 cast<MachineSDNode>(Ret)->setMemRefs(MemOp, MemOp + 1); 1477 SDValue RetVals[] = { Undef, Ret }; 1478 return CurDAG->getMergeValues(RetVals, 2, dl).getNode(); 1479 } 1480} 1481 1482/// HasNoSignedComparisonUses - Test whether the given X86ISD::CMP node has 1483/// any uses which require the SF or OF bits to be accurate. 1484static bool HasNoSignedComparisonUses(SDNode *N) { 1485 // Examine each user of the node. 1486 for (SDNode::use_iterator UI = N->use_begin(), 1487 UE = N->use_end(); UI != UE; ++UI) { 1488 // Only examine CopyToReg uses. 1489 if (UI->getOpcode() != ISD::CopyToReg) 1490 return false; 1491 // Only examine CopyToReg uses that copy to EFLAGS. 1492 if (cast<RegisterSDNode>(UI->getOperand(1))->getReg() != 1493 X86::EFLAGS) 1494 return false; 1495 // Examine each user of the CopyToReg use. 1496 for (SDNode::use_iterator FlagUI = UI->use_begin(), 1497 FlagUE = UI->use_end(); FlagUI != FlagUE; ++FlagUI) { 1498 // Only examine the Flag result. 1499 if (FlagUI.getUse().getResNo() != 1) continue; 1500 // Anything unusual: assume conservatively. 1501 if (!FlagUI->isMachineOpcode()) return false; 1502 // Examine the opcode of the user. 1503 switch (FlagUI->getMachineOpcode()) { 1504 // These comparisons don't treat the most significant bit specially. 1505 case X86::SETAr: case X86::SETAEr: case X86::SETBr: case X86::SETBEr: 1506 case X86::SETEr: case X86::SETNEr: case X86::SETPr: case X86::SETNPr: 1507 case X86::SETAm: case X86::SETAEm: case X86::SETBm: case X86::SETBEm: 1508 case X86::SETEm: case X86::SETNEm: case X86::SETPm: case X86::SETNPm: 1509 case X86::JA_4: case X86::JAE_4: case X86::JB_4: case X86::JBE_4: 1510 case X86::JE_4: case X86::JNE_4: case X86::JP_4: case X86::JNP_4: 1511 case X86::CMOVA16rr: case X86::CMOVA16rm: 1512 case X86::CMOVA32rr: case X86::CMOVA32rm: 1513 case X86::CMOVA64rr: case X86::CMOVA64rm: 1514 case X86::CMOVAE16rr: case X86::CMOVAE16rm: 1515 case X86::CMOVAE32rr: case X86::CMOVAE32rm: 1516 case X86::CMOVAE64rr: case X86::CMOVAE64rm: 1517 case X86::CMOVB16rr: case X86::CMOVB16rm: 1518 case X86::CMOVB32rr: case X86::CMOVB32rm: 1519 case X86::CMOVB64rr: case X86::CMOVB64rm: 1520 case X86::CMOVBE16rr: case X86::CMOVBE16rm: 1521 case X86::CMOVBE32rr: case X86::CMOVBE32rm: 1522 case X86::CMOVBE64rr: case X86::CMOVBE64rm: 1523 case X86::CMOVE16rr: case X86::CMOVE16rm: 1524 case X86::CMOVE32rr: case X86::CMOVE32rm: 1525 case X86::CMOVE64rr: case X86::CMOVE64rm: 1526 case X86::CMOVNE16rr: case X86::CMOVNE16rm: 1527 case X86::CMOVNE32rr: case X86::CMOVNE32rm: 1528 case X86::CMOVNE64rr: case X86::CMOVNE64rm: 1529 case X86::CMOVNP16rr: case X86::CMOVNP16rm: 1530 case X86::CMOVNP32rr: case X86::CMOVNP32rm: 1531 case X86::CMOVNP64rr: case X86::CMOVNP64rm: 1532 case X86::CMOVP16rr: case X86::CMOVP16rm: 1533 case X86::CMOVP32rr: case X86::CMOVP32rm: 1534 case X86::CMOVP64rr: case X86::CMOVP64rm: 1535 continue; 1536 // Anything else: assume conservatively. 1537 default: return false; 1538 } 1539 } 1540 } 1541 return true; 1542} 1543 1544SDNode *X86DAGToDAGISel::Select(SDNode *Node) { 1545 EVT NVT = Node->getValueType(0); 1546 unsigned Opc, MOpc; 1547 unsigned Opcode = Node->getOpcode(); 1548 DebugLoc dl = Node->getDebugLoc(); 1549 1550 DEBUG(dbgs() << "Selecting: "; Node->dump(CurDAG); dbgs() << '\n'); 1551 1552 if (Node->isMachineOpcode()) { 1553 DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n'); 1554 return NULL; // Already selected. 1555 } 1556 1557 switch (Opcode) { 1558 default: break; 1559 case X86ISD::GlobalBaseReg: 1560 return getGlobalBaseReg(); 1561 1562 case X86ISD::ATOMOR64_DAG: 1563 return SelectAtomic64(Node, X86::ATOMOR6432); 1564 case X86ISD::ATOMXOR64_DAG: 1565 return SelectAtomic64(Node, X86::ATOMXOR6432); 1566 case X86ISD::ATOMADD64_DAG: 1567 return SelectAtomic64(Node, X86::ATOMADD6432); 1568 case X86ISD::ATOMSUB64_DAG: 1569 return SelectAtomic64(Node, X86::ATOMSUB6432); 1570 case X86ISD::ATOMNAND64_DAG: 1571 return SelectAtomic64(Node, X86::ATOMNAND6432); 1572 case X86ISD::ATOMAND64_DAG: 1573 return SelectAtomic64(Node, X86::ATOMAND6432); 1574 case X86ISD::ATOMSWAP64_DAG: 1575 return SelectAtomic64(Node, X86::ATOMSWAP6432); 1576 1577 case ISD::ATOMIC_LOAD_ADD: { 1578 SDNode *RetVal = SelectAtomicLoadAdd(Node, NVT); 1579 if (RetVal) 1580 return RetVal; 1581 break; 1582 } 1583 case ISD::AND: 1584 case ISD::OR: 1585 case ISD::XOR: { 1586 // For operations of the form (x << C1) op C2, check if we can use a smaller 1587 // encoding for C2 by transforming it into (x op (C2>>C1)) << C1. 1588 SDValue N0 = Node->getOperand(0); 1589 SDValue N1 = Node->getOperand(1); 1590 1591 if (N0->getOpcode() != ISD::SHL || !N0->hasOneUse()) 1592 break; 1593 1594 // i8 is unshrinkable, i16 should be promoted to i32. 1595 if (NVT != MVT::i32 && NVT != MVT::i64) 1596 break; 1597 1598 ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N1); 1599 ConstantSDNode *ShlCst = dyn_cast<ConstantSDNode>(N0->getOperand(1)); 1600 if (!Cst || !ShlCst) 1601 break; 1602 1603 int64_t Val = Cst->getSExtValue(); 1604 uint64_t ShlVal = ShlCst->getZExtValue(); 1605 1606 // Make sure that we don't change the operation by removing bits. 1607 // This only matters for OR and XOR, AND is unaffected. 1608 if (Opcode != ISD::AND && ((Val >> ShlVal) << ShlVal) != Val) 1609 break; 1610 1611 unsigned ShlOp, Op; 1612 EVT CstVT = NVT; 1613 1614 // Check the minimum bitwidth for the new constant. 1615 // TODO: AND32ri is the same as AND64ri32 with zext imm. 1616 // TODO: MOV32ri+OR64r is cheaper than MOV64ri64+OR64rr 1617 // TODO: Using 16 and 8 bit operations is also possible for or32 & xor32. 1618 if (!isInt<8>(Val) && isInt<8>(Val >> ShlVal)) 1619 CstVT = MVT::i8; 1620 else if (!isInt<32>(Val) && isInt<32>(Val >> ShlVal)) 1621 CstVT = MVT::i32; 1622 1623 // Bail if there is no smaller encoding. 1624 if (NVT == CstVT) 1625 break; 1626 1627 switch (NVT.getSimpleVT().SimpleTy) { 1628 default: llvm_unreachable("Unsupported VT!"); 1629 case MVT::i32: 1630 assert(CstVT == MVT::i8); 1631 ShlOp = X86::SHL32ri; 1632 1633 switch (Opcode) { 1634 case ISD::AND: Op = X86::AND32ri8; break; 1635 case ISD::OR: Op = X86::OR32ri8; break; 1636 case ISD::XOR: Op = X86::XOR32ri8; break; 1637 } 1638 break; 1639 case MVT::i64: 1640 assert(CstVT == MVT::i8 || CstVT == MVT::i32); 1641 ShlOp = X86::SHL64ri; 1642 1643 switch (Opcode) { 1644 case ISD::AND: Op = CstVT==MVT::i8? X86::AND64ri8 : X86::AND64ri32; break; 1645 case ISD::OR: Op = CstVT==MVT::i8? X86::OR64ri8 : X86::OR64ri32; break; 1646 case ISD::XOR: Op = CstVT==MVT::i8? X86::XOR64ri8 : X86::XOR64ri32; break; 1647 } 1648 break; 1649 } 1650 1651 // Emit the smaller op and the shift. 1652 SDValue NewCst = CurDAG->getTargetConstant(Val >> ShlVal, CstVT); 1653 SDNode *New = CurDAG->getMachineNode(Op, dl, NVT, N0->getOperand(0),NewCst); 1654 return CurDAG->SelectNodeTo(Node, ShlOp, NVT, SDValue(New, 0), 1655 getI8Imm(ShlVal)); 1656 break; 1657 } 1658 case X86ISD::UMUL: { 1659 SDValue N0 = Node->getOperand(0); 1660 SDValue N1 = Node->getOperand(1); 1661 1662 unsigned LoReg; 1663 switch (NVT.getSimpleVT().SimpleTy) { 1664 default: llvm_unreachable("Unsupported VT!"); 1665 case MVT::i8: LoReg = X86::AL; Opc = X86::MUL8r; break; 1666 case MVT::i16: LoReg = X86::AX; Opc = X86::MUL16r; break; 1667 case MVT::i32: LoReg = X86::EAX; Opc = X86::MUL32r; break; 1668 case MVT::i64: LoReg = X86::RAX; Opc = X86::MUL64r; break; 1669 } 1670 1671 SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, LoReg, 1672 N0, SDValue()).getValue(1); 1673 1674 SDVTList VTs = CurDAG->getVTList(NVT, NVT, MVT::i32); 1675 SDValue Ops[] = {N1, InFlag}; 1676 SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops, 2); 1677 1678 ReplaceUses(SDValue(Node, 0), SDValue(CNode, 0)); 1679 ReplaceUses(SDValue(Node, 1), SDValue(CNode, 1)); 1680 ReplaceUses(SDValue(Node, 2), SDValue(CNode, 2)); 1681 return NULL; 1682 } 1683 1684 case ISD::SMUL_LOHI: 1685 case ISD::UMUL_LOHI: { 1686 SDValue N0 = Node->getOperand(0); 1687 SDValue N1 = Node->getOperand(1); 1688 1689 bool isSigned = Opcode == ISD::SMUL_LOHI; 1690 if (!isSigned) { 1691 switch (NVT.getSimpleVT().SimpleTy) { 1692 default: llvm_unreachable("Unsupported VT!"); 1693 case MVT::i8: Opc = X86::MUL8r; MOpc = X86::MUL8m; break; 1694 case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break; 1695 case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break; 1696 case MVT::i64: Opc = X86::MUL64r; MOpc = X86::MUL64m; break; 1697 } 1698 } else { 1699 switch (NVT.getSimpleVT().SimpleTy) { 1700 default: llvm_unreachable("Unsupported VT!"); 1701 case MVT::i8: Opc = X86::IMUL8r; MOpc = X86::IMUL8m; break; 1702 case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break; 1703 case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break; 1704 case MVT::i64: Opc = X86::IMUL64r; MOpc = X86::IMUL64m; break; 1705 } 1706 } 1707 1708 unsigned LoReg, HiReg; 1709 switch (NVT.getSimpleVT().SimpleTy) { 1710 default: llvm_unreachable("Unsupported VT!"); 1711 case MVT::i8: LoReg = X86::AL; HiReg = X86::AH; break; 1712 case MVT::i16: LoReg = X86::AX; HiReg = X86::DX; break; 1713 case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break; 1714 case MVT::i64: LoReg = X86::RAX; HiReg = X86::RDX; break; 1715 } 1716 1717 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4; 1718 bool foldedLoad = TryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4); 1719 // Multiply is commmutative. 1720 if (!foldedLoad) { 1721 foldedLoad = TryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4); 1722 if (foldedLoad) 1723 std::swap(N0, N1); 1724 } 1725 1726 SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, LoReg, 1727 N0, SDValue()).getValue(1); 1728 1729 if (foldedLoad) { 1730 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0), 1731 InFlag }; 1732 SDNode *CNode = 1733 CurDAG->getMachineNode(MOpc, dl, MVT::Other, MVT::Glue, Ops, 1734 array_lengthof(Ops)); 1735 InFlag = SDValue(CNode, 1); 1736 1737 // Update the chain. 1738 ReplaceUses(N1.getValue(1), SDValue(CNode, 0)); 1739 } else { 1740 SDNode *CNode = CurDAG->getMachineNode(Opc, dl, MVT::Glue, N1, InFlag); 1741 InFlag = SDValue(CNode, 0); 1742 } 1743 1744 // Prevent use of AH in a REX instruction by referencing AX instead. 1745 if (HiReg == X86::AH && Subtarget->is64Bit() && 1746 !SDValue(Node, 1).use_empty()) { 1747 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1748 X86::AX, MVT::i16, InFlag); 1749 InFlag = Result.getValue(2); 1750 // Get the low part if needed. Don't use getCopyFromReg for aliasing 1751 // registers. 1752 if (!SDValue(Node, 0).use_empty()) 1753 ReplaceUses(SDValue(Node, 1), 1754 CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result)); 1755 1756 // Shift AX down 8 bits. 1757 Result = SDValue(CurDAG->getMachineNode(X86::SHR16ri, dl, MVT::i16, 1758 Result, 1759 CurDAG->getTargetConstant(8, MVT::i8)), 0); 1760 // Then truncate it down to i8. 1761 ReplaceUses(SDValue(Node, 1), 1762 CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result)); 1763 } 1764 // Copy the low half of the result, if it is needed. 1765 if (!SDValue(Node, 0).use_empty()) { 1766 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1767 LoReg, NVT, InFlag); 1768 InFlag = Result.getValue(2); 1769 ReplaceUses(SDValue(Node, 0), Result); 1770 DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n'); 1771 } 1772 // Copy the high half of the result, if it is needed. 1773 if (!SDValue(Node, 1).use_empty()) { 1774 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1775 HiReg, NVT, InFlag); 1776 InFlag = Result.getValue(2); 1777 ReplaceUses(SDValue(Node, 1), Result); 1778 DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n'); 1779 } 1780 1781 return NULL; 1782 } 1783 1784 case ISD::SDIVREM: 1785 case ISD::UDIVREM: { 1786 SDValue N0 = Node->getOperand(0); 1787 SDValue N1 = Node->getOperand(1); 1788 1789 bool isSigned = Opcode == ISD::SDIVREM; 1790 if (!isSigned) { 1791 switch (NVT.getSimpleVT().SimpleTy) { 1792 default: llvm_unreachable("Unsupported VT!"); 1793 case MVT::i8: Opc = X86::DIV8r; MOpc = X86::DIV8m; break; 1794 case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break; 1795 case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break; 1796 case MVT::i64: Opc = X86::DIV64r; MOpc = X86::DIV64m; break; 1797 } 1798 } else { 1799 switch (NVT.getSimpleVT().SimpleTy) { 1800 default: llvm_unreachable("Unsupported VT!"); 1801 case MVT::i8: Opc = X86::IDIV8r; MOpc = X86::IDIV8m; break; 1802 case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break; 1803 case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break; 1804 case MVT::i64: Opc = X86::IDIV64r; MOpc = X86::IDIV64m; break; 1805 } 1806 } 1807 1808 unsigned LoReg, HiReg, ClrReg; 1809 unsigned ClrOpcode, SExtOpcode; 1810 switch (NVT.getSimpleVT().SimpleTy) { 1811 default: llvm_unreachable("Unsupported VT!"); 1812 case MVT::i8: 1813 LoReg = X86::AL; ClrReg = HiReg = X86::AH; 1814 ClrOpcode = 0; 1815 SExtOpcode = X86::CBW; 1816 break; 1817 case MVT::i16: 1818 LoReg = X86::AX; HiReg = X86::DX; 1819 ClrOpcode = X86::MOV16r0; ClrReg = X86::DX; 1820 SExtOpcode = X86::CWD; 1821 break; 1822 case MVT::i32: 1823 LoReg = X86::EAX; ClrReg = HiReg = X86::EDX; 1824 ClrOpcode = X86::MOV32r0; 1825 SExtOpcode = X86::CDQ; 1826 break; 1827 case MVT::i64: 1828 LoReg = X86::RAX; ClrReg = HiReg = X86::RDX; 1829 ClrOpcode = X86::MOV64r0; 1830 SExtOpcode = X86::CQO; 1831 break; 1832 } 1833 1834 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4; 1835 bool foldedLoad = TryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4); 1836 bool signBitIsZero = CurDAG->SignBitIsZero(N0); 1837 1838 SDValue InFlag; 1839 if (NVT == MVT::i8 && (!isSigned || signBitIsZero)) { 1840 // Special case for div8, just use a move with zero extension to AX to 1841 // clear the upper 8 bits (AH). 1842 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Move, Chain; 1843 if (TryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) { 1844 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N0.getOperand(0) }; 1845 Move = 1846 SDValue(CurDAG->getMachineNode(X86::MOVZX16rm8, dl, MVT::i16, 1847 MVT::Other, Ops, 1848 array_lengthof(Ops)), 0); 1849 Chain = Move.getValue(1); 1850 ReplaceUses(N0.getValue(1), Chain); 1851 } else { 1852 Move = 1853 SDValue(CurDAG->getMachineNode(X86::MOVZX16rr8, dl, MVT::i16, N0),0); 1854 Chain = CurDAG->getEntryNode(); 1855 } 1856 Chain = CurDAG->getCopyToReg(Chain, dl, X86::AX, Move, SDValue()); 1857 InFlag = Chain.getValue(1); 1858 } else { 1859 InFlag = 1860 CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, 1861 LoReg, N0, SDValue()).getValue(1); 1862 if (isSigned && !signBitIsZero) { 1863 // Sign extend the low part into the high part. 1864 InFlag = 1865 SDValue(CurDAG->getMachineNode(SExtOpcode, dl, MVT::Glue, InFlag),0); 1866 } else { 1867 // Zero out the high part, effectively zero extending the input. 1868 SDValue ClrNode = 1869 SDValue(CurDAG->getMachineNode(ClrOpcode, dl, NVT), 0); 1870 InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, ClrReg, 1871 ClrNode, InFlag).getValue(1); 1872 } 1873 } 1874 1875 if (foldedLoad) { 1876 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0), 1877 InFlag }; 1878 SDNode *CNode = 1879 CurDAG->getMachineNode(MOpc, dl, MVT::Other, MVT::Glue, Ops, 1880 array_lengthof(Ops)); 1881 InFlag = SDValue(CNode, 1); 1882 // Update the chain. 1883 ReplaceUses(N1.getValue(1), SDValue(CNode, 0)); 1884 } else { 1885 InFlag = 1886 SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Glue, N1, InFlag), 0); 1887 } 1888 1889 // Prevent use of AH in a REX instruction by referencing AX instead. 1890 // Shift it down 8 bits. 1891 if (HiReg == X86::AH && Subtarget->is64Bit() && 1892 !SDValue(Node, 1).use_empty()) { 1893 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1894 X86::AX, MVT::i16, InFlag); 1895 InFlag = Result.getValue(2); 1896 1897 // If we also need AL (the quotient), get it by extracting a subreg from 1898 // Result. The fast register allocator does not like multiple CopyFromReg 1899 // nodes using aliasing registers. 1900 if (!SDValue(Node, 0).use_empty()) 1901 ReplaceUses(SDValue(Node, 0), 1902 CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result)); 1903 1904 // Shift AX right by 8 bits instead of using AH. 1905 Result = SDValue(CurDAG->getMachineNode(X86::SHR16ri, dl, MVT::i16, 1906 Result, 1907 CurDAG->getTargetConstant(8, MVT::i8)), 1908 0); 1909 ReplaceUses(SDValue(Node, 1), 1910 CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result)); 1911 } 1912 // Copy the division (low) result, if it is needed. 1913 if (!SDValue(Node, 0).use_empty()) { 1914 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1915 LoReg, NVT, InFlag); 1916 InFlag = Result.getValue(2); 1917 ReplaceUses(SDValue(Node, 0), Result); 1918 DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n'); 1919 } 1920 // Copy the remainder (high) result, if it is needed. 1921 if (!SDValue(Node, 1).use_empty()) { 1922 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 1923 HiReg, NVT, InFlag); 1924 InFlag = Result.getValue(2); 1925 ReplaceUses(SDValue(Node, 1), Result); 1926 DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n'); 1927 } 1928 return NULL; 1929 } 1930 1931 case X86ISD::CMP: { 1932 SDValue N0 = Node->getOperand(0); 1933 SDValue N1 = Node->getOperand(1); 1934 1935 // Look for (X86cmp (and $op, $imm), 0) and see if we can convert it to 1936 // use a smaller encoding. 1937 if (N0.getOpcode() == ISD::TRUNCATE && N0.hasOneUse() && 1938 HasNoSignedComparisonUses(Node)) 1939 // Look past the truncate if CMP is the only use of it. 1940 N0 = N0.getOperand(0); 1941 if (N0.getNode()->getOpcode() == ISD::AND && N0.getNode()->hasOneUse() && 1942 N0.getValueType() != MVT::i8 && 1943 X86::isZeroNode(N1)) { 1944 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N0.getNode()->getOperand(1)); 1945 if (!C) break; 1946 1947 // For example, convert "testl %eax, $8" to "testb %al, $8" 1948 if ((C->getZExtValue() & ~UINT64_C(0xff)) == 0 && 1949 (!(C->getZExtValue() & 0x80) || 1950 HasNoSignedComparisonUses(Node))) { 1951 SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), MVT::i8); 1952 SDValue Reg = N0.getNode()->getOperand(0); 1953 1954 // On x86-32, only the ABCD registers have 8-bit subregisters. 1955 if (!Subtarget->is64Bit()) { 1956 TargetRegisterClass *TRC = 0; 1957 switch (N0.getValueType().getSimpleVT().SimpleTy) { 1958 case MVT::i32: TRC = &X86::GR32_ABCDRegClass; break; 1959 case MVT::i16: TRC = &X86::GR16_ABCDRegClass; break; 1960 default: llvm_unreachable("Unsupported TEST operand type!"); 1961 } 1962 SDValue RC = CurDAG->getTargetConstant(TRC->getID(), MVT::i32); 1963 Reg = SDValue(CurDAG->getMachineNode(X86::COPY_TO_REGCLASS, dl, 1964 Reg.getValueType(), Reg, RC), 0); 1965 } 1966 1967 // Extract the l-register. 1968 SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, 1969 MVT::i8, Reg); 1970 1971 // Emit a testb. 1972 return CurDAG->getMachineNode(X86::TEST8ri, dl, MVT::i32, Subreg, Imm); 1973 } 1974 1975 // For example, "testl %eax, $2048" to "testb %ah, $8". 1976 if ((C->getZExtValue() & ~UINT64_C(0xff00)) == 0 && 1977 (!(C->getZExtValue() & 0x8000) || 1978 HasNoSignedComparisonUses(Node))) { 1979 // Shift the immediate right by 8 bits. 1980 SDValue ShiftedImm = CurDAG->getTargetConstant(C->getZExtValue() >> 8, 1981 MVT::i8); 1982 SDValue Reg = N0.getNode()->getOperand(0); 1983 1984 // Put the value in an ABCD register. 1985 TargetRegisterClass *TRC = 0; 1986 switch (N0.getValueType().getSimpleVT().SimpleTy) { 1987 case MVT::i64: TRC = &X86::GR64_ABCDRegClass; break; 1988 case MVT::i32: TRC = &X86::GR32_ABCDRegClass; break; 1989 case MVT::i16: TRC = &X86::GR16_ABCDRegClass; break; 1990 default: llvm_unreachable("Unsupported TEST operand type!"); 1991 } 1992 SDValue RC = CurDAG->getTargetConstant(TRC->getID(), MVT::i32); 1993 Reg = SDValue(CurDAG->getMachineNode(X86::COPY_TO_REGCLASS, dl, 1994 Reg.getValueType(), Reg, RC), 0); 1995 1996 // Extract the h-register. 1997 SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_8bit_hi, dl, 1998 MVT::i8, Reg); 1999 2000 // Emit a testb. No special NOREX tricks are needed since there's 2001 // only one GPR operand! 2002 return CurDAG->getMachineNode(X86::TEST8ri, dl, MVT::i32, 2003 Subreg, ShiftedImm); 2004 } 2005 2006 // For example, "testl %eax, $32776" to "testw %ax, $32776". 2007 if ((C->getZExtValue() & ~UINT64_C(0xffff)) == 0 && 2008 N0.getValueType() != MVT::i16 && 2009 (!(C->getZExtValue() & 0x8000) || 2010 HasNoSignedComparisonUses(Node))) { 2011 SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), MVT::i16); 2012 SDValue Reg = N0.getNode()->getOperand(0); 2013 2014 // Extract the 16-bit subregister. 2015 SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_16bit, dl, 2016 MVT::i16, Reg); 2017 2018 // Emit a testw. 2019 return CurDAG->getMachineNode(X86::TEST16ri, dl, MVT::i32, Subreg, Imm); 2020 } 2021 2022 // For example, "testq %rax, $268468232" to "testl %eax, $268468232". 2023 if ((C->getZExtValue() & ~UINT64_C(0xffffffff)) == 0 && 2024 N0.getValueType() == MVT::i64 && 2025 (!(C->getZExtValue() & 0x80000000) || 2026 HasNoSignedComparisonUses(Node))) { 2027 SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), MVT::i32); 2028 SDValue Reg = N0.getNode()->getOperand(0); 2029 2030 // Extract the 32-bit subregister. 2031 SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_32bit, dl, 2032 MVT::i32, Reg); 2033 2034 // Emit a testl. 2035 return CurDAG->getMachineNode(X86::TEST32ri, dl, MVT::i32, Subreg, Imm); 2036 } 2037 } 2038 break; 2039 } 2040 } 2041 2042 SDNode *ResNode = SelectCode(Node); 2043 2044 DEBUG(dbgs() << "=> "; 2045 if (ResNode == NULL || ResNode == Node) 2046 Node->dump(CurDAG); 2047 else 2048 ResNode->dump(CurDAG); 2049 dbgs() << '\n'); 2050 2051 return ResNode; 2052} 2053 2054bool X86DAGToDAGISel:: 2055SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode, 2056 std::vector<SDValue> &OutOps) { 2057 SDValue Op0, Op1, Op2, Op3, Op4; 2058 switch (ConstraintCode) { 2059 case 'o': // offsetable ?? 2060 case 'v': // not offsetable ?? 2061 default: return true; 2062 case 'm': // memory 2063 if (!SelectAddr(0, Op, Op0, Op1, Op2, Op3, Op4)) 2064 return true; 2065 break; 2066 } 2067 2068 OutOps.push_back(Op0); 2069 OutOps.push_back(Op1); 2070 OutOps.push_back(Op2); 2071 OutOps.push_back(Op3); 2072 OutOps.push_back(Op4); 2073 return false; 2074} 2075 2076/// createX86ISelDag - This pass converts a legalized DAG into a 2077/// X86-specific DAG, ready for instruction scheduling. 2078/// 2079FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM, 2080 llvm::CodeGenOpt::Level OptLevel) { 2081 return new X86DAGToDAGISel(TM, OptLevel); 2082} 2083