LLVM API Documentation
00001 //===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the Evan Cheng and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines a DAG pattern matching instruction selector for X86, 00011 // converting from a legalized dag to a X86 dag. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "isel" 00016 #include "X86.h" 00017 #include "X86InstrBuilder.h" 00018 #include "X86ISelLowering.h" 00019 #include "X86RegisterInfo.h" 00020 #include "X86Subtarget.h" 00021 #include "X86TargetMachine.h" 00022 #include "llvm/GlobalValue.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/Intrinsics.h" 00025 #include "llvm/Support/CFG.h" 00026 #include "llvm/CodeGen/MachineConstantPool.h" 00027 #include "llvm/CodeGen/MachineFunction.h" 00028 #include "llvm/CodeGen/MachineFrameInfo.h" 00029 #include "llvm/CodeGen/MachineInstrBuilder.h" 00030 #include "llvm/CodeGen/SSARegMap.h" 00031 #include "llvm/CodeGen/SelectionDAGISel.h" 00032 #include "llvm/Target/TargetMachine.h" 00033 #include "llvm/Support/Debug.h" 00034 #include "llvm/Support/Visibility.h" 00035 #include "llvm/ADT/Statistic.h" 00036 #include <iostream> 00037 #include <set> 00038 using namespace llvm; 00039 00040 //===----------------------------------------------------------------------===// 00041 // Pattern Matcher Implementation 00042 //===----------------------------------------------------------------------===// 00043 00044 namespace { 00045 /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses 00046 /// SDOperand's instead of register numbers for the leaves of the matched 00047 /// tree. 00048 struct X86ISelAddressMode { 00049 enum { 00050 RegBase, 00051 FrameIndexBase 00052 } BaseType; 00053 00054 struct { // This is really a union, discriminated by BaseType! 00055 SDOperand Reg; 00056 int FrameIndex; 00057 } Base; 00058 00059 unsigned Scale; 00060 SDOperand IndexReg; 00061 unsigned Disp; 00062 GlobalValue *GV; 00063 Constant *CP; 00064 unsigned Align; // CP alignment. 00065 00066 X86ISelAddressMode() 00067 : BaseType(RegBase), Scale(1), IndexReg(), Disp(0), GV(0), 00068 CP(0), Align(0) { 00069 } 00070 }; 00071 } 00072 00073 namespace { 00074 Statistic<> 00075 NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added"); 00076 00077 //===--------------------------------------------------------------------===// 00078 /// ISel - X86 specific code to select X86 machine instructions for 00079 /// SelectionDAG operations. 00080 /// 00081 class VISIBILITY_HIDDEN X86DAGToDAGISel : public SelectionDAGISel { 00082 /// ContainsFPCode - Every instruction we select that uses or defines a FP 00083 /// register should set this to true. 00084 bool ContainsFPCode; 00085 00086 /// X86Lowering - This object fully describes how to lower LLVM code to an 00087 /// X86-specific SelectionDAG. 00088 X86TargetLowering X86Lowering; 00089 00090 /// Subtarget - Keep a pointer to the X86Subtarget around so that we can 00091 /// make the right decision when generating code for different targets. 00092 const X86Subtarget *Subtarget; 00093 00094 unsigned GlobalBaseReg; 00095 public: 00096 X86DAGToDAGISel(X86TargetMachine &TM) 00097 : SelectionDAGISel(X86Lowering), 00098 X86Lowering(*TM.getTargetLowering()) { 00099 Subtarget = &TM.getSubtarget<X86Subtarget>(); 00100 } 00101 00102 virtual bool runOnFunction(Function &Fn) { 00103 // Make sure we re-emit a set of the global base reg if necessary 00104 GlobalBaseReg = 0; 00105 return SelectionDAGISel::runOnFunction(Fn); 00106 } 00107 00108 virtual const char *getPassName() const { 00109 return "X86 DAG->DAG Instruction Selection"; 00110 } 00111 00112 /// InstructionSelectBasicBlock - This callback is invoked by 00113 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen. 00114 virtual void InstructionSelectBasicBlock(SelectionDAG &DAG); 00115 00116 virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF); 00117 00118 // Include the pieces autogenerated from the target description. 00119 #include "X86GenDAGISel.inc" 00120 00121 private: 00122 void Select(SDOperand &Result, SDOperand N); 00123 00124 bool MatchAddress(SDOperand N, X86ISelAddressMode &AM, bool isRoot = true); 00125 bool SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 00126 SDOperand &Index, SDOperand &Disp); 00127 bool SelectLEAAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 00128 SDOperand &Index, SDOperand &Disp); 00129 bool TryFoldLoad(SDOperand P, SDOperand N, 00130 SDOperand &Base, SDOperand &Scale, 00131 SDOperand &Index, SDOperand &Disp); 00132 /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for 00133 /// inline asm expressions. 00134 virtual bool SelectInlineAsmMemoryOperand(const SDOperand &Op, 00135 char ConstraintCode, 00136 std::vector<SDOperand> &OutOps, 00137 SelectionDAG &DAG); 00138 00139 void EmitSpecialCodeForMain(MachineBasicBlock *BB, MachineFrameInfo *MFI); 00140 00141 inline void getAddressOperands(X86ISelAddressMode &AM, SDOperand &Base, 00142 SDOperand &Scale, SDOperand &Index, 00143 SDOperand &Disp) { 00144 Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ? 00145 CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, MVT::i32) : AM.Base.Reg; 00146 Scale = getI8Imm(AM.Scale); 00147 Index = AM.IndexReg; 00148 Disp = AM.GV ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp) 00149 : (AM.CP ? 00150 CurDAG->getTargetConstantPool(AM.CP, MVT::i32, AM.Align, AM.Disp) 00151 : getI32Imm(AM.Disp)); 00152 } 00153 00154 /// getI8Imm - Return a target constant with the specified value, of type 00155 /// i8. 00156 inline SDOperand getI8Imm(unsigned Imm) { 00157 return CurDAG->getTargetConstant(Imm, MVT::i8); 00158 } 00159 00160 /// getI16Imm - Return a target constant with the specified value, of type 00161 /// i16. 00162 inline SDOperand getI16Imm(unsigned Imm) { 00163 return CurDAG->getTargetConstant(Imm, MVT::i16); 00164 } 00165 00166 /// getI32Imm - Return a target constant with the specified value, of type 00167 /// i32. 00168 inline SDOperand getI32Imm(unsigned Imm) { 00169 return CurDAG->getTargetConstant(Imm, MVT::i32); 00170 } 00171 00172 /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC 00173 /// base register. Return the virtual register that holds this value. 00174 SDOperand getGlobalBaseReg(); 00175 00176 #ifndef NDEBUG 00177 unsigned Indent; 00178 #endif 00179 }; 00180 } 00181 00182 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel 00183 /// when it has created a SelectionDAG for us to codegen. 00184 void X86DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) { 00185 DEBUG(BB->dump()); 00186 MachineFunction::iterator FirstMBB = BB; 00187 00188 // Codegen the basic block. 00189 #ifndef NDEBUG 00190 DEBUG(std::cerr << "===== Instruction selection begins:\n"); 00191 Indent = 0; 00192 #endif 00193 DAG.setRoot(SelectRoot(DAG.getRoot())); 00194 assert(InFlightSet.empty() && "ISel InFlightSet has not been emptied!"); 00195 #ifndef NDEBUG 00196 DEBUG(std::cerr << "===== Instruction selection ends:\n"); 00197 #endif 00198 CodeGenMap.clear(); 00199 HandleMap.clear(); 00200 ReplaceMap.clear(); 00201 DAG.RemoveDeadNodes(); 00202 00203 // Emit machine code to BB. 00204 ScheduleAndEmitDAG(DAG); 00205 00206 // If we are emitting FP stack code, scan the basic block to determine if this 00207 // block defines any FP values. If so, put an FP_REG_KILL instruction before 00208 // the terminator of the block. 00209 if (!Subtarget->hasSSE2()) { 00210 // Note that FP stack instructions *are* used in SSE code when returning 00211 // values, but these are not live out of the basic block, so we don't need 00212 // an FP_REG_KILL in this case either. 00213 bool ContainsFPCode = false; 00214 00215 // Scan all of the machine instructions in these MBBs, checking for FP 00216 // stores. 00217 MachineFunction::iterator MBBI = FirstMBB; 00218 do { 00219 for (MachineBasicBlock::iterator I = MBBI->begin(), E = MBBI->end(); 00220 !ContainsFPCode && I != E; ++I) { 00221 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 00222 if (I->getOperand(op).isRegister() && I->getOperand(op).isDef() && 00223 MRegisterInfo::isVirtualRegister(I->getOperand(op).getReg()) && 00224 RegMap->getRegClass(I->getOperand(0).getReg()) == 00225 X86::RFPRegisterClass) { 00226 ContainsFPCode = true; 00227 break; 00228 } 00229 } 00230 } 00231 } while (!ContainsFPCode && &*(MBBI++) != BB); 00232 00233 // Check PHI nodes in successor blocks. These PHI's will be lowered to have 00234 // a copy of the input value in this block. 00235 if (!ContainsFPCode) { 00236 // Final check, check LLVM BB's that are successors to the LLVM BB 00237 // corresponding to BB for FP PHI nodes. 00238 const BasicBlock *LLVMBB = BB->getBasicBlock(); 00239 const PHINode *PN; 00240 for (succ_const_iterator SI = succ_begin(LLVMBB), E = succ_end(LLVMBB); 00241 !ContainsFPCode && SI != E; ++SI) { 00242 for (BasicBlock::const_iterator II = SI->begin(); 00243 (PN = dyn_cast<PHINode>(II)); ++II) { 00244 if (PN->getType()->isFloatingPoint()) { 00245 ContainsFPCode = true; 00246 break; 00247 } 00248 } 00249 } 00250 } 00251 00252 // Finally, if we found any FP code, emit the FP_REG_KILL instruction. 00253 if (ContainsFPCode) { 00254 BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0); 00255 ++NumFPKill; 00256 } 00257 } 00258 } 00259 00260 /// EmitSpecialCodeForMain - Emit any code that needs to be executed only in 00261 /// the main function. 00262 void X86DAGToDAGISel::EmitSpecialCodeForMain(MachineBasicBlock *BB, 00263 MachineFrameInfo *MFI) { 00264 if (Subtarget->TargetType == X86Subtarget::isCygwin) 00265 BuildMI(BB, X86::CALLpcrel32, 1).addExternalSymbol("__main"); 00266 00267 // Switch the FPU to 64-bit precision mode for better compatibility and speed. 00268 int CWFrameIdx = MFI->CreateStackObject(2, 2); 00269 addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx); 00270 00271 // Set the high part to be 64-bit precision. 00272 addFrameReference(BuildMI(BB, X86::MOV8mi, 5), 00273 CWFrameIdx, 1).addImm(2); 00274 00275 // Reload the modified control word now. 00276 addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx); 00277 } 00278 00279 void X86DAGToDAGISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) { 00280 // If this is main, emit special code for main. 00281 MachineBasicBlock *BB = MF.begin(); 00282 if (Fn.hasExternalLinkage() && Fn.getName() == "main") 00283 EmitSpecialCodeForMain(BB, MF.getFrameInfo()); 00284 } 00285 00286 /// MatchAddress - Add the specified node to the specified addressing mode, 00287 /// returning true if it cannot be done. This just pattern matches for the 00288 /// addressing mode 00289 bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM, 00290 bool isRoot) { 00291 bool Available = false; 00292 // If N has already been selected, reuse the result unless in some very 00293 // specific cases. 00294 std::map<SDOperand, SDOperand>::iterator CGMI= CodeGenMap.find(N.getValue(0)); 00295 if (CGMI != CodeGenMap.end()) { 00296 Available = true; 00297 } 00298 00299 switch (N.getOpcode()) { 00300 default: break; 00301 case ISD::Constant: 00302 AM.Disp += cast<ConstantSDNode>(N)->getValue(); 00303 return false; 00304 00305 case X86ISD::Wrapper: 00306 // If both base and index components have been picked, we can't fit 00307 // the result available in the register in the addressing mode. Duplicate 00308 // GlobalAddress or ConstantPool as displacement. 00309 if (!Available || (AM.Base.Reg.Val && AM.IndexReg.Val)) { 00310 if (ConstantPoolSDNode *CP = 00311 dyn_cast<ConstantPoolSDNode>(N.getOperand(0))) { 00312 if (AM.CP == 0) { 00313 AM.CP = CP->get(); 00314 AM.Align = CP->getAlignment(); 00315 AM.Disp += CP->getOffset(); 00316 return false; 00317 } 00318 } else if (GlobalAddressSDNode *G = 00319 dyn_cast<GlobalAddressSDNode>(N.getOperand(0))) { 00320 if (AM.GV == 0) { 00321 AM.GV = G->getGlobal(); 00322 AM.Disp += G->getOffset(); 00323 return false; 00324 } 00325 } 00326 } 00327 break; 00328 00329 case ISD::FrameIndex: 00330 if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) { 00331 AM.BaseType = X86ISelAddressMode::FrameIndexBase; 00332 AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex(); 00333 return false; 00334 } 00335 break; 00336 00337 case ISD::SHL: 00338 if (!Available && AM.IndexReg.Val == 0 && AM.Scale == 1) 00339 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) { 00340 unsigned Val = CN->getValue(); 00341 if (Val == 1 || Val == 2 || Val == 3) { 00342 AM.Scale = 1 << Val; 00343 SDOperand ShVal = N.Val->getOperand(0); 00344 00345 // Okay, we know that we have a scale by now. However, if the scaled 00346 // value is an add of something and a constant, we can fold the 00347 // constant into the disp field here. 00348 if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() && 00349 isa<ConstantSDNode>(ShVal.Val->getOperand(1))) { 00350 AM.IndexReg = ShVal.Val->getOperand(0); 00351 ConstantSDNode *AddVal = 00352 cast<ConstantSDNode>(ShVal.Val->getOperand(1)); 00353 AM.Disp += AddVal->getValue() << Val; 00354 } else { 00355 AM.IndexReg = ShVal; 00356 } 00357 return false; 00358 } 00359 } 00360 break; 00361 00362 case ISD::MUL: 00363 // X*[3,5,9] -> X+X*[2,4,8] 00364 if (!Available && 00365 AM.BaseType == X86ISelAddressMode::RegBase && 00366 AM.Base.Reg.Val == 0 && 00367 AM.IndexReg.Val == 0) 00368 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) 00369 if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) { 00370 AM.Scale = unsigned(CN->getValue())-1; 00371 00372 SDOperand MulVal = N.Val->getOperand(0); 00373 SDOperand Reg; 00374 00375 // Okay, we know that we have a scale by now. However, if the scaled 00376 // value is an add of something and a constant, we can fold the 00377 // constant into the disp field here. 00378 if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() && 00379 isa<ConstantSDNode>(MulVal.Val->getOperand(1))) { 00380 Reg = MulVal.Val->getOperand(0); 00381 ConstantSDNode *AddVal = 00382 cast<ConstantSDNode>(MulVal.Val->getOperand(1)); 00383 AM.Disp += AddVal->getValue() * CN->getValue(); 00384 } else { 00385 Reg = N.Val->getOperand(0); 00386 } 00387 00388 AM.IndexReg = AM.Base.Reg = Reg; 00389 return false; 00390 } 00391 break; 00392 00393 case ISD::ADD: { 00394 if (!Available) { 00395 X86ISelAddressMode Backup = AM; 00396 if (!MatchAddress(N.Val->getOperand(0), AM, false) && 00397 !MatchAddress(N.Val->getOperand(1), AM, false)) 00398 return false; 00399 AM = Backup; 00400 if (!MatchAddress(N.Val->getOperand(1), AM, false) && 00401 !MatchAddress(N.Val->getOperand(0), AM, false)) 00402 return false; 00403 AM = Backup; 00404 } 00405 break; 00406 } 00407 00408 case ISD::OR: { 00409 if (!Available) { 00410 X86ISelAddressMode Backup = AM; 00411 // Look for (x << c1) | c2 where (c2 < c1) 00412 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(0)); 00413 if (CN && !MatchAddress(N.Val->getOperand(1), AM, false)) { 00414 if (AM.GV == NULL && AM.Disp == 0 && CN->getValue() < AM.Scale) { 00415 AM.Disp = CN->getValue(); 00416 return false; 00417 } 00418 } 00419 AM = Backup; 00420 CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1)); 00421 if (CN && !MatchAddress(N.Val->getOperand(0), AM, false)) { 00422 if (AM.GV == NULL && AM.Disp == 0 && CN->getValue() < AM.Scale) { 00423 AM.Disp = CN->getValue(); 00424 return false; 00425 } 00426 } 00427 AM = Backup; 00428 } 00429 break; 00430 } 00431 } 00432 00433 // Is the base register already occupied? 00434 if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) { 00435 // If so, check to see if the scale index register is set. 00436 if (AM.IndexReg.Val == 0) { 00437 AM.IndexReg = N; 00438 AM.Scale = 1; 00439 return false; 00440 } 00441 00442 // Otherwise, we cannot select it. 00443 return true; 00444 } 00445 00446 // Default, generate it as a register. 00447 AM.BaseType = X86ISelAddressMode::RegBase; 00448 AM.Base.Reg = N; 00449 return false; 00450 } 00451 00452 /// SelectAddr - returns true if it is able pattern match an addressing mode. 00453 /// It returns the operands which make up the maximal addressing mode it can 00454 /// match by reference. 00455 bool X86DAGToDAGISel::SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 00456 SDOperand &Index, SDOperand &Disp) { 00457 X86ISelAddressMode AM; 00458 if (MatchAddress(N, AM)) 00459 return false; 00460 00461 if (AM.BaseType == X86ISelAddressMode::RegBase) { 00462 if (!AM.Base.Reg.Val) 00463 AM.Base.Reg = CurDAG->getRegister(0, MVT::i32); 00464 } 00465 00466 if (!AM.IndexReg.Val) 00467 AM.IndexReg = CurDAG->getRegister(0, MVT::i32); 00468 00469 getAddressOperands(AM, Base, Scale, Index, Disp); 00470 00471 return true; 00472 } 00473 00474 /// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing 00475 /// mode it matches can be cost effectively emitted as an LEA instruction. 00476 bool X86DAGToDAGISel::SelectLEAAddr(SDOperand N, SDOperand &Base, 00477 SDOperand &Scale, 00478 SDOperand &Index, SDOperand &Disp) { 00479 X86ISelAddressMode AM; 00480 if (MatchAddress(N, AM)) 00481 return false; 00482 00483 unsigned Complexity = 0; 00484 if (AM.BaseType == X86ISelAddressMode::RegBase) 00485 if (AM.Base.Reg.Val) 00486 Complexity = 1; 00487 else 00488 AM.Base.Reg = CurDAG->getRegister(0, MVT::i32); 00489 else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase) 00490 Complexity = 4; 00491 00492 if (AM.IndexReg.Val) 00493 Complexity++; 00494 else 00495 AM.IndexReg = CurDAG->getRegister(0, MVT::i32); 00496 00497 if (AM.Scale > 2) 00498 Complexity += 2; 00499 // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg 00500 else if (AM.Scale > 1) 00501 Complexity++; 00502 00503 // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA 00504 // to a LEA. This is determined with some expermentation but is by no means 00505 // optimal (especially for code size consideration). LEA is nice because of 00506 // its three-address nature. Tweak the cost function again when we can run 00507 // convertToThreeAddress() at register allocation time. 00508 if (AM.GV || AM.CP) 00509 Complexity += 2; 00510 00511 if (AM.Disp && (AM.Base.Reg.Val || AM.IndexReg.Val)) 00512 Complexity++; 00513 00514 if (Complexity > 2) { 00515 getAddressOperands(AM, Base, Scale, Index, Disp); 00516 return true; 00517 } 00518 00519 return false; 00520 } 00521 00522 bool X86DAGToDAGISel::TryFoldLoad(SDOperand P, SDOperand N, 00523 SDOperand &Base, SDOperand &Scale, 00524 SDOperand &Index, SDOperand &Disp) { 00525 if (N.getOpcode() == ISD::LOAD && 00526 N.hasOneUse() && 00527 !CodeGenMap.count(N.getValue(0)) && 00528 (P.getNumOperands() == 1 || !isNonImmUse(P.Val, N.Val))) 00529 return SelectAddr(N.getOperand(1), Base, Scale, Index, Disp); 00530 return false; 00531 } 00532 00533 static bool isRegister0(SDOperand Op) { 00534 if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op)) 00535 return (R->getReg() == 0); 00536 return false; 00537 } 00538 00539 /// getGlobalBaseReg - Output the instructions required to put the 00540 /// base address to use for accessing globals into a register. 00541 /// 00542 SDOperand X86DAGToDAGISel::getGlobalBaseReg() { 00543 if (!GlobalBaseReg) { 00544 // Insert the set of GlobalBaseReg into the first MBB of the function 00545 MachineBasicBlock &FirstMBB = BB->getParent()->front(); 00546 MachineBasicBlock::iterator MBBI = FirstMBB.begin(); 00547 SSARegMap *RegMap = BB->getParent()->getSSARegMap(); 00548 // FIXME: when we get to LP64, we will need to create the appropriate 00549 // type of register here. 00550 GlobalBaseReg = RegMap->createVirtualRegister(X86::GR32RegisterClass); 00551 BuildMI(FirstMBB, MBBI, X86::MovePCtoStack, 0); 00552 BuildMI(FirstMBB, MBBI, X86::POP32r, 1, GlobalBaseReg); 00553 } 00554 return CurDAG->getRegister(GlobalBaseReg, MVT::i32); 00555 } 00556 00557 static SDNode *FindCallStartFromCall(SDNode *Node) { 00558 if (Node->getOpcode() == ISD::CALLSEQ_START) return Node; 00559 assert(Node->getOperand(0).getValueType() == MVT::Other && 00560 "Node doesn't have a token chain argument!"); 00561 return FindCallStartFromCall(Node->getOperand(0).Val); 00562 } 00563 00564 void X86DAGToDAGISel::Select(SDOperand &Result, SDOperand N) { 00565 SDNode *Node = N.Val; 00566 MVT::ValueType NVT = Node->getValueType(0); 00567 unsigned Opc, MOpc; 00568 unsigned Opcode = Node->getOpcode(); 00569 00570 #ifndef NDEBUG 00571 DEBUG(std::cerr << std::string(Indent, ' ')); 00572 DEBUG(std::cerr << "Selecting: "); 00573 DEBUG(Node->dump(CurDAG)); 00574 DEBUG(std::cerr << "\n"); 00575 Indent += 2; 00576 #endif 00577 00578 if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER) { 00579 Result = N; 00580 #ifndef NDEBUG 00581 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00582 DEBUG(std::cerr << "== "); 00583 DEBUG(Node->dump(CurDAG)); 00584 DEBUG(std::cerr << "\n"); 00585 Indent -= 2; 00586 #endif 00587 return; // Already selected. 00588 } 00589 00590 std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N); 00591 if (CGMI != CodeGenMap.end()) { 00592 Result = CGMI->second; 00593 #ifndef NDEBUG 00594 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00595 DEBUG(std::cerr << "== "); 00596 DEBUG(Result.Val->dump(CurDAG)); 00597 DEBUG(std::cerr << "\n"); 00598 Indent -= 2; 00599 #endif 00600 return; 00601 } 00602 00603 switch (Opcode) { 00604 default: break; 00605 case X86ISD::GlobalBaseReg: 00606 Result = getGlobalBaseReg(); 00607 return; 00608 00609 case ISD::ADD: { 00610 // Turn ADD X, c to MOV32ri X+c. This cannot be done with tblgen'd 00611 // code and is matched first so to prevent it from being turned into 00612 // LEA32r X+c. 00613 SDOperand N0 = N.getOperand(0); 00614 SDOperand N1 = N.getOperand(1); 00615 if (N.Val->getValueType(0) == MVT::i32 && 00616 N0.getOpcode() == X86ISD::Wrapper && 00617 N1.getOpcode() == ISD::Constant) { 00618 unsigned Offset = (unsigned)cast<ConstantSDNode>(N1)->getValue(); 00619 SDOperand C(0, 0); 00620 // TODO: handle ExternalSymbolSDNode. 00621 if (GlobalAddressSDNode *G = 00622 dyn_cast<GlobalAddressSDNode>(N0.getOperand(0))) { 00623 C = CurDAG->getTargetGlobalAddress(G->getGlobal(), MVT::i32, 00624 G->getOffset() + Offset); 00625 } else if (ConstantPoolSDNode *CP = 00626 dyn_cast<ConstantPoolSDNode>(N0.getOperand(0))) { 00627 C = CurDAG->getTargetConstantPool(CP->get(), MVT::i32, 00628 CP->getAlignment(), 00629 CP->getOffset()+Offset); 00630 } 00631 00632 if (C.Val) { 00633 if (N.Val->hasOneUse()) { 00634 Result = CurDAG->SelectNodeTo(N.Val, X86::MOV32ri, MVT::i32, C); 00635 } else { 00636 SDNode *ResNode = CurDAG->getTargetNode(X86::MOV32ri, MVT::i32, C); 00637 Result = CodeGenMap[N] = SDOperand(ResNode, 0); 00638 } 00639 return; 00640 } 00641 } 00642 00643 // Other cases are handled by auto-generated code. 00644 break; 00645 } 00646 00647 case ISD::MULHU: 00648 case ISD::MULHS: { 00649 if (Opcode == ISD::MULHU) 00650 switch (NVT) { 00651 default: assert(0 && "Unsupported VT!"); 00652 case MVT::i8: Opc = X86::MUL8r; MOpc = X86::MUL8m; break; 00653 case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break; 00654 case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break; 00655 } 00656 else 00657 switch (NVT) { 00658 default: assert(0 && "Unsupported VT!"); 00659 case MVT::i8: Opc = X86::IMUL8r; MOpc = X86::IMUL8m; break; 00660 case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break; 00661 case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break; 00662 } 00663 00664 unsigned LoReg, HiReg; 00665 switch (NVT) { 00666 default: assert(0 && "Unsupported VT!"); 00667 case MVT::i8: LoReg = X86::AL; HiReg = X86::AH; break; 00668 case MVT::i16: LoReg = X86::AX; HiReg = X86::DX; break; 00669 case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break; 00670 } 00671 00672 SDOperand N0 = Node->getOperand(0); 00673 SDOperand N1 = Node->getOperand(1); 00674 00675 bool foldedLoad = false; 00676 SDOperand Tmp0, Tmp1, Tmp2, Tmp3; 00677 foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 00678 // MULHU and MULHS are commmutative 00679 if (!foldedLoad) { 00680 foldedLoad = TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3); 00681 if (foldedLoad) { 00682 N0 = Node->getOperand(1); 00683 N1 = Node->getOperand(0); 00684 } 00685 } 00686 00687 SDOperand Chain; 00688 if (foldedLoad) 00689 Select(Chain, N1.getOperand(0)); 00690 else 00691 Chain = CurDAG->getEntryNode(); 00692 00693 SDOperand InFlag(0, 0); 00694 Select(N0, N0); 00695 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT), 00696 N0, InFlag); 00697 InFlag = Chain.getValue(1); 00698 00699 if (foldedLoad) { 00700 Select(Tmp0, Tmp0); 00701 Select(Tmp1, Tmp1); 00702 Select(Tmp2, Tmp2); 00703 Select(Tmp3, Tmp3); 00704 SDNode *CNode = 00705 CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1, 00706 Tmp2, Tmp3, Chain, InFlag); 00707 Chain = SDOperand(CNode, 0); 00708 InFlag = SDOperand(CNode, 1); 00709 } else { 00710 Select(N1, N1); 00711 InFlag = 00712 SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0); 00713 } 00714 00715 Result = CurDAG->getCopyFromReg(Chain, HiReg, NVT, InFlag); 00716 CodeGenMap[N.getValue(0)] = Result; 00717 if (foldedLoad) { 00718 CodeGenMap[N1.getValue(1)] = Result.getValue(1); 00719 AddHandleReplacement(N1.Val, 1, Result.Val, 1); 00720 } 00721 00722 #ifndef NDEBUG 00723 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00724 DEBUG(std::cerr << "== "); 00725 DEBUG(Result.Val->dump(CurDAG)); 00726 DEBUG(std::cerr << "\n"); 00727 Indent -= 2; 00728 #endif 00729 return; 00730 } 00731 00732 case ISD::SDIV: 00733 case ISD::UDIV: 00734 case ISD::SREM: 00735 case ISD::UREM: { 00736 bool isSigned = Opcode == ISD::SDIV || Opcode == ISD::SREM; 00737 bool isDiv = Opcode == ISD::SDIV || Opcode == ISD::UDIV; 00738 if (!isSigned) 00739 switch (NVT) { 00740 default: assert(0 && "Unsupported VT!"); 00741 case MVT::i8: Opc = X86::DIV8r; MOpc = X86::DIV8m; break; 00742 case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break; 00743 case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break; 00744 } 00745 else 00746 switch (NVT) { 00747 default: assert(0 && "Unsupported VT!"); 00748 case MVT::i8: Opc = X86::IDIV8r; MOpc = X86::IDIV8m; break; 00749 case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break; 00750 case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break; 00751 } 00752 00753 unsigned LoReg, HiReg; 00754 unsigned ClrOpcode, SExtOpcode; 00755 switch (NVT) { 00756 default: assert(0 && "Unsupported VT!"); 00757 case MVT::i8: 00758 LoReg = X86::AL; HiReg = X86::AH; 00759 ClrOpcode = X86::MOV8r0; 00760 SExtOpcode = X86::CBW; 00761 break; 00762 case MVT::i16: 00763 LoReg = X86::AX; HiReg = X86::DX; 00764 ClrOpcode = X86::MOV16r0; 00765 SExtOpcode = X86::CWD; 00766 break; 00767 case MVT::i32: 00768 LoReg = X86::EAX; HiReg = X86::EDX; 00769 ClrOpcode = X86::MOV32r0; 00770 SExtOpcode = X86::CDQ; 00771 break; 00772 } 00773 00774 SDOperand N0 = Node->getOperand(0); 00775 SDOperand N1 = Node->getOperand(1); 00776 00777 bool foldedLoad = false; 00778 SDOperand Tmp0, Tmp1, Tmp2, Tmp3; 00779 foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 00780 SDOperand Chain; 00781 if (foldedLoad) 00782 Select(Chain, N1.getOperand(0)); 00783 else 00784 Chain = CurDAG->getEntryNode(); 00785 00786 SDOperand InFlag(0, 0); 00787 Select(N0, N0); 00788 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT), 00789 N0, InFlag); 00790 InFlag = Chain.getValue(1); 00791 00792 if (isSigned) { 00793 // Sign extend the low part into the high part. 00794 InFlag = 00795 SDOperand(CurDAG->getTargetNode(SExtOpcode, MVT::Flag, InFlag), 0); 00796 } else { 00797 // Zero out the high part, effectively zero extending the input. 00798 SDOperand ClrNode = SDOperand(CurDAG->getTargetNode(ClrOpcode, NVT), 0); 00799 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(HiReg, NVT), 00800 ClrNode, InFlag); 00801 InFlag = Chain.getValue(1); 00802 } 00803 00804 if (foldedLoad) { 00805 Select(Tmp0, Tmp0); 00806 Select(Tmp1, Tmp1); 00807 Select(Tmp2, Tmp2); 00808 Select(Tmp3, Tmp3); 00809 SDNode *CNode = 00810 CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1, 00811 Tmp2, Tmp3, Chain, InFlag); 00812 Chain = SDOperand(CNode, 0); 00813 InFlag = SDOperand(CNode, 1); 00814 } else { 00815 Select(N1, N1); 00816 InFlag = 00817 SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0); 00818 } 00819 00820 Result = CurDAG->getCopyFromReg(Chain, isDiv ? LoReg : HiReg, 00821 NVT, InFlag); 00822 CodeGenMap[N.getValue(0)] = Result; 00823 if (foldedLoad) { 00824 CodeGenMap[N1.getValue(1)] = Result.getValue(1); 00825 AddHandleReplacement(N1.Val, 1, Result.Val, 1); 00826 } 00827 00828 #ifndef NDEBUG 00829 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00830 DEBUG(std::cerr << "== "); 00831 DEBUG(Result.Val->dump(CurDAG)); 00832 DEBUG(std::cerr << "\n"); 00833 Indent -= 2; 00834 #endif 00835 return; 00836 } 00837 00838 case ISD::TRUNCATE: { 00839 if (NVT == MVT::i8) { 00840 unsigned Opc2; 00841 MVT::ValueType VT; 00842 switch (Node->getOperand(0).getValueType()) { 00843 default: assert(0 && "Unknown truncate!"); 00844 case MVT::i16: 00845 Opc = X86::MOV16to16_; 00846 VT = MVT::i16; 00847 Opc2 = X86::TRUNC_GR16_GR8; 00848 break; 00849 case MVT::i32: 00850 Opc = X86::MOV32to32_; 00851 VT = MVT::i32; 00852 Opc2 = X86::TRUNC_GR32_GR8; 00853 break; 00854 } 00855 00856 SDOperand Tmp0, Tmp1; 00857 Select(Tmp0, Node->getOperand(0)); 00858 Tmp1 = SDOperand(CurDAG->getTargetNode(Opc, VT, Tmp0), 0); 00859 Result = CodeGenMap[N] = 00860 SDOperand(CurDAG->getTargetNode(Opc2, NVT, Tmp1), 0); 00861 00862 #ifndef NDEBUG 00863 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00864 DEBUG(std::cerr << "== "); 00865 DEBUG(Result.Val->dump(CurDAG)); 00866 DEBUG(std::cerr << "\n"); 00867 Indent -= 2; 00868 #endif 00869 return; 00870 } 00871 00872 break; 00873 } 00874 } 00875 00876 SelectCode(Result, N); 00877 #ifndef NDEBUG 00878 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00879 DEBUG(std::cerr << "=> "); 00880 DEBUG(Result.Val->dump(CurDAG)); 00881 DEBUG(std::cerr << "\n"); 00882 Indent -= 2; 00883 #endif 00884 } 00885 00886 bool X86DAGToDAGISel:: 00887 SelectInlineAsmMemoryOperand(const SDOperand &Op, char ConstraintCode, 00888 std::vector<SDOperand> &OutOps, SelectionDAG &DAG){ 00889 SDOperand Op0, Op1, Op2, Op3; 00890 switch (ConstraintCode) { 00891 case 'o': // offsetable ?? 00892 case 'v': // not offsetable ?? 00893 default: return true; 00894 case 'm': // memory 00895 if (!SelectAddr(Op, Op0, Op1, Op2, Op3)) 00896 return true; 00897 break; 00898 } 00899 00900 OutOps.resize(4); 00901 Select(OutOps[0], Op0); 00902 Select(OutOps[1], Op1); 00903 Select(OutOps[2], Op2); 00904 Select(OutOps[3], Op3); 00905 return false; 00906 } 00907 00908 /// createX86ISelDag - This pass converts a legalized DAG into a 00909 /// X86-specific DAG, ready for instruction scheduling. 00910 /// 00911 FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM) { 00912 return new X86DAGToDAGISel(TM); 00913 }