← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/Utils/CloneFunction.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Transforms/Utils/CloneFunction.cpp
 
1
//===- CloneFunction.cpp - Clone a function into another function ---------===//
 
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 file implements the CloneFunctionInto interface, which is used as the
 
11
// low-level function cloner.  This is used by the CloneFunction and function
 
12
// inliner to do the dirty work of copying the body of a function around.
 
13
//
 
14
//===----------------------------------------------------------------------===//
 
15
 
 
16
#include "llvm/Transforms/Utils/Cloning.h"
 
17
#include "llvm/Constants.h"
 
18
#include "llvm/DerivedTypes.h"
 
19
#include "llvm/Instructions.h"
 
20
#include "llvm/IntrinsicInst.h"
 
21
#include "llvm/GlobalVariable.h"
 
22
#include "llvm/Function.h"
 
23
#include "llvm/LLVMContext.h"
 
24
#include "llvm/Metadata.h"
 
25
#include "llvm/Support/CFG.h"
 
26
#include "llvm/Transforms/Utils/ValueMapper.h"
 
27
#include "llvm/Analysis/ConstantFolding.h"
 
28
#include "llvm/Analysis/DebugInfo.h"
 
29
#include "llvm/ADT/SmallVector.h"
 
30
#include <map>
 
31
using namespace llvm;
 
32
 
 
33
// CloneBasicBlock - See comments in Cloning.h
 
34
BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
 
35
                                  DenseMap<const Value*, Value*> &ValueMap,
 
36
                                  const Twine &NameSuffix, Function *F,
 
37
                                  ClonedCodeInfo *CodeInfo) {
 
38
  BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F);
 
39
  if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
 
40
 
 
41
  bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
 
42
  
 
43
  // Loop over all instructions, and copy them over.
 
44
  for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
 
45
       II != IE; ++II) {
 
46
    Instruction *NewInst = II->clone();
 
47
    if (II->hasName())
 
48
      NewInst->setName(II->getName()+NameSuffix);
 
49
    NewBB->getInstList().push_back(NewInst);
 
50
    ValueMap[II] = NewInst;                // Add instruction map to value.
 
51
    
 
52
    hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
 
53
    if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
 
54
      if (isa<ConstantInt>(AI->getArraySize()))
 
55
        hasStaticAllocas = true;
 
56
      else
 
57
        hasDynamicAllocas = true;
 
58
    }
 
59
  }
 
60
  
 
61
  if (CodeInfo) {
 
62
    CodeInfo->ContainsCalls          |= hasCalls;
 
63
    CodeInfo->ContainsUnwinds        |= isa<UnwindInst>(BB->getTerminator());
 
64
    CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
 
65
    CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
 
66
                                        BB != &BB->getParent()->getEntryBlock();
 
67
  }
 
68
  return NewBB;
 
69
}
 
70
 
 
71
// Clone OldFunc into NewFunc, transforming the old arguments into references to
 
72
// ArgMap values.
 
73
//
 
74
void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
 
75
                             DenseMap<const Value*, Value*> &ValueMap,
 
76
                             SmallVectorImpl<ReturnInst*> &Returns,
 
77
                             const char *NameSuffix, ClonedCodeInfo *CodeInfo) {
 
78
  assert(NameSuffix && "NameSuffix cannot be null!");
 
79
 
 
80
#ifndef NDEBUG
 
81
  for (Function::const_arg_iterator I = OldFunc->arg_begin(), 
 
82
       E = OldFunc->arg_end(); I != E; ++I)
 
83
    assert(ValueMap.count(I) && "No mapping from source argument specified!");
 
84
#endif
 
85
 
 
86
  // Clone any attributes.
 
87
  if (NewFunc->arg_size() == OldFunc->arg_size())
 
88
    NewFunc->copyAttributesFrom(OldFunc);
 
89
  else {
 
90
    //Some arguments were deleted with the ValueMap. Copy arguments one by one
 
91
    for (Function::const_arg_iterator I = OldFunc->arg_begin(), 
 
92
           E = OldFunc->arg_end(); I != E; ++I)
 
93
      if (Argument* Anew = dyn_cast<Argument>(ValueMap[I]))
 
94
        Anew->addAttr( OldFunc->getAttributes()
 
95
                       .getParamAttributes(I->getArgNo() + 1));
 
96
    NewFunc->setAttributes(NewFunc->getAttributes()
 
97
                           .addAttr(0, OldFunc->getAttributes()
 
98
                                     .getRetAttributes()));
 
99
    NewFunc->setAttributes(NewFunc->getAttributes()
 
100
                           .addAttr(~0, OldFunc->getAttributes()
 
101
                                     .getFnAttributes()));
 
102
 
 
103
  }
 
104
 
 
105
  // Loop over all of the basic blocks in the function, cloning them as
 
106
  // appropriate.  Note that we save BE this way in order to handle cloning of
 
107
  // recursive functions into themselves.
 
108
  //
 
109
  for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
 
110
       BI != BE; ++BI) {
 
111
    const BasicBlock &BB = *BI;
 
112
 
 
113
    // Create a new basic block and copy instructions into it!
 
114
    BasicBlock *CBB = CloneBasicBlock(&BB, ValueMap, NameSuffix, NewFunc,
 
115
                                      CodeInfo);
 
116
    ValueMap[&BB] = CBB;                       // Add basic block mapping.
 
117
 
 
118
    if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator()))
 
119
      Returns.push_back(RI);
 
120
  }
 
121
 
 
122
  // Loop over all of the instructions in the function, fixing up operand
 
123
  // references as we go.  This uses ValueMap to do all the hard work.
 
124
  //
 
125
  for (Function::iterator BB = cast<BasicBlock>(ValueMap[OldFunc->begin()]),
 
126
         BE = NewFunc->end(); BB != BE; ++BB)
 
127
    // Loop over all instructions, fixing each one as we find it...
 
128
    for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
 
129
      RemapInstruction(II, ValueMap);
 
130
}
 
131
 
 
132
/// CloneFunction - Return a copy of the specified function, but without
 
133
/// embedding the function into another module.  Also, any references specified
 
134
/// in the ValueMap are changed to refer to their mapped value instead of the
 
135
/// original one.  If any of the arguments to the function are in the ValueMap,
 
136
/// the arguments are deleted from the resultant function.  The ValueMap is
 
137
/// updated to include mappings from all of the instructions and basicblocks in
 
138
/// the function from their old to new values.
 
139
///
 
140
Function *llvm::CloneFunction(const Function *F,
 
141
                              DenseMap<const Value*, Value*> &ValueMap,
 
142
                              ClonedCodeInfo *CodeInfo) {
 
143
  std::vector<const Type*> ArgTypes;
 
144
 
 
145
  // The user might be deleting arguments to the function by specifying them in
 
146
  // the ValueMap.  If so, we need to not add the arguments to the arg ty vector
 
147
  //
 
148
  for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
 
149
       I != E; ++I)
 
150
    if (ValueMap.count(I) == 0)  // Haven't mapped the argument to anything yet?
 
151
      ArgTypes.push_back(I->getType());
 
152
 
 
153
  // Create a new function type...
 
154
  FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(),
 
155
                                    ArgTypes, F->getFunctionType()->isVarArg());
 
156
 
 
157
  // Create the new function...
 
158
  Function *NewF = Function::Create(FTy, F->getLinkage(), F->getName());
 
159
 
 
160
  // Loop over the arguments, copying the names of the mapped arguments over...
 
161
  Function::arg_iterator DestI = NewF->arg_begin();
 
162
  for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
 
163
       I != E; ++I)
 
164
    if (ValueMap.count(I) == 0) {   // Is this argument preserved?
 
165
      DestI->setName(I->getName()); // Copy the name over...
 
166
      ValueMap[I] = DestI++;        // Add mapping to ValueMap
 
167
    }
 
168
 
 
169
  SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
 
170
  CloneFunctionInto(NewF, F, ValueMap, Returns, "", CodeInfo);
 
171
  return NewF;
 
172
}
 
173
 
 
174
 
 
175
 
 
176
namespace {
 
177
  /// PruningFunctionCloner - This class is a private class used to implement
 
178
  /// the CloneAndPruneFunctionInto method.
 
179
  struct PruningFunctionCloner {
 
180
    Function *NewFunc;
 
181
    const Function *OldFunc;
 
182
    DenseMap<const Value*, Value*> &ValueMap;
 
183
    SmallVectorImpl<ReturnInst*> &Returns;
 
184
    const char *NameSuffix;
 
185
    ClonedCodeInfo *CodeInfo;
 
186
    const TargetData *TD;
 
187
  public:
 
188
    PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
 
189
                          DenseMap<const Value*, Value*> &valueMap,
 
190
                          SmallVectorImpl<ReturnInst*> &returns,
 
191
                          const char *nameSuffix, 
 
192
                          ClonedCodeInfo *codeInfo,
 
193
                          const TargetData *td)
 
194
    : NewFunc(newFunc), OldFunc(oldFunc), ValueMap(valueMap), Returns(returns),
 
195
      NameSuffix(nameSuffix), CodeInfo(codeInfo), TD(td) {
 
196
    }
 
197
 
 
198
    /// CloneBlock - The specified block is found to be reachable, clone it and
 
199
    /// anything that it can reach.
 
200
    void CloneBlock(const BasicBlock *BB,
 
201
                    std::vector<const BasicBlock*> &ToClone);
 
202
    
 
203
  public:
 
204
    /// ConstantFoldMappedInstruction - Constant fold the specified instruction,
 
205
    /// mapping its operands through ValueMap if they are available.
 
206
    Constant *ConstantFoldMappedInstruction(const Instruction *I);
 
207
  };
 
208
}
 
209
 
 
210
/// CloneBlock - The specified block is found to be reachable, clone it and
 
211
/// anything that it can reach.
 
212
void PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
 
213
                                       std::vector<const BasicBlock*> &ToClone){
 
214
  Value *&BBEntry = ValueMap[BB];
 
215
 
 
216
  // Have we already cloned this block?
 
217
  if (BBEntry) return;
 
218
  
 
219
  // Nope, clone it now.
 
220
  BasicBlock *NewBB;
 
221
  BBEntry = NewBB = BasicBlock::Create(BB->getContext());
 
222
  if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
 
223
 
 
224
  bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
 
225
  
 
226
  // Loop over all instructions, and copy them over, DCE'ing as we go.  This
 
227
  // loop doesn't include the terminator.
 
228
  for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end();
 
229
       II != IE; ++II) {
 
230
    // If this instruction constant folds, don't bother cloning the instruction,
 
231
    // instead, just add the constant to the value map.
 
232
    if (Constant *C = ConstantFoldMappedInstruction(II)) {
 
233
      ValueMap[II] = C;
 
234
      continue;
 
235
    }
 
236
 
 
237
    Instruction *NewInst = II->clone();
 
238
    if (II->hasName())
 
239
      NewInst->setName(II->getName()+NameSuffix);
 
240
    NewBB->getInstList().push_back(NewInst);
 
241
    ValueMap[II] = NewInst;                // Add instruction map to value.
 
242
    
 
243
    hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
 
244
    if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
 
245
      if (isa<ConstantInt>(AI->getArraySize()))
 
246
        hasStaticAllocas = true;
 
247
      else
 
248
        hasDynamicAllocas = true;
 
249
    }
 
250
  }
 
251
  
 
252
  // Finally, clone over the terminator.
 
253
  const TerminatorInst *OldTI = BB->getTerminator();
 
254
  bool TerminatorDone = false;
 
255
  if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
 
256
    if (BI->isConditional()) {
 
257
      // If the condition was a known constant in the callee...
 
258
      ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
 
259
      // Or is a known constant in the caller...
 
260
      if (Cond == 0)  
 
261
        Cond = dyn_cast_or_null<ConstantInt>(ValueMap[BI->getCondition()]);
 
262
 
 
263
      // Constant fold to uncond branch!
 
264
      if (Cond) {
 
265
        BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
 
266
        ValueMap[OldTI] = BranchInst::Create(Dest, NewBB);
 
267
        ToClone.push_back(Dest);
 
268
        TerminatorDone = true;
 
269
      }
 
270
    }
 
271
  } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
 
272
    // If switching on a value known constant in the caller.
 
273
    ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
 
274
    if (Cond == 0)  // Or known constant after constant prop in the callee...
 
275
      Cond = dyn_cast_or_null<ConstantInt>(ValueMap[SI->getCondition()]);
 
276
    if (Cond) {     // Constant fold to uncond branch!
 
277
      BasicBlock *Dest = SI->getSuccessor(SI->findCaseValue(Cond));
 
278
      ValueMap[OldTI] = BranchInst::Create(Dest, NewBB);
 
279
      ToClone.push_back(Dest);
 
280
      TerminatorDone = true;
 
281
    }
 
282
  }
 
283
  
 
284
  if (!TerminatorDone) {
 
285
    Instruction *NewInst = OldTI->clone();
 
286
    if (OldTI->hasName())
 
287
      NewInst->setName(OldTI->getName()+NameSuffix);
 
288
    NewBB->getInstList().push_back(NewInst);
 
289
    ValueMap[OldTI] = NewInst;             // Add instruction map to value.
 
290
    
 
291
    // Recursively clone any reachable successor blocks.
 
292
    const TerminatorInst *TI = BB->getTerminator();
 
293
    for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 
294
      ToClone.push_back(TI->getSuccessor(i));
 
295
  }
 
296
  
 
297
  if (CodeInfo) {
 
298
    CodeInfo->ContainsCalls          |= hasCalls;
 
299
    CodeInfo->ContainsUnwinds        |= isa<UnwindInst>(OldTI);
 
300
    CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
 
301
    CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
 
302
      BB != &BB->getParent()->front();
 
303
  }
 
304
  
 
305
  if (ReturnInst *RI = dyn_cast<ReturnInst>(NewBB->getTerminator()))
 
306
    Returns.push_back(RI);
 
307
}
 
308
 
 
309
/// ConstantFoldMappedInstruction - Constant fold the specified instruction,
 
310
/// mapping its operands through ValueMap if they are available.
 
311
Constant *PruningFunctionCloner::
 
312
ConstantFoldMappedInstruction(const Instruction *I) {
 
313
  SmallVector<Constant*, 8> Ops;
 
314
  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 
315
    if (Constant *Op = dyn_cast_or_null<Constant>(MapValue(I->getOperand(i),
 
316
                                                           ValueMap)))
 
317
      Ops.push_back(Op);
 
318
    else
 
319
      return 0;  // All operands not constant!
 
320
 
 
321
  if (const CmpInst *CI = dyn_cast<CmpInst>(I))
 
322
    return ConstantFoldCompareInstOperands(CI->getPredicate(), Ops[0], Ops[1],
 
323
                                           TD);
 
324
 
 
325
  if (const LoadInst *LI = dyn_cast<LoadInst>(I))
 
326
    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0]))
 
327
      if (!LI->isVolatile() && CE->getOpcode() == Instruction::GetElementPtr)
 
328
        if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
 
329
          if (GV->isConstant() && GV->hasDefinitiveInitializer())
 
330
            return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(),
 
331
                                                          CE);
 
332
 
 
333
  return ConstantFoldInstOperands(I->getOpcode(), I->getType(), &Ops[0],
 
334
                                  Ops.size(), TD);
 
335
}
 
336
 
 
337
static MDNode *UpdateInlinedAtInfo(MDNode *InsnMD, MDNode *TheCallMD) {
 
338
  DILocation ILoc(InsnMD);
 
339
  if (ILoc.isNull()) return InsnMD;
 
340
 
 
341
  DILocation CallLoc(TheCallMD);
 
342
  if (CallLoc.isNull()) return InsnMD;
 
343
 
 
344
  DILocation OrigLocation = ILoc.getOrigLocation();
 
345
  MDNode *NewLoc = TheCallMD;
 
346
  if (!OrigLocation.isNull())
 
347
    NewLoc = UpdateInlinedAtInfo(OrigLocation.getNode(), TheCallMD);
 
348
 
 
349
  Value *MDVs[] = {
 
350
    InsnMD->getOperand(0), // Line
 
351
    InsnMD->getOperand(1), // Col
 
352
    InsnMD->getOperand(2), // Scope
 
353
    NewLoc
 
354
  };
 
355
  return MDNode::get(InsnMD->getContext(), MDVs, 4);
 
356
}
 
357
 
 
358
/// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
 
359
/// except that it does some simple constant prop and DCE on the fly.  The
 
360
/// effect of this is to copy significantly less code in cases where (for
 
361
/// example) a function call with constant arguments is inlined, and those
 
362
/// constant arguments cause a significant amount of code in the callee to be
 
363
/// dead.  Since this doesn't produce an exact copy of the input, it can't be
 
364
/// used for things like CloneFunction or CloneModule.
 
365
void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
 
366
                                     DenseMap<const Value*, Value*> &ValueMap,
 
367
                                     SmallVectorImpl<ReturnInst*> &Returns,
 
368
                                     const char *NameSuffix, 
 
369
                                     ClonedCodeInfo *CodeInfo,
 
370
                                     const TargetData *TD,
 
371
                                     Instruction *TheCall) {
 
372
  assert(NameSuffix && "NameSuffix cannot be null!");
 
373
  
 
374
#ifndef NDEBUG
 
375
  for (Function::const_arg_iterator II = OldFunc->arg_begin(), 
 
376
       E = OldFunc->arg_end(); II != E; ++II)
 
377
    assert(ValueMap.count(II) && "No mapping from source argument specified!");
 
378
#endif
 
379
 
 
380
  PruningFunctionCloner PFC(NewFunc, OldFunc, ValueMap, Returns,
 
381
                            NameSuffix, CodeInfo, TD);
 
382
 
 
383
  // Clone the entry block, and anything recursively reachable from it.
 
384
  std::vector<const BasicBlock*> CloneWorklist;
 
385
  CloneWorklist.push_back(&OldFunc->getEntryBlock());
 
386
  while (!CloneWorklist.empty()) {
 
387
    const BasicBlock *BB = CloneWorklist.back();
 
388
    CloneWorklist.pop_back();
 
389
    PFC.CloneBlock(BB, CloneWorklist);
 
390
  }
 
391
  
 
392
  // Loop over all of the basic blocks in the old function.  If the block was
 
393
  // reachable, we have cloned it and the old block is now in the value map:
 
394
  // insert it into the new function in the right order.  If not, ignore it.
 
395
  //
 
396
  // Defer PHI resolution until rest of function is resolved.
 
397
  SmallVector<const PHINode*, 16> PHIToResolve;
 
398
  for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
 
399
       BI != BE; ++BI) {
 
400
    BasicBlock *NewBB = cast_or_null<BasicBlock>(ValueMap[BI]);
 
401
    if (NewBB == 0) continue;  // Dead block.
 
402
 
 
403
    // Add the new block to the new function.
 
404
    NewFunc->getBasicBlockList().push_back(NewBB);
 
405
    
 
406
    // Loop over all of the instructions in the block, fixing up operand
 
407
    // references as we go.  This uses ValueMap to do all the hard work.
 
408
    //
 
409
    BasicBlock::iterator I = NewBB->begin();
 
410
 
 
411
    unsigned DbgKind = OldFunc->getContext().getMDKindID("dbg");
 
412
    MDNode *TheCallMD = NULL;
 
413
    if (TheCall && TheCall->hasMetadata()) 
 
414
      TheCallMD = TheCall->getMetadata(DbgKind);
 
415
    
 
416
    // Handle PHI nodes specially, as we have to remove references to dead
 
417
    // blocks.
 
418
    if (PHINode *PN = dyn_cast<PHINode>(I)) {
 
419
      // Skip over all PHI nodes, remembering them for later.
 
420
      BasicBlock::const_iterator OldI = BI->begin();
 
421
      for (; (PN = dyn_cast<PHINode>(I)); ++I, ++OldI) {
 
422
        if (I->hasMetadata()) {
 
423
          if (TheCallMD) {
 
424
            if (MDNode *IMD = I->getMetadata(DbgKind)) {
 
425
              MDNode *NewMD = UpdateInlinedAtInfo(IMD, TheCallMD);
 
426
              I->setMetadata(DbgKind, NewMD);
 
427
            }
 
428
          } else {
 
429
            // The cloned instruction has dbg info but the call instruction
 
430
            // does not have dbg info. Remove dbg info from cloned instruction.
 
431
            I->setMetadata(DbgKind, 0);
 
432
          }
 
433
        }
 
434
        PHIToResolve.push_back(cast<PHINode>(OldI));
 
435
      }
 
436
    }
 
437
    
 
438
    // FIXME:
 
439
    // FIXME:
 
440
    // FIXME: Unclone all this metadata stuff.
 
441
    // FIXME:
 
442
    // FIXME:
 
443
    
 
444
    // Otherwise, remap the rest of the instructions normally.
 
445
    for (; I != NewBB->end(); ++I) {
 
446
      if (I->hasMetadata()) {
 
447
        if (TheCallMD) {
 
448
          if (MDNode *IMD = I->getMetadata(DbgKind)) {
 
449
            MDNode *NewMD = UpdateInlinedAtInfo(IMD, TheCallMD);
 
450
            I->setMetadata(DbgKind, NewMD);
 
451
          }
 
452
        } else {
 
453
          // The cloned instruction has dbg info but the call instruction
 
454
          // does not have dbg info. Remove dbg info from cloned instruction.
 
455
          I->setMetadata(DbgKind, 0);
 
456
        }
 
457
      }
 
458
      RemapInstruction(I, ValueMap);
 
459
    }
 
460
  }
 
461
  
 
462
  // Defer PHI resolution until rest of function is resolved, PHI resolution
 
463
  // requires the CFG to be up-to-date.
 
464
  for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
 
465
    const PHINode *OPN = PHIToResolve[phino];
 
466
    unsigned NumPreds = OPN->getNumIncomingValues();
 
467
    const BasicBlock *OldBB = OPN->getParent();
 
468
    BasicBlock *NewBB = cast<BasicBlock>(ValueMap[OldBB]);
 
469
 
 
470
    // Map operands for blocks that are live and remove operands for blocks
 
471
    // that are dead.
 
472
    for (; phino != PHIToResolve.size() &&
 
473
         PHIToResolve[phino]->getParent() == OldBB; ++phino) {
 
474
      OPN = PHIToResolve[phino];
 
475
      PHINode *PN = cast<PHINode>(ValueMap[OPN]);
 
476
      for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
 
477
        if (BasicBlock *MappedBlock = 
 
478
            cast_or_null<BasicBlock>(ValueMap[PN->getIncomingBlock(pred)])) {
 
479
          Value *InVal = MapValue(PN->getIncomingValue(pred),
 
480
                                  ValueMap);
 
481
          assert(InVal && "Unknown input value?");
 
482
          PN->setIncomingValue(pred, InVal);
 
483
          PN->setIncomingBlock(pred, MappedBlock);
 
484
        } else {
 
485
          PN->removeIncomingValue(pred, false);
 
486
          --pred, --e;  // Revisit the next entry.
 
487
        }
 
488
      } 
 
489
    }
 
490
    
 
491
    // The loop above has removed PHI entries for those blocks that are dead
 
492
    // and has updated others.  However, if a block is live (i.e. copied over)
 
493
    // but its terminator has been changed to not go to this block, then our
 
494
    // phi nodes will have invalid entries.  Update the PHI nodes in this
 
495
    // case.
 
496
    PHINode *PN = cast<PHINode>(NewBB->begin());
 
497
    NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
 
498
    if (NumPreds != PN->getNumIncomingValues()) {
 
499
      assert(NumPreds < PN->getNumIncomingValues());
 
500
      // Count how many times each predecessor comes to this block.
 
501
      std::map<BasicBlock*, unsigned> PredCount;
 
502
      for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
 
503
           PI != E; ++PI)
 
504
        --PredCount[*PI];
 
505
      
 
506
      // Figure out how many entries to remove from each PHI.
 
507
      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 
508
        ++PredCount[PN->getIncomingBlock(i)];
 
509
      
 
510
      // At this point, the excess predecessor entries are positive in the
 
511
      // map.  Loop over all of the PHIs and remove excess predecessor
 
512
      // entries.
 
513
      BasicBlock::iterator I = NewBB->begin();
 
514
      for (; (PN = dyn_cast<PHINode>(I)); ++I) {
 
515
        for (std::map<BasicBlock*, unsigned>::iterator PCI =PredCount.begin(),
 
516
             E = PredCount.end(); PCI != E; ++PCI) {
 
517
          BasicBlock *Pred     = PCI->first;
 
518
          for (unsigned NumToRemove = PCI->second; NumToRemove; --NumToRemove)
 
519
            PN->removeIncomingValue(Pred, false);
 
520
        }
 
521
      }
 
522
    }
 
523
    
 
524
    // If the loops above have made these phi nodes have 0 or 1 operand,
 
525
    // replace them with undef or the input value.  We must do this for
 
526
    // correctness, because 0-operand phis are not valid.
 
527
    PN = cast<PHINode>(NewBB->begin());
 
528
    if (PN->getNumIncomingValues() == 0) {
 
529
      BasicBlock::iterator I = NewBB->begin();
 
530
      BasicBlock::const_iterator OldI = OldBB->begin();
 
531
      while ((PN = dyn_cast<PHINode>(I++))) {
 
532
        Value *NV = UndefValue::get(PN->getType());
 
533
        PN->replaceAllUsesWith(NV);
 
534
        assert(ValueMap[OldI] == PN && "ValueMap mismatch");
 
535
        ValueMap[OldI] = NV;
 
536
        PN->eraseFromParent();
 
537
        ++OldI;
 
538
      }
 
539
    }
 
540
    // NOTE: We cannot eliminate single entry phi nodes here, because of
 
541
    // ValueMap.  Single entry phi nodes can have multiple ValueMap entries
 
542
    // pointing at them.  Thus, deleting one would require scanning the ValueMap
 
543
    // to update any entries in it that would require that.  This would be
 
544
    // really slow.
 
545
  }
 
546
  
 
547
  // Now that the inlined function body has been fully constructed, go through
 
548
  // and zap unconditional fall-through branches.  This happen all the time when
 
549
  // specializing code: code specialization turns conditional branches into
 
550
  // uncond branches, and this code folds them.
 
551
  Function::iterator I = cast<BasicBlock>(ValueMap[&OldFunc->getEntryBlock()]);
 
552
  while (I != NewFunc->end()) {
 
553
    BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
 
554
    if (!BI || BI->isConditional()) { ++I; continue; }
 
555
    
 
556
    // Note that we can't eliminate uncond branches if the destination has
 
557
    // single-entry PHI nodes.  Eliminating the single-entry phi nodes would
 
558
    // require scanning the ValueMap to update any entries that point to the phi
 
559
    // node.
 
560
    BasicBlock *Dest = BI->getSuccessor(0);
 
561
    if (!Dest->getSinglePredecessor() || isa<PHINode>(Dest->begin())) {
 
562
      ++I; continue;
 
563
    }
 
564
    
 
565
    // We know all single-entry PHI nodes in the inlined function have been
 
566
    // removed, so we just need to splice the blocks.
 
567
    BI->eraseFromParent();
 
568
    
 
569
    // Move all the instructions in the succ to the pred.
 
570
    I->getInstList().splice(I->end(), Dest->getInstList());
 
571
    
 
572
    // Make all PHI nodes that referred to Dest now refer to I as their source.
 
573
    Dest->replaceAllUsesWith(I);
 
574
 
 
575
    // Remove the dest block.
 
576
    Dest->eraseFromParent();
 
577
    
 
578
    // Do not increment I, iteratively merge all things this block branches to.
 
579
  }
 
580
}