← 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/Scalar/Sink.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/Scalar/Sink.cpp
 
1
//===-- Sink.cpp - Code Sinking -------------------------------------------===//
 
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 moves instructions into successor blocks, when possible, so that
 
11
// they aren't executed on paths where their results aren't needed.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
 
 
15
#define DEBUG_TYPE "sink"
 
16
#include "llvm/Transforms/Scalar.h"
 
17
#include "llvm/IntrinsicInst.h"
 
18
#include "llvm/Analysis/Dominators.h"
 
19
#include "llvm/Analysis/LoopInfo.h"
 
20
#include "llvm/Analysis/AliasAnalysis.h"
 
21
#include "llvm/Assembly/Writer.h"
 
22
#include "llvm/ADT/Statistic.h"
 
23
#include "llvm/Support/CFG.h"
 
24
#include "llvm/Support/Debug.h"
 
25
#include "llvm/Support/raw_ostream.h"
 
26
using namespace llvm;
 
27
 
 
28
STATISTIC(NumSunk, "Number of instructions sunk");
 
29
 
 
30
namespace {
 
31
  class Sinking : public FunctionPass {
 
32
    DominatorTree *DT;
 
33
    LoopInfo *LI;
 
34
    AliasAnalysis *AA;
 
35
 
 
36
  public:
 
37
    static char ID; // Pass identification
 
38
    Sinking() : FunctionPass(ID) {}
 
39
    
 
40
    virtual bool runOnFunction(Function &F);
 
41
    
 
42
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
43
      AU.setPreservesCFG();
 
44
      FunctionPass::getAnalysisUsage(AU);
 
45
      AU.addRequired<AliasAnalysis>();
 
46
      AU.addRequired<DominatorTree>();
 
47
      AU.addRequired<LoopInfo>();
 
48
      AU.addPreserved<DominatorTree>();
 
49
      AU.addPreserved<LoopInfo>();
 
50
    }
 
51
  private:
 
52
    bool ProcessBlock(BasicBlock &BB);
 
53
    bool SinkInstruction(Instruction *I, SmallPtrSet<Instruction *, 8> &Stores);
 
54
    bool AllUsesDominatedByBlock(Instruction *Inst, BasicBlock *BB) const;
 
55
  };
 
56
} // end anonymous namespace
 
57
  
 
58
char Sinking::ID = 0;
 
59
INITIALIZE_PASS(Sinking, "sink", "Code sinking", false, false);
 
60
 
 
61
FunctionPass *llvm::createSinkingPass() { return new Sinking(); }
 
62
 
 
63
/// AllUsesDominatedByBlock - Return true if all uses of the specified value
 
64
/// occur in blocks dominated by the specified block.
 
65
bool Sinking::AllUsesDominatedByBlock(Instruction *Inst, 
 
66
                                      BasicBlock *BB) const {
 
67
  // Ignoring debug uses is necessary so debug info doesn't affect the code.
 
68
  // This may leave a referencing dbg_value in the original block, before
 
69
  // the definition of the vreg.  Dwarf generator handles this although the
 
70
  // user might not get the right info at runtime.
 
71
  for (Value::use_iterator I = Inst->use_begin(),
 
72
       E = Inst->use_end(); I != E; ++I) {
 
73
    // Determine the block of the use.
 
74
    Instruction *UseInst = cast<Instruction>(*I);
 
75
    BasicBlock *UseBlock = UseInst->getParent();
 
76
    if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
 
77
      // PHI nodes use the operand in the predecessor block, not the block with
 
78
      // the PHI.
 
79
      unsigned Num = PHINode::getIncomingValueNumForOperand(I.getOperandNo());
 
80
      UseBlock = PN->getIncomingBlock(Num);
 
81
    }
 
82
    // Check that it dominates.
 
83
    if (!DT->dominates(BB, UseBlock))
 
84
      return false;
 
85
  }
 
86
  return true;
 
87
}
 
88
 
 
89
bool Sinking::runOnFunction(Function &F) {
 
90
  DT = &getAnalysis<DominatorTree>();
 
91
  LI = &getAnalysis<LoopInfo>();
 
92
  AA = &getAnalysis<AliasAnalysis>();
 
93
 
 
94
  bool EverMadeChange = false;
 
95
  
 
96
  while (1) {
 
97
    bool MadeChange = false;
 
98
 
 
99
    // Process all basic blocks.
 
100
    for (Function::iterator I = F.begin(), E = F.end(); 
 
101
         I != E; ++I)
 
102
      MadeChange |= ProcessBlock(*I);
 
103
    
 
104
    // If this iteration over the code changed anything, keep iterating.
 
105
    if (!MadeChange) break;
 
106
    EverMadeChange = true;
 
107
  } 
 
108
  return EverMadeChange;
 
109
}
 
110
 
 
111
bool Sinking::ProcessBlock(BasicBlock &BB) {
 
112
  // Can't sink anything out of a block that has less than two successors.
 
113
  if (BB.getTerminator()->getNumSuccessors() <= 1 || BB.empty()) return false;
 
114
 
 
115
  // Don't bother sinking code out of unreachable blocks. In addition to being
 
116
  // unprofitable, it can also lead to infinite looping, because in an unreachable
 
117
  // loop there may be nowhere to stop.
 
118
  if (!DT->isReachableFromEntry(&BB)) return false;
 
119
 
 
120
  bool MadeChange = false;
 
121
 
 
122
  // Walk the basic block bottom-up.  Remember if we saw a store.
 
123
  BasicBlock::iterator I = BB.end();
 
124
  --I;
 
125
  bool ProcessedBegin = false;
 
126
  SmallPtrSet<Instruction *, 8> Stores;
 
127
  do {
 
128
    Instruction *Inst = I;  // The instruction to sink.
 
129
    
 
130
    // Predecrement I (if it's not begin) so that it isn't invalidated by
 
131
    // sinking.
 
132
    ProcessedBegin = I == BB.begin();
 
133
    if (!ProcessedBegin)
 
134
      --I;
 
135
 
 
136
    if (isa<DbgInfoIntrinsic>(Inst))
 
137
      continue;
 
138
 
 
139
    if (SinkInstruction(Inst, Stores))
 
140
      ++NumSunk, MadeChange = true;
 
141
    
 
142
    // If we just processed the first instruction in the block, we're done.
 
143
  } while (!ProcessedBegin);
 
144
  
 
145
  return MadeChange;
 
146
}
 
147
 
 
148
static bool isSafeToMove(Instruction *Inst, AliasAnalysis *AA,
 
149
                         SmallPtrSet<Instruction *, 8> &Stores) {
 
150
  if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
 
151
    if (L->isVolatile()) return false;
 
152
 
 
153
    Value *Ptr = L->getPointerOperand();
 
154
    unsigned Size = AA->getTypeStoreSize(L->getType());
 
155
    for (SmallPtrSet<Instruction *, 8>::iterator I = Stores.begin(),
 
156
         E = Stores.end(); I != E; ++I)
 
157
      if (AA->getModRefInfo(*I, Ptr, Size) & AliasAnalysis::Mod)
 
158
        return false;
 
159
  }
 
160
 
 
161
  if (Inst->mayWriteToMemory()) {
 
162
    Stores.insert(Inst);
 
163
    return false;
 
164
  }
 
165
 
 
166
  return Inst->isSafeToSpeculativelyExecute();
 
167
}
 
168
 
 
169
/// SinkInstruction - Determine whether it is safe to sink the specified machine
 
170
/// instruction out of its current block into a successor.
 
171
bool Sinking::SinkInstruction(Instruction *Inst,
 
172
                              SmallPtrSet<Instruction *, 8> &Stores) {
 
173
  // Check if it's safe to move the instruction.
 
174
  if (!isSafeToMove(Inst, AA, Stores))
 
175
    return false;
 
176
  
 
177
  // FIXME: This should include support for sinking instructions within the
 
178
  // block they are currently in to shorten the live ranges.  We often get
 
179
  // instructions sunk into the top of a large block, but it would be better to
 
180
  // also sink them down before their first use in the block.  This xform has to
 
181
  // be careful not to *increase* register pressure though, e.g. sinking
 
182
  // "x = y + z" down if it kills y and z would increase the live ranges of y
 
183
  // and z and only shrink the live range of x.
 
184
  
 
185
  // Loop over all the operands of the specified instruction.  If there is
 
186
  // anything we can't handle, bail out.
 
187
  BasicBlock *ParentBlock = Inst->getParent();
 
188
  
 
189
  // SuccToSinkTo - This is the successor to sink this instruction to, once we
 
190
  // decide.
 
191
  BasicBlock *SuccToSinkTo = 0;
 
192
  
 
193
  // FIXME: This picks a successor to sink into based on having one
 
194
  // successor that dominates all the uses.  However, there are cases where
 
195
  // sinking can happen but where the sink point isn't a successor.  For
 
196
  // example:
 
197
  //   x = computation
 
198
  //   if () {} else {}
 
199
  //   use x
 
200
  // the instruction could be sunk over the whole diamond for the 
 
201
  // if/then/else (or loop, etc), allowing it to be sunk into other blocks
 
202
  // after that.
 
203
  
 
204
  // Instructions can only be sunk if all their uses are in blocks
 
205
  // dominated by one of the successors.
 
206
  // Look at all the successors and decide which one
 
207
  // we should sink to.
 
208
  for (succ_iterator SI = succ_begin(ParentBlock),
 
209
       E = succ_end(ParentBlock); SI != E; ++SI) {
 
210
    if (AllUsesDominatedByBlock(Inst, *SI)) {
 
211
      SuccToSinkTo = *SI;
 
212
      break;
 
213
    }
 
214
  }
 
215
      
 
216
  // If we couldn't find a block to sink to, ignore this instruction.
 
217
  if (SuccToSinkTo == 0)
 
218
    return false;
 
219
  
 
220
  // It is not possible to sink an instruction into its own block.  This can
 
221
  // happen with loops.
 
222
  if (Inst->getParent() == SuccToSinkTo)
 
223
    return false;
 
224
  
 
225
  DEBUG(dbgs() << "Sink instr " << *Inst);
 
226
  DEBUG(dbgs() << "to block ";
 
227
        WriteAsOperand(dbgs(), SuccToSinkTo, false));
 
228
  
 
229
  // If the block has multiple predecessors, this would introduce computation on
 
230
  // a path that it doesn't already exist.  We could split the critical edge,
 
231
  // but for now we just punt.
 
232
  // FIXME: Split critical edges if not backedges.
 
233
  if (SuccToSinkTo->getUniquePredecessor() != ParentBlock) {
 
234
    // We cannot sink a load across a critical edge - there may be stores in
 
235
    // other code paths.
 
236
    if (!Inst->isSafeToSpeculativelyExecute()) {
 
237
      DEBUG(dbgs() << " *** PUNTING: Wont sink load along critical edge.\n");
 
238
      return false;
 
239
    }
 
240
 
 
241
    // We don't want to sink across a critical edge if we don't dominate the
 
242
    // successor. We could be introducing calculations to new code paths.
 
243
    if (!DT->dominates(ParentBlock, SuccToSinkTo)) {
 
244
      DEBUG(dbgs() << " *** PUNTING: Critical edge found\n");
 
245
      return false;
 
246
    }
 
247
 
 
248
    // Don't sink instructions into a loop.
 
249
    if (LI->isLoopHeader(SuccToSinkTo)) {
 
250
      DEBUG(dbgs() << " *** PUNTING: Loop header found\n");
 
251
      return false;
 
252
    }
 
253
 
 
254
    // Otherwise we are OK with sinking along a critical edge.
 
255
    DEBUG(dbgs() << "Sinking along critical edge.\n");
 
256
  }
 
257
  
 
258
  // Determine where to insert into.  Skip phi nodes.
 
259
  BasicBlock::iterator InsertPos = SuccToSinkTo->begin();
 
260
  while (InsertPos != SuccToSinkTo->end() && isa<PHINode>(InsertPos))
 
261
    ++InsertPos;
 
262
  
 
263
  // Move the instruction.
 
264
  Inst->moveBefore(InsertPos);
 
265
  return true;
 
266
}