FunctionLoweringInfo.cpp revision 10c6d12a9fd4dab411091f64db4db69670b88850 
1//===-- FunctionLoweringInfo.cpp ------------------------------------------===//
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 implements routines for translating functions from LLVM IR into
11// Machine IR.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "function-lowering-info"
16#include "llvm/CodeGen/FunctionLoweringInfo.h"
17#include "llvm/DerivedTypes.h"
18#include "llvm/Function.h"
19#include "llvm/Instructions.h"
20#include "llvm/IntrinsicInst.h"
21#include "llvm/LLVMContext.h"
22#include "llvm/Module.h"
23#include "llvm/Analysis/DebugInfo.h"
24#include "llvm/CodeGen/Analysis.h"
25#include "llvm/CodeGen/MachineFunction.h"
26#include "llvm/CodeGen/MachineFrameInfo.h"
27#include "llvm/CodeGen/MachineInstrBuilder.h"
28#include "llvm/CodeGen/MachineModuleInfo.h"
29#include "llvm/CodeGen/MachineRegisterInfo.h"
30#include "llvm/Target/TargetRegisterInfo.h"
31#include "llvm/Target/TargetData.h"
32#include "llvm/Target/TargetInstrInfo.h"
33#include "llvm/Target/TargetLowering.h"
34#include "llvm/Target/TargetOptions.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/ErrorHandling.h"
37#include "llvm/Support/MathExtras.h"
38#include <algorithm>
39using namespace llvm;
40
41/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
42/// PHI nodes or outside of the basic block that defines it, or used by a
43/// switch or atomic instruction, which may expand to multiple basic blocks.
44static bool isUsedOutsideOfDefiningBlock(const Instruction *I) {
45  if (I->use_empty()) return false;
46  if (isa<PHINode>(I)) return true;
47  const BasicBlock *BB = I->getParent();
48  for (Value::const_use_iterator UI = I->use_begin(), E = I->use_end();
49        UI != E; ++UI) {
50    const User *U = *UI;
51    if (cast<Instruction>(U)->getParent() != BB || isa<PHINode>(U))
52      return true;
53  }
54  return false;
55}
56
57FunctionLoweringInfo::FunctionLoweringInfo(const TargetLowering &tli)
58  : TLI(tli) {
59}
60
61void FunctionLoweringInfo::set(const Function &fn, MachineFunction &mf) {
62  Fn = &fn;
63  MF = &mf;
64  RegInfo = &MF->getRegInfo();
65
66  // Check whether the function can return without sret-demotion.
67  SmallVector<ISD::OutputArg, 4> Outs;
68  GetReturnInfo(Fn->getReturnType(),
69                Fn->getAttributes().getRetAttributes(), Outs, TLI);
70  CanLowerReturn = TLI.CanLowerReturn(Fn->getCallingConv(), *MF,
71				      Fn->isVarArg(),
72                                      Outs, Fn->getContext());
73
74  // Initialize the mapping of values to registers.  This is only set up for
75  // instruction values that are used outside of the block that defines
76  // them.
77  Function::const_iterator BB = Fn->begin(), EB = Fn->end();
78  for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I)
79    if (const AllocaInst *AI = dyn_cast<AllocaInst>(I))
80      if (const ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
81        Type *Ty = AI->getAllocatedType();
82        uint64_t TySize = TLI.getTargetData()->getTypeAllocSize(Ty);
83        unsigned Align =
84          std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
85                   AI->getAlignment());
86
87        TySize *= CUI->getZExtValue();   // Get total allocated size.
88        if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
89
90        // The object may need to be placed onto the stack near the stack
91        // protector if one exists. Determine here if this object is a suitable
92        // candidate. I.e., it would trigger the creation of a stack protector.
93        bool MayNeedSP =
94          (AI->isArrayAllocation() ||
95           (TySize > 8 && isa<ArrayType>(Ty) &&
96            cast<ArrayType>(Ty)->getElementType()->isIntegerTy(8)));
97        StaticAllocaMap[AI] =
98          MF->getFrameInfo()->CreateStackObject(TySize, Align, false, MayNeedSP);
99      }
100
101  for (; BB != EB; ++BB)
102    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
103      // Mark values used outside their block as exported, by allocating
104      // a virtual register for them.
105      if (isUsedOutsideOfDefiningBlock(I))
106        if (!isa<AllocaInst>(I) ||
107            !StaticAllocaMap.count(cast<AllocaInst>(I)))
108          InitializeRegForValue(I);
109
110      // Collect llvm.dbg.declare information. This is done now instead of
111      // during the initial isel pass through the IR so that it is done
112      // in a predictable order.
113      if (const DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(I)) {
114        MachineModuleInfo &MMI = MF->getMMI();
115        if (MMI.hasDebugInfo() &&
116            DIVariable(DI->getVariable()).Verify() &&
117            !DI->getDebugLoc().isUnknown()) {
118          // Don't handle byval struct arguments or VLAs, for example.
119          // Non-byval arguments are handled here (they refer to the stack
120          // temporary alloca at this point).
121          const Value *Address = DI->getAddress();
122          if (Address) {
123            if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Address))
124              Address = BCI->getOperand(0);
125            if (const AllocaInst *AI = dyn_cast<AllocaInst>(Address)) {
126              DenseMap<const AllocaInst *, int>::iterator SI =
127                StaticAllocaMap.find(AI);
128              if (SI != StaticAllocaMap.end()) { // Check for VLAs.
129                int FI = SI->second;
130                MMI.setVariableDbgInfo(DI->getVariable(),
131                                       FI, DI->getDebugLoc());
132              }
133            }
134          }
135        }
136      }
137    }
138
139  // Create an initial MachineBasicBlock for each LLVM BasicBlock in F.  This
140  // also creates the initial PHI MachineInstrs, though none of the input
141  // operands are populated.
142  for (BB = Fn->begin(); BB != EB; ++BB) {
143    MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB);
144    MBBMap[BB] = MBB;
145    MF->push_back(MBB);
146
147    // Transfer the address-taken flag. This is necessary because there could
148    // be multiple MachineBasicBlocks corresponding to one BasicBlock, and only
149    // the first one should be marked.
150    if (BB->hasAddressTaken())
151      MBB->setHasAddressTaken();
152
153    // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
154    // appropriate.
155    for (BasicBlock::const_iterator I = BB->begin();
156         const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
157      if (PN->use_empty()) continue;
158
159      // Skip empty types
160      if (PN->getType()->isEmptyTy())
161        continue;
162
163      DebugLoc DL = PN->getDebugLoc();
164      unsigned PHIReg = ValueMap[PN];
165      assert(PHIReg && "PHI node does not have an assigned virtual register!");
166
167      SmallVector<EVT, 4> ValueVTs;
168      ComputeValueVTs(TLI, PN->getType(), ValueVTs);
169      for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) {
170        EVT VT = ValueVTs[vti];
171        unsigned NumRegisters = TLI.getNumRegisters(Fn->getContext(), VT);
172        const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
173        for (unsigned i = 0; i != NumRegisters; ++i)
174          BuildMI(MBB, DL, TII->get(TargetOpcode::PHI), PHIReg + i);
175        PHIReg += NumRegisters;
176      }
177    }
178  }
179
180  // Mark landing pad blocks.
181  for (BB = Fn->begin(); BB != EB; ++BB)
182    if (const InvokeInst *Invoke = dyn_cast<InvokeInst>(BB->getTerminator()))
183      MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
184}
185
186/// clear - Clear out all the function-specific state. This returns this
187/// FunctionLoweringInfo to an empty state, ready to be used for a
188/// different function.
189void FunctionLoweringInfo::clear() {
190  assert(CatchInfoFound.size() == CatchInfoLost.size() &&
191         "Not all catch info was assigned to a landing pad!");
192
193  MBBMap.clear();
194  ValueMap.clear();
195  StaticAllocaMap.clear();
196#ifndef NDEBUG
197  CatchInfoLost.clear();
198  CatchInfoFound.clear();
199#endif
200  LiveOutRegInfo.clear();
201  VisitedBBs.clear();
202  ArgDbgValues.clear();
203  ByValArgFrameIndexMap.clear();
204  RegFixups.clear();
205}
206
207/// CreateReg - Allocate a single virtual register for the given type.
208unsigned FunctionLoweringInfo::CreateReg(EVT VT) {
209  return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
210}
211
212/// CreateRegs - Allocate the appropriate number of virtual registers of
213/// the correctly promoted or expanded types.  Assign these registers
214/// consecutive vreg numbers and return the first assigned number.
215///
216/// In the case that the given value has struct or array type, this function
217/// will assign registers for each member or element.
218///
219unsigned FunctionLoweringInfo::CreateRegs(Type *Ty) {
220  SmallVector<EVT, 4> ValueVTs;
221  ComputeValueVTs(TLI, Ty, ValueVTs);
222
223  unsigned FirstReg = 0;
224  for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
225    EVT ValueVT = ValueVTs[Value];
226    EVT RegisterVT = TLI.getRegisterType(Ty->getContext(), ValueVT);
227
228    unsigned NumRegs = TLI.getNumRegisters(Ty->getContext(), ValueVT);
229    for (unsigned i = 0; i != NumRegs; ++i) {
230      unsigned R = CreateReg(RegisterVT);
231      if (!FirstReg) FirstReg = R;
232    }
233  }
234  return FirstReg;
235}
236
237/// GetLiveOutRegInfo - Gets LiveOutInfo for a register, returning NULL if the
238/// register is a PHI destination and the PHI's LiveOutInfo is not valid. If
239/// the register's LiveOutInfo is for a smaller bit width, it is extended to
240/// the larger bit width by zero extension. The bit width must be no smaller
241/// than the LiveOutInfo's existing bit width.
242const FunctionLoweringInfo::LiveOutInfo *
243FunctionLoweringInfo::GetLiveOutRegInfo(unsigned Reg, unsigned BitWidth) {
244  if (!LiveOutRegInfo.inBounds(Reg))
245    return NULL;
246
247  LiveOutInfo *LOI = &LiveOutRegInfo[Reg];
248  if (!LOI->IsValid)
249    return NULL;
250
251  if (BitWidth > LOI->KnownZero.getBitWidth()) {
252    LOI->NumSignBits = 1;
253    LOI->KnownZero = LOI->KnownZero.zextOrTrunc(BitWidth);
254    LOI->KnownOne = LOI->KnownOne.zextOrTrunc(BitWidth);
255  }
256
257  return LOI;
258}
259
260/// ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI's destination
261/// register based on the LiveOutInfo of its operands.
262void FunctionLoweringInfo::ComputePHILiveOutRegInfo(const PHINode *PN) {
263  Type *Ty = PN->getType();
264  if (!Ty->isIntegerTy() || Ty->isVectorTy())
265    return;
266
267  SmallVector<EVT, 1> ValueVTs;
268  ComputeValueVTs(TLI, Ty, ValueVTs);
269  assert(ValueVTs.size() == 1 &&
270         "PHIs with non-vector integer types should have a single VT.");
271  EVT IntVT = ValueVTs[0];
272
273  if (TLI.getNumRegisters(PN->getContext(), IntVT) != 1)
274    return;
275  IntVT = TLI.getTypeToTransformTo(PN->getContext(), IntVT);
276  unsigned BitWidth = IntVT.getSizeInBits();
277
278  unsigned DestReg = ValueMap[PN];
279  if (!TargetRegisterInfo::isVirtualRegister(DestReg))
280    return;
281  LiveOutRegInfo.grow(DestReg);
282  LiveOutInfo &DestLOI = LiveOutRegInfo[DestReg];
283
284  Value *V = PN->getIncomingValue(0);
285  if (isa<UndefValue>(V) || isa<ConstantExpr>(V)) {
286    DestLOI.NumSignBits = 1;
287    APInt Zero(BitWidth, 0);
288    DestLOI.KnownZero = Zero;
289    DestLOI.KnownOne = Zero;
290    return;
291  }
292
293  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
294    APInt Val = CI->getValue().zextOrTrunc(BitWidth);
295    DestLOI.NumSignBits = Val.getNumSignBits();
296    DestLOI.KnownZero = ~Val;
297    DestLOI.KnownOne = Val;
298  } else {
299    assert(ValueMap.count(V) && "V should have been placed in ValueMap when its"
300                                "CopyToReg node was created.");
301    unsigned SrcReg = ValueMap[V];
302    if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) {
303      DestLOI.IsValid = false;
304      return;
305    }
306    const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth);
307    if (!SrcLOI) {
308      DestLOI.IsValid = false;
309      return;
310    }
311    DestLOI = *SrcLOI;
312  }
313
314  assert(DestLOI.KnownZero.getBitWidth() == BitWidth &&
315         DestLOI.KnownOne.getBitWidth() == BitWidth &&
316         "Masks should have the same bit width as the type.");
317
318  for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
319    Value *V = PN->getIncomingValue(i);
320    if (isa<UndefValue>(V) || isa<ConstantExpr>(V)) {
321      DestLOI.NumSignBits = 1;
322      APInt Zero(BitWidth, 0);
323      DestLOI.KnownZero = Zero;
324      DestLOI.KnownOne = Zero;
325      return;
326    }
327
328    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
329      APInt Val = CI->getValue().zextOrTrunc(BitWidth);
330      DestLOI.NumSignBits = std::min(DestLOI.NumSignBits, Val.getNumSignBits());
331      DestLOI.KnownZero &= ~Val;
332      DestLOI.KnownOne &= Val;
333      continue;
334    }
335
336    assert(ValueMap.count(V) && "V should have been placed in ValueMap when "
337                                "its CopyToReg node was created.");
338    unsigned SrcReg = ValueMap[V];
339    if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) {
340      DestLOI.IsValid = false;
341      return;
342    }
343    const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth);
344    if (!SrcLOI) {
345      DestLOI.IsValid = false;
346      return;
347    }
348    DestLOI.NumSignBits = std::min(DestLOI.NumSignBits, SrcLOI->NumSignBits);
349    DestLOI.KnownZero &= SrcLOI->KnownZero;
350    DestLOI.KnownOne &= SrcLOI->KnownOne;
351  }
352}
353
354/// setByValArgumentFrameIndex - Record frame index for the byval
355/// argument. This overrides previous frame index entry for this argument,
356/// if any.
357void FunctionLoweringInfo::setByValArgumentFrameIndex(const Argument *A,
358                                                      int FI) {
359  assert (A->hasByValAttr() && "Argument does not have byval attribute!");
360  ByValArgFrameIndexMap[A] = FI;
361}
362
363/// getByValArgumentFrameIndex - Get frame index for the byval argument.
364/// If the argument does not have any assigned frame index then 0 is
365/// returned.
366int FunctionLoweringInfo::getByValArgumentFrameIndex(const Argument *A) {
367  assert (A->hasByValAttr() && "Argument does not have byval attribute!");
368  DenseMap<const Argument *, int>::iterator I =
369    ByValArgFrameIndexMap.find(A);
370  if (I != ByValArgFrameIndexMap.end())
371    return I->second;
372  DEBUG(dbgs() << "Argument does not have assigned frame index!");
373  return 0;
374}
375
376/// AddCatchInfo - Extract the personality and type infos from an eh.selector
377/// call, and add them to the specified machine basic block.
378void llvm::AddCatchInfo(const CallInst &I, MachineModuleInfo *MMI,
379                        MachineBasicBlock *MBB) {
380  // Inform the MachineModuleInfo of the personality for this landing pad.
381  const ConstantExpr *CE = cast<ConstantExpr>(I.getArgOperand(1));
382  assert(CE->getOpcode() == Instruction::BitCast &&
383         isa<Function>(CE->getOperand(0)) &&
384         "Personality should be a function");
385  MMI->addPersonality(MBB, cast<Function>(CE->getOperand(0)));
386
387  // Gather all the type infos for this landing pad and pass them along to
388  // MachineModuleInfo.
389  std::vector<const GlobalVariable *> TyInfo;
390  unsigned N = I.getNumArgOperands();
391
392  for (unsigned i = N - 1; i > 1; --i) {
393    if (const ConstantInt *CI = dyn_cast<ConstantInt>(I.getArgOperand(i))) {
394      unsigned FilterLength = CI->getZExtValue();
395      unsigned FirstCatch = i + FilterLength + !FilterLength;
396      assert(FirstCatch <= N && "Invalid filter length");
397
398      if (FirstCatch < N) {
399        TyInfo.reserve(N - FirstCatch);
400        for (unsigned j = FirstCatch; j < N; ++j)
401          TyInfo.push_back(ExtractTypeInfo(I.getArgOperand(j)));
402        MMI->addCatchTypeInfo(MBB, TyInfo);
403        TyInfo.clear();
404      }
405
406      if (!FilterLength) {
407        // Cleanup.
408        MMI->addCleanup(MBB);
409      } else {
410        // Filter.
411        TyInfo.reserve(FilterLength - 1);
412        for (unsigned j = i + 1; j < FirstCatch; ++j)
413          TyInfo.push_back(ExtractTypeInfo(I.getArgOperand(j)));
414        MMI->addFilterTypeInfo(MBB, TyInfo);
415        TyInfo.clear();
416      }
417
418      N = i;
419    }
420  }
421
422  if (N > 2) {
423    TyInfo.reserve(N - 2);
424    for (unsigned j = 2; j < N; ++j)
425      TyInfo.push_back(ExtractTypeInfo(I.getArgOperand(j)));
426    MMI->addCatchTypeInfo(MBB, TyInfo);
427  }
428}
429
430void llvm::CopyCatchInfo(const BasicBlock *SuccBB, const BasicBlock *LPad,
431                         MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) {
432  SmallPtrSet<const BasicBlock*, 4> Visited;
433
434  // The 'eh.selector' call may not be in the direct successor of a basic block,
435  // but could be several successors deeper. If we don't find it, try going one
436  // level further. <rdar://problem/8824861>
437  while (Visited.insert(SuccBB)) {
438    for (BasicBlock::const_iterator I = SuccBB->begin(), E = --SuccBB->end();
439         I != E; ++I)
440      if (const EHSelectorInst *EHSel = dyn_cast<EHSelectorInst>(I)) {
441        // Apply the catch info to LPad.
442        AddCatchInfo(*EHSel, MMI, FLI.MBBMap[LPad]);
443#ifndef NDEBUG
444        if (!FLI.MBBMap[SuccBB]->isLandingPad())
445          FLI.CatchInfoFound.insert(EHSel);
446#endif
447        return;
448      }
449
450    const BranchInst *Br = dyn_cast<BranchInst>(SuccBB->getTerminator());
451    if (Br && Br->isUnconditional())
452      SuccBB = Br->getSuccessor(0);
453    else
454      break;
455  }
456}
457