blob: 24efdf1456c6c186edd6c9fe968d57b240886d90 [file] [log] [blame]
Vikram S. Advea1d14f32001-10-10 20:50:43 +00001// $Id$ -*-c++-*-
2//***************************************************************************
3// File:
4// InstrSelectionSupport.h
5//
6// Purpose:
7// Target-independent instruction selection code.
8// See SparcInstrSelection.cpp for usage.
9//
10// History:
11// 10/10/01 - Vikram Adve - Created
12//**************************************************************************/
13
14#include "llvm/CodeGen/InstrSelectionSupport.h"
15#include "llvm/CodeGen/InstrSelection.h"
16#include "llvm/CodeGen/MachineInstr.h"
Chris Lattnerfb3b1ec2002-02-03 07:39:06 +000017#include "llvm/CodeGen/MachineCodeForInstruction.h"
18#include "llvm/CodeGen/MachineCodeForMethod.h"
19#include "llvm/CodeGen/InstrForest.h"
Vikram S. Advea1d14f32001-10-10 20:50:43 +000020#include "llvm/Target/TargetMachine.h"
21#include "llvm/Target/MachineRegInfo.h"
Chris Lattnere9bb2df2001-12-03 22:26:30 +000022#include "llvm/ConstantVals.h"
Chris Lattner2fbfdcf2002-04-07 20:49:59 +000023#include "llvm/Function.h"
Vikram S. Adve94e40ef2001-10-28 21:46:23 +000024#include "llvm/BasicBlock.h"
Vikram S. Advea1d14f32001-10-10 20:50:43 +000025#include "llvm/Type.h"
26#include "llvm/iMemory.h"
Chris Lattner697954c2002-01-20 22:54:45 +000027using std::vector;
Vikram S. Advea1d14f32001-10-10 20:50:43 +000028
29//*************************** Local Functions ******************************/
30
Vikram S. Advea1d14f32001-10-10 20:50:43 +000031
Vikram S. Adve6d353262001-10-17 23:57:50 +000032static TmpInstruction*
Chris Lattner2fbfdcf2002-04-07 20:49:59 +000033InsertCodeToLoadConstant(Function *F,
Vikram S. Adve42f63202002-03-18 03:33:43 +000034 Value* opValue,
Vikram S. Adve6d353262001-10-17 23:57:50 +000035 Instruction* vmInstr,
36 vector<MachineInstr*>& loadConstVec,
37 TargetMachine& target)
Vikram S. Advea1d14f32001-10-10 20:50:43 +000038{
Vikram S. Adve6d353262001-10-17 23:57:50 +000039 vector<TmpInstruction*> tempVec;
Vikram S. Advea1d14f32001-10-10 20:50:43 +000040
Vikram S. Adve6d353262001-10-17 23:57:50 +000041 // Create a tmp virtual register to hold the constant.
Chris Lattnerfb3b1ec2002-02-03 07:39:06 +000042 TmpInstruction* tmpReg = new TmpInstruction(opValue);
43 MachineCodeForInstruction &MCFI = MachineCodeForInstruction::get(vmInstr);
44 MCFI.addTemp(tmpReg);
Vikram S. Advea1d14f32001-10-10 20:50:43 +000045
Chris Lattner2fbfdcf2002-04-07 20:49:59 +000046 target.getInstrInfo().CreateCodeToLoadConst(F, opValue, tmpReg,
Vikram S. Adve6d353262001-10-17 23:57:50 +000047 loadConstVec, tempVec);
48
49 // Register the new tmp values created for this m/c instruction sequence
50 for (unsigned i=0; i < tempVec.size(); i++)
Chris Lattnerfb3b1ec2002-02-03 07:39:06 +000051 MCFI.addTemp(tempVec[i]);
Vikram S. Adve6d353262001-10-17 23:57:50 +000052
53 // Record the mapping from the tmp VM instruction to machine instruction.
54 // Do this for all machine instructions that were not mapped to any
55 // other temp values created by
56 // tmpReg->addMachineInstruction(loadConstVec.back());
57
58 return tmpReg;
Vikram S. Advea1d14f32001-10-10 20:50:43 +000059}
60
61
Vikram S. Adve6d353262001-10-17 23:57:50 +000062//---------------------------------------------------------------------------
63// Function GetConstantValueAsSignedInt
64//
65// Convenience function to get the value of an integer constant, for an
66// appropriate integer or non-integer type that can be held in an integer.
67// The type of the argument must be the following:
68// Signed or unsigned integer
69// Boolean
70// Pointer
71//
72// isValidConstant is set to true if a valid constant was found.
73//---------------------------------------------------------------------------
74
75int64_t
76GetConstantValueAsSignedInt(const Value *V,
77 bool &isValidConstant)
Vikram S. Advea1d14f32001-10-10 20:50:43 +000078{
Chris Lattnere9bb2df2001-12-03 22:26:30 +000079 if (!isa<Constant>(V))
Vikram S. Advea1d14f32001-10-10 20:50:43 +000080 {
Vikram S. Adve6d353262001-10-17 23:57:50 +000081 isValidConstant = false;
82 return 0;
Vikram S. Advea1d14f32001-10-10 20:50:43 +000083 }
84
Vikram S. Adve6d353262001-10-17 23:57:50 +000085 isValidConstant = true;
86
87 if (V->getType() == Type::BoolTy)
Chris Lattnere9bb2df2001-12-03 22:26:30 +000088 return (int64_t) cast<ConstantBool>(V)->getValue();
Vikram S. Adve6d353262001-10-17 23:57:50 +000089
90 if (V->getType()->isIntegral())
91 {
92 if (V->getType()->isSigned())
Chris Lattnere9bb2df2001-12-03 22:26:30 +000093 return cast<ConstantSInt>(V)->getValue();
Vikram S. Adve6d353262001-10-17 23:57:50 +000094
95 assert(V->getType()->isUnsigned());
Chris Lattnere9bb2df2001-12-03 22:26:30 +000096 uint64_t Val = cast<ConstantUInt>(V)->getValue();
Vikram S. Adve6d353262001-10-17 23:57:50 +000097 if (Val < INT64_MAX) // then safe to cast to signed
98 return (int64_t)Val;
99 }
Vikram S. Adve17927792002-03-31 18:56:51 +0000100
Vikram S. Adve6d353262001-10-17 23:57:50 +0000101 isValidConstant = false;
102 return 0;
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000103}
104
105
106//---------------------------------------------------------------------------
107// Function: FoldGetElemChain
108//
109// Purpose:
Vikram S. Advec941b872002-03-24 03:37:53 +0000110// Fold a chain of GetElementPtr instructions containing only
111// structure offsets into an equivalent (Pointer, IndexVector) pair.
112// Returns the pointer Value, and stores the resulting IndexVector
113// in argument chainIdxVec.
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000114//---------------------------------------------------------------------------
115
116Value*
117FoldGetElemChain(const InstructionNode* getElemInstrNode,
Vikram S. Advefa248972001-12-15 00:36:32 +0000118 vector<Value*>& chainIdxVec)
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000119{
120 MemAccessInst* getElemInst = (MemAccessInst*)
121 getElemInstrNode->getInstruction();
122
Vikram S. Adve17927792002-03-31 18:56:51 +0000123 // Return NULL if we don't fold any instructions in.
Vikram S. Advec941b872002-03-24 03:37:53 +0000124 Value* ptrVal = NULL;
Vikram S. Adve17927792002-03-31 18:56:51 +0000125
126 // The incoming index vector must be for the user of the chain.
127 // Its leading index must be [0] and we insert indices after that.
128 assert(chainIdxVec.size() > 0 &&
129 isa<ConstantUInt>(chainIdxVec.front()) &&
130 cast<ConstantUInt>(chainIdxVec.front())->getValue() == 0);
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000131
Vikram S. Advec941b872002-03-24 03:37:53 +0000132 // Now chase the chain of getElementInstr instructions, if any.
133 // Check for any array indices and stop there.
134 //
135 const InstrTreeNode* ptrChild = getElemInstrNode;
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000136 while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
137 ptrChild->getOpLabel() == GetElemPtrIdx)
138 {
139 // Child is a GetElemPtr instruction
140 getElemInst = (MemAccessInst*)
141 ((InstructionNode*) ptrChild)->getInstruction();
Vikram S. Advefa248972001-12-15 00:36:32 +0000142 const vector<Value*>& idxVec = getElemInst->copyIndices();
Vikram S. Advec941b872002-03-24 03:37:53 +0000143 bool allStructureOffsets = true;
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000144
Vikram S. Advec941b872002-03-24 03:37:53 +0000145 // If it is a struct* access, the first offset must be array index [0],
146 // and all other offsets must be structure (not array) offsets
147 if (!isa<ConstantUInt>(idxVec.front()) ||
148 cast<ConstantUInt>(idxVec.front())->getValue() != 0)
149 allStructureOffsets = false;
150
151 if (allStructureOffsets)
152 for (unsigned int i=1; i < idxVec.size(); i++)
153 if (idxVec[i]->getType() == Type::UIntTy)
154 {
155 allStructureOffsets = false;
156 break;
157 }
158
159 if (allStructureOffsets)
Vikram S. Adve17927792002-03-31 18:56:51 +0000160 { // Get pointer value out of ptrChild.
Vikram S. Advec941b872002-03-24 03:37:53 +0000161 ptrVal = getElemInst->getPointerOperand();
Vikram S. Adve17927792002-03-31 18:56:51 +0000162
163 // Insert its index vector at the start, but after the leading [0]
164 chainIdxVec.insert(chainIdxVec.begin()+1,
Vikram S. Advec941b872002-03-24 03:37:53 +0000165 idxVec.begin()+1, idxVec.end());
Vikram S. Adve17927792002-03-31 18:56:51 +0000166
167 // Mark the folded node so no code is generated for it.
Vikram S. Advec941b872002-03-24 03:37:53 +0000168 ((InstructionNode*) ptrChild)->markFoldedIntoParent();
Vikram S. Advec941b872002-03-24 03:37:53 +0000169 }
170 else // cannot fold this getElementPtr instr. or any further ones
171 break;
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000172
173 ptrChild = ptrChild->leftChild();
174 }
175
176 return ptrVal;
177}
178
179
180//------------------------------------------------------------------------
181// Function Set2OperandsFromInstr
182// Function Set3OperandsFromInstr
183//
184// For the common case of 2- and 3-operand arithmetic/logical instructions,
185// set the m/c instr. operands directly from the VM instruction's operands.
186// Check whether the first or second operand is 0 and can use a dedicated "0"
187// register.
188// Check whether the second operand should use an immediate field or register.
189// (First and third operands are never immediates for such instructions.)
190//
191// Arguments:
192// canDiscardResult: Specifies that the result operand can be discarded
193// by using the dedicated "0"
194//
195// op1position, op2position and resultPosition: Specify in which position
196// in the machine instruction the 3 operands (arg1, arg2
197// and result) should go.
198//
199// RETURN VALUE: unsigned int flags, where
200// flags & 0x01 => operand 1 is constant and needs a register
201// flags & 0x02 => operand 2 is constant and needs a register
202//------------------------------------------------------------------------
203
204void
205Set2OperandsFromInstr(MachineInstr* minstr,
206 InstructionNode* vmInstrNode,
207 const TargetMachine& target,
208 bool canDiscardResult,
209 int op1Position,
210 int resultPosition)
211{
212 Set3OperandsFromInstr(minstr, vmInstrNode, target,
213 canDiscardResult, op1Position,
214 /*op2Position*/ -1, resultPosition);
215}
216
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000217
218void
219Set3OperandsFromInstr(MachineInstr* minstr,
220 InstructionNode* vmInstrNode,
221 const TargetMachine& target,
222 bool canDiscardResult,
223 int op1Position,
224 int op2Position,
225 int resultPosition)
226{
227 assert(op1Position >= 0);
228 assert(resultPosition >= 0);
229
230 // operand 1
Vikram S. Adve42f63202002-03-18 03:33:43 +0000231 minstr->SetMachineOperandVal(op1Position, MachineOperand::MO_VirtualRegister,
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000232 vmInstrNode->leftChild()->getValue());
233
234 // operand 2 (if any)
235 if (op2Position >= 0)
Vikram S. Adve42f63202002-03-18 03:33:43 +0000236 minstr->SetMachineOperandVal(op2Position, MachineOperand::MO_VirtualRegister,
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000237 vmInstrNode->rightChild()->getValue());
238
239 // result operand: if it can be discarded, use a dead register if one exists
240 if (canDiscardResult && target.getRegInfo().getZeroRegNum() >= 0)
Vikram S. Adve42f63202002-03-18 03:33:43 +0000241 minstr->SetMachineOperandReg(resultPosition,
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000242 target.getRegInfo().getZeroRegNum());
243 else
Vikram S. Adve42f63202002-03-18 03:33:43 +0000244 minstr->SetMachineOperandVal(resultPosition,
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000245 MachineOperand::MO_VirtualRegister, vmInstrNode->getValue());
246}
247
248
249MachineOperand::MachineOperandType
250ChooseRegOrImmed(Value* val,
251 MachineOpCode opCode,
252 const TargetMachine& target,
253 bool canUseImmed,
254 unsigned int& getMachineRegNum,
255 int64_t& getImmedValue)
256{
257 MachineOperand::MachineOperandType opType =
258 MachineOperand::MO_VirtualRegister;
259 getMachineRegNum = 0;
260 getImmedValue = 0;
261
262 // Check for the common case first: argument is not constant
263 //
Chris Lattnere9bb2df2001-12-03 22:26:30 +0000264 Constant *CPV = dyn_cast<Constant>(val);
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000265 if (!CPV) return opType;
266
Chris Lattnere9bb2df2001-12-03 22:26:30 +0000267 if (ConstantBool *CPB = dyn_cast<ConstantBool>(CPV))
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000268 {
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000269 if (!CPB->getValue() && target.getRegInfo().getZeroRegNum() >= 0)
270 {
271 getMachineRegNum = target.getRegInfo().getZeroRegNum();
272 return MachineOperand::MO_MachineRegister;
273 }
274
275 getImmedValue = 1;
276 return MachineOperand::MO_SignExtendedImmed;
277 }
278
Vikram S. Advec8117452001-11-14 17:24:49 +0000279 // Otherwise it needs to be an integer or a NULL pointer
280 if (! CPV->getType()->isIntegral() &&
281 ! (CPV->getType()->isPointerType() &&
282 CPV->isNullValue()))
283 return opType;
284
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000285 // Now get the constant value and check if it fits in the IMMED field.
286 // Take advantage of the fact that the max unsigned value will rarely
287 // fit into any IMMED field and ignore that case (i.e., cast smaller
288 // unsigned constants to signed).
289 //
290 int64_t intValue;
Vikram S. Advec8117452001-11-14 17:24:49 +0000291 if (CPV->getType()->isPointerType())
292 {
293 intValue = 0;
294 }
Vikram S. Adve9e29f782001-11-14 17:55:02 +0000295 else if (CPV->getType()->isSigned())
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000296 {
Chris Lattnere9bb2df2001-12-03 22:26:30 +0000297 intValue = cast<ConstantSInt>(CPV)->getValue();
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000298 }
299 else
300 {
Chris Lattnere9bb2df2001-12-03 22:26:30 +0000301 uint64_t V = cast<ConstantUInt>(CPV)->getValue();
Vikram S. Advea1d14f32001-10-10 20:50:43 +0000302 if (V >= INT64_MAX) return opType;
303 intValue = (int64_t)V;
304 }
305
306 if (intValue == 0 && target.getRegInfo().getZeroRegNum() >= 0)
307 {
308 opType = MachineOperand::MO_MachineRegister;
309 getMachineRegNum = target.getRegInfo().getZeroRegNum();
310 }
311 else if (canUseImmed &&
312 target.getInstrInfo().constantFitsInImmedField(opCode, intValue))
313 {
314 opType = MachineOperand::MO_SignExtendedImmed;
315 getImmedValue = intValue;
316 }
317
318 return opType;
319}
320
Vikram S. Adve6d353262001-10-17 23:57:50 +0000321
322//---------------------------------------------------------------------------
323// Function: FixConstantOperandsForInstr
324//
325// Purpose:
326// Special handling for constant operands of a machine instruction
327// -- if the constant is 0, use the hardwired 0 register, if any;
328// -- if the constant fits in the IMMEDIATE field, use that field;
329// -- else create instructions to put the constant into a register, either
330// directly or by loading explicitly from the constant pool.
331//
332// In the first 2 cases, the operand of `minstr' is modified in place.
333// Returns a vector of machine instructions generated for operands that
334// fall under case 3; these must be inserted before `minstr'.
335//---------------------------------------------------------------------------
336
337vector<MachineInstr*>
338FixConstantOperandsForInstr(Instruction* vmInstr,
339 MachineInstr* minstr,
340 TargetMachine& target)
341{
342 vector<MachineInstr*> loadConstVec;
343
344 const MachineInstrDescriptor& instrDesc =
345 target.getInstrInfo().getDescriptor(minstr->getOpCode());
346
Chris Lattner2fbfdcf2002-04-07 20:49:59 +0000347 Function *F = vmInstr->getParent()->getParent();
Vikram S. Adve94e40ef2001-10-28 21:46:23 +0000348
Vikram S. Adve6d353262001-10-17 23:57:50 +0000349 for (unsigned op=0; op < minstr->getNumOperands(); op++)
350 {
351 const MachineOperand& mop = minstr->getOperand(op);
352
353 // skip the result position (for efficiency below) and any other
354 // positions already marked as not a virtual register
355 if (instrDesc.resultPos == (int) op ||
356 mop.getOperandType() != MachineOperand::MO_VirtualRegister ||
357 mop.getVRegValue() == NULL)
358 {
359 continue;
360 }
361
362 Value* opValue = mop.getVRegValue();
363 bool constantThatMustBeLoaded = false;
364
Vikram S. Adve42f63202002-03-18 03:33:43 +0000365 if (Constant *opConst = dyn_cast<Constant>(opValue))
366 {
Vikram S. Adve6d353262001-10-17 23:57:50 +0000367 unsigned int machineRegNum;
368 int64_t immedValue;
369 MachineOperand::MachineOperandType opType =
370 ChooseRegOrImmed(opValue, minstr->getOpCode(), target,
Vikram S. Adve42f63202002-03-18 03:33:43 +0000371 (target.getInstrInfo().getImmedConstantPos(minstr->getOpCode()) == (int) op),
Vikram S. Adve6d353262001-10-17 23:57:50 +0000372 machineRegNum, immedValue);
Vikram S. Adveecd58132001-11-14 18:49:45 +0000373
Vikram S. Adve6d353262001-10-17 23:57:50 +0000374 if (opType == MachineOperand::MO_MachineRegister)
Vikram S. Adve42f63202002-03-18 03:33:43 +0000375 minstr->SetMachineOperandReg(op, machineRegNum);
Vikram S. Adve6d353262001-10-17 23:57:50 +0000376 else if (opType == MachineOperand::MO_VirtualRegister)
377 constantThatMustBeLoaded = true; // load is generated below
378 else
Vikram S. Adve42f63202002-03-18 03:33:43 +0000379 minstr->SetMachineOperandConst(op, opType, immedValue);
Vikram S. Adve94e40ef2001-10-28 21:46:23 +0000380 }
381
Vikram S. Adve6d353262001-10-17 23:57:50 +0000382 if (constantThatMustBeLoaded || isa<GlobalValue>(opValue))
383 { // opValue is a constant that must be explicitly loaded into a reg.
Chris Lattner2fbfdcf2002-04-07 20:49:59 +0000384 TmpInstruction* tmpReg = InsertCodeToLoadConstant(F, opValue, vmInstr,
385 loadConstVec,
386 target);
Vikram S. Adve42f63202002-03-18 03:33:43 +0000387 minstr->SetMachineOperandVal(op, MachineOperand::MO_VirtualRegister,
388 tmpReg);
Vikram S. Adve6d353262001-10-17 23:57:50 +0000389 }
390 }
391
392 //
393 // Also, check for implicit operands used (not those defined) by the
394 // machine instruction. These include:
395 // -- arguments to a Call
396 // -- return value of a Return
397 // Any such operand that is a constant value needs to be fixed also.
398 // The current instructions with implicit refs (viz., Call and Return)
399 // have no immediate fields, so the constant always needs to be loaded
400 // into a register.
401 //
402 for (unsigned i=0, N=minstr->getNumImplicitRefs(); i < N; ++i)
Chris Lattnere9bb2df2001-12-03 22:26:30 +0000403 if (isa<Constant>(minstr->getImplicitRef(i)) ||
Vikram S. Adve6d353262001-10-17 23:57:50 +0000404 isa<GlobalValue>(minstr->getImplicitRef(i)))
405 {
Vikram S. Adve94e40ef2001-10-28 21:46:23 +0000406 Value* oldVal = minstr->getImplicitRef(i);
Vikram S. Adve6d353262001-10-17 23:57:50 +0000407 TmpInstruction* tmpReg =
Chris Lattner2fbfdcf2002-04-07 20:49:59 +0000408 InsertCodeToLoadConstant(F, oldVal, vmInstr, loadConstVec, target);
Vikram S. Adve6d353262001-10-17 23:57:50 +0000409 minstr->setImplicitRef(i, tmpReg);
410 }
411
412 return loadConstVec;
413}
414
415