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