FunctionLoweringInfo.cpp revision 80ffc965f513bed2252316af8530c14c36c2e295 
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 "FunctionLoweringInfo.h"
17#include "llvm/CallingConv.h"
18#include "llvm/DerivedTypes.h"
19#include "llvm/Function.h"
20#include "llvm/Instructions.h"
21#include "llvm/IntrinsicInst.h"
22#include "llvm/LLVMContext.h"
23#include "llvm/Module.h"
24#include "llvm/CodeGen/MachineFunction.h"
25#include "llvm/CodeGen/MachineFrameInfo.h"
26#include "llvm/CodeGen/MachineInstrBuilder.h"
27#include "llvm/CodeGen/MachineModuleInfo.h"
28#include "llvm/CodeGen/MachineRegisterInfo.h"
29#include "llvm/Analysis/DebugInfo.h"
30#include "llvm/Target/TargetRegisterInfo.h"
31#include "llvm/Target/TargetData.h"
32#include "llvm/Target/TargetFrameInfo.h"
33#include "llvm/Target/TargetInstrInfo.h"
34#include "llvm/Target/TargetIntrinsicInfo.h"
35#include "llvm/Target/TargetLowering.h"
36#include "llvm/Target/TargetOptions.h"
37#include "llvm/Support/Compiler.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/ErrorHandling.h"
40#include "llvm/Support/MathExtras.h"
41#include "llvm/Support/raw_ostream.h"
42#include <algorithm>
43using namespace llvm;
44
45/// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence
46/// of insertvalue or extractvalue indices that identify a member, return
47/// the linearized index of the start of the member.
48///
49unsigned llvm::ComputeLinearIndex(const TargetLowering &TLI, const Type *Ty,
50                                  const unsigned *Indices,
51                                  const unsigned *IndicesEnd,
52                                  unsigned CurIndex) {
53  // Base case: We're done.
54  if (Indices && Indices == IndicesEnd)
55    return CurIndex;
56
57  // Given a struct type, recursively traverse the elements.
58  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
59    for (StructType::element_iterator EB = STy->element_begin(),
60                                      EI = EB,
61                                      EE = STy->element_end();
62        EI != EE; ++EI) {
63      if (Indices && *Indices == unsigned(EI - EB))
64        return ComputeLinearIndex(TLI, *EI, Indices+1, IndicesEnd, CurIndex);
65      CurIndex = ComputeLinearIndex(TLI, *EI, 0, 0, CurIndex);
66    }
67    return CurIndex;
68  }
69  // Given an array type, recursively traverse the elements.
70  else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
71    const Type *EltTy = ATy->getElementType();
72    for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
73      if (Indices && *Indices == i)
74        return ComputeLinearIndex(TLI, EltTy, Indices+1, IndicesEnd, CurIndex);
75      CurIndex = ComputeLinearIndex(TLI, EltTy, 0, 0, CurIndex);
76    }
77    return CurIndex;
78  }
79  // We haven't found the type we're looking for, so keep searching.
80  return CurIndex + 1;
81}
82
83/// ComputeValueVTs - Given an LLVM IR type, compute a sequence of
84/// EVTs that represent all the individual underlying
85/// non-aggregate types that comprise it.
86///
87/// If Offsets is non-null, it points to a vector to be filled in
88/// with the in-memory offsets of each of the individual values.
89///
90void llvm::ComputeValueVTs(const TargetLowering &TLI, const Type *Ty,
91                           SmallVectorImpl<EVT> &ValueVTs,
92                           SmallVectorImpl<uint64_t> *Offsets,
93                           uint64_t StartingOffset) {
94  // Given a struct type, recursively traverse the elements.
95  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
96    const StructLayout *SL = TLI.getTargetData()->getStructLayout(STy);
97    for (StructType::element_iterator EB = STy->element_begin(),
98                                      EI = EB,
99                                      EE = STy->element_end();
100         EI != EE; ++EI)
101      ComputeValueVTs(TLI, *EI, ValueVTs, Offsets,
102                      StartingOffset + SL->getElementOffset(EI - EB));
103    return;
104  }
105  // Given an array type, recursively traverse the elements.
106  if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
107    const Type *EltTy = ATy->getElementType();
108    uint64_t EltSize = TLI.getTargetData()->getTypeAllocSize(EltTy);
109    for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
110      ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets,
111                      StartingOffset + i * EltSize);
112    return;
113  }
114  // Interpret void as zero return values.
115  if (Ty->isVoidTy())
116    return;
117  // Base case: we can get an EVT for this LLVM IR type.
118  ValueVTs.push_back(TLI.getValueType(Ty));
119  if (Offsets)
120    Offsets->push_back(StartingOffset);
121}
122
123/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
124/// PHI nodes or outside of the basic block that defines it, or used by a
125/// switch or atomic instruction, which may expand to multiple basic blocks.
126static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
127  if (isa<PHINode>(I)) return true;
128  BasicBlock *BB = I->getParent();
129  for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
130    if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI))
131      return true;
132  return false;
133}
134
135/// isOnlyUsedInEntryBlock - If the specified argument is only used in the
136/// entry block, return true.  This includes arguments used by switches, since
137/// the switch may expand into multiple basic blocks.
138static bool isOnlyUsedInEntryBlock(Argument *A, bool EnableFastISel) {
139  // With FastISel active, we may be splitting blocks, so force creation
140  // of virtual registers for all non-dead arguments.
141  // Don't force virtual registers for byval arguments though, because
142  // fast-isel can't handle those in all cases.
143  if (EnableFastISel && !A->hasByValAttr())
144    return A->use_empty();
145
146  BasicBlock *Entry = A->getParent()->begin();
147  for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI)
148    if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI))
149      return false;  // Use not in entry block.
150  return true;
151}
152
153FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli)
154  : TLI(tli) {
155}
156
157void FunctionLoweringInfo::set(Function &fn, MachineFunction &mf,
158                               bool EnableFastISel) {
159  Fn = &fn;
160  MF = &mf;
161  RegInfo = &MF->getRegInfo();
162
163  // Create a vreg for each argument register that is not dead and is used
164  // outside of the entry block for the function.
165  for (Function::arg_iterator AI = Fn->arg_begin(), E = Fn->arg_end();
166       AI != E; ++AI)
167    if (!isOnlyUsedInEntryBlock(AI, EnableFastISel))
168      InitializeRegForValue(AI);
169
170  // Initialize the mapping of values to registers.  This is only set up for
171  // instruction values that are used outside of the block that defines
172  // them.
173  Function::iterator BB = Fn->begin(), EB = Fn->end();
174  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
175    if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
176      if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
177        const Type *Ty = AI->getAllocatedType();
178        uint64_t TySize = TLI.getTargetData()->getTypeAllocSize(Ty);
179        unsigned Align =
180          std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
181                   AI->getAlignment());
182
183        TySize *= CUI->getZExtValue();   // Get total allocated size.
184        if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
185        StaticAllocaMap[AI] =
186          MF->getFrameInfo()->CreateStackObject(TySize, Align, false);
187      }
188
189  for (; BB != EB; ++BB)
190    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
191      if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
192        if (!isa<AllocaInst>(I) ||
193            !StaticAllocaMap.count(cast<AllocaInst>(I)))
194          InitializeRegForValue(I);
195
196  // Create an initial MachineBasicBlock for each LLVM BasicBlock in F.  This
197  // also creates the initial PHI MachineInstrs, though none of the input
198  // operands are populated.
199  for (BB = Fn->begin(), EB = Fn->end(); BB != EB; ++BB) {
200    MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB);
201    MBBMap[BB] = MBB;
202    MF->push_back(MBB);
203
204    // Transfer the address-taken flag. This is necessary because there could
205    // be multiple MachineBasicBlocks corresponding to one BasicBlock, and only
206    // the first one should be marked.
207    if (BB->hasAddressTaken())
208      MBB->setHasAddressTaken();
209
210    // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
211    // appropriate.
212    PHINode *PN;
213    DebugLoc DL;
214    for (BasicBlock::iterator
215           I = BB->begin(), E = BB->end(); I != E; ++I) {
216
217      PN = dyn_cast<PHINode>(I);
218      if (!PN || PN->use_empty()) continue;
219
220      unsigned PHIReg = ValueMap[PN];
221      assert(PHIReg && "PHI node does not have an assigned virtual register!");
222
223      SmallVector<EVT, 4> ValueVTs;
224      ComputeValueVTs(TLI, PN->getType(), ValueVTs);
225      for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) {
226        EVT VT = ValueVTs[vti];
227        unsigned NumRegisters = TLI.getNumRegisters(Fn->getContext(), VT);
228        const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
229        for (unsigned i = 0; i != NumRegisters; ++i)
230          BuildMI(MBB, DL, TII->get(TargetInstrInfo::PHI), PHIReg + i);
231        PHIReg += NumRegisters;
232      }
233    }
234  }
235}
236
237/// clear - Clear out all the function-specific state. This returns this
238/// FunctionLoweringInfo to an empty state, ready to be used for a
239/// different function.
240void FunctionLoweringInfo::clear() {
241  MBBMap.clear();
242  ValueMap.clear();
243  StaticAllocaMap.clear();
244#ifndef NDEBUG
245  CatchInfoLost.clear();
246  CatchInfoFound.clear();
247#endif
248  LiveOutRegInfo.clear();
249}
250
251unsigned FunctionLoweringInfo::MakeReg(EVT VT) {
252  return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
253}
254
255/// CreateRegForValue - Allocate the appropriate number of virtual registers of
256/// the correctly promoted or expanded types.  Assign these registers
257/// consecutive vreg numbers and return the first assigned number.
258///
259/// In the case that the given value has struct or array type, this function
260/// will assign registers for each member or element.
261///
262unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
263  SmallVector<EVT, 4> ValueVTs;
264  ComputeValueVTs(TLI, V->getType(), ValueVTs);
265
266  unsigned FirstReg = 0;
267  for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
268    EVT ValueVT = ValueVTs[Value];
269    EVT RegisterVT = TLI.getRegisterType(V->getContext(), ValueVT);
270
271    unsigned NumRegs = TLI.getNumRegisters(V->getContext(), ValueVT);
272    for (unsigned i = 0; i != NumRegs; ++i) {
273      unsigned R = MakeReg(RegisterVT);
274      if (!FirstReg) FirstReg = R;
275    }
276  }
277  return FirstReg;
278}
279
280/// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V.
281GlobalVariable *llvm::ExtractTypeInfo(Value *V) {
282  V = V->stripPointerCasts();
283  GlobalVariable *GV = dyn_cast<GlobalVariable>(V);
284  assert ((GV || isa<ConstantPointerNull>(V)) &&
285          "TypeInfo must be a global variable or NULL");
286  return GV;
287}
288
289/// AddCatchInfo - Extract the personality and type infos from an eh.selector
290/// call, and add them to the specified machine basic block.
291void llvm::AddCatchInfo(CallInst &I, MachineModuleInfo *MMI,
292                        MachineBasicBlock *MBB) {
293  // Inform the MachineModuleInfo of the personality for this landing pad.
294  ConstantExpr *CE = cast<ConstantExpr>(I.getOperand(2));
295  assert(CE->getOpcode() == Instruction::BitCast &&
296         isa<Function>(CE->getOperand(0)) &&
297         "Personality should be a function");
298  MMI->addPersonality(MBB, cast<Function>(CE->getOperand(0)));
299
300  // Gather all the type infos for this landing pad and pass them along to
301  // MachineModuleInfo.
302  std::vector<GlobalVariable *> TyInfo;
303  unsigned N = I.getNumOperands();
304
305  for (unsigned i = N - 1; i > 2; --i) {
306    if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i))) {
307      unsigned FilterLength = CI->getZExtValue();
308      unsigned FirstCatch = i + FilterLength + !FilterLength;
309      assert (FirstCatch <= N && "Invalid filter length");
310
311      if (FirstCatch < N) {
312        TyInfo.reserve(N - FirstCatch);
313        for (unsigned j = FirstCatch; j < N; ++j)
314          TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
315        MMI->addCatchTypeInfo(MBB, TyInfo);
316        TyInfo.clear();
317      }
318
319      if (!FilterLength) {
320        // Cleanup.
321        MMI->addCleanup(MBB);
322      } else {
323        // Filter.
324        TyInfo.reserve(FilterLength - 1);
325        for (unsigned j = i + 1; j < FirstCatch; ++j)
326          TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
327        MMI->addFilterTypeInfo(MBB, TyInfo);
328        TyInfo.clear();
329      }
330
331      N = i;
332    }
333  }
334
335  if (N > 3) {
336    TyInfo.reserve(N - 3);
337    for (unsigned j = 3; j < N; ++j)
338      TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
339    MMI->addCatchTypeInfo(MBB, TyInfo);
340  }
341}
342
343void llvm::CopyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB,
344                         MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) {
345  for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I)
346    if (EHSelectorInst *EHSel = dyn_cast<EHSelectorInst>(I)) {
347      // Apply the catch info to DestBB.
348      AddCatchInfo(*EHSel, MMI, FLI.MBBMap[DestBB]);
349#ifndef NDEBUG
350      if (!FLI.MBBMap[SrcBB]->isLandingPad())
351        FLI.CatchInfoFound.insert(EHSel);
352#endif
353    }
354}
355