← 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/Analysis/LoopPass.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/Analysis/LoopPass.cpp
 
1
//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
 
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 LoopPass and LPPassManager. All loop optimization
 
11
// and transformation passes are derived from LoopPass. LPPassManager is
 
12
// responsible for managing LoopPasses.
 
13
//
 
14
//===----------------------------------------------------------------------===//
 
15
 
 
16
#include "llvm/Analysis/LoopPass.h"
 
17
using namespace llvm;
 
18
 
 
19
//===----------------------------------------------------------------------===//
 
20
// LPPassManager
 
21
//
 
22
 
 
23
char LPPassManager::ID = 0;
 
24
 
 
25
LPPassManager::LPPassManager(int Depth) 
 
26
  : FunctionPass(&ID), PMDataManager(Depth) { 
 
27
  skipThisLoop = false;
 
28
  redoThisLoop = false;
 
29
  LI = NULL;
 
30
  CurrentLoop = NULL;
 
31
}
 
32
 
 
33
/// Delete loop from the loop queue and loop hierarchy (LoopInfo). 
 
34
void LPPassManager::deleteLoopFromQueue(Loop *L) {
 
35
 
 
36
  if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop.
 
37
    // Reparent all of the blocks in this loop.  Since BBLoop had a parent,
 
38
    // they are now all in it.
 
39
    for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 
 
40
         I != E; ++I)
 
41
      if (LI->getLoopFor(*I) == L)    // Don't change blocks in subloops.
 
42
        LI->changeLoopFor(*I, ParentLoop);
 
43
    
 
44
    // Remove the loop from its parent loop.
 
45
    for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();;
 
46
         ++I) {
 
47
      assert(I != E && "Couldn't find loop");
 
48
      if (*I == L) {
 
49
        ParentLoop->removeChildLoop(I);
 
50
        break;
 
51
      }
 
52
    }
 
53
    
 
54
    // Move all subloops into the parent loop.
 
55
    while (!L->empty())
 
56
      ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1));
 
57
  } else {
 
58
    // Reparent all of the blocks in this loop.  Since BBLoop had no parent,
 
59
    // they no longer in a loop at all.
 
60
    
 
61
    for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
 
62
      // Don't change blocks in subloops.
 
63
      if (LI->getLoopFor(L->getBlocks()[i]) == L) {
 
64
        LI->removeBlock(L->getBlocks()[i]);
 
65
        --i;
 
66
      }
 
67
    }
 
68
 
 
69
    // Remove the loop from the top-level LoopInfo object.
 
70
    for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) {
 
71
      assert(I != E && "Couldn't find loop");
 
72
      if (*I == L) {
 
73
        LI->removeLoop(I);
 
74
        break;
 
75
      }
 
76
    }
 
77
 
 
78
    // Move all of the subloops to the top-level.
 
79
    while (!L->empty())
 
80
      LI->addTopLevelLoop(L->removeChildLoop(L->end()-1));
 
81
  }
 
82
 
 
83
  delete L;
 
84
 
 
85
  // If L is current loop then skip rest of the passes and let
 
86
  // runOnFunction remove L from LQ. Otherwise, remove L from LQ now
 
87
  // and continue applying other passes on CurrentLoop.
 
88
  if (CurrentLoop == L) {
 
89
    skipThisLoop = true;
 
90
    return;
 
91
  }
 
92
 
 
93
  for (std::deque<Loop *>::iterator I = LQ.begin(),
 
94
         E = LQ.end(); I != E; ++I) {
 
95
    if (*I == L) {
 
96
      LQ.erase(I);
 
97
      break;
 
98
    }
 
99
  }
 
100
}
 
101
 
 
102
// Inset loop into loop nest (LoopInfo) and loop queue (LQ).
 
103
void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) {
 
104
 
 
105
  assert (CurrentLoop != L && "Cannot insert CurrentLoop");
 
106
 
 
107
  // Insert into loop nest
 
108
  if (ParentLoop)
 
109
    ParentLoop->addChildLoop(L);
 
110
  else
 
111
    LI->addTopLevelLoop(L);
 
112
 
 
113
  insertLoopIntoQueue(L);
 
114
}
 
115
 
 
116
void LPPassManager::insertLoopIntoQueue(Loop *L) {
 
117
  // Insert L into loop queue
 
118
  if (L == CurrentLoop) 
 
119
    redoLoop(L);
 
120
  else if (!L->getParentLoop())
 
121
    // This is top level loop. 
 
122
    LQ.push_front(L);
 
123
  else {
 
124
    // Insert L after the parent loop.
 
125
    for (std::deque<Loop *>::iterator I = LQ.begin(),
 
126
           E = LQ.end(); I != E; ++I) {
 
127
      if (*I == L->getParentLoop()) {
 
128
        // deque does not support insert after.
 
129
        ++I;
 
130
        LQ.insert(I, 1, L);
 
131
        break;
 
132
      }
 
133
    }
 
134
  }
 
135
}
 
136
 
 
137
// Reoptimize this loop. LPPassManager will re-insert this loop into the
 
138
// queue. This allows LoopPass to change loop nest for the loop. This
 
139
// utility may send LPPassManager into infinite loops so use caution.
 
140
void LPPassManager::redoLoop(Loop *L) {
 
141
  assert (CurrentLoop == L && "Can redo only CurrentLoop");
 
142
  redoThisLoop = true;
 
143
}
 
144
 
 
145
/// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
 
146
/// all loop passes.
 
147
void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, 
 
148
                                                  BasicBlock *To, Loop *L) {
 
149
  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {  
 
150
    LoopPass *LP = (LoopPass *)getContainedPass(Index);
 
151
    LP->cloneBasicBlockAnalysis(From, To, L);
 
152
  }
 
153
}
 
154
 
 
155
/// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
 
156
void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
 
157
  if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
 
158
    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; 
 
159
         ++BI) {
 
160
      Instruction &I = *BI;
 
161
      deleteSimpleAnalysisValue(&I, L);
 
162
    }
 
163
  }
 
164
  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {  
 
165
    LoopPass *LP = (LoopPass *)getContainedPass(Index);
 
166
    LP->deleteAnalysisValue(V, L);
 
167
  }
 
168
}
 
169
 
 
170
 
 
171
// Recurse through all subloops and all loops  into LQ.
 
172
static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
 
173
  LQ.push_back(L);
 
174
  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 
175
    addLoopIntoQueue(*I, LQ);
 
176
}
 
177
 
 
178
/// Pass Manager itself does not invalidate any analysis info.
 
179
void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
 
180
  // LPPassManager needs LoopInfo. In the long term LoopInfo class will 
 
181
  // become part of LPPassManager.
 
182
  Info.addRequired<LoopInfo>();
 
183
  Info.setPreservesAll();
 
184
}
 
185
 
 
186
/// run - Execute all of the passes scheduled for execution.  Keep track of
 
187
/// whether any of the passes modifies the function, and if so, return true.
 
188
bool LPPassManager::runOnFunction(Function &F) {
 
189
  LI = &getAnalysis<LoopInfo>();
 
190
  bool Changed = false;
 
191
 
 
192
  // Collect inherited analysis from Module level pass manager.
 
193
  populateInheritedAnalysis(TPM->activeStack);
 
194
 
 
195
  // Populate Loop Queue
 
196
  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
 
197
    addLoopIntoQueue(*I, LQ);
 
198
 
 
199
  if (LQ.empty()) // No loops, skip calling finalizers
 
200
    return false;
 
201
 
 
202
  // Initialization
 
203
  for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
 
204
       I != E; ++I) {
 
205
    Loop *L = *I;
 
206
    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {  
 
207
      LoopPass *P = (LoopPass*)getContainedPass(Index);
 
208
      Changed |= P->doInitialization(L, *this);
 
209
    }
 
210
  }
 
211
 
 
212
  // Walk Loops
 
213
  while (!LQ.empty()) {
 
214
      
 
215
    CurrentLoop  = LQ.back();
 
216
    skipThisLoop = false;
 
217
    redoThisLoop = false;
 
218
 
 
219
    // Run all passes on the current Loop.
 
220
    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {  
 
221
      LoopPass *P = (LoopPass*)getContainedPass(Index);
 
222
 
 
223
      dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
 
224
                   CurrentLoop->getHeader()->getNameStr());
 
225
      dumpRequiredSet(P);
 
226
 
 
227
      initializeAnalysisImpl(P);
 
228
 
 
229
      {
 
230
        PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
 
231
        Timer *T = StartPassTimer(P);
 
232
        Changed |= P->runOnLoop(CurrentLoop, *this);
 
233
        StopPassTimer(P, T);
 
234
      }
 
235
 
 
236
      if (Changed)
 
237
        dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
 
238
                     skipThisLoop ? "<deleted>" :
 
239
                                    CurrentLoop->getHeader()->getNameStr());
 
240
      dumpPreservedSet(P);
 
241
 
 
242
      if (!skipThisLoop) {
 
243
        // Manually check that this loop is still healthy. This is done
 
244
        // instead of relying on LoopInfo::verifyLoop since LoopInfo
 
245
        // is a function pass and it's really expensive to verify every
 
246
        // loop in the function every time. That level of checking can be
 
247
        // enabled with the -verify-loop-info option.
 
248
        Timer *T = StartPassTimer(LI);
 
249
        CurrentLoop->verifyLoop();
 
250
        StopPassTimer(LI, T);
 
251
 
 
252
        // Then call the regular verifyAnalysis functions.
 
253
        verifyPreservedAnalysis(P);
 
254
      }
 
255
 
 
256
      removeNotPreservedAnalysis(P);
 
257
      recordAvailableAnalysis(P);
 
258
      removeDeadPasses(P,
 
259
                       skipThisLoop ? "<deleted>" :
 
260
                                      CurrentLoop->getHeader()->getNameStr(),
 
261
                       ON_LOOP_MSG);
 
262
 
 
263
      if (skipThisLoop)
 
264
        // Do not run other passes on this loop.
 
265
        break;
 
266
    }
 
267
    
 
268
    // If the loop was deleted, release all the loop passes. This frees up
 
269
    // some memory, and avoids trouble with the pass manager trying to call
 
270
    // verifyAnalysis on them.
 
271
    if (skipThisLoop)
 
272
      for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {  
 
273
        Pass *P = getContainedPass(Index);
 
274
        freePass(P, "<deleted>", ON_LOOP_MSG);
 
275
      }
 
276
 
 
277
    // Pop the loop from queue after running all passes.
 
278
    LQ.pop_back();
 
279
    
 
280
    if (redoThisLoop)
 
281
      LQ.push_back(CurrentLoop);
 
282
  }
 
283
  
 
284
  // Finalization
 
285
  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 
286
    LoopPass *P = (LoopPass *)getContainedPass(Index);
 
287
    Changed |= P->doFinalization();
 
288
  }
 
289
 
 
290
  return Changed;
 
291
}
 
292
 
 
293
/// Print passes managed by this manager
 
294
void LPPassManager::dumpPassStructure(unsigned Offset) {
 
295
  errs().indent(Offset*2) << "Loop Pass Manager\n";
 
296
  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 
297
    Pass *P = getContainedPass(Index);
 
298
    P->dumpPassStructure(Offset + 1);
 
299
    dumpLastUses(P, Offset+1);
 
300
  }
 
301
}
 
302
 
 
303
 
 
304
//===----------------------------------------------------------------------===//
 
305
// LoopPass
 
306
 
 
307
// Check if this pass is suitable for the current LPPassManager, if
 
308
// available. This pass P is not suitable for a LPPassManager if P
 
309
// is not preserving higher level analysis info used by other
 
310
// LPPassManager passes. In such case, pop LPPassManager from the
 
311
// stack. This will force assignPassManager() to create new
 
312
// LPPassManger as expected.
 
313
void LoopPass::preparePassManager(PMStack &PMS) {
 
314
 
 
315
  // Find LPPassManager 
 
316
  while (!PMS.empty() &&
 
317
         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 
318
    PMS.pop();
 
319
 
 
320
  // If this pass is destroying high level information that is used
 
321
  // by other passes that are managed by LPM then do not insert
 
322
  // this pass in current LPM. Use new LPPassManager.
 
323
  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
 
324
      !PMS.top()->preserveHigherLevelAnalysis(this)) 
 
325
    PMS.pop();
 
326
}
 
327
 
 
328
/// Assign pass manager to manage this pass.
 
329
void LoopPass::assignPassManager(PMStack &PMS,
 
330
                                 PassManagerType PreferredType) {
 
331
  // Find LPPassManager 
 
332
  while (!PMS.empty() &&
 
333
         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 
334
    PMS.pop();
 
335
 
 
336
  LPPassManager *LPPM;
 
337
  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
 
338
    LPPM = (LPPassManager*)PMS.top();
 
339
  else {
 
340
    // Create new Loop Pass Manager if it does not exist. 
 
341
    assert (!PMS.empty() && "Unable to create Loop Pass Manager");
 
342
    PMDataManager *PMD = PMS.top();
 
343
 
 
344
    // [1] Create new Call Graph Pass Manager
 
345
    LPPM = new LPPassManager(PMD->getDepth() + 1);
 
346
    LPPM->populateInheritedAnalysis(PMS);
 
347
 
 
348
    // [2] Set up new manager's top level manager
 
349
    PMTopLevelManager *TPM = PMD->getTopLevelManager();
 
350
    TPM->addIndirectPassManager(LPPM);
 
351
 
 
352
    // [3] Assign manager to manage this new manager. This may create
 
353
    // and push new managers into PMS
 
354
    Pass *P = LPPM->getAsPass();
 
355
    TPM->schedulePass(P);
 
356
 
 
357
    // [4] Push new manager into PMS
 
358
    PMS.push(LPPM);
 
359
  }
 
360
 
 
361
  LPPM->add(this);
 
362
}