1 //===-- AlphaISelDAGToDAG.cpp - Alpha pattern matching inst selector ------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a pattern matching instruction selector for Alpha,
11 // converting from a legalized dag to a Alpha dag.
13 //===----------------------------------------------------------------------===//
16 #include "AlphaTargetMachine.h"
17 #include "AlphaISelLowering.h"
18 #include "llvm/CodeGen/MachineInstrBuilder.h"
19 #include "llvm/CodeGen/MachineFrameInfo.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/CodeGen/SelectionDAG.h"
23 #include "llvm/CodeGen/SelectionDAGISel.h"
24 #include "llvm/Target/TargetOptions.h"
25 #include "llvm/Constants.h"
26 #include "llvm/DerivedTypes.h"
27 #include "llvm/GlobalValue.h"
28 #include "llvm/Intrinsics.h"
29 #include "llvm/Support/Compiler.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/MathExtras.h"
37 //===--------------------------------------------------------------------===//
38 /// AlphaDAGToDAGISel - Alpha specific code to select Alpha machine
39 /// instructions for SelectionDAG operations.
40 class AlphaDAGToDAGISel
: public SelectionDAGISel
{
41 static const int64_t IMM_LOW
= -32768;
42 static const int64_t IMM_HIGH
= 32767;
43 static const int64_t IMM_MULT
= 65536;
44 static const int64_t IMM_FULLHIGH
= IMM_HIGH
+ IMM_HIGH
* IMM_MULT
;
45 static const int64_t IMM_FULLLOW
= IMM_LOW
+ IMM_LOW
* IMM_MULT
;
47 static int64_t get_ldah16(int64_t x
) {
48 int64_t y
= x
/ IMM_MULT
;
49 if (x
% IMM_MULT
> IMM_HIGH
)
54 static int64_t get_lda16(int64_t x
) {
55 return x
- get_ldah16(x
) * IMM_MULT
;
58 /// get_zapImm - Return a zap mask if X is a valid immediate for a zapnot
59 /// instruction (if not, return 0). Note that this code accepts partial
60 /// zap masks. For example (and LHS, 1) is a valid zap, as long we know
61 /// that the bits 1-7 of LHS are already zero. If LHS is non-null, we are
62 /// in checking mode. If LHS is null, we assume that the mask has already
63 /// been validated before.
64 uint64_t get_zapImm(SDValue LHS
, uint64_t Constant
) {
65 uint64_t BitsToCheck
= 0;
67 for (unsigned i
= 0; i
!= 8; ++i
) {
68 if (((Constant
>> 8*i
) & 0xFF) == 0) {
72 if (((Constant
>> 8*i
) & 0xFF) == 0xFF) {
73 // If the entire byte is set, zapnot the byte.
74 } else if (LHS
.getNode() == 0) {
75 // Otherwise, if the mask was previously validated, we know its okay
76 // to zapnot this entire byte even though all the bits aren't set.
78 // Otherwise we don't know that the it's okay to zapnot this entire
79 // byte. Only do this iff we can prove that the missing bits are
80 // already null, so the bytezap doesn't need to really null them.
81 BitsToCheck
|= ~Constant
& (0xFF << 8*i
);
86 // If there are missing bits in a byte (for example, X & 0xEF00), check to
87 // see if the missing bits (0x1000) are already known zero if not, the zap
88 // isn't okay to do, as it won't clear all the required bits.
90 !CurDAG
->MaskedValueIsZero(LHS
,
91 APInt(LHS
.getValueSizeInBits(),
98 static uint64_t get_zapImm(uint64_t x
) {
100 for(int i
= 0; i
!= 8; ++i
) {
101 if ((x
& 0x00FF) == 0x00FF)
103 else if ((x
& 0x00FF) != 0)
111 static uint64_t getNearPower2(uint64_t x
) {
113 unsigned at
= CountLeadingZeros_64(x
);
114 uint64_t complow
= 1 << (63 - at
);
115 uint64_t comphigh
= 1 << (64 - at
);
116 //cerr << x << ":" << complow << ":" << comphigh << "\n";
117 if (abs(complow
- x
) <= abs(comphigh
- x
))
123 static bool chkRemNearPower2(uint64_t x
, uint64_t r
, bool swap
) {
124 uint64_t y
= getNearPower2(x
);
131 static bool isFPZ(SDValue N
) {
132 ConstantFPSDNode
*CN
= dyn_cast
<ConstantFPSDNode
>(N
);
133 return (CN
&& (CN
->getValueAPF().isZero()));
135 static bool isFPZn(SDValue N
) {
136 ConstantFPSDNode
*CN
= dyn_cast
<ConstantFPSDNode
>(N
);
137 return (CN
&& CN
->getValueAPF().isNegZero());
139 static bool isFPZp(SDValue N
) {
140 ConstantFPSDNode
*CN
= dyn_cast
<ConstantFPSDNode
>(N
);
141 return (CN
&& CN
->getValueAPF().isPosZero());
145 explicit AlphaDAGToDAGISel(AlphaTargetMachine
&TM
)
146 : SelectionDAGISel(TM
)
149 /// getI64Imm - Return a target constant with the specified value, of type
151 inline SDValue
getI64Imm(int64_t Imm
) {
152 return CurDAG
->getTargetConstant(Imm
, MVT::i64
);
155 // Select - Convert the specified operand from a target-independent to a
156 // target-specific node if it hasn't already been changed.
157 SDNode
*Select(SDValue Op
);
159 /// InstructionSelect - This callback is invoked by
160 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
161 virtual void InstructionSelect();
163 virtual const char *getPassName() const {
164 return "Alpha DAG->DAG Pattern Instruction Selection";
167 /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
168 /// inline asm expressions.
169 virtual bool SelectInlineAsmMemoryOperand(const SDValue
&Op
,
171 std::vector
<SDValue
> &OutOps
) {
173 switch (ConstraintCode
) {
174 default: return true;
180 OutOps
.push_back(Op0
);
184 // Include the pieces autogenerated from the target description.
185 #include "AlphaGenDAGISel.inc"
188 SDValue
getGlobalBaseReg();
189 SDValue
getGlobalRetAddr();
190 void SelectCALL(SDValue Op
);
195 /// getGlobalBaseReg - Output the instructions required to put the
196 /// GOT address into a register.
198 SDValue
AlphaDAGToDAGISel::getGlobalBaseReg() {
200 for(MachineRegisterInfo::livein_iterator ii
= RegInfo
->livein_begin(),
201 ee
= RegInfo
->livein_end(); ii
!= ee
; ++ii
)
202 if (ii
->first
== Alpha::R29
) {
206 assert(GP
&& "GOT PTR not in liveins");
207 // FIXME is there anywhere sensible to get a DebugLoc here?
208 return CurDAG
->getCopyFromReg(CurDAG
->getEntryNode(),
209 DebugLoc::getUnknownLoc(), GP
, MVT::i64
);
212 /// getRASaveReg - Grab the return address
214 SDValue
AlphaDAGToDAGISel::getGlobalRetAddr() {
216 for(MachineRegisterInfo::livein_iterator ii
= RegInfo
->livein_begin(),
217 ee
= RegInfo
->livein_end(); ii
!= ee
; ++ii
)
218 if (ii
->first
== Alpha::R26
) {
222 assert(RA
&& "RA PTR not in liveins");
223 // FIXME is there anywhere sensible to get a DebugLoc here?
224 return CurDAG
->getCopyFromReg(CurDAG
->getEntryNode(),
225 DebugLoc::getUnknownLoc(), RA
, MVT::i64
);
228 /// InstructionSelect - This callback is invoked by
229 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
230 void AlphaDAGToDAGISel::InstructionSelect() {
233 // Select target instructions for the DAG.
235 CurDAG
->RemoveDeadNodes();
238 // Select - Convert the specified operand from a target-independent to a
239 // target-specific node if it hasn't already been changed.
240 SDNode
*AlphaDAGToDAGISel::Select(SDValue Op
) {
241 SDNode
*N
= Op
.getNode();
242 if (N
->isMachineOpcode()) {
243 return NULL
; // Already selected.
245 DebugLoc dl
= N
->getDebugLoc();
247 switch (N
->getOpcode()) {
253 case ISD::FrameIndex
: {
254 int FI
= cast
<FrameIndexSDNode
>(N
)->getIndex();
255 return CurDAG
->SelectNodeTo(N
, Alpha::LDA
, MVT::i64
,
256 CurDAG
->getTargetFrameIndex(FI
, MVT::i32
),
259 case ISD::GLOBAL_OFFSET_TABLE
: {
260 SDValue Result
= getGlobalBaseReg();
261 ReplaceUses(Op
, Result
);
264 case AlphaISD::GlobalRetAddr
: {
265 SDValue Result
= getGlobalRetAddr();
266 ReplaceUses(Op
, Result
);
270 case AlphaISD::DivCall
: {
271 SDValue Chain
= CurDAG
->getEntryNode();
272 SDValue N0
= Op
.getOperand(0);
273 SDValue N1
= Op
.getOperand(1);
274 SDValue N2
= Op
.getOperand(2);
275 Chain
= CurDAG
->getCopyToReg(Chain
, dl
, Alpha::R24
, N1
,
277 Chain
= CurDAG
->getCopyToReg(Chain
, dl
, Alpha::R25
, N2
,
279 Chain
= CurDAG
->getCopyToReg(Chain
, dl
, Alpha::R27
, N0
,
282 CurDAG
->getTargetNode(Alpha::JSRs
, dl
, MVT::Other
, MVT::Flag
,
283 Chain
, Chain
.getValue(1));
284 Chain
= CurDAG
->getCopyFromReg(Chain
, dl
, Alpha::R27
, MVT::i64
,
286 return CurDAG
->SelectNodeTo(N
, Alpha::BISr
, MVT::i64
, Chain
, Chain
);
289 case ISD::READCYCLECOUNTER
: {
290 SDValue Chain
= N
->getOperand(0);
291 return CurDAG
->getTargetNode(Alpha::RPCC
, dl
, MVT::i64
, MVT::Other
,
295 case ISD::Constant
: {
296 uint64_t uval
= cast
<ConstantSDNode
>(N
)->getZExtValue();
299 SDValue Result
= CurDAG
->getCopyFromReg(CurDAG
->getEntryNode(), dl
,
300 Alpha::R31
, MVT::i64
);
301 ReplaceUses(Op
, Result
);
305 int64_t val
= (int64_t)uval
;
306 int32_t val32
= (int32_t)val
;
307 if (val
<= IMM_HIGH
+ IMM_HIGH
* IMM_MULT
&&
308 val
>= IMM_LOW
+ IMM_LOW
* IMM_MULT
)
309 break; //(LDAH (LDA))
310 if ((uval
>> 32) == 0 && //empty upper bits
311 val32
<= IMM_HIGH
+ IMM_HIGH
* IMM_MULT
)
312 // val32 >= IMM_LOW + IMM_LOW * IMM_MULT) //always true
313 break; //(zext (LDAH (LDA)))
314 //Else use the constant pool
315 ConstantInt
*C
= ConstantInt::get(Type::Int64Ty
, uval
);
316 SDValue CPI
= CurDAG
->getTargetConstantPool(C
, MVT::i64
);
317 SDNode
*Tmp
= CurDAG
->getTargetNode(Alpha::LDAHr
, dl
, MVT::i64
, CPI
,
319 return CurDAG
->SelectNodeTo(N
, Alpha::LDQr
, MVT::i64
, MVT::Other
,
320 CPI
, SDValue(Tmp
, 0), CurDAG
->getEntryNode());
322 case ISD::TargetConstantFP
:
323 case ISD::ConstantFP
: {
324 ConstantFPSDNode
*CN
= cast
<ConstantFPSDNode
>(N
);
325 bool isDouble
= N
->getValueType(0) == MVT::f64
;
326 MVT T
= isDouble
? MVT::f64
: MVT::f32
;
327 if (CN
->getValueAPF().isPosZero()) {
328 return CurDAG
->SelectNodeTo(N
, isDouble
? Alpha::CPYST
: Alpha::CPYSS
,
329 T
, CurDAG
->getRegister(Alpha::F31
, T
),
330 CurDAG
->getRegister(Alpha::F31
, T
));
331 } else if (CN
->getValueAPF().isNegZero()) {
332 return CurDAG
->SelectNodeTo(N
, isDouble
? Alpha::CPYSNT
: Alpha::CPYSNS
,
333 T
, CurDAG
->getRegister(Alpha::F31
, T
),
334 CurDAG
->getRegister(Alpha::F31
, T
));
342 if (N
->getOperand(0).getNode()->getValueType(0).isFloatingPoint()) {
343 ISD::CondCode CC
= cast
<CondCodeSDNode
>(N
->getOperand(2))->get();
345 unsigned Opc
= Alpha::WTF
;
349 default: DEBUG(N
->dump(CurDAG
)); assert(0 && "Unknown FP comparison!");
350 case ISD::SETEQ
: case ISD::SETOEQ
: case ISD::SETUEQ
:
351 Opc
= Alpha::CMPTEQ
; break;
352 case ISD::SETLT
: case ISD::SETOLT
: case ISD::SETULT
:
353 Opc
= Alpha::CMPTLT
; break;
354 case ISD::SETLE
: case ISD::SETOLE
: case ISD::SETULE
:
355 Opc
= Alpha::CMPTLE
; break;
356 case ISD::SETGT
: case ISD::SETOGT
: case ISD::SETUGT
:
357 Opc
= Alpha::CMPTLT
; rev
= true; break;
358 case ISD::SETGE
: case ISD::SETOGE
: case ISD::SETUGE
:
359 Opc
= Alpha::CMPTLE
; rev
= true; break;
360 case ISD::SETNE
: case ISD::SETONE
: case ISD::SETUNE
:
361 Opc
= Alpha::CMPTEQ
; inv
= true; break;
363 Opc
= Alpha::CMPTUN
; inv
= true; break;
365 Opc
= Alpha::CMPTUN
; break;
367 SDValue tmp1
= N
->getOperand(rev
?1:0);
368 SDValue tmp2
= N
->getOperand(rev
?0:1);
369 SDNode
*cmp
= CurDAG
->getTargetNode(Opc
, dl
, MVT::f64
, tmp1
, tmp2
);
371 cmp
= CurDAG
->getTargetNode(Alpha::CMPTEQ
, dl
,
372 MVT::f64
, SDValue(cmp
, 0),
373 CurDAG
->getRegister(Alpha::F31
, MVT::f64
));
375 case ISD::SETUEQ
: case ISD::SETULT
: case ISD::SETULE
:
376 case ISD::SETUNE
: case ISD::SETUGT
: case ISD::SETUGE
:
378 SDNode
* cmp2
= CurDAG
->getTargetNode(Alpha::CMPTUN
, dl
, MVT::f64
,
380 cmp
= CurDAG
->getTargetNode(Alpha::ADDT
, dl
, MVT::f64
,
381 SDValue(cmp2
, 0), SDValue(cmp
, 0));
387 SDNode
* LD
= CurDAG
->getTargetNode(Alpha::FTOIT
, dl
,
388 MVT::i64
, SDValue(cmp
, 0));
389 return CurDAG
->getTargetNode(Alpha::CMPULT
, dl
, MVT::i64
,
390 CurDAG
->getRegister(Alpha::R31
, MVT::i64
),
396 if (N
->getValueType(0).isFloatingPoint() &&
397 (N
->getOperand(0).getOpcode() != ISD::SETCC
||
398 !N
->getOperand(0).getOperand(1).getValueType().isFloatingPoint())) {
399 //This should be the condition not covered by the Patterns
400 //FIXME: Don't have SelectCode die, but rather return something testable
401 // so that things like this can be caught in fall though code
403 bool isDouble
= N
->getValueType(0) == MVT::f64
;
404 SDValue cond
= N
->getOperand(0);
405 SDValue TV
= N
->getOperand(1);
406 SDValue FV
= N
->getOperand(2);
408 SDNode
* LD
= CurDAG
->getTargetNode(Alpha::ITOFT
, dl
, MVT::f64
, cond
);
409 return CurDAG
->getTargetNode(isDouble
?Alpha::FCMOVNET
:Alpha::FCMOVNES
,
410 dl
, MVT::f64
, FV
, TV
, SDValue(LD
,0));
415 ConstantSDNode
* SC
= NULL
;
416 ConstantSDNode
* MC
= NULL
;
417 if (N
->getOperand(0).getOpcode() == ISD::SRL
&&
418 (MC
= dyn_cast
<ConstantSDNode
>(N
->getOperand(1))) &&
419 (SC
= dyn_cast
<ConstantSDNode
>(N
->getOperand(0).getOperand(1)))) {
420 uint64_t sval
= SC
->getZExtValue();
421 uint64_t mval
= MC
->getZExtValue();
422 // If the result is a zap, let the autogened stuff handle it.
423 if (get_zapImm(N
->getOperand(0), mval
))
425 // given mask X, and shift S, we want to see if there is any zap in the
426 // mask if we play around with the botton S bits
427 uint64_t dontcare
= (~0ULL) >> (64 - sval
);
428 uint64_t mask
= mval
<< sval
;
430 if (get_zapImm(mask
| dontcare
))
431 mask
= mask
| dontcare
;
433 if (get_zapImm(mask
)) {
435 SDValue(CurDAG
->getTargetNode(Alpha::ZAPNOTi
, dl
, MVT::i64
,
436 N
->getOperand(0).getOperand(0),
437 getI64Imm(get_zapImm(mask
))), 0);
438 return CurDAG
->getTargetNode(Alpha::SRLr
, dl
, MVT::i64
, Z
,
447 return SelectCode(Op
);
450 void AlphaDAGToDAGISel::SelectCALL(SDValue Op
) {
451 //TODO: add flag stuff to prevent nondeturministic breakage!
453 SDNode
*N
= Op
.getNode();
454 SDValue Chain
= N
->getOperand(0);
455 SDValue Addr
= N
->getOperand(1);
456 SDValue
InFlag(0,0); // Null incoming flag value.
457 DebugLoc dl
= N
->getDebugLoc();
459 std::vector
<SDValue
> CallOperands
;
460 std::vector
<MVT
> TypeOperands
;
463 for(int i
= 2, e
= N
->getNumOperands(); i
< e
; ++i
) {
464 TypeOperands
.push_back(N
->getOperand(i
).getValueType());
465 CallOperands
.push_back(N
->getOperand(i
));
467 int count
= N
->getNumOperands() - 2;
469 static const unsigned args_int
[] = {Alpha::R16
, Alpha::R17
, Alpha::R18
,
470 Alpha::R19
, Alpha::R20
, Alpha::R21
};
471 static const unsigned args_float
[] = {Alpha::F16
, Alpha::F17
, Alpha::F18
,
472 Alpha::F19
, Alpha::F20
, Alpha::F21
};
474 for (int i
= 6; i
< count
; ++i
) {
475 unsigned Opc
= Alpha::WTF
;
476 if (TypeOperands
[i
].isInteger()) {
478 } else if (TypeOperands
[i
] == MVT::f32
) {
480 } else if (TypeOperands
[i
] == MVT::f64
) {
483 assert(0 && "Unknown operand");
485 SDValue Ops
[] = { CallOperands
[i
], getI64Imm((i
- 6) * 8),
486 CurDAG
->getCopyFromReg(Chain
, dl
, Alpha::R30
, MVT::i64
),
488 Chain
= SDValue(CurDAG
->getTargetNode(Opc
, dl
, MVT::Other
, Ops
, 4), 0);
490 for (int i
= 0; i
< std::min(6, count
); ++i
) {
491 if (TypeOperands
[i
].isInteger()) {
492 Chain
= CurDAG
->getCopyToReg(Chain
, dl
, args_int
[i
],
493 CallOperands
[i
], InFlag
);
494 InFlag
= Chain
.getValue(1);
495 } else if (TypeOperands
[i
] == MVT::f32
|| TypeOperands
[i
] == MVT::f64
) {
496 Chain
= CurDAG
->getCopyToReg(Chain
, dl
, args_float
[i
],
497 CallOperands
[i
], InFlag
);
498 InFlag
= Chain
.getValue(1);
500 assert(0 && "Unknown operand");
503 // Finally, once everything is in registers to pass to the call, emit the
505 if (Addr
.getOpcode() == AlphaISD::GPRelLo
) {
506 SDValue GOT
= getGlobalBaseReg();
507 Chain
= CurDAG
->getCopyToReg(Chain
, dl
, Alpha::R29
, GOT
, InFlag
);
508 InFlag
= Chain
.getValue(1);
509 Chain
= SDValue(CurDAG
->getTargetNode(Alpha::BSR
, dl
, MVT::Other
,
510 MVT::Flag
, Addr
.getOperand(0),
513 Chain
= CurDAG
->getCopyToReg(Chain
, dl
, Alpha::R27
, Addr
, InFlag
);
514 InFlag
= Chain
.getValue(1);
515 Chain
= SDValue(CurDAG
->getTargetNode(Alpha::JSR
, dl
, MVT::Other
,
516 MVT::Flag
, Chain
, InFlag
), 0);
518 InFlag
= Chain
.getValue(1);
520 std::vector
<SDValue
> CallResults
;
522 switch (N
->getValueType(0).getSimpleVT()) {
523 default: assert(0 && "Unexpected ret value!");
524 case MVT::Other
: break;
526 Chain
= CurDAG
->getCopyFromReg(Chain
, dl
,
527 Alpha::R0
, MVT::i64
, InFlag
).getValue(1);
528 CallResults
.push_back(Chain
.getValue(0));
531 Chain
= CurDAG
->getCopyFromReg(Chain
, dl
,
532 Alpha::F0
, MVT::f32
, InFlag
).getValue(1);
533 CallResults
.push_back(Chain
.getValue(0));
536 Chain
= CurDAG
->getCopyFromReg(Chain
, dl
,
537 Alpha::F0
, MVT::f64
, InFlag
).getValue(1);
538 CallResults
.push_back(Chain
.getValue(0));
542 CallResults
.push_back(Chain
);
543 for (unsigned i
= 0, e
= CallResults
.size(); i
!= e
; ++i
)
544 ReplaceUses(Op
.getValue(i
), CallResults
[i
]);
548 /// createAlphaISelDag - This pass converts a legalized DAG into a
549 /// Alpha-specific DAG, ready for instruction scheduling.
551 FunctionPass
*llvm::createAlphaISelDag(AlphaTargetMachine
&TM
) {
552 return new AlphaDAGToDAGISel(TM
);