blob: 8bdd12329fbd9a3a57e9bb965beff67a8fbce662 [file] [log] [blame]
Chris Lattner7a125372005-11-16 22:59:19 +00001//===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===//
Chris Lattnerc961eea2005-11-16 01:54:32 +00002//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Chris Lattnerc961eea2005-11-16 01:54:32 +00007//
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
Evan Cheng2ef88a02006-08-07 22:28:20 +000015#define DEBUG_TYPE "x86-isel"
Chris Lattnerc961eea2005-11-16 01:54:32 +000016#include "X86.h"
Evan Cheng8700e142006-01-11 06:09:51 +000017#include "X86InstrBuilder.h"
Evan Cheng0475ab52008-01-05 00:41:47 +000018#include "X86MachineFunctionInfo.h"
Chris Lattner92cb0af2006-01-11 01:15:34 +000019#include "X86RegisterInfo.h"
Chris Lattnerc961eea2005-11-16 01:54:32 +000020#include "X86Subtarget.h"
Evan Chengc4c62572006-03-13 23:20:37 +000021#include "X86TargetMachine.h"
Chris Lattner92cb0af2006-01-11 01:15:34 +000022#include "llvm/Instructions.h"
Chris Lattner420736d2006-03-25 06:47:10 +000023#include "llvm/Intrinsics.h"
Chris Lattner92cb0af2006-01-11 01:15:34 +000024#include "llvm/Support/CFG.h"
Reid Spencer7aa8a452007-01-12 23:22:14 +000025#include "llvm/Type.h"
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +000026#include "llvm/CodeGen/MachineConstantPool.h"
Chris Lattnerc961eea2005-11-16 01:54:32 +000027#include "llvm/CodeGen/MachineFunction.h"
Evan Chengaaca22c2006-01-10 20:26:56 +000028#include "llvm/CodeGen/MachineFrameInfo.h"
Chris Lattner92cb0af2006-01-11 01:15:34 +000029#include "llvm/CodeGen/MachineInstrBuilder.h"
Chris Lattner84bc5422007-12-31 04:13:23 +000030#include "llvm/CodeGen/MachineRegisterInfo.h"
Chris Lattnerc961eea2005-11-16 01:54:32 +000031#include "llvm/CodeGen/SelectionDAGISel.h"
32#include "llvm/Target/TargetMachine.h"
Evan Chengb7a75a52008-09-26 23:41:32 +000033#include "llvm/Target/TargetOptions.h"
Evan Cheng25ab6902006-09-08 06:48:29 +000034#include "llvm/Support/Debug.h"
Torok Edwindac237e2009-07-08 20:53:28 +000035#include "llvm/Support/ErrorHandling.h"
Evan Cheng25ab6902006-09-08 06:48:29 +000036#include "llvm/Support/MathExtras.h"
Torok Edwindac237e2009-07-08 20:53:28 +000037#include "llvm/Support/raw_ostream.h"
Evan Chengcdda25d2008-04-25 08:22:20 +000038#include "llvm/ADT/SmallPtrSet.h"
Chris Lattnerc961eea2005-11-16 01:54:32 +000039#include "llvm/ADT/Statistic.h"
40using namespace llvm;
41
Chris Lattner95b2c7d2006-12-19 22:59:26 +000042STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor");
43
Chris Lattnerc961eea2005-11-16 01:54:32 +000044//===----------------------------------------------------------------------===//
45// Pattern Matcher Implementation
46//===----------------------------------------------------------------------===//
47
48namespace {
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +000049 /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses
Dan Gohman475871a2008-07-27 21:46:04 +000050 /// SDValue's instead of register numbers for the leaves of the matched
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +000051 /// tree.
52 struct X86ISelAddressMode {
53 enum {
54 RegBase,
Chris Lattnerd74ea2b2006-05-24 17:04:05 +000055 FrameIndexBase
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +000056 } BaseType;
57
Dan Gohmanffce6f12010-04-29 23:30:41 +000058 // This is really a union, discriminated by BaseType!
59 SDValue Base_Reg;
60 int Base_FrameIndex;
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +000061
62 unsigned Scale;
Dan Gohman475871a2008-07-27 21:46:04 +000063 SDValue IndexReg;
Dan Gohman27cae7b2008-11-11 15:52:29 +000064 int32_t Disp;
Rafael Espindola094fad32009-04-08 21:14:34 +000065 SDValue Segment;
Dan Gohman46510a72010-04-15 01:51:59 +000066 const GlobalValue *GV;
67 const Constant *CP;
68 const BlockAddress *BlockAddr;
Evan Cheng25ab6902006-09-08 06:48:29 +000069 const char *ES;
70 int JT;
Evan Cheng51a9ed92006-02-25 10:09:08 +000071 unsigned Align; // CP alignment.
Chris Lattnerb8afeb92009-06-26 05:51:45 +000072 unsigned char SymbolFlags; // X86II::MO_*
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +000073
74 X86ISelAddressMode()
Dan Gohmanffce6f12010-04-29 23:30:41 +000075 : BaseType(RegBase), Base_FrameIndex(0), Scale(1), IndexReg(), Disp(0),
Chris Lattner43f44aa2009-11-01 03:25:03 +000076 Segment(), GV(0), CP(0), BlockAddr(0), ES(0), JT(-1), Align(0),
Dan Gohman79b765d2009-08-25 17:47:44 +000077 SymbolFlags(X86II::MO_NO_FLAG) {
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +000078 }
Dan Gohman2d0a1cc2009-02-07 00:43:41 +000079
80 bool hasSymbolicDisplacement() const {
Chris Lattner43f44aa2009-11-01 03:25:03 +000081 return GV != 0 || CP != 0 || ES != 0 || JT != -1 || BlockAddr != 0;
Dan Gohman2d0a1cc2009-02-07 00:43:41 +000082 }
Chris Lattner18c59872009-06-27 04:16:01 +000083
84 bool hasBaseOrIndexReg() const {
Dan Gohmanffce6f12010-04-29 23:30:41 +000085 return IndexReg.getNode() != 0 || Base_Reg.getNode() != 0;
Chris Lattner18c59872009-06-27 04:16:01 +000086 }
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 =
Dan Gohmanffce6f12010-04-29 23:30:41 +000093 dyn_cast_or_null<RegisterSDNode>(Base_Reg.getNode()))
Chris Lattner18c59872009-06-27 04:16:01 +000094 return RegNode->getReg() == X86::RIP;
95 return false;
96 }
97
98 void setBaseReg(SDValue Reg) {
99 BaseType = RegBase;
Dan Gohmanffce6f12010-04-29 23:30:41 +0000100 Base_Reg = Reg;
Chris Lattner18c59872009-06-27 04:16:01 +0000101 }
Dan Gohman2d0a1cc2009-02-07 00:43:41 +0000102
Dale Johannesen50dd1d02008-08-11 23:46:25 +0000103 void dump() {
David Greened7f4f242010-01-05 01:29:08 +0000104 dbgs() << "X86ISelAddressMode " << this << '\n';
Dan Gohmanffce6f12010-04-29 23:30:41 +0000105 dbgs() << "Base_Reg ";
106 if (Base_Reg.getNode() != 0)
107 Base_Reg.getNode()->dump();
Bill Wendling12321672009-08-07 21:33:25 +0000108 else
David Greened7f4f242010-01-05 01:29:08 +0000109 dbgs() << "nul";
Dan Gohmanffce6f12010-04-29 23:30:41 +0000110 dbgs() << " Base.FrameIndex " << Base_FrameIndex << '\n'
Benjamin Kramer072a56e2009-08-23 11:52:17 +0000111 << " Scale" << Scale << '\n'
112 << "IndexReg ";
Bill Wendling12321672009-08-07 21:33:25 +0000113 if (IndexReg.getNode() != 0)
114 IndexReg.getNode()->dump();
115 else
David Greened7f4f242010-01-05 01:29:08 +0000116 dbgs() << "nul";
117 dbgs() << " Disp " << Disp << '\n'
Benjamin Kramer072a56e2009-08-23 11:52:17 +0000118 << "GV ";
Bill Wendling12321672009-08-07 21:33:25 +0000119 if (GV)
120 GV->dump();
121 else
David Greened7f4f242010-01-05 01:29:08 +0000122 dbgs() << "nul";
123 dbgs() << " CP ";
Bill Wendling12321672009-08-07 21:33:25 +0000124 if (CP)
125 CP->dump();
126 else
David Greened7f4f242010-01-05 01:29:08 +0000127 dbgs() << "nul";
128 dbgs() << '\n'
Benjamin Kramer072a56e2009-08-23 11:52:17 +0000129 << "ES ";
Bill Wendling12321672009-08-07 21:33:25 +0000130 if (ES)
David Greened7f4f242010-01-05 01:29:08 +0000131 dbgs() << ES;
Bill Wendling12321672009-08-07 21:33:25 +0000132 else
David Greened7f4f242010-01-05 01:29:08 +0000133 dbgs() << "nul";
134 dbgs() << " JT" << JT << " Align" << Align << '\n';
Dale Johannesen50dd1d02008-08-11 23:46:25 +0000135 }
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000136 };
137}
138
139namespace {
Chris Lattnerc961eea2005-11-16 01:54:32 +0000140 //===--------------------------------------------------------------------===//
141 /// ISel - X86 specific code to select X86 machine instructions for
142 /// SelectionDAG operations.
143 ///
Nick Lewycky6726b6d2009-10-25 06:33:48 +0000144 class X86DAGToDAGISel : public SelectionDAGISel {
Chris Lattnerc961eea2005-11-16 01:54:32 +0000145 /// X86Lowering - This object fully describes how to lower LLVM code to an
146 /// X86-specific SelectionDAG.
Dan Gohmand858e902010-04-17 15:26:15 +0000147 const X86TargetLowering &X86Lowering;
Chris Lattnerc961eea2005-11-16 01:54:32 +0000148
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;
Evan Cheng7ccced62006-02-18 00:15:05 +0000152
Evan Chengb7a75a52008-09-26 23:41:32 +0000153 /// OptForSize - If true, selector should try to optimize for code size
154 /// instead of performance.
155 bool OptForSize;
156
Chris Lattnerc961eea2005-11-16 01:54:32 +0000157 public:
Bill Wendling98a366d2009-04-29 23:29:43 +0000158 explicit X86DAGToDAGISel(X86TargetMachine &tm, CodeGenOpt::Level OptLevel)
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +0000159 : SelectionDAGISel(tm, OptLevel),
Dan Gohmanc5534622009-06-03 20:20:00 +0000160 X86Lowering(*tm.getTargetLowering()),
161 Subtarget(&tm.getSubtarget<X86Subtarget>()),
Devang Patel4ae641f2008-10-01 23:18:38 +0000162 OptForSize(false) {}
Chris Lattnerc961eea2005-11-16 01:54:32 +0000163
164 virtual const char *getPassName() const {
165 return "X86 DAG->DAG Instruction Selection";
166 }
167
Dan Gohman64652652010-04-14 20:17:22 +0000168 virtual void EmitFunctionEntryCode();
Anton Korobeynikov2fe12592007-09-25 21:52:30 +0000169
Evan Cheng014bf212010-02-15 19:41:07 +0000170 virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
171
Chris Lattner7c306da2010-03-02 06:34:30 +0000172 virtual void PreprocessISelDAG();
173
Chris Lattnerc961eea2005-11-16 01:54:32 +0000174// Include the pieces autogenerated from the target description.
175#include "X86GenDAGISel.inc"
176
177 private:
Dan Gohmaneeb3a002010-01-05 01:24:18 +0000178 SDNode *Select(SDNode *N);
Dale Johannesen48c1bc22008-10-02 18:53:47 +0000179 SDNode *SelectAtomic64(SDNode *Node, unsigned Opc);
Owen Andersone50ed302009-08-10 22:56:29 +0000180 SDNode *SelectAtomicLoadAdd(SDNode *Node, EVT NVT);
Chris Lattnerc961eea2005-11-16 01:54:32 +0000181
Rafael Espindola094fad32009-04-08 21:14:34 +0000182 bool MatchSegmentBaseAddress(SDValue N, X86ISelAddressMode &AM);
183 bool MatchLoad(SDValue N, X86ISelAddressMode &AM);
Rafael Espindola49a168d2009-04-12 21:55:03 +0000184 bool MatchWrapper(SDValue N, X86ISelAddressMode &AM);
Dan Gohman41d0b9d2009-07-22 23:26:55 +0000185 bool MatchAddress(SDValue N, X86ISelAddressMode &AM);
186 bool MatchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
187 unsigned Depth);
Rafael Espindola523249f2009-03-31 16:16:57 +0000188 bool MatchAddressBase(SDValue N, X86ISelAddressMode &AM);
Dan Gohmaneeb3a002010-01-05 01:24:18 +0000189 bool SelectAddr(SDNode *Op, SDValue N, SDValue &Base,
Rafael Espindola094fad32009-04-08 21:14:34 +0000190 SDValue &Scale, SDValue &Index, SDValue &Disp,
191 SDValue &Segment);
Dan Gohmaneeb3a002010-01-05 01:24:18 +0000192 bool SelectLEAAddr(SDNode *Op, SDValue N, SDValue &Base,
Dan Gohman475871a2008-07-27 21:46:04 +0000193 SDValue &Scale, SDValue &Index, SDValue &Disp);
Dan Gohmaneeb3a002010-01-05 01:24:18 +0000194 bool SelectTLSADDRAddr(SDNode *Op, SDValue N, SDValue &Base,
Chris Lattner5c0b16d2009-06-20 20:38:48 +0000195 SDValue &Scale, SDValue &Index, SDValue &Disp);
Chris Lattnere60f7b42010-03-01 22:51:11 +0000196 bool SelectScalarSSELoad(SDNode *Root, SDValue N,
Chris Lattner92d3ada2010-02-16 22:35:06 +0000197 SDValue &Base, SDValue &Scale,
Dan Gohman475871a2008-07-27 21:46:04 +0000198 SDValue &Index, SDValue &Disp,
Rafael Espindola094fad32009-04-08 21:14:34 +0000199 SDValue &Segment,
Chris Lattnera170b5e2010-02-21 03:17:59 +0000200 SDValue &NodeWithChain);
201
Dan Gohmaneeb3a002010-01-05 01:24:18 +0000202 bool TryFoldLoad(SDNode *P, SDValue N,
Dan Gohman475871a2008-07-27 21:46:04 +0000203 SDValue &Base, SDValue &Scale,
Rafael Espindola094fad32009-04-08 21:14:34 +0000204 SDValue &Index, SDValue &Disp,
205 SDValue &Segment);
Chris Lattner7c306da2010-03-02 06:34:30 +0000206
Chris Lattnerc0bad572006-06-08 18:03:49 +0000207 /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
208 /// inline asm expressions.
Dan Gohman475871a2008-07-27 21:46:04 +0000209 virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
Chris Lattnerc0bad572006-06-08 18:03:49 +0000210 char ConstraintCode,
Dan Gohmanf350b272008-08-23 02:25:05 +0000211 std::vector<SDValue> &OutOps);
Chris Lattnerc0bad572006-06-08 18:03:49 +0000212
Anton Korobeynikov2fe12592007-09-25 21:52:30 +0000213 void EmitSpecialCodeForMain(MachineBasicBlock *BB, MachineFrameInfo *MFI);
214
Dan Gohman475871a2008-07-27 21:46:04 +0000215 inline void getAddressOperands(X86ISelAddressMode &AM, SDValue &Base,
216 SDValue &Scale, SDValue &Index,
Rafael Espindola094fad32009-04-08 21:14:34 +0000217 SDValue &Disp, SDValue &Segment) {
Evan Chenge5280532005-12-12 21:49:40 +0000218 Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ?
Dan Gohmanffce6f12010-04-29 23:30:41 +0000219 CurDAG->getTargetFrameIndex(AM.Base_FrameIndex, TLI.getPointerTy()) :
220 AM.Base_Reg;
Evan Chengbdce7b42005-12-17 09:13:43 +0000221 Scale = getI8Imm(AM.Scale);
Evan Chenge5280532005-12-12 21:49:40 +0000222 Index = AM.IndexReg;
Evan Cheng25ab6902006-09-08 06:48:29 +0000223 // These are 32-bit even in 64-bit mode since RIP relative offset
224 // is 32-bit.
225 if (AM.GV)
Owen Anderson825b72b2009-08-11 20:47:22 +0000226 Disp = CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp,
Chris Lattnerb8afeb92009-06-26 05:51:45 +0000227 AM.SymbolFlags);
Evan Cheng25ab6902006-09-08 06:48:29 +0000228 else if (AM.CP)
Owen Anderson825b72b2009-08-11 20:47:22 +0000229 Disp = CurDAG->getTargetConstantPool(AM.CP, MVT::i32,
Chris Lattnerb8afeb92009-06-26 05:51:45 +0000230 AM.Align, AM.Disp, AM.SymbolFlags);
Evan Cheng25ab6902006-09-08 06:48:29 +0000231 else if (AM.ES)
Owen Anderson825b72b2009-08-11 20:47:22 +0000232 Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i32, AM.SymbolFlags);
Evan Cheng25ab6902006-09-08 06:48:29 +0000233 else if (AM.JT != -1)
Owen Anderson825b72b2009-08-11 20:47:22 +0000234 Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i32, AM.SymbolFlags);
Chris Lattner43f44aa2009-11-01 03:25:03 +0000235 else if (AM.BlockAddr)
Dan Gohman29cbade2009-11-20 23:18:13 +0000236 Disp = CurDAG->getBlockAddress(AM.BlockAddr, MVT::i32,
237 true, AM.SymbolFlags);
Evan Cheng25ab6902006-09-08 06:48:29 +0000238 else
Owen Anderson825b72b2009-08-11 20:47:22 +0000239 Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i32);
Rafael Espindola094fad32009-04-08 21:14:34 +0000240
241 if (AM.Segment.getNode())
242 Segment = AM.Segment;
243 else
Owen Anderson825b72b2009-08-11 20:47:22 +0000244 Segment = CurDAG->getRegister(0, MVT::i32);
Evan Chenge5280532005-12-12 21:49:40 +0000245 }
246
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000247 /// getI8Imm - Return a target constant with the specified value, of type
248 /// i8.
Dan Gohman475871a2008-07-27 21:46:04 +0000249 inline SDValue getI8Imm(unsigned Imm) {
Owen Anderson825b72b2009-08-11 20:47:22 +0000250 return CurDAG->getTargetConstant(Imm, MVT::i8);
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000251 }
252
Chris Lattnerc961eea2005-11-16 01:54:32 +0000253 /// getI16Imm - Return a target constant with the specified value, of type
254 /// i16.
Dan Gohman475871a2008-07-27 21:46:04 +0000255 inline SDValue getI16Imm(unsigned Imm) {
Owen Anderson825b72b2009-08-11 20:47:22 +0000256 return CurDAG->getTargetConstant(Imm, MVT::i16);
Chris Lattnerc961eea2005-11-16 01:54:32 +0000257 }
258
259 /// getI32Imm - Return a target constant with the specified value, of type
260 /// i32.
Dan Gohman475871a2008-07-27 21:46:04 +0000261 inline SDValue getI32Imm(unsigned Imm) {
Owen Anderson825b72b2009-08-11 20:47:22 +0000262 return CurDAG->getTargetConstant(Imm, MVT::i32);
Chris Lattnerc961eea2005-11-16 01:54:32 +0000263 }
Evan Chengf597dc72006-02-10 22:24:32 +0000264
Dan Gohman8b746962008-09-23 18:22:58 +0000265 /// getGlobalBaseReg - Return an SDNode that returns the value of
266 /// the global base register. Output instructions required to
267 /// initialize the global base register, if necessary.
268 ///
Evan Cheng9ade2182006-08-26 05:34:46 +0000269 SDNode *getGlobalBaseReg();
Evan Cheng7ccced62006-02-18 00:15:05 +0000270
Dan Gohmanc5534622009-06-03 20:20:00 +0000271 /// getTargetMachine - Return a reference to the TargetMachine, casted
272 /// to the target-specific type.
273 const X86TargetMachine &getTargetMachine() {
274 return static_cast<const X86TargetMachine &>(TM);
275 }
276
277 /// getInstrInfo - Return a reference to the TargetInstrInfo, casted
278 /// to the target-specific type.
279 const X86InstrInfo *getInstrInfo() {
280 return getTargetMachine().getInstrInfo();
281 }
Chris Lattnerc961eea2005-11-16 01:54:32 +0000282 };
283}
284
Evan Chengf4b4c412006-08-08 00:31:00 +0000285
Evan Cheng014bf212010-02-15 19:41:07 +0000286bool
287X86DAGToDAGISel::IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const {
Bill Wendling98a366d2009-04-29 23:29:43 +0000288 if (OptLevel == CodeGenOpt::None) return false;
Evan Cheng27e1fe92006-10-14 08:33:25 +0000289
Evan Cheng014bf212010-02-15 19:41:07 +0000290 if (!N.hasOneUse())
291 return false;
292
293 if (N.getOpcode() != ISD::LOAD)
294 return true;
295
296 // If N is a load, do additional profitability checks.
297 if (U == Root) {
Evan Cheng884c70c2008-11-27 00:49:46 +0000298 switch (U->getOpcode()) {
299 default: break;
Dan Gohman9ef51c82010-01-04 20:51:50 +0000300 case X86ISD::ADD:
301 case X86ISD::SUB:
302 case X86ISD::AND:
303 case X86ISD::XOR:
304 case X86ISD::OR:
Evan Cheng884c70c2008-11-27 00:49:46 +0000305 case ISD::ADD:
306 case ISD::ADDC:
307 case ISD::ADDE:
308 case ISD::AND:
309 case ISD::OR:
310 case ISD::XOR: {
Rafael Espindoladbcfb302009-04-10 10:09:34 +0000311 SDValue Op1 = U->getOperand(1);
312
Evan Cheng884c70c2008-11-27 00:49:46 +0000313 // If the other operand is a 8-bit immediate we should fold the immediate
314 // instead. This reduces code size.
315 // e.g.
316 // movl 4(%esp), %eax
317 // addl $4, %eax
318 // vs.
319 // movl $4, %eax
320 // addl 4(%esp), %eax
321 // The former is 2 bytes shorter. In case where the increment is 1, then
322 // the saving can be 4 bytes (by using incl %eax).
Rafael Espindoladbcfb302009-04-10 10:09:34 +0000323 if (ConstantSDNode *Imm = dyn_cast<ConstantSDNode>(Op1))
Dan Gohman9a49d312009-03-14 02:07:16 +0000324 if (Imm->getAPIntValue().isSignedIntN(8))
325 return false;
Rafael Espindoladbcfb302009-04-10 10:09:34 +0000326
327 // If the other operand is a TLS address, we should fold it instead.
328 // This produces
329 // movl %gs:0, %eax
330 // leal i@NTPOFF(%eax), %eax
331 // instead of
332 // movl $i@NTPOFF, %eax
333 // addl %gs:0, %eax
334 // if the block also has an access to a second TLS address this will save
335 // a load.
336 // FIXME: This is probably also true for non TLS addresses.
337 if (Op1.getOpcode() == X86ISD::Wrapper) {
338 SDValue Val = Op1.getOperand(0);
339 if (Val.getOpcode() == ISD::TargetGlobalTLSAddress)
340 return false;
341 }
Evan Cheng884c70c2008-11-27 00:49:46 +0000342 }
343 }
Evan Cheng014bf212010-02-15 19:41:07 +0000344 }
345
346 return true;
347}
348
Evan Chengf48ef032010-03-14 03:48:46 +0000349/// MoveBelowCallOrigChain - Replace the original chain operand of the call with
350/// load's chain operand and move load below the call's chain operand.
351static void MoveBelowOrigChain(SelectionDAG *CurDAG, SDValue Load,
352 SDValue Call, SDValue OrigChain) {
Evan Chengab6c3bb2008-08-25 21:27:18 +0000353 SmallVector<SDValue, 8> Ops;
Evan Chengf48ef032010-03-14 03:48:46 +0000354 SDValue Chain = OrigChain.getOperand(0);
Evan Cheng5b2e5892009-01-26 18:43:34 +0000355 if (Chain.getNode() == Load.getNode())
356 Ops.push_back(Load.getOperand(0));
357 else {
358 assert(Chain.getOpcode() == ISD::TokenFactor &&
Evan Chengf48ef032010-03-14 03:48:46 +0000359 "Unexpected chain operand");
Evan Cheng5b2e5892009-01-26 18:43:34 +0000360 for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i)
361 if (Chain.getOperand(i).getNode() == Load.getNode())
362 Ops.push_back(Load.getOperand(0));
363 else
364 Ops.push_back(Chain.getOperand(i));
365 SDValue NewChain =
Dale Johannesened2eee62009-02-06 01:31:28 +0000366 CurDAG->getNode(ISD::TokenFactor, Load.getDebugLoc(),
Owen Anderson825b72b2009-08-11 20:47:22 +0000367 MVT::Other, &Ops[0], Ops.size());
Evan Cheng5b2e5892009-01-26 18:43:34 +0000368 Ops.clear();
369 Ops.push_back(NewChain);
370 }
Evan Chengf48ef032010-03-14 03:48:46 +0000371 for (unsigned i = 1, e = OrigChain.getNumOperands(); i != e; ++i)
372 Ops.push_back(OrigChain.getOperand(i));
373 CurDAG->UpdateNodeOperands(OrigChain, &Ops[0], Ops.size());
Evan Chengab6c3bb2008-08-25 21:27:18 +0000374 CurDAG->UpdateNodeOperands(Load, Call.getOperand(0),
375 Load.getOperand(1), Load.getOperand(2));
376 Ops.clear();
Gabor Greifba36cb52008-08-28 21:40:38 +0000377 Ops.push_back(SDValue(Load.getNode(), 1));
378 for (unsigned i = 1, e = Call.getNode()->getNumOperands(); i != e; ++i)
Evan Chengab6c3bb2008-08-25 21:27:18 +0000379 Ops.push_back(Call.getOperand(i));
380 CurDAG->UpdateNodeOperands(Call, &Ops[0], Ops.size());
381}
382
383/// isCalleeLoad - Return true if call address is a load and it can be
384/// moved below CALLSEQ_START and the chains leading up to the call.
385/// Return the CALLSEQ_START by reference as a second output.
Evan Chengf48ef032010-03-14 03:48:46 +0000386/// In the case of a tail call, there isn't a callseq node between the call
387/// chain and the load.
388static bool isCalleeLoad(SDValue Callee, SDValue &Chain, bool HasCallSeq) {
Gabor Greifba36cb52008-08-28 21:40:38 +0000389 if (Callee.getNode() == Chain.getNode() || !Callee.hasOneUse())
Evan Chengab6c3bb2008-08-25 21:27:18 +0000390 return false;
Gabor Greifba36cb52008-08-28 21:40:38 +0000391 LoadSDNode *LD = dyn_cast<LoadSDNode>(Callee.getNode());
Evan Chengab6c3bb2008-08-25 21:27:18 +0000392 if (!LD ||
393 LD->isVolatile() ||
394 LD->getAddressingMode() != ISD::UNINDEXED ||
395 LD->getExtensionType() != ISD::NON_EXTLOAD)
396 return false;
397
398 // Now let's find the callseq_start.
Evan Chengf48ef032010-03-14 03:48:46 +0000399 while (HasCallSeq && Chain.getOpcode() != ISD::CALLSEQ_START) {
Evan Chengab6c3bb2008-08-25 21:27:18 +0000400 if (!Chain.hasOneUse())
401 return false;
402 Chain = Chain.getOperand(0);
403 }
Evan Chengf48ef032010-03-14 03:48:46 +0000404
405 if (!Chain.getNumOperands())
406 return false;
Evan Cheng5b2e5892009-01-26 18:43:34 +0000407 if (Chain.getOperand(0).getNode() == Callee.getNode())
408 return true;
409 if (Chain.getOperand(0).getOpcode() == ISD::TokenFactor &&
Dan Gohman1e038a82009-09-15 01:22:01 +0000410 Callee.getValue(1).isOperandOf(Chain.getOperand(0).getNode()) &&
411 Callee.getValue(1).hasOneUse())
Evan Cheng5b2e5892009-01-26 18:43:34 +0000412 return true;
413 return false;
Evan Chengab6c3bb2008-08-25 21:27:18 +0000414}
415
Chris Lattnerfb444af2010-03-02 23:12:51 +0000416void X86DAGToDAGISel::PreprocessISelDAG() {
Chris Lattner97d85342010-03-04 01:43:43 +0000417 // OptForSize is used in pattern predicates that isel is matching.
Chris Lattnerfb444af2010-03-02 23:12:51 +0000418 OptForSize = MF->getFunction()->hasFnAttr(Attribute::OptimizeForSize);
419
Dan Gohmanf350b272008-08-23 02:25:05 +0000420 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
421 E = CurDAG->allnodes_end(); I != E; ) {
Chris Lattnerd43d00c2008-01-24 08:07:48 +0000422 SDNode *N = I++; // Preincrement iterator to avoid invalidation issues.
Chris Lattnerfb444af2010-03-02 23:12:51 +0000423
Evan Chengf48ef032010-03-14 03:48:46 +0000424 if (OptLevel != CodeGenOpt::None &&
425 (N->getOpcode() == X86ISD::CALL ||
426 N->getOpcode() == X86ISD::TC_RETURN)) {
Chris Lattnerfb444af2010-03-02 23:12:51 +0000427 /// Also try moving call address load from outside callseq_start to just
428 /// before the call to allow it to be folded.
429 ///
430 /// [Load chain]
431 /// ^
432 /// |
433 /// [Load]
434 /// ^ ^
435 /// | |
436 /// / \--
437 /// / |
438 ///[CALLSEQ_START] |
439 /// ^ |
440 /// | |
441 /// [LOAD/C2Reg] |
442 /// | |
443 /// \ /
444 /// \ /
445 /// [CALL]
Evan Chengf48ef032010-03-14 03:48:46 +0000446 bool HasCallSeq = N->getOpcode() == X86ISD::CALL;
Chris Lattnerfb444af2010-03-02 23:12:51 +0000447 SDValue Chain = N->getOperand(0);
448 SDValue Load = N->getOperand(1);
Evan Chengf48ef032010-03-14 03:48:46 +0000449 if (!isCalleeLoad(Load, Chain, HasCallSeq))
Chris Lattnerfb444af2010-03-02 23:12:51 +0000450 continue;
Evan Chengf48ef032010-03-14 03:48:46 +0000451 MoveBelowOrigChain(CurDAG, Load, SDValue(N, 0), Chain);
Chris Lattnerfb444af2010-03-02 23:12:51 +0000452 ++NumLoadMoved;
453 continue;
454 }
455
456 // Lower fpround and fpextend nodes that target the FP stack to be store and
457 // load to the stack. This is a gross hack. We would like to simply mark
458 // these as being illegal, but when we do that, legalize produces these when
459 // it expands calls, then expands these in the same legalize pass. We would
460 // like dag combine to be able to hack on these between the call expansion
461 // and the node legalization. As such this pass basically does "really
462 // late" legalization of these inline with the X86 isel pass.
463 // FIXME: This should only happen when not compiled with -O0.
Chris Lattnerd43d00c2008-01-24 08:07:48 +0000464 if (N->getOpcode() != ISD::FP_ROUND && N->getOpcode() != ISD::FP_EXTEND)
465 continue;
466
467 // If the source and destination are SSE registers, then this is a legal
468 // conversion that should not be lowered.
Owen Andersone50ed302009-08-10 22:56:29 +0000469 EVT SrcVT = N->getOperand(0).getValueType();
470 EVT DstVT = N->getValueType(0);
Chris Lattnerd43d00c2008-01-24 08:07:48 +0000471 bool SrcIsSSE = X86Lowering.isScalarFPTypeInSSEReg(SrcVT);
472 bool DstIsSSE = X86Lowering.isScalarFPTypeInSSEReg(DstVT);
473 if (SrcIsSSE && DstIsSSE)
474 continue;
475
Chris Lattner6fa2f9c2008-03-09 07:05:32 +0000476 if (!SrcIsSSE && !DstIsSSE) {
477 // If this is an FPStack extension, it is a noop.
478 if (N->getOpcode() == ISD::FP_EXTEND)
479 continue;
480 // If this is a value-preserving FPStack truncation, it is a noop.
481 if (N->getConstantOperandVal(1))
482 continue;
483 }
484
Chris Lattnerd43d00c2008-01-24 08:07:48 +0000485 // Here we could have an FP stack truncation or an FPStack <-> SSE convert.
486 // FPStack has extload and truncstore. SSE can fold direct loads into other
487 // operations. Based on this, decide what we want to do.
Owen Andersone50ed302009-08-10 22:56:29 +0000488 EVT MemVT;
Chris Lattnerd43d00c2008-01-24 08:07:48 +0000489 if (N->getOpcode() == ISD::FP_ROUND)
490 MemVT = DstVT; // FP_ROUND must use DstVT, we can't do a 'trunc load'.
491 else
492 MemVT = SrcIsSSE ? SrcVT : DstVT;
493
Dan Gohmanf350b272008-08-23 02:25:05 +0000494 SDValue MemTmp = CurDAG->CreateStackTemporary(MemVT);
Dale Johannesend8392542009-02-03 21:48:12 +0000495 DebugLoc dl = N->getDebugLoc();
Chris Lattnerd43d00c2008-01-24 08:07:48 +0000496
497 // FIXME: optimize the case where the src/dest is a load or store?
Dale Johannesend8392542009-02-03 21:48:12 +0000498 SDValue Store = CurDAG->getTruncStore(CurDAG->getEntryNode(), dl,
Dan Gohmanf350b272008-08-23 02:25:05 +0000499 N->getOperand(0),
David Greenedb8d9892010-02-15 16:57:43 +0000500 MemTmp, NULL, 0, MemVT,
501 false, false, 0);
Dale Johannesend8392542009-02-03 21:48:12 +0000502 SDValue Result = CurDAG->getExtLoad(ISD::EXTLOAD, dl, DstVT, Store, MemTmp,
David Greenedb8d9892010-02-15 16:57:43 +0000503 NULL, 0, MemVT, false, false, 0);
Chris Lattnerd43d00c2008-01-24 08:07:48 +0000504
505 // We're about to replace all uses of the FP_ROUND/FP_EXTEND with the
506 // extload we created. This will cause general havok on the dag because
507 // anything below the conversion could be folded into other existing nodes.
508 // To avoid invalidating 'I', back it up to the convert node.
509 --I;
Dan Gohmanf350b272008-08-23 02:25:05 +0000510 CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Result);
Chris Lattnerd43d00c2008-01-24 08:07:48 +0000511
512 // Now that we did that, the node is dead. Increment the iterator to the
513 // next node to process, then delete N.
514 ++I;
Dan Gohmanf350b272008-08-23 02:25:05 +0000515 CurDAG->DeleteNode(N);
Chris Lattnerd43d00c2008-01-24 08:07:48 +0000516 }
517}
518
Chris Lattnerc961eea2005-11-16 01:54:32 +0000519
Anton Korobeynikov2fe12592007-09-25 21:52:30 +0000520/// EmitSpecialCodeForMain - Emit any code that needs to be executed only in
521/// the main function.
522void X86DAGToDAGISel::EmitSpecialCodeForMain(MachineBasicBlock *BB,
523 MachineFrameInfo *MFI) {
524 const TargetInstrInfo *TII = TM.getInstrInfo();
525 if (Subtarget->isTargetCygMing())
Chris Lattnerc7f3ace2010-04-02 20:16:16 +0000526 BuildMI(BB, DebugLoc(),
Dale Johannesen8d13f8f2009-02-13 02:33:27 +0000527 TII->get(X86::CALLpcrel32)).addExternalSymbol("__main");
Anton Korobeynikov2fe12592007-09-25 21:52:30 +0000528}
529
Dan Gohman64652652010-04-14 20:17:22 +0000530void X86DAGToDAGISel::EmitFunctionEntryCode() {
Anton Korobeynikov2fe12592007-09-25 21:52:30 +0000531 // If this is main, emit special code for main.
Dan Gohman64652652010-04-14 20:17:22 +0000532 if (const Function *Fn = MF->getFunction())
533 if (Fn->hasExternalLinkage() && Fn->getName() == "main")
534 EmitSpecialCodeForMain(MF->begin(), MF->getFrameInfo());
Anton Korobeynikov2fe12592007-09-25 21:52:30 +0000535}
536
Rafael Espindola094fad32009-04-08 21:14:34 +0000537
538bool X86DAGToDAGISel::MatchSegmentBaseAddress(SDValue N,
539 X86ISelAddressMode &AM) {
540 assert(N.getOpcode() == X86ISD::SegmentBaseAddress);
541 SDValue Segment = N.getOperand(0);
542
543 if (AM.Segment.getNode() == 0) {
544 AM.Segment = Segment;
545 return false;
546 }
547
548 return true;
549}
550
551bool X86DAGToDAGISel::MatchLoad(SDValue N, X86ISelAddressMode &AM) {
552 // This optimization is valid because the GNU TLS model defines that
553 // gs:0 (or fs:0 on X86-64) contains its own address.
554 // For more information see http://people.redhat.com/drepper/tls.pdf
555
556 SDValue Address = N.getOperand(1);
557 if (Address.getOpcode() == X86ISD::SegmentBaseAddress &&
558 !MatchSegmentBaseAddress (Address, AM))
559 return false;
560
561 return true;
562}
563
Chris Lattner18c59872009-06-27 04:16:01 +0000564/// MatchWrapper - Try to match X86ISD::Wrapper and X86ISD::WrapperRIP nodes
565/// into an addressing mode. These wrap things that will resolve down into a
566/// symbol reference. If no match is possible, this returns true, otherwise it
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000567/// returns false.
Rafael Espindola49a168d2009-04-12 21:55:03 +0000568bool X86DAGToDAGISel::MatchWrapper(SDValue N, X86ISelAddressMode &AM) {
Chris Lattner18c59872009-06-27 04:16:01 +0000569 // If the addressing mode already has a symbol as the displacement, we can
570 // never match another symbol.
Rafael Espindola49a168d2009-04-12 21:55:03 +0000571 if (AM.hasSymbolicDisplacement())
572 return true;
Rafael Espindola49a168d2009-04-12 21:55:03 +0000573
574 SDValue N0 = N.getOperand(0);
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000575 CodeModel::Model M = TM.getCodeModel();
576
Chris Lattner18c59872009-06-27 04:16:01 +0000577 // Handle X86-64 rip-relative addresses. We check this before checking direct
578 // folding because RIP is preferable to non-RIP accesses.
579 if (Subtarget->is64Bit() &&
580 // Under X86-64 non-small code model, GV (and friends) are 64-bits, so
581 // they cannot be folded into immediate fields.
582 // FIXME: This can be improved for kernel and other models?
Anton Korobeynikov25f1aa02009-08-21 15:41:56 +0000583 (M == CodeModel::Small || M == CodeModel::Kernel) &&
Chris Lattner18c59872009-06-27 04:16:01 +0000584 // Base and index reg must be 0 in order to use %rip as base and lowering
585 // must allow RIP.
586 !AM.hasBaseOrIndexReg() && N.getOpcode() == X86ISD::WrapperRIP) {
Chris Lattner18c59872009-06-27 04:16:01 +0000587 if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
588 int64_t Offset = AM.Disp + G->getOffset();
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000589 if (!X86::isOffsetSuitableForCodeModel(Offset, M)) return true;
Chris Lattner18c59872009-06-27 04:16:01 +0000590 AM.GV = G->getGlobal();
591 AM.Disp = Offset;
Chris Lattnerb8afeb92009-06-26 05:51:45 +0000592 AM.SymbolFlags = G->getTargetFlags();
Chris Lattner18c59872009-06-27 04:16:01 +0000593 } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
594 int64_t Offset = AM.Disp + CP->getOffset();
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000595 if (!X86::isOffsetSuitableForCodeModel(Offset, M)) return true;
Rafael Espindola49a168d2009-04-12 21:55:03 +0000596 AM.CP = CP->getConstVal();
597 AM.Align = CP->getAlignment();
Chris Lattner18c59872009-06-27 04:16:01 +0000598 AM.Disp = Offset;
Chris Lattner0b0deab2009-06-26 05:56:49 +0000599 AM.SymbolFlags = CP->getTargetFlags();
Chris Lattner18c59872009-06-27 04:16:01 +0000600 } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
601 AM.ES = S->getSymbol();
602 AM.SymbolFlags = S->getTargetFlags();
Chris Lattner43f44aa2009-11-01 03:25:03 +0000603 } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
Chris Lattner18c59872009-06-27 04:16:01 +0000604 AM.JT = J->getIndex();
605 AM.SymbolFlags = J->getTargetFlags();
Chris Lattner43f44aa2009-11-01 03:25:03 +0000606 } else {
607 AM.BlockAddr = cast<BlockAddressSDNode>(N0)->getBlockAddress();
Dan Gohman29cbade2009-11-20 23:18:13 +0000608 AM.SymbolFlags = cast<BlockAddressSDNode>(N0)->getTargetFlags();
Rafael Espindola49a168d2009-04-12 21:55:03 +0000609 }
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000610
Chris Lattner18c59872009-06-27 04:16:01 +0000611 if (N.getOpcode() == X86ISD::WrapperRIP)
Owen Anderson825b72b2009-08-11 20:47:22 +0000612 AM.setBaseReg(CurDAG->getRegister(X86::RIP, MVT::i64));
Rafael Espindola49a168d2009-04-12 21:55:03 +0000613 return false;
Chris Lattner18c59872009-06-27 04:16:01 +0000614 }
615
616 // Handle the case when globals fit in our immediate field: This is true for
617 // X86-32 always and X86-64 when in -static -mcmodel=small mode. In 64-bit
618 // mode, this results in a non-RIP-relative computation.
619 if (!Subtarget->is64Bit() ||
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000620 ((M == CodeModel::Small || M == CodeModel::Kernel) &&
Chris Lattner18c59872009-06-27 04:16:01 +0000621 TM.getRelocationModel() == Reloc::Static)) {
622 if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
623 AM.GV = G->getGlobal();
624 AM.Disp += G->getOffset();
625 AM.SymbolFlags = G->getTargetFlags();
626 } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
627 AM.CP = CP->getConstVal();
628 AM.Align = CP->getAlignment();
629 AM.Disp += CP->getOffset();
630 AM.SymbolFlags = CP->getTargetFlags();
631 } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
632 AM.ES = S->getSymbol();
633 AM.SymbolFlags = S->getTargetFlags();
Chris Lattner43f44aa2009-11-01 03:25:03 +0000634 } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
Chris Lattner18c59872009-06-27 04:16:01 +0000635 AM.JT = J->getIndex();
636 AM.SymbolFlags = J->getTargetFlags();
Chris Lattner43f44aa2009-11-01 03:25:03 +0000637 } else {
638 AM.BlockAddr = cast<BlockAddressSDNode>(N0)->getBlockAddress();
Dan Gohman29cbade2009-11-20 23:18:13 +0000639 AM.SymbolFlags = cast<BlockAddressSDNode>(N0)->getTargetFlags();
Chris Lattner18c59872009-06-27 04:16:01 +0000640 }
Rafael Espindola49a168d2009-04-12 21:55:03 +0000641 return false;
642 }
643
644 return true;
645}
646
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000647/// MatchAddress - Add the specified node to the specified addressing mode,
648/// returning true if it cannot be done. This just pattern matches for the
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000649/// addressing mode.
Dan Gohman41d0b9d2009-07-22 23:26:55 +0000650bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM) {
Dan Gohmane5408102010-06-18 01:24:29 +0000651 if (MatchAddressRecursively(N, AM, 0))
Dan Gohman41d0b9d2009-07-22 23:26:55 +0000652 return true;
653
654 // Post-processing: Convert lea(,%reg,2) to lea(%reg,%reg), which has
655 // a smaller encoding and avoids a scaled-index.
656 if (AM.Scale == 2 &&
657 AM.BaseType == X86ISelAddressMode::RegBase &&
Dan Gohmanffce6f12010-04-29 23:30:41 +0000658 AM.Base_Reg.getNode() == 0) {
659 AM.Base_Reg = AM.IndexReg;
Dan Gohman41d0b9d2009-07-22 23:26:55 +0000660 AM.Scale = 1;
661 }
662
Dan Gohmanef74e9b2009-08-20 18:23:44 +0000663 // Post-processing: Convert foo to foo(%rip), even in non-PIC mode,
664 // because it has a smaller encoding.
665 // TODO: Which other code models can use this?
666 if (TM.getCodeModel() == CodeModel::Small &&
667 Subtarget->is64Bit() &&
668 AM.Scale == 1 &&
669 AM.BaseType == X86ISelAddressMode::RegBase &&
Dan Gohmanffce6f12010-04-29 23:30:41 +0000670 AM.Base_Reg.getNode() == 0 &&
Dan Gohmanef74e9b2009-08-20 18:23:44 +0000671 AM.IndexReg.getNode() == 0 &&
Dan Gohman79b765d2009-08-25 17:47:44 +0000672 AM.SymbolFlags == X86II::MO_NO_FLAG &&
Dan Gohmanef74e9b2009-08-20 18:23:44 +0000673 AM.hasSymbolicDisplacement())
Dan Gohmanffce6f12010-04-29 23:30:41 +0000674 AM.Base_Reg = CurDAG->getRegister(X86::RIP, MVT::i64);
Dan Gohmanef74e9b2009-08-20 18:23:44 +0000675
Dan Gohman41d0b9d2009-07-22 23:26:55 +0000676 return false;
677}
678
Chris Lattnerd6139422010-04-20 23:18:40 +0000679/// isLogicallyAddWithConstant - Return true if this node is semantically an
680/// add of a value with a constantint.
681static bool isLogicallyAddWithConstant(SDValue V, SelectionDAG *CurDAG) {
682 // Check for (add x, Cst)
683 if (V->getOpcode() == ISD::ADD)
684 return isa<ConstantSDNode>(V->getOperand(1));
685
686 // Check for (or x, Cst), where Cst & x == 0.
687 if (V->getOpcode() != ISD::OR ||
688 !isa<ConstantSDNode>(V->getOperand(1)))
689 return false;
690
691 // Handle "X | C" as "X + C" iff X is known to have C bits clear.
692 ConstantSDNode *CN = cast<ConstantSDNode>(V->getOperand(1));
693
694 // Check to see if the LHS & C is zero.
695 return CurDAG->MaskedValueIsZero(V->getOperand(0), CN->getAPIntValue());
696}
697
Dan Gohman41d0b9d2009-07-22 23:26:55 +0000698bool X86DAGToDAGISel::MatchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
699 unsigned Depth) {
Dan Gohman6520e202008-10-18 02:06:02 +0000700 bool is64Bit = Subtarget->is64Bit();
Dale Johannesen6f38cb62009-02-07 19:59:05 +0000701 DebugLoc dl = N.getDebugLoc();
Bill Wendling12321672009-08-07 21:33:25 +0000702 DEBUG({
David Greened7f4f242010-01-05 01:29:08 +0000703 dbgs() << "MatchAddress: ";
Bill Wendling12321672009-08-07 21:33:25 +0000704 AM.dump();
705 });
Dan Gohmanbadb2d22007-08-13 20:03:06 +0000706 // Limit recursion.
707 if (Depth > 5)
Rafael Espindola523249f2009-03-31 16:16:57 +0000708 return MatchAddressBase(N, AM);
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000709
710 CodeModel::Model M = TM.getCodeModel();
711
Chris Lattner18c59872009-06-27 04:16:01 +0000712 // If this is already a %rip relative address, we can only merge immediates
713 // into it. Instead of handling this in every case, we handle it here.
Evan Cheng25ab6902006-09-08 06:48:29 +0000714 // RIP relative addressing: %rip + 32-bit displacement!
Chris Lattner18c59872009-06-27 04:16:01 +0000715 if (AM.isRIPRelative()) {
716 // FIXME: JumpTable and ExternalSymbol address currently don't like
717 // displacements. It isn't very important, but this should be fixed for
718 // consistency.
719 if (!AM.ES && AM.JT != -1) return true;
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000720
Chris Lattner18c59872009-06-27 04:16:01 +0000721 if (ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N)) {
722 int64_t Val = AM.Disp + Cst->getSExtValue();
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000723 if (X86::isOffsetSuitableForCodeModel(Val, M,
724 AM.hasSymbolicDisplacement())) {
Chris Lattner18c59872009-06-27 04:16:01 +0000725 AM.Disp = Val;
Evan Cheng25ab6902006-09-08 06:48:29 +0000726 return false;
727 }
728 }
729 return true;
730 }
731
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000732 switch (N.getOpcode()) {
733 default: break;
Evan Cheng25ab6902006-09-08 06:48:29 +0000734 case ISD::Constant: {
Dan Gohman27cae7b2008-11-11 15:52:29 +0000735 uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000736 if (!is64Bit ||
737 X86::isOffsetSuitableForCodeModel(AM.Disp + Val, M,
738 AM.hasSymbolicDisplacement())) {
Evan Cheng25ab6902006-09-08 06:48:29 +0000739 AM.Disp += Val;
740 return false;
741 }
742 break;
743 }
Evan Cheng51a9ed92006-02-25 10:09:08 +0000744
Rafael Espindola094fad32009-04-08 21:14:34 +0000745 case X86ISD::SegmentBaseAddress:
746 if (!MatchSegmentBaseAddress(N, AM))
747 return false;
748 break;
749
Rafael Espindola49a168d2009-04-12 21:55:03 +0000750 case X86ISD::Wrapper:
Chris Lattner18c59872009-06-27 04:16:01 +0000751 case X86ISD::WrapperRIP:
Rafael Espindola49a168d2009-04-12 21:55:03 +0000752 if (!MatchWrapper(N, AM))
753 return false;
Evan Cheng51a9ed92006-02-25 10:09:08 +0000754 break;
755
Rafael Espindola094fad32009-04-08 21:14:34 +0000756 case ISD::LOAD:
757 if (!MatchLoad(N, AM))
758 return false;
759 break;
760
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000761 case ISD::FrameIndex:
Gabor Greif93c53e52008-08-31 15:37:04 +0000762 if (AM.BaseType == X86ISelAddressMode::RegBase
Dan Gohmanffce6f12010-04-29 23:30:41 +0000763 && AM.Base_Reg.getNode() == 0) {
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000764 AM.BaseType = X86ISelAddressMode::FrameIndexBase;
Dan Gohmanffce6f12010-04-29 23:30:41 +0000765 AM.Base_FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000766 return false;
767 }
768 break;
Evan Chengec693f72005-12-08 02:01:35 +0000769
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000770 case ISD::SHL:
Chris Lattner18c59872009-06-27 04:16:01 +0000771 if (AM.IndexReg.getNode() != 0 || AM.Scale != 1)
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000772 break;
773
Gabor Greif93c53e52008-08-31 15:37:04 +0000774 if (ConstantSDNode
775 *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1))) {
Dan Gohmanf5aeb1a2008-09-12 16:56:44 +0000776 unsigned Val = CN->getZExtValue();
Dan Gohman41d0b9d2009-07-22 23:26:55 +0000777 // Note that we handle x<<1 as (,x,2) rather than (x,x) here so
778 // that the base operand remains free for further matching. If
779 // the base doesn't end up getting used, a post-processing step
780 // in MatchAddress turns (,x,2) into (x,x), which is cheaper.
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000781 if (Val == 1 || Val == 2 || Val == 3) {
782 AM.Scale = 1 << Val;
Gabor Greifba36cb52008-08-28 21:40:38 +0000783 SDValue ShVal = N.getNode()->getOperand(0);
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000784
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000785 // Okay, we know that we have a scale by now. However, if the scaled
786 // value is an add of something and a constant, we can fold the
787 // constant into the disp field here.
Chris Lattnerd6139422010-04-20 23:18:40 +0000788 if (isLogicallyAddWithConstant(ShVal, CurDAG)) {
Gabor Greifba36cb52008-08-28 21:40:38 +0000789 AM.IndexReg = ShVal.getNode()->getOperand(0);
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000790 ConstantSDNode *AddVal =
Gabor Greifba36cb52008-08-28 21:40:38 +0000791 cast<ConstantSDNode>(ShVal.getNode()->getOperand(1));
Evan Cheng8e278262009-01-17 07:09:27 +0000792 uint64_t Disp = AM.Disp + (AddVal->getSExtValue() << Val);
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000793 if (!is64Bit ||
794 X86::isOffsetSuitableForCodeModel(Disp, M,
795 AM.hasSymbolicDisplacement()))
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000796 AM.Disp = Disp;
797 else
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000798 AM.IndexReg = ShVal;
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000799 } else {
800 AM.IndexReg = ShVal;
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000801 }
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000802 return false;
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000803 }
804 break;
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000805 }
Evan Chengec693f72005-12-08 02:01:35 +0000806
Dan Gohman83688052007-10-22 20:22:24 +0000807 case ISD::SMUL_LOHI:
808 case ISD::UMUL_LOHI:
809 // A mul_lohi where we need the low part can be folded as a plain multiply.
Gabor Greif99a6cb92008-08-26 22:36:50 +0000810 if (N.getResNo() != 0) break;
Dan Gohman83688052007-10-22 20:22:24 +0000811 // FALL THROUGH
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000812 case ISD::MUL:
Evan Cheng73f24c92009-03-30 21:36:47 +0000813 case X86ISD::MUL_IMM:
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000814 // X*[3,5,9] -> X+X*[2,4,8]
Dan Gohman8be6bbe2008-11-05 04:14:16 +0000815 if (AM.BaseType == X86ISelAddressMode::RegBase &&
Dan Gohmanffce6f12010-04-29 23:30:41 +0000816 AM.Base_Reg.getNode() == 0 &&
Chris Lattner18c59872009-06-27 04:16:01 +0000817 AM.IndexReg.getNode() == 0) {
Gabor Greif93c53e52008-08-31 15:37:04 +0000818 if (ConstantSDNode
819 *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1)))
Dan Gohmanf5aeb1a2008-09-12 16:56:44 +0000820 if (CN->getZExtValue() == 3 || CN->getZExtValue() == 5 ||
821 CN->getZExtValue() == 9) {
822 AM.Scale = unsigned(CN->getZExtValue())-1;
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000823
Gabor Greifba36cb52008-08-28 21:40:38 +0000824 SDValue MulVal = N.getNode()->getOperand(0);
Dan Gohman475871a2008-07-27 21:46:04 +0000825 SDValue Reg;
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000826
827 // Okay, we know that we have a scale by now. However, if the scaled
828 // value is an add of something and a constant, we can fold the
829 // constant into the disp field here.
Gabor Greifba36cb52008-08-28 21:40:38 +0000830 if (MulVal.getNode()->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
831 isa<ConstantSDNode>(MulVal.getNode()->getOperand(1))) {
832 Reg = MulVal.getNode()->getOperand(0);
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000833 ConstantSDNode *AddVal =
Gabor Greifba36cb52008-08-28 21:40:38 +0000834 cast<ConstantSDNode>(MulVal.getNode()->getOperand(1));
Evan Cheng8e278262009-01-17 07:09:27 +0000835 uint64_t Disp = AM.Disp + AddVal->getSExtValue() *
Dan Gohmanf5aeb1a2008-09-12 16:56:44 +0000836 CN->getZExtValue();
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000837 if (!is64Bit ||
838 X86::isOffsetSuitableForCodeModel(Disp, M,
839 AM.hasSymbolicDisplacement()))
Evan Cheng25ab6902006-09-08 06:48:29 +0000840 AM.Disp = Disp;
841 else
Gabor Greifba36cb52008-08-28 21:40:38 +0000842 Reg = N.getNode()->getOperand(0);
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000843 } else {
Gabor Greifba36cb52008-08-28 21:40:38 +0000844 Reg = N.getNode()->getOperand(0);
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000845 }
846
Dan Gohmanffce6f12010-04-29 23:30:41 +0000847 AM.IndexReg = AM.Base_Reg = Reg;
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000848 return false;
849 }
Chris Lattner62412262007-02-04 20:18:17 +0000850 }
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000851 break;
852
Dan Gohman3cd90a12009-05-11 18:02:53 +0000853 case ISD::SUB: {
854 // Given A-B, if A can be completely folded into the address and
855 // the index field with the index field unused, use -B as the index.
856 // This is a win if a has multiple parts that can be folded into
857 // the address. Also, this saves a mov if the base register has
858 // other uses, since it avoids a two-address sub instruction, however
859 // it costs an additional mov if the index register has other uses.
860
Dan Gohmane5408102010-06-18 01:24:29 +0000861 // Add an artificial use to this node so that we can keep track of
862 // it if it gets CSE'd with a different node.
863 HandleSDNode Handle(N);
864
Dan Gohman3cd90a12009-05-11 18:02:53 +0000865 // Test if the LHS of the sub can be folded.
866 X86ISelAddressMode Backup = AM;
Dan Gohmane5408102010-06-18 01:24:29 +0000867 if (MatchAddressRecursively(N.getNode()->getOperand(0), AM, Depth+1)) {
Dan Gohman3cd90a12009-05-11 18:02:53 +0000868 AM = Backup;
869 break;
870 }
871 // Test if the index field is free for use.
Chris Lattner18c59872009-06-27 04:16:01 +0000872 if (AM.IndexReg.getNode() || AM.isRIPRelative()) {
Dan Gohman3cd90a12009-05-11 18:02:53 +0000873 AM = Backup;
874 break;
875 }
Evan Chengf3caa522010-03-17 23:58:35 +0000876
Dan Gohman3cd90a12009-05-11 18:02:53 +0000877 int Cost = 0;
Dan Gohmane5408102010-06-18 01:24:29 +0000878 SDValue RHS = Handle.getValue().getNode()->getOperand(1);
Dan Gohman3cd90a12009-05-11 18:02:53 +0000879 // If the RHS involves a register with multiple uses, this
880 // transformation incurs an extra mov, due to the neg instruction
881 // clobbering its operand.
882 if (!RHS.getNode()->hasOneUse() ||
883 RHS.getNode()->getOpcode() == ISD::CopyFromReg ||
884 RHS.getNode()->getOpcode() == ISD::TRUNCATE ||
885 RHS.getNode()->getOpcode() == ISD::ANY_EXTEND ||
886 (RHS.getNode()->getOpcode() == ISD::ZERO_EXTEND &&
Owen Anderson825b72b2009-08-11 20:47:22 +0000887 RHS.getNode()->getOperand(0).getValueType() == MVT::i32))
Dan Gohman3cd90a12009-05-11 18:02:53 +0000888 ++Cost;
889 // If the base is a register with multiple uses, this
890 // transformation may save a mov.
891 if ((AM.BaseType == X86ISelAddressMode::RegBase &&
Dan Gohmanffce6f12010-04-29 23:30:41 +0000892 AM.Base_Reg.getNode() &&
893 !AM.Base_Reg.getNode()->hasOneUse()) ||
Dan Gohman3cd90a12009-05-11 18:02:53 +0000894 AM.BaseType == X86ISelAddressMode::FrameIndexBase)
895 --Cost;
896 // If the folded LHS was interesting, this transformation saves
897 // address arithmetic.
898 if ((AM.hasSymbolicDisplacement() && !Backup.hasSymbolicDisplacement()) +
899 ((AM.Disp != 0) && (Backup.Disp == 0)) +
900 (AM.Segment.getNode() && !Backup.Segment.getNode()) >= 2)
901 --Cost;
902 // If it doesn't look like it may be an overall win, don't do it.
903 if (Cost >= 0) {
904 AM = Backup;
905 break;
906 }
907
908 // Ok, the transformation is legal and appears profitable. Go for it.
909 SDValue Zero = CurDAG->getConstant(0, N.getValueType());
910 SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
911 AM.IndexReg = Neg;
912 AM.Scale = 1;
913
914 // Insert the new nodes into the topological ordering.
915 if (Zero.getNode()->getNodeId() == -1 ||
916 Zero.getNode()->getNodeId() > N.getNode()->getNodeId()) {
917 CurDAG->RepositionNode(N.getNode(), Zero.getNode());
918 Zero.getNode()->setNodeId(N.getNode()->getNodeId());
919 }
920 if (Neg.getNode()->getNodeId() == -1 ||
921 Neg.getNode()->getNodeId() > N.getNode()->getNodeId()) {
922 CurDAG->RepositionNode(N.getNode(), Neg.getNode());
923 Neg.getNode()->setNodeId(N.getNode()->getNodeId());
924 }
925 return false;
926 }
927
Evan Cheng8e278262009-01-17 07:09:27 +0000928 case ISD::ADD: {
Dan Gohmane5408102010-06-18 01:24:29 +0000929 // Add an artificial use to this node so that we can keep track of
930 // it if it gets CSE'd with a different node.
931 HandleSDNode Handle(N);
932 SDValue LHS = Handle.getValue().getNode()->getOperand(0);
933 SDValue RHS = Handle.getValue().getNode()->getOperand(1);
934
Evan Cheng8e278262009-01-17 07:09:27 +0000935 X86ISelAddressMode Backup = AM;
Dan Gohmane5408102010-06-18 01:24:29 +0000936 if (!MatchAddressRecursively(LHS, AM, Depth+1) &&
937 !MatchAddressRecursively(RHS, AM, Depth+1))
938 return false;
939 AM = Backup;
940 LHS = Handle.getValue().getNode()->getOperand(0);
941 RHS = Handle.getValue().getNode()->getOperand(1);
Evan Chengf3caa522010-03-17 23:58:35 +0000942
943 // Try again after commuting the operands.
Dan Gohmane5408102010-06-18 01:24:29 +0000944 if (!MatchAddressRecursively(RHS, AM, Depth+1) &&
945 !MatchAddressRecursively(LHS, AM, Depth+1))
946 return false;
Evan Cheng8e278262009-01-17 07:09:27 +0000947 AM = Backup;
Dan Gohmane5408102010-06-18 01:24:29 +0000948 LHS = Handle.getValue().getNode()->getOperand(0);
949 RHS = Handle.getValue().getNode()->getOperand(1);
Dan Gohman77502c92009-03-13 02:25:09 +0000950
951 // If we couldn't fold both operands into the address at the same time,
952 // see if we can just put each operand into a register and fold at least
953 // the add.
954 if (AM.BaseType == X86ISelAddressMode::RegBase &&
Dan Gohmanffce6f12010-04-29 23:30:41 +0000955 !AM.Base_Reg.getNode() &&
Chris Lattner18c59872009-06-27 04:16:01 +0000956 !AM.IndexReg.getNode()) {
Dan Gohmane5408102010-06-18 01:24:29 +0000957 AM.Base_Reg = LHS;
958 AM.IndexReg = RHS;
Dan Gohman77502c92009-03-13 02:25:09 +0000959 AM.Scale = 1;
960 return false;
961 }
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +0000962 break;
Evan Cheng8e278262009-01-17 07:09:27 +0000963 }
Evan Chenge6ad27e2006-05-30 06:59:36 +0000964
Chris Lattner62412262007-02-04 20:18:17 +0000965 case ISD::OR:
966 // Handle "X | C" as "X + C" iff X is known to have C bits clear.
Chris Lattnerd6139422010-04-20 23:18:40 +0000967 if (isLogicallyAddWithConstant(N, CurDAG)) {
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000968 X86ISelAddressMode Backup = AM;
Chris Lattnerd6139422010-04-20 23:18:40 +0000969 ConstantSDNode *CN = cast<ConstantSDNode>(N.getOperand(1));
Dan Gohman27cae7b2008-11-11 15:52:29 +0000970 uint64_t Offset = CN->getSExtValue();
Evan Chengf3caa522010-03-17 23:58:35 +0000971
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000972 // Start with the LHS as an addr mode.
Dan Gohmane5408102010-06-18 01:24:29 +0000973 if (!MatchAddressRecursively(N.getOperand(0), AM, Depth+1) &&
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000974 // Address could not have picked a GV address for the displacement.
975 AM.GV == NULL &&
976 // On x86-64, the resultant disp must fit in 32-bits.
Anton Korobeynikovb5e01722009-08-05 23:01:26 +0000977 (!is64Bit ||
978 X86::isOffsetSuitableForCodeModel(AM.Disp + Offset, M,
Evan Chengf3caa522010-03-17 23:58:35 +0000979 AM.hasSymbolicDisplacement()))) {
Dan Gohman27cae7b2008-11-11 15:52:29 +0000980 AM.Disp += Offset;
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000981 return false;
Evan Chenge6ad27e2006-05-30 06:59:36 +0000982 }
Chris Lattner5aaddaa2007-12-08 07:22:58 +0000983 AM = Backup;
Evan Chenge6ad27e2006-05-30 06:59:36 +0000984 }
985 break;
Evan Cheng1314b002007-12-13 00:43:27 +0000986
987 case ISD::AND: {
Dan Gohman21e3dfb2009-04-13 16:09:41 +0000988 // Perform some heroic transforms on an and of a constant-count shift
989 // with a constant to enable use of the scaled offset field.
990
Dan Gohman475871a2008-07-27 21:46:04 +0000991 SDValue Shift = N.getOperand(0);
Dan Gohman21e3dfb2009-04-13 16:09:41 +0000992 if (Shift.getNumOperands() != 2) break;
Dan Gohman8be6bbe2008-11-05 04:14:16 +0000993
Evan Cheng1314b002007-12-13 00:43:27 +0000994 // Scale must not be used already.
Gabor Greifba36cb52008-08-28 21:40:38 +0000995 if (AM.IndexReg.getNode() != 0 || AM.Scale != 1) break;
Evan Chengbe3bf422008-02-07 08:53:49 +0000996
Dan Gohman21e3dfb2009-04-13 16:09:41 +0000997 SDValue X = Shift.getOperand(0);
Evan Cheng1314b002007-12-13 00:43:27 +0000998 ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(N.getOperand(1));
999 ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Shift.getOperand(1));
1000 if (!C1 || !C2) break;
1001
Dan Gohman21e3dfb2009-04-13 16:09:41 +00001002 // Handle "(X >> (8-C1)) & C2" as "(X >> 8) & 0xff)" if safe. This
1003 // allows us to convert the shift and and into an h-register extract and
1004 // a scaled index.
1005 if (Shift.getOpcode() == ISD::SRL && Shift.hasOneUse()) {
1006 unsigned ScaleLog = 8 - C1->getZExtValue();
Rafael Espindola7c366832009-04-16 12:34:53 +00001007 if (ScaleLog > 0 && ScaleLog < 4 &&
Dan Gohman21e3dfb2009-04-13 16:09:41 +00001008 C2->getZExtValue() == (UINT64_C(0xff) << ScaleLog)) {
Owen Anderson825b72b2009-08-11 20:47:22 +00001009 SDValue Eight = CurDAG->getConstant(8, MVT::i8);
Dan Gohman21e3dfb2009-04-13 16:09:41 +00001010 SDValue Mask = CurDAG->getConstant(0xff, N.getValueType());
1011 SDValue Srl = CurDAG->getNode(ISD::SRL, dl, N.getValueType(),
1012 X, Eight);
1013 SDValue And = CurDAG->getNode(ISD::AND, dl, N.getValueType(),
1014 Srl, Mask);
Owen Anderson825b72b2009-08-11 20:47:22 +00001015 SDValue ShlCount = CurDAG->getConstant(ScaleLog, MVT::i8);
Dan Gohman62ad1382009-04-14 22:45:05 +00001016 SDValue Shl = CurDAG->getNode(ISD::SHL, dl, N.getValueType(),
1017 And, ShlCount);
Dan Gohman21e3dfb2009-04-13 16:09:41 +00001018
1019 // Insert the new nodes into the topological ordering.
1020 if (Eight.getNode()->getNodeId() == -1 ||
1021 Eight.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1022 CurDAG->RepositionNode(X.getNode(), Eight.getNode());
1023 Eight.getNode()->setNodeId(X.getNode()->getNodeId());
1024 }
1025 if (Mask.getNode()->getNodeId() == -1 ||
1026 Mask.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1027 CurDAG->RepositionNode(X.getNode(), Mask.getNode());
1028 Mask.getNode()->setNodeId(X.getNode()->getNodeId());
1029 }
1030 if (Srl.getNode()->getNodeId() == -1 ||
1031 Srl.getNode()->getNodeId() > Shift.getNode()->getNodeId()) {
1032 CurDAG->RepositionNode(Shift.getNode(), Srl.getNode());
1033 Srl.getNode()->setNodeId(Shift.getNode()->getNodeId());
1034 }
1035 if (And.getNode()->getNodeId() == -1 ||
1036 And.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1037 CurDAG->RepositionNode(N.getNode(), And.getNode());
1038 And.getNode()->setNodeId(N.getNode()->getNodeId());
1039 }
Dan Gohman62ad1382009-04-14 22:45:05 +00001040 if (ShlCount.getNode()->getNodeId() == -1 ||
1041 ShlCount.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1042 CurDAG->RepositionNode(X.getNode(), ShlCount.getNode());
1043 ShlCount.getNode()->setNodeId(N.getNode()->getNodeId());
1044 }
1045 if (Shl.getNode()->getNodeId() == -1 ||
1046 Shl.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1047 CurDAG->RepositionNode(N.getNode(), Shl.getNode());
1048 Shl.getNode()->setNodeId(N.getNode()->getNodeId());
1049 }
Dan Gohmane5408102010-06-18 01:24:29 +00001050 CurDAG->ReplaceAllUsesWith(N, Shl);
Dan Gohman21e3dfb2009-04-13 16:09:41 +00001051 AM.IndexReg = And;
1052 AM.Scale = (1 << ScaleLog);
1053 return false;
1054 }
1055 }
1056
1057 // Handle "(X << C1) & C2" as "(X & (C2>>C1)) << C1" if safe and if this
1058 // allows us to fold the shift into this addressing mode.
1059 if (Shift.getOpcode() != ISD::SHL) break;
1060
Evan Cheng1314b002007-12-13 00:43:27 +00001061 // Not likely to be profitable if either the AND or SHIFT node has more
1062 // than one use (unless all uses are for address computation). Besides,
1063 // isel mechanism requires their node ids to be reused.
1064 if (!N.hasOneUse() || !Shift.hasOneUse())
1065 break;
1066
1067 // Verify that the shift amount is something we can fold.
Dan Gohmanf5aeb1a2008-09-12 16:56:44 +00001068 unsigned ShiftCst = C1->getZExtValue();
Evan Cheng1314b002007-12-13 00:43:27 +00001069 if (ShiftCst != 1 && ShiftCst != 2 && ShiftCst != 3)
1070 break;
1071
1072 // Get the new AND mask, this folds to a constant.
Dale Johannesend8392542009-02-03 21:48:12 +00001073 SDValue NewANDMask = CurDAG->getNode(ISD::SRL, dl, N.getValueType(),
Evan Cheng552e3be2008-10-14 17:15:39 +00001074 SDValue(C2, 0), SDValue(C1, 0));
Dale Johannesend8392542009-02-03 21:48:12 +00001075 SDValue NewAND = CurDAG->getNode(ISD::AND, dl, N.getValueType(), X,
1076 NewANDMask);
1077 SDValue NewSHIFT = CurDAG->getNode(ISD::SHL, dl, N.getValueType(),
Dan Gohman7b8e9642008-10-13 20:52:04 +00001078 NewAND, SDValue(C1, 0));
Dan Gohman8be6bbe2008-11-05 04:14:16 +00001079
1080 // Insert the new nodes into the topological ordering.
1081 if (C1->getNodeId() > X.getNode()->getNodeId()) {
1082 CurDAG->RepositionNode(X.getNode(), C1);
1083 C1->setNodeId(X.getNode()->getNodeId());
1084 }
1085 if (NewANDMask.getNode()->getNodeId() == -1 ||
1086 NewANDMask.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1087 CurDAG->RepositionNode(X.getNode(), NewANDMask.getNode());
1088 NewANDMask.getNode()->setNodeId(X.getNode()->getNodeId());
1089 }
1090 if (NewAND.getNode()->getNodeId() == -1 ||
1091 NewAND.getNode()->getNodeId() > Shift.getNode()->getNodeId()) {
1092 CurDAG->RepositionNode(Shift.getNode(), NewAND.getNode());
1093 NewAND.getNode()->setNodeId(Shift.getNode()->getNodeId());
1094 }
1095 if (NewSHIFT.getNode()->getNodeId() == -1 ||
1096 NewSHIFT.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1097 CurDAG->RepositionNode(N.getNode(), NewSHIFT.getNode());
1098 NewSHIFT.getNode()->setNodeId(N.getNode()->getNodeId());
1099 }
1100
Dan Gohmane5408102010-06-18 01:24:29 +00001101 CurDAG->ReplaceAllUsesWith(N, NewSHIFT);
Evan Cheng1314b002007-12-13 00:43:27 +00001102
1103 AM.Scale = 1 << ShiftCst;
1104 AM.IndexReg = NewAND;
1105 return false;
1106 }
Evan Chenge6ad27e2006-05-30 06:59:36 +00001107 }
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +00001108
Rafael Espindola523249f2009-03-31 16:16:57 +00001109 return MatchAddressBase(N, AM);
Dan Gohmanbadb2d22007-08-13 20:03:06 +00001110}
1111
1112/// MatchAddressBase - Helper for MatchAddress. Add the specified node to the
1113/// specified addressing mode without any further recursion.
Rafael Espindola523249f2009-03-31 16:16:57 +00001114bool X86DAGToDAGISel::MatchAddressBase(SDValue N, X86ISelAddressMode &AM) {
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +00001115 // Is the base register already occupied?
Dan Gohmanffce6f12010-04-29 23:30:41 +00001116 if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base_Reg.getNode()) {
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +00001117 // If so, check to see if the scale index register is set.
Chris Lattner18c59872009-06-27 04:16:01 +00001118 if (AM.IndexReg.getNode() == 0) {
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +00001119 AM.IndexReg = N;
1120 AM.Scale = 1;
1121 return false;
1122 }
1123
1124 // Otherwise, we cannot select it.
1125 return true;
1126 }
1127
1128 // Default, generate it as a register.
1129 AM.BaseType = X86ISelAddressMode::RegBase;
Dan Gohmanffce6f12010-04-29 23:30:41 +00001130 AM.Base_Reg = N;
Chris Lattnerf9ce9fb2005-11-19 02:11:08 +00001131 return false;
1132}
1133
Evan Chengec693f72005-12-08 02:01:35 +00001134/// SelectAddr - returns true if it is able pattern match an addressing mode.
1135/// It returns the operands which make up the maximal addressing mode it can
1136/// match by reference.
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001137bool X86DAGToDAGISel::SelectAddr(SDNode *Op, SDValue N, SDValue &Base,
Dan Gohman475871a2008-07-27 21:46:04 +00001138 SDValue &Scale, SDValue &Index,
Rafael Espindola094fad32009-04-08 21:14:34 +00001139 SDValue &Disp, SDValue &Segment) {
Evan Chengec693f72005-12-08 02:01:35 +00001140 X86ISelAddressMode AM;
Evan Chengc7928f82009-12-18 01:59:21 +00001141 if (MatchAddress(N, AM))
Evan Cheng8700e142006-01-11 06:09:51 +00001142 return false;
Evan Chengec693f72005-12-08 02:01:35 +00001143
Owen Andersone50ed302009-08-10 22:56:29 +00001144 EVT VT = N.getValueType();
Evan Cheng8700e142006-01-11 06:09:51 +00001145 if (AM.BaseType == X86ISelAddressMode::RegBase) {
Dan Gohmanffce6f12010-04-29 23:30:41 +00001146 if (!AM.Base_Reg.getNode())
1147 AM.Base_Reg = CurDAG->getRegister(0, VT);
Evan Chengec693f72005-12-08 02:01:35 +00001148 }
Evan Cheng8700e142006-01-11 06:09:51 +00001149
Gabor Greifba36cb52008-08-28 21:40:38 +00001150 if (!AM.IndexReg.getNode())
Evan Cheng25ab6902006-09-08 06:48:29 +00001151 AM.IndexReg = CurDAG->getRegister(0, VT);
Evan Cheng8700e142006-01-11 06:09:51 +00001152
Rafael Espindola094fad32009-04-08 21:14:34 +00001153 getAddressOperands(AM, Base, Scale, Index, Disp, Segment);
Evan Cheng8700e142006-01-11 06:09:51 +00001154 return true;
Evan Chengec693f72005-12-08 02:01:35 +00001155}
1156
Chris Lattner3a7cd952006-10-07 21:55:32 +00001157/// SelectScalarSSELoad - Match a scalar SSE load. In particular, we want to
1158/// match a load whose top elements are either undef or zeros. The load flavor
1159/// is derived from the type of N, which is either v4f32 or v2f64.
Chris Lattner64b49862010-02-17 06:07:47 +00001160///
1161/// We also return:
Chris Lattnera170b5e2010-02-21 03:17:59 +00001162/// PatternChainNode: this is the matched node that has a chain input and
1163/// output.
Chris Lattnere60f7b42010-03-01 22:51:11 +00001164bool X86DAGToDAGISel::SelectScalarSSELoad(SDNode *Root,
Dan Gohman475871a2008-07-27 21:46:04 +00001165 SDValue N, SDValue &Base,
1166 SDValue &Scale, SDValue &Index,
Rafael Espindola094fad32009-04-08 21:14:34 +00001167 SDValue &Disp, SDValue &Segment,
Chris Lattnera170b5e2010-02-21 03:17:59 +00001168 SDValue &PatternNodeWithChain) {
Chris Lattner3a7cd952006-10-07 21:55:32 +00001169 if (N.getOpcode() == ISD::SCALAR_TO_VECTOR) {
Chris Lattnera170b5e2010-02-21 03:17:59 +00001170 PatternNodeWithChain = N.getOperand(0);
1171 if (ISD::isNON_EXTLoad(PatternNodeWithChain.getNode()) &&
1172 PatternNodeWithChain.hasOneUse() &&
Chris Lattnerf1c64282010-02-21 04:53:34 +00001173 IsProfitableToFold(N.getOperand(0), N.getNode(), Root) &&
Dan Gohmand858e902010-04-17 15:26:15 +00001174 IsLegalToFold(N.getOperand(0), N.getNode(), Root, OptLevel)) {
Chris Lattnera170b5e2010-02-21 03:17:59 +00001175 LoadSDNode *LD = cast<LoadSDNode>(PatternNodeWithChain);
Chris Lattner92d3ada2010-02-16 22:35:06 +00001176 if (!SelectAddr(Root, LD->getBasePtr(), Base, Scale, Index, Disp,Segment))
Chris Lattner3a7cd952006-10-07 21:55:32 +00001177 return false;
1178 return true;
1179 }
1180 }
Chris Lattner4fe4f252006-10-11 22:09:58 +00001181
1182 // Also handle the case where we explicitly require zeros in the top
Chris Lattner3a7cd952006-10-07 21:55:32 +00001183 // elements. This is a vector shuffle from the zero vector.
Gabor Greifba36cb52008-08-28 21:40:38 +00001184 if (N.getOpcode() == X86ISD::VZEXT_MOVL && N.getNode()->hasOneUse() &&
Chris Lattner8a594482007-11-25 00:24:49 +00001185 // Check to see if the top elements are all zeros (or bitcast of zeros).
Evan Cheng7e2ff772008-05-08 00:57:18 +00001186 N.getOperand(0).getOpcode() == ISD::SCALAR_TO_VECTOR &&
Gabor Greifba36cb52008-08-28 21:40:38 +00001187 N.getOperand(0).getNode()->hasOneUse() &&
1188 ISD::isNON_EXTLoad(N.getOperand(0).getOperand(0).getNode()) &&
Chris Lattner92d3ada2010-02-16 22:35:06 +00001189 N.getOperand(0).getOperand(0).hasOneUse() &&
1190 IsProfitableToFold(N.getOperand(0), N.getNode(), Root) &&
Dan Gohmand858e902010-04-17 15:26:15 +00001191 IsLegalToFold(N.getOperand(0), N.getNode(), Root, OptLevel)) {
Evan Cheng7e2ff772008-05-08 00:57:18 +00001192 // Okay, this is a zero extending load. Fold it.
1193 LoadSDNode *LD = cast<LoadSDNode>(N.getOperand(0).getOperand(0));
Chris Lattner92d3ada2010-02-16 22:35:06 +00001194 if (!SelectAddr(Root, LD->getBasePtr(), Base, Scale, Index, Disp, Segment))
Evan Cheng7e2ff772008-05-08 00:57:18 +00001195 return false;
Chris Lattnera170b5e2010-02-21 03:17:59 +00001196 PatternNodeWithChain = SDValue(LD, 0);
Evan Cheng7e2ff772008-05-08 00:57:18 +00001197 return true;
Chris Lattner4fe4f252006-10-11 22:09:58 +00001198 }
Chris Lattner3a7cd952006-10-07 21:55:32 +00001199 return false;
1200}
1201
1202
Evan Cheng51a9ed92006-02-25 10:09:08 +00001203/// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing
1204/// mode it matches can be cost effectively emitted as an LEA instruction.
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001205bool X86DAGToDAGISel::SelectLEAAddr(SDNode *Op, SDValue N,
Dan Gohman475871a2008-07-27 21:46:04 +00001206 SDValue &Base, SDValue &Scale,
1207 SDValue &Index, SDValue &Disp) {
Evan Cheng51a9ed92006-02-25 10:09:08 +00001208 X86ISelAddressMode AM;
Rafael Espindoladbcfb302009-04-10 10:09:34 +00001209
1210 // Set AM.Segment to prevent MatchAddress from using one. LEA doesn't support
1211 // segments.
1212 SDValue Copy = AM.Segment;
Owen Anderson825b72b2009-08-11 20:47:22 +00001213 SDValue T = CurDAG->getRegister(0, MVT::i32);
Rafael Espindoladbcfb302009-04-10 10:09:34 +00001214 AM.Segment = T;
Evan Cheng51a9ed92006-02-25 10:09:08 +00001215 if (MatchAddress(N, AM))
1216 return false;
Rafael Espindoladbcfb302009-04-10 10:09:34 +00001217 assert (T == AM.Segment);
1218 AM.Segment = Copy;
Rafael Espindola094fad32009-04-08 21:14:34 +00001219
Owen Andersone50ed302009-08-10 22:56:29 +00001220 EVT VT = N.getValueType();
Evan Cheng51a9ed92006-02-25 10:09:08 +00001221 unsigned Complexity = 0;
1222 if (AM.BaseType == X86ISelAddressMode::RegBase)
Dan Gohmanffce6f12010-04-29 23:30:41 +00001223 if (AM.Base_Reg.getNode())
Evan Cheng51a9ed92006-02-25 10:09:08 +00001224 Complexity = 1;
1225 else
Dan Gohmanffce6f12010-04-29 23:30:41 +00001226 AM.Base_Reg = CurDAG->getRegister(0, VT);
Evan Cheng51a9ed92006-02-25 10:09:08 +00001227 else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
1228 Complexity = 4;
1229
Gabor Greifba36cb52008-08-28 21:40:38 +00001230 if (AM.IndexReg.getNode())
Evan Cheng51a9ed92006-02-25 10:09:08 +00001231 Complexity++;
1232 else
Evan Cheng25ab6902006-09-08 06:48:29 +00001233 AM.IndexReg = CurDAG->getRegister(0, VT);
Evan Cheng51a9ed92006-02-25 10:09:08 +00001234
Chris Lattnera16b7cb2007-03-20 06:08:29 +00001235 // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg, or with
1236 // a simple shift.
1237 if (AM.Scale > 1)
Evan Cheng8c03fe42006-02-28 21:13:57 +00001238 Complexity++;
Evan Cheng51a9ed92006-02-25 10:09:08 +00001239
1240 // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA
1241 // to a LEA. This is determined with some expermentation but is by no means
1242 // optimal (especially for code size consideration). LEA is nice because of
1243 // its three-address nature. Tweak the cost function again when we can run
1244 // convertToThreeAddress() at register allocation time.
Dan Gohman2d0a1cc2009-02-07 00:43:41 +00001245 if (AM.hasSymbolicDisplacement()) {
Evan Cheng25ab6902006-09-08 06:48:29 +00001246 // For X86-64, we should always use lea to materialize RIP relative
1247 // addresses.
Evan Cheng953fa042006-12-05 22:03:40 +00001248 if (Subtarget->is64Bit())
Evan Cheng25ab6902006-09-08 06:48:29 +00001249 Complexity = 4;
1250 else
1251 Complexity += 2;
1252 }
Evan Cheng51a9ed92006-02-25 10:09:08 +00001253
Dan Gohmanffce6f12010-04-29 23:30:41 +00001254 if (AM.Disp && (AM.Base_Reg.getNode() || AM.IndexReg.getNode()))
Evan Cheng51a9ed92006-02-25 10:09:08 +00001255 Complexity++;
1256
Chris Lattner25142782009-07-11 22:50:33 +00001257 // If it isn't worth using an LEA, reject it.
Chris Lattner14f75112009-07-11 23:07:30 +00001258 if (Complexity <= 2)
Chris Lattner25142782009-07-11 22:50:33 +00001259 return false;
1260
1261 SDValue Segment;
1262 getAddressOperands(AM, Base, Scale, Index, Disp, Segment);
1263 return true;
Evan Cheng51a9ed92006-02-25 10:09:08 +00001264}
1265
Chris Lattner5c0b16d2009-06-20 20:38:48 +00001266/// SelectTLSADDRAddr - This is only run on TargetGlobalTLSAddress nodes.
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001267bool X86DAGToDAGISel::SelectTLSADDRAddr(SDNode *Op, SDValue N, SDValue &Base,
Chris Lattner5c0b16d2009-06-20 20:38:48 +00001268 SDValue &Scale, SDValue &Index,
1269 SDValue &Disp) {
Chris Lattner5c0b16d2009-06-20 20:38:48 +00001270 assert(N.getOpcode() == ISD::TargetGlobalTLSAddress);
1271 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
Eric Christopher30ef0e52010-06-03 04:07:48 +00001272
Chris Lattner5c0b16d2009-06-20 20:38:48 +00001273 X86ISelAddressMode AM;
1274 AM.GV = GA->getGlobal();
1275 AM.Disp += GA->getOffset();
Dan Gohmanffce6f12010-04-29 23:30:41 +00001276 AM.Base_Reg = CurDAG->getRegister(0, N.getValueType());
Chris Lattnerba8ef452009-06-26 21:18:37 +00001277 AM.SymbolFlags = GA->getTargetFlags();
1278
Owen Anderson825b72b2009-08-11 20:47:22 +00001279 if (N.getValueType() == MVT::i32) {
Chris Lattner5c0b16d2009-06-20 20:38:48 +00001280 AM.Scale = 1;
Owen Anderson825b72b2009-08-11 20:47:22 +00001281 AM.IndexReg = CurDAG->getRegister(X86::EBX, MVT::i32);
Chris Lattner5c0b16d2009-06-20 20:38:48 +00001282 } else {
Owen Anderson825b72b2009-08-11 20:47:22 +00001283 AM.IndexReg = CurDAG->getRegister(0, MVT::i64);
Chris Lattner5c0b16d2009-06-20 20:38:48 +00001284 }
1285
1286 SDValue Segment;
1287 getAddressOperands(AM, Base, Scale, Index, Disp, Segment);
1288 return true;
1289}
1290
1291
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001292bool X86DAGToDAGISel::TryFoldLoad(SDNode *P, SDValue N,
Dan Gohman475871a2008-07-27 21:46:04 +00001293 SDValue &Base, SDValue &Scale,
Rafael Espindola094fad32009-04-08 21:14:34 +00001294 SDValue &Index, SDValue &Disp,
1295 SDValue &Segment) {
Chris Lattnerd1b73822010-03-02 22:20:06 +00001296 if (!ISD::isNON_EXTLoad(N.getNode()) ||
1297 !IsProfitableToFold(N, P, P) ||
Dan Gohmand858e902010-04-17 15:26:15 +00001298 !IsLegalToFold(N, P, P, OptLevel))
Chris Lattnerd1b73822010-03-02 22:20:06 +00001299 return false;
1300
1301 return SelectAddr(P, N.getOperand(1), Base, Scale, Index, Disp, Segment);
Evan Cheng0114e942006-01-06 20:36:21 +00001302}
1303
Dan Gohman8b746962008-09-23 18:22:58 +00001304/// getGlobalBaseReg - Return an SDNode that returns the value of
1305/// the global base register. Output instructions required to
1306/// initialize the global base register, if necessary.
Evan Cheng7ccced62006-02-18 00:15:05 +00001307///
Evan Cheng9ade2182006-08-26 05:34:46 +00001308SDNode *X86DAGToDAGISel::getGlobalBaseReg() {
Dan Gohmanc5534622009-06-03 20:20:00 +00001309 unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF);
Gabor Greifba36cb52008-08-28 21:40:38 +00001310 return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode();
Evan Cheng7ccced62006-02-18 00:15:05 +00001311}
1312
Evan Chengb245d922006-05-20 01:36:52 +00001313static SDNode *FindCallStartFromCall(SDNode *Node) {
1314 if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
Owen Anderson825b72b2009-08-11 20:47:22 +00001315 assert(Node->getOperand(0).getValueType() == MVT::Other &&
Evan Chengb245d922006-05-20 01:36:52 +00001316 "Node doesn't have a token chain argument!");
Gabor Greifba36cb52008-08-28 21:40:38 +00001317 return FindCallStartFromCall(Node->getOperand(0).getNode());
Evan Chengb245d922006-05-20 01:36:52 +00001318}
1319
Dale Johannesen48c1bc22008-10-02 18:53:47 +00001320SDNode *X86DAGToDAGISel::SelectAtomic64(SDNode *Node, unsigned Opc) {
1321 SDValue Chain = Node->getOperand(0);
1322 SDValue In1 = Node->getOperand(1);
1323 SDValue In2L = Node->getOperand(2);
1324 SDValue In2H = Node->getOperand(3);
Rafael Espindola094fad32009-04-08 21:14:34 +00001325 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001326 if (!SelectAddr(In1.getNode(), In1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4))
Dale Johannesen48c1bc22008-10-02 18:53:47 +00001327 return NULL;
Dan Gohmanc76909a2009-09-25 20:36:54 +00001328 MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
1329 MemOp[0] = cast<MemSDNode>(Node)->getMemOperand();
1330 const SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, In2L, In2H, Chain};
1331 SDNode *ResNode = CurDAG->getMachineNode(Opc, Node->getDebugLoc(),
1332 MVT::i32, MVT::i32, MVT::Other, Ops,
1333 array_lengthof(Ops));
1334 cast<MachineSDNode>(ResNode)->setMemRefs(MemOp, MemOp + 1);
1335 return ResNode;
Dale Johannesen48c1bc22008-10-02 18:53:47 +00001336}
Christopher Lambc59e5212007-08-10 21:48:46 +00001337
Owen Andersone50ed302009-08-10 22:56:29 +00001338SDNode *X86DAGToDAGISel::SelectAtomicLoadAdd(SDNode *Node, EVT NVT) {
Evan Cheng37b73872009-07-30 08:33:02 +00001339 if (Node->hasAnyUseOfValue(0))
1340 return 0;
1341
1342 // Optimize common patterns for __sync_add_and_fetch and
1343 // __sync_sub_and_fetch where the result is not used. This allows us
1344 // to use "lock" version of add, sub, inc, dec instructions.
1345 // FIXME: Do not use special instructions but instead add the "lock"
1346 // prefix to the target node somehow. The extra information will then be
1347 // transferred to machine instruction and it denotes the prefix.
1348 SDValue Chain = Node->getOperand(0);
1349 SDValue Ptr = Node->getOperand(1);
1350 SDValue Val = Node->getOperand(2);
1351 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001352 if (!SelectAddr(Ptr.getNode(), Ptr, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4))
Evan Cheng37b73872009-07-30 08:33:02 +00001353 return 0;
1354
1355 bool isInc = false, isDec = false, isSub = false, isCN = false;
1356 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val);
1357 if (CN) {
1358 isCN = true;
1359 int64_t CNVal = CN->getSExtValue();
1360 if (CNVal == 1)
1361 isInc = true;
1362 else if (CNVal == -1)
1363 isDec = true;
1364 else if (CNVal >= 0)
1365 Val = CurDAG->getTargetConstant(CNVal, NVT);
1366 else {
1367 isSub = true;
1368 Val = CurDAG->getTargetConstant(-CNVal, NVT);
1369 }
1370 } else if (Val.hasOneUse() &&
1371 Val.getOpcode() == ISD::SUB &&
1372 X86::isZeroNode(Val.getOperand(0))) {
1373 isSub = true;
1374 Val = Val.getOperand(1);
1375 }
1376
1377 unsigned Opc = 0;
Owen Anderson825b72b2009-08-11 20:47:22 +00001378 switch (NVT.getSimpleVT().SimpleTy) {
Evan Cheng37b73872009-07-30 08:33:02 +00001379 default: return 0;
Owen Anderson825b72b2009-08-11 20:47:22 +00001380 case MVT::i8:
Evan Cheng37b73872009-07-30 08:33:02 +00001381 if (isInc)
1382 Opc = X86::LOCK_INC8m;
1383 else if (isDec)
1384 Opc = X86::LOCK_DEC8m;
1385 else if (isSub) {
1386 if (isCN)
1387 Opc = X86::LOCK_SUB8mi;
1388 else
1389 Opc = X86::LOCK_SUB8mr;
1390 } else {
1391 if (isCN)
1392 Opc = X86::LOCK_ADD8mi;
1393 else
1394 Opc = X86::LOCK_ADD8mr;
1395 }
1396 break;
Owen Anderson825b72b2009-08-11 20:47:22 +00001397 case MVT::i16:
Evan Cheng37b73872009-07-30 08:33:02 +00001398 if (isInc)
1399 Opc = X86::LOCK_INC16m;
1400 else if (isDec)
1401 Opc = X86::LOCK_DEC16m;
1402 else if (isSub) {
1403 if (isCN) {
Chris Lattner18409912010-03-03 01:45:01 +00001404 if (Predicate_immSext8(Val.getNode()))
Evan Cheng37b73872009-07-30 08:33:02 +00001405 Opc = X86::LOCK_SUB16mi8;
1406 else
1407 Opc = X86::LOCK_SUB16mi;
1408 } else
1409 Opc = X86::LOCK_SUB16mr;
1410 } else {
1411 if (isCN) {
Chris Lattner18409912010-03-03 01:45:01 +00001412 if (Predicate_immSext8(Val.getNode()))
Evan Cheng37b73872009-07-30 08:33:02 +00001413 Opc = X86::LOCK_ADD16mi8;
1414 else
1415 Opc = X86::LOCK_ADD16mi;
1416 } else
1417 Opc = X86::LOCK_ADD16mr;
1418 }
1419 break;
Owen Anderson825b72b2009-08-11 20:47:22 +00001420 case MVT::i32:
Evan Cheng37b73872009-07-30 08:33:02 +00001421 if (isInc)
1422 Opc = X86::LOCK_INC32m;
1423 else if (isDec)
1424 Opc = X86::LOCK_DEC32m;
1425 else if (isSub) {
1426 if (isCN) {
Chris Lattner18409912010-03-03 01:45:01 +00001427 if (Predicate_immSext8(Val.getNode()))
Evan Cheng37b73872009-07-30 08:33:02 +00001428 Opc = X86::LOCK_SUB32mi8;
1429 else
1430 Opc = X86::LOCK_SUB32mi;
1431 } else
1432 Opc = X86::LOCK_SUB32mr;
1433 } else {
1434 if (isCN) {
Chris Lattner18409912010-03-03 01:45:01 +00001435 if (Predicate_immSext8(Val.getNode()))
Evan Cheng37b73872009-07-30 08:33:02 +00001436 Opc = X86::LOCK_ADD32mi8;
1437 else
1438 Opc = X86::LOCK_ADD32mi;
1439 } else
1440 Opc = X86::LOCK_ADD32mr;
1441 }
1442 break;
Owen Anderson825b72b2009-08-11 20:47:22 +00001443 case MVT::i64:
Evan Cheng37b73872009-07-30 08:33:02 +00001444 if (isInc)
1445 Opc = X86::LOCK_INC64m;
1446 else if (isDec)
1447 Opc = X86::LOCK_DEC64m;
1448 else if (isSub) {
1449 Opc = X86::LOCK_SUB64mr;
1450 if (isCN) {
Chris Lattner18409912010-03-03 01:45:01 +00001451 if (Predicate_immSext8(Val.getNode()))
Evan Cheng37b73872009-07-30 08:33:02 +00001452 Opc = X86::LOCK_SUB64mi8;
1453 else if (Predicate_i64immSExt32(Val.getNode()))
1454 Opc = X86::LOCK_SUB64mi32;
1455 }
1456 } else {
1457 Opc = X86::LOCK_ADD64mr;
1458 if (isCN) {
Chris Lattner18409912010-03-03 01:45:01 +00001459 if (Predicate_immSext8(Val.getNode()))
Evan Cheng37b73872009-07-30 08:33:02 +00001460 Opc = X86::LOCK_ADD64mi8;
1461 else if (Predicate_i64immSExt32(Val.getNode()))
1462 Opc = X86::LOCK_ADD64mi32;
1463 }
1464 }
1465 break;
1466 }
1467
1468 DebugLoc dl = Node->getDebugLoc();
Chris Lattner518bb532010-02-09 19:54:29 +00001469 SDValue Undef = SDValue(CurDAG->getMachineNode(TargetOpcode::IMPLICIT_DEF,
Dan Gohman602b0c82009-09-25 18:54:59 +00001470 dl, NVT), 0);
Dan Gohmanc76909a2009-09-25 20:36:54 +00001471 MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
1472 MemOp[0] = cast<MemSDNode>(Node)->getMemOperand();
Evan Cheng37b73872009-07-30 08:33:02 +00001473 if (isInc || isDec) {
Dan Gohmanc76909a2009-09-25 20:36:54 +00001474 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Chain };
1475 SDValue Ret = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Other, Ops, 6), 0);
1476 cast<MachineSDNode>(Ret)->setMemRefs(MemOp, MemOp + 1);
Evan Cheng37b73872009-07-30 08:33:02 +00001477 SDValue RetVals[] = { Undef, Ret };
1478 return CurDAG->getMergeValues(RetVals, 2, dl).getNode();
1479 } else {
Dan Gohmanc76909a2009-09-25 20:36:54 +00001480 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Val, Chain };
1481 SDValue Ret = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Other, Ops, 7), 0);
1482 cast<MachineSDNode>(Ret)->setMemRefs(MemOp, MemOp + 1);
Evan Cheng37b73872009-07-30 08:33:02 +00001483 SDValue RetVals[] = { Undef, Ret };
1484 return CurDAG->getMergeValues(RetVals, 2, dl).getNode();
1485 }
1486}
1487
Dan Gohman11596ed2009-10-09 20:35:19 +00001488/// HasNoSignedComparisonUses - Test whether the given X86ISD::CMP node has
1489/// any uses which require the SF or OF bits to be accurate.
1490static bool HasNoSignedComparisonUses(SDNode *N) {
1491 // Examine each user of the node.
1492 for (SDNode::use_iterator UI = N->use_begin(),
1493 UE = N->use_end(); UI != UE; ++UI) {
1494 // Only examine CopyToReg uses.
1495 if (UI->getOpcode() != ISD::CopyToReg)
1496 return false;
1497 // Only examine CopyToReg uses that copy to EFLAGS.
1498 if (cast<RegisterSDNode>(UI->getOperand(1))->getReg() !=
1499 X86::EFLAGS)
1500 return false;
1501 // Examine each user of the CopyToReg use.
1502 for (SDNode::use_iterator FlagUI = UI->use_begin(),
1503 FlagUE = UI->use_end(); FlagUI != FlagUE; ++FlagUI) {
1504 // Only examine the Flag result.
1505 if (FlagUI.getUse().getResNo() != 1) continue;
1506 // Anything unusual: assume conservatively.
1507 if (!FlagUI->isMachineOpcode()) return false;
1508 // Examine the opcode of the user.
1509 switch (FlagUI->getMachineOpcode()) {
1510 // These comparisons don't treat the most significant bit specially.
1511 case X86::SETAr: case X86::SETAEr: case X86::SETBr: case X86::SETBEr:
1512 case X86::SETEr: case X86::SETNEr: case X86::SETPr: case X86::SETNPr:
1513 case X86::SETAm: case X86::SETAEm: case X86::SETBm: case X86::SETBEm:
1514 case X86::SETEm: case X86::SETNEm: case X86::SETPm: case X86::SETNPm:
Chris Lattnerbd13fb62010-02-11 19:25:55 +00001515 case X86::JA_4: case X86::JAE_4: case X86::JB_4: case X86::JBE_4:
1516 case X86::JE_4: case X86::JNE_4: case X86::JP_4: case X86::JNP_4:
Dan Gohman11596ed2009-10-09 20:35:19 +00001517 case X86::CMOVA16rr: case X86::CMOVA16rm:
1518 case X86::CMOVA32rr: case X86::CMOVA32rm:
1519 case X86::CMOVA64rr: case X86::CMOVA64rm:
1520 case X86::CMOVAE16rr: case X86::CMOVAE16rm:
1521 case X86::CMOVAE32rr: case X86::CMOVAE32rm:
1522 case X86::CMOVAE64rr: case X86::CMOVAE64rm:
1523 case X86::CMOVB16rr: case X86::CMOVB16rm:
1524 case X86::CMOVB32rr: case X86::CMOVB32rm:
1525 case X86::CMOVB64rr: case X86::CMOVB64rm:
1526 case X86::CMOVBE16rr: case X86::CMOVBE16rm:
1527 case X86::CMOVBE32rr: case X86::CMOVBE32rm:
1528 case X86::CMOVBE64rr: case X86::CMOVBE64rm:
1529 case X86::CMOVE16rr: case X86::CMOVE16rm:
1530 case X86::CMOVE32rr: case X86::CMOVE32rm:
1531 case X86::CMOVE64rr: case X86::CMOVE64rm:
1532 case X86::CMOVNE16rr: case X86::CMOVNE16rm:
1533 case X86::CMOVNE32rr: case X86::CMOVNE32rm:
1534 case X86::CMOVNE64rr: case X86::CMOVNE64rm:
1535 case X86::CMOVNP16rr: case X86::CMOVNP16rm:
1536 case X86::CMOVNP32rr: case X86::CMOVNP32rm:
1537 case X86::CMOVNP64rr: case X86::CMOVNP64rm:
1538 case X86::CMOVP16rr: case X86::CMOVP16rm:
1539 case X86::CMOVP32rr: case X86::CMOVP32rm:
1540 case X86::CMOVP64rr: case X86::CMOVP64rm:
1541 continue;
1542 // Anything else: assume conservatively.
1543 default: return false;
1544 }
1545 }
1546 }
1547 return true;
1548}
1549
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001550SDNode *X86DAGToDAGISel::Select(SDNode *Node) {
Owen Andersone50ed302009-08-10 22:56:29 +00001551 EVT NVT = Node->getValueType(0);
Evan Cheng0114e942006-01-06 20:36:21 +00001552 unsigned Opc, MOpc;
1553 unsigned Opcode = Node->getOpcode();
Dale Johannesend8392542009-02-03 21:48:12 +00001554 DebugLoc dl = Node->getDebugLoc();
1555
Chris Lattner7c306da2010-03-02 06:34:30 +00001556 DEBUG(dbgs() << "Selecting: "; Node->dump(CurDAG); dbgs() << '\n');
Evan Chengf597dc72006-02-10 22:24:32 +00001557
Dan Gohmane8be6c62008-07-17 19:10:17 +00001558 if (Node->isMachineOpcode()) {
Chris Lattner7c306da2010-03-02 06:34:30 +00001559 DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n');
Evan Cheng64a752f2006-08-11 09:08:15 +00001560 return NULL; // Already selected.
Evan Cheng34167212006-02-09 00:37:58 +00001561 }
Evan Cheng38262ca2006-01-11 22:15:18 +00001562
Evan Cheng0114e942006-01-06 20:36:21 +00001563 switch (Opcode) {
Dan Gohman72677342009-08-02 16:10:52 +00001564 default: break;
1565 case X86ISD::GlobalBaseReg:
1566 return getGlobalBaseReg();
Evan Cheng020d2e82006-02-23 20:41:18 +00001567
Dan Gohman72677342009-08-02 16:10:52 +00001568 case X86ISD::ATOMOR64_DAG:
1569 return SelectAtomic64(Node, X86::ATOMOR6432);
1570 case X86ISD::ATOMXOR64_DAG:
1571 return SelectAtomic64(Node, X86::ATOMXOR6432);
1572 case X86ISD::ATOMADD64_DAG:
1573 return SelectAtomic64(Node, X86::ATOMADD6432);
1574 case X86ISD::ATOMSUB64_DAG:
1575 return SelectAtomic64(Node, X86::ATOMSUB6432);
1576 case X86ISD::ATOMNAND64_DAG:
1577 return SelectAtomic64(Node, X86::ATOMNAND6432);
1578 case X86ISD::ATOMAND64_DAG:
1579 return SelectAtomic64(Node, X86::ATOMAND6432);
1580 case X86ISD::ATOMSWAP64_DAG:
1581 return SelectAtomic64(Node, X86::ATOMSWAP6432);
Dale Johannesen48c1bc22008-10-02 18:53:47 +00001582
Dan Gohman72677342009-08-02 16:10:52 +00001583 case ISD::ATOMIC_LOAD_ADD: {
1584 SDNode *RetVal = SelectAtomicLoadAdd(Node, NVT);
1585 if (RetVal)
1586 return RetVal;
1587 break;
1588 }
1589
1590 case ISD::SMUL_LOHI:
1591 case ISD::UMUL_LOHI: {
1592 SDValue N0 = Node->getOperand(0);
1593 SDValue N1 = Node->getOperand(1);
1594
1595 bool isSigned = Opcode == ISD::SMUL_LOHI;
Bill Wendling12321672009-08-07 21:33:25 +00001596 if (!isSigned) {
Owen Anderson825b72b2009-08-11 20:47:22 +00001597 switch (NVT.getSimpleVT().SimpleTy) {
Dan Gohman72677342009-08-02 16:10:52 +00001598 default: llvm_unreachable("Unsupported VT!");
Owen Anderson825b72b2009-08-11 20:47:22 +00001599 case MVT::i8: Opc = X86::MUL8r; MOpc = X86::MUL8m; break;
1600 case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break;
1601 case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break;
1602 case MVT::i64: Opc = X86::MUL64r; MOpc = X86::MUL64m; break;
Dan Gohman72677342009-08-02 16:10:52 +00001603 }
Bill Wendling12321672009-08-07 21:33:25 +00001604 } else {
Owen Anderson825b72b2009-08-11 20:47:22 +00001605 switch (NVT.getSimpleVT().SimpleTy) {
Dan Gohman72677342009-08-02 16:10:52 +00001606 default: llvm_unreachable("Unsupported VT!");
Owen Anderson825b72b2009-08-11 20:47:22 +00001607 case MVT::i8: Opc = X86::IMUL8r; MOpc = X86::IMUL8m; break;
1608 case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break;
1609 case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break;
1610 case MVT::i64: Opc = X86::IMUL64r; MOpc = X86::IMUL64m; break;
Dan Gohman72677342009-08-02 16:10:52 +00001611 }
Bill Wendling12321672009-08-07 21:33:25 +00001612 }
Dan Gohman72677342009-08-02 16:10:52 +00001613
1614 unsigned LoReg, HiReg;
Owen Anderson825b72b2009-08-11 20:47:22 +00001615 switch (NVT.getSimpleVT().SimpleTy) {
Dan Gohman72677342009-08-02 16:10:52 +00001616 default: llvm_unreachable("Unsupported VT!");
Owen Anderson825b72b2009-08-11 20:47:22 +00001617 case MVT::i8: LoReg = X86::AL; HiReg = X86::AH; break;
1618 case MVT::i16: LoReg = X86::AX; HiReg = X86::DX; break;
1619 case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break;
1620 case MVT::i64: LoReg = X86::RAX; HiReg = X86::RDX; break;
Dan Gohman72677342009-08-02 16:10:52 +00001621 }
1622
1623 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001624 bool foldedLoad = TryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
Bill Wendling12321672009-08-07 21:33:25 +00001625 // Multiply is commmutative.
Dan Gohman72677342009-08-02 16:10:52 +00001626 if (!foldedLoad) {
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001627 foldedLoad = TryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
Dan Gohman72677342009-08-02 16:10:52 +00001628 if (foldedLoad)
1629 std::swap(N0, N1);
1630 }
1631
1632 SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, LoReg,
1633 N0, SDValue()).getValue(1);
1634
1635 if (foldedLoad) {
1636 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
1637 InFlag };
1638 SDNode *CNode =
Dan Gohman602b0c82009-09-25 18:54:59 +00001639 CurDAG->getMachineNode(MOpc, dl, MVT::Other, MVT::Flag, Ops,
1640 array_lengthof(Ops));
Dan Gohman72677342009-08-02 16:10:52 +00001641 InFlag = SDValue(CNode, 1);
1642 // Update the chain.
1643 ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
1644 } else {
1645 InFlag =
Dan Gohman602b0c82009-09-25 18:54:59 +00001646 SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Flag, N1, InFlag), 0);
Dan Gohman72677342009-08-02 16:10:52 +00001647 }
1648
1649 // Copy the low half of the result, if it is needed.
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001650 if (!SDValue(Node, 0).use_empty()) {
Dan Gohman72677342009-08-02 16:10:52 +00001651 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1652 LoReg, NVT, InFlag);
1653 InFlag = Result.getValue(2);
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001654 ReplaceUses(SDValue(Node, 0), Result);
Chris Lattner7c306da2010-03-02 06:34:30 +00001655 DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n');
Dan Gohman72677342009-08-02 16:10:52 +00001656 }
1657 // Copy the high half of the result, if it is needed.
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001658 if (!SDValue(Node, 1).use_empty()) {
Dan Gohman72677342009-08-02 16:10:52 +00001659 SDValue Result;
1660 if (HiReg == X86::AH && Subtarget->is64Bit()) {
1661 // Prevent use of AH in a REX instruction by referencing AX instead.
1662 // Shift it down 8 bits.
1663 Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
Owen Anderson825b72b2009-08-11 20:47:22 +00001664 X86::AX, MVT::i16, InFlag);
Dan Gohman72677342009-08-02 16:10:52 +00001665 InFlag = Result.getValue(2);
Dan Gohman602b0c82009-09-25 18:54:59 +00001666 Result = SDValue(CurDAG->getMachineNode(X86::SHR16ri, dl, MVT::i16,
1667 Result,
Owen Anderson825b72b2009-08-11 20:47:22 +00001668 CurDAG->getTargetConstant(8, MVT::i8)), 0);
Dan Gohman72677342009-08-02 16:10:52 +00001669 // Then truncate it down to i8.
Jakob Stoklund Olesen3458e9e2010-05-24 14:48:17 +00001670 Result = CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl,
Dan Gohman6a402dc2009-08-19 18:16:17 +00001671 MVT::i8, Result);
Dan Gohman72677342009-08-02 16:10:52 +00001672 } else {
1673 Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1674 HiReg, NVT, InFlag);
1675 InFlag = Result.getValue(2);
1676 }
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001677 ReplaceUses(SDValue(Node, 1), Result);
Chris Lattner7c306da2010-03-02 06:34:30 +00001678 DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n');
Dan Gohman72677342009-08-02 16:10:52 +00001679 }
1680
Dan Gohman72677342009-08-02 16:10:52 +00001681 return NULL;
1682 }
1683
1684 case ISD::SDIVREM:
1685 case ISD::UDIVREM: {
1686 SDValue N0 = Node->getOperand(0);
1687 SDValue N1 = Node->getOperand(1);
1688
1689 bool isSigned = Opcode == ISD::SDIVREM;
Bill Wendling12321672009-08-07 21:33:25 +00001690 if (!isSigned) {
Owen Anderson825b72b2009-08-11 20:47:22 +00001691 switch (NVT.getSimpleVT().SimpleTy) {
Dan Gohman72677342009-08-02 16:10:52 +00001692 default: llvm_unreachable("Unsupported VT!");
Owen Anderson825b72b2009-08-11 20:47:22 +00001693 case MVT::i8: Opc = X86::DIV8r; MOpc = X86::DIV8m; break;
1694 case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break;
1695 case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break;
1696 case MVT::i64: Opc = X86::DIV64r; MOpc = X86::DIV64m; break;
Dan Gohman72677342009-08-02 16:10:52 +00001697 }
Bill Wendling12321672009-08-07 21:33:25 +00001698 } else {
Owen Anderson825b72b2009-08-11 20:47:22 +00001699 switch (NVT.getSimpleVT().SimpleTy) {
Dan Gohman72677342009-08-02 16:10:52 +00001700 default: llvm_unreachable("Unsupported VT!");
Owen Anderson825b72b2009-08-11 20:47:22 +00001701 case MVT::i8: Opc = X86::IDIV8r; MOpc = X86::IDIV8m; break;
1702 case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break;
1703 case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break;
1704 case MVT::i64: Opc = X86::IDIV64r; MOpc = X86::IDIV64m; break;
Dan Gohman72677342009-08-02 16:10:52 +00001705 }
Bill Wendling12321672009-08-07 21:33:25 +00001706 }
Dan Gohman72677342009-08-02 16:10:52 +00001707
Chris Lattner9e323832009-12-23 01:45:04 +00001708 unsigned LoReg, HiReg, ClrReg;
Dan Gohman72677342009-08-02 16:10:52 +00001709 unsigned ClrOpcode, SExtOpcode;
Owen Anderson825b72b2009-08-11 20:47:22 +00001710 switch (NVT.getSimpleVT().SimpleTy) {
Dan Gohman72677342009-08-02 16:10:52 +00001711 default: llvm_unreachable("Unsupported VT!");
Owen Anderson825b72b2009-08-11 20:47:22 +00001712 case MVT::i8:
Chris Lattner9e323832009-12-23 01:45:04 +00001713 LoReg = X86::AL; ClrReg = HiReg = X86::AH;
Dan Gohman72677342009-08-02 16:10:52 +00001714 ClrOpcode = 0;
1715 SExtOpcode = X86::CBW;
1716 break;
Owen Anderson825b72b2009-08-11 20:47:22 +00001717 case MVT::i16:
Dan Gohman72677342009-08-02 16:10:52 +00001718 LoReg = X86::AX; HiReg = X86::DX;
Dan Gohmanf1b4d262010-01-12 04:42:54 +00001719 ClrOpcode = X86::MOV16r0; ClrReg = X86::DX;
Dan Gohman72677342009-08-02 16:10:52 +00001720 SExtOpcode = X86::CWD;
1721 break;
Owen Anderson825b72b2009-08-11 20:47:22 +00001722 case MVT::i32:
Chris Lattner9e323832009-12-23 01:45:04 +00001723 LoReg = X86::EAX; ClrReg = HiReg = X86::EDX;
Dan Gohman72677342009-08-02 16:10:52 +00001724 ClrOpcode = X86::MOV32r0;
1725 SExtOpcode = X86::CDQ;
1726 break;
Owen Anderson825b72b2009-08-11 20:47:22 +00001727 case MVT::i64:
Chris Lattner9e323832009-12-23 01:45:04 +00001728 LoReg = X86::RAX; ClrReg = HiReg = X86::RDX;
Dan Gohmanf1b4d262010-01-12 04:42:54 +00001729 ClrOpcode = X86::MOV64r0;
Dan Gohman72677342009-08-02 16:10:52 +00001730 SExtOpcode = X86::CQO;
Evan Cheng37b73872009-07-30 08:33:02 +00001731 break;
1732 }
1733
Dan Gohman72677342009-08-02 16:10:52 +00001734 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001735 bool foldedLoad = TryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
Dan Gohman72677342009-08-02 16:10:52 +00001736 bool signBitIsZero = CurDAG->SignBitIsZero(N0);
Dan Gohman525178c2007-10-08 18:33:35 +00001737
Dan Gohman72677342009-08-02 16:10:52 +00001738 SDValue InFlag;
Owen Anderson825b72b2009-08-11 20:47:22 +00001739 if (NVT == MVT::i8 && (!isSigned || signBitIsZero)) {
Dan Gohman72677342009-08-02 16:10:52 +00001740 // Special case for div8, just use a move with zero extension to AX to
1741 // clear the upper 8 bits (AH).
1742 SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Move, Chain;
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001743 if (TryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) {
Dan Gohman72677342009-08-02 16:10:52 +00001744 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N0.getOperand(0) };
1745 Move =
Dan Gohman602b0c82009-09-25 18:54:59 +00001746 SDValue(CurDAG->getMachineNode(X86::MOVZX16rm8, dl, MVT::i16,
1747 MVT::Other, Ops,
1748 array_lengthof(Ops)), 0);
Dan Gohman72677342009-08-02 16:10:52 +00001749 Chain = Move.getValue(1);
1750 ReplaceUses(N0.getValue(1), Chain);
Evan Cheng0114e942006-01-06 20:36:21 +00001751 } else {
Dan Gohman72677342009-08-02 16:10:52 +00001752 Move =
Dan Gohman602b0c82009-09-25 18:54:59 +00001753 SDValue(CurDAG->getMachineNode(X86::MOVZX16rr8, dl, MVT::i16, N0),0);
Dan Gohman72677342009-08-02 16:10:52 +00001754 Chain = CurDAG->getEntryNode();
1755 }
1756 Chain = CurDAG->getCopyToReg(Chain, dl, X86::AX, Move, SDValue());
1757 InFlag = Chain.getValue(1);
1758 } else {
1759 InFlag =
1760 CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl,
1761 LoReg, N0, SDValue()).getValue(1);
1762 if (isSigned && !signBitIsZero) {
1763 // Sign extend the low part into the high part.
Evan Cheng7e9b26f2006-02-09 07:17:49 +00001764 InFlag =
Dan Gohman602b0c82009-09-25 18:54:59 +00001765 SDValue(CurDAG->getMachineNode(SExtOpcode, dl, MVT::Flag, InFlag),0);
Dan Gohman72677342009-08-02 16:10:52 +00001766 } else {
1767 // Zero out the high part, effectively zero extending the input.
Dan Gohmanf1b4d262010-01-12 04:42:54 +00001768 SDValue ClrNode =
1769 SDValue(CurDAG->getMachineNode(ClrOpcode, dl, NVT), 0);
Chris Lattner9e323832009-12-23 01:45:04 +00001770 InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, ClrReg,
Dan Gohman72677342009-08-02 16:10:52 +00001771 ClrNode, InFlag).getValue(1);
Dan Gohman525178c2007-10-08 18:33:35 +00001772 }
Evan Cheng948f3432006-01-06 23:19:29 +00001773 }
Dan Gohman525178c2007-10-08 18:33:35 +00001774
Dan Gohman72677342009-08-02 16:10:52 +00001775 if (foldedLoad) {
1776 SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
1777 InFlag };
1778 SDNode *CNode =
Dan Gohman602b0c82009-09-25 18:54:59 +00001779 CurDAG->getMachineNode(MOpc, dl, MVT::Other, MVT::Flag, Ops,
1780 array_lengthof(Ops));
Dan Gohman72677342009-08-02 16:10:52 +00001781 InFlag = SDValue(CNode, 1);
1782 // Update the chain.
1783 ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
1784 } else {
1785 InFlag =
Dan Gohman602b0c82009-09-25 18:54:59 +00001786 SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Flag, N1, InFlag), 0);
Dan Gohman72677342009-08-02 16:10:52 +00001787 }
Evan Cheng948f3432006-01-06 23:19:29 +00001788
Dan Gohman72677342009-08-02 16:10:52 +00001789 // Copy the division (low) result, if it is needed.
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001790 if (!SDValue(Node, 0).use_empty()) {
Dan Gohman72677342009-08-02 16:10:52 +00001791 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1792 LoReg, NVT, InFlag);
1793 InFlag = Result.getValue(2);
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001794 ReplaceUses(SDValue(Node, 0), Result);
Chris Lattner7c306da2010-03-02 06:34:30 +00001795 DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n');
Dan Gohman72677342009-08-02 16:10:52 +00001796 }
1797 // Copy the remainder (high) result, if it is needed.
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001798 if (!SDValue(Node, 1).use_empty()) {
Dan Gohman72677342009-08-02 16:10:52 +00001799 SDValue Result;
1800 if (HiReg == X86::AH && Subtarget->is64Bit()) {
1801 // Prevent use of AH in a REX instruction by referencing AX instead.
1802 // Shift it down 8 bits.
1803 Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
Owen Anderson825b72b2009-08-11 20:47:22 +00001804 X86::AX, MVT::i16, InFlag);
Dan Gohmana37c9f72007-09-25 18:23:27 +00001805 InFlag = Result.getValue(2);
Dan Gohman602b0c82009-09-25 18:54:59 +00001806 Result = SDValue(CurDAG->getMachineNode(X86::SHR16ri, dl, MVT::i16,
Dan Gohman72677342009-08-02 16:10:52 +00001807 Result,
Owen Anderson825b72b2009-08-11 20:47:22 +00001808 CurDAG->getTargetConstant(8, MVT::i8)),
Dan Gohman72677342009-08-02 16:10:52 +00001809 0);
1810 // Then truncate it down to i8.
Jakob Stoklund Olesen3458e9e2010-05-24 14:48:17 +00001811 Result = CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl,
Dan Gohman6a402dc2009-08-19 18:16:17 +00001812 MVT::i8, Result);
Dan Gohman72677342009-08-02 16:10:52 +00001813 } else {
1814 Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1815 HiReg, NVT, InFlag);
1816 InFlag = Result.getValue(2);
Evan Chengf7ef26e2007-08-09 21:59:35 +00001817 }
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001818 ReplaceUses(SDValue(Node, 1), Result);
Chris Lattner7c306da2010-03-02 06:34:30 +00001819 DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n');
Dan Gohman72677342009-08-02 16:10:52 +00001820 }
Dan Gohman72677342009-08-02 16:10:52 +00001821 return NULL;
1822 }
1823
Dan Gohman6a402dc2009-08-19 18:16:17 +00001824 case X86ISD::CMP: {
Dan Gohman6a402dc2009-08-19 18:16:17 +00001825 SDValue N0 = Node->getOperand(0);
1826 SDValue N1 = Node->getOperand(1);
1827
1828 // Look for (X86cmp (and $op, $imm), 0) and see if we can convert it to
1829 // use a smaller encoding.
Evan Cheng2bce5f4b2010-04-28 08:30:49 +00001830 if (N0.getOpcode() == ISD::TRUNCATE && N0.hasOneUse())
1831 // Look past the truncate if CMP is the only use of it.
1832 N0 = N0.getOperand(0);
Dan Gohman6a402dc2009-08-19 18:16:17 +00001833 if (N0.getNode()->getOpcode() == ISD::AND && N0.getNode()->hasOneUse() &&
1834 N0.getValueType() != MVT::i8 &&
1835 X86::isZeroNode(N1)) {
1836 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N0.getNode()->getOperand(1));
1837 if (!C) break;
1838
1839 // For example, convert "testl %eax, $8" to "testb %al, $8"
Dan Gohman11596ed2009-10-09 20:35:19 +00001840 if ((C->getZExtValue() & ~UINT64_C(0xff)) == 0 &&
1841 (!(C->getZExtValue() & 0x80) ||
1842 HasNoSignedComparisonUses(Node))) {
Dan Gohman6a402dc2009-08-19 18:16:17 +00001843 SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), MVT::i8);
1844 SDValue Reg = N0.getNode()->getOperand(0);
1845
1846 // On x86-32, only the ABCD registers have 8-bit subregisters.
1847 if (!Subtarget->is64Bit()) {
1848 TargetRegisterClass *TRC = 0;
1849 switch (N0.getValueType().getSimpleVT().SimpleTy) {
1850 case MVT::i32: TRC = &X86::GR32_ABCDRegClass; break;
1851 case MVT::i16: TRC = &X86::GR16_ABCDRegClass; break;
1852 default: llvm_unreachable("Unsupported TEST operand type!");
1853 }
1854 SDValue RC = CurDAG->getTargetConstant(TRC->getID(), MVT::i32);
Dan Gohman602b0c82009-09-25 18:54:59 +00001855 Reg = SDValue(CurDAG->getMachineNode(X86::COPY_TO_REGCLASS, dl,
1856 Reg.getValueType(), Reg, RC), 0);
Dan Gohman6a402dc2009-08-19 18:16:17 +00001857 }
1858
1859 // Extract the l-register.
Jakob Stoklund Olesen3458e9e2010-05-24 14:48:17 +00001860 SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl,
Dan Gohman6a402dc2009-08-19 18:16:17 +00001861 MVT::i8, Reg);
1862
1863 // Emit a testb.
Dan Gohman602b0c82009-09-25 18:54:59 +00001864 return CurDAG->getMachineNode(X86::TEST8ri, dl, MVT::i32, Subreg, Imm);
Dan Gohman6a402dc2009-08-19 18:16:17 +00001865 }
1866
1867 // For example, "testl %eax, $2048" to "testb %ah, $8".
Dan Gohman11596ed2009-10-09 20:35:19 +00001868 if ((C->getZExtValue() & ~UINT64_C(0xff00)) == 0 &&
1869 (!(C->getZExtValue() & 0x8000) ||
1870 HasNoSignedComparisonUses(Node))) {
Dan Gohman6a402dc2009-08-19 18:16:17 +00001871 // Shift the immediate right by 8 bits.
1872 SDValue ShiftedImm = CurDAG->getTargetConstant(C->getZExtValue() >> 8,
1873 MVT::i8);
1874 SDValue Reg = N0.getNode()->getOperand(0);
1875
1876 // Put the value in an ABCD register.
1877 TargetRegisterClass *TRC = 0;
1878 switch (N0.getValueType().getSimpleVT().SimpleTy) {
1879 case MVT::i64: TRC = &X86::GR64_ABCDRegClass; break;
1880 case MVT::i32: TRC = &X86::GR32_ABCDRegClass; break;
1881 case MVT::i16: TRC = &X86::GR16_ABCDRegClass; break;
1882 default: llvm_unreachable("Unsupported TEST operand type!");
1883 }
1884 SDValue RC = CurDAG->getTargetConstant(TRC->getID(), MVT::i32);
Dan Gohman602b0c82009-09-25 18:54:59 +00001885 Reg = SDValue(CurDAG->getMachineNode(X86::COPY_TO_REGCLASS, dl,
1886 Reg.getValueType(), Reg, RC), 0);
Dan Gohman6a402dc2009-08-19 18:16:17 +00001887
1888 // Extract the h-register.
Jakob Stoklund Olesen3458e9e2010-05-24 14:48:17 +00001889 SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_8bit_hi, dl,
Dan Gohman6a402dc2009-08-19 18:16:17 +00001890 MVT::i8, Reg);
1891
1892 // Emit a testb. No special NOREX tricks are needed since there's
1893 // only one GPR operand!
Dan Gohman602b0c82009-09-25 18:54:59 +00001894 return CurDAG->getMachineNode(X86::TEST8ri, dl, MVT::i32,
1895 Subreg, ShiftedImm);
Dan Gohman6a402dc2009-08-19 18:16:17 +00001896 }
1897
1898 // For example, "testl %eax, $32776" to "testw %ax, $32776".
1899 if ((C->getZExtValue() & ~UINT64_C(0xffff)) == 0 &&
Dan Gohman11596ed2009-10-09 20:35:19 +00001900 N0.getValueType() != MVT::i16 &&
1901 (!(C->getZExtValue() & 0x8000) ||
1902 HasNoSignedComparisonUses(Node))) {
Dan Gohman6a402dc2009-08-19 18:16:17 +00001903 SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), MVT::i16);
1904 SDValue Reg = N0.getNode()->getOperand(0);
1905
1906 // Extract the 16-bit subregister.
Jakob Stoklund Olesen3458e9e2010-05-24 14:48:17 +00001907 SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_16bit, dl,
Dan Gohman6a402dc2009-08-19 18:16:17 +00001908 MVT::i16, Reg);
1909
1910 // Emit a testw.
Dan Gohman602b0c82009-09-25 18:54:59 +00001911 return CurDAG->getMachineNode(X86::TEST16ri, dl, MVT::i32, Subreg, Imm);
Dan Gohman6a402dc2009-08-19 18:16:17 +00001912 }
1913
1914 // For example, "testq %rax, $268468232" to "testl %eax, $268468232".
1915 if ((C->getZExtValue() & ~UINT64_C(0xffffffff)) == 0 &&
Dan Gohman11596ed2009-10-09 20:35:19 +00001916 N0.getValueType() == MVT::i64 &&
1917 (!(C->getZExtValue() & 0x80000000) ||
1918 HasNoSignedComparisonUses(Node))) {
Dan Gohman6a402dc2009-08-19 18:16:17 +00001919 SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), MVT::i32);
1920 SDValue Reg = N0.getNode()->getOperand(0);
1921
1922 // Extract the 32-bit subregister.
Jakob Stoklund Olesen3458e9e2010-05-24 14:48:17 +00001923 SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_32bit, dl,
Dan Gohman6a402dc2009-08-19 18:16:17 +00001924 MVT::i32, Reg);
1925
1926 // Emit a testl.
Dan Gohman602b0c82009-09-25 18:54:59 +00001927 return CurDAG->getMachineNode(X86::TEST32ri, dl, MVT::i32, Subreg, Imm);
Dan Gohman6a402dc2009-08-19 18:16:17 +00001928 }
1929 }
1930 break;
1931 }
Chris Lattnerc961eea2005-11-16 01:54:32 +00001932 }
1933
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001934 SDNode *ResNode = SelectCode(Node);
Evan Cheng64a752f2006-08-11 09:08:15 +00001935
Chris Lattner7c306da2010-03-02 06:34:30 +00001936 DEBUG(dbgs() << "=> ";
1937 if (ResNode == NULL || ResNode == Node)
1938 Node->dump(CurDAG);
1939 else
1940 ResNode->dump(CurDAG);
1941 dbgs() << '\n');
Evan Cheng64a752f2006-08-11 09:08:15 +00001942
1943 return ResNode;
Chris Lattnerc961eea2005-11-16 01:54:32 +00001944}
1945
Chris Lattnerc0bad572006-06-08 18:03:49 +00001946bool X86DAGToDAGISel::
Dan Gohman475871a2008-07-27 21:46:04 +00001947SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
Dan Gohmanf350b272008-08-23 02:25:05 +00001948 std::vector<SDValue> &OutOps) {
Rafael Espindola094fad32009-04-08 21:14:34 +00001949 SDValue Op0, Op1, Op2, Op3, Op4;
Chris Lattnerc0bad572006-06-08 18:03:49 +00001950 switch (ConstraintCode) {
1951 case 'o': // offsetable ??
1952 case 'v': // not offsetable ??
1953 default: return true;
1954 case 'm': // memory
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001955 if (!SelectAddr(Op.getNode(), Op, Op0, Op1, Op2, Op3, Op4))
Chris Lattnerc0bad572006-06-08 18:03:49 +00001956 return true;
1957 break;
1958 }
1959
Evan Cheng04699902006-08-26 01:05:16 +00001960 OutOps.push_back(Op0);
1961 OutOps.push_back(Op1);
1962 OutOps.push_back(Op2);
1963 OutOps.push_back(Op3);
Rafael Espindola094fad32009-04-08 21:14:34 +00001964 OutOps.push_back(Op4);
Chris Lattnerc0bad572006-06-08 18:03:49 +00001965 return false;
1966}
1967
Chris Lattnerc961eea2005-11-16 01:54:32 +00001968/// createX86ISelDag - This pass converts a legalized DAG into a
1969/// X86-specific DAG, ready for instruction scheduling.
1970///
Bill Wendling98a366d2009-04-29 23:29:43 +00001971FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM,
1972 llvm::CodeGenOpt::Level OptLevel) {
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +00001973 return new X86DAGToDAGISel(TM, OptLevel);
Chris Lattnerc961eea2005-11-16 01:54:32 +00001974}