← Back to branch summary

~ubuntu-branches/ubuntu/wily/clamav/wily-proposed

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Analysis/IVUsers.cpp

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Analysis/IVUsers.cpp
 
1
//===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
 
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 bookkeeping for "interesting" users of expressions
 
11
// computed from induction variables.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
 
 
15
#define DEBUG_TYPE "iv-users"
 
16
#include "llvm/Analysis/IVUsers.h"
 
17
#include "llvm/Constants.h"
 
18
#include "llvm/Instructions.h"
 
19
#include "llvm/Type.h"
 
20
#include "llvm/DerivedTypes.h"
 
21
#include "llvm/Analysis/Dominators.h"
 
22
#include "llvm/Analysis/LoopPass.h"
 
23
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
 
24
#include "llvm/ADT/STLExtras.h"
 
25
#include "llvm/Support/Debug.h"
 
26
#include "llvm/Support/raw_ostream.h"
 
27
#include <algorithm>
 
28
using namespace llvm;
 
29
 
 
30
char IVUsers::ID = 0;
 
31
INITIALIZE_PASS(IVUsers, "iv-users", "Induction Variable Users", false, true);
 
32
 
 
33
Pass *llvm::createIVUsersPass() {
 
34
  return new IVUsers();
 
35
}
 
36
 
 
37
/// isInteresting - Test whether the given expression is "interesting" when
 
38
/// used by the given expression, within the context of analyzing the
 
39
/// given loop.
 
40
static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
 
41
                          ScalarEvolution *SE) {
 
42
  // An addrec is interesting if it's affine or if it has an interesting start.
 
43
  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
 
44
    // Keep things simple. Don't touch loop-variant strides.
 
45
    if (AR->getLoop() == L)
 
46
      return AR->isAffine() || !L->contains(I);
 
47
    // Otherwise recurse to see if the start value is interesting, and that
 
48
    // the step value is not interesting, since we don't yet know how to
 
49
    // do effective SCEV expansions for addrecs with interesting steps.
 
50
    return isInteresting(AR->getStart(), I, L, SE) &&
 
51
          !isInteresting(AR->getStepRecurrence(*SE), I, L, SE);
 
52
  }
 
53
 
 
54
  // An add is interesting if exactly one of its operands is interesting.
 
55
  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
 
56
    bool AnyInterestingYet = false;
 
57
    for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end();
 
58
         OI != OE; ++OI)
 
59
      if (isInteresting(*OI, I, L, SE)) {
 
60
        if (AnyInterestingYet)
 
61
          return false;
 
62
        AnyInterestingYet = true;
 
63
      }
 
64
    return AnyInterestingYet;
 
65
  }
 
66
 
 
67
  // Nothing else is interesting here.
 
68
  return false;
 
69
}
 
70
 
 
71
/// AddUsersIfInteresting - Inspect the specified instruction.  If it is a
 
72
/// reducible SCEV, recursively add its users to the IVUsesByStride set and
 
73
/// return true.  Otherwise, return false.
 
74
bool IVUsers::AddUsersIfInteresting(Instruction *I) {
 
75
  if (!SE->isSCEVable(I->getType()))
 
76
    return false;   // Void and FP expressions cannot be reduced.
 
77
 
 
78
  // LSR is not APInt clean, do not touch integers bigger than 64-bits.
 
79
  if (SE->getTypeSizeInBits(I->getType()) > 64)
 
80
    return false;
 
81
 
 
82
  if (!Processed.insert(I))
 
83
    return true;    // Instruction already handled.
 
84
 
 
85
  // Get the symbolic expression for this instruction.
 
86
  const SCEV *ISE = SE->getSCEV(I);
 
87
 
 
88
  // If we've come to an uninteresting expression, stop the traversal and
 
89
  // call this a user.
 
90
  if (!isInteresting(ISE, I, L, SE))
 
91
    return false;
 
92
 
 
93
  SmallPtrSet<Instruction *, 4> UniqueUsers;
 
94
  for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 
95
       UI != E; ++UI) {
 
96
    Instruction *User = cast<Instruction>(*UI);
 
97
    if (!UniqueUsers.insert(User))
 
98
      continue;
 
99
 
 
100
    // Do not infinitely recurse on PHI nodes.
 
101
    if (isa<PHINode>(User) && Processed.count(User))
 
102
      continue;
 
103
 
 
104
    // Descend recursively, but not into PHI nodes outside the current loop.
 
105
    // It's important to see the entire expression outside the loop to get
 
106
    // choices that depend on addressing mode use right, although we won't
 
107
    // consider references outside the loop in all cases.
 
108
    // If User is already in Processed, we don't want to recurse into it again,
 
109
    // but do want to record a second reference in the same instruction.
 
110
    bool AddUserToIVUsers = false;
 
111
    if (LI->getLoopFor(User->getParent()) != L) {
 
112
      if (isa<PHINode>(User) || Processed.count(User) ||
 
113
          !AddUsersIfInteresting(User)) {
 
114
        DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
 
115
                     << "   OF SCEV: " << *ISE << '\n');
 
116
        AddUserToIVUsers = true;
 
117
      }
 
118
    } else if (Processed.count(User) ||
 
119
               !AddUsersIfInteresting(User)) {
 
120
      DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
 
121
                   << "   OF SCEV: " << *ISE << '\n');
 
122
      AddUserToIVUsers = true;
 
123
    }
 
124
 
 
125
    if (AddUserToIVUsers) {
 
126
      // Okay, we found a user that we cannot reduce.
 
127
      IVUses.push_back(new IVStrideUse(this, User, I));
 
128
      IVStrideUse &NewUse = IVUses.back();
 
129
      // Transform the expression into a normalized form.
 
130
      ISE = TransformForPostIncUse(NormalizeAutodetect,
 
131
                                   ISE, User, I,
 
132
                                   NewUse.PostIncLoops,
 
133
                                   *SE, *DT);
 
134
      DEBUG(dbgs() << "   NORMALIZED TO: " << *ISE << '\n');
 
135
    }
 
136
  }
 
137
  return true;
 
138
}
 
139
 
 
140
IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
 
141
  IVUses.push_back(new IVStrideUse(this, User, Operand));
 
142
  return IVUses.back();
 
143
}
 
144
 
 
145
IVUsers::IVUsers()
 
146
 : LoopPass(ID) {
 
147
}
 
148
 
 
149
void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
 
150
  AU.addRequired<LoopInfo>();
 
151
  AU.addRequired<DominatorTree>();
 
152
  AU.addRequired<ScalarEvolution>();
 
153
  AU.setPreservesAll();
 
154
}
 
155
 
 
156
bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
 
157
 
 
158
  L = l;
 
159
  LI = &getAnalysis<LoopInfo>();
 
160
  DT = &getAnalysis<DominatorTree>();
 
161
  SE = &getAnalysis<ScalarEvolution>();
 
162
 
 
163
  // Find all uses of induction variables in this loop, and categorize
 
164
  // them by stride.  Start by finding all of the PHI nodes in the header for
 
165
  // this loop.  If they are induction variables, inspect their uses.
 
166
  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
 
167
    (void)AddUsersIfInteresting(I);
 
168
 
 
169
  return false;
 
170
}
 
171
 
 
172
void IVUsers::print(raw_ostream &OS, const Module *M) const {
 
173
  OS << "IV Users for loop ";
 
174
  WriteAsOperand(OS, L->getHeader(), false);
 
175
  if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
 
176
    OS << " with backedge-taken count "
 
177
       << *SE->getBackedgeTakenCount(L);
 
178
  }
 
179
  OS << ":\n";
 
180
 
 
181
  for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(),
 
182
       E = IVUses.end(); UI != E; ++UI) {
 
183
    OS << "  ";
 
184
    WriteAsOperand(OS, UI->getOperandValToReplace(), false);
 
185
    OS << " = " << *getReplacementExpr(*UI);
 
186
    for (PostIncLoopSet::const_iterator
 
187
         I = UI->PostIncLoops.begin(),
 
188
         E = UI->PostIncLoops.end(); I != E; ++I) {
 
189
      OS << " (post-inc with loop ";
 
190
      WriteAsOperand(OS, (*I)->getHeader(), false);
 
191
      OS << ")";
 
192
    }
 
193
    OS << " in  ";
 
194
    UI->getUser()->print(OS);
 
195
    OS << '\n';
 
196
  }
 
197
}
 
198
 
 
199
void IVUsers::dump() const {
 
200
  print(dbgs());
 
201
}
 
202
 
 
203
void IVUsers::releaseMemory() {
 
204
  Processed.clear();
 
205
  IVUses.clear();
 
206
}
 
207
 
 
208
/// getReplacementExpr - Return a SCEV expression which computes the
 
209
/// value of the OperandValToReplace.
 
210
const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const {
 
211
  return SE->getSCEV(IU.getOperandValToReplace());
 
212
}
 
213
 
 
214
/// getExpr - Return the expression for the use.
 
215
const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
 
216
  return
 
217
    TransformForPostIncUse(Normalize, getReplacementExpr(IU),
 
218
                           IU.getUser(), IU.getOperandValToReplace(),
 
219
                           const_cast<PostIncLoopSet &>(IU.getPostIncLoops()),
 
220
                           *SE, *DT);
 
221
}
 
222
 
 
223
static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
 
224
  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
 
225
    if (AR->getLoop() == L)
 
226
      return AR;
 
227
    return findAddRecForLoop(AR->getStart(), L);
 
228
  }
 
229
 
 
230
  if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
 
231
    for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
 
232
         I != E; ++I)
 
233
      if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L))
 
234
        return AR;
 
235
    return 0;
 
236
  }
 
237
 
 
238
  return 0;
 
239
}
 
240
 
 
241
const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const {
 
242
  if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L))
 
243
    return AR->getStepRecurrence(*SE);
 
244
  return 0;
 
245
}
 
246
 
 
247
void IVStrideUse::transformToPostInc(const Loop *L) {
 
248
  PostIncLoops.insert(L);
 
249
}
 
250
 
 
251
void IVStrideUse::deleted() {
 
252
  // Remove this user from the list.
 
253
  Parent->IVUses.erase(this);
 
254
  // this now dangles!
 
255
}