← 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/Transforms/Utils/SSAUpdater.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/Transforms/Utils/SSAUpdater.cpp
 
1
//===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===//
 
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 SSAUpdater class.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
#define DEBUG_TYPE "ssaupdater"
 
15
#include "llvm/Instructions.h"
 
16
#include "llvm/ADT/DenseMap.h"
 
17
#include "llvm/Support/AlignOf.h"
 
18
#include "llvm/Support/Allocator.h"
 
19
#include "llvm/Support/CFG.h"
 
20
#include "llvm/Support/Debug.h"
 
21
#include "llvm/Support/raw_ostream.h"
 
22
#include "llvm/Transforms/Utils/SSAUpdater.h"
 
23
#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
 
24
using namespace llvm;
 
25
 
 
26
typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
 
27
static AvailableValsTy &getAvailableVals(void *AV) {
 
28
  return *static_cast<AvailableValsTy*>(AV);
 
29
}
 
30
 
 
31
SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
 
32
  : AV(0), ProtoType(0), ProtoName(), InsertedPHIs(NewPHI) {}
 
33
 
 
34
SSAUpdater::~SSAUpdater() {
 
35
  delete &getAvailableVals(AV);
 
36
}
 
37
 
 
38
/// Initialize - Reset this object to get ready for a new set of SSA
 
39
/// updates with type 'Ty'.  PHI nodes get a name based on 'Name'.
 
40
void SSAUpdater::Initialize(const Type *Ty, StringRef Name) {
 
41
  if (AV == 0)
 
42
    AV = new AvailableValsTy();
 
43
  else
 
44
    getAvailableVals(AV).clear();
 
45
  ProtoType = Ty;
 
46
  ProtoName = Name;
 
47
}
 
48
 
 
49
/// HasValueForBlock - Return true if the SSAUpdater already has a value for
 
50
/// the specified block.
 
51
bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {
 
52
  return getAvailableVals(AV).count(BB);
 
53
}
 
54
 
 
55
/// AddAvailableValue - Indicate that a rewritten value is available in the
 
56
/// specified block with the specified value.
 
57
void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
 
58
  assert(ProtoType != 0 && "Need to initialize SSAUpdater");
 
59
  assert(ProtoType == V->getType() &&
 
60
         "All rewritten values must have the same type");
 
61
  getAvailableVals(AV)[BB] = V;
 
62
}
 
63
 
 
64
/// IsEquivalentPHI - Check if PHI has the same incoming value as specified
 
65
/// in ValueMapping for each predecessor block.
 
66
static bool IsEquivalentPHI(PHINode *PHI,
 
67
                            DenseMap<BasicBlock*, Value*> &ValueMapping) {
 
68
  unsigned PHINumValues = PHI->getNumIncomingValues();
 
69
  if (PHINumValues != ValueMapping.size())
 
70
    return false;
 
71
 
 
72
  // Scan the phi to see if it matches.
 
73
  for (unsigned i = 0, e = PHINumValues; i != e; ++i)
 
74
    if (ValueMapping[PHI->getIncomingBlock(i)] !=
 
75
        PHI->getIncomingValue(i)) {
 
76
      return false;
 
77
    }
 
78
 
 
79
  return true;
 
80
}
 
81
 
 
82
/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
 
83
/// live at the end of the specified block.
 
84
Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
 
85
  Value *Res = GetValueAtEndOfBlockInternal(BB);
 
86
  return Res;
 
87
}
 
88
 
 
89
/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
 
90
/// is live in the middle of the specified block.
 
91
///
 
92
/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
 
93
/// important case: if there is a definition of the rewritten value after the
 
94
/// 'use' in BB.  Consider code like this:
 
95
///
 
96
///      X1 = ...
 
97
///   SomeBB:
 
98
///      use(X)
 
99
///      X2 = ...
 
100
///      br Cond, SomeBB, OutBB
 
101
///
 
102
/// In this case, there are two values (X1 and X2) added to the AvailableVals
 
103
/// set by the client of the rewriter, and those values are both live out of
 
104
/// their respective blocks.  However, the use of X happens in the *middle* of
 
105
/// a block.  Because of this, we need to insert a new PHI node in SomeBB to
 
106
/// merge the appropriate values, and this value isn't live out of the block.
 
107
///
 
108
Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
 
109
  // If there is no definition of the renamed variable in this block, just use
 
110
  // GetValueAtEndOfBlock to do our work.
 
111
  if (!HasValueForBlock(BB))
 
112
    return GetValueAtEndOfBlock(BB);
 
113
 
 
114
  // Otherwise, we have the hard case.  Get the live-in values for each
 
115
  // predecessor.
 
116
  SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues;
 
117
  Value *SingularValue = 0;
 
118
 
 
119
  // We can get our predecessor info by walking the pred_iterator list, but it
 
120
  // is relatively slow.  If we already have PHI nodes in this block, walk one
 
121
  // of them to get the predecessor list instead.
 
122
  if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
 
123
    for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
 
124
      BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
 
125
      Value *PredVal = GetValueAtEndOfBlock(PredBB);
 
126
      PredValues.push_back(std::make_pair(PredBB, PredVal));
 
127
 
 
128
      // Compute SingularValue.
 
129
      if (i == 0)
 
130
        SingularValue = PredVal;
 
131
      else if (PredVal != SingularValue)
 
132
        SingularValue = 0;
 
133
    }
 
134
  } else {
 
135
    bool isFirstPred = true;
 
136
    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 
137
      BasicBlock *PredBB = *PI;
 
138
      Value *PredVal = GetValueAtEndOfBlock(PredBB);
 
139
      PredValues.push_back(std::make_pair(PredBB, PredVal));
 
140
 
 
141
      // Compute SingularValue.
 
142
      if (isFirstPred) {
 
143
        SingularValue = PredVal;
 
144
        isFirstPred = false;
 
145
      } else if (PredVal != SingularValue)
 
146
        SingularValue = 0;
 
147
    }
 
148
  }
 
149
 
 
150
  // If there are no predecessors, just return undef.
 
151
  if (PredValues.empty())
 
152
    return UndefValue::get(ProtoType);
 
153
 
 
154
  // Otherwise, if all the merged values are the same, just use it.
 
155
  if (SingularValue != 0)
 
156
    return SingularValue;
 
157
 
 
158
  // Otherwise, we do need a PHI: check to see if we already have one available
 
159
  // in this block that produces the right value.
 
160
  if (isa<PHINode>(BB->begin())) {
 
161
    DenseMap<BasicBlock*, Value*> ValueMapping(PredValues.begin(),
 
162
                                               PredValues.end());
 
163
    PHINode *SomePHI;
 
164
    for (BasicBlock::iterator It = BB->begin();
 
165
         (SomePHI = dyn_cast<PHINode>(It)); ++It) {
 
166
      if (IsEquivalentPHI(SomePHI, ValueMapping))
 
167
        return SomePHI;
 
168
    }
 
169
  }
 
170
 
 
171
  // Ok, we have no way out, insert a new one now.
 
172
  PHINode *InsertedPHI = PHINode::Create(ProtoType, ProtoName, &BB->front());
 
173
  InsertedPHI->reserveOperandSpace(PredValues.size());
 
174
 
 
175
  // Fill in all the predecessors of the PHI.
 
176
  for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
 
177
    InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first);
 
178
 
 
179
  // See if the PHI node can be merged to a single value.  This can happen in
 
180
  // loop cases when we get a PHI of itself and one other value.
 
181
  if (Value *ConstVal = InsertedPHI->hasConstantValue()) {
 
182
    InsertedPHI->eraseFromParent();
 
183
    return ConstVal;
 
184
  }
 
185
 
 
186
  // If the client wants to know about all new instructions, tell it.
 
187
  if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
 
188
 
 
189
  DEBUG(dbgs() << "  Inserted PHI: " << *InsertedPHI << "\n");
 
190
  return InsertedPHI;
 
191
}
 
192
 
 
193
/// RewriteUse - Rewrite a use of the symbolic value.  This handles PHI nodes,
 
194
/// which use their value in the corresponding predecessor.
 
195
void SSAUpdater::RewriteUse(Use &U) {
 
196
  Instruction *User = cast<Instruction>(U.getUser());
 
197
 
 
198
  Value *V;
 
199
  if (PHINode *UserPN = dyn_cast<PHINode>(User))
 
200
    V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
 
201
  else
 
202
    V = GetValueInMiddleOfBlock(User->getParent());
 
203
 
 
204
  U.set(V);
 
205
}
 
206
 
 
207
/// RewriteUseAfterInsertions - Rewrite a use, just like RewriteUse.  However,
 
208
/// this version of the method can rewrite uses in the same block as a
 
209
/// definition, because it assumes that all uses of a value are below any
 
210
/// inserted values.
 
211
void SSAUpdater::RewriteUseAfterInsertions(Use &U) {
 
212
  Instruction *User = cast<Instruction>(U.getUser());
 
213
  
 
214
  Value *V;
 
215
  if (PHINode *UserPN = dyn_cast<PHINode>(User))
 
216
    V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
 
217
  else
 
218
    V = GetValueAtEndOfBlock(User->getParent());
 
219
  
 
220
  U.set(V);
 
221
}
 
222
 
 
223
/// PHIiter - Iterator for PHI operands.  This is used for the PHI_iterator
 
224
/// in the SSAUpdaterImpl template.
 
225
namespace {
 
226
  class PHIiter {
 
227
  private:
 
228
    PHINode *PHI;
 
229
    unsigned idx;
 
230
 
 
231
  public:
 
232
    explicit PHIiter(PHINode *P) // begin iterator
 
233
      : PHI(P), idx(0) {}
 
234
    PHIiter(PHINode *P, bool) // end iterator
 
235
      : PHI(P), idx(PHI->getNumIncomingValues()) {}
 
236
 
 
237
    PHIiter &operator++() { ++idx; return *this; } 
 
238
    bool operator==(const PHIiter& x) const { return idx == x.idx; }
 
239
    bool operator!=(const PHIiter& x) const { return !operator==(x); }
 
240
    Value *getIncomingValue() { return PHI->getIncomingValue(idx); }
 
241
    BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); }
 
242
  };
 
243
}
 
244
 
 
245
/// SSAUpdaterTraits<SSAUpdater> - Traits for the SSAUpdaterImpl template,
 
246
/// specialized for SSAUpdater.
 
247
namespace llvm {
 
248
template<>
 
249
class SSAUpdaterTraits<SSAUpdater> {
 
250
public:
 
251
  typedef BasicBlock BlkT;
 
252
  typedef Value *ValT;
 
253
  typedef PHINode PhiT;
 
254
 
 
255
  typedef succ_iterator BlkSucc_iterator;
 
256
  static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); }
 
257
  static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); }
 
258
 
 
259
  typedef PHIiter PHI_iterator;
 
260
  static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
 
261
  static inline PHI_iterator PHI_end(PhiT *PHI) {
 
262
    return PHI_iterator(PHI, true);
 
263
  }
 
264
 
 
265
  /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
 
266
  /// vector, set Info->NumPreds, and allocate space in Info->Preds.
 
267
  static void FindPredecessorBlocks(BasicBlock *BB,
 
268
                                    SmallVectorImpl<BasicBlock*> *Preds) {
 
269
    // We can get our predecessor info by walking the pred_iterator list,
 
270
    // but it is relatively slow.  If we already have PHI nodes in this
 
271
    // block, walk one of them to get the predecessor list instead.
 
272
    if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
 
273
      for (unsigned PI = 0, E = SomePhi->getNumIncomingValues(); PI != E; ++PI)
 
274
        Preds->push_back(SomePhi->getIncomingBlock(PI));
 
275
    } else {
 
276
      for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
 
277
        Preds->push_back(*PI);
 
278
    }
 
279
  }
 
280
 
 
281
  /// GetUndefVal - Get an undefined value of the same type as the value
 
282
  /// being handled.
 
283
  static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) {
 
284
    return UndefValue::get(Updater->ProtoType);
 
285
  }
 
286
 
 
287
  /// CreateEmptyPHI - Create a new PHI instruction in the specified block.
 
288
  /// Reserve space for the operands but do not fill them in yet.
 
289
  static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds,
 
290
                               SSAUpdater *Updater) {
 
291
    PHINode *PHI = PHINode::Create(Updater->ProtoType, Updater->ProtoName,
 
292
                                   &BB->front());
 
293
    PHI->reserveOperandSpace(NumPreds);
 
294
    return PHI;
 
295
  }
 
296
 
 
297
  /// AddPHIOperand - Add the specified value as an operand of the PHI for
 
298
  /// the specified predecessor block.
 
299
  static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) {
 
300
    PHI->addIncoming(Val, Pred);
 
301
  }
 
302
 
 
303
  /// InstrIsPHI - Check if an instruction is a PHI.
 
304
  ///
 
305
  static PHINode *InstrIsPHI(Instruction *I) {
 
306
    return dyn_cast<PHINode>(I);
 
307
  }
 
308
 
 
309
  /// ValueIsPHI - Check if a value is a PHI.
 
310
  ///
 
311
  static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {
 
312
    return dyn_cast<PHINode>(Val);
 
313
  }
 
314
 
 
315
  /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
 
316
  /// operands, i.e., it was just added.
 
317
  static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) {
 
318
    PHINode *PHI = ValueIsPHI(Val, Updater);
 
319
    if (PHI && PHI->getNumIncomingValues() == 0)
 
320
      return PHI;
 
321
    return 0;
 
322
  }
 
323
 
 
324
  /// GetPHIValue - For the specified PHI instruction, return the value
 
325
  /// that it defines.
 
326
  static Value *GetPHIValue(PHINode *PHI) {
 
327
    return PHI;
 
328
  }
 
329
};
 
330
 
 
331
} // End llvm namespace
 
332
 
 
333
/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
 
334
/// for the specified BB and if so, return it.  If not, construct SSA form by
 
335
/// first calculating the required placement of PHIs and then inserting new
 
336
/// PHIs where needed.
 
337
Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
 
338
  AvailableValsTy &AvailableVals = getAvailableVals(AV);
 
339
  if (Value *V = AvailableVals[BB])
 
340
    return V;
 
341
 
 
342
  SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
 
343
  return Impl.GetValue(BB);
 
344
}