← 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/LCSSA.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/LCSSA.cpp
 
1
//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===//
 
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 pass transforms loops by placing phi nodes at the end of the loops for
 
11
// all values that are live across the loop boundary.  For example, it turns
 
12
// the left into the right code:
 
13
// 
 
14
// for (...)                for (...)
 
15
//   if (c)                   if (c)
 
16
//     X1 = ...                 X1 = ...
 
17
//   else                     else
 
18
//     X2 = ...                 X2 = ...
 
19
//   X3 = phi(X1, X2)         X3 = phi(X1, X2)
 
20
// ... = X3 + 4             X4 = phi(X3)
 
21
//                          ... = X4 + 4
 
22
//
 
23
// This is still valid LLVM; the extra phi nodes are purely redundant, and will
 
24
// be trivially eliminated by InstCombine.  The major benefit of this 
 
25
// transformation is that it makes many other loop optimizations, such as 
 
26
// LoopUnswitching, simpler.
 
27
//
 
28
//===----------------------------------------------------------------------===//
 
29
 
 
30
#define DEBUG_TYPE "lcssa"
 
31
#include "llvm/Transforms/Scalar.h"
 
32
#include "llvm/Constants.h"
 
33
#include "llvm/Pass.h"
 
34
#include "llvm/Function.h"
 
35
#include "llvm/Instructions.h"
 
36
#include "llvm/Analysis/Dominators.h"
 
37
#include "llvm/Analysis/LoopPass.h"
 
38
#include "llvm/Analysis/ScalarEvolution.h"
 
39
#include "llvm/Transforms/Utils/SSAUpdater.h"
 
40
#include "llvm/ADT/Statistic.h"
 
41
#include "llvm/ADT/STLExtras.h"
 
42
#include "llvm/Support/PredIteratorCache.h"
 
43
using namespace llvm;
 
44
 
 
45
STATISTIC(NumLCSSA, "Number of live out of a loop variables");
 
46
 
 
47
namespace {
 
48
  struct LCSSA : public LoopPass {
 
49
    static char ID; // Pass identification, replacement for typeid
 
50
    LCSSA() : LoopPass(&ID) {}
 
51
 
 
52
    // Cached analysis information for the current function.
 
53
    DominatorTree *DT;
 
54
    std::vector<BasicBlock*> LoopBlocks;
 
55
    PredIteratorCache PredCache;
 
56
    Loop *L;
 
57
    
 
58
    virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
 
59
 
 
60
    /// This transformation requires natural loop information & requires that
 
61
    /// loop preheaders be inserted into the CFG.  It maintains both of these,
 
62
    /// as well as the CFG.  It also requires dominator information.
 
63
    ///
 
64
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
65
      AU.setPreservesCFG();
 
66
 
 
67
      // LCSSA doesn't actually require LoopSimplify, but the PassManager
 
68
      // doesn't know how to schedule LoopSimplify by itself.
 
69
      AU.addRequiredID(LoopSimplifyID);
 
70
      AU.addPreservedID(LoopSimplifyID);
 
71
      AU.addRequiredTransitive<LoopInfo>();
 
72
      AU.addPreserved<LoopInfo>();
 
73
      AU.addRequiredTransitive<DominatorTree>();
 
74
      AU.addPreserved<ScalarEvolution>();
 
75
      AU.addPreserved<DominatorTree>();
 
76
 
 
77
      // Request DominanceFrontier now, even though LCSSA does
 
78
      // not use it. This allows Pass Manager to schedule Dominance
 
79
      // Frontier early enough such that one LPPassManager can handle
 
80
      // multiple loop transformation passes.
 
81
      AU.addRequired<DominanceFrontier>(); 
 
82
      AU.addPreserved<DominanceFrontier>();
 
83
    }
 
84
  private:
 
85
    bool ProcessInstruction(Instruction *Inst,
 
86
                            const SmallVectorImpl<BasicBlock*> &ExitBlocks);
 
87
    
 
88
    /// verifyAnalysis() - Verify loop nest.
 
89
    virtual void verifyAnalysis() const {
 
90
      // Check the special guarantees that LCSSA makes.
 
91
      assert(L->isLCSSAForm() && "LCSSA form not preserved!");
 
92
    }
 
93
 
 
94
    /// inLoop - returns true if the given block is within the current loop
 
95
    bool inLoop(BasicBlock *B) const {
 
96
      return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
 
97
    }
 
98
  };
 
99
}
 
100
  
 
101
char LCSSA::ID = 0;
 
102
static RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass");
 
103
 
 
104
Pass *llvm::createLCSSAPass() { return new LCSSA(); }
 
105
const PassInfo *const llvm::LCSSAID = &X;
 
106
 
 
107
 
 
108
/// BlockDominatesAnExit - Return true if the specified block dominates at least
 
109
/// one of the blocks in the specified list.
 
110
static bool BlockDominatesAnExit(BasicBlock *BB,
 
111
                                 const SmallVectorImpl<BasicBlock*> &ExitBlocks,
 
112
                                 DominatorTree *DT) {
 
113
  DomTreeNode *DomNode = DT->getNode(BB);
 
114
  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
 
115
    if (DT->dominates(DomNode, DT->getNode(ExitBlocks[i])))
 
116
      return true;
 
117
 
 
118
  return false;
 
119
}
 
120
 
 
121
 
 
122
/// runOnFunction - Process all loops in the function, inner-most out.
 
123
bool LCSSA::runOnLoop(Loop *TheLoop, LPPassManager &LPM) {
 
124
  L = TheLoop;
 
125
  
 
126
  DT = &getAnalysis<DominatorTree>();
 
127
 
 
128
  // Get the set of exiting blocks.
 
129
  SmallVector<BasicBlock*, 8> ExitBlocks;
 
130
  L->getExitBlocks(ExitBlocks);
 
131
  
 
132
  if (ExitBlocks.empty())
 
133
    return false;
 
134
  
 
135
  // Speed up queries by creating a sorted vector of blocks.
 
136
  LoopBlocks.clear();
 
137
  LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
 
138
  array_pod_sort(LoopBlocks.begin(), LoopBlocks.end());
 
139
  
 
140
  // Look at all the instructions in the loop, checking to see if they have uses
 
141
  // outside the loop.  If so, rewrite those uses.
 
142
  bool MadeChange = false;
 
143
  
 
144
  for (Loop::block_iterator BBI = L->block_begin(), E = L->block_end();
 
145
       BBI != E; ++BBI) {
 
146
    BasicBlock *BB = *BBI;
 
147
    
 
148
    // For large loops, avoid use-scanning by using dominance information:  In
 
149
    // particular, if a block does not dominate any of the loop exits, then none
 
150
    // of the values defined in the block could be used outside the loop.
 
151
    if (!BlockDominatesAnExit(BB, ExitBlocks, DT))
 
152
      continue;
 
153
    
 
154
    for (BasicBlock::iterator I = BB->begin(), E = BB->end();
 
155
         I != E; ++I) {
 
156
      // Reject two common cases fast: instructions with no uses (like stores)
 
157
      // and instructions with one use that is in the same block as this.
 
158
      if (I->use_empty() ||
 
159
          (I->hasOneUse() && I->use_back()->getParent() == BB &&
 
160
           !isa<PHINode>(I->use_back())))
 
161
        continue;
 
162
      
 
163
      MadeChange |= ProcessInstruction(I, ExitBlocks);
 
164
    }
 
165
  }
 
166
  
 
167
  assert(L->isLCSSAForm());
 
168
  PredCache.clear();
 
169
 
 
170
  return MadeChange;
 
171
}
 
172
 
 
173
/// isExitBlock - Return true if the specified block is in the list.
 
174
static bool isExitBlock(BasicBlock *BB,
 
175
                        const SmallVectorImpl<BasicBlock*> &ExitBlocks) {
 
176
  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
 
177
    if (ExitBlocks[i] == BB)
 
178
      return true;
 
179
  return false;
 
180
}
 
181
 
 
182
/// ProcessInstruction - Given an instruction in the loop, check to see if it
 
183
/// has any uses that are outside the current loop.  If so, insert LCSSA PHI
 
184
/// nodes and rewrite the uses.
 
185
bool LCSSA::ProcessInstruction(Instruction *Inst,
 
186
                               const SmallVectorImpl<BasicBlock*> &ExitBlocks) {
 
187
  SmallVector<Use*, 16> UsesToRewrite;
 
188
  
 
189
  BasicBlock *InstBB = Inst->getParent();
 
190
  
 
191
  for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end();
 
192
       UI != E; ++UI) {
 
193
    BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
 
194
    if (PHINode *PN = dyn_cast<PHINode>(*UI))
 
195
      UserBB = PN->getIncomingBlock(UI);
 
196
    
 
197
    if (InstBB != UserBB && !inLoop(UserBB))
 
198
      UsesToRewrite.push_back(&UI.getUse());
 
199
  }
 
200
  
 
201
  // If there are no uses outside the loop, exit with no change.
 
202
  if (UsesToRewrite.empty()) return false;
 
203
  
 
204
  ++NumLCSSA; // We are applying the transformation
 
205
 
 
206
  // Invoke instructions are special in that their result value is not available
 
207
  // along their unwind edge. The code below tests to see whether DomBB dominates
 
208
  // the value, so adjust DomBB to the normal destination block, which is
 
209
  // effectively where the value is first usable.
 
210
  BasicBlock *DomBB = Inst->getParent();
 
211
  if (InvokeInst *Inv = dyn_cast<InvokeInst>(Inst))
 
212
    DomBB = Inv->getNormalDest();
 
213
 
 
214
  DomTreeNode *DomNode = DT->getNode(DomBB);
 
215
 
 
216
  SSAUpdater SSAUpdate;
 
217
  SSAUpdate.Initialize(Inst);
 
218
  
 
219
  // Insert the LCSSA phi's into all of the exit blocks dominated by the
 
220
  // value, and add them to the Phi's map.
 
221
  for (SmallVectorImpl<BasicBlock*>::const_iterator BBI = ExitBlocks.begin(),
 
222
      BBE = ExitBlocks.end(); BBI != BBE; ++BBI) {
 
223
    BasicBlock *ExitBB = *BBI;
 
224
    if (!DT->dominates(DomNode, DT->getNode(ExitBB))) continue;
 
225
    
 
226
    // If we already inserted something for this BB, don't reprocess it.
 
227
    if (SSAUpdate.HasValueForBlock(ExitBB)) continue;
 
228
    
 
229
    PHINode *PN = PHINode::Create(Inst->getType(), Inst->getName()+".lcssa",
 
230
                                  ExitBB->begin());
 
231
    PN->reserveOperandSpace(PredCache.GetNumPreds(ExitBB));
 
232
 
 
233
    // Add inputs from inside the loop for this PHI.
 
234
    for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) {
 
235
      PN->addIncoming(Inst, *PI);
 
236
 
 
237
      // If the exit block has a predecessor not within the loop, arrange for
 
238
      // the incoming value use corresponding to that predecessor to be
 
239
      // rewritten in terms of a different LCSSA PHI.
 
240
      if (!inLoop(*PI))
 
241
        UsesToRewrite.push_back(
 
242
          &PN->getOperandUse(
 
243
            PN->getOperandNumForIncomingValue(PN->getNumIncomingValues()-1)));
 
244
    }
 
245
    
 
246
    // Remember that this phi makes the value alive in this block.
 
247
    SSAUpdate.AddAvailableValue(ExitBB, PN);
 
248
  }
 
249
  
 
250
  // Rewrite all uses outside the loop in terms of the new PHIs we just
 
251
  // inserted.
 
252
  for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) {
 
253
    // If this use is in an exit block, rewrite to use the newly inserted PHI.
 
254
    // This is required for correctness because SSAUpdate doesn't handle uses in
 
255
    // the same block.  It assumes the PHI we inserted is at the end of the
 
256
    // block.
 
257
    Instruction *User = cast<Instruction>(UsesToRewrite[i]->getUser());
 
258
    BasicBlock *UserBB = User->getParent();
 
259
    if (PHINode *PN = dyn_cast<PHINode>(User))
 
260
      UserBB = PN->getIncomingBlock(*UsesToRewrite[i]);
 
261
 
 
262
    if (isa<PHINode>(UserBB->begin()) &&
 
263
        isExitBlock(UserBB, ExitBlocks)) {
 
264
      UsesToRewrite[i]->set(UserBB->begin());
 
265
      continue;
 
266
    }
 
267
    
 
268
    // Otherwise, do full PHI insertion.
 
269
    SSAUpdate.RewriteUse(*UsesToRewrite[i]);
 
270
  }
 
271
  
 
272
  return true;
 
273
}
 
274