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/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/CodeGen/Analysis.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/Target/TargetRegisterInfo.h"
30 #include "llvm/Target/TargetData.h"
31 #include "llvm/Target/TargetFrameInfo.h"
32 #include "llvm/Target/TargetInstrInfo.h"
33 #include "llvm/Target/TargetIntrinsicInfo.h"
34 #include "llvm/Target/TargetLowering.h"
35 #include "llvm/Target/TargetOptions.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/MathExtras.h"
39 #include <algorithm>
40 using namespace llvm;
41 
42 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
43 /// PHI nodes or outside of the basic block that defines it, or used by a
44 /// switch or atomic instruction, which may expand to multiple basic blocks.
45 static bool isUsedOutsideOfDefiningBlock(const Instruction *I) {
46   if (I->use_empty()) return false;
47   if (isa<PHINode>(I)) return true;
48   const BasicBlock *BB = I->getParent();
49   for (Value::const_use_iterator UI = I->use_begin(), E = I->use_end();
50         UI != E; ++UI)
51     if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI))
52       return true;
53   return false;
54 }
55 
56 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the
57 /// entry block, return true.  This includes arguments used by switches, since
58 /// the switch may expand into multiple basic blocks.
59 static bool isOnlyUsedInEntryBlock(const Argument *A, bool EnableFastISel) {
60   // With FastISel active, we may be splitting blocks, so force creation
61   // of virtual registers for all non-dead arguments.
62   if (EnableFastISel)
63     return A->use_empty();
64 
65   const BasicBlock *Entry = A->getParent()->begin();
66   for (Value::const_use_iterator UI = A->use_begin(), E = A->use_end();
67        UI != E; ++UI)
68     if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI))
69       return false;  // Use not in entry block.
70   return true;
71 }
72 
73 FunctionLoweringInfo::FunctionLoweringInfo(const TargetLowering &tli)
74   : TLI(tli) {
75 }
76 
77 void FunctionLoweringInfo::set(const Function &fn, MachineFunction &mf,
78                                bool EnableFastISel) {
79   Fn = &fn;
80   MF = &mf;
81   RegInfo = &MF->getRegInfo();
82 
83   // Create a vreg for each argument register that is not dead and is used
84   // outside of the entry block for the function.
85   for (Function::const_arg_iterator AI = Fn->arg_begin(), E = Fn->arg_end();
86        AI != E; ++AI)
87     if (!isOnlyUsedInEntryBlock(AI, EnableFastISel))
88       InitializeRegForValue(AI);
89 
90   // Initialize the mapping of values to registers.  This is only set up for
91   // instruction values that are used outside of the block that defines
92   // them.
93   Function::const_iterator BB = Fn->begin(), EB = Fn->end();
94   for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I)
95     if (const AllocaInst *AI = dyn_cast<AllocaInst>(I))
96       if (const ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
97         const Type *Ty = AI->getAllocatedType();
98         uint64_t TySize = TLI.getTargetData()->getTypeAllocSize(Ty);
99         unsigned Align =
100           std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
101                    AI->getAlignment());
102 
103         TySize *= CUI->getZExtValue();   // Get total allocated size.
104         if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
105         StaticAllocaMap[AI] =
106           MF->getFrameInfo()->CreateStackObject(TySize, Align, false);
107       }
108 
109   for (; BB != EB; ++BB)
110     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I)
111       if (isUsedOutsideOfDefiningBlock(I))
112         if (!isa<AllocaInst>(I) ||
113             !StaticAllocaMap.count(cast<AllocaInst>(I)))
114           InitializeRegForValue(I);
115 
116   // Create an initial MachineBasicBlock for each LLVM BasicBlock in F.  This
117   // also creates the initial PHI MachineInstrs, though none of the input
118   // operands are populated.
119   for (BB = Fn->begin(); BB != EB; ++BB) {
120     MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB);
121     MBBMap[BB] = MBB;
122     MF->push_back(MBB);
123 
124     // Transfer the address-taken flag. This is necessary because there could
125     // be multiple MachineBasicBlocks corresponding to one BasicBlock, and only
126     // the first one should be marked.
127     if (BB->hasAddressTaken())
128       MBB->setHasAddressTaken();
129 
130     // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
131     // appropriate.
132     for (BasicBlock::const_iterator I = BB->begin();
133          const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
134       if (PN->use_empty()) continue;
135 
136       DebugLoc DL = PN->getDebugLoc();
137       unsigned PHIReg = ValueMap[PN];
138       assert(PHIReg && "PHI node does not have an assigned virtual register!");
139 
140       SmallVector<EVT, 4> ValueVTs;
141       ComputeValueVTs(TLI, PN->getType(), ValueVTs);
142       for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) {
143         EVT VT = ValueVTs[vti];
144         unsigned NumRegisters = TLI.getNumRegisters(Fn->getContext(), VT);
145         const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
146         for (unsigned i = 0; i != NumRegisters; ++i)
147           BuildMI(MBB, DL, TII->get(TargetOpcode::PHI), PHIReg + i);
148         PHIReg += NumRegisters;
149       }
150     }
151   }
152 
153   // Mark landing pad blocks.
154   for (BB = Fn->begin(); BB != EB; ++BB)
155     if (const InvokeInst *Invoke = dyn_cast<InvokeInst>(BB->getTerminator()))
156       MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
157 }
158 
159 /// clear - Clear out all the function-specific state. This returns this
160 /// FunctionLoweringInfo to an empty state, ready to be used for a
161 /// different function.
162 void FunctionLoweringInfo::clear() {
163   assert(CatchInfoFound.size() == CatchInfoLost.size() &&
164          "Not all catch info was assigned to a landing pad!");
165 
166   MBBMap.clear();
167   ValueMap.clear();
168   StaticAllocaMap.clear();
169 #ifndef NDEBUG
170   CatchInfoLost.clear();
171   CatchInfoFound.clear();
172 #endif
173   LiveOutRegInfo.clear();
174   ArgDbgValues.clear();
175 }
176 
177 unsigned FunctionLoweringInfo::MakeReg(EVT VT) {
178   return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
179 }
180 
181 /// CreateRegForValue - Allocate the appropriate number of virtual registers of
182 /// the correctly promoted or expanded types.  Assign these registers
183 /// consecutive vreg numbers and return the first assigned number.
184 ///
185 /// In the case that the given value has struct or array type, this function
186 /// will assign registers for each member or element.
187 ///
188 unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
189   SmallVector<EVT, 4> ValueVTs;
190   ComputeValueVTs(TLI, V->getType(), ValueVTs);
191 
192   unsigned FirstReg = 0;
193   for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
194     EVT ValueVT = ValueVTs[Value];
195     EVT RegisterVT = TLI.getRegisterType(V->getContext(), ValueVT);
196 
197     unsigned NumRegs = TLI.getNumRegisters(V->getContext(), ValueVT);
198     for (unsigned i = 0; i != NumRegs; ++i) {
199       unsigned R = MakeReg(RegisterVT);
200       if (!FirstReg) FirstReg = R;
201     }
202   }
203   return FirstReg;
204 }
205 
206 /// AddCatchInfo - Extract the personality and type infos from an eh.selector
207 /// call, and add them to the specified machine basic block.
208 void llvm::AddCatchInfo(const CallInst &I, MachineModuleInfo *MMI,
209                         MachineBasicBlock *MBB) {
210   // Inform the MachineModuleInfo of the personality for this landing pad.
211   const ConstantExpr *CE = cast<ConstantExpr>(I.getOperand(2));
212   assert(CE->getOpcode() == Instruction::BitCast &&
213          isa<Function>(CE->getOperand(0)) &&
214          "Personality should be a function");
215   MMI->addPersonality(MBB, cast<Function>(CE->getOperand(0)));
216 
217   // Gather all the type infos for this landing pad and pass them along to
218   // MachineModuleInfo.
219   std::vector<const GlobalVariable *> TyInfo;
220   unsigned N = I.getNumOperands();
221 
222   for (unsigned i = N - 1; i > 2; --i) {
223     if (const ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i))) {
224       unsigned FilterLength = CI->getZExtValue();
225       unsigned FirstCatch = i + FilterLength + !FilterLength;
226       assert (FirstCatch <= N && "Invalid filter length");
227 
228       if (FirstCatch < N) {
229         TyInfo.reserve(N - FirstCatch);
230         for (unsigned j = FirstCatch; j < N; ++j)
231           TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
232         MMI->addCatchTypeInfo(MBB, TyInfo);
233         TyInfo.clear();
234       }
235 
236       if (!FilterLength) {
237         // Cleanup.
238         MMI->addCleanup(MBB);
239       } else {
240         // Filter.
241         TyInfo.reserve(FilterLength - 1);
242         for (unsigned j = i + 1; j < FirstCatch; ++j)
243           TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
244         MMI->addFilterTypeInfo(MBB, TyInfo);
245         TyInfo.clear();
246       }
247 
248       N = i;
249     }
250   }
251 
252   if (N > 3) {
253     TyInfo.reserve(N - 3);
254     for (unsigned j = 3; j < N; ++j)
255       TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
256     MMI->addCatchTypeInfo(MBB, TyInfo);
257   }
258 }
259 
260 void llvm::CopyCatchInfo(const BasicBlock *SrcBB, const BasicBlock *DestBB,
261                          MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) {
262   for (BasicBlock::const_iterator I = SrcBB->begin(), E = --SrcBB->end();
263        I != E; ++I)
264     if (const EHSelectorInst *EHSel = dyn_cast<EHSelectorInst>(I)) {
265       // Apply the catch info to DestBB.
266       AddCatchInfo(*EHSel, MMI, FLI.MBBMap[DestBB]);
267 #ifndef NDEBUG
268       if (!FLI.MBBMap[SrcBB]->isLandingPad())
269         FLI.CatchInfoFound.insert(EHSel);
270 #endif
271     }
272 }
273