/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

Bug Summary

File:	lib/Target/PowerPC/PPCISelDAGToDAG.cpp
Location:	line 567, column 12
Description:	Value stored to 'Hi' during its initialization is never read

Annotated Source Code

1	//===-- PPCISelDAGToDAG.cpp - PPC --pattern matching inst selector --------===//
2	//
3	// The LLVM Compiler Infrastructure
4	//
5	// This file is distributed under the University of Illinois Open Source
6	// License. See LICENSE.TXT for details.
7	//
8	//===----------------------------------------------------------------------===//
9	//
10	// This file defines a pattern matching instruction selector for PowerPC,
11	// converting from a legalized dag to a PPC dag.
12	//
13	//===----------------------------------------------------------------------===//
14
15	#include "PPC.h"
16	#include "MCTargetDesc/PPCPredicates.h"
17	#include "PPCMachineFunctionInfo.h"
18	#include "PPCTargetMachine.h"
19	#include "llvm/CodeGen/MachineFunction.h"
20	#include "llvm/CodeGen/MachineInstrBuilder.h"
21	#include "llvm/CodeGen/MachineRegisterInfo.h"
22	#include "llvm/CodeGen/SelectionDAG.h"
23	#include "llvm/CodeGen/SelectionDAGISel.h"
24	#include "llvm/IR/Constants.h"
25	#include "llvm/IR/Function.h"
26	#include "llvm/IR/GlobalAlias.h"
27	#include "llvm/IR/GlobalValue.h"
28	#include "llvm/IR/GlobalVariable.h"
29	#include "llvm/IR/Intrinsics.h"
30	#include "llvm/IR/Module.h"
31	#include "llvm/Support/CommandLine.h"
32	#include "llvm/Support/Debug.h"
33	#include "llvm/Support/ErrorHandling.h"
34	#include "llvm/Support/MathExtras.h"
35	#include "llvm/Support/raw_ostream.h"
36	#include "llvm/Target/TargetOptions.h"
37	using namespace llvm;
38
39	#define DEBUG_TYPE"ppc-codegen" "ppc-codegen"
40
41	// FIXME: Remove this once the bug has been fixed!
42	cl::opt<bool> ANDIGlueBug("expose-ppc-andi-glue-bug",
43	cl::desc("expose the ANDI glue bug on PPC"), cl::Hidden);
44
45	static cl::opt<bool>
46	UseBitPermRewriter("ppc-use-bit-perm-rewriter", cl::init(true),
47	cl::desc("use aggressive ppc isel for bit permutations"),
48	cl::Hidden);
49	static cl::opt<bool> BPermRewriterNoMasking(
50	"ppc-bit-perm-rewriter-stress-rotates",
51	cl::desc("stress rotate selection in aggressive ppc isel for "
52	"bit permutations"),
53	cl::Hidden);
54
55	namespace llvm {
56	void initializePPCDAGToDAGISelPass(PassRegistry&);
57	}
58
59	namespace {
60	//===--------------------------------------------------------------------===//
61	/// PPCDAGToDAGISel - PPC specific code to select PPC machine
62	/// instructions for SelectionDAG operations.
63	///
64	class PPCDAGToDAGISel : public SelectionDAGISel {
65	const PPCTargetMachine &TM;
66	const PPCSubtarget *PPCSubTarget;
67	const PPCTargetLowering *PPCLowering;
68	unsigned GlobalBaseReg;
69	public:
70	explicit PPCDAGToDAGISel(PPCTargetMachine &tm)
71	: SelectionDAGISel(tm), TM(tm) {
72	initializePPCDAGToDAGISelPass(*PassRegistry::getPassRegistry());
73	}
74
75	bool runOnMachineFunction(MachineFunction &MF) override {
76	// Make sure we re-emit a set of the global base reg if necessary
77	GlobalBaseReg = 0;
78	PPCSubTarget = &MF.getSubtarget<PPCSubtarget>();
79	PPCLowering = PPCSubTarget->getTargetLowering();
80	SelectionDAGISel::runOnMachineFunction(MF);
81
82	if (!PPCSubTarget->isSVR4ABI())
83	InsertVRSaveCode(MF);
84
85	return true;
86	}
87
88	void PreprocessISelDAG() override;
89	void PostprocessISelDAG() override;
90
91	/// getI32Imm - Return a target constant with the specified value, of type
92	/// i32.
93	inline SDValue getI32Imm(unsigned Imm, SDLoc dl) {
94	return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
95	}
96
97	/// getI64Imm - Return a target constant with the specified value, of type
98	/// i64.
99	inline SDValue getI64Imm(uint64_t Imm, SDLoc dl) {
100	return CurDAG->getTargetConstant(Imm, dl, MVT::i64);
101	}
102
103	/// getSmallIPtrImm - Return a target constant of pointer type.
104	inline SDValue getSmallIPtrImm(unsigned Imm, SDLoc dl) {
105	return CurDAG->getTargetConstant(
106	Imm, dl, PPCLowering->getPointerTy(CurDAG->getDataLayout()));
107	}
108
109	/// isRotateAndMask - Returns true if Mask and Shift can be folded into a
110	/// rotate and mask opcode and mask operation.
111	static bool isRotateAndMask(SDNode *N, unsigned Mask, bool isShiftMask,
112	unsigned &SH, unsigned &MB, unsigned &ME);
113
114	/// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
115	/// base register. Return the virtual register that holds this value.
116	SDNode *getGlobalBaseReg();
117
118	SDNode getFrameIndex(SDNode SN, SDNode *N, unsigned Offset = 0);
119
120	// Select - Convert the specified operand from a target-independent to a
121	// target-specific node if it hasn't already been changed.
122	SDNode Select(SDNode N) override;
123
124	SDNode SelectBitfieldInsert(SDNode N);
125	SDNode SelectBitPermutation(SDNode N);
126
127	/// SelectCC - Select a comparison of the specified values with the
128	/// specified condition code, returning the CR# of the expression.
129	SDValue SelectCC(SDValue LHS, SDValue RHS, ISD::CondCode CC, SDLoc dl);
130
131	/// SelectAddrImm - Returns true if the address N can be represented by
132	/// a base register plus a signed 16-bit displacement [r+imm].
133	bool SelectAddrImm(SDValue N, SDValue &Disp,
134	SDValue &Base) {
135	return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG, false);
136	}
137
138	/// SelectAddrImmOffs - Return true if the operand is valid for a preinc
139	/// immediate field. Note that the operand at this point is already the
140	/// result of a prior SelectAddressRegImm call.
141	bool SelectAddrImmOffs(SDValue N, SDValue &Out) const {
142	if (N.getOpcode() == ISD::TargetConstant \|\|
143	N.getOpcode() == ISD::TargetGlobalAddress) {
144	Out = N;
145	return true;
146	}
147
148	return false;
149	}
150
151	/// SelectAddrIdx - Given the specified addressed, check to see if it can be
152	/// represented as an indexed [r+r] operation. Returns false if it can
153	/// be represented by [r+imm], which are preferred.
154	bool SelectAddrIdx(SDValue N, SDValue &Base, SDValue &Index) {
155	return PPCLowering->SelectAddressRegReg(N, Base, Index, *CurDAG);
156	}
157
158	/// SelectAddrIdxOnly - Given the specified addressed, force it to be
159	/// represented as an indexed [r+r] operation.
160	bool SelectAddrIdxOnly(SDValue N, SDValue &Base, SDValue &Index) {
161	return PPCLowering->SelectAddressRegRegOnly(N, Base, Index, *CurDAG);
162	}
163
164	/// SelectAddrImmX4 - Returns true if the address N can be represented by
165	/// a base register plus a signed 16-bit displacement that is a multiple of 4.
166	/// Suitable for use by STD and friends.
167	bool SelectAddrImmX4(SDValue N, SDValue &Disp, SDValue &Base) {
168	return PPCLowering->SelectAddressRegImm(N, Disp, Base, *CurDAG, true);
169	}
170
171	// Select an address into a single register.
172	bool SelectAddr(SDValue N, SDValue &Base) {
173	Base = N;
174	return true;
175	}
176
177	/// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
178	/// inline asm expressions. It is always correct to compute the value into
179	/// a register. The case of adding a (possibly relocatable) constant to a
180	/// register can be improved, but it is wrong to substitute Reg+Reg for
181	/// Reg in an asm, because the load or store opcode would have to change.
182	bool SelectInlineAsmMemoryOperand(const SDValue &Op,
183	unsigned ConstraintID,
184	std::vector<SDValue> &OutOps) override {
185
186	switch(ConstraintID) {
187	default:
188	errs() << "ConstraintID: " << ConstraintID << "\n";
189	llvm_unreachable("Unexpected asm memory constraint")::llvm::llvm_unreachable_internal("Unexpected asm memory constraint" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 189);
190	case InlineAsm::Constraint_es:
191	case InlineAsm::Constraint_i:
192	case InlineAsm::Constraint_m:
193	case InlineAsm::Constraint_o:
194	case InlineAsm::Constraint_Q:
195	case InlineAsm::Constraint_Z:
196	case InlineAsm::Constraint_Zy:
197	// We need to make sure that this one operand does not end up in r0
198	// (because we might end up lowering this as 0(%op)).
199	const TargetRegisterInfo *TRI = PPCSubTarget->getRegisterInfo();
200	const TargetRegisterClass TRC = TRI->getPointerRegClass(MF, /Kind=/1);
201	SDLoc dl(Op);
202	SDValue RC = CurDAG->getTargetConstant(TRC->getID(), dl, MVT::i32);
203	SDValue NewOp =
204	SDValue(CurDAG->getMachineNode(TargetOpcode::COPY_TO_REGCLASS,
205	dl, Op.getValueType(),
206	Op, RC), 0);
207
208	OutOps.push_back(NewOp);
209	return false;
210	}
211	return true;
212	}
213
214	void InsertVRSaveCode(MachineFunction &MF);
215
216	const char *getPassName() const override {
217	return "PowerPC DAG->DAG Pattern Instruction Selection";
218	}
219
220	// Include the pieces autogenerated from the target description.
221	#include "PPCGenDAGISel.inc"
222
223	private:
224	SDNode SelectSETCC(SDNode N);
225
226	void PeepholePPC64();
227	void PeepholePPC64ZExt();
228	void PeepholeCROps();
229
230	SDValue combineToCMPB(SDNode *N);
231	void foldBoolExts(SDValue &Res, SDNode *&N);
232
233	bool AllUsersSelectZero(SDNode *N);
234	void SwapAllSelectUsers(SDNode *N);
235
236	SDNode transferMemOperands(SDNode N, SDNode *Result);
237	};
238	}
239
240	/// InsertVRSaveCode - Once the entire function has been instruction selected,
241	/// all virtual registers are created and all machine instructions are built,
242	/// check to see if we need to save/restore VRSAVE. If so, do it.
243	void PPCDAGToDAGISel::InsertVRSaveCode(MachineFunction &Fn) {
244	// Check to see if this function uses vector registers, which means we have to
245	// save and restore the VRSAVE register and update it with the regs we use.
246	//
247	// In this case, there will be virtual registers of vector type created
248	// by the scheduler. Detect them now.
249	bool HasVectorVReg = false;
250	for (unsigned i = 0, e = RegInfo->getNumVirtRegs(); i != e; ++i) {
251	unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
252	if (RegInfo->getRegClass(Reg) == &PPC::VRRCRegClass) {
253	HasVectorVReg = true;
254	break;
255	}
256	}
257	if (!HasVectorVReg) return; // nothing to do.
258
259	// If we have a vector register, we want to emit code into the entry and exit
260	// blocks to save and restore the VRSAVE register. We do this here (instead
261	// of marking all vector instructions as clobbering VRSAVE) for two reasons:
262	//
263	// 1. This (trivially) reduces the load on the register allocator, by not
264	// having to represent the live range of the VRSAVE register.
265	// 2. This (more significantly) allows us to create a temporary virtual
266	// register to hold the saved VRSAVE value, allowing this temporary to be
267	// register allocated, instead of forcing it to be spilled to the stack.
268
269	// Create two vregs - one to hold the VRSAVE register that is live-in to the
270	// function and one for the value after having bits or'd into it.
271	unsigned InVRSAVE = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
272	unsigned UpdatedVRSAVE = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
273
274	const TargetInstrInfo &TII = *PPCSubTarget->getInstrInfo();
275	MachineBasicBlock &EntryBB = *Fn.begin();
276	DebugLoc dl;
277	// Emit the following code into the entry block:
278	// InVRSAVE = MFVRSAVE
279	// UpdatedVRSAVE = UPDATE_VRSAVE InVRSAVE
280	// MTVRSAVE UpdatedVRSAVE
281	MachineBasicBlock::iterator IP = EntryBB.begin(); // Insert Point
282	BuildMI(EntryBB, IP, dl, TII.get(PPC::MFVRSAVE), InVRSAVE);
283	BuildMI(EntryBB, IP, dl, TII.get(PPC::UPDATE_VRSAVE),
284	UpdatedVRSAVE).addReg(InVRSAVE);
285	BuildMI(EntryBB, IP, dl, TII.get(PPC::MTVRSAVE)).addReg(UpdatedVRSAVE);
286
287	// Find all return blocks, outputting a restore in each epilog.
288	for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
289	if (BB->isReturnBlock()) {
290	IP = BB->end(); --IP;
291
292	// Skip over all terminator instructions, which are part of the return
293	// sequence.
294	MachineBasicBlock::iterator I2 = IP;
295	while (I2 != BB->begin() && (--I2)->isTerminator())
296	IP = I2;
297
298	// Emit: MTVRSAVE InVRSave
299	BuildMI(*BB, IP, dl, TII.get(PPC::MTVRSAVE)).addReg(InVRSAVE);
300	}
301	}
302	}
303
304
305	/// getGlobalBaseReg - Output the instructions required to put the
306	/// base address to use for accessing globals into a register.
307	///
308	SDNode *PPCDAGToDAGISel::getGlobalBaseReg() {
309	if (!GlobalBaseReg) {
310	const TargetInstrInfo &TII = *PPCSubTarget->getInstrInfo();
311	// Insert the set of GlobalBaseReg into the first MBB of the function
312	MachineBasicBlock &FirstMBB = MF->front();
313	MachineBasicBlock::iterator MBBI = FirstMBB.begin();
314	const Module *M = MF->getFunction()->getParent();
315	DebugLoc dl;
316
317	if (PPCLowering->getPointerTy(CurDAG->getDataLayout()) == MVT::i32) {
318	if (PPCSubTarget->isTargetELF()) {
319	GlobalBaseReg = PPC::R30;
320	if (M->getPICLevel() == PICLevel::Small) {
321	BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MoveGOTtoLR));
322	BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
323	MF->getInfo<PPCFunctionInfo>()->setUsesPICBase(true);
324	} else {
325	BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR));
326	BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
327	unsigned TempReg = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
328	BuildMI(FirstMBB, MBBI, dl,
329	TII.get(PPC::UpdateGBR), GlobalBaseReg)
330	.addReg(TempReg, RegState::Define).addReg(GlobalBaseReg);
331	MF->getInfo<PPCFunctionInfo>()->setUsesPICBase(true);
332	}
333	} else {
334	GlobalBaseReg =
335	RegInfo->createVirtualRegister(&PPC::GPRC_NOR0RegClass);
336	BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR));
337	BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
338	}
339	} else {
340	GlobalBaseReg = RegInfo->createVirtualRegister(&PPC::G8RC_NOX0RegClass);
341	BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR8));
342	BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR8), GlobalBaseReg);
343	}
344	}
345	return CurDAG->getRegister(GlobalBaseReg,
346	PPCLowering->getPointerTy(CurDAG->getDataLayout()))
347	.getNode();
348	}
349
350	/// isIntS16Immediate - This method tests to see if the node is either a 32-bit
351	/// or 64-bit immediate, and if the value can be accurately represented as a
352	/// sign extension from a 16-bit value. If so, this returns true and the
353	/// immediate.
354	static bool isIntS16Immediate(SDNode *N, short &Imm) {
355	if (N->getOpcode() != ISD::Constant)
356	return false;
357
358	Imm = (short)cast<ConstantSDNode>(N)->getZExtValue();
359	if (N->getValueType(0) == MVT::i32)
360	return Imm == (int32_t)cast<ConstantSDNode>(N)->getZExtValue();
361	else
362	return Imm == (int64_t)cast<ConstantSDNode>(N)->getZExtValue();
363	}
364
365	static bool isIntS16Immediate(SDValue Op, short &Imm) {
366	return isIntS16Immediate(Op.getNode(), Imm);
367	}
368
369
370	/// isInt32Immediate - This method tests to see if the node is a 32-bit constant
371	/// operand. If so Imm will receive the 32-bit value.
372	static bool isInt32Immediate(SDNode *N, unsigned &Imm) {
373	if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i32) {
374	Imm = cast<ConstantSDNode>(N)->getZExtValue();
375	return true;
376	}
377	return false;
378	}
379
380	/// isInt64Immediate - This method tests to see if the node is a 64-bit constant
381	/// operand. If so Imm will receive the 64-bit value.
382	static bool isInt64Immediate(SDNode *N, uint64_t &Imm) {
383	if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i64) {
384	Imm = cast<ConstantSDNode>(N)->getZExtValue();
385	return true;
386	}
387	return false;
388	}
389
390	// isInt32Immediate - This method tests to see if a constant operand.
391	// If so Imm will receive the 32 bit value.
392	static bool isInt32Immediate(SDValue N, unsigned &Imm) {
393	return isInt32Immediate(N.getNode(), Imm);
394	}
395
396
397	// isOpcWithIntImmediate - This method tests to see if the node is a specific
398	// opcode and that it has a immediate integer right operand.
399	// If so Imm will receive the 32 bit value.
400	static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
401	return N->getOpcode() == Opc
402	&& isInt32Immediate(N->getOperand(1).getNode(), Imm);
403	}
404
405	SDNode PPCDAGToDAGISel::getFrameIndex(SDNode SN, SDNode *N, unsigned Offset) {
406	SDLoc dl(SN);
407	int FI = cast<FrameIndexSDNode>(N)->getIndex();
408	SDValue TFI = CurDAG->getTargetFrameIndex(FI, N->getValueType(0));
409	unsigned Opc = N->getValueType(0) == MVT::i32 ? PPC::ADDI : PPC::ADDI8;
410	if (SN->hasOneUse())
411	return CurDAG->SelectNodeTo(SN, Opc, N->getValueType(0), TFI,
412	getSmallIPtrImm(Offset, dl));
413	return CurDAG->getMachineNode(Opc, dl, N->getValueType(0), TFI,
414	getSmallIPtrImm(Offset, dl));
415	}
416
417	bool PPCDAGToDAGISel::isRotateAndMask(SDNode *N, unsigned Mask,
418	bool isShiftMask, unsigned &SH,
419	unsigned &MB, unsigned &ME) {
420	// Don't even go down this path for i64, since different logic will be
421	// necessary for rldicl/rldicr/rldimi.
422	if (N->getValueType(0) != MVT::i32)
423	return false;
424
425	unsigned Shift = 32;
426	unsigned Indeterminant = ~0; // bit mask marking indeterminant results
427	unsigned Opcode = N->getOpcode();
428	if (N->getNumOperands() != 2 \|\|
429	!isInt32Immediate(N->getOperand(1).getNode(), Shift) \|\| (Shift > 31))
430	return false;
431
432	if (Opcode == ISD::SHL) {
433	// apply shift left to mask if it comes first
434	if (isShiftMask) Mask = Mask << Shift;
435	// determine which bits are made indeterminant by shift
436	Indeterminant = ~(0xFFFFFFFFu << Shift);
437	} else if (Opcode == ISD::SRL) {
438	// apply shift right to mask if it comes first
439	if (isShiftMask) Mask = Mask >> Shift;
440	// determine which bits are made indeterminant by shift
441	Indeterminant = ~(0xFFFFFFFFu >> Shift);
442	// adjust for the left rotate
443	Shift = 32 - Shift;
444	} else if (Opcode == ISD::ROTL) {
445	Indeterminant = 0;
446	} else {
447	return false;
448	}
449
450	// if the mask doesn't intersect any Indeterminant bits
451	if (Mask && !(Mask & Indeterminant)) {
452	SH = Shift & 31;
453	// make sure the mask is still a mask (wrap arounds may not be)
454	return isRunOfOnes(Mask, MB, ME);
455	}
456	return false;
457	}
458
459	/// SelectBitfieldInsert - turn an or of two masked values into
460	/// the rotate left word immediate then mask insert (rlwimi) instruction.
461	SDNode PPCDAGToDAGISel::SelectBitfieldInsert(SDNode N) {
462	SDValue Op0 = N->getOperand(0);
463	SDValue Op1 = N->getOperand(1);
464	SDLoc dl(N);
465
466	APInt LKZ, LKO, RKZ, RKO;
467	CurDAG->computeKnownBits(Op0, LKZ, LKO);
468	CurDAG->computeKnownBits(Op1, RKZ, RKO);
469
470	unsigned TargetMask = LKZ.getZExtValue();
471	unsigned InsertMask = RKZ.getZExtValue();
472
473	if ((TargetMask \| InsertMask) == 0xFFFFFFFF) {
474	unsigned Op0Opc = Op0.getOpcode();
475	unsigned Op1Opc = Op1.getOpcode();
476	unsigned Value, SH = 0;
477	TargetMask = ~TargetMask;
478	InsertMask = ~InsertMask;
479
480	// If the LHS has a foldable shift and the RHS does not, then swap it to the
481	// RHS so that we can fold the shift into the insert.
482	if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
483	if (Op0.getOperand(0).getOpcode() == ISD::SHL \|\|
484	Op0.getOperand(0).getOpcode() == ISD::SRL) {
485	if (Op1.getOperand(0).getOpcode() != ISD::SHL &&
486	Op1.getOperand(0).getOpcode() != ISD::SRL) {
487	std::swap(Op0, Op1);
488	std::swap(Op0Opc, Op1Opc);
489	std::swap(TargetMask, InsertMask);
490	}
491	}
492	} else if (Op0Opc == ISD::SHL \|\| Op0Opc == ISD::SRL) {
493	if (Op1Opc == ISD::AND && Op1.getOperand(0).getOpcode() != ISD::SHL &&
494	Op1.getOperand(0).getOpcode() != ISD::SRL) {
495	std::swap(Op0, Op1);
496	std::swap(Op0Opc, Op1Opc);
497	std::swap(TargetMask, InsertMask);
498	}
499	}
500
501	unsigned MB, ME;
502	if (isRunOfOnes(InsertMask, MB, ME)) {
503	SDValue Tmp1, Tmp2;
504
505	if ((Op1Opc == ISD::SHL \|\| Op1Opc == ISD::SRL) &&
506	isInt32Immediate(Op1.getOperand(1), Value)) {
507	Op1 = Op1.getOperand(0);
508	SH = (Op1Opc == ISD::SHL) ? Value : 32 - Value;
509	}
510	if (Op1Opc == ISD::AND) {
511	// The AND mask might not be a constant, and we need to make sure that
512	// if we're going to fold the masking with the insert, all bits not
513	// know to be zero in the mask are known to be one.
514	APInt MKZ, MKO;
515	CurDAG->computeKnownBits(Op1.getOperand(1), MKZ, MKO);
516	bool CanFoldMask = InsertMask == MKO.getZExtValue();
517
518	unsigned SHOpc = Op1.getOperand(0).getOpcode();
519	if ((SHOpc == ISD::SHL \|\| SHOpc == ISD::SRL) && CanFoldMask &&
520	isInt32Immediate(Op1.getOperand(0).getOperand(1), Value)) {
521	// Note that Value must be in range here (less than 32) because
522	// otherwise there would not be any bits set in InsertMask.
523	Op1 = Op1.getOperand(0).getOperand(0);
524	SH = (SHOpc == ISD::SHL) ? Value : 32 - Value;
525	}
526	}
527
528	SH &= 31;
529	SDValue Ops[] = { Op0, Op1, getI32Imm(SH, dl), getI32Imm(MB, dl),
530	getI32Imm(ME, dl) };
531	return CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops);
532	}
533	}
534	return nullptr;
535	}
536
537	// Predict the number of instructions that would be generated by calling
538	// SelectInt64(N).
539	static unsigned SelectInt64CountDirect(int64_t Imm) {
540	// Assume no remaining bits.
541	unsigned Remainder = 0;
542	// Assume no shift required.
543	unsigned Shift = 0;
544
545	// If it can't be represented as a 32 bit value.
546	if (!isInt<32>(Imm)) {
547	Shift = countTrailingZeros<uint64_t>(Imm);
548	int64_t ImmSh = static_cast<uint64_t>(Imm) >> Shift;
549
550	// If the shifted value fits 32 bits.
551	if (isInt<32>(ImmSh)) {
552	// Go with the shifted value.
553	Imm = ImmSh;
554	} else {
555	// Still stuck with a 64 bit value.
556	Remainder = Imm;
557	Shift = 32;
558	Imm >>= 32;
559	}
560	}
561
562	// Intermediate operand.
563	unsigned Result = 0;
564
565	// Handle first 32 bits.
566	unsigned Lo = Imm & 0xFFFF;
567	unsigned Hi = (Imm >> 16) & 0xFFFF;
	Value stored to 'Hi' during its initialization is never read
568
569	// Simple value.
570	if (isInt<16>(Imm)) {
571	// Just the Lo bits.
572	++Result;
573	} else if (Lo) {
574	// Handle the Hi bits and Lo bits.
575	Result += 2;
576	} else {
577	// Just the Hi bits.
578	++Result;
579	}
580
581	// If no shift, we're done.
582	if (!Shift) return Result;
583
584	// Shift for next step if the upper 32-bits were not zero.
585	if (Imm)
586	++Result;
587
588	// Add in the last bits as required.
589	if ((Hi = (Remainder >> 16) & 0xFFFF))
590	++Result;
591	if ((Lo = Remainder & 0xFFFF))
592	++Result;
593
594	return Result;
595	}
596
597	static uint64_t Rot64(uint64_t Imm, unsigned R) {
598	return (Imm << R) \| (Imm >> (64 - R));
599	}
600
601	static unsigned SelectInt64Count(int64_t Imm) {
602	unsigned Count = SelectInt64CountDirect(Imm);
603	if (Count == 1)
604	return Count;
605
606	for (unsigned r = 1; r < 63; ++r) {
607	uint64_t RImm = Rot64(Imm, r);
608	unsigned RCount = SelectInt64CountDirect(RImm) + 1;
609	Count = std::min(Count, RCount);
610
611	// See comments in SelectInt64 for an explanation of the logic below.
612	unsigned LS = findLastSet(RImm);
613	if (LS != r-1)
614	continue;
615
616	uint64_t OnesMask = -(int64_t) (UINT64_C(1)1UL << (LS+1));
617	uint64_t RImmWithOnes = RImm \| OnesMask;
618
619	RCount = SelectInt64CountDirect(RImmWithOnes) + 1;
620	Count = std::min(Count, RCount);
621	}
622
623	return Count;
624	}
625
626	// Select a 64-bit constant. For cost-modeling purposes, SelectInt64Count
627	// (above) needs to be kept in sync with this function.
628	static SDNode SelectInt64Direct(SelectionDAG CurDAG, SDLoc dl, int64_t Imm) {
629	// Assume no remaining bits.
630	unsigned Remainder = 0;
631	// Assume no shift required.
632	unsigned Shift = 0;
633
634	// If it can't be represented as a 32 bit value.
635	if (!isInt<32>(Imm)) {
636	Shift = countTrailingZeros<uint64_t>(Imm);
637	int64_t ImmSh = static_cast<uint64_t>(Imm) >> Shift;
638
639	// If the shifted value fits 32 bits.
640	if (isInt<32>(ImmSh)) {
641	// Go with the shifted value.
642	Imm = ImmSh;
643	} else {
644	// Still stuck with a 64 bit value.
645	Remainder = Imm;
646	Shift = 32;
647	Imm >>= 32;
648	}
649	}
650
651	// Intermediate operand.
652	SDNode *Result;
653
654	// Handle first 32 bits.
655	unsigned Lo = Imm & 0xFFFF;
656	unsigned Hi = (Imm >> 16) & 0xFFFF;
657
658	auto getI32Imm = [CurDAG, dl](unsigned Imm) {
659	return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
660	};
661
662	// Simple value.
663	if (isInt<16>(Imm)) {
664	// Just the Lo bits.
665	Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, getI32Imm(Lo));
666	} else if (Lo) {
667	// Handle the Hi bits.
668	unsigned OpC = Hi ? PPC::LIS8 : PPC::LI8;
669	Result = CurDAG->getMachineNode(OpC, dl, MVT::i64, getI32Imm(Hi));
670	// And Lo bits.
671	Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64,
672	SDValue(Result, 0), getI32Imm(Lo));
673	} else {
674	// Just the Hi bits.
675	Result = CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64, getI32Imm(Hi));
676	}
677
678	// If no shift, we're done.
679	if (!Shift) return Result;
680
681	// Shift for next step if the upper 32-bits were not zero.
682	if (Imm) {
683	Result = CurDAG->getMachineNode(PPC::RLDICR, dl, MVT::i64,
684	SDValue(Result, 0),
685	getI32Imm(Shift),
686	getI32Imm(63 - Shift));
687	}
688
689	// Add in the last bits as required.
690	if ((Hi = (Remainder >> 16) & 0xFFFF)) {
691	Result = CurDAG->getMachineNode(PPC::ORIS8, dl, MVT::i64,
692	SDValue(Result, 0), getI32Imm(Hi));
693	}
694	if ((Lo = Remainder & 0xFFFF)) {
695	Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64,
696	SDValue(Result, 0), getI32Imm(Lo));
697	}
698
699	return Result;
700	}
701
702	static SDNode SelectInt64(SelectionDAG CurDAG, SDLoc dl, int64_t Imm) {
703	unsigned Count = SelectInt64CountDirect(Imm);
704	if (Count == 1)
705	return SelectInt64Direct(CurDAG, dl, Imm);
706
707	unsigned RMin = 0;
708
709	int64_t MatImm;
710	unsigned MaskEnd;
711
712	for (unsigned r = 1; r < 63; ++r) {
713	uint64_t RImm = Rot64(Imm, r);
714	unsigned RCount = SelectInt64CountDirect(RImm) + 1;
715	if (RCount < Count) {
716	Count = RCount;
717	RMin = r;
718	MatImm = RImm;
719	MaskEnd = 63;
720	}
721
722	// If the immediate to generate has many trailing zeros, it might be
723	// worthwhile to generate a rotated value with too many leading ones
724	// (because that's free with li/lis's sign-extension semantics), and then
725	// mask them off after rotation.
726
727	unsigned LS = findLastSet(RImm);
728	// We're adding (63-LS) higher-order ones, and we expect to mask them off
729	// after performing the inverse rotation by (64-r). So we need that:
730	// 63-LS == 64-r => LS == r-1
731	if (LS != r-1)
732	continue;
733
734	uint64_t OnesMask = -(int64_t) (UINT64_C(1)1UL << (LS+1));
735	uint64_t RImmWithOnes = RImm \| OnesMask;
736
737	RCount = SelectInt64CountDirect(RImmWithOnes) + 1;
738	if (RCount < Count) {
739	Count = RCount;
740	RMin = r;
741	MatImm = RImmWithOnes;
742	MaskEnd = LS;
743	}
744	}
745
746	if (!RMin)
747	return SelectInt64Direct(CurDAG, dl, Imm);
748
749	auto getI32Imm = [CurDAG, dl](unsigned Imm) {
750	return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
751	};
752
753	SDValue Val = SDValue(SelectInt64Direct(CurDAG, dl, MatImm), 0);
754	return CurDAG->getMachineNode(PPC::RLDICR, dl, MVT::i64, Val,
755	getI32Imm(64 - RMin), getI32Imm(MaskEnd));
756	}
757
758	// Select a 64-bit constant.
759	static SDNode SelectInt64(SelectionDAG CurDAG, SDNode *N) {
760	SDLoc dl(N);
761
762	// Get 64 bit value.
763	int64_t Imm = cast<ConstantSDNode>(N)->getZExtValue();
764	return SelectInt64(CurDAG, dl, Imm);
765	}
766
767	namespace {
768	class BitPermutationSelector {
769	struct ValueBit {
770	SDValue V;
771
772	// The bit number in the value, using a convention where bit 0 is the
773	// lowest-order bit.
774	unsigned Idx;
775
776	enum Kind {
777	ConstZero,
778	Variable
779	} K;
780
781	ValueBit(SDValue V, unsigned I, Kind K = Variable)
782	: V(V), Idx(I), K(K) {}
783	ValueBit(Kind K = Variable)
784	: V(SDValue(nullptr, 0)), Idx(UINT32_MAX(4294967295U)), K(K) {}
785
786	bool isZero() const {
787	return K == ConstZero;
788	}
789
790	bool hasValue() const {
791	return K == Variable;
792	}
793
794	SDValue getValue() const {
795	assert(hasValue() && "Cannot get the value of a constant bit")((hasValue() && "Cannot get the value of a constant bit" ) ? static_cast<void> (0) : __assert_fail ("hasValue() && \"Cannot get the value of a constant bit\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 795, __PRETTY_FUNCTION__));
796	return V;
797	}
798
799	unsigned getValueBitIndex() const {
800	assert(hasValue() && "Cannot get the value bit index of a constant bit")((hasValue() && "Cannot get the value bit index of a constant bit" ) ? static_cast<void> (0) : __assert_fail ("hasValue() && \"Cannot get the value bit index of a constant bit\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 800, __PRETTY_FUNCTION__));
801	return Idx;
802	}
803	};
804
805	// A bit group has the same underlying value and the same rotate factor.
806	struct BitGroup {
807	SDValue V;
808	unsigned RLAmt;
809	unsigned StartIdx, EndIdx;
810
811	// This rotation amount assumes that the lower 32 bits of the quantity are
812	// replicated in the high 32 bits by the rotation operator (which is done
813	// by rlwinm and friends in 64-bit mode).
814	bool Repl32;
815	// Did converting to Repl32 == true change the rotation factor? If it did,
816	// it decreased it by 32.
817	bool Repl32CR;
818	// Was this group coalesced after setting Repl32 to true?
819	bool Repl32Coalesced;
820
821	BitGroup(SDValue V, unsigned R, unsigned S, unsigned E)
822	: V(V), RLAmt(R), StartIdx(S), EndIdx(E), Repl32(false), Repl32CR(false),
823	Repl32Coalesced(false) {
824	DEBUG(dbgs() << "\tbit group for " << V.getNode() << " RLAmt = " << R <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tbit group for " << V.getNode() << " RLAmt = " << R << " [" << S << ", " << E << "]\n"; } } while (0)
825	" [" << S << ", " << E << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tbit group for " << V.getNode() << " RLAmt = " << R << " [" << S << ", " << E << "]\n"; } } while (0);
826	}
827	};
828
829	// Information on each (Value, RLAmt) pair (like the number of groups
830	// associated with each) used to choose the lowering method.
831	struct ValueRotInfo {
832	SDValue V;
833	unsigned RLAmt;
834	unsigned NumGroups;
835	unsigned FirstGroupStartIdx;
836	bool Repl32;
837
838	ValueRotInfo()
839	: RLAmt(UINT32_MAX(4294967295U)), NumGroups(0), FirstGroupStartIdx(UINT32_MAX(4294967295U)),
840	Repl32(false) {}
841
842	// For sorting (in reverse order) by NumGroups, and then by
843	// FirstGroupStartIdx.
844	bool operator < (const ValueRotInfo &Other) const {
845	// We need to sort so that the non-Repl32 come first because, when we're
846	// doing masking, the Repl32 bit groups might be subsumed into the 64-bit
847	// masking operation.
848	if (Repl32 < Other.Repl32)
849	return true;
850	else if (Repl32 > Other.Repl32)
851	return false;
852	else if (NumGroups > Other.NumGroups)
853	return true;
854	else if (NumGroups < Other.NumGroups)
855	return false;
856	else if (FirstGroupStartIdx < Other.FirstGroupStartIdx)
857	return true;
858	return false;
859	}
860	};
861
862	// Return true if something interesting was deduced, return false if we're
863	// providing only a generic representation of V (or something else likewise
864	// uninteresting for instruction selection).
865	bool getValueBits(SDValue V, SmallVector<ValueBit, 64> &Bits) {
866	switch (V.getOpcode()) {
867	default: break;
868	case ISD::ROTL:
869	if (isa<ConstantSDNode>(V.getOperand(1))) {
870	unsigned RotAmt = V.getConstantOperandVal(1);
871
872	SmallVector<ValueBit, 64> LHSBits(Bits.size());
873	getValueBits(V.getOperand(0), LHSBits);
874
875	for (unsigned i = 0; i < Bits.size(); ++i)
876	Bits[i] = LHSBits[i < RotAmt ? i + (Bits.size() - RotAmt) : i - RotAmt];
877
878	return true;
879	}
880	break;
881	case ISD::SHL:
882	if (isa<ConstantSDNode>(V.getOperand(1))) {
883	unsigned ShiftAmt = V.getConstantOperandVal(1);
884
885	SmallVector<ValueBit, 64> LHSBits(Bits.size());
886	getValueBits(V.getOperand(0), LHSBits);
887
888	for (unsigned i = ShiftAmt; i < Bits.size(); ++i)
889	Bits[i] = LHSBits[i - ShiftAmt];
890
891	for (unsigned i = 0; i < ShiftAmt; ++i)
892	Bits[i] = ValueBit(ValueBit::ConstZero);
893
894	return true;
895	}
896	break;
897	case ISD::SRL:
898	if (isa<ConstantSDNode>(V.getOperand(1))) {
899	unsigned ShiftAmt = V.getConstantOperandVal(1);
900
901	SmallVector<ValueBit, 64> LHSBits(Bits.size());
902	getValueBits(V.getOperand(0), LHSBits);
903
904	for (unsigned i = 0; i < Bits.size() - ShiftAmt; ++i)
905	Bits[i] = LHSBits[i + ShiftAmt];
906
907	for (unsigned i = Bits.size() - ShiftAmt; i < Bits.size(); ++i)
908	Bits[i] = ValueBit(ValueBit::ConstZero);
909
910	return true;
911	}
912	break;
913	case ISD::AND:
914	if (isa<ConstantSDNode>(V.getOperand(1))) {
915	uint64_t Mask = V.getConstantOperandVal(1);
916
917	SmallVector<ValueBit, 64> LHSBits(Bits.size());
918	bool LHSTrivial = getValueBits(V.getOperand(0), LHSBits);
919
920	for (unsigned i = 0; i < Bits.size(); ++i)
921	if (((Mask >> i) & 1) == 1)
922	Bits[i] = LHSBits[i];
923	else
924	Bits[i] = ValueBit(ValueBit::ConstZero);
925
926	// Mark this as interesting, only if the LHS was also interesting. This
927	// prevents the overall procedure from matching a single immediate 'and'
928	// (which is non-optimal because such an and might be folded with other
929	// things if we don't select it here).
930	return LHSTrivial;
931	}
932	break;
933	case ISD::OR: {
934	SmallVector<ValueBit, 64> LHSBits(Bits.size()), RHSBits(Bits.size());
935	getValueBits(V.getOperand(0), LHSBits);
936	getValueBits(V.getOperand(1), RHSBits);
937
938	bool AllDisjoint = true;
939	for (unsigned i = 0; i < Bits.size(); ++i)
940	if (LHSBits[i].isZero())
941	Bits[i] = RHSBits[i];
942	else if (RHSBits[i].isZero())
943	Bits[i] = LHSBits[i];
944	else {
945	AllDisjoint = false;
946	break;
947	}
948
949	if (!AllDisjoint)
950	break;
951
952	return true;
953	}
954	}
955
956	for (unsigned i = 0; i < Bits.size(); ++i)
957	Bits[i] = ValueBit(V, i);
958
959	return false;
960	}
961
962	// For each value (except the constant ones), compute the left-rotate amount
963	// to get it from its original to final position.
964	void computeRotationAmounts() {
965	HasZeros = false;
966	RLAmt.resize(Bits.size());
967	for (unsigned i = 0; i < Bits.size(); ++i)
968	if (Bits[i].hasValue()) {
969	unsigned VBI = Bits[i].getValueBitIndex();
970	if (i >= VBI)
971	RLAmt[i] = i - VBI;
972	else
973	RLAmt[i] = Bits.size() - (VBI - i);
974	} else if (Bits[i].isZero()) {
975	HasZeros = true;
976	RLAmt[i] = UINT32_MAX(4294967295U);
977	} else {
978	llvm_unreachable("Unknown value bit type")::llvm::llvm_unreachable_internal("Unknown value bit type", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 978);
979	}
980	}
981
982	// Collect groups of consecutive bits with the same underlying value and
983	// rotation factor. If we're doing late masking, we ignore zeros, otherwise
984	// they break up groups.
985	void collectBitGroups(bool LateMask) {
986	BitGroups.clear();
987
988	unsigned LastRLAmt = RLAmt[0];
989	SDValue LastValue = Bits[0].hasValue() ? Bits[0].getValue() : SDValue();
990	unsigned LastGroupStartIdx = 0;
991	for (unsigned i = 1; i < Bits.size(); ++i) {
992	unsigned ThisRLAmt = RLAmt[i];
993	SDValue ThisValue = Bits[i].hasValue() ? Bits[i].getValue() : SDValue();
994	if (LateMask && !ThisValue) {
995	ThisValue = LastValue;
996	ThisRLAmt = LastRLAmt;
997	// If we're doing late masking, then the first bit group always starts
998	// at zero (even if the first bits were zero).
999	if (BitGroups.empty())
1000	LastGroupStartIdx = 0;
1001	}
1002
1003	// If this bit has the same underlying value and the same rotate factor as
1004	// the last one, then they're part of the same group.
1005	if (ThisRLAmt == LastRLAmt && ThisValue == LastValue)
1006	continue;
1007
1008	if (LastValue.getNode())
1009	BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
1010	i-1));
1011	LastRLAmt = ThisRLAmt;
1012	LastValue = ThisValue;
1013	LastGroupStartIdx = i;
1014	}
1015	if (LastValue.getNode())
1016	BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
1017	Bits.size()-1));
1018
1019	if (BitGroups.empty())
1020	return;
1021
1022	// We might be able to combine the first and last groups.
1023	if (BitGroups.size() > 1) {
1024	// If the first and last groups are the same, then remove the first group
1025	// in favor of the last group, making the ending index of the last group
1026	// equal to the ending index of the to-be-removed first group.
1027	if (BitGroups[0].StartIdx == 0 &&
1028	BitGroups[BitGroups.size()-1].EndIdx == Bits.size()-1 &&
1029	BitGroups[0].V == BitGroups[BitGroups.size()-1].V &&
1030	BitGroups[0].RLAmt == BitGroups[BitGroups.size()-1].RLAmt) {
1031	DEBUG(dbgs() << "\tcombining final bit group with initial one\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining final bit group with initial one\n" ; } } while (0);
1032	BitGroups[BitGroups.size()-1].EndIdx = BitGroups[0].EndIdx;
1033	BitGroups.erase(BitGroups.begin());
1034	}
1035	}
1036	}
1037
1038	// Take all (SDValue, RLAmt) pairs and sort them by the number of groups
1039	// associated with each. If there is a degeneracy, pick the one that occurs
1040	// first (in the final value).
1041	void collectValueRotInfo() {
1042	ValueRots.clear();
1043
1044	for (auto &BG : BitGroups) {
1045	unsigned RLAmtKey = BG.RLAmt + (BG.Repl32 ? 64 : 0);
1046	ValueRotInfo &VRI = ValueRots[std::make_pair(BG.V, RLAmtKey)];
1047	VRI.V = BG.V;
1048	VRI.RLAmt = BG.RLAmt;
1049	VRI.Repl32 = BG.Repl32;
1050	VRI.NumGroups += 1;
1051	VRI.FirstGroupStartIdx = std::min(VRI.FirstGroupStartIdx, BG.StartIdx);
1052	}
1053
1054	// Now that we've collected the various ValueRotInfo instances, we need to
1055	// sort them.
1056	ValueRotsVec.clear();
1057	for (auto &I : ValueRots) {
1058	ValueRotsVec.push_back(I.second);
1059	}
1060	std::sort(ValueRotsVec.begin(), ValueRotsVec.end());
1061	}
1062
1063	// In 64-bit mode, rlwinm and friends have a rotation operator that
1064	// replicates the low-order 32 bits into the high-order 32-bits. The mask
1065	// indices of these instructions can only be in the lower 32 bits, so they
1066	// can only represent some 64-bit bit groups. However, when they can be used,
1067	// the 32-bit replication can be used to represent, as a single bit group,
1068	// otherwise separate bit groups. We'll convert to replicated-32-bit bit
1069	// groups when possible. Returns true if any of the bit groups were
1070	// converted.
1071	void assignRepl32BitGroups() {
1072	// If we have bits like this:
1073	//
1074	// Indices: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
1075	// V bits: ... 7 6 5 4 3 2 1 0 31 30 29 28 27 26 25 24
1076	// Groups: \| RLAmt = 8 \| RLAmt = 40 \|
1077	//
1078	// But, making use of a 32-bit operation that replicates the low-order 32
1079	// bits into the high-order 32 bits, this can be one bit group with a RLAmt
1080	// of 8.
1081
1082	auto IsAllLow32 = [this](BitGroup & BG) {
1083	if (BG.StartIdx <= BG.EndIdx) {
1084	for (unsigned i = BG.StartIdx; i <= BG.EndIdx; ++i) {
1085	if (!Bits[i].hasValue())
1086	continue;
1087	if (Bits[i].getValueBitIndex() >= 32)
1088	return false;
1089	}
1090	} else {
1091	for (unsigned i = BG.StartIdx; i < Bits.size(); ++i) {
1092	if (!Bits[i].hasValue())
1093	continue;
1094	if (Bits[i].getValueBitIndex() >= 32)
1095	return false;
1096	}
1097	for (unsigned i = 0; i <= BG.EndIdx; ++i) {
1098	if (!Bits[i].hasValue())
1099	continue;
1100	if (Bits[i].getValueBitIndex() >= 32)
1101	return false;
1102	}
1103	}
1104
1105	return true;
1106	};
1107
1108	for (auto &BG : BitGroups) {
1109	if (BG.StartIdx < 32 && BG.EndIdx < 32) {
1110	if (IsAllLow32(BG)) {
1111	if (BG.RLAmt >= 32) {
1112	BG.RLAmt -= 32;
1113	BG.Repl32CR = true;
1114	}
1115
1116	BG.Repl32 = true;
1117
1118	DEBUG(dbgs() << "\t32-bit replicated bit group for " <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t32-bit replicated bit group for " << BG.V.getNode() << " RLAmt = " << BG.RLAmt << " [" << BG.StartIdx << ", " << BG .EndIdx << "]\n"; } } while (0)
1119	BG.V.getNode() << " RLAmt = " << BG.RLAmt <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t32-bit replicated bit group for " << BG.V.getNode() << " RLAmt = " << BG.RLAmt << " [" << BG.StartIdx << ", " << BG .EndIdx << "]\n"; } } while (0)
1120	" [" << BG.StartIdx << ", " << BG.EndIdx << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t32-bit replicated bit group for " << BG.V.getNode() << " RLAmt = " << BG.RLAmt << " [" << BG.StartIdx << ", " << BG .EndIdx << "]\n"; } } while (0);
1121	}
1122	}
1123	}
1124
1125	// Now walk through the bit groups, consolidating where possible.
1126	for (auto I = BitGroups.begin(); I != BitGroups.end();) {
1127	// We might want to remove this bit group by merging it with the previous
1128	// group (which might be the ending group).
1129	auto IP = (I == BitGroups.begin()) ?
1130	std::prev(BitGroups.end()) : std::prev(I);
1131	if (I->Repl32 && IP->Repl32 && I->V == IP->V && I->RLAmt == IP->RLAmt &&
1132	I->StartIdx == (IP->EndIdx + 1) % 64 && I != IP) {
1133
1134	DEBUG(dbgs() << "\tcombining 32-bit replicated bit group for " <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining 32-bit replicated bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with group with range [" << IP ->StartIdx << ", " << IP->EndIdx << "]\n" ; } } while (0)
1135	I->V.getNode() << " RLAmt = " << I->RLAmt <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining 32-bit replicated bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with group with range [" << IP ->StartIdx << ", " << IP->EndIdx << "]\n" ; } } while (0)
1136	" [" << I->StartIdx << ", " << I->EndIdx <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining 32-bit replicated bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with group with range [" << IP ->StartIdx << ", " << IP->EndIdx << "]\n" ; } } while (0)
1137	"] with group with range [" <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining 32-bit replicated bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with group with range [" << IP ->StartIdx << ", " << IP->EndIdx << "]\n" ; } } while (0)
1138	IP->StartIdx << ", " << IP->EndIdx << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining 32-bit replicated bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with group with range [" << IP ->StartIdx << ", " << IP->EndIdx << "]\n" ; } } while (0);
1139
1140	IP->EndIdx = I->EndIdx;
1141	IP->Repl32CR = IP->Repl32CR \|\| I->Repl32CR;
1142	IP->Repl32Coalesced = true;
1143	I = BitGroups.erase(I);
1144	continue;
1145	} else {
1146	// There is a special case worth handling: If there is a single group
1147	// covering the entire upper 32 bits, and it can be merged with both
1148	// the next and previous groups (which might be the same group), then
1149	// do so. If it is the same group (so there will be only one group in
1150	// total), then we need to reverse the order of the range so that it
1151	// covers the entire 64 bits.
1152	if (I->StartIdx == 32 && I->EndIdx == 63) {
1153	assert(std::next(I) == BitGroups.end() &&((std::next(I) == BitGroups.end() && "bit group ends at index 63 but there is another?" ) ? static_cast<void> (0) : __assert_fail ("std::next(I) == BitGroups.end() && \"bit group ends at index 63 but there is another?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1154, __PRETTY_FUNCTION__))
1154	"bit group ends at index 63 but there is another?")((std::next(I) == BitGroups.end() && "bit group ends at index 63 but there is another?" ) ? static_cast<void> (0) : __assert_fail ("std::next(I) == BitGroups.end() && \"bit group ends at index 63 but there is another?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1154, __PRETTY_FUNCTION__));
1155	auto IN = BitGroups.begin();
1156
1157	if (IP->Repl32 && IN->Repl32 && I->V == IP->V && I->V == IN->V &&
1158	(I->RLAmt % 32) == IP->RLAmt && (I->RLAmt % 32) == IN->RLAmt &&
1159	IP->EndIdx == 31 && IN->StartIdx == 0 && I != IP &&
1160	IsAllLow32(*I)) {
1161
1162	DEBUG(dbgs() << "\tcombining bit group for " <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with 32-bit replicated groups with ranges [" << IP->StartIdx << ", " << IP->EndIdx << "] and [" << IN->StartIdx << ", " << IN->EndIdx << "]\n"; } } while (0)
1163	I->V.getNode() << " RLAmt = " << I->RLAmt <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with 32-bit replicated groups with ranges [" << IP->StartIdx << ", " << IP->EndIdx << "] and [" << IN->StartIdx << ", " << IN->EndIdx << "]\n"; } } while (0)
1164	" [" << I->StartIdx << ", " << I->EndIdx <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with 32-bit replicated groups with ranges [" << IP->StartIdx << ", " << IP->EndIdx << "] and [" << IN->StartIdx << ", " << IN->EndIdx << "]\n"; } } while (0)
1165	"] with 32-bit replicated groups with ranges [" <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with 32-bit replicated groups with ranges [" << IP->StartIdx << ", " << IP->EndIdx << "] and [" << IN->StartIdx << ", " << IN->EndIdx << "]\n"; } } while (0)
1166	IP->StartIdx << ", " << IP->EndIdx << "] and [" <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with 32-bit replicated groups with ranges [" << IP->StartIdx << ", " << IP->EndIdx << "] and [" << IN->StartIdx << ", " << IN->EndIdx << "]\n"; } } while (0)
1167	IN->StartIdx << ", " << IN->EndIdx << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tcombining bit group for " << I->V.getNode() << " RLAmt = " << I-> RLAmt << " [" << I->StartIdx << ", " << I->EndIdx << "] with 32-bit replicated groups with ranges [" << IP->StartIdx << ", " << IP->EndIdx << "] and [" << IN->StartIdx << ", " << IN->EndIdx << "]\n"; } } while (0);
1168
1169	if (IP == IN) {
1170	// There is only one other group; change it to cover the whole
1171	// range (backward, so that it can still be Repl32 but cover the
1172	// whole 64-bit range).
1173	IP->StartIdx = 31;
1174	IP->EndIdx = 30;
1175	IP->Repl32CR = IP->Repl32CR \|\| I->RLAmt >= 32;
1176	IP->Repl32Coalesced = true;
1177	I = BitGroups.erase(I);
1178	} else {
1179	// There are two separate groups, one before this group and one
1180	// after us (at the beginning). We're going to remove this group,
1181	// but also the group at the very beginning.
1182	IP->EndIdx = IN->EndIdx;
1183	IP->Repl32CR = IP->Repl32CR \|\| IN->Repl32CR \|\| I->RLAmt >= 32;
1184	IP->Repl32Coalesced = true;
1185	I = BitGroups.erase(I);
1186	BitGroups.erase(BitGroups.begin());
1187	}
1188
1189	// This must be the last group in the vector (and we might have
1190	// just invalidated the iterator above), so break here.
1191	break;
1192	}
1193	}
1194	}
1195
1196	++I;
1197	}
1198	}
1199
1200	SDValue getI32Imm(unsigned Imm, SDLoc dl) {
1201	return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
1202	}
1203
1204	uint64_t getZerosMask() {
1205	uint64_t Mask = 0;
1206	for (unsigned i = 0; i < Bits.size(); ++i) {
1207	if (Bits[i].hasValue())
1208	continue;
1209	Mask \|= (UINT64_C(1)1UL << i);
1210	}
1211
1212	return ~Mask;
1213	}
1214
1215	// Depending on the number of groups for a particular value, it might be
1216	// better to rotate, mask explicitly (using andi/andis), and then or the
1217	// result. Select this part of the result first.
1218	void SelectAndParts32(SDLoc dl, SDValue &Res, unsigned *InstCnt) {
1219	if (BPermRewriterNoMasking)
1220	return;
1221
1222	for (ValueRotInfo &VRI : ValueRotsVec) {
1223	unsigned Mask = 0;
1224	for (unsigned i = 0; i < Bits.size(); ++i) {
1225	if (!Bits[i].hasValue() \|\| Bits[i].getValue() != VRI.V)
1226	continue;
1227	if (RLAmt[i] != VRI.RLAmt)
1228	continue;
1229	Mask \|= (1u << i);
1230	}
1231
1232	// Compute the masks for andi/andis that would be necessary.
1233	unsigned ANDIMask = (Mask & UINT16_MAX(65535)), ANDISMask = Mask >> 16;
1234	assert((ANDIMask != 0 \|\| ANDISMask != 0) &&(((ANDIMask != 0 \|\| ANDISMask != 0) && "No set bits in mask for value bit groups" ) ? static_cast<void> (0) : __assert_fail ("(ANDIMask != 0 \|\| ANDISMask != 0) && \"No set bits in mask for value bit groups\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1235, __PRETTY_FUNCTION__))
1235	"No set bits in mask for value bit groups")(((ANDIMask != 0 \|\| ANDISMask != 0) && "No set bits in mask for value bit groups" ) ? static_cast<void> (0) : __assert_fail ("(ANDIMask != 0 \|\| ANDISMask != 0) && \"No set bits in mask for value bit groups\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1235, __PRETTY_FUNCTION__));
1236	bool NeedsRotate = VRI.RLAmt != 0;
1237
1238	// We're trying to minimize the number of instructions. If we have one
1239	// group, using one of andi/andis can break even. If we have three
1240	// groups, we can use both andi and andis and break even (to use both
1241	// andi and andis we also need to or the results together). We need four
1242	// groups if we also need to rotate. To use andi/andis we need to do more
1243	// than break even because rotate-and-mask instructions tend to be easier
1244	// to schedule.
1245
1246	// FIXME: We've biased here against using andi/andis, which is right for
1247	// POWER cores, but not optimal everywhere. For example, on the A2,
1248	// andi/andis have single-cycle latency whereas the rotate-and-mask
1249	// instructions take two cycles, and it would be better to bias toward
1250	// andi/andis in break-even cases.
1251
1252	unsigned NumAndInsts = (unsigned) NeedsRotate +
1253	(unsigned) (ANDIMask != 0) +
1254	(unsigned) (ANDISMask != 0) +
1255	(unsigned) (ANDIMask != 0 && ANDISMask != 0) +
1256	(unsigned) (bool) Res;
1257
1258	DEBUG(dbgs() << "\t\trotation groups for " << VRI.V.getNode() <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\trotation groups for " << VRI.V.getNode() << " RL: " << VRI.RLAmt << ":" << "\n\t\t\tisel using masking: " << NumAndInsts << " using rotates: " << VRI.NumGroups << "\n"; } } while (0)
1259	" RL: " << VRI.RLAmt << ":" <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\trotation groups for " << VRI.V.getNode() << " RL: " << VRI.RLAmt << ":" << "\n\t\t\tisel using masking: " << NumAndInsts << " using rotates: " << VRI.NumGroups << "\n"; } } while (0)
1260	"\n\t\t\tisel using masking: " << NumAndInsts <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\trotation groups for " << VRI.V.getNode() << " RL: " << VRI.RLAmt << ":" << "\n\t\t\tisel using masking: " << NumAndInsts << " using rotates: " << VRI.NumGroups << "\n"; } } while (0)
1261	" using rotates: " << VRI.NumGroups << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\trotation groups for " << VRI.V.getNode() << " RL: " << VRI.RLAmt << ":" << "\n\t\t\tisel using masking: " << NumAndInsts << " using rotates: " << VRI.NumGroups << "\n"; } } while (0);
1262
1263	if (NumAndInsts >= VRI.NumGroups)
1264	continue;
1265
1266	DEBUG(dbgs() << "\t\t\t\tusing masking\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\t\t\tusing masking\n"; } } while (0);
1267
1268	if (InstCnt) *InstCnt += NumAndInsts;
1269
1270	SDValue VRot;
1271	if (VRI.RLAmt) {
1272	SDValue Ops[] =
1273	{ VRI.V, getI32Imm(VRI.RLAmt, dl), getI32Imm(0, dl),
1274	getI32Imm(31, dl) };
1275	VRot = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32,
1276	Ops), 0);
1277	} else {
1278	VRot = VRI.V;
1279	}
1280
1281	SDValue ANDIVal, ANDISVal;
1282	if (ANDIMask != 0)
1283	ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDIo, dl, MVT::i32,
1284	VRot, getI32Imm(ANDIMask, dl)), 0);
1285	if (ANDISMask != 0)
1286	ANDISVal = SDValue(CurDAG->getMachineNode(PPC::ANDISo, dl, MVT::i32,
1287	VRot, getI32Imm(ANDISMask, dl)), 0);
1288
1289	SDValue TotalVal;
1290	if (!ANDIVal)
1291	TotalVal = ANDISVal;
1292	else if (!ANDISVal)
1293	TotalVal = ANDIVal;
1294	else
1295	TotalVal = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
1296	ANDIVal, ANDISVal), 0);
1297
1298	if (!Res)
1299	Res = TotalVal;
1300	else
1301	Res = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
1302	Res, TotalVal), 0);
1303
1304	// Now, remove all groups with this underlying value and rotation
1305	// factor.
1306	eraseMatchingBitGroups([VRI](const BitGroup &BG) {
1307	return BG.V == VRI.V && BG.RLAmt == VRI.RLAmt;
1308	});
1309	}
1310	}
1311
1312	// Instruction selection for the 32-bit case.
1313	SDNode Select32(SDNode N, bool LateMask, unsigned *InstCnt) {
1314	SDLoc dl(N);
1315	SDValue Res;
1316
1317	if (InstCnt) *InstCnt = 0;
1318
1319	// Take care of cases that should use andi/andis first.
1320	SelectAndParts32(dl, Res, InstCnt);
1321
1322	// If we've not yet selected a 'starting' instruction, and we have no zeros
1323	// to fill in, select the (Value, RLAmt) with the highest priority (largest
1324	// number of groups), and start with this rotated value.
1325	if ((!HasZeros \|\| LateMask) && !Res) {
1326	ValueRotInfo &VRI = ValueRotsVec[0];
1327	if (VRI.RLAmt) {
1328	if (InstCnt) *InstCnt += 1;
1329	SDValue Ops[] =
1330	{ VRI.V, getI32Imm(VRI.RLAmt, dl), getI32Imm(0, dl),
1331	getI32Imm(31, dl) };
1332	Res = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops),
1333	0);
1334	} else {
1335	Res = VRI.V;
1336	}
1337
1338	// Now, remove all groups with this underlying value and rotation factor.
1339	eraseMatchingBitGroups([VRI](const BitGroup &BG) {
1340	return BG.V == VRI.V && BG.RLAmt == VRI.RLAmt;
1341	});
1342	}
1343
1344	if (InstCnt) *InstCnt += BitGroups.size();
1345
1346	// Insert the other groups (one at a time).
1347	for (auto &BG : BitGroups) {
1348	if (!Res) {
1349	SDValue Ops[] =
1350	{ BG.V, getI32Imm(BG.RLAmt, dl),
1351	getI32Imm(Bits.size() - BG.EndIdx - 1, dl),
1352	getI32Imm(Bits.size() - BG.StartIdx - 1, dl) };
1353	Res = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
1354	} else {
1355	SDValue Ops[] =
1356	{ Res, BG.V, getI32Imm(BG.RLAmt, dl),
1357	getI32Imm(Bits.size() - BG.EndIdx - 1, dl),
1358	getI32Imm(Bits.size() - BG.StartIdx - 1, dl) };
1359	Res = SDValue(CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops), 0);
1360	}
1361	}
1362
1363	if (LateMask) {
1364	unsigned Mask = (unsigned) getZerosMask();
1365
1366	unsigned ANDIMask = (Mask & UINT16_MAX(65535)), ANDISMask = Mask >> 16;
1367	assert((ANDIMask != 0 \|\| ANDISMask != 0) &&(((ANDIMask != 0 \|\| ANDISMask != 0) && "No set bits in zeros mask?" ) ? static_cast<void> (0) : __assert_fail ("(ANDIMask != 0 \|\| ANDISMask != 0) && \"No set bits in zeros mask?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1368, __PRETTY_FUNCTION__))
1368	"No set bits in zeros mask?")(((ANDIMask != 0 \|\| ANDISMask != 0) && "No set bits in zeros mask?" ) ? static_cast<void> (0) : __assert_fail ("(ANDIMask != 0 \|\| ANDISMask != 0) && \"No set bits in zeros mask?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1368, __PRETTY_FUNCTION__));
1369
1370	if (InstCnt) *InstCnt += (unsigned) (ANDIMask != 0) +
1371	(unsigned) (ANDISMask != 0) +
1372	(unsigned) (ANDIMask != 0 && ANDISMask != 0);
1373
1374	SDValue ANDIVal, ANDISVal;
1375	if (ANDIMask != 0)
1376	ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDIo, dl, MVT::i32,
1377	Res, getI32Imm(ANDIMask, dl)), 0);
1378	if (ANDISMask != 0)
1379	ANDISVal = SDValue(CurDAG->getMachineNode(PPC::ANDISo, dl, MVT::i32,
1380	Res, getI32Imm(ANDISMask, dl)), 0);
1381
1382	if (!ANDIVal)
1383	Res = ANDISVal;
1384	else if (!ANDISVal)
1385	Res = ANDIVal;
1386	else
1387	Res = SDValue(CurDAG->getMachineNode(PPC::OR, dl, MVT::i32,
1388	ANDIVal, ANDISVal), 0);
1389	}
1390
1391	return Res.getNode();
1392	}
1393
1394	unsigned SelectRotMask64Count(unsigned RLAmt, bool Repl32,
1395	unsigned MaskStart, unsigned MaskEnd,
1396	bool IsIns) {
1397	// In the notation used by the instructions, 'start' and 'end' are reversed
1398	// because bits are counted from high to low order.
1399	unsigned InstMaskStart = 64 - MaskEnd - 1,
1400	InstMaskEnd = 64 - MaskStart - 1;
1401
1402	if (Repl32)
1403	return 1;
1404
1405	if ((!IsIns && (InstMaskEnd == 63 \|\| InstMaskStart == 0)) \|\|
1406	InstMaskEnd == 63 - RLAmt)
1407	return 1;
1408
1409	return 2;
1410	}
1411
1412	// For 64-bit values, not all combinations of rotates and masks are
1413	// available. Produce one if it is available.
1414	SDValue SelectRotMask64(SDValue V, SDLoc dl, unsigned RLAmt, bool Repl32,
1415	unsigned MaskStart, unsigned MaskEnd,
1416	unsigned *InstCnt = nullptr) {
1417	// In the notation used by the instructions, 'start' and 'end' are reversed
1418	// because bits are counted from high to low order.
1419	unsigned InstMaskStart = 64 - MaskEnd - 1,
1420	InstMaskEnd = 64 - MaskStart - 1;
1421
1422	if (InstCnt) *InstCnt += 1;
1423
1424	if (Repl32) {
1425	// This rotation amount assumes that the lower 32 bits of the quantity
1426	// are replicated in the high 32 bits by the rotation operator (which is
1427	// done by rlwinm and friends).
1428	assert(InstMaskStart >= 32 && "Mask cannot start out of range")((InstMaskStart >= 32 && "Mask cannot start out of range" ) ? static_cast<void> (0) : __assert_fail ("InstMaskStart >= 32 && \"Mask cannot start out of range\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1428, __PRETTY_FUNCTION__));
1429	assert(InstMaskEnd >= 32 && "Mask cannot end out of range")((InstMaskEnd >= 32 && "Mask cannot end out of range" ) ? static_cast<void> (0) : __assert_fail ("InstMaskEnd >= 32 && \"Mask cannot end out of range\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1429, __PRETTY_FUNCTION__));
1430	SDValue Ops[] =
1431	{ V, getI32Imm(RLAmt, dl), getI32Imm(InstMaskStart - 32, dl),
1432	getI32Imm(InstMaskEnd - 32, dl) };
1433	return SDValue(CurDAG->getMachineNode(PPC::RLWINM8, dl, MVT::i64,
1434	Ops), 0);
1435	}
1436
1437	if (InstMaskEnd == 63) {
1438	SDValue Ops[] =
1439	{ V, getI32Imm(RLAmt, dl), getI32Imm(InstMaskStart, dl) };
1440	return SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, Ops), 0);
1441	}
1442
1443	if (InstMaskStart == 0) {
1444	SDValue Ops[] =
1445	{ V, getI32Imm(RLAmt, dl), getI32Imm(InstMaskEnd, dl) };
1446	return SDValue(CurDAG->getMachineNode(PPC::RLDICR, dl, MVT::i64, Ops), 0);
1447	}
1448
1449	if (InstMaskEnd == 63 - RLAmt) {
1450	SDValue Ops[] =
1451	{ V, getI32Imm(RLAmt, dl), getI32Imm(InstMaskStart, dl) };
1452	return SDValue(CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, Ops), 0);
1453	}
1454
1455	// We cannot do this with a single instruction, so we'll use two. The
1456	// problem is that we're not free to choose both a rotation amount and mask
1457	// start and end independently. We can choose an arbitrary mask start and
1458	// end, but then the rotation amount is fixed. Rotation, however, can be
1459	// inverted, and so by applying an "inverse" rotation first, we can get the
1460	// desired result.
1461	if (InstCnt) *InstCnt += 1;
1462
1463	// The rotation mask for the second instruction must be MaskStart.
1464	unsigned RLAmt2 = MaskStart;
1465	// The first instruction must rotate V so that the overall rotation amount
1466	// is RLAmt.
1467	unsigned RLAmt1 = (64 + RLAmt - RLAmt2) % 64;
1468	if (RLAmt1)
1469	V = SelectRotMask64(V, dl, RLAmt1, false, 0, 63);
1470	return SelectRotMask64(V, dl, RLAmt2, false, MaskStart, MaskEnd);
1471	}
1472
1473	// For 64-bit values, not all combinations of rotates and masks are
1474	// available. Produce a rotate-mask-and-insert if one is available.
1475	SDValue SelectRotMaskIns64(SDValue Base, SDValue V, SDLoc dl, unsigned RLAmt,
1476	bool Repl32, unsigned MaskStart,
1477	unsigned MaskEnd, unsigned *InstCnt = nullptr) {
1478	// In the notation used by the instructions, 'start' and 'end' are reversed
1479	// because bits are counted from high to low order.
1480	unsigned InstMaskStart = 64 - MaskEnd - 1,
1481	InstMaskEnd = 64 - MaskStart - 1;
1482
1483	if (InstCnt) *InstCnt += 1;
1484
1485	if (Repl32) {
1486	// This rotation amount assumes that the lower 32 bits of the quantity
1487	// are replicated in the high 32 bits by the rotation operator (which is
1488	// done by rlwinm and friends).
1489	assert(InstMaskStart >= 32 && "Mask cannot start out of range")((InstMaskStart >= 32 && "Mask cannot start out of range" ) ? static_cast<void> (0) : __assert_fail ("InstMaskStart >= 32 && \"Mask cannot start out of range\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1489, __PRETTY_FUNCTION__));
1490	assert(InstMaskEnd >= 32 && "Mask cannot end out of range")((InstMaskEnd >= 32 && "Mask cannot end out of range" ) ? static_cast<void> (0) : __assert_fail ("InstMaskEnd >= 32 && \"Mask cannot end out of range\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1490, __PRETTY_FUNCTION__));
1491	SDValue Ops[] =
1492	{ Base, V, getI32Imm(RLAmt, dl), getI32Imm(InstMaskStart - 32, dl),
1493	getI32Imm(InstMaskEnd - 32, dl) };
1494	return SDValue(CurDAG->getMachineNode(PPC::RLWIMI8, dl, MVT::i64,
1495	Ops), 0);
1496	}
1497
1498	if (InstMaskEnd == 63 - RLAmt) {
1499	SDValue Ops[] =
1500	{ Base, V, getI32Imm(RLAmt, dl), getI32Imm(InstMaskStart, dl) };
1501	return SDValue(CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops), 0);
1502	}
1503
1504	// We cannot do this with a single instruction, so we'll use two. The
1505	// problem is that we're not free to choose both a rotation amount and mask
1506	// start and end independently. We can choose an arbitrary mask start and
1507	// end, but then the rotation amount is fixed. Rotation, however, can be
1508	// inverted, and so by applying an "inverse" rotation first, we can get the
1509	// desired result.
1510	if (InstCnt) *InstCnt += 1;
1511
1512	// The rotation mask for the second instruction must be MaskStart.
1513	unsigned RLAmt2 = MaskStart;
1514	// The first instruction must rotate V so that the overall rotation amount
1515	// is RLAmt.
1516	unsigned RLAmt1 = (64 + RLAmt - RLAmt2) % 64;
1517	if (RLAmt1)
1518	V = SelectRotMask64(V, dl, RLAmt1, false, 0, 63);
1519	return SelectRotMaskIns64(Base, V, dl, RLAmt2, false, MaskStart, MaskEnd);
1520	}
1521
1522	void SelectAndParts64(SDLoc dl, SDValue &Res, unsigned *InstCnt) {
1523	if (BPermRewriterNoMasking)
1524	return;
1525
1526	// The idea here is the same as in the 32-bit version, but with additional
1527	// complications from the fact that Repl32 might be true. Because we
1528	// aggressively convert bit groups to Repl32 form (which, for small
1529	// rotation factors, involves no other change), and then coalesce, it might
1530	// be the case that a single 64-bit masking operation could handle both
1531	// some Repl32 groups and some non-Repl32 groups. If converting to Repl32
1532	// form allowed coalescing, then we must use a 32-bit rotaton in order to
1533	// completely capture the new combined bit group.
1534
1535	for (ValueRotInfo &VRI : ValueRotsVec) {
1536	uint64_t Mask = 0;
1537
1538	// We need to add to the mask all bits from the associated bit groups.
1539	// If Repl32 is false, we need to add bits from bit groups that have
1540	// Repl32 true, but are trivially convertable to Repl32 false. Such a
1541	// group is trivially convertable if it overlaps only with the lower 32
1542	// bits, and the group has not been coalesced.
1543	auto MatchingBG = [VRI](const BitGroup &BG) {
1544	if (VRI.V != BG.V)
1545	return false;
1546
1547	unsigned EffRLAmt = BG.RLAmt;
1548	if (!VRI.Repl32 && BG.Repl32) {
1549	if (BG.StartIdx < 32 && BG.EndIdx < 32 && BG.StartIdx <= BG.EndIdx &&
1550	!BG.Repl32Coalesced) {
1551	if (BG.Repl32CR)
1552	EffRLAmt += 32;
1553	} else {
1554	return false;
1555	}
1556	} else if (VRI.Repl32 != BG.Repl32) {
1557	return false;
1558	}
1559
1560	if (VRI.RLAmt != EffRLAmt)
1561	return false;
1562
1563	return true;
1564	};
1565
1566	for (auto &BG : BitGroups) {
1567	if (!MatchingBG(BG))
1568	continue;
1569
1570	if (BG.StartIdx <= BG.EndIdx) {
1571	for (unsigned i = BG.StartIdx; i <= BG.EndIdx; ++i)
1572	Mask \|= (UINT64_C(1)1UL << i);
1573	} else {
1574	for (unsigned i = BG.StartIdx; i < Bits.size(); ++i)
1575	Mask \|= (UINT64_C(1)1UL << i);
1576	for (unsigned i = 0; i <= BG.EndIdx; ++i)
1577	Mask \|= (UINT64_C(1)1UL << i);
1578	}
1579	}
1580
1581	// We can use the 32-bit andi/andis technique if the mask does not
1582	// require any higher-order bits. This can save an instruction compared
1583	// to always using the general 64-bit technique.
1584	bool Use32BitInsts = isUInt<32>(Mask);
1585	// Compute the masks for andi/andis that would be necessary.
1586	unsigned ANDIMask = (Mask & UINT16_MAX(65535)),
1587	ANDISMask = (Mask >> 16) & UINT16_MAX(65535);
1588
1589	bool NeedsRotate = VRI.RLAmt \|\| (VRI.Repl32 && !isUInt<32>(Mask));
1590
1591	unsigned NumAndInsts = (unsigned) NeedsRotate +
1592	(unsigned) (bool) Res;
1593	if (Use32BitInsts)
1594	NumAndInsts += (unsigned) (ANDIMask != 0) + (unsigned) (ANDISMask != 0) +
1595	(unsigned) (ANDIMask != 0 && ANDISMask != 0);
1596	else
1597	NumAndInsts += SelectInt64Count(Mask) + /* and */ 1;
1598
1599	unsigned NumRLInsts = 0;
1600	bool FirstBG = true;
1601	for (auto &BG : BitGroups) {
1602	if (!MatchingBG(BG))
1603	continue;
1604	NumRLInsts +=
1605	SelectRotMask64Count(BG.RLAmt, BG.Repl32, BG.StartIdx, BG.EndIdx,
1606	!FirstBG);
1607	FirstBG = false;
1608	}
1609
1610	DEBUG(dbgs() << "\t\trotation groups for " << VRI.V.getNode() <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\trotation groups for " << VRI.V.getNode() << " RL: " << VRI.RLAmt << (VRI.Repl32 ? " (32):" : ":") << "\n\t\t\tisel using masking: " << NumAndInsts << " using rotates: " << NumRLInsts << "\n"; } } while (0)
1611	" RL: " << VRI.RLAmt << (VRI.Repl32 ? " (32):" : ":") <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\trotation groups for " << VRI.V.getNode() << " RL: " << VRI.RLAmt << (VRI.Repl32 ? " (32):" : ":") << "\n\t\t\tisel using masking: " << NumAndInsts << " using rotates: " << NumRLInsts << "\n"; } } while (0)
1612	"\n\t\t\tisel using masking: " << NumAndInsts <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\trotation groups for " << VRI.V.getNode() << " RL: " << VRI.RLAmt << (VRI.Repl32 ? " (32):" : ":") << "\n\t\t\tisel using masking: " << NumAndInsts << " using rotates: " << NumRLInsts << "\n"; } } while (0)
1613	" using rotates: " << NumRLInsts << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\trotation groups for " << VRI.V.getNode() << " RL: " << VRI.RLAmt << (VRI.Repl32 ? " (32):" : ":") << "\n\t\t\tisel using masking: " << NumAndInsts << " using rotates: " << NumRLInsts << "\n"; } } while (0);
1614
1615	// When we'd use andi/andis, we bias toward using the rotates (andi only
1616	// has a record form, and is cracked on POWER cores). However, when using
1617	// general 64-bit constant formation, bias toward the constant form,
1618	// because that exposes more opportunities for CSE.
1619	if (NumAndInsts > NumRLInsts)
1620	continue;
1621	if (Use32BitInsts && NumAndInsts == NumRLInsts)
1622	continue;
1623
1624	DEBUG(dbgs() << "\t\t\t\tusing masking\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\t\t\tusing masking\n"; } } while (0);
1625
1626	if (InstCnt) *InstCnt += NumAndInsts;
1627
1628	SDValue VRot;
1629	// We actually need to generate a rotation if we have a non-zero rotation
1630	// factor or, in the Repl32 case, if we care about any of the
1631	// higher-order replicated bits. In the latter case, we generate a mask
1632	// backward so that it actually includes the entire 64 bits.
1633	if (VRI.RLAmt \|\| (VRI.Repl32 && !isUInt<32>(Mask)))
1634	VRot = SelectRotMask64(VRI.V, dl, VRI.RLAmt, VRI.Repl32,
1635	VRI.Repl32 ? 31 : 0, VRI.Repl32 ? 30 : 63);
1636	else
1637	VRot = VRI.V;
1638
1639	SDValue TotalVal;
1640	if (Use32BitInsts) {
1641	assert((ANDIMask != 0 \|\| ANDISMask != 0) &&(((ANDIMask != 0 \|\| ANDISMask != 0) && "No set bits in mask when using 32-bit ands for 64-bit value" ) ? static_cast<void> (0) : __assert_fail ("(ANDIMask != 0 \|\| ANDISMask != 0) && \"No set bits in mask when using 32-bit ands for 64-bit value\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1642, __PRETTY_FUNCTION__))
1642	"No set bits in mask when using 32-bit ands for 64-bit value")(((ANDIMask != 0 \|\| ANDISMask != 0) && "No set bits in mask when using 32-bit ands for 64-bit value" ) ? static_cast<void> (0) : __assert_fail ("(ANDIMask != 0 \|\| ANDISMask != 0) && \"No set bits in mask when using 32-bit ands for 64-bit value\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1642, __PRETTY_FUNCTION__));
1643
1644	SDValue ANDIVal, ANDISVal;
1645	if (ANDIMask != 0)
1646	ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDIo8, dl, MVT::i64,
1647	VRot, getI32Imm(ANDIMask, dl)), 0);
1648	if (ANDISMask != 0)
1649	ANDISVal = SDValue(CurDAG->getMachineNode(PPC::ANDISo8, dl, MVT::i64,
1650	VRot, getI32Imm(ANDISMask, dl)), 0);
1651
1652	if (!ANDIVal)
1653	TotalVal = ANDISVal;
1654	else if (!ANDISVal)
1655	TotalVal = ANDIVal;
1656	else
1657	TotalVal = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
1658	ANDIVal, ANDISVal), 0);
1659	} else {
1660	TotalVal = SDValue(SelectInt64(CurDAG, dl, Mask), 0);
1661	TotalVal =
1662	SDValue(CurDAG->getMachineNode(PPC::AND8, dl, MVT::i64,
1663	VRot, TotalVal), 0);
1664	}
1665
1666	if (!Res)
1667	Res = TotalVal;
1668	else
1669	Res = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
1670	Res, TotalVal), 0);
1671
1672	// Now, remove all groups with this underlying value and rotation
1673	// factor.
1674	eraseMatchingBitGroups(MatchingBG);
1675	}
1676	}
1677
1678	// Instruction selection for the 64-bit case.
1679	SDNode Select64(SDNode N, bool LateMask, unsigned *InstCnt) {
1680	SDLoc dl(N);
1681	SDValue Res;
1682
1683	if (InstCnt) *InstCnt = 0;
1684
1685	// Take care of cases that should use andi/andis first.
1686	SelectAndParts64(dl, Res, InstCnt);
1687
1688	// If we've not yet selected a 'starting' instruction, and we have no zeros
1689	// to fill in, select the (Value, RLAmt) with the highest priority (largest
1690	// number of groups), and start with this rotated value.
1691	if ((!HasZeros \|\| LateMask) && !Res) {
1692	// If we have both Repl32 groups and non-Repl32 groups, the non-Repl32
1693	// groups will come first, and so the VRI representing the largest number
1694	// of groups might not be first (it might be the first Repl32 groups).
1695	unsigned MaxGroupsIdx = 0;
1696	if (!ValueRotsVec[0].Repl32) {
1697	for (unsigned i = 0, ie = ValueRotsVec.size(); i < ie; ++i)
1698	if (ValueRotsVec[i].Repl32) {
1699	if (ValueRotsVec[i].NumGroups > ValueRotsVec[0].NumGroups)
1700	MaxGroupsIdx = i;
1701	break;
1702	}
1703	}
1704
1705	ValueRotInfo &VRI = ValueRotsVec[MaxGroupsIdx];
1706	bool NeedsRotate = false;
1707	if (VRI.RLAmt) {
1708	NeedsRotate = true;
1709	} else if (VRI.Repl32) {
1710	for (auto &BG : BitGroups) {
1711	if (BG.V != VRI.V \|\| BG.RLAmt != VRI.RLAmt \|\|
1712	BG.Repl32 != VRI.Repl32)
1713	continue;
1714
1715	// We don't need a rotate if the bit group is confined to the lower
1716	// 32 bits.
1717	if (BG.StartIdx < 32 && BG.EndIdx < 32 && BG.StartIdx < BG.EndIdx)
1718	continue;
1719
1720	NeedsRotate = true;
1721	break;
1722	}
1723	}
1724
1725	if (NeedsRotate)
1726	Res = SelectRotMask64(VRI.V, dl, VRI.RLAmt, VRI.Repl32,
1727	VRI.Repl32 ? 31 : 0, VRI.Repl32 ? 30 : 63,
1728	InstCnt);
1729	else
1730	Res = VRI.V;
1731
1732	// Now, remove all groups with this underlying value and rotation factor.
1733	if (Res)
1734	eraseMatchingBitGroups([VRI](const BitGroup &BG) {
1735	return BG.V == VRI.V && BG.RLAmt == VRI.RLAmt &&
1736	BG.Repl32 == VRI.Repl32;
1737	});
1738	}
1739
1740	// Because 64-bit rotates are more flexible than inserts, we might have a
1741	// preference regarding which one we do first (to save one instruction).
1742	if (!Res)
1743	for (auto I = BitGroups.begin(), IE = BitGroups.end(); I != IE; ++I) {
1744	if (SelectRotMask64Count(I->RLAmt, I->Repl32, I->StartIdx, I->EndIdx,
1745	false) <
1746	SelectRotMask64Count(I->RLAmt, I->Repl32, I->StartIdx, I->EndIdx,
1747	true)) {
1748	if (I != BitGroups.begin()) {
1749	BitGroup BG = *I;
1750	BitGroups.erase(I);
1751	BitGroups.insert(BitGroups.begin(), BG);
1752	}
1753
1754	break;
1755	}
1756	}
1757
1758	// Insert the other groups (one at a time).
1759	for (auto &BG : BitGroups) {
1760	if (!Res)
1761	Res = SelectRotMask64(BG.V, dl, BG.RLAmt, BG.Repl32, BG.StartIdx,
1762	BG.EndIdx, InstCnt);
1763	else
1764	Res = SelectRotMaskIns64(Res, BG.V, dl, BG.RLAmt, BG.Repl32,
1765	BG.StartIdx, BG.EndIdx, InstCnt);
1766	}
1767
1768	if (LateMask) {
1769	uint64_t Mask = getZerosMask();
1770
1771	// We can use the 32-bit andi/andis technique if the mask does not
1772	// require any higher-order bits. This can save an instruction compared
1773	// to always using the general 64-bit technique.
1774	bool Use32BitInsts = isUInt<32>(Mask);
1775	// Compute the masks for andi/andis that would be necessary.
1776	unsigned ANDIMask = (Mask & UINT16_MAX(65535)),
1777	ANDISMask = (Mask >> 16) & UINT16_MAX(65535);
1778
1779	if (Use32BitInsts) {
1780	assert((ANDIMask != 0 \|\| ANDISMask != 0) &&(((ANDIMask != 0 \|\| ANDISMask != 0) && "No set bits in mask when using 32-bit ands for 64-bit value" ) ? static_cast<void> (0) : __assert_fail ("(ANDIMask != 0 \|\| ANDISMask != 0) && \"No set bits in mask when using 32-bit ands for 64-bit value\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1781, __PRETTY_FUNCTION__))
1781	"No set bits in mask when using 32-bit ands for 64-bit value")(((ANDIMask != 0 \|\| ANDISMask != 0) && "No set bits in mask when using 32-bit ands for 64-bit value" ) ? static_cast<void> (0) : __assert_fail ("(ANDIMask != 0 \|\| ANDISMask != 0) && \"No set bits in mask when using 32-bit ands for 64-bit value\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1781, __PRETTY_FUNCTION__));
1782
1783	if (InstCnt) *InstCnt += (unsigned) (ANDIMask != 0) +
1784	(unsigned) (ANDISMask != 0) +
1785	(unsigned) (ANDIMask != 0 && ANDISMask != 0);
1786
1787	SDValue ANDIVal, ANDISVal;
1788	if (ANDIMask != 0)
1789	ANDIVal = SDValue(CurDAG->getMachineNode(PPC::ANDIo8, dl, MVT::i64,
1790	Res, getI32Imm(ANDIMask, dl)), 0);
1791	if (ANDISMask != 0)
1792	ANDISVal = SDValue(CurDAG->getMachineNode(PPC::ANDISo8, dl, MVT::i64,
1793	Res, getI32Imm(ANDISMask, dl)), 0);
1794
1795	if (!ANDIVal)
1796	Res = ANDISVal;
1797	else if (!ANDISVal)
1798	Res = ANDIVal;
1799	else
1800	Res = SDValue(CurDAG->getMachineNode(PPC::OR8, dl, MVT::i64,
1801	ANDIVal, ANDISVal), 0);
1802	} else {
1803	if (InstCnt) InstCnt += SelectInt64Count(Mask) + / and */ 1;
1804
1805	SDValue MaskVal = SDValue(SelectInt64(CurDAG, dl, Mask), 0);
1806	Res =
1807	SDValue(CurDAG->getMachineNode(PPC::AND8, dl, MVT::i64,
1808	Res, MaskVal), 0);
1809	}
1810	}
1811
1812	return Res.getNode();
1813	}
1814
1815	SDNode Select(SDNode N, bool LateMask, unsigned *InstCnt = nullptr) {
1816	// Fill in BitGroups.
1817	collectBitGroups(LateMask);
1818	if (BitGroups.empty())
1819	return nullptr;
1820
1821	// For 64-bit values, figure out when we can use 32-bit instructions.
1822	if (Bits.size() == 64)
1823	assignRepl32BitGroups();
1824
1825	// Fill in ValueRotsVec.
1826	collectValueRotInfo();
1827
1828	if (Bits.size() == 32) {
1829	return Select32(N, LateMask, InstCnt);
1830	} else {
1831	assert(Bits.size() == 64 && "Not 64 bits here?")((Bits.size() == 64 && "Not 64 bits here?") ? static_cast <void> (0) : __assert_fail ("Bits.size() == 64 && \"Not 64 bits here?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 1831, __PRETTY_FUNCTION__));
1832	return Select64(N, LateMask, InstCnt);
1833	}
1834
1835	return nullptr;
1836	}
1837
1838	void eraseMatchingBitGroups(function_ref<bool(const BitGroup &)> F) {
1839	BitGroups.erase(std::remove_if(BitGroups.begin(), BitGroups.end(), F),
1840	BitGroups.end());
1841	}
1842
1843	SmallVector<ValueBit, 64> Bits;
1844
1845	bool HasZeros;
1846	SmallVector<unsigned, 64> RLAmt;
1847
1848	SmallVector<BitGroup, 16> BitGroups;
1849
1850	DenseMap<std::pair<SDValue, unsigned>, ValueRotInfo> ValueRots;
1851	SmallVector<ValueRotInfo, 16> ValueRotsVec;
1852
1853	SelectionDAG *CurDAG;
1854
1855	public:
1856	BitPermutationSelector(SelectionDAG *DAG)
1857	: CurDAG(DAG) {}
1858
1859	// Here we try to match complex bit permutations into a set of
1860	// rotate-and-shift/shift/and/or instructions, using a set of heuristics
1861	// known to produce optimial code for common cases (like i32 byte swapping).
1862	SDNode Select(SDNode N) {
1863	Bits.resize(N->getValueType(0).getSizeInBits());
1864	if (!getValueBits(SDValue(N, 0), Bits))
1865	return nullptr;
1866
1867	DEBUG(dbgs() << "Considering bit-permutation-based instruction"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "Considering bit-permutation-based instruction" " selection for: "; } } while (0)
1868	" selection for: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "Considering bit-permutation-based instruction" " selection for: "; } } while (0);
1869	DEBUG(N->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { N->dump(CurDAG); } } while (0);
1870
1871	// Fill it RLAmt and set HasZeros.
1872	computeRotationAmounts();
1873
1874	if (!HasZeros)
1875	return Select(N, false);
1876
1877	// We currently have two techniques for handling results with zeros: early
1878	// masking (the default) and late masking. Late masking is sometimes more
1879	// efficient, but because the structure of the bit groups is different, it
1880	// is hard to tell without generating both and comparing the results. With
1881	// late masking, we ignore zeros in the resulting value when inserting each
1882	// set of bit groups, and then mask in the zeros at the end. With early
1883	// masking, we only insert the non-zero parts of the result at every step.
1884
1885	unsigned InstCnt, InstCntLateMask;
1886	DEBUG(dbgs() << "\tEarly masking:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tEarly masking:\n"; } } while (0);
1887	SDNode *RN = Select(N, false, &InstCnt);
1888	DEBUG(dbgs() << "\t\tisel would use " << InstCnt << " instructions\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\tisel would use " << InstCnt << " instructions\n"; } } while (0);
1889
1890	DEBUG(dbgs() << "\tLate masking:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tLate masking:\n"; } } while (0);
1891	SDNode *RNLM = Select(N, true, &InstCntLateMask);
1892	DEBUG(dbgs() << "\t\tisel would use " << InstCntLateMask <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\tisel would use " << InstCntLateMask << " instructions\n"; } } while (0)
1893	" instructions\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\t\tisel would use " << InstCntLateMask << " instructions\n"; } } while (0);
1894
1895	if (InstCnt <= InstCntLateMask) {
1896	DEBUG(dbgs() << "\tUsing early-masking for isel\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tUsing early-masking for isel\n" ; } } while (0);
1897	return RN;
1898	}
1899
1900	DEBUG(dbgs() << "\tUsing late-masking for isel\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\tUsing late-masking for isel\n" ; } } while (0);
1901	return RNLM;
1902	}
1903	};
1904	} // anonymous namespace
1905
1906	SDNode PPCDAGToDAGISel::SelectBitPermutation(SDNode N) {
1907	if (N->getValueType(0) != MVT::i32 &&
1908	N->getValueType(0) != MVT::i64)
1909	return nullptr;
1910
1911	if (!UseBitPermRewriter)
1912	return nullptr;
1913
1914	switch (N->getOpcode()) {
1915	default: break;
1916	case ISD::ROTL:
1917	case ISD::SHL:
1918	case ISD::SRL:
1919	case ISD::AND:
1920	case ISD::OR: {
1921	BitPermutationSelector BPS(CurDAG);
1922	return BPS.Select(N);
1923	}
1924	}
1925
1926	return nullptr;
1927	}
1928
1929	/// SelectCC - Select a comparison of the specified values with the specified
1930	/// condition code, returning the CR# of the expression.
1931	SDValue PPCDAGToDAGISel::SelectCC(SDValue LHS, SDValue RHS,
1932	ISD::CondCode CC, SDLoc dl) {
1933	// Always select the LHS.
1934	unsigned Opc;
1935
1936	if (LHS.getValueType() == MVT::i32) {
1937	unsigned Imm;
1938	if (CC == ISD::SETEQ \|\| CC == ISD::SETNE) {
1939	if (isInt32Immediate(RHS, Imm)) {
1940	// SETEQ/SETNE comparison with 16-bit immediate, fold it.
1941	if (isUInt<16>(Imm))
1942	return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, LHS,
1943	getI32Imm(Imm & 0xFFFF, dl)),
1944	0);
1945	// If this is a 16-bit signed immediate, fold it.
1946	if (isInt<16>((int)Imm))
1947	return SDValue(CurDAG->getMachineNode(PPC::CMPWI, dl, MVT::i32, LHS,
1948	getI32Imm(Imm & 0xFFFF, dl)),
1949	0);
1950
1951	// For non-equality comparisons, the default code would materialize the
1952	// constant, then compare against it, like this:
1953	// lis r2, 4660
1954	// ori r2, r2, 22136
1955	// cmpw cr0, r3, r2
1956	// Since we are just comparing for equality, we can emit this instead:
1957	// xoris r0,r3,0x1234
1958	// cmplwi cr0,r0,0x5678
1959	// beq cr0,L6
1960	SDValue Xor(CurDAG->getMachineNode(PPC::XORIS, dl, MVT::i32, LHS,
1961	getI32Imm(Imm >> 16, dl)), 0);
1962	return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, Xor,
1963	getI32Imm(Imm & 0xFFFF, dl)), 0);
1964	}
1965	Opc = PPC::CMPLW;
1966	} else if (ISD::isUnsignedIntSetCC(CC)) {
1967	if (isInt32Immediate(RHS, Imm) && isUInt<16>(Imm))
1968	return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, LHS,
1969	getI32Imm(Imm & 0xFFFF, dl)), 0);
1970	Opc = PPC::CMPLW;
1971	} else {
1972	short SImm;
1973	if (isIntS16Immediate(RHS, SImm))
1974	return SDValue(CurDAG->getMachineNode(PPC::CMPWI, dl, MVT::i32, LHS,
1975	getI32Imm((int)SImm & 0xFFFF,
1976	dl)),
1977	0);
1978	Opc = PPC::CMPW;
1979	}
1980	} else if (LHS.getValueType() == MVT::i64) {
1981	uint64_t Imm;
1982	if (CC == ISD::SETEQ \|\| CC == ISD::SETNE) {
1983	if (isInt64Immediate(RHS.getNode(), Imm)) {
1984	// SETEQ/SETNE comparison with 16-bit immediate, fold it.
1985	if (isUInt<16>(Imm))
1986	return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, LHS,
1987	getI32Imm(Imm & 0xFFFF, dl)),
1988	0);
1989	// If this is a 16-bit signed immediate, fold it.
1990	if (isInt<16>(Imm))
1991	return SDValue(CurDAG->getMachineNode(PPC::CMPDI, dl, MVT::i64, LHS,
1992	getI32Imm(Imm & 0xFFFF, dl)),
1993	0);
1994
1995	// For non-equality comparisons, the default code would materialize the
1996	// constant, then compare against it, like this:
1997	// lis r2, 4660
1998	// ori r2, r2, 22136
1999	// cmpd cr0, r3, r2
2000	// Since we are just comparing for equality, we can emit this instead:
2001	// xoris r0,r3,0x1234
2002	// cmpldi cr0,r0,0x5678
2003	// beq cr0,L6
2004	if (isUInt<32>(Imm)) {
2005	SDValue Xor(CurDAG->getMachineNode(PPC::XORIS8, dl, MVT::i64, LHS,
2006	getI64Imm(Imm >> 16, dl)), 0);
2007	return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, Xor,
2008	getI64Imm(Imm & 0xFFFF, dl)),
2009	0);
2010	}
2011	}
2012	Opc = PPC::CMPLD;
2013	} else if (ISD::isUnsignedIntSetCC(CC)) {
2014	if (isInt64Immediate(RHS.getNode(), Imm) && isUInt<16>(Imm))
2015	return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, LHS,
2016	getI64Imm(Imm & 0xFFFF, dl)), 0);
2017	Opc = PPC::CMPLD;
2018	} else {
2019	short SImm;
2020	if (isIntS16Immediate(RHS, SImm))
2021	return SDValue(CurDAG->getMachineNode(PPC::CMPDI, dl, MVT::i64, LHS,
2022	getI64Imm(SImm & 0xFFFF, dl)),
2023	0);
2024	Opc = PPC::CMPD;
2025	}
2026	} else if (LHS.getValueType() == MVT::f32) {
2027	Opc = PPC::FCMPUS;
2028	} else {
2029	assert(LHS.getValueType() == MVT::f64 && "Unknown vt!")((LHS.getValueType() == MVT::f64 && "Unknown vt!") ? static_cast <void> (0) : __assert_fail ("LHS.getValueType() == MVT::f64 && \"Unknown vt!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2029, __PRETTY_FUNCTION__));
2030	Opc = PPCSubTarget->hasVSX() ? PPC::XSCMPUDP : PPC::FCMPUD;
2031	}
2032	return SDValue(CurDAG->getMachineNode(Opc, dl, MVT::i32, LHS, RHS), 0);
2033	}
2034
2035	static PPC::Predicate getPredicateForSetCC(ISD::CondCode CC) {
2036	switch (CC) {
2037	case ISD::SETUEQ:
2038	case ISD::SETONE:
2039	case ISD::SETOLE:
2040	case ISD::SETOGE:
2041	llvm_unreachable("Should be lowered by legalize!")::llvm::llvm_unreachable_internal("Should be lowered by legalize!" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2041);
2042	default: llvm_unreachable("Unknown condition!")::llvm::llvm_unreachable_internal("Unknown condition!", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2042);
2043	case ISD::SETOEQ:
2044	case ISD::SETEQ: return PPC::PRED_EQ;
2045	case ISD::SETUNE:
2046	case ISD::SETNE: return PPC::PRED_NE;
2047	case ISD::SETOLT:
2048	case ISD::SETLT: return PPC::PRED_LT;
2049	case ISD::SETULE:
2050	case ISD::SETLE: return PPC::PRED_LE;
2051	case ISD::SETOGT:
2052	case ISD::SETGT: return PPC::PRED_GT;
2053	case ISD::SETUGE:
2054	case ISD::SETGE: return PPC::PRED_GE;
2055	case ISD::SETO: return PPC::PRED_NU;
2056	case ISD::SETUO: return PPC::PRED_UN;
2057	// These two are invalid for floating point. Assume we have int.
2058	case ISD::SETULT: return PPC::PRED_LT;
2059	case ISD::SETUGT: return PPC::PRED_GT;
2060	}
2061	}
2062
2063	/// getCRIdxForSetCC - Return the index of the condition register field
2064	/// associated with the SetCC condition, and whether or not the field is
2065	/// treated as inverted. That is, lt = 0; ge = 0 inverted.
2066	static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool &Invert) {
2067	Invert = false;
2068	switch (CC) {
2069	default: llvm_unreachable("Unknown condition!")::llvm::llvm_unreachable_internal("Unknown condition!", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2069);
2070	case ISD::SETOLT:
2071	case ISD::SETLT: return 0; // Bit #0 = SETOLT
2072	case ISD::SETOGT:
2073	case ISD::SETGT: return 1; // Bit #1 = SETOGT
2074	case ISD::SETOEQ:
2075	case ISD::SETEQ: return 2; // Bit #2 = SETOEQ
2076	case ISD::SETUO: return 3; // Bit #3 = SETUO
2077	case ISD::SETUGE:
2078	case ISD::SETGE: Invert = true; return 0; // !Bit #0 = SETUGE
2079	case ISD::SETULE:
2080	case ISD::SETLE: Invert = true; return 1; // !Bit #1 = SETULE
2081	case ISD::SETUNE:
2082	case ISD::SETNE: Invert = true; return 2; // !Bit #2 = SETUNE
2083	case ISD::SETO: Invert = true; return 3; // !Bit #3 = SETO
2084	case ISD::SETUEQ:
2085	case ISD::SETOGE:
2086	case ISD::SETOLE:
2087	case ISD::SETONE:
2088	llvm_unreachable("Invalid branch code: should be expanded by legalize")::llvm::llvm_unreachable_internal("Invalid branch code: should be expanded by legalize" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2088);
2089	// These are invalid for floating point. Assume integer.
2090	case ISD::SETULT: return 0;
2091	case ISD::SETUGT: return 1;
2092	}
2093	}
2094
2095	// getVCmpInst: return the vector compare instruction for the specified
2096	// vector type and condition code. Since this is for altivec specific code,
2097	// only support the altivec types (v16i8, v8i16, v4i32, v2i64, and v4f32).
2098	static unsigned int getVCmpInst(MVT VecVT, ISD::CondCode CC,
2099	bool HasVSX, bool &Swap, bool &Negate) {
2100	Swap = false;
2101	Negate = false;
2102
2103	if (VecVT.isFloatingPoint()) {
2104	/* Handle some cases by swapping input operands. */
2105	switch (CC) {
2106	case ISD::SETLE: CC = ISD::SETGE; Swap = true; break;
2107	case ISD::SETLT: CC = ISD::SETGT; Swap = true; break;
2108	case ISD::SETOLE: CC = ISD::SETOGE; Swap = true; break;
2109	case ISD::SETOLT: CC = ISD::SETOGT; Swap = true; break;
2110	case ISD::SETUGE: CC = ISD::SETULE; Swap = true; break;
2111	case ISD::SETUGT: CC = ISD::SETULT; Swap = true; break;
2112	default: break;
2113	}
2114	/* Handle some cases by negating the result. */
2115	switch (CC) {
2116	case ISD::SETNE: CC = ISD::SETEQ; Negate = true; break;
2117	case ISD::SETUNE: CC = ISD::SETOEQ; Negate = true; break;
2118	case ISD::SETULE: CC = ISD::SETOGT; Negate = true; break;
2119	case ISD::SETULT: CC = ISD::SETOGE; Negate = true; break;
2120	default: break;
2121	}
2122	/* We have instructions implementing the remaining cases. */
2123	switch (CC) {
2124	case ISD::SETEQ:
2125	case ISD::SETOEQ:
2126	if (VecVT == MVT::v4f32)
2127	return HasVSX ? PPC::XVCMPEQSP : PPC::VCMPEQFP;
2128	else if (VecVT == MVT::v2f64)
2129	return PPC::XVCMPEQDP;
2130	break;
2131	case ISD::SETGT:
2132	case ISD::SETOGT:
2133	if (VecVT == MVT::v4f32)
2134	return HasVSX ? PPC::XVCMPGTSP : PPC::VCMPGTFP;
2135	else if (VecVT == MVT::v2f64)
2136	return PPC::XVCMPGTDP;
2137	break;
2138	case ISD::SETGE:
2139	case ISD::SETOGE:
2140	if (VecVT == MVT::v4f32)
2141	return HasVSX ? PPC::XVCMPGESP : PPC::VCMPGEFP;
2142	else if (VecVT == MVT::v2f64)
2143	return PPC::XVCMPGEDP;
2144	break;
2145	default:
2146	break;
2147	}
2148	llvm_unreachable("Invalid floating-point vector compare condition")::llvm::llvm_unreachable_internal("Invalid floating-point vector compare condition" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2148);
2149	} else {
2150	/* Handle some cases by swapping input operands. */
2151	switch (CC) {
2152	case ISD::SETGE: CC = ISD::SETLE; Swap = true; break;
2153	case ISD::SETLT: CC = ISD::SETGT; Swap = true; break;
2154	case ISD::SETUGE: CC = ISD::SETULE; Swap = true; break;
2155	case ISD::SETULT: CC = ISD::SETUGT; Swap = true; break;
2156	default: break;
2157	}
2158	/* Handle some cases by negating the result. */
2159	switch (CC) {
2160	case ISD::SETNE: CC = ISD::SETEQ; Negate = true; break;
2161	case ISD::SETUNE: CC = ISD::SETUEQ; Negate = true; break;
2162	case ISD::SETLE: CC = ISD::SETGT; Negate = true; break;
2163	case ISD::SETULE: CC = ISD::SETUGT; Negate = true; break;
2164	default: break;
2165	}
2166	/* We have instructions implementing the remaining cases. */
2167	switch (CC) {
2168	case ISD::SETEQ:
2169	case ISD::SETUEQ:
2170	if (VecVT == MVT::v16i8)
2171	return PPC::VCMPEQUB;
2172	else if (VecVT == MVT::v8i16)
2173	return PPC::VCMPEQUH;
2174	else if (VecVT == MVT::v4i32)
2175	return PPC::VCMPEQUW;
2176	else if (VecVT == MVT::v2i64)
2177	return PPC::VCMPEQUD;
2178	break;
2179	case ISD::SETGT:
2180	if (VecVT == MVT::v16i8)
2181	return PPC::VCMPGTSB;
2182	else if (VecVT == MVT::v8i16)
2183	return PPC::VCMPGTSH;
2184	else if (VecVT == MVT::v4i32)
2185	return PPC::VCMPGTSW;
2186	else if (VecVT == MVT::v2i64)
2187	return PPC::VCMPGTSD;
2188	break;
2189	case ISD::SETUGT:
2190	if (VecVT == MVT::v16i8)
2191	return PPC::VCMPGTUB;
2192	else if (VecVT == MVT::v8i16)
2193	return PPC::VCMPGTUH;
2194	else if (VecVT == MVT::v4i32)
2195	return PPC::VCMPGTUW;
2196	else if (VecVT == MVT::v2i64)
2197	return PPC::VCMPGTUD;
2198	break;
2199	default:
2200	break;
2201	}
2202	llvm_unreachable("Invalid integer vector compare condition")::llvm::llvm_unreachable_internal("Invalid integer vector compare condition" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2202);
2203	}
2204	}
2205
2206	SDNode PPCDAGToDAGISel::SelectSETCC(SDNode N) {
2207	SDLoc dl(N);
2208	unsigned Imm;
2209	ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
2210	EVT PtrVT =
2211	CurDAG->getTargetLoweringInfo().getPointerTy(CurDAG->getDataLayout());
2212	bool isPPC64 = (PtrVT == MVT::i64);
2213
2214	if (!PPCSubTarget->useCRBits() &&
2215	isInt32Immediate(N->getOperand(1), Imm)) {
2216	// We can codegen setcc op, imm very efficiently compared to a brcond.
2217	// Check for those cases here.
2218	// setcc op, 0
2219	if (Imm == 0) {
2220	SDValue Op = N->getOperand(0);
2221	switch (CC) {
2222	default: break;
2223	case ISD::SETEQ: {
2224	Op = SDValue(CurDAG->getMachineNode(PPC::CNTLZW, dl, MVT::i32, Op), 0);
2225	SDValue Ops[] = { Op, getI32Imm(27, dl), getI32Imm(5, dl),
2226	getI32Imm(31, dl) };
2227	return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2228	}
2229	case ISD::SETNE: {
2230	if (isPPC64) break;
2231	SDValue AD =
2232	SDValue(CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
2233	Op, getI32Imm(~0U, dl)), 0);
2234	return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op,
2235	AD.getValue(1));
2236	}
2237	case ISD::SETLT: {
2238	SDValue Ops[] = { Op, getI32Imm(1, dl), getI32Imm(31, dl),
2239	getI32Imm(31, dl) };
2240	return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2241	}
2242	case ISD::SETGT: {
2243	SDValue T =
2244	SDValue(CurDAG->getMachineNode(PPC::NEG, dl, MVT::i32, Op), 0);
2245	T = SDValue(CurDAG->getMachineNode(PPC::ANDC, dl, MVT::i32, T, Op), 0);
2246	SDValue Ops[] = { T, getI32Imm(1, dl), getI32Imm(31, dl),
2247	getI32Imm(31, dl) };
2248	return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2249	}
2250	}
2251	} else if (Imm == ~0U) { // setcc op, -1
2252	SDValue Op = N->getOperand(0);
2253	switch (CC) {
2254	default: break;
2255	case ISD::SETEQ:
2256	if (isPPC64) break;
2257	Op = SDValue(CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
2258	Op, getI32Imm(1, dl)), 0);
2259	return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
2260	SDValue(CurDAG->getMachineNode(PPC::LI, dl,
2261	MVT::i32,
2262	getI32Imm(0, dl)),
2263	0), Op.getValue(1));
2264	case ISD::SETNE: {
2265	if (isPPC64) break;
2266	Op = SDValue(CurDAG->getMachineNode(PPC::NOR, dl, MVT::i32, Op, Op), 0);
2267	SDNode *AD = CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
2268	Op, getI32Imm(~0U, dl));
2269	return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, SDValue(AD, 0),
2270	Op, SDValue(AD, 1));
2271	}
2272	case ISD::SETLT: {
2273	SDValue AD = SDValue(CurDAG->getMachineNode(PPC::ADDI, dl, MVT::i32, Op,
2274	getI32Imm(1, dl)), 0);
2275	SDValue AN = SDValue(CurDAG->getMachineNode(PPC::AND, dl, MVT::i32, AD,
2276	Op), 0);
2277	SDValue Ops[] = { AN, getI32Imm(1, dl), getI32Imm(31, dl),
2278	getI32Imm(31, dl) };
2279	return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2280	}
2281	case ISD::SETGT: {
2282	SDValue Ops[] = { Op, getI32Imm(1, dl), getI32Imm(31, dl),
2283	getI32Imm(31, dl) };
2284	Op = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
2285	return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Op,
2286	getI32Imm(1, dl));
2287	}
2288	}
2289	}
2290	}
2291
2292	SDValue LHS = N->getOperand(0);
2293	SDValue RHS = N->getOperand(1);
2294
2295	// Altivec Vector compare instructions do not set any CR register by default and
2296	// vector compare operations return the same type as the operands.
2297	if (LHS.getValueType().isVector()) {
2298	if (PPCSubTarget->hasQPX())
2299	return nullptr;
2300
2301	EVT VecVT = LHS.getValueType();
2302	bool Swap, Negate;
2303	unsigned int VCmpInst = getVCmpInst(VecVT.getSimpleVT(), CC,
2304	PPCSubTarget->hasVSX(), Swap, Negate);
2305	if (Swap)
2306	std::swap(LHS, RHS);
2307
2308	EVT ResVT = VecVT.changeVectorElementTypeToInteger();
2309	if (Negate) {
2310	SDValue VCmp(CurDAG->getMachineNode(VCmpInst, dl, ResVT, LHS, RHS), 0);
2311	return CurDAG->SelectNodeTo(N, PPCSubTarget->hasVSX() ? PPC::XXLNOR :
2312	PPC::VNOR,
2313	ResVT, VCmp, VCmp);
2314	}
2315
2316	return CurDAG->SelectNodeTo(N, VCmpInst, ResVT, LHS, RHS);
2317	}
2318
2319	if (PPCSubTarget->useCRBits())
2320	return nullptr;
2321
2322	bool Inv;
2323	unsigned Idx = getCRIdxForSetCC(CC, Inv);
2324	SDValue CCReg = SelectCC(LHS, RHS, CC, dl);
2325	SDValue IntCR;
2326
2327	// Force the ccreg into CR7.
2328	SDValue CR7Reg = CurDAG->getRegister(PPC::CR7, MVT::i32);
2329
2330	SDValue InFlag(nullptr, 0); // Null incoming flag value.
2331	CCReg = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, CR7Reg, CCReg,
2332	InFlag).getValue(1);
2333
2334	IntCR = SDValue(CurDAG->getMachineNode(PPC::MFOCRF, dl, MVT::i32, CR7Reg,
2335	CCReg), 0);
2336
2337	SDValue Ops[] = { IntCR, getI32Imm((32 - (3 - Idx)) & 31, dl),
2338	getI32Imm(31, dl), getI32Imm(31, dl) };
2339	if (!Inv)
2340	return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2341
2342	// Get the specified bit.
2343	SDValue Tmp =
2344	SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops), 0);
2345	return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1, dl));
2346	}
2347
2348	SDNode PPCDAGToDAGISel::transferMemOperands(SDNode N, SDNode *Result) {
2349	// Transfer memoperands.
2350	MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
2351	MemOp[0] = cast<MemSDNode>(N)->getMemOperand();
2352	cast<MachineSDNode>(Result)->setMemRefs(MemOp, MemOp + 1);
2353	return Result;
2354	}
2355
2356
2357	// Select - Convert the specified operand from a target-independent to a
2358	// target-specific node if it hasn't already been changed.
2359	SDNode PPCDAGToDAGISel::Select(SDNode N) {
2360	SDLoc dl(N);
2361	if (N->isMachineOpcode()) {
2362	N->setNodeId(-1);
2363	return nullptr; // Already selected.
2364	}
2365
2366	// In case any misguided DAG-level optimizations form an ADD with a
2367	// TargetConstant operand, crash here instead of miscompiling (by selecting
2368	// an r+r add instead of some kind of r+i add).
2369	if (N->getOpcode() == ISD::ADD &&
2370	N->getOperand(1).getOpcode() == ISD::TargetConstant)
2371	llvm_unreachable("Invalid ADD with TargetConstant operand")::llvm::llvm_unreachable_internal("Invalid ADD with TargetConstant operand" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2371);
2372
2373	// Try matching complex bit permutations before doing anything else.
2374	if (SDNode *NN = SelectBitPermutation(N))
2375	return NN;
2376
2377	switch (N->getOpcode()) {
2378	default: break;
2379
2380	case ISD::Constant: {
2381	if (N->getValueType(0) == MVT::i64)
2382	return SelectInt64(CurDAG, N);
2383	break;
2384	}
2385
2386	case ISD::SETCC: {
2387	SDNode *SN = SelectSETCC(N);
2388	if (SN)
2389	return SN;
2390	break;
2391	}
2392	case PPCISD::GlobalBaseReg:
2393	return getGlobalBaseReg();
2394
2395	case ISD::FrameIndex:
2396	return getFrameIndex(N, N);
2397
2398	case PPCISD::MFOCRF: {
2399	SDValue InFlag = N->getOperand(1);
2400	return CurDAG->getMachineNode(PPC::MFOCRF, dl, MVT::i32,
2401	N->getOperand(0), InFlag);
2402	}
2403
2404	case PPCISD::READ_TIME_BASE: {
2405	return CurDAG->getMachineNode(PPC::ReadTB, dl, MVT::i32, MVT::i32,
2406	MVT::Other, N->getOperand(0));
2407	}
2408
2409	case PPCISD::SRA_ADDZE: {
2410	SDValue N0 = N->getOperand(0);
2411	SDValue ShiftAmt =
2412	CurDAG->getTargetConstant(*cast<ConstantSDNode>(N->getOperand(1))->
2413	getConstantIntValue(), dl,
2414	N->getValueType(0));
2415	if (N->getValueType(0) == MVT::i64) {
2416	SDNode *Op =
2417	CurDAG->getMachineNode(PPC::SRADI, dl, MVT::i64, MVT::Glue,
2418	N0, ShiftAmt);
2419	return CurDAG->SelectNodeTo(N, PPC::ADDZE8, MVT::i64,
2420	SDValue(Op, 0), SDValue(Op, 1));
2421	} else {
2422	assert(N->getValueType(0) == MVT::i32 &&((N->getValueType(0) == MVT::i32 && "Expecting i64 or i32 in PPCISD::SRA_ADDZE" ) ? static_cast<void> (0) : __assert_fail ("N->getValueType(0) == MVT::i32 && \"Expecting i64 or i32 in PPCISD::SRA_ADDZE\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2423, __PRETTY_FUNCTION__))
2423	"Expecting i64 or i32 in PPCISD::SRA_ADDZE")((N->getValueType(0) == MVT::i32 && "Expecting i64 or i32 in PPCISD::SRA_ADDZE" ) ? static_cast<void> (0) : __assert_fail ("N->getValueType(0) == MVT::i32 && \"Expecting i64 or i32 in PPCISD::SRA_ADDZE\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2423, __PRETTY_FUNCTION__));
2424	SDNode *Op =
2425	CurDAG->getMachineNode(PPC::SRAWI, dl, MVT::i32, MVT::Glue,
2426	N0, ShiftAmt);
2427	return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
2428	SDValue(Op, 0), SDValue(Op, 1));
2429	}
2430	}
2431
2432	case ISD::LOAD: {
2433	// Handle preincrement loads.
2434	LoadSDNode *LD = cast<LoadSDNode>(N);
2435	EVT LoadedVT = LD->getMemoryVT();
2436
2437	// Normal loads are handled by code generated from the .td file.
2438	if (LD->getAddressingMode() != ISD::PRE_INC)
2439	break;
2440
2441	SDValue Offset = LD->getOffset();
2442	if (Offset.getOpcode() == ISD::TargetConstant \|\|
2443	Offset.getOpcode() == ISD::TargetGlobalAddress) {
2444
2445	unsigned Opcode;
2446	bool isSExt = LD->getExtensionType() == ISD::SEXTLOAD;
2447	if (LD->getValueType(0) != MVT::i64) {
2448	// Handle PPC32 integer and normal FP loads.
2449	assert((!isSExt \|\| LoadedVT == MVT::i16) && "Invalid sext update load")(((!isSExt \|\| LoadedVT == MVT::i16) && "Invalid sext update load" ) ? static_cast<void> (0) : __assert_fail ("(!isSExt \|\| LoadedVT == MVT::i16) && \"Invalid sext update load\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2449, __PRETTY_FUNCTION__));
2450	switch (LoadedVT.getSimpleVT().SimpleTy) {
2451	default: llvm_unreachable("Invalid PPC load type!")::llvm::llvm_unreachable_internal("Invalid PPC load type!", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2451);
2452	case MVT::f64: Opcode = PPC::LFDU; break;
2453	case MVT::f32: Opcode = PPC::LFSU; break;
2454	case MVT::i32: Opcode = PPC::LWZU; break;
2455	case MVT::i16: Opcode = isSExt ? PPC::LHAU : PPC::LHZU; break;
2456	case MVT::i1:
2457	case MVT::i8: Opcode = PPC::LBZU; break;
2458	}
2459	} else {
2460	assert(LD->getValueType(0) == MVT::i64 && "Unknown load result type!")((LD->getValueType(0) == MVT::i64 && "Unknown load result type!" ) ? static_cast<void> (0) : __assert_fail ("LD->getValueType(0) == MVT::i64 && \"Unknown load result type!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2460, __PRETTY_FUNCTION__));
2461	assert((!isSExt \|\| LoadedVT == MVT::i16) && "Invalid sext update load")(((!isSExt \|\| LoadedVT == MVT::i16) && "Invalid sext update load" ) ? static_cast<void> (0) : __assert_fail ("(!isSExt \|\| LoadedVT == MVT::i16) && \"Invalid sext update load\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2461, __PRETTY_FUNCTION__));
2462	switch (LoadedVT.getSimpleVT().SimpleTy) {
2463	default: llvm_unreachable("Invalid PPC load type!")::llvm::llvm_unreachable_internal("Invalid PPC load type!", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2463);
2464	case MVT::i64: Opcode = PPC::LDU; break;
2465	case MVT::i32: Opcode = PPC::LWZU8; break;
2466	case MVT::i16: Opcode = isSExt ? PPC::LHAU8 : PPC::LHZU8; break;
2467	case MVT::i1:
2468	case MVT::i8: Opcode = PPC::LBZU8; break;
2469	}
2470	}
2471
2472	SDValue Chain = LD->getChain();
2473	SDValue Base = LD->getBasePtr();
2474	SDValue Ops[] = { Offset, Base, Chain };
2475	return transferMemOperands(
2476	N, CurDAG->getMachineNode(
2477	Opcode, dl, LD->getValueType(0),
2478	PPCLowering->getPointerTy(CurDAG->getDataLayout()), MVT::Other,
2479	Ops));
2480	} else {
2481	unsigned Opcode;
2482	bool isSExt = LD->getExtensionType() == ISD::SEXTLOAD;
2483	if (LD->getValueType(0) != MVT::i64) {
2484	// Handle PPC32 integer and normal FP loads.
2485	assert((!isSExt \|\| LoadedVT == MVT::i16) && "Invalid sext update load")(((!isSExt \|\| LoadedVT == MVT::i16) && "Invalid sext update load" ) ? static_cast<void> (0) : __assert_fail ("(!isSExt \|\| LoadedVT == MVT::i16) && \"Invalid sext update load\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2485, __PRETTY_FUNCTION__));
2486	switch (LoadedVT.getSimpleVT().SimpleTy) {
2487	default: llvm_unreachable("Invalid PPC load type!")::llvm::llvm_unreachable_internal("Invalid PPC load type!", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2487);
2488	case MVT::v4f64: Opcode = PPC::QVLFDUX; break; // QPX
2489	case MVT::v4f32: Opcode = PPC::QVLFSUX; break; // QPX
2490	case MVT::f64: Opcode = PPC::LFDUX; break;
2491	case MVT::f32: Opcode = PPC::LFSUX; break;
2492	case MVT::i32: Opcode = PPC::LWZUX; break;
2493	case MVT::i16: Opcode = isSExt ? PPC::LHAUX : PPC::LHZUX; break;
2494	case MVT::i1:
2495	case MVT::i8: Opcode = PPC::LBZUX; break;
2496	}
2497	} else {
2498	assert(LD->getValueType(0) == MVT::i64 && "Unknown load result type!")((LD->getValueType(0) == MVT::i64 && "Unknown load result type!" ) ? static_cast<void> (0) : __assert_fail ("LD->getValueType(0) == MVT::i64 && \"Unknown load result type!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2498, __PRETTY_FUNCTION__));
2499	assert((!isSExt \|\| LoadedVT == MVT::i16 \|\| LoadedVT == MVT::i32) &&(((!isSExt \|\| LoadedVT == MVT::i16 \|\| LoadedVT == MVT::i32) && "Invalid sext update load") ? static_cast<void> (0) : __assert_fail ("(!isSExt \|\| LoadedVT == MVT::i16 \|\| LoadedVT == MVT::i32) && \"Invalid sext update load\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2500, __PRETTY_FUNCTION__))
2500	"Invalid sext update load")(((!isSExt \|\| LoadedVT == MVT::i16 \|\| LoadedVT == MVT::i32) && "Invalid sext update load") ? static_cast<void> (0) : __assert_fail ("(!isSExt \|\| LoadedVT == MVT::i16 \|\| LoadedVT == MVT::i32) && \"Invalid sext update load\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2500, __PRETTY_FUNCTION__));
2501	switch (LoadedVT.getSimpleVT().SimpleTy) {
2502	default: llvm_unreachable("Invalid PPC load type!")::llvm::llvm_unreachable_internal("Invalid PPC load type!", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2502);
2503	case MVT::i64: Opcode = PPC::LDUX; break;
2504	case MVT::i32: Opcode = isSExt ? PPC::LWAUX : PPC::LWZUX8; break;
2505	case MVT::i16: Opcode = isSExt ? PPC::LHAUX8 : PPC::LHZUX8; break;
2506	case MVT::i1:
2507	case MVT::i8: Opcode = PPC::LBZUX8; break;
2508	}
2509	}
2510
2511	SDValue Chain = LD->getChain();
2512	SDValue Base = LD->getBasePtr();
2513	SDValue Ops[] = { Base, Offset, Chain };
2514	return transferMemOperands(
2515	N, CurDAG->getMachineNode(
2516	Opcode, dl, LD->getValueType(0),
2517	PPCLowering->getPointerTy(CurDAG->getDataLayout()), MVT::Other,
2518	Ops));
2519	}
2520	}
2521
2522	case ISD::AND: {
2523	unsigned Imm, Imm2, SH, MB, ME;
2524	uint64_t Imm64;
2525
2526	// If this is an and of a value rotated between 0 and 31 bits and then and'd
2527	// with a mask, emit rlwinm
2528	if (isInt32Immediate(N->getOperand(1), Imm) &&
2529	isRotateAndMask(N->getOperand(0).getNode(), Imm, false, SH, MB, ME)) {
2530	SDValue Val = N->getOperand(0).getOperand(0);
2531	SDValue Ops[] = { Val, getI32Imm(SH, dl), getI32Imm(MB, dl),
2532	getI32Imm(ME, dl) };
2533	return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2534	}
2535	// If this is just a masked value where the input is not handled above, and
2536	// is not a rotate-left (handled by a pattern in the .td file), emit rlwinm
2537	if (isInt32Immediate(N->getOperand(1), Imm) &&
2538	isRunOfOnes(Imm, MB, ME) &&
2539	N->getOperand(0).getOpcode() != ISD::ROTL) {
2540	SDValue Val = N->getOperand(0);
2541	SDValue Ops[] = { Val, getI32Imm(0, dl), getI32Imm(MB, dl),
2542	getI32Imm(ME, dl) };
2543	return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2544	}
2545	// If this is a 64-bit zero-extension mask, emit rldicl.
2546	if (isInt64Immediate(N->getOperand(1).getNode(), Imm64) &&
2547	isMask_64(Imm64)) {
2548	SDValue Val = N->getOperand(0);
2549	MB = 64 - countTrailingOnes(Imm64);
2550	SH = 0;
2551
2552	// If the operand is a logical right shift, we can fold it into this
2553	// instruction: rldicl(rldicl(x, 64-n, n), 0, mb) -> rldicl(x, 64-n, mb)
2554	// for n <= mb. The right shift is really a left rotate followed by a
2555	// mask, and this mask is a more-restrictive sub-mask of the mask implied
2556	// by the shift.
2557	if (Val.getOpcode() == ISD::SRL &&
2558	isInt32Immediate(Val.getOperand(1).getNode(), Imm) && Imm <= MB) {
2559	assert(Imm < 64 && "Illegal shift amount")((Imm < 64 && "Illegal shift amount") ? static_cast <void> (0) : __assert_fail ("Imm < 64 && \"Illegal shift amount\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2559, __PRETTY_FUNCTION__));
2560	Val = Val.getOperand(0);
2561	SH = 64 - Imm;
2562	}
2563
2564	SDValue Ops[] = { Val, getI32Imm(SH, dl), getI32Imm(MB, dl) };
2565	return CurDAG->SelectNodeTo(N, PPC::RLDICL, MVT::i64, Ops);
2566	}
2567	// AND X, 0 -> 0, not "rlwinm 32".
2568	if (isInt32Immediate(N->getOperand(1), Imm) && (Imm == 0)) {
2569	ReplaceUses(SDValue(N, 0), N->getOperand(1));
2570	return nullptr;
2571	}
2572	// ISD::OR doesn't get all the bitfield insertion fun.
2573	// (and (or x, c1), c2) where isRunOfOnes(~(c1^c2)) might be a
2574	// bitfield insert.
2575	if (isInt32Immediate(N->getOperand(1), Imm) &&
2576	N->getOperand(0).getOpcode() == ISD::OR &&
2577	isInt32Immediate(N->getOperand(0).getOperand(1), Imm2)) {
2578	// The idea here is to check whether this is equivalent to:
2579	// (c1 & m) \| (x & ~m)
2580	// where m is a run-of-ones mask. The logic here is that, for each bit in
2581	// c1 and c2:
2582	// - if both are 1, then the output will be 1.
2583	// - if both are 0, then the output will be 0.
2584	// - if the bit in c1 is 0, and the bit in c2 is 1, then the output will
2585	// come from x.
2586	// - if the bit in c1 is 1, and the bit in c2 is 0, then the output will
2587	// be 0.
2588	// If that last condition is never the case, then we can form m from the
2589	// bits that are the same between c1 and c2.
2590	unsigned MB, ME;
2591	if (isRunOfOnes(~(Imm^Imm2), MB, ME) && !(~Imm & Imm2)) {
2592	SDValue Ops[] = { N->getOperand(0).getOperand(0),
2593	N->getOperand(0).getOperand(1),
2594	getI32Imm(0, dl), getI32Imm(MB, dl),
2595	getI32Imm(ME, dl) };
2596	return CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops);
2597	}
2598	}
2599
2600	// Other cases are autogenerated.
2601	break;
2602	}
2603	case ISD::OR: {
2604	if (N->getValueType(0) == MVT::i32)
2605	if (SDNode *I = SelectBitfieldInsert(N))
2606	return I;
2607
2608	short Imm;
2609	if (N->getOperand(0)->getOpcode() == ISD::FrameIndex &&
2610	isIntS16Immediate(N->getOperand(1), Imm)) {
2611	APInt LHSKnownZero, LHSKnownOne;
2612	CurDAG->computeKnownBits(N->getOperand(0), LHSKnownZero, LHSKnownOne);
2613
2614	// If this is equivalent to an add, then we can fold it with the
2615	// FrameIndex calculation.
2616	if ((LHSKnownZero.getZExtValue()\|~(uint64_t)Imm) == ~0ULL)
2617	return getFrameIndex(N, N->getOperand(0).getNode(), (int)Imm);
2618	}
2619
2620	// Other cases are autogenerated.
2621	break;
2622	}
2623	case ISD::ADD: {
2624	short Imm;
2625	if (N->getOperand(0)->getOpcode() == ISD::FrameIndex &&
2626	isIntS16Immediate(N->getOperand(1), Imm))
2627	return getFrameIndex(N, N->getOperand(0).getNode(), (int)Imm);
2628
2629	break;
2630	}
2631	case ISD::SHL: {
2632	unsigned Imm, SH, MB, ME;
2633	if (isOpcWithIntImmediate(N->getOperand(0).getNode(), ISD::AND, Imm) &&
2634	isRotateAndMask(N, Imm, true, SH, MB, ME)) {
2635	SDValue Ops[] = { N->getOperand(0).getOperand(0),
2636	getI32Imm(SH, dl), getI32Imm(MB, dl),
2637	getI32Imm(ME, dl) };
2638	return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2639	}
2640
2641	// Other cases are autogenerated.
2642	break;
2643	}
2644	case ISD::SRL: {
2645	unsigned Imm, SH, MB, ME;
2646	if (isOpcWithIntImmediate(N->getOperand(0).getNode(), ISD::AND, Imm) &&
2647	isRotateAndMask(N, Imm, true, SH, MB, ME)) {
2648	SDValue Ops[] = { N->getOperand(0).getOperand(0),
2649	getI32Imm(SH, dl), getI32Imm(MB, dl),
2650	getI32Imm(ME, dl) };
2651	return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
2652	}
2653
2654	// Other cases are autogenerated.
2655	break;
2656	}
2657	// FIXME: Remove this once the ANDI glue bug is fixed:
2658	case PPCISD::ANDIo_1_EQ_BIT:
2659	case PPCISD::ANDIo_1_GT_BIT: {
2660	if (!ANDIGlueBug)
2661	break;
2662
2663	EVT InVT = N->getOperand(0).getValueType();
2664	assert((InVT == MVT::i64 \|\| InVT == MVT::i32) &&(((InVT == MVT::i64 \|\| InVT == MVT::i32) && "Invalid input type for ANDIo_1_EQ_BIT" ) ? static_cast<void> (0) : __assert_fail ("(InVT == MVT::i64 \|\| InVT == MVT::i32) && \"Invalid input type for ANDIo_1_EQ_BIT\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2665, __PRETTY_FUNCTION__))
2665	"Invalid input type for ANDIo_1_EQ_BIT")(((InVT == MVT::i64 \|\| InVT == MVT::i32) && "Invalid input type for ANDIo_1_EQ_BIT" ) ? static_cast<void> (0) : __assert_fail ("(InVT == MVT::i64 \|\| InVT == MVT::i32) && \"Invalid input type for ANDIo_1_EQ_BIT\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2665, __PRETTY_FUNCTION__));
2666
2667	unsigned Opcode = (InVT == MVT::i64) ? PPC::ANDIo8 : PPC::ANDIo;
2668	SDValue AndI(CurDAG->getMachineNode(Opcode, dl, InVT, MVT::Glue,
2669	N->getOperand(0),
2670	CurDAG->getTargetConstant(1, dl, InVT)),
2671	0);
2672	SDValue CR0Reg = CurDAG->getRegister(PPC::CR0, MVT::i32);
2673	SDValue SRIdxVal =
2674	CurDAG->getTargetConstant(N->getOpcode() == PPCISD::ANDIo_1_EQ_BIT ?
2675	PPC::sub_eq : PPC::sub_gt, dl, MVT::i32);
2676
2677	return CurDAG->SelectNodeTo(N, TargetOpcode::EXTRACT_SUBREG, MVT::i1,
2678	CR0Reg, SRIdxVal,
2679	SDValue(AndI.getNode(), 1) /* glue */);
2680	}
2681	case ISD::SELECT_CC: {
2682	ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
2683	EVT PtrVT =
2684	CurDAG->getTargetLoweringInfo().getPointerTy(CurDAG->getDataLayout());
2685	bool isPPC64 = (PtrVT == MVT::i64);
2686
2687	// If this is a select of i1 operands, we'll pattern match it.
2688	if (PPCSubTarget->useCRBits() &&
2689	N->getOperand(0).getValueType() == MVT::i1)
2690	break;
2691
2692	// Handle the setcc cases here. select_cc lhs, 0, 1, 0, cc
2693	if (!isPPC64)
2694	if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1)))
2695	if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N->getOperand(2)))
2696	if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N->getOperand(3)))
2697	if (N1C->isNullValue() && N3C->isNullValue() &&
2698	N2C->getZExtValue() == 1ULL && CC == ISD::SETNE &&
2699	// FIXME: Implement this optzn for PPC64.
2700	N->getValueType(0) == MVT::i32) {
2701	SDNode *Tmp =
2702	CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
2703	N->getOperand(0), getI32Imm(~0U, dl));
2704	return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32,
2705	SDValue(Tmp, 0), N->getOperand(0),
2706	SDValue(Tmp, 1));
2707	}
2708
2709	SDValue CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC, dl);
2710
2711	if (N->getValueType(0) == MVT::i1) {
2712	// An i1 select is: (c & t) \| (!c & f).
2713	bool Inv;
2714	unsigned Idx = getCRIdxForSetCC(CC, Inv);
2715
2716	unsigned SRI;
2717	switch (Idx) {
2718	default: llvm_unreachable("Invalid CC index")::llvm::llvm_unreachable_internal("Invalid CC index", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2718);
2719	case 0: SRI = PPC::sub_lt; break;
2720	case 1: SRI = PPC::sub_gt; break;
2721	case 2: SRI = PPC::sub_eq; break;
2722	case 3: SRI = PPC::sub_un; break;
2723	}
2724
2725	SDValue CCBit = CurDAG->getTargetExtractSubreg(SRI, dl, MVT::i1, CCReg);
2726
2727	SDValue NotCCBit(CurDAG->getMachineNode(PPC::CRNOR, dl, MVT::i1,
2728	CCBit, CCBit), 0);
2729	SDValue C = Inv ? NotCCBit : CCBit,
2730	NotC = Inv ? CCBit : NotCCBit;
2731
2732	SDValue CAndT(CurDAG->getMachineNode(PPC::CRAND, dl, MVT::i1,
2733	C, N->getOperand(2)), 0);
2734	SDValue NotCAndF(CurDAG->getMachineNode(PPC::CRAND, dl, MVT::i1,
2735	NotC, N->getOperand(3)), 0);
2736
2737	return CurDAG->SelectNodeTo(N, PPC::CROR, MVT::i1, CAndT, NotCAndF);
2738	}
2739
2740	unsigned BROpc = getPredicateForSetCC(CC);
2741
2742	unsigned SelectCCOp;
2743	if (N->getValueType(0) == MVT::i32)
2744	SelectCCOp = PPC::SELECT_CC_I4;
2745	else if (N->getValueType(0) == MVT::i64)
2746	SelectCCOp = PPC::SELECT_CC_I8;
2747	else if (N->getValueType(0) == MVT::f32)
2748	if (PPCSubTarget->hasP8Vector())
2749	SelectCCOp = PPC::SELECT_CC_VSSRC;
2750	else
2751	SelectCCOp = PPC::SELECT_CC_F4;
2752	else if (N->getValueType(0) == MVT::f64)
2753	if (PPCSubTarget->hasVSX())
2754	SelectCCOp = PPC::SELECT_CC_VSFRC;
2755	else
2756	SelectCCOp = PPC::SELECT_CC_F8;
2757	else if (PPCSubTarget->hasQPX() && N->getValueType(0) == MVT::v4f64)
2758	SelectCCOp = PPC::SELECT_CC_QFRC;
2759	else if (PPCSubTarget->hasQPX() && N->getValueType(0) == MVT::v4f32)
2760	SelectCCOp = PPC::SELECT_CC_QSRC;
2761	else if (PPCSubTarget->hasQPX() && N->getValueType(0) == MVT::v4i1)
2762	SelectCCOp = PPC::SELECT_CC_QBRC;
2763	else if (N->getValueType(0) == MVT::v2f64 \|\|
2764	N->getValueType(0) == MVT::v2i64)
2765	SelectCCOp = PPC::SELECT_CC_VSRC;
2766	else
2767	SelectCCOp = PPC::SELECT_CC_VRRC;
2768
2769	SDValue Ops[] = { CCReg, N->getOperand(2), N->getOperand(3),
2770	getI32Imm(BROpc, dl) };
2771	return CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), Ops);
2772	}
2773	case ISD::VSELECT:
2774	if (PPCSubTarget->hasVSX()) {
2775	SDValue Ops[] = { N->getOperand(2), N->getOperand(1), N->getOperand(0) };
2776	return CurDAG->SelectNodeTo(N, PPC::XXSEL, N->getValueType(0), Ops);
2777	}
2778
2779	break;
2780	case ISD::VECTOR_SHUFFLE:
2781	if (PPCSubTarget->hasVSX() && (N->getValueType(0) == MVT::v2f64 \|\|
2782	N->getValueType(0) == MVT::v2i64)) {
2783	ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
2784
2785	SDValue Op1 = N->getOperand(SVN->getMaskElt(0) < 2 ? 0 : 1),
2786	Op2 = N->getOperand(SVN->getMaskElt(1) < 2 ? 0 : 1);
2787	unsigned DM[2];
2788
2789	for (int i = 0; i < 2; ++i)
2790	if (SVN->getMaskElt(i) <= 0 \|\| SVN->getMaskElt(i) == 2)
2791	DM[i] = 0;
2792	else
2793	DM[i] = 1;
2794
2795	if (Op1 == Op2 && DM[0] == 0 && DM[1] == 0 &&
2796	Op1.getOpcode() == ISD::SCALAR_TO_VECTOR &&
2797	isa<LoadSDNode>(Op1.getOperand(0))) {
2798	LoadSDNode *LD = cast<LoadSDNode>(Op1.getOperand(0));
2799	SDValue Base, Offset;
2800
2801	if (LD->isUnindexed() &&
2802	(LD->getMemoryVT() == MVT::f64 \|\|
2803	LD->getMemoryVT() == MVT::i64) &&
2804	SelectAddrIdxOnly(LD->getBasePtr(), Base, Offset)) {
2805	SDValue Chain = LD->getChain();
2806	SDValue Ops[] = { Base, Offset, Chain };
2807	return CurDAG->SelectNodeTo(N, PPC::LXVDSX,
2808	N->getValueType(0), Ops);
2809	}
2810	}
2811
2812	// For little endian, we must swap the input operands and adjust
2813	// the mask elements (reverse and invert them).
2814	if (PPCSubTarget->isLittleEndian()) {
2815	std::swap(Op1, Op2);
2816	unsigned tmp = DM[0];
2817	DM[0] = 1 - DM[1];
2818	DM[1] = 1 - tmp;
2819	}
2820
2821	SDValue DMV = CurDAG->getTargetConstant(DM[1] \| (DM[0] << 1), dl,
2822	MVT::i32);
2823	SDValue Ops[] = { Op1, Op2, DMV };
2824	return CurDAG->SelectNodeTo(N, PPC::XXPERMDI, N->getValueType(0), Ops);
2825	}
2826
2827	break;
2828	case PPCISD::BDNZ:
2829	case PPCISD::BDZ: {
2830	bool IsPPC64 = PPCSubTarget->isPPC64();
2831	SDValue Ops[] = { N->getOperand(1), N->getOperand(0) };
2832	return CurDAG->SelectNodeTo(N, N->getOpcode() == PPCISD::BDNZ ?
2833	(IsPPC64 ? PPC::BDNZ8 : PPC::BDNZ) :
2834	(IsPPC64 ? PPC::BDZ8 : PPC::BDZ),
2835	MVT::Other, Ops);
2836	}
2837	case PPCISD::COND_BRANCH: {
2838	// Op #0 is the Chain.
2839	// Op #1 is the PPC::PRED_* number.
2840	// Op #2 is the CR#
2841	// Op #3 is the Dest MBB
2842	// Op #4 is the Flag.
2843	// Prevent PPC::PRED_* from being selected into LI.
2844	SDValue Pred =
2845	getI32Imm(cast<ConstantSDNode>(N->getOperand(1))->getZExtValue(), dl);
2846	SDValue Ops[] = { Pred, N->getOperand(2), N->getOperand(3),
2847	N->getOperand(0), N->getOperand(4) };
2848	return CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops);
2849	}
2850	case ISD::BR_CC: {
2851	ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
2852	unsigned PCC = getPredicateForSetCC(CC);
2853
2854	if (N->getOperand(2).getValueType() == MVT::i1) {
2855	unsigned Opc;
2856	bool Swap;
2857	switch (PCC) {
2858	default: llvm_unreachable("Unexpected Boolean-operand predicate")::llvm::llvm_unreachable_internal("Unexpected Boolean-operand predicate" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2858);
2859	case PPC::PRED_LT: Opc = PPC::CRANDC; Swap = true; break;
2860	case PPC::PRED_LE: Opc = PPC::CRORC; Swap = true; break;
2861	case PPC::PRED_EQ: Opc = PPC::CREQV; Swap = false; break;
2862	case PPC::PRED_GE: Opc = PPC::CRORC; Swap = false; break;
2863	case PPC::PRED_GT: Opc = PPC::CRANDC; Swap = false; break;
2864	case PPC::PRED_NE: Opc = PPC::CRXOR; Swap = false; break;
2865	}
2866
2867	SDValue BitComp(CurDAG->getMachineNode(Opc, dl, MVT::i1,
2868	N->getOperand(Swap ? 3 : 2),
2869	N->getOperand(Swap ? 2 : 3)), 0);
2870	return CurDAG->SelectNodeTo(N, PPC::BC, MVT::Other,
2871	BitComp, N->getOperand(4), N->getOperand(0));
2872	}
2873
2874	SDValue CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC, dl);
2875	SDValue Ops[] = { getI32Imm(PCC, dl), CondCode,
2876	N->getOperand(4), N->getOperand(0) };
2877	return CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops);
2878	}
2879	case ISD::BRIND: {
2880	// FIXME: Should custom lower this.
2881	SDValue Chain = N->getOperand(0);
2882	SDValue Target = N->getOperand(1);
2883	unsigned Opc = Target.getValueType() == MVT::i32 ? PPC::MTCTR : PPC::MTCTR8;
2884	unsigned Reg = Target.getValueType() == MVT::i32 ? PPC::BCTR : PPC::BCTR8;
2885	Chain = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Glue, Target,
2886	Chain), 0);
2887	return CurDAG->SelectNodeTo(N, Reg, MVT::Other, Chain);
2888	}
2889	case PPCISD::TOC_ENTRY: {
2890	assert ((PPCSubTarget->isPPC64() \|\| PPCSubTarget->isSVR4ABI()) &&(((PPCSubTarget->isPPC64() \|\| PPCSubTarget->isSVR4ABI() ) && "Only supported for 64-bit ABI and 32-bit SVR4") ? static_cast<void> (0) : __assert_fail ("(PPCSubTarget->isPPC64() \|\| PPCSubTarget->isSVR4ABI()) && \"Only supported for 64-bit ABI and 32-bit SVR4\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2891, __PRETTY_FUNCTION__))
2891	"Only supported for 64-bit ABI and 32-bit SVR4")(((PPCSubTarget->isPPC64() \|\| PPCSubTarget->isSVR4ABI() ) && "Only supported for 64-bit ABI and 32-bit SVR4") ? static_cast<void> (0) : __assert_fail ("(PPCSubTarget->isPPC64() \|\| PPCSubTarget->isSVR4ABI()) && \"Only supported for 64-bit ABI and 32-bit SVR4\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2891, __PRETTY_FUNCTION__));
2892	if (PPCSubTarget->isSVR4ABI() && !PPCSubTarget->isPPC64()) {
2893	SDValue GA = N->getOperand(0);
2894	return transferMemOperands(N, CurDAG->getMachineNode(PPC::LWZtoc, dl,
2895	MVT::i32, GA, N->getOperand(1)));
2896	}
2897
2898	// For medium and large code model, we generate two instructions as
2899	// described below. Otherwise we allow SelectCodeCommon to handle this,
2900	// selecting one of LDtoc, LDtocJTI, LDtocCPT, and LDtocBA.
2901	CodeModel::Model CModel = TM.getCodeModel();
2902	if (CModel != CodeModel::Medium && CModel != CodeModel::Large)
2903	break;
2904
2905	// The first source operand is a TargetGlobalAddress or a TargetJumpTable.
2906	// If it is an externally defined symbol, a symbol with common linkage,
2907	// a non-local function address, or a jump table address, or if we are
2908	// generating code for large code model, we generate:
2909	// LDtocL(<ga:@sym>, ADDIStocHA(%X2, <ga:@sym>))
2910	// Otherwise we generate:
2911	// ADDItocL(ADDIStocHA(%X2, <ga:@sym>), <ga:@sym>)
2912	SDValue GA = N->getOperand(0);
2913	SDValue TOCbase = N->getOperand(1);
2914	SDNode *Tmp = CurDAG->getMachineNode(PPC::ADDIStocHA, dl, MVT::i64,
2915	TOCbase, GA);
2916
2917	if (isa<JumpTableSDNode>(GA) \|\| isa<BlockAddressSDNode>(GA) \|\|
2918	CModel == CodeModel::Large)
2919	return transferMemOperands(N, CurDAG->getMachineNode(PPC::LDtocL, dl,
2920	MVT::i64, GA, SDValue(Tmp, 0)));
2921
2922	if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(GA)) {
2923	const GlobalValue *GValue = G->getGlobal();
2924	if ((GValue->getType()->getElementType()->isFunctionTy() &&
2925	!GValue->isStrongDefinitionForLinker()) \|\|
2926	GValue->isDeclaration() \|\| GValue->hasCommonLinkage() \|\|
2927	GValue->hasAvailableExternallyLinkage())
2928	return transferMemOperands(N, CurDAG->getMachineNode(PPC::LDtocL, dl,
2929	MVT::i64, GA, SDValue(Tmp, 0)));
2930	}
2931
2932	return CurDAG->getMachineNode(PPC::ADDItocL, dl, MVT::i64,
2933	SDValue(Tmp, 0), GA);
2934	}
2935	case PPCISD::PPC32_PICGOT: {
2936	// Generate a PIC-safe GOT reference.
2937	assert(!PPCSubTarget->isPPC64() && PPCSubTarget->isSVR4ABI() &&((!PPCSubTarget->isPPC64() && PPCSubTarget->isSVR4ABI () && "PPCISD::PPC32_PICGOT is only supported for 32-bit SVR4" ) ? static_cast<void> (0) : __assert_fail ("!PPCSubTarget->isPPC64() && PPCSubTarget->isSVR4ABI() && \"PPCISD::PPC32_PICGOT is only supported for 32-bit SVR4\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2938, __PRETTY_FUNCTION__))
2938	"PPCISD::PPC32_PICGOT is only supported for 32-bit SVR4")((!PPCSubTarget->isPPC64() && PPCSubTarget->isSVR4ABI () && "PPCISD::PPC32_PICGOT is only supported for 32-bit SVR4" ) ? static_cast<void> (0) : __assert_fail ("!PPCSubTarget->isPPC64() && PPCSubTarget->isSVR4ABI() && \"PPCISD::PPC32_PICGOT is only supported for 32-bit SVR4\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2938, __PRETTY_FUNCTION__));
2939	return CurDAG->SelectNodeTo(
2940	N, PPC::PPC32PICGOT, PPCLowering->getPointerTy(CurDAG->getDataLayout()),
2941	MVT::i32);
2942	}
2943	case PPCISD::VADD_SPLAT: {
2944	// This expands into one of three sequences, depending on whether
2945	// the first operand is odd or even, positive or negative.
2946	assert(isa<ConstantSDNode>(N->getOperand(0)) &&((isa<ConstantSDNode>(N->getOperand(0)) && isa <ConstantSDNode>(N->getOperand(1)) && "Invalid operand on VADD_SPLAT!" ) ? static_cast<void> (0) : __assert_fail ("isa<ConstantSDNode>(N->getOperand(0)) && isa<ConstantSDNode>(N->getOperand(1)) && \"Invalid operand on VADD_SPLAT!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2948, __PRETTY_FUNCTION__))
2947	isa<ConstantSDNode>(N->getOperand(1)) &&((isa<ConstantSDNode>(N->getOperand(0)) && isa <ConstantSDNode>(N->getOperand(1)) && "Invalid operand on VADD_SPLAT!" ) ? static_cast<void> (0) : __assert_fail ("isa<ConstantSDNode>(N->getOperand(0)) && isa<ConstantSDNode>(N->getOperand(1)) && \"Invalid operand on VADD_SPLAT!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2948, __PRETTY_FUNCTION__))
2948	"Invalid operand on VADD_SPLAT!")((isa<ConstantSDNode>(N->getOperand(0)) && isa <ConstantSDNode>(N->getOperand(1)) && "Invalid operand on VADD_SPLAT!" ) ? static_cast<void> (0) : __assert_fail ("isa<ConstantSDNode>(N->getOperand(0)) && isa<ConstantSDNode>(N->getOperand(1)) && \"Invalid operand on VADD_SPLAT!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2948, __PRETTY_FUNCTION__));
2949
2950	int Elt = N->getConstantOperandVal(0);
2951	int EltSize = N->getConstantOperandVal(1);
2952	unsigned Opc1, Opc2, Opc3;
2953	EVT VT;
2954
2955	if (EltSize == 1) {
2956	Opc1 = PPC::VSPLTISB;
2957	Opc2 = PPC::VADDUBM;
2958	Opc3 = PPC::VSUBUBM;
2959	VT = MVT::v16i8;
2960	} else if (EltSize == 2) {
2961	Opc1 = PPC::VSPLTISH;
2962	Opc2 = PPC::VADDUHM;
2963	Opc3 = PPC::VSUBUHM;
2964	VT = MVT::v8i16;
2965	} else {
2966	assert(EltSize == 4 && "Invalid element size on VADD_SPLAT!")((EltSize == 4 && "Invalid element size on VADD_SPLAT!" ) ? static_cast<void> (0) : __assert_fail ("EltSize == 4 && \"Invalid element size on VADD_SPLAT!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 2966, __PRETTY_FUNCTION__));
2967	Opc1 = PPC::VSPLTISW;
2968	Opc2 = PPC::VADDUWM;
2969	Opc3 = PPC::VSUBUWM;
2970	VT = MVT::v4i32;
2971	}
2972
2973	if ((Elt & 1) == 0) {
2974	// Elt is even, in the range [-32,-18] + [16,30].
2975	//
2976	// Convert: VADD_SPLAT elt, size
2977	// Into: tmp = VSPLTIS[BHW] elt
2978	// VADDU[BHW]M tmp, tmp
2979	// Where: [BHW] = B for size = 1, H for size = 2, W for size = 4
2980	SDValue EltVal = getI32Imm(Elt >> 1, dl);
2981	SDNode *Tmp = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
2982	SDValue TmpVal = SDValue(Tmp, 0);
2983	return CurDAG->getMachineNode(Opc2, dl, VT, TmpVal, TmpVal);
2984
2985	} else if (Elt > 0) {
2986	// Elt is odd and positive, in the range [17,31].
2987	//
2988	// Convert: VADD_SPLAT elt, size
2989	// Into: tmp1 = VSPLTIS[BHW] elt-16
2990	// tmp2 = VSPLTIS[BHW] -16
2991	// VSUBU[BHW]M tmp1, tmp2
2992	SDValue EltVal = getI32Imm(Elt - 16, dl);
2993	SDNode *Tmp1 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
2994	EltVal = getI32Imm(-16, dl);
2995	SDNode *Tmp2 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
2996	return CurDAG->getMachineNode(Opc3, dl, VT, SDValue(Tmp1, 0),
2997	SDValue(Tmp2, 0));
2998
2999	} else {
3000	// Elt is odd and negative, in the range [-31,-17].
3001	//
3002	// Convert: VADD_SPLAT elt, size
3003	// Into: tmp1 = VSPLTIS[BHW] elt+16
3004	// tmp2 = VSPLTIS[BHW] -16
3005	// VADDU[BHW]M tmp1, tmp2
3006	SDValue EltVal = getI32Imm(Elt + 16, dl);
3007	SDNode *Tmp1 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
3008	EltVal = getI32Imm(-16, dl);
3009	SDNode *Tmp2 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
3010	return CurDAG->getMachineNode(Opc2, dl, VT, SDValue(Tmp1, 0),
3011	SDValue(Tmp2, 0));
3012	}
3013	}
3014	}
3015
3016	return SelectCode(N);
3017	}
3018
3019	// If the target supports the cmpb instruction, do the idiom recognition here.
3020	// We don't do this as a DAG combine because we don't want to do it as nodes
3021	// are being combined (because we might miss part of the eventual idiom). We
3022	// don't want to do it during instruction selection because we want to reuse
3023	// the logic for lowering the masking operations already part of the
3024	// instruction selector.
3025	SDValue PPCDAGToDAGISel::combineToCMPB(SDNode *N) {
3026	SDLoc dl(N);
3027
3028	assert(N->getOpcode() == ISD::OR &&((N->getOpcode() == ISD::OR && "Only OR nodes are supported for CMPB" ) ? static_cast<void> (0) : __assert_fail ("N->getOpcode() == ISD::OR && \"Only OR nodes are supported for CMPB\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 3029, __PRETTY_FUNCTION__))
3029	"Only OR nodes are supported for CMPB")((N->getOpcode() == ISD::OR && "Only OR nodes are supported for CMPB" ) ? static_cast<void> (0) : __assert_fail ("N->getOpcode() == ISD::OR && \"Only OR nodes are supported for CMPB\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 3029, __PRETTY_FUNCTION__));
3030
3031	SDValue Res;
3032	if (!PPCSubTarget->hasCMPB())
3033	return Res;
3034
3035	if (N->getValueType(0) != MVT::i32 &&
3036	N->getValueType(0) != MVT::i64)
3037	return Res;
3038
3039	EVT VT = N->getValueType(0);
3040
3041	SDValue RHS, LHS;
3042	bool BytesFound[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
3043	uint64_t Mask = 0, Alt = 0;
3044
3045	auto IsByteSelectCC = [this](SDValue O, unsigned &b,
3046	uint64_t &Mask, uint64_t &Alt,
3047	SDValue &LHS, SDValue &RHS) {
3048	if (O.getOpcode() != ISD::SELECT_CC)
3049	return false;
3050	ISD::CondCode CC = cast<CondCodeSDNode>(O.getOperand(4))->get();
3051
3052	if (!isa<ConstantSDNode>(O.getOperand(2)) \|\|
3053	!isa<ConstantSDNode>(O.getOperand(3)))
3054	return false;
3055
3056	uint64_t PM = O.getConstantOperandVal(2);
3057	uint64_t PAlt = O.getConstantOperandVal(3);
3058	for (b = 0; b < 8; ++b) {
3059	uint64_t Mask = UINT64_C(0xFF)0xFFUL << (8*b);
3060	if (PM && (PM & Mask) == PM && (PAlt & Mask) == PAlt)
3061	break;
3062	}
3063
3064	if (b == 8)
3065	return false;
3066	Mask \|= PM;
3067	Alt \|= PAlt;
3068
3069	if (!isa<ConstantSDNode>(O.getOperand(1)) \|\|
3070	O.getConstantOperandVal(1) != 0) {
3071	SDValue Op0 = O.getOperand(0), Op1 = O.getOperand(1);
3072	if (Op0.getOpcode() == ISD::TRUNCATE)
3073	Op0 = Op0.getOperand(0);
3074	if (Op1.getOpcode() == ISD::TRUNCATE)
3075	Op1 = Op1.getOperand(0);
3076
3077	if (Op0.getOpcode() == ISD::SRL && Op1.getOpcode() == ISD::SRL &&
3078	Op0.getOperand(1) == Op1.getOperand(1) && CC == ISD::SETEQ &&
3079	isa<ConstantSDNode>(Op0.getOperand(1))) {
3080
3081	unsigned Bits = Op0.getValueType().getSizeInBits();
3082	if (b != Bits/8-1)
3083	return false;
3084	if (Op0.getConstantOperandVal(1) != Bits-8)
3085	return false;
3086
3087	LHS = Op0.getOperand(0);
3088	RHS = Op1.getOperand(0);
3089	return true;
3090	}
3091
3092	// When we have small integers (i16 to be specific), the form present
3093	// post-legalization uses SETULT in the SELECT_CC for the
3094	// higher-order byte, depending on the fact that the
3095	// even-higher-order bytes are known to all be zero, for example:
3096	// select_cc (xor $lhs, $rhs), 256, 65280, 0, setult
3097	// (so when the second byte is the same, because all higher-order
3098	// bits from bytes 3 and 4 are known to be zero, the result of the
3099	// xor can be at most 255)
3100	if (Op0.getOpcode() == ISD::XOR && CC == ISD::SETULT &&
3101	isa<ConstantSDNode>(O.getOperand(1))) {
3102
3103	uint64_t ULim = O.getConstantOperandVal(1);
3104	if (ULim != (UINT64_C(1)1UL << b*8))
3105	return false;
3106
3107	// Now we need to make sure that the upper bytes are known to be
3108	// zero.
3109	unsigned Bits = Op0.getValueType().getSizeInBits();
3110	if (!CurDAG->MaskedValueIsZero(Op0,
3111	APInt::getHighBitsSet(Bits, Bits - (b+1)*8)))
3112	return false;
3113
3114	LHS = Op0.getOperand(0);
3115	RHS = Op0.getOperand(1);
3116	return true;
3117	}
3118
3119	return false;
3120	}
3121
3122	if (CC != ISD::SETEQ)
3123	return false;
3124
3125	SDValue Op = O.getOperand(0);
3126	if (Op.getOpcode() == ISD::AND) {
3127	if (!isa<ConstantSDNode>(Op.getOperand(1)))
3128	return false;
3129	if (Op.getConstantOperandVal(1) != (UINT64_C(0xFF)0xFFUL << (8*b)))
3130	return false;
3131
3132	SDValue XOR = Op.getOperand(0);
3133	if (XOR.getOpcode() == ISD::TRUNCATE)
3134	XOR = XOR.getOperand(0);
3135	if (XOR.getOpcode() != ISD::XOR)
3136	return false;
3137
3138	LHS = XOR.getOperand(0);
3139	RHS = XOR.getOperand(1);
3140	return true;
3141	} else if (Op.getOpcode() == ISD::SRL) {
3142	if (!isa<ConstantSDNode>(Op.getOperand(1)))
3143	return false;
3144	unsigned Bits = Op.getValueType().getSizeInBits();
3145	if (b != Bits/8-1)
3146	return false;
3147	if (Op.getConstantOperandVal(1) != Bits-8)
3148	return false;
3149
3150	SDValue XOR = Op.getOperand(0);
3151	if (XOR.getOpcode() == ISD::TRUNCATE)
3152	XOR = XOR.getOperand(0);
3153	if (XOR.getOpcode() != ISD::XOR)
3154	return false;
3155
3156	LHS = XOR.getOperand(0);
3157	RHS = XOR.getOperand(1);
3158	return true;
3159	}
3160
3161	return false;
3162	};
3163
3164	SmallVector<SDValue, 8> Queue(1, SDValue(N, 0));
3165	while (!Queue.empty()) {
3166	SDValue V = Queue.pop_back_val();
3167
3168	for (const SDValue &O : V.getNode()->ops()) {
3169	unsigned b;
3170	uint64_t M = 0, A = 0;
3171	SDValue OLHS, ORHS;
3172	if (O.getOpcode() == ISD::OR) {
3173	Queue.push_back(O);
3174	} else if (IsByteSelectCC(O, b, M, A, OLHS, ORHS)) {
3175	if (!LHS) {
3176	LHS = OLHS;
3177	RHS = ORHS;
3178	BytesFound[b] = true;
3179	Mask \|= M;
3180	Alt \|= A;
3181	} else if ((LHS == ORHS && RHS == OLHS) \|\|
3182	(RHS == ORHS && LHS == OLHS)) {
3183	BytesFound[b] = true;
3184	Mask \|= M;
3185	Alt \|= A;
3186	} else {
3187	return Res;
3188	}
3189	} else {
3190	return Res;
3191	}
3192	}
3193	}
3194
3195	unsigned LastB = 0, BCnt = 0;
3196	for (unsigned i = 0; i < 8; ++i)
3197	if (BytesFound[LastB]) {
3198	++BCnt;
3199	LastB = i;
3200	}
3201
3202	if (!LastB \|\| BCnt < 2)
3203	return Res;
3204
3205	// Because we'll be zero-extending the output anyway if don't have a specific
3206	// value for each input byte (via the Mask), we can 'anyext' the inputs.
3207	if (LHS.getValueType() != VT) {
3208	LHS = CurDAG->getAnyExtOrTrunc(LHS, dl, VT);
3209	RHS = CurDAG->getAnyExtOrTrunc(RHS, dl, VT);
3210	}
3211
3212	Res = CurDAG->getNode(PPCISD::CMPB, dl, VT, LHS, RHS);
3213
3214	bool NonTrivialMask = ((int64_t) Mask) != INT64_C(-1)-1L;
3215	if (NonTrivialMask && !Alt) {
3216	// Res = Mask & CMPB
3217	Res = CurDAG->getNode(ISD::AND, dl, VT, Res,
3218	CurDAG->getConstant(Mask, dl, VT));
3219	} else if (Alt) {
3220	// Res = (CMPB & Mask) \| (~CMPB & Alt)
3221	// Which, as suggested here:
3222	// https://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge
3223	// can be written as:
3224	// Res = Alt ^ ((Alt ^ Mask) & CMPB)
3225	// useful because the (Alt ^ Mask) can be pre-computed.
3226	Res = CurDAG->getNode(ISD::AND, dl, VT, Res,
3227	CurDAG->getConstant(Mask ^ Alt, dl, VT));
3228	Res = CurDAG->getNode(ISD::XOR, dl, VT, Res,
3229	CurDAG->getConstant(Alt, dl, VT));
3230	}
3231
3232	return Res;
3233	}
3234
3235	// When CR bit registers are enabled, an extension of an i1 variable to a i32
3236	// or i64 value is lowered in terms of a SELECT_I[48] operation, and thus
3237	// involves constant materialization of a 0 or a 1 or both. If the result of
3238	// the extension is then operated upon by some operator that can be constant
3239	// folded with a constant 0 or 1, and that constant can be materialized using
3240	// only one instruction (like a zero or one), then we should fold in those
3241	// operations with the select.
3242	void PPCDAGToDAGISel::foldBoolExts(SDValue &Res, SDNode *&N) {
3243	if (!PPCSubTarget->useCRBits())
3244	return;
3245
3246	if (N->getOpcode() != ISD::ZERO_EXTEND &&
3247	N->getOpcode() != ISD::SIGN_EXTEND &&
3248	N->getOpcode() != ISD::ANY_EXTEND)
3249	return;
3250
3251	if (N->getOperand(0).getValueType() != MVT::i1)
3252	return;
3253
3254	if (!N->hasOneUse())
3255	return;
3256
3257	SDLoc dl(N);
3258	EVT VT = N->getValueType(0);
3259	SDValue Cond = N->getOperand(0);
3260	SDValue ConstTrue =
3261	CurDAG->getConstant(N->getOpcode() == ISD::SIGN_EXTEND ? -1 : 1, dl, VT);
3262	SDValue ConstFalse = CurDAG->getConstant(0, dl, VT);
3263
3264	do {
3265	SDNode User = N->use_begin();
3266	if (User->getNumOperands() != 2)
3267	break;
3268
3269	auto TryFold = [this, N, User, dl](SDValue Val) {
3270	SDValue UserO0 = User->getOperand(0), UserO1 = User->getOperand(1);
3271	SDValue O0 = UserO0.getNode() == N ? Val : UserO0;
3272	SDValue O1 = UserO1.getNode() == N ? Val : UserO1;
3273
3274	return CurDAG->FoldConstantArithmetic(User->getOpcode(), dl,
3275	User->getValueType(0),
3276	O0.getNode(), O1.getNode());
3277	};
3278
3279	SDValue TrueRes = TryFold(ConstTrue);
3280	if (!TrueRes)
3281	break;
3282	SDValue FalseRes = TryFold(ConstFalse);
3283	if (!FalseRes)
3284	break;
3285
3286	// For us to materialize these using one instruction, we must be able to
3287	// represent them as signed 16-bit integers.
3288	uint64_t True = cast<ConstantSDNode>(TrueRes)->getZExtValue(),
3289	False = cast<ConstantSDNode>(FalseRes)->getZExtValue();
3290	if (!isInt<16>(True) \|\| !isInt<16>(False))
3291	break;
3292
3293	// We can replace User with a new SELECT node, and try again to see if we
3294	// can fold the select with its user.
3295	Res = CurDAG->getSelect(dl, User->getValueType(0), Cond, TrueRes, FalseRes);
3296	N = User;
3297	ConstTrue = TrueRes;
3298	ConstFalse = FalseRes;
3299	} while (N->hasOneUse());
3300	}
3301
3302	void PPCDAGToDAGISel::PreprocessISelDAG() {
3303	SelectionDAG::allnodes_iterator Position(CurDAG->getRoot().getNode());
3304	++Position;
3305
3306	bool MadeChange = false;
3307	while (Position != CurDAG->allnodes_begin()) {
3308	SDNode N = &--Position;
3309	if (N->use_empty())
3310	continue;
3311
3312	SDValue Res;
3313	switch (N->getOpcode()) {
3314	default: break;
3315	case ISD::OR:
3316	Res = combineToCMPB(N);
3317	break;
3318	}
3319
3320	if (!Res)
3321	foldBoolExts(Res, N);
3322
3323	if (Res) {
3324	DEBUG(dbgs() << "PPC DAG preprocessing replacing:\nOld: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "PPC DAG preprocessing replacing:\nOld: " ; } } while (0);
3325	DEBUG(N->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { N->dump(CurDAG); } } while (0);
3326	DEBUG(dbgs() << "\nNew: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\nNew: "; } } while (0);
3327	DEBUG(Res.getNode()->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { Res.getNode()->dump(CurDAG); } } while ( 0);
3328	DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\n"; } } while (0);
3329
3330	CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Res);
3331	MadeChange = true;
3332	}
3333	}
3334
3335	if (MadeChange)
3336	CurDAG->RemoveDeadNodes();
3337	}
3338
3339	/// PostprocessISelDAG - Perform some late peephole optimizations
3340	/// on the DAG representation.
3341	void PPCDAGToDAGISel::PostprocessISelDAG() {
3342
3343	// Skip peepholes at -O0.
3344	if (TM.getOptLevel() == CodeGenOpt::None)
3345	return;
3346
3347	PeepholePPC64();
3348	PeepholeCROps();
3349	PeepholePPC64ZExt();
3350	}
3351
3352	// Check if all users of this node will become isel where the second operand
3353	// is the constant zero. If this is so, and if we can negate the condition,
3354	// then we can flip the true and false operands. This will allow the zero to
3355	// be folded with the isel so that we don't need to materialize a register
3356	// containing zero.
3357	bool PPCDAGToDAGISel::AllUsersSelectZero(SDNode *N) {
3358	// If we're not using isel, then this does not matter.
3359	if (!PPCSubTarget->hasISEL())
3360	return false;
3361
3362	for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
3363	UI != UE; ++UI) {
3364	SDNode User = UI;
3365	if (!User->isMachineOpcode())
3366	return false;
3367	if (User->getMachineOpcode() != PPC::SELECT_I4 &&
3368	User->getMachineOpcode() != PPC::SELECT_I8)
3369	return false;
3370
3371	SDNode *Op2 = User->getOperand(2).getNode();
3372	if (!Op2->isMachineOpcode())
3373	return false;
3374
3375	if (Op2->getMachineOpcode() != PPC::LI &&
3376	Op2->getMachineOpcode() != PPC::LI8)
3377	return false;
3378
3379	ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op2->getOperand(0));
3380	if (!C)
3381	return false;
3382
3383	if (!C->isNullValue())
3384	return false;
3385	}
3386
3387	return true;
3388	}
3389
3390	void PPCDAGToDAGISel::SwapAllSelectUsers(SDNode *N) {
3391	SmallVector<SDNode *, 4> ToReplace;
3392	for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
3393	UI != UE; ++UI) {
3394	SDNode User = UI;
3395	assert((User->getMachineOpcode() == PPC::SELECT_I4 \|\|(((User->getMachineOpcode() == PPC::SELECT_I4 \|\| User-> getMachineOpcode() == PPC::SELECT_I8) && "Must have all select users" ) ? static_cast<void> (0) : __assert_fail ("(User->getMachineOpcode() == PPC::SELECT_I4 \|\| User->getMachineOpcode() == PPC::SELECT_I8) && \"Must have all select users\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 3397, __PRETTY_FUNCTION__))
3396	User->getMachineOpcode() == PPC::SELECT_I8) &&(((User->getMachineOpcode() == PPC::SELECT_I4 \|\| User-> getMachineOpcode() == PPC::SELECT_I8) && "Must have all select users" ) ? static_cast<void> (0) : __assert_fail ("(User->getMachineOpcode() == PPC::SELECT_I4 \|\| User->getMachineOpcode() == PPC::SELECT_I8) && \"Must have all select users\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 3397, __PRETTY_FUNCTION__))
3397	"Must have all select users")(((User->getMachineOpcode() == PPC::SELECT_I4 \|\| User-> getMachineOpcode() == PPC::SELECT_I8) && "Must have all select users" ) ? static_cast<void> (0) : __assert_fail ("(User->getMachineOpcode() == PPC::SELECT_I4 \|\| User->getMachineOpcode() == PPC::SELECT_I8) && \"Must have all select users\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 3397, __PRETTY_FUNCTION__));
3398	ToReplace.push_back(User);
3399	}
3400
3401	for (SmallVector<SDNode *, 4>::iterator UI = ToReplace.begin(),
3402	UE = ToReplace.end(); UI != UE; ++UI) {
3403	SDNode User = UI;
3404	SDNode *ResNode =
3405	CurDAG->getMachineNode(User->getMachineOpcode(), SDLoc(User),
3406	User->getValueType(0), User->getOperand(0),
3407	User->getOperand(2),
3408	User->getOperand(1));
3409
3410	DEBUG(dbgs() << "CR Peephole replacing:\nOld: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "CR Peephole replacing:\nOld: " ; } } while (0);
3411	DEBUG(User->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { User->dump(CurDAG); } } while (0);
3412	DEBUG(dbgs() << "\nNew: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\nNew: "; } } while (0);
3413	DEBUG(ResNode->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { ResNode->dump(CurDAG); } } while (0);
3414	DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\n"; } } while (0);
3415
3416	ReplaceUses(User, ResNode);
3417	}
3418	}
3419
3420	void PPCDAGToDAGISel::PeepholeCROps() {
3421	bool IsModified;
3422	do {
3423	IsModified = false;
3424	for (SDNode &Node : CurDAG->allnodes()) {
3425	MachineSDNode *MachineNode = dyn_cast<MachineSDNode>(&Node);
3426	if (!MachineNode \|\| MachineNode->use_empty())
3427	continue;
3428	SDNode *ResNode = MachineNode;
3429
3430	bool Op1Set = false, Op1Unset = false,
3431	Op1Not = false,
3432	Op2Set = false, Op2Unset = false,
3433	Op2Not = false;
3434
3435	unsigned Opcode = MachineNode->getMachineOpcode();
3436	switch (Opcode) {
3437	default: break;
3438	case PPC::CRAND:
3439	case PPC::CRNAND:
3440	case PPC::CROR:
3441	case PPC::CRXOR:
3442	case PPC::CRNOR:
3443	case PPC::CREQV:
3444	case PPC::CRANDC:
3445	case PPC::CRORC: {
3446	SDValue Op = MachineNode->getOperand(1);
3447	if (Op.isMachineOpcode()) {
3448	if (Op.getMachineOpcode() == PPC::CRSET)
3449	Op2Set = true;
3450	else if (Op.getMachineOpcode() == PPC::CRUNSET)
3451	Op2Unset = true;
3452	else if (Op.getMachineOpcode() == PPC::CRNOR &&
3453	Op.getOperand(0) == Op.getOperand(1))
3454	Op2Not = true;
3455	}
3456	} // fallthrough
3457	case PPC::BC:
3458	case PPC::BCn:
3459	case PPC::SELECT_I4:
3460	case PPC::SELECT_I8:
3461	case PPC::SELECT_F4:
3462	case PPC::SELECT_F8:
3463	case PPC::SELECT_QFRC:
3464	case PPC::SELECT_QSRC:
3465	case PPC::SELECT_QBRC:
3466	case PPC::SELECT_VRRC:
3467	case PPC::SELECT_VSFRC:
3468	case PPC::SELECT_VSSRC:
3469	case PPC::SELECT_VSRC: {
3470	SDValue Op = MachineNode->getOperand(0);
3471	if (Op.isMachineOpcode()) {
3472	if (Op.getMachineOpcode() == PPC::CRSET)
3473	Op1Set = true;
3474	else if (Op.getMachineOpcode() == PPC::CRUNSET)
3475	Op1Unset = true;
3476	else if (Op.getMachineOpcode() == PPC::CRNOR &&
3477	Op.getOperand(0) == Op.getOperand(1))
3478	Op1Not = true;
3479	}
3480	}
3481	break;
3482	}
3483
3484	bool SelectSwap = false;
3485	switch (Opcode) {
3486	default: break;
3487	case PPC::CRAND:
3488	if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3489	// x & x = x
3490	ResNode = MachineNode->getOperand(0).getNode();
3491	else if (Op1Set)
3492	// 1 & y = y
3493	ResNode = MachineNode->getOperand(1).getNode();
3494	else if (Op2Set)
3495	// x & 1 = x
3496	ResNode = MachineNode->getOperand(0).getNode();
3497	else if (Op1Unset \|\| Op2Unset)
3498	// x & 0 = 0 & y = 0
3499	ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3500	MVT::i1);
3501	else if (Op1Not)
3502	// ~x & y = andc(y, x)
3503	ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3504	MVT::i1, MachineNode->getOperand(1),
3505	MachineNode->getOperand(0).
3506	getOperand(0));
3507	else if (Op2Not)
3508	// x & ~y = andc(x, y)
3509	ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3510	MVT::i1, MachineNode->getOperand(0),
3511	MachineNode->getOperand(1).
3512	getOperand(0));
3513	else if (AllUsersSelectZero(MachineNode))
3514	ResNode = CurDAG->getMachineNode(PPC::CRNAND, SDLoc(MachineNode),
3515	MVT::i1, MachineNode->getOperand(0),
3516	MachineNode->getOperand(1)),
3517	SelectSwap = true;
3518	break;
3519	case PPC::CRNAND:
3520	if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3521	// nand(x, x) -> nor(x, x)
3522	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3523	MVT::i1, MachineNode->getOperand(0),
3524	MachineNode->getOperand(0));
3525	else if (Op1Set)
3526	// nand(1, y) -> nor(y, y)
3527	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3528	MVT::i1, MachineNode->getOperand(1),
3529	MachineNode->getOperand(1));
3530	else if (Op2Set)
3531	// nand(x, 1) -> nor(x, x)
3532	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3533	MVT::i1, MachineNode->getOperand(0),
3534	MachineNode->getOperand(0));
3535	else if (Op1Unset \|\| Op2Unset)
3536	// nand(x, 0) = nand(0, y) = 1
3537	ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3538	MVT::i1);
3539	else if (Op1Not)
3540	// nand(~x, y) = ~(~x & y) = x \| ~y = orc(x, y)
3541	ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3542	MVT::i1, MachineNode->getOperand(0).
3543	getOperand(0),
3544	MachineNode->getOperand(1));
3545	else if (Op2Not)
3546	// nand(x, ~y) = ~x \| y = orc(y, x)
3547	ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3548	MVT::i1, MachineNode->getOperand(1).
3549	getOperand(0),
3550	MachineNode->getOperand(0));
3551	else if (AllUsersSelectZero(MachineNode))
3552	ResNode = CurDAG->getMachineNode(PPC::CRAND, SDLoc(MachineNode),
3553	MVT::i1, MachineNode->getOperand(0),
3554	MachineNode->getOperand(1)),
3555	SelectSwap = true;
3556	break;
3557	case PPC::CROR:
3558	if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3559	// x \| x = x
3560	ResNode = MachineNode->getOperand(0).getNode();
3561	else if (Op1Set \|\| Op2Set)
3562	// x \| 1 = 1 \| y = 1
3563	ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3564	MVT::i1);
3565	else if (Op1Unset)
3566	// 0 \| y = y
3567	ResNode = MachineNode->getOperand(1).getNode();
3568	else if (Op2Unset)
3569	// x \| 0 = x
3570	ResNode = MachineNode->getOperand(0).getNode();
3571	else if (Op1Not)
3572	// ~x \| y = orc(y, x)
3573	ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3574	MVT::i1, MachineNode->getOperand(1),
3575	MachineNode->getOperand(0).
3576	getOperand(0));
3577	else if (Op2Not)
3578	// x \| ~y = orc(x, y)
3579	ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3580	MVT::i1, MachineNode->getOperand(0),
3581	MachineNode->getOperand(1).
3582	getOperand(0));
3583	else if (AllUsersSelectZero(MachineNode))
3584	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3585	MVT::i1, MachineNode->getOperand(0),
3586	MachineNode->getOperand(1)),
3587	SelectSwap = true;
3588	break;
3589	case PPC::CRXOR:
3590	if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3591	// xor(x, x) = 0
3592	ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3593	MVT::i1);
3594	else if (Op1Set)
3595	// xor(1, y) -> nor(y, y)
3596	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3597	MVT::i1, MachineNode->getOperand(1),
3598	MachineNode->getOperand(1));
3599	else if (Op2Set)
3600	// xor(x, 1) -> nor(x, x)
3601	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3602	MVT::i1, MachineNode->getOperand(0),
3603	MachineNode->getOperand(0));
3604	else if (Op1Unset)
3605	// xor(0, y) = y
3606	ResNode = MachineNode->getOperand(1).getNode();
3607	else if (Op2Unset)
3608	// xor(x, 0) = x
3609	ResNode = MachineNode->getOperand(0).getNode();
3610	else if (Op1Not)
3611	// xor(~x, y) = eqv(x, y)
3612	ResNode = CurDAG->getMachineNode(PPC::CREQV, SDLoc(MachineNode),
3613	MVT::i1, MachineNode->getOperand(0).
3614	getOperand(0),
3615	MachineNode->getOperand(1));
3616	else if (Op2Not)
3617	// xor(x, ~y) = eqv(x, y)
3618	ResNode = CurDAG->getMachineNode(PPC::CREQV, SDLoc(MachineNode),
3619	MVT::i1, MachineNode->getOperand(0),
3620	MachineNode->getOperand(1).
3621	getOperand(0));
3622	else if (AllUsersSelectZero(MachineNode))
3623	ResNode = CurDAG->getMachineNode(PPC::CREQV, SDLoc(MachineNode),
3624	MVT::i1, MachineNode->getOperand(0),
3625	MachineNode->getOperand(1)),
3626	SelectSwap = true;
3627	break;
3628	case PPC::CRNOR:
3629	if (Op1Set \|\| Op2Set)
3630	// nor(1, y) -> 0
3631	ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3632	MVT::i1);
3633	else if (Op1Unset)
3634	// nor(0, y) = ~y -> nor(y, y)
3635	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3636	MVT::i1, MachineNode->getOperand(1),
3637	MachineNode->getOperand(1));
3638	else if (Op2Unset)
3639	// nor(x, 0) = ~x
3640	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3641	MVT::i1, MachineNode->getOperand(0),
3642	MachineNode->getOperand(0));
3643	else if (Op1Not)
3644	// nor(~x, y) = andc(x, y)
3645	ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3646	MVT::i1, MachineNode->getOperand(0).
3647	getOperand(0),
3648	MachineNode->getOperand(1));
3649	else if (Op2Not)
3650	// nor(x, ~y) = andc(y, x)
3651	ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3652	MVT::i1, MachineNode->getOperand(1).
3653	getOperand(0),
3654	MachineNode->getOperand(0));
3655	else if (AllUsersSelectZero(MachineNode))
3656	ResNode = CurDAG->getMachineNode(PPC::CROR, SDLoc(MachineNode),
3657	MVT::i1, MachineNode->getOperand(0),
3658	MachineNode->getOperand(1)),
3659	SelectSwap = true;
3660	break;
3661	case PPC::CREQV:
3662	if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3663	// eqv(x, x) = 1
3664	ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3665	MVT::i1);
3666	else if (Op1Set)
3667	// eqv(1, y) = y
3668	ResNode = MachineNode->getOperand(1).getNode();
3669	else if (Op2Set)
3670	// eqv(x, 1) = x
3671	ResNode = MachineNode->getOperand(0).getNode();
3672	else if (Op1Unset)
3673	// eqv(0, y) = ~y -> nor(y, y)
3674	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3675	MVT::i1, MachineNode->getOperand(1),
3676	MachineNode->getOperand(1));
3677	else if (Op2Unset)
3678	// eqv(x, 0) = ~x
3679	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3680	MVT::i1, MachineNode->getOperand(0),
3681	MachineNode->getOperand(0));
3682	else if (Op1Not)
3683	// eqv(~x, y) = xor(x, y)
3684	ResNode = CurDAG->getMachineNode(PPC::CRXOR, SDLoc(MachineNode),
3685	MVT::i1, MachineNode->getOperand(0).
3686	getOperand(0),
3687	MachineNode->getOperand(1));
3688	else if (Op2Not)
3689	// eqv(x, ~y) = xor(x, y)
3690	ResNode = CurDAG->getMachineNode(PPC::CRXOR, SDLoc(MachineNode),
3691	MVT::i1, MachineNode->getOperand(0),
3692	MachineNode->getOperand(1).
3693	getOperand(0));
3694	else if (AllUsersSelectZero(MachineNode))
3695	ResNode = CurDAG->getMachineNode(PPC::CRXOR, SDLoc(MachineNode),
3696	MVT::i1, MachineNode->getOperand(0),
3697	MachineNode->getOperand(1)),
3698	SelectSwap = true;
3699	break;
3700	case PPC::CRANDC:
3701	if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3702	// andc(x, x) = 0
3703	ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3704	MVT::i1);
3705	else if (Op1Set)
3706	// andc(1, y) = ~y
3707	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3708	MVT::i1, MachineNode->getOperand(1),
3709	MachineNode->getOperand(1));
3710	else if (Op1Unset \|\| Op2Set)
3711	// andc(0, y) = andc(x, 1) = 0
3712	ResNode = CurDAG->getMachineNode(PPC::CRUNSET, SDLoc(MachineNode),
3713	MVT::i1);
3714	else if (Op2Unset)
3715	// andc(x, 0) = x
3716	ResNode = MachineNode->getOperand(0).getNode();
3717	else if (Op1Not)
3718	// andc(~x, y) = ~(x \| y) = nor(x, y)
3719	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3720	MVT::i1, MachineNode->getOperand(0).
3721	getOperand(0),
3722	MachineNode->getOperand(1));
3723	else if (Op2Not)
3724	// andc(x, ~y) = x & y
3725	ResNode = CurDAG->getMachineNode(PPC::CRAND, SDLoc(MachineNode),
3726	MVT::i1, MachineNode->getOperand(0),
3727	MachineNode->getOperand(1).
3728	getOperand(0));
3729	else if (AllUsersSelectZero(MachineNode))
3730	ResNode = CurDAG->getMachineNode(PPC::CRORC, SDLoc(MachineNode),
3731	MVT::i1, MachineNode->getOperand(1),
3732	MachineNode->getOperand(0)),
3733	SelectSwap = true;
3734	break;
3735	case PPC::CRORC:
3736	if (MachineNode->getOperand(0) == MachineNode->getOperand(1))
3737	// orc(x, x) = 1
3738	ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3739	MVT::i1);
3740	else if (Op1Set \|\| Op2Unset)
3741	// orc(1, y) = orc(x, 0) = 1
3742	ResNode = CurDAG->getMachineNode(PPC::CRSET, SDLoc(MachineNode),
3743	MVT::i1);
3744	else if (Op2Set)
3745	// orc(x, 1) = x
3746	ResNode = MachineNode->getOperand(0).getNode();
3747	else if (Op1Unset)
3748	// orc(0, y) = ~y
3749	ResNode = CurDAG->getMachineNode(PPC::CRNOR, SDLoc(MachineNode),
3750	MVT::i1, MachineNode->getOperand(1),
3751	MachineNode->getOperand(1));
3752	else if (Op1Not)
3753	// orc(~x, y) = ~(x & y) = nand(x, y)
3754	ResNode = CurDAG->getMachineNode(PPC::CRNAND, SDLoc(MachineNode),
3755	MVT::i1, MachineNode->getOperand(0).
3756	getOperand(0),
3757	MachineNode->getOperand(1));
3758	else if (Op2Not)
3759	// orc(x, ~y) = x \| y
3760	ResNode = CurDAG->getMachineNode(PPC::CROR, SDLoc(MachineNode),
3761	MVT::i1, MachineNode->getOperand(0),
3762	MachineNode->getOperand(1).
3763	getOperand(0));
3764	else if (AllUsersSelectZero(MachineNode))
3765	ResNode = CurDAG->getMachineNode(PPC::CRANDC, SDLoc(MachineNode),
3766	MVT::i1, MachineNode->getOperand(1),
3767	MachineNode->getOperand(0)),
3768	SelectSwap = true;
3769	break;
3770	case PPC::SELECT_I4:
3771	case PPC::SELECT_I8:
3772	case PPC::SELECT_F4:
3773	case PPC::SELECT_F8:
3774	case PPC::SELECT_QFRC:
3775	case PPC::SELECT_QSRC:
3776	case PPC::SELECT_QBRC:
3777	case PPC::SELECT_VRRC:
3778	case PPC::SELECT_VSFRC:
3779	case PPC::SELECT_VSSRC:
3780	case PPC::SELECT_VSRC:
3781	if (Op1Set)
3782	ResNode = MachineNode->getOperand(1).getNode();
3783	else if (Op1Unset)
3784	ResNode = MachineNode->getOperand(2).getNode();
3785	else if (Op1Not)
3786	ResNode = CurDAG->getMachineNode(MachineNode->getMachineOpcode(),
3787	SDLoc(MachineNode),
3788	MachineNode->getValueType(0),
3789	MachineNode->getOperand(0).
3790	getOperand(0),
3791	MachineNode->getOperand(2),
3792	MachineNode->getOperand(1));
3793	break;
3794	case PPC::BC:
3795	case PPC::BCn:
3796	if (Op1Not)
3797	ResNode = CurDAG->getMachineNode(Opcode == PPC::BC ? PPC::BCn :
3798	PPC::BC,
3799	SDLoc(MachineNode),
3800	MVT::Other,
3801	MachineNode->getOperand(0).
3802	getOperand(0),
3803	MachineNode->getOperand(1),
3804	MachineNode->getOperand(2));
3805	// FIXME: Handle Op1Set, Op1Unset here too.
3806	break;
3807	}
3808
3809	// If we're inverting this node because it is used only by selects that
3810	// we'd like to swap, then swap the selects before the node replacement.
3811	if (SelectSwap)
3812	SwapAllSelectUsers(MachineNode);
3813
3814	if (ResNode != MachineNode) {
3815	DEBUG(dbgs() << "CR Peephole replacing:\nOld: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "CR Peephole replacing:\nOld: " ; } } while (0);
3816	DEBUG(MachineNode->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { MachineNode->dump(CurDAG); } } while (0 );
3817	DEBUG(dbgs() << "\nNew: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\nNew: "; } } while (0);
3818	DEBUG(ResNode->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { ResNode->dump(CurDAG); } } while (0);
3819	DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\n"; } } while (0);
3820
3821	ReplaceUses(MachineNode, ResNode);
3822	IsModified = true;
3823	}
3824	}
3825	if (IsModified)
3826	CurDAG->RemoveDeadNodes();
3827	} while (IsModified);
3828	}
3829
3830	// Gather the set of 32-bit operations that are known to have their
3831	// higher-order 32 bits zero, where ToPromote contains all such operations.
3832	static bool PeepholePPC64ZExtGather(SDValue Op32,
3833	SmallPtrSetImpl<SDNode *> &ToPromote) {
3834	if (!Op32.isMachineOpcode())
3835	return false;
3836
3837	// First, check for the "frontier" instructions (those that will clear the
3838	// higher-order 32 bits.
3839
3840	// For RLWINM and RLWNM, we need to make sure that the mask does not wrap
3841	// around. If it does not, then these instructions will clear the
3842	// higher-order bits.
3843	if ((Op32.getMachineOpcode() == PPC::RLWINM \|\|
3844	Op32.getMachineOpcode() == PPC::RLWNM) &&
3845	Op32.getConstantOperandVal(2) <= Op32.getConstantOperandVal(3)) {
3846	ToPromote.insert(Op32.getNode());
3847	return true;
3848	}
3849
3850	// SLW and SRW always clear the higher-order bits.
3851	if (Op32.getMachineOpcode() == PPC::SLW \|\|
3852	Op32.getMachineOpcode() == PPC::SRW) {
3853	ToPromote.insert(Op32.getNode());
3854	return true;
3855	}
3856
3857	// For LI and LIS, we need the immediate to be positive (so that it is not
3858	// sign extended).
3859	if (Op32.getMachineOpcode() == PPC::LI \|\|
3860	Op32.getMachineOpcode() == PPC::LIS) {
3861	if (!isUInt<15>(Op32.getConstantOperandVal(0)))
3862	return false;
3863
3864	ToPromote.insert(Op32.getNode());
3865	return true;
3866	}
3867
3868	// LHBRX and LWBRX always clear the higher-order bits.
3869	if (Op32.getMachineOpcode() == PPC::LHBRX \|\|
3870	Op32.getMachineOpcode() == PPC::LWBRX) {
3871	ToPromote.insert(Op32.getNode());
3872	return true;
3873	}
3874
3875	// CNTLZW always produces a 64-bit value in [0,32], and so is zero extended.
3876	if (Op32.getMachineOpcode() == PPC::CNTLZW) {
3877	ToPromote.insert(Op32.getNode());
3878	return true;
3879	}
3880
3881	// Next, check for those instructions we can look through.
3882
3883	// Assuming the mask does not wrap around, then the higher-order bits are
3884	// taken directly from the first operand.
3885	if (Op32.getMachineOpcode() == PPC::RLWIMI &&
3886	Op32.getConstantOperandVal(3) <= Op32.getConstantOperandVal(4)) {
3887	SmallPtrSet<SDNode *, 16> ToPromote1;
3888	if (!PeepholePPC64ZExtGather(Op32.getOperand(0), ToPromote1))
3889	return false;
3890
3891	ToPromote.insert(Op32.getNode());
3892	ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3893	return true;
3894	}
3895
3896	// For OR, the higher-order bits are zero if that is true for both operands.
3897	// For SELECT_I4, the same is true (but the relevant operand numbers are
3898	// shifted by 1).
3899	if (Op32.getMachineOpcode() == PPC::OR \|\|
3900	Op32.getMachineOpcode() == PPC::SELECT_I4) {
3901	unsigned B = Op32.getMachineOpcode() == PPC::SELECT_I4 ? 1 : 0;
3902	SmallPtrSet<SDNode *, 16> ToPromote1;
3903	if (!PeepholePPC64ZExtGather(Op32.getOperand(B+0), ToPromote1))
3904	return false;
3905	if (!PeepholePPC64ZExtGather(Op32.getOperand(B+1), ToPromote1))
3906	return false;
3907
3908	ToPromote.insert(Op32.getNode());
3909	ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3910	return true;
3911	}
3912
3913	// For ORI and ORIS, we need the higher-order bits of the first operand to be
3914	// zero, and also for the constant to be positive (so that it is not sign
3915	// extended).
3916	if (Op32.getMachineOpcode() == PPC::ORI \|\|
3917	Op32.getMachineOpcode() == PPC::ORIS) {
3918	SmallPtrSet<SDNode *, 16> ToPromote1;
3919	if (!PeepholePPC64ZExtGather(Op32.getOperand(0), ToPromote1))
3920	return false;
3921	if (!isUInt<15>(Op32.getConstantOperandVal(1)))
3922	return false;
3923
3924	ToPromote.insert(Op32.getNode());
3925	ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3926	return true;
3927	}
3928
3929	// The higher-order bits of AND are zero if that is true for at least one of
3930	// the operands.
3931	if (Op32.getMachineOpcode() == PPC::AND) {
3932	SmallPtrSet<SDNode *, 16> ToPromote1, ToPromote2;
3933	bool Op0OK =
3934	PeepholePPC64ZExtGather(Op32.getOperand(0), ToPromote1);
3935	bool Op1OK =
3936	PeepholePPC64ZExtGather(Op32.getOperand(1), ToPromote2);
3937	if (!Op0OK && !Op1OK)
3938	return false;
3939
3940	ToPromote.insert(Op32.getNode());
3941
3942	if (Op0OK)
3943	ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3944
3945	if (Op1OK)
3946	ToPromote.insert(ToPromote2.begin(), ToPromote2.end());
3947
3948	return true;
3949	}
3950
3951	// For ANDI and ANDIS, the higher-order bits are zero if either that is true
3952	// of the first operand, or if the second operand is positive (so that it is
3953	// not sign extended).
3954	if (Op32.getMachineOpcode() == PPC::ANDIo \|\|
3955	Op32.getMachineOpcode() == PPC::ANDISo) {
3956	SmallPtrSet<SDNode *, 16> ToPromote1;
3957	bool Op0OK =
3958	PeepholePPC64ZExtGather(Op32.getOperand(0), ToPromote1);
3959	bool Op1OK = isUInt<15>(Op32.getConstantOperandVal(1));
3960	if (!Op0OK && !Op1OK)
3961	return false;
3962
3963	ToPromote.insert(Op32.getNode());
3964
3965	if (Op0OK)
3966	ToPromote.insert(ToPromote1.begin(), ToPromote1.end());
3967
3968	return true;
3969	}
3970
3971	return false;
3972	}
3973
3974	void PPCDAGToDAGISel::PeepholePPC64ZExt() {
3975	if (!PPCSubTarget->isPPC64())
3976	return;
3977
3978	// When we zero-extend from i32 to i64, we use a pattern like this:
3979	// def : Pat<(i64 (zext i32:$in)),
3980	// (RLDICL (INSERT_SUBREG (i64 (IMPLICIT_DEF)), $in, sub_32),
3981	// 0, 32)>;
3982	// There are several 32-bit shift/rotate instructions, however, that will
3983	// clear the higher-order bits of their output, rendering the RLDICL
3984	// unnecessary. When that happens, we remove it here, and redefine the
3985	// relevant 32-bit operation to be a 64-bit operation.
3986
3987	SelectionDAG::allnodes_iterator Position(CurDAG->getRoot().getNode());
3988	++Position;
3989
3990	bool MadeChange = false;
3991	while (Position != CurDAG->allnodes_begin()) {
3992	SDNode N = &--Position;
3993	// Skip dead nodes and any non-machine opcodes.
3994	if (N->use_empty() \|\| !N->isMachineOpcode())
3995	continue;
3996
3997	if (N->getMachineOpcode() != PPC::RLDICL)
3998	continue;
3999
4000	if (N->getConstantOperandVal(1) != 0 \|\|
4001	N->getConstantOperandVal(2) != 32)
4002	continue;
4003
4004	SDValue ISR = N->getOperand(0);
4005	if (!ISR.isMachineOpcode() \|\|
4006	ISR.getMachineOpcode() != TargetOpcode::INSERT_SUBREG)
4007	continue;
4008
4009	if (!ISR.hasOneUse())
4010	continue;
4011
4012	if (ISR.getConstantOperandVal(2) != PPC::sub_32)
4013	continue;
4014
4015	SDValue IDef = ISR.getOperand(0);
4016	if (!IDef.isMachineOpcode() \|\|
4017	IDef.getMachineOpcode() != TargetOpcode::IMPLICIT_DEF)
4018	continue;
4019
4020	// We now know that we're looking at a canonical i32 -> i64 zext. See if we
4021	// can get rid of it.
4022
4023	SDValue Op32 = ISR->getOperand(1);
4024	if (!Op32.isMachineOpcode())
4025	continue;
4026
4027	// There are some 32-bit instructions that always clear the high-order 32
4028	// bits, there are also some instructions (like AND) that we can look
4029	// through.
4030	SmallPtrSet<SDNode *, 16> ToPromote;
4031	if (!PeepholePPC64ZExtGather(Op32, ToPromote))
4032	continue;
4033
4034	// If the ToPromote set contains nodes that have uses outside of the set
4035	// (except for the original INSERT_SUBREG), then abort the transformation.
4036	bool OutsideUse = false;
4037	for (SDNode *PN : ToPromote) {
4038	for (SDNode *UN : PN->uses()) {
4039	if (!ToPromote.count(UN) && UN != ISR.getNode()) {
4040	OutsideUse = true;
4041	break;
4042	}
4043	}
4044
4045	if (OutsideUse)
4046	break;
4047	}
4048	if (OutsideUse)
4049	continue;
4050
4051	MadeChange = true;
4052
4053	// We now know that this zero extension can be removed by promoting to
4054	// nodes in ToPromote to 64-bit operations, where for operations in the
4055	// frontier of the set, we need to insert INSERT_SUBREGs for their
4056	// operands.
4057	for (SDNode *PN : ToPromote) {
4058	unsigned NewOpcode;
4059	switch (PN->getMachineOpcode()) {
4060	default:
4061	llvm_unreachable("Don't know the 64-bit variant of this instruction")::llvm::llvm_unreachable_internal("Don't know the 64-bit variant of this instruction" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn251506/lib/Target/PowerPC/PPCISelDAGToDAG.cpp" , 4061);
4062	case PPC::RLWINM: NewOpcode = PPC::RLWINM8; break;
4063	case PPC::RLWNM: NewOpcode = PPC::RLWNM8; break;
4064	case PPC::SLW: NewOpcode = PPC::SLW8; break;
4065	case PPC::SRW: NewOpcode = PPC::SRW8; break;
4066	case PPC::LI: NewOpcode = PPC::LI8; break;
4067	case PPC::LIS: NewOpcode = PPC::LIS8; break;
4068	case PPC::LHBRX: NewOpcode = PPC::LHBRX8; break;
4069	case PPC::LWBRX: NewOpcode = PPC::LWBRX8; break;
4070	case PPC::CNTLZW: NewOpcode = PPC::CNTLZW8; break;
4071	case PPC::RLWIMI: NewOpcode = PPC::RLWIMI8; break;
4072	case PPC::OR: NewOpcode = PPC::OR8; break;
4073	case PPC::SELECT_I4: NewOpcode = PPC::SELECT_I8; break;
4074	case PPC::ORI: NewOpcode = PPC::ORI8; break;
4075	case PPC::ORIS: NewOpcode = PPC::ORIS8; break;
4076	case PPC::AND: NewOpcode = PPC::AND8; break;
4077	case PPC::ANDIo: NewOpcode = PPC::ANDIo8; break;
4078	case PPC::ANDISo: NewOpcode = PPC::ANDISo8; break;
4079	}
4080
4081	// Note: During the replacement process, the nodes will be in an
4082	// inconsistent state (some instructions will have operands with values
4083	// of the wrong type). Once done, however, everything should be right
4084	// again.
4085
4086	SmallVector<SDValue, 4> Ops;
4087	for (const SDValue &V : PN->ops()) {
4088	if (!ToPromote.count(V.getNode()) && V.getValueType() == MVT::i32 &&
4089	!isa<ConstantSDNode>(V)) {
4090	SDValue ReplOpOps[] = { ISR.getOperand(0), V, ISR.getOperand(2) };
4091	SDNode *ReplOp =
4092	CurDAG->getMachineNode(TargetOpcode::INSERT_SUBREG, SDLoc(V),
4093	ISR.getNode()->getVTList(), ReplOpOps);
4094	Ops.push_back(SDValue(ReplOp, 0));
4095	} else {
4096	Ops.push_back(V);
4097	}
4098	}
4099
4100	// Because all to-be-promoted nodes only have users that are other
4101	// promoted nodes (or the original INSERT_SUBREG), we can safely replace
4102	// the i32 result value type with i64.
4103
4104	SmallVector<EVT, 2> NewVTs;
4105	SDVTList VTs = PN->getVTList();
4106	for (unsigned i = 0, ie = VTs.NumVTs; i != ie; ++i)
4107	if (VTs.VTs[i] == MVT::i32)
4108	NewVTs.push_back(MVT::i64);
4109	else
4110	NewVTs.push_back(VTs.VTs[i]);
4111
4112	DEBUG(dbgs() << "PPC64 ZExt Peephole morphing:\nOld: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "PPC64 ZExt Peephole morphing:\nOld: " ; } } while (0);
4113	DEBUG(PN->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { PN->dump(CurDAG); } } while (0);
4114
4115	CurDAG->SelectNodeTo(PN, NewOpcode, CurDAG->getVTList(NewVTs), Ops);
4116
4117	DEBUG(dbgs() << "\nNew: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\nNew: "; } } while (0);
4118	DEBUG(PN->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { PN->dump(CurDAG); } } while (0);
4119	DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\n"; } } while (0);
4120	}
4121
4122	// Now we replace the original zero extend and its associated INSERT_SUBREG
4123	// with the value feeding the INSERT_SUBREG (which has now been promoted to
4124	// return an i64).
4125
4126	DEBUG(dbgs() << "PPC64 ZExt Peephole replacing:\nOld: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "PPC64 ZExt Peephole replacing:\nOld: " ; } } while (0);
4127	DEBUG(N->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { N->dump(CurDAG); } } while (0);
4128	DEBUG(dbgs() << "\nNew: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\nNew: "; } } while (0);
4129	DEBUG(Op32.getNode()->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { Op32.getNode()->dump(CurDAG); } } while (0);
4130	DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\n"; } } while (0);
4131
4132	ReplaceUses(N, Op32.getNode());
4133	}
4134
4135	if (MadeChange)
4136	CurDAG->RemoveDeadNodes();
4137	}
4138
4139	void PPCDAGToDAGISel::PeepholePPC64() {
4140	// These optimizations are currently supported only for 64-bit SVR4.
4141	if (PPCSubTarget->isDarwin() \|\| !PPCSubTarget->isPPC64())
4142	return;
4143
4144	SelectionDAG::allnodes_iterator Position(CurDAG->getRoot().getNode());
4145	++Position;
4146
4147	while (Position != CurDAG->allnodes_begin()) {
4148	SDNode N = &--Position;
4149	// Skip dead nodes and any non-machine opcodes.
4150	if (N->use_empty() \|\| !N->isMachineOpcode())
4151	continue;
4152
4153	unsigned FirstOp;
4154	unsigned StorageOpcode = N->getMachineOpcode();
4155
4156	switch (StorageOpcode) {
4157	default: continue;
4158
4159	case PPC::LBZ:
4160	case PPC::LBZ8:
4161	case PPC::LD:
4162	case PPC::LFD:
4163	case PPC::LFS:
4164	case PPC::LHA:
4165	case PPC::LHA8:
4166	case PPC::LHZ:
4167	case PPC::LHZ8:
4168	case PPC::LWA:
4169	case PPC::LWZ:
4170	case PPC::LWZ8:
4171	FirstOp = 0;
4172	break;
4173
4174	case PPC::STB:
4175	case PPC::STB8:
4176	case PPC::STD:
4177	case PPC::STFD:
4178	case PPC::STFS:
4179	case PPC::STH:
4180	case PPC::STH8:
4181	case PPC::STW:
4182	case PPC::STW8:
4183	FirstOp = 1;
4184	break;
4185	}
4186
4187	// If this is a load or store with a zero offset, we may be able to
4188	// fold an add-immediate into the memory operation.
4189	if (!isa<ConstantSDNode>(N->getOperand(FirstOp)) \|\|
4190	N->getConstantOperandVal(FirstOp) != 0)
4191	continue;
4192
4193	SDValue Base = N->getOperand(FirstOp + 1);
4194	if (!Base.isMachineOpcode())
4195	continue;
4196
4197	unsigned Flags = 0;
4198	bool ReplaceFlags = true;
4199
4200	// When the feeding operation is an add-immediate of some sort,
4201	// determine whether we need to add relocation information to the
4202	// target flags on the immediate operand when we fold it into the
4203	// load instruction.
4204	//
4205	// For something like ADDItocL, the relocation information is
4206	// inferred from the opcode; when we process it in the AsmPrinter,
4207	// we add the necessary relocation there. A load, though, can receive
4208	// relocation from various flavors of ADDIxxx, so we need to carry
4209	// the relocation information in the target flags.
4210	switch (Base.getMachineOpcode()) {
4211	default: continue;
4212
4213	case PPC::ADDI8:
4214	case PPC::ADDI:
4215	// In some cases (such as TLS) the relocation information
4216	// is already in place on the operand, so copying the operand
4217	// is sufficient.
4218	ReplaceFlags = false;
4219	// For these cases, the immediate may not be divisible by 4, in
4220	// which case the fold is illegal for DS-form instructions. (The
4221	// other cases provide aligned addresses and are always safe.)
4222	if ((StorageOpcode == PPC::LWA \|\|
4223	StorageOpcode == PPC::LD \|\|
4224	StorageOpcode == PPC::STD) &&
4225	(!isa<ConstantSDNode>(Base.getOperand(1)) \|\|
4226	Base.getConstantOperandVal(1) % 4 != 0))
4227	continue;
4228	break;
4229	case PPC::ADDIdtprelL:
4230	Flags = PPCII::MO_DTPREL_LO;
4231	break;
4232	case PPC::ADDItlsldL:
4233	Flags = PPCII::MO_TLSLD_LO;
4234	break;
4235	case PPC::ADDItocL:
4236	Flags = PPCII::MO_TOC_LO;
4237	break;
4238	}
4239
4240	// We found an opportunity. Reverse the operands from the add
4241	// immediate and substitute them into the load or store. If
4242	// needed, update the target flags for the immediate operand to
4243	// reflect the necessary relocation information.
4244	DEBUG(dbgs() << "Folding add-immediate into mem-op:\nBase: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "Folding add-immediate into mem-op:\nBase: " ; } } while (0);
4245	DEBUG(Base->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { Base->dump(CurDAG); } } while (0);
4246	DEBUG(dbgs() << "\nN: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\nN: "; } } while (0);
4247	DEBUG(N->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { N->dump(CurDAG); } } while (0);
4248	DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "\n"; } } while (0);
4249
4250	SDValue ImmOpnd = Base.getOperand(1);
4251
4252	// If the relocation information isn't already present on the
4253	// immediate operand, add it now.
4254	if (ReplaceFlags) {
4255	if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(ImmOpnd)) {
4256	SDLoc dl(GA);
4257	const GlobalValue *GV = GA->getGlobal();
4258	// We can't perform this optimization for data whose alignment
4259	// is insufficient for the instruction encoding.
4260	if (GV->getAlignment() < 4 &&
4261	(StorageOpcode == PPC::LD \|\| StorageOpcode == PPC::STD \|\|
4262	StorageOpcode == PPC::LWA)) {
4263	DEBUG(dbgs() << "Rejected this candidate for alignment.\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("ppc-codegen")) { dbgs() << "Rejected this candidate for alignment.\n\n" ; } } while (0);
4264	continue;
4265	}
4266	ImmOpnd = CurDAG->getTargetGlobalAddress(GV, dl, MVT::i64, 0, Flags);
4267	} else if (ConstantPoolSDNode *CP =
4268	dyn_cast<ConstantPoolSDNode>(ImmOpnd)) {
4269	const Constant *C = CP->getConstVal();
4270	ImmOpnd = CurDAG->getTargetConstantPool(C, MVT::i64,
4271	CP->getAlignment(),
4272	0, Flags);
4273	}
4274	}
4275
4276	if (FirstOp == 1) // Store
4277	(void)CurDAG->UpdateNodeOperands(N, N->getOperand(0), ImmOpnd,
4278	Base.getOperand(0), N->getOperand(3));
4279	else // Load
4280	(void)CurDAG->UpdateNodeOperands(N, ImmOpnd, Base.getOperand(0),
4281	N->getOperand(2));
4282
4283	// The add-immediate may now be dead, in which case remove it.
4284	if (Base.getNode()->use_empty())
4285	CurDAG->RemoveDeadNode(Base.getNode());
4286	}
4287	}
4288
4289
4290	/// createPPCISelDag - This pass converts a legalized DAG into a
4291	/// PowerPC-specific DAG, ready for instruction scheduling.
4292	///
4293	FunctionPass *llvm::createPPCISelDag(PPCTargetMachine &TM) {
4294	return new PPCDAGToDAGISel(TM);
4295	}
4296
4297	static void initializePassOnce(PassRegistry &Registry) {
4298	const char *Name = "PowerPC DAG->DAG Pattern Instruction Selection";
4299	PassInfo *PI = new PassInfo(Name, "ppc-codegen", &SelectionDAGISel::ID,
4300	nullptr, false, false);
4301	Registry.registerPass(*PI, true);
4302	}
4303
4304	void llvm::initializePPCDAGToDAGISelPass(PassRegistry &Registry) {
4305	CALL_ONCE_INITIALIZATION(initializePassOnce)static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized, 1, 0); if (old_val == 0) { initializePassOnce(Registry); sys::MemoryFence(); ; ; initialized = 2; ; } else { sys::cas_flag tmp = initialized; sys::MemoryFence (); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ;;
4306	}
4307