]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
1 //===-- FunctionLoweringInfo.cpp ------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements routines for translating functions from LLVM IR into
13 //===----------------------------------------------------------------------===//
15 #include "llvm/CodeGen/FunctionLoweringInfo.h"
16 #include "llvm/ADT/PostOrderIterator.h"
17 #include "llvm/CodeGen/Analysis.h"
18 #include "llvm/CodeGen/MachineFrameInfo.h"
19 #include "llvm/CodeGen/MachineFunction.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineModuleInfo.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/DebugInfo.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/Function.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/IntrinsicInst.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/ErrorHandling.h"
33 #include "llvm/Support/MathExtras.h"
34 #include "llvm/Target/TargetFrameLowering.h"
35 #include "llvm/Target/TargetInstrInfo.h"
36 #include "llvm/Target/TargetLowering.h"
37 #include "llvm/Target/TargetOptions.h"
38 #include "llvm/Target/TargetRegisterInfo.h"
39 #include "llvm/Target/TargetSubtargetInfo.h"
43 #define DEBUG_TYPE "function-lowering-info"
45 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
46 /// PHI nodes or outside of the basic block that defines it, or used by a
47 /// switch or atomic instruction, which may expand to multiple basic blocks.
48 static bool isUsedOutsideOfDefiningBlock(const Instruction
*I
) {
49 if (I
->use_empty()) return false;
50 if (isa
<PHINode
>(I
)) return true;
51 const BasicBlock
*BB
= I
->getParent();
52 for (const User
*U
: I
->users())
53 if (cast
<Instruction
>(U
)->getParent() != BB
|| isa
<PHINode
>(U
))
59 static ISD::NodeType
getPreferredExtendForValue(const Value
*V
) {
60 // For the users of the source value being used for compare instruction, if
61 // the number of signed predicate is greater than unsigned predicate, we
62 // prefer to use SIGN_EXTEND.
64 // With this optimization, we would be able to reduce some redundant sign or
65 // zero extension instruction, and eventually more machine CSE opportunities
67 ISD::NodeType ExtendKind
= ISD::ANY_EXTEND
;
68 unsigned NumOfSigned
= 0, NumOfUnsigned
= 0;
69 for (const User
*U
: V
->users()) {
70 if (const auto *CI
= dyn_cast
<CmpInst
>(U
)) {
71 NumOfSigned
+= CI
->isSigned();
72 NumOfUnsigned
+= CI
->isUnsigned();
75 if (NumOfSigned
> NumOfUnsigned
)
76 ExtendKind
= ISD::SIGN_EXTEND
;
81 void FunctionLoweringInfo::set(const Function
&fn
, MachineFunction
&mf
,
83 const TargetLowering
*TLI
= TM
.getSubtargetImpl()->getTargetLowering();
87 RegInfo
= &MF
->getRegInfo();
89 // Check whether the function can return without sret-demotion.
90 SmallVector
<ISD::OutputArg
, 4> Outs
;
91 GetReturnInfo(Fn
->getReturnType(), Fn
->getAttributes(), Outs
, *TLI
);
92 CanLowerReturn
= TLI
->CanLowerReturn(Fn
->getCallingConv(), *MF
,
94 Outs
, Fn
->getContext());
96 // Initialize the mapping of values to registers. This is only set up for
97 // instruction values that are used outside of the block that defines
99 Function::const_iterator BB
= Fn
->begin(), EB
= Fn
->end();
100 for (; BB
!= EB
; ++BB
)
101 for (BasicBlock::const_iterator I
= BB
->begin(), E
= BB
->end();
103 if (const AllocaInst
*AI
= dyn_cast
<AllocaInst
>(I
)) {
104 // Static allocas can be folded into the initial stack frame adjustment.
105 if (AI
->isStaticAlloca()) {
106 const ConstantInt
*CUI
= cast
<ConstantInt
>(AI
->getArraySize());
107 Type
*Ty
= AI
->getAllocatedType();
108 uint64_t TySize
= TLI
->getDataLayout()->getTypeAllocSize(Ty
);
110 std::max((unsigned)TLI
->getDataLayout()->getPrefTypeAlignment(Ty
),
113 TySize
*= CUI
->getZExtValue(); // Get total allocated size.
114 if (TySize
== 0) TySize
= 1; // Don't create zero-sized stack objects.
116 StaticAllocaMap
[AI
] =
117 MF
->getFrameInfo()->CreateStackObject(TySize
, Align
, false, AI
);
120 unsigned Align
= std::max(
121 (unsigned)TLI
->getDataLayout()->getPrefTypeAlignment(
122 AI
->getAllocatedType()),
124 unsigned StackAlign
=
125 TM
.getSubtargetImpl()->getFrameLowering()->getStackAlignment();
126 if (Align
<= StackAlign
)
128 // Inform the Frame Information that we have variable-sized objects.
129 MF
->getFrameInfo()->CreateVariableSizedObject(Align
? Align
: 1, AI
);
133 // Look for inline asm that clobbers the SP register.
134 if (isa
<CallInst
>(I
) || isa
<InvokeInst
>(I
)) {
135 ImmutableCallSite
CS(I
);
136 if (isa
<InlineAsm
>(CS
.getCalledValue())) {
137 unsigned SP
= TLI
->getStackPointerRegisterToSaveRestore();
138 std::vector
<TargetLowering::AsmOperandInfo
> Ops
=
139 TLI
->ParseConstraints(CS
);
140 for (size_t I
= 0, E
= Ops
.size(); I
!= E
; ++I
) {
141 TargetLowering::AsmOperandInfo
&Op
= Ops
[I
];
142 if (Op
.Type
== InlineAsm::isClobber
) {
143 // Clobbers don't have SDValue operands, hence SDValue().
144 TLI
->ComputeConstraintToUse(Op
, SDValue(), DAG
);
145 std::pair
<unsigned, const TargetRegisterClass
*> PhysReg
=
146 TLI
->getRegForInlineAsmConstraint(Op
.ConstraintCode
,
148 if (PhysReg
.first
== SP
)
149 MF
->getFrameInfo()->setHasInlineAsmWithSPAdjust(true);
155 // Look for calls to the @llvm.va_start intrinsic. We can omit some
156 // prologue boilerplate for variadic functions that don't examine their
158 if (const auto *II
= dyn_cast
<IntrinsicInst
>(I
)) {
159 if (II
->getIntrinsicID() == Intrinsic::vastart
)
160 MF
->getFrameInfo()->setHasVAStart(true);
163 // If we have a musttail call in a variadic funciton, we need to ensure we
164 // forward implicit register parameters.
165 if (const auto *CI
= dyn_cast
<CallInst
>(I
)) {
166 if (CI
->isMustTailCall() && Fn
->isVarArg())
167 MF
->getFrameInfo()->setHasMustTailInVarArgFunc(true);
170 // Mark values used outside their block as exported, by allocating
171 // a virtual register for them.
172 if (isUsedOutsideOfDefiningBlock(I
))
173 if (!isa
<AllocaInst
>(I
) ||
174 !StaticAllocaMap
.count(cast
<AllocaInst
>(I
)))
175 InitializeRegForValue(I
);
177 // Collect llvm.dbg.declare information. This is done now instead of
178 // during the initial isel pass through the IR so that it is done
179 // in a predictable order.
180 if (const DbgDeclareInst
*DI
= dyn_cast
<DbgDeclareInst
>(I
)) {
181 MachineModuleInfo
&MMI
= MF
->getMMI();
182 DIVariable
DIVar(DI
->getVariable());
183 assert((!DIVar
|| DIVar
.isVariable()) &&
184 "Variable in DbgDeclareInst should be either null or a DIVariable.");
185 if (MMI
.hasDebugInfo() &&
187 !DI
->getDebugLoc().isUnknown()) {
188 // Don't handle byval struct arguments or VLAs, for example.
189 // Non-byval arguments are handled here (they refer to the stack
190 // temporary alloca at this point).
191 const Value
*Address
= DI
->getAddress();
193 if (const BitCastInst
*BCI
= dyn_cast
<BitCastInst
>(Address
))
194 Address
= BCI
->getOperand(0);
195 if (const AllocaInst
*AI
= dyn_cast
<AllocaInst
>(Address
)) {
196 DenseMap
<const AllocaInst
*, int>::iterator SI
=
197 StaticAllocaMap
.find(AI
);
198 if (SI
!= StaticAllocaMap
.end()) { // Check for VLAs.
200 MMI
.setVariableDbgInfo(DI
->getVariable(),
201 FI
, DI
->getDebugLoc());
208 // Decide the preferred extend type for a value.
209 PreferredExtendType
[I
] = getPreferredExtendForValue(I
);
212 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This
213 // also creates the initial PHI MachineInstrs, though none of the input
214 // operands are populated.
215 for (BB
= Fn
->begin(); BB
!= EB
; ++BB
) {
216 MachineBasicBlock
*MBB
= mf
.CreateMachineBasicBlock(BB
);
220 // Transfer the address-taken flag. This is necessary because there could
221 // be multiple MachineBasicBlocks corresponding to one BasicBlock, and only
222 // the first one should be marked.
223 if (BB
->hasAddressTaken())
224 MBB
->setHasAddressTaken();
226 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
228 for (BasicBlock::const_iterator I
= BB
->begin();
229 const PHINode
*PN
= dyn_cast
<PHINode
>(I
); ++I
) {
230 if (PN
->use_empty()) continue;
233 if (PN
->getType()->isEmptyTy())
236 DebugLoc DL
= PN
->getDebugLoc();
237 unsigned PHIReg
= ValueMap
[PN
];
238 assert(PHIReg
&& "PHI node does not have an assigned virtual register!");
240 SmallVector
<EVT
, 4> ValueVTs
;
241 ComputeValueVTs(*TLI
, PN
->getType(), ValueVTs
);
242 for (unsigned vti
= 0, vte
= ValueVTs
.size(); vti
!= vte
; ++vti
) {
243 EVT VT
= ValueVTs
[vti
];
244 unsigned NumRegisters
= TLI
->getNumRegisters(Fn
->getContext(), VT
);
245 const TargetInstrInfo
*TII
= MF
->getSubtarget().getInstrInfo();
246 for (unsigned i
= 0; i
!= NumRegisters
; ++i
)
247 BuildMI(MBB
, DL
, TII
->get(TargetOpcode::PHI
), PHIReg
+ i
);
248 PHIReg
+= NumRegisters
;
253 // Mark landing pad blocks.
254 for (BB
= Fn
->begin(); BB
!= EB
; ++BB
)
255 if (const InvokeInst
*Invoke
= dyn_cast
<InvokeInst
>(BB
->getTerminator()))
256 MBBMap
[Invoke
->getSuccessor(1)]->setIsLandingPad();
259 /// clear - Clear out all the function-specific state. This returns this
260 /// FunctionLoweringInfo to an empty state, ready to be used for a
261 /// different function.
262 void FunctionLoweringInfo::clear() {
263 assert(CatchInfoFound
.size() == CatchInfoLost
.size() &&
264 "Not all catch info was assigned to a landing pad!");
268 StaticAllocaMap
.clear();
270 CatchInfoLost
.clear();
271 CatchInfoFound
.clear();
273 LiveOutRegInfo
.clear();
275 ArgDbgValues
.clear();
276 ByValArgFrameIndexMap
.clear();
278 PreferredExtendType
.clear();
281 /// CreateReg - Allocate a single virtual register for the given type.
282 unsigned FunctionLoweringInfo::CreateReg(MVT VT
) {
283 return RegInfo
->createVirtualRegister(
284 TM
.getSubtargetImpl()->getTargetLowering()->getRegClassFor(VT
));
287 /// CreateRegs - Allocate the appropriate number of virtual registers of
288 /// the correctly promoted or expanded types. Assign these registers
289 /// consecutive vreg numbers and return the first assigned number.
291 /// In the case that the given value has struct or array type, this function
292 /// will assign registers for each member or element.
294 unsigned FunctionLoweringInfo::CreateRegs(Type
*Ty
) {
295 const TargetLowering
*TLI
= TM
.getSubtargetImpl()->getTargetLowering();
297 SmallVector
<EVT
, 4> ValueVTs
;
298 ComputeValueVTs(*TLI
, Ty
, ValueVTs
);
300 unsigned FirstReg
= 0;
301 for (unsigned Value
= 0, e
= ValueVTs
.size(); Value
!= e
; ++Value
) {
302 EVT ValueVT
= ValueVTs
[Value
];
303 MVT RegisterVT
= TLI
->getRegisterType(Ty
->getContext(), ValueVT
);
305 unsigned NumRegs
= TLI
->getNumRegisters(Ty
->getContext(), ValueVT
);
306 for (unsigned i
= 0; i
!= NumRegs
; ++i
) {
307 unsigned R
= CreateReg(RegisterVT
);
308 if (!FirstReg
) FirstReg
= R
;
314 /// GetLiveOutRegInfo - Gets LiveOutInfo for a register, returning NULL if the
315 /// register is a PHI destination and the PHI's LiveOutInfo is not valid. If
316 /// the register's LiveOutInfo is for a smaller bit width, it is extended to
317 /// the larger bit width by zero extension. The bit width must be no smaller
318 /// than the LiveOutInfo's existing bit width.
319 const FunctionLoweringInfo::LiveOutInfo
*
320 FunctionLoweringInfo::GetLiveOutRegInfo(unsigned Reg
, unsigned BitWidth
) {
321 if (!LiveOutRegInfo
.inBounds(Reg
))
324 LiveOutInfo
*LOI
= &LiveOutRegInfo
[Reg
];
328 if (BitWidth
> LOI
->KnownZero
.getBitWidth()) {
329 LOI
->NumSignBits
= 1;
330 LOI
->KnownZero
= LOI
->KnownZero
.zextOrTrunc(BitWidth
);
331 LOI
->KnownOne
= LOI
->KnownOne
.zextOrTrunc(BitWidth
);
337 /// ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI's destination
338 /// register based on the LiveOutInfo of its operands.
339 void FunctionLoweringInfo::ComputePHILiveOutRegInfo(const PHINode
*PN
) {
340 Type
*Ty
= PN
->getType();
341 if (!Ty
->isIntegerTy() || Ty
->isVectorTy())
344 const TargetLowering
*TLI
= TM
.getSubtargetImpl()->getTargetLowering();
346 SmallVector
<EVT
, 1> ValueVTs
;
347 ComputeValueVTs(*TLI
, Ty
, ValueVTs
);
348 assert(ValueVTs
.size() == 1 &&
349 "PHIs with non-vector integer types should have a single VT.");
350 EVT IntVT
= ValueVTs
[0];
352 if (TLI
->getNumRegisters(PN
->getContext(), IntVT
) != 1)
354 IntVT
= TLI
->getTypeToTransformTo(PN
->getContext(), IntVT
);
355 unsigned BitWidth
= IntVT
.getSizeInBits();
357 unsigned DestReg
= ValueMap
[PN
];
358 if (!TargetRegisterInfo::isVirtualRegister(DestReg
))
360 LiveOutRegInfo
.grow(DestReg
);
361 LiveOutInfo
&DestLOI
= LiveOutRegInfo
[DestReg
];
363 Value
*V
= PN
->getIncomingValue(0);
364 if (isa
<UndefValue
>(V
) || isa
<ConstantExpr
>(V
)) {
365 DestLOI
.NumSignBits
= 1;
366 APInt
Zero(BitWidth
, 0);
367 DestLOI
.KnownZero
= Zero
;
368 DestLOI
.KnownOne
= Zero
;
372 if (ConstantInt
*CI
= dyn_cast
<ConstantInt
>(V
)) {
373 APInt Val
= CI
->getValue().zextOrTrunc(BitWidth
);
374 DestLOI
.NumSignBits
= Val
.getNumSignBits();
375 DestLOI
.KnownZero
= ~Val
;
376 DestLOI
.KnownOne
= Val
;
378 assert(ValueMap
.count(V
) && "V should have been placed in ValueMap when its"
379 "CopyToReg node was created.");
380 unsigned SrcReg
= ValueMap
[V
];
381 if (!TargetRegisterInfo::isVirtualRegister(SrcReg
)) {
382 DestLOI
.IsValid
= false;
385 const LiveOutInfo
*SrcLOI
= GetLiveOutRegInfo(SrcReg
, BitWidth
);
387 DestLOI
.IsValid
= false;
393 assert(DestLOI
.KnownZero
.getBitWidth() == BitWidth
&&
394 DestLOI
.KnownOne
.getBitWidth() == BitWidth
&&
395 "Masks should have the same bit width as the type.");
397 for (unsigned i
= 1, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
) {
398 Value
*V
= PN
->getIncomingValue(i
);
399 if (isa
<UndefValue
>(V
) || isa
<ConstantExpr
>(V
)) {
400 DestLOI
.NumSignBits
= 1;
401 APInt
Zero(BitWidth
, 0);
402 DestLOI
.KnownZero
= Zero
;
403 DestLOI
.KnownOne
= Zero
;
407 if (ConstantInt
*CI
= dyn_cast
<ConstantInt
>(V
)) {
408 APInt Val
= CI
->getValue().zextOrTrunc(BitWidth
);
409 DestLOI
.NumSignBits
= std::min(DestLOI
.NumSignBits
, Val
.getNumSignBits());
410 DestLOI
.KnownZero
&= ~Val
;
411 DestLOI
.KnownOne
&= Val
;
415 assert(ValueMap
.count(V
) && "V should have been placed in ValueMap when "
416 "its CopyToReg node was created.");
417 unsigned SrcReg
= ValueMap
[V
];
418 if (!TargetRegisterInfo::isVirtualRegister(SrcReg
)) {
419 DestLOI
.IsValid
= false;
422 const LiveOutInfo
*SrcLOI
= GetLiveOutRegInfo(SrcReg
, BitWidth
);
424 DestLOI
.IsValid
= false;
427 DestLOI
.NumSignBits
= std::min(DestLOI
.NumSignBits
, SrcLOI
->NumSignBits
);
428 DestLOI
.KnownZero
&= SrcLOI
->KnownZero
;
429 DestLOI
.KnownOne
&= SrcLOI
->KnownOne
;
433 /// setArgumentFrameIndex - Record frame index for the byval
434 /// argument. This overrides previous frame index entry for this argument,
436 void FunctionLoweringInfo::setArgumentFrameIndex(const Argument
*A
,
438 ByValArgFrameIndexMap
[A
] = FI
;
441 /// getArgumentFrameIndex - Get frame index for the byval argument.
442 /// If the argument does not have any assigned frame index then 0 is
444 int FunctionLoweringInfo::getArgumentFrameIndex(const Argument
*A
) {
445 DenseMap
<const Argument
*, int>::iterator I
=
446 ByValArgFrameIndexMap
.find(A
);
447 if (I
!= ByValArgFrameIndexMap
.end())
449 DEBUG(dbgs() << "Argument does not have assigned frame index!\n");
453 /// ComputeUsesVAFloatArgument - Determine if any floating-point values are
454 /// being passed to this variadic function, and set the MachineModuleInfo's
455 /// usesVAFloatArgument flag if so. This flag is used to emit an undefined
456 /// reference to _fltused on Windows, which will link in MSVCRT's
457 /// floating-point support.
458 void llvm::ComputeUsesVAFloatArgument(const CallInst
&I
,
459 MachineModuleInfo
*MMI
)
461 FunctionType
*FT
= cast
<FunctionType
>(
462 I
.getCalledValue()->getType()->getContainedType(0));
463 if (FT
->isVarArg() && !MMI
->usesVAFloatArgument()) {
464 for (unsigned i
= 0, e
= I
.getNumArgOperands(); i
!= e
; ++i
) {
465 Type
* T
= I
.getArgOperand(i
)->getType();
466 for (po_iterator
<Type
*> i
= po_begin(T
), e
= po_end(T
);
468 if (i
->isFloatingPointTy()) {
469 MMI
->setUsesVAFloatArgument(true);
477 /// AddCatchInfo - Extract the personality and type infos from an eh.selector
478 /// call, and add them to the specified machine basic block.
479 void llvm::AddCatchInfo(const CallInst
&I
, MachineModuleInfo
*MMI
,
480 MachineBasicBlock
*MBB
) {
481 // Inform the MachineModuleInfo of the personality for this landing pad.
482 const ConstantExpr
*CE
= cast
<ConstantExpr
>(I
.getArgOperand(1));
483 assert(CE
->getOpcode() == Instruction::BitCast
&&
484 isa
<Function
>(CE
->getOperand(0)) &&
485 "Personality should be a function");
486 MMI
->addPersonality(MBB
, cast
<Function
>(CE
->getOperand(0)));
488 // Gather all the type infos for this landing pad and pass them along to
489 // MachineModuleInfo.
490 std::vector
<const GlobalVariable
*> TyInfo
;
491 unsigned N
= I
.getNumArgOperands();
493 for (unsigned i
= N
- 1; i
> 1; --i
) {
494 if (const ConstantInt
*CI
= dyn_cast
<ConstantInt
>(I
.getArgOperand(i
))) {
495 unsigned FilterLength
= CI
->getZExtValue();
496 unsigned FirstCatch
= i
+ FilterLength
+ !FilterLength
;
497 assert(FirstCatch
<= N
&& "Invalid filter length");
499 if (FirstCatch
< N
) {
500 TyInfo
.reserve(N
- FirstCatch
);
501 for (unsigned j
= FirstCatch
; j
< N
; ++j
)
502 TyInfo
.push_back(ExtractTypeInfo(I
.getArgOperand(j
)));
503 MMI
->addCatchTypeInfo(MBB
, TyInfo
);
509 MMI
->addCleanup(MBB
);
512 TyInfo
.reserve(FilterLength
- 1);
513 for (unsigned j
= i
+ 1; j
< FirstCatch
; ++j
)
514 TyInfo
.push_back(ExtractTypeInfo(I
.getArgOperand(j
)));
515 MMI
->addFilterTypeInfo(MBB
, TyInfo
);
524 TyInfo
.reserve(N
- 2);
525 for (unsigned j
= 2; j
< N
; ++j
)
526 TyInfo
.push_back(ExtractTypeInfo(I
.getArgOperand(j
)));
527 MMI
->addCatchTypeInfo(MBB
, TyInfo
);
531 /// AddLandingPadInfo - Extract the exception handling information from the
532 /// landingpad instruction and add them to the specified machine module info.
533 void llvm::AddLandingPadInfo(const LandingPadInst
&I
, MachineModuleInfo
&MMI
,
534 MachineBasicBlock
*MBB
) {
535 MMI
.addPersonality(MBB
,
536 cast
<Function
>(I
.getPersonalityFn()->stripPointerCasts()));
541 // FIXME: New EH - Add the clauses in reverse order. This isn't 100% correct,
542 // but we need to do it this way because of how the DWARF EH emitter
543 // processes the clauses.
544 for (unsigned i
= I
.getNumClauses(); i
!= 0; --i
) {
545 Value
*Val
= I
.getClause(i
- 1);
546 if (I
.isCatch(i
- 1)) {
547 MMI
.addCatchTypeInfo(MBB
,
548 dyn_cast
<GlobalVariable
>(Val
->stripPointerCasts()));
550 // Add filters in a list.
551 Constant
*CVal
= cast
<Constant
>(Val
);
552 SmallVector
<const GlobalVariable
*, 4> FilterList
;
553 for (User::op_iterator
554 II
= CVal
->op_begin(), IE
= CVal
->op_end(); II
!= IE
; ++II
)
555 FilterList
.push_back(cast
<GlobalVariable
>((*II
)->stripPointerCasts()));
557 MMI
.addFilterTypeInfo(MBB
, FilterList
);