FunctionLoweringInfo.cpp revision 165dac08d1bb8428b32a5f39cdd3dbee2888987f 
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/TargetLowering.h"
35#include "llvm/Target/TargetOptions.h"
36#include "llvm/Support/Compiler.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/ErrorHandling.h"
39#include "llvm/Support/MathExtras.h"
40#include "llvm/Support/raw_ostream.h"
41#include <algorithm>
42using namespace llvm;
43
44/// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence
45/// of insertvalue or extractvalue indices that identify a member, return
46/// the linearized index of the start of the member.
47///
48unsigned llvm::ComputeLinearIndex(const TargetLowering &TLI, const Type *Ty,
49                                  const unsigned *Indices,
50                                  const unsigned *IndicesEnd,
51                                  unsigned CurIndex) {
52  // Base case: We're done.
53  if (Indices && Indices == IndicesEnd)
54    return CurIndex;
55
56  // Given a struct type, recursively traverse the elements.
57  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
58    for (StructType::element_iterator EB = STy->element_begin(),
59                                      EI = EB,
60                                      EE = STy->element_end();
61        EI != EE; ++EI) {
62      if (Indices && *Indices == unsigned(EI - EB))
63        return ComputeLinearIndex(TLI, *EI, Indices+1, IndicesEnd, CurIndex);
64      CurIndex = ComputeLinearIndex(TLI, *EI, 0, 0, CurIndex);
65    }
66    return CurIndex;
67  }
68  // Given an array type, recursively traverse the elements.
69  else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
70    const Type *EltTy = ATy->getElementType();
71    for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
72      if (Indices && *Indices == i)
73        return ComputeLinearIndex(TLI, EltTy, Indices+1, IndicesEnd, CurIndex);
74      CurIndex = ComputeLinearIndex(TLI, EltTy, 0, 0, CurIndex);
75    }
76    return CurIndex;
77  }
78  // We haven't found the type we're looking for, so keep searching.
79  return CurIndex + 1;
80}
81
82/// ComputeValueVTs - Given an LLVM IR type, compute a sequence of
83/// EVTs that represent all the individual underlying
84/// non-aggregate types that comprise it.
85///
86/// If Offsets is non-null, it points to a vector to be filled in
87/// with the in-memory offsets of each of the individual values.
88///
89void llvm::ComputeValueVTs(const TargetLowering &TLI, const Type *Ty,
90                           SmallVectorImpl<EVT> &ValueVTs,
91                           SmallVectorImpl<uint64_t> *Offsets,
92                           uint64_t StartingOffset) {
93  // Given a struct type, recursively traverse the elements.
94  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
95    const StructLayout *SL = TLI.getTargetData()->getStructLayout(STy);
96    for (StructType::element_iterator EB = STy->element_begin(),
97                                      EI = EB,
98                                      EE = STy->element_end();
99         EI != EE; ++EI)
100      ComputeValueVTs(TLI, *EI, ValueVTs, Offsets,
101                      StartingOffset + SL->getElementOffset(EI - EB));
102    return;
103  }
104  // Given an array type, recursively traverse the elements.
105  if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
106    const Type *EltTy = ATy->getElementType();
107    uint64_t EltSize = TLI.getTargetData()->getTypeAllocSize(EltTy);
108    for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
109      ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets,
110                      StartingOffset + i * EltSize);
111    return;
112  }
113  // Interpret void as zero return values.
114  if (Ty->isVoidTy())
115    return;
116  // Base case: we can get an EVT for this LLVM IR type.
117  ValueVTs.push_back(TLI.getValueType(Ty));
118  if (Offsets)
119    Offsets->push_back(StartingOffset);
120}
121
122/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
123/// PHI nodes or outside of the basic block that defines it, or used by a
124/// switch or atomic instruction, which may expand to multiple basic blocks.
125static bool isUsedOutsideOfDefiningBlock(const Instruction *I) {
126  if (isa<PHINode>(I)) return true;
127  const BasicBlock *BB = I->getParent();
128  for (Value::const_use_iterator UI = I->use_begin(), E = I->use_end();
129        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(const 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  const BasicBlock *Entry = A->getParent()->begin();
147  for (Value::const_use_iterator UI = A->use_begin(), E = A->use_end();
148       UI != E; ++UI)
149    if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI))
150      return false;  // Use not in entry block.
151  return true;
152}
153
154FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli)
155  : TLI(tli) {
156}
157
158void FunctionLoweringInfo::set(const Function &fn, MachineFunction &mf,
159                               bool EnableFastISel) {
160  Fn = &fn;
161  MF = &mf;
162  RegInfo = &MF->getRegInfo();
163
164  // Create a vreg for each argument register that is not dead and is used
165  // outside of the entry block for the function.
166  for (Function::const_arg_iterator AI = Fn->arg_begin(), E = Fn->arg_end();
167       AI != E; ++AI)
168    if (!isOnlyUsedInEntryBlock(AI, EnableFastISel))
169      InitializeRegForValue(AI);
170
171  // Initialize the mapping of values to registers.  This is only set up for
172  // instruction values that are used outside of the block that defines
173  // them.
174  Function::const_iterator BB = Fn->begin(), EB = Fn->end();
175  for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I)
176    if (const AllocaInst *AI = dyn_cast<AllocaInst>(I))
177      if (const ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
178        const Type *Ty = AI->getAllocatedType();
179        uint64_t TySize = TLI.getTargetData()->getTypeAllocSize(Ty);
180        unsigned Align =
181          std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
182                   AI->getAlignment());
183
184        TySize *= CUI->getZExtValue();   // Get total allocated size.
185        if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
186        StaticAllocaMap[AI] =
187          MF->getFrameInfo()->CreateStackObject(TySize, Align, false);
188      }
189
190  for (; BB != EB; ++BB)
191    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I)
192      if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
193        if (!isa<AllocaInst>(I) ||
194            !StaticAllocaMap.count(cast<AllocaInst>(I)))
195          InitializeRegForValue(I);
196
197  // Create an initial MachineBasicBlock for each LLVM BasicBlock in F.  This
198  // also creates the initial PHI MachineInstrs, though none of the input
199  // operands are populated.
200  for (BB = Fn->begin(); BB != EB; ++BB) {
201    MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB);
202    MBBMap[BB] = MBB;
203    MF->push_back(MBB);
204
205    // Transfer the address-taken flag. This is necessary because there could
206    // be multiple MachineBasicBlocks corresponding to one BasicBlock, and only
207    // the first one should be marked.
208    if (BB->hasAddressTaken())
209      MBB->setHasAddressTaken();
210
211    // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
212    // appropriate.
213    const PHINode *PN;
214    DebugLoc DL;
215    for (BasicBlock::const_iterator
216           I = BB->begin(), E = BB->end(); I != E; ++I) {
217
218      PN = dyn_cast<PHINode>(I);
219      if (!PN || PN->use_empty()) continue;
220
221      unsigned PHIReg = ValueMap[PN];
222      assert(PHIReg && "PHI node does not have an assigned virtual register!");
223
224      SmallVector<EVT, 4> ValueVTs;
225      ComputeValueVTs(TLI, PN->getType(), ValueVTs);
226      for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) {
227        EVT VT = ValueVTs[vti];
228        unsigned NumRegisters = TLI.getNumRegisters(Fn->getContext(), VT);
229        const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
230        for (unsigned i = 0; i != NumRegisters; ++i)
231          BuildMI(MBB, DL, TII->get(TargetOpcode::PHI), PHIReg + i);
232        PHIReg += NumRegisters;
233      }
234    }
235  }
236
237  // Mark landing pad blocks.
238  for (BB = Fn->begin(); BB != EB; ++BB)
239    if (const InvokeInst *Invoke = dyn_cast<InvokeInst>(BB->getTerminator()))
240      MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
241}
242
243/// clear - Clear out all the function-specific state. This returns this
244/// FunctionLoweringInfo to an empty state, ready to be used for a
245/// different function.
246void FunctionLoweringInfo::clear() {
247  assert(CatchInfoFound.size() == CatchInfoLost.size() &&
248         "Not all catch info was assigned to a landing pad!");
249
250  MBBMap.clear();
251  ValueMap.clear();
252  StaticAllocaMap.clear();
253#ifndef NDEBUG
254  CatchInfoLost.clear();
255  CatchInfoFound.clear();
256#endif
257  LiveOutRegInfo.clear();
258}
259
260unsigned FunctionLoweringInfo::MakeReg(EVT VT) {
261  return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
262}
263
264/// CreateRegForValue - Allocate the appropriate number of virtual registers of
265/// the correctly promoted or expanded types.  Assign these registers
266/// consecutive vreg numbers and return the first assigned number.
267///
268/// In the case that the given value has struct or array type, this function
269/// will assign registers for each member or element.
270///
271unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
272  SmallVector<EVT, 4> ValueVTs;
273  ComputeValueVTs(TLI, V->getType(), ValueVTs);
274
275  unsigned FirstReg = 0;
276  for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
277    EVT ValueVT = ValueVTs[Value];
278    EVT RegisterVT = TLI.getRegisterType(V->getContext(), ValueVT);
279
280    unsigned NumRegs = TLI.getNumRegisters(V->getContext(), ValueVT);
281    for (unsigned i = 0; i != NumRegs; ++i) {
282      unsigned R = MakeReg(RegisterVT);
283      if (!FirstReg) FirstReg = R;
284    }
285  }
286  return FirstReg;
287}
288
289/// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V.
290GlobalVariable *llvm::ExtractTypeInfo(Value *V) {
291  V = V->stripPointerCasts();
292  GlobalVariable *GV = dyn_cast<GlobalVariable>(V);
293
294  if (GV && GV->getName() == ".llvm.eh.catch.all.value") {
295    assert(GV->hasInitializer() &&
296           "The EH catch-all value must have an initializer");
297    Value *Init = GV->getInitializer();
298    GV = dyn_cast<GlobalVariable>(Init);
299    if (!GV) V = cast<ConstantPointerNull>(Init);
300  }
301
302  assert((GV || isa<ConstantPointerNull>(V)) &&
303         "TypeInfo must be a global variable or NULL");
304  return GV;
305}
306
307/// AddCatchInfo - Extract the personality and type infos from an eh.selector
308/// call, and add them to the specified machine basic block.
309void llvm::AddCatchInfo(const CallInst &I, MachineModuleInfo *MMI,
310                        MachineBasicBlock *MBB) {
311  // Inform the MachineModuleInfo of the personality for this landing pad.
312  const ConstantExpr *CE = cast<ConstantExpr>(I.getOperand(1));
313  assert(CE->getOpcode() == Instruction::BitCast &&
314         isa<Function>(CE->getOperand(0)) &&
315         "Personality should be a function");
316  MMI->addPersonality(MBB, cast<Function>(CE->getOperand(0)));
317
318  // Gather all the type infos for this landing pad and pass them along to
319  // MachineModuleInfo.
320  std::vector<const GlobalVariable *> TyInfo;
321  unsigned N = I.getNumOperands() - 1;
322
323  for (unsigned i = N - 1; i > 1; --i) {
324    if (const ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i))) {
325      unsigned FilterLength = CI->getZExtValue();
326      unsigned FirstCatch = i + FilterLength + !FilterLength;
327      assert (FirstCatch <= N && "Invalid filter length");
328
329      if (FirstCatch < N) {
330        TyInfo.reserve(N - FirstCatch);
331        for (unsigned j = FirstCatch; j < N; ++j)
332          TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
333        MMI->addCatchTypeInfo(MBB, TyInfo);
334        TyInfo.clear();
335      }
336
337      if (!FilterLength) {
338        // Cleanup.
339        MMI->addCleanup(MBB);
340      } else {
341        // Filter.
342        TyInfo.reserve(FilterLength - 1);
343        for (unsigned j = i + 1; j < FirstCatch; ++j)
344          TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
345        MMI->addFilterTypeInfo(MBB, TyInfo);
346        TyInfo.clear();
347      }
348
349      N = i;
350    }
351  }
352
353  if (N > 2) {
354    TyInfo.reserve(N - 2);
355    for (unsigned j = 2; j < N - 1; ++j)
356      TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
357    MMI->addCatchTypeInfo(MBB, TyInfo);
358  }
359}
360
361void llvm::CopyCatchInfo(const BasicBlock *SrcBB, const BasicBlock *DestBB,
362                         MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) {
363  for (BasicBlock::const_iterator I = SrcBB->begin(), E = --SrcBB->end();
364       I != E; ++I)
365    if (const EHSelectorInst *EHSel = dyn_cast<EHSelectorInst>(I)) {
366      // Apply the catch info to DestBB.
367      AddCatchInfo(*EHSel, MMI, FLI.MBBMap[DestBB]);
368#ifndef NDEBUG
369      if (!FLI.MBBMap[SrcBB]->isLandingPad())
370        FLI.CatchInfoFound.insert(EHSel);
371#endif
372    }
373}
374
375/// hasInlineAsmMemConstraint - Return true if the inline asm instruction being
376/// processed uses a memory 'm' constraint.
377bool
378llvm::hasInlineAsmMemConstraint(std::vector<InlineAsm::ConstraintInfo> &CInfos,
379                                const TargetLowering &TLI) {
380  for (unsigned i = 0, e = CInfos.size(); i != e; ++i) {
381    InlineAsm::ConstraintInfo &CI = CInfos[i];
382    for (unsigned j = 0, ee = CI.Codes.size(); j != ee; ++j) {
383      TargetLowering::ConstraintType CType = TLI.getConstraintType(CI.Codes[j]);
384      if (CType == TargetLowering::C_Memory)
385        return true;
386    }
387
388    // Indirect operand accesses access memory.
389    if (CI.isIndirect)
390      return true;
391  }
392
393  return false;
394}
395
396/// getFCmpCondCode - Return the ISD condition code corresponding to
397/// the given LLVM IR floating-point condition code.  This includes
398/// consideration of global floating-point math flags.
399///
400ISD::CondCode llvm::getFCmpCondCode(FCmpInst::Predicate Pred) {
401  ISD::CondCode FPC, FOC;
402  switch (Pred) {
403  case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
404  case FCmpInst::FCMP_OEQ:   FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
405  case FCmpInst::FCMP_OGT:   FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
406  case FCmpInst::FCMP_OGE:   FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
407  case FCmpInst::FCMP_OLT:   FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
408  case FCmpInst::FCMP_OLE:   FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
409  case FCmpInst::FCMP_ONE:   FOC = ISD::SETNE; FPC = ISD::SETONE; break;
410  case FCmpInst::FCMP_ORD:   FOC = FPC = ISD::SETO;   break;
411  case FCmpInst::FCMP_UNO:   FOC = FPC = ISD::SETUO;  break;
412  case FCmpInst::FCMP_UEQ:   FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
413  case FCmpInst::FCMP_UGT:   FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
414  case FCmpInst::FCMP_UGE:   FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
415  case FCmpInst::FCMP_ULT:   FOC = ISD::SETLT; FPC = ISD::SETULT; break;
416  case FCmpInst::FCMP_ULE:   FOC = ISD::SETLE; FPC = ISD::SETULE; break;
417  case FCmpInst::FCMP_UNE:   FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
418  case FCmpInst::FCMP_TRUE:  FOC = FPC = ISD::SETTRUE; break;
419  default:
420    llvm_unreachable("Invalid FCmp predicate opcode!");
421    FOC = FPC = ISD::SETFALSE;
422    break;
423  }
424  if (FiniteOnlyFPMath())
425    return FOC;
426  else
427    return FPC;
428}
429
430/// getICmpCondCode - Return the ISD condition code corresponding to
431/// the given LLVM IR integer condition code.
432///
433ISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) {
434  switch (Pred) {
435  case ICmpInst::ICMP_EQ:  return ISD::SETEQ;
436  case ICmpInst::ICMP_NE:  return ISD::SETNE;
437  case ICmpInst::ICMP_SLE: return ISD::SETLE;
438  case ICmpInst::ICMP_ULE: return ISD::SETULE;
439  case ICmpInst::ICMP_SGE: return ISD::SETGE;
440  case ICmpInst::ICMP_UGE: return ISD::SETUGE;
441  case ICmpInst::ICMP_SLT: return ISD::SETLT;
442  case ICmpInst::ICMP_ULT: return ISD::SETULT;
443  case ICmpInst::ICMP_SGT: return ISD::SETGT;
444  case ICmpInst::ICMP_UGT: return ISD::SETUGT;
445  default:
446    llvm_unreachable("Invalid ICmp predicate opcode!");
447    return ISD::SETNE;
448  }
449}
450