← Back to branch summary

~ubuntu-branches/ubuntu/hardy/clamav/hardy-security

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/MachineLICM.cpp

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Marc Deslauriers, Scott Kitterman
  • Date: 2013-03-21 08:37:54 UTC
  • mfrom: (43.1.79 raring-proposed)
  • Revision ID: package-import@ubuntu.com-20130321083754-r3dnl8aewkny2rxu
Tags: 0.97.7+dfsg-1ubuntu0.08.04.1
https://launchpad.net/bugs/1157385
[ Marc Deslauriers ]
* SECURITY UPDATE: Updated to 0.97.7 to fix multiple security issues.
  (LP: #1157385)
  - CVE numbers pending

[ Scott Kitterman ]
* Changes to adapt to Hardy:
  - Build without llvm support on lpia to fix FTBFS (not a regression as
    llvm has never built on hardy lpia)
  - Drop -T -W from apparmor_parser calls in clamav-daemon and freshclam
    postinsts since it is not supported in Hardy's apparmor
  - Drop deny rule in freshclam apparmor profile since deny is not
    supported in Hardy's apparmor
  - Drop dh_lintian from debian/rules and adjust version of debhelper
    build-dep
  - Drop build-dep and libclamav-dev depends on non-existent libtommath-dev
  - Changed Section to 'utils' for clamav-dbg package
  - Ignore test suite errors on hppa
  - Build-depend on libltdl3-dev instead of libltdl-dev
  - Drop hardening flags changes
  - Drop unneeded versioning on lsb-base (clamav ships it's own status
    function)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/MachineLICM.cpp
 
1
//===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===//
 
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 performs loop invariant code motion on machine instructions. We
 
11
// attempt to remove as much code from the body of a loop as possible.
 
12
//
 
13
// This pass does not attempt to throttle itself to limit register pressure.
 
14
// The register allocation phases are expected to perform rematerialization
 
15
// to recover when register pressure is high.
 
16
//
 
17
// This pass is not intended to be a replacement or a complete alternative
 
18
// for the LLVM-IR-level LICM pass. It is only designed to hoist simple
 
19
// constructs that are not exposed before lowering and instruction selection.
 
20
//
 
21
//===----------------------------------------------------------------------===//
 
22
 
 
23
#define DEBUG_TYPE "machine-licm"
 
24
#include "llvm/CodeGen/Passes.h"
 
25
#include "llvm/CodeGen/MachineDominators.h"
 
26
#include "llvm/CodeGen/MachineFrameInfo.h"
 
27
#include "llvm/CodeGen/MachineLoopInfo.h"
 
28
#include "llvm/CodeGen/MachineMemOperand.h"
 
29
#include "llvm/CodeGen/MachineRegisterInfo.h"
 
30
#include "llvm/CodeGen/PseudoSourceValue.h"
 
31
#include "llvm/Target/TargetRegisterInfo.h"
 
32
#include "llvm/Target/TargetInstrInfo.h"
 
33
#include "llvm/Target/TargetMachine.h"
 
34
#include "llvm/Analysis/AliasAnalysis.h"
 
35
#include "llvm/ADT/DenseMap.h"
 
36
#include "llvm/ADT/SmallSet.h"
 
37
#include "llvm/ADT/Statistic.h"
 
38
#include "llvm/Support/Debug.h"
 
39
#include "llvm/Support/raw_ostream.h"
 
40
 
 
41
using namespace llvm;
 
42
 
 
43
STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops");
 
44
STATISTIC(NumCSEed,   "Number of hoisted machine instructions CSEed");
 
45
STATISTIC(NumPostRAHoisted,
 
46
          "Number of machine instructions hoisted out of loops post regalloc");
 
47
 
 
48
namespace {
 
49
  class MachineLICM : public MachineFunctionPass {
 
50
    bool PreRegAlloc;
 
51
 
 
52
    const TargetMachine   *TM;
 
53
    const TargetInstrInfo *TII;
 
54
    const TargetRegisterInfo *TRI;
 
55
    const MachineFrameInfo *MFI;
 
56
    MachineRegisterInfo *RegInfo;
 
57
 
 
58
    // Various analyses that we use...
 
59
    AliasAnalysis        *AA;      // Alias analysis info.
 
60
    MachineLoopInfo      *MLI;     // Current MachineLoopInfo
 
61
    MachineDominatorTree *DT;      // Machine dominator tree for the cur loop
 
62
 
 
63
    // State that is updated as we process loops
 
64
    bool         Changed;          // True if a loop is changed.
 
65
    bool         FirstInLoop;      // True if it's the first LICM in the loop.
 
66
    MachineLoop *CurLoop;          // The current loop we are working on.
 
67
    MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
 
68
 
 
69
    BitVector AllocatableSet;
 
70
 
 
71
    // For each opcode, keep a list of potential CSE instructions.
 
72
    DenseMap<unsigned, std::vector<const MachineInstr*> > CSEMap;
 
73
 
 
74
  public:
 
75
    static char ID; // Pass identification, replacement for typeid
 
76
    MachineLICM() :
 
77
      MachineFunctionPass(ID), PreRegAlloc(true) {}
 
78
 
 
79
    explicit MachineLICM(bool PreRA) :
 
80
      MachineFunctionPass(ID), PreRegAlloc(PreRA) {}
 
81
 
 
82
    virtual bool runOnMachineFunction(MachineFunction &MF);
 
83
 
 
84
    const char *getPassName() const { return "Machine Instruction LICM"; }
 
85
 
 
86
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
87
      AU.setPreservesCFG();
 
88
      AU.addRequired<MachineLoopInfo>();
 
89
      AU.addRequired<MachineDominatorTree>();
 
90
      AU.addRequired<AliasAnalysis>();
 
91
      AU.addPreserved<MachineLoopInfo>();
 
92
      AU.addPreserved<MachineDominatorTree>();
 
93
      MachineFunctionPass::getAnalysisUsage(AU);
 
94
    }
 
95
 
 
96
    virtual void releaseMemory() {
 
97
      CSEMap.clear();
 
98
    }
 
99
 
 
100
  private:
 
101
    /// CandidateInfo - Keep track of information about hoisting candidates.
 
102
    struct CandidateInfo {
 
103
      MachineInstr *MI;
 
104
      unsigned      Def;
 
105
      int           FI;
 
106
      CandidateInfo(MachineInstr *mi, unsigned def, int fi)
 
107
        : MI(mi), Def(def), FI(fi) {}
 
108
    };
 
109
 
 
110
    /// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop
 
111
    /// invariants out to the preheader.
 
112
    void HoistRegionPostRA();
 
113
 
 
114
    /// HoistPostRA - When an instruction is found to only use loop invariant
 
115
    /// operands that is safe to hoist, this instruction is called to do the
 
116
    /// dirty work.
 
117
    void HoistPostRA(MachineInstr *MI, unsigned Def);
 
118
 
 
119
    /// ProcessMI - Examine the instruction for potentai LICM candidate. Also
 
120
    /// gather register def and frame object update information.
 
121
    void ProcessMI(MachineInstr *MI, unsigned *PhysRegDefs,
 
122
                   SmallSet<int, 32> &StoredFIs,
 
123
                   SmallVector<CandidateInfo, 32> &Candidates);
 
124
 
 
125
    /// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the
 
126
    /// current loop.
 
127
    void AddToLiveIns(unsigned Reg);
 
128
 
 
129
    /// IsLICMCandidate - Returns true if the instruction may be a suitable
 
130
    /// candidate for LICM. e.g. If the instruction is a call, then it's
 
131
    /// obviously not safe to hoist it.
 
132
    bool IsLICMCandidate(MachineInstr &I);
 
133
 
 
134
    /// IsLoopInvariantInst - Returns true if the instruction is loop
 
135
    /// invariant. I.e., all virtual register operands are defined outside of
 
136
    /// the loop, physical registers aren't accessed (explicitly or implicitly),
 
137
    /// and the instruction is hoistable.
 
138
    /// 
 
139
    bool IsLoopInvariantInst(MachineInstr &I);
 
140
 
 
141
    /// IsProfitableToHoist - Return true if it is potentially profitable to
 
142
    /// hoist the given loop invariant.
 
143
    bool IsProfitableToHoist(MachineInstr &MI);
 
144
 
 
145
    /// HoistRegion - Walk the specified region of the CFG (defined by all
 
146
    /// blocks dominated by the specified block, and that are in the current
 
147
    /// loop) in depth first order w.r.t the DominatorTree. This allows us to
 
148
    /// visit definitions before uses, allowing us to hoist a loop body in one
 
149
    /// pass without iteration.
 
150
    ///
 
151
    void HoistRegion(MachineDomTreeNode *N);
 
152
 
 
153
    /// isLoadFromConstantMemory - Return true if the given instruction is a
 
154
    /// load from constant memory.
 
155
    bool isLoadFromConstantMemory(MachineInstr *MI);
 
156
 
 
157
    /// ExtractHoistableLoad - Unfold a load from the given machineinstr if
 
158
    /// the load itself could be hoisted. Return the unfolded and hoistable
 
159
    /// load, or null if the load couldn't be unfolded or if it wouldn't
 
160
    /// be hoistable.
 
161
    MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
 
162
 
 
163
    /// LookForDuplicate - Find an instruction amount PrevMIs that is a
 
164
    /// duplicate of MI. Return this instruction if it's found.
 
165
    const MachineInstr *LookForDuplicate(const MachineInstr *MI,
 
166
                                     std::vector<const MachineInstr*> &PrevMIs);
 
167
 
 
168
    /// EliminateCSE - Given a LICM'ed instruction, look for an instruction on
 
169
    /// the preheader that compute the same value. If it's found, do a RAU on
 
170
    /// with the definition of the existing instruction rather than hoisting
 
171
    /// the instruction to the preheader.
 
172
    bool EliminateCSE(MachineInstr *MI,
 
173
           DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI);
 
174
 
 
175
    /// Hoist - When an instruction is found to only use loop invariant operands
 
176
    /// that is safe to hoist, this instruction is called to do the dirty work.
 
177
    ///
 
178
    void Hoist(MachineInstr *MI);
 
179
 
 
180
    /// InitCSEMap - Initialize the CSE map with instructions that are in the
 
181
    /// current loop preheader that may become duplicates of instructions that
 
182
    /// are hoisted out of the loop.
 
183
    void InitCSEMap(MachineBasicBlock *BB);
 
184
 
 
185
    /// getCurPreheader - Get the preheader for the current loop, splitting
 
186
    /// a critical edge if needed.
 
187
    MachineBasicBlock *getCurPreheader();
 
188
  };
 
189
} // end anonymous namespace
 
190
 
 
191
char MachineLICM::ID = 0;
 
192
INITIALIZE_PASS(MachineLICM, "machinelicm",
 
193
                "Machine Loop Invariant Code Motion", false, false);
 
194
 
 
195
FunctionPass *llvm::createMachineLICMPass(bool PreRegAlloc) {
 
196
  return new MachineLICM(PreRegAlloc);
 
197
}
 
198
 
 
199
/// LoopIsOuterMostWithPredecessor - Test if the given loop is the outer-most
 
200
/// loop that has a unique predecessor.
 
201
static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) {
 
202
  // Check whether this loop even has a unique predecessor.
 
203
  if (!CurLoop->getLoopPredecessor())
 
204
    return false;
 
205
  // Ok, now check to see if any of its outer loops do.
 
206
  for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop())
 
207
    if (L->getLoopPredecessor())
 
208
      return false;
 
209
  // None of them did, so this is the outermost with a unique predecessor.
 
210
  return true;
 
211
}
 
212
 
 
213
bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
 
214
  if (PreRegAlloc)
 
215
    DEBUG(dbgs() << "******** Pre-regalloc Machine LICM ********\n");
 
216
  else
 
217
    DEBUG(dbgs() << "******** Post-regalloc Machine LICM ********\n");
 
218
 
 
219
  Changed = FirstInLoop = false;
 
220
  TM = &MF.getTarget();
 
221
  TII = TM->getInstrInfo();
 
222
  TRI = TM->getRegisterInfo();
 
223
  MFI = MF.getFrameInfo();
 
224
  RegInfo = &MF.getRegInfo();
 
225
  AllocatableSet = TRI->getAllocatableSet(MF);
 
226
 
 
227
  // Get our Loop information...
 
228
  MLI = &getAnalysis<MachineLoopInfo>();
 
229
  DT  = &getAnalysis<MachineDominatorTree>();
 
230
  AA  = &getAnalysis<AliasAnalysis>();
 
231
 
 
232
  SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
 
233
  while (!Worklist.empty()) {
 
234
    CurLoop = Worklist.pop_back_val();
 
235
    CurPreheader = 0;
 
236
 
 
237
    // If this is done before regalloc, only visit outer-most preheader-sporting
 
238
    // loops.
 
239
    if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) {
 
240
      Worklist.append(CurLoop->begin(), CurLoop->end());
 
241
      continue;
 
242
    }
 
243
 
 
244
    if (!PreRegAlloc)
 
245
      HoistRegionPostRA();
 
246
    else {
 
247
      // CSEMap is initialized for loop header when the first instruction is
 
248
      // being hoisted.
 
249
      MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader());
 
250
      FirstInLoop = true;
 
251
      HoistRegion(N);
 
252
      CSEMap.clear();
 
253
    }
 
254
  }
 
255
 
 
256
  return Changed;
 
257
}
 
258
 
 
259
/// InstructionStoresToFI - Return true if instruction stores to the
 
260
/// specified frame.
 
261
static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {
 
262
  for (MachineInstr::mmo_iterator o = MI->memoperands_begin(),
 
263
         oe = MI->memoperands_end(); o != oe; ++o) {
 
264
    if (!(*o)->isStore() || !(*o)->getValue())
 
265
      continue;
 
266
    if (const FixedStackPseudoSourceValue *Value =
 
267
        dyn_cast<const FixedStackPseudoSourceValue>((*o)->getValue())) {
 
268
      if (Value->getFrameIndex() == FI)
 
269
        return true;
 
270
    }
 
271
  }
 
272
  return false;
 
273
}
 
274
 
 
275
/// ProcessMI - Examine the instruction for potentai LICM candidate. Also
 
276
/// gather register def and frame object update information.
 
277
void MachineLICM::ProcessMI(MachineInstr *MI,
 
278
                            unsigned *PhysRegDefs,
 
279
                            SmallSet<int, 32> &StoredFIs,
 
280
                            SmallVector<CandidateInfo, 32> &Candidates) {
 
281
  bool RuledOut = false;
 
282
  bool HasNonInvariantUse = false;
 
283
  unsigned Def = 0;
 
284
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
285
    const MachineOperand &MO = MI->getOperand(i);
 
286
    if (MO.isFI()) {
 
287
      // Remember if the instruction stores to the frame index.
 
288
      int FI = MO.getIndex();
 
289
      if (!StoredFIs.count(FI) &&
 
290
          MFI->isSpillSlotObjectIndex(FI) &&
 
291
          InstructionStoresToFI(MI, FI))
 
292
        StoredFIs.insert(FI);
 
293
      HasNonInvariantUse = true;
 
294
      continue;
 
295
    }
 
296
 
 
297
    if (!MO.isReg())
 
298
      continue;
 
299
    unsigned Reg = MO.getReg();
 
300
    if (!Reg)
 
301
      continue;
 
302
    assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
 
303
           "Not expecting virtual register!");
 
304
 
 
305
    if (!MO.isDef()) {
 
306
      if (Reg && PhysRegDefs[Reg])
 
307
        // If it's using a non-loop-invariant register, then it's obviously not
 
308
        // safe to hoist.
 
309
        HasNonInvariantUse = true;
 
310
      continue;
 
311
    }
 
312
 
 
313
    if (MO.isImplicit()) {
 
314
      ++PhysRegDefs[Reg];
 
315
      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
 
316
        ++PhysRegDefs[*AS];
 
317
      if (!MO.isDead())
 
318
        // Non-dead implicit def? This cannot be hoisted.
 
319
        RuledOut = true;
 
320
      // No need to check if a dead implicit def is also defined by
 
321
      // another instruction.
 
322
      continue;
 
323
    }
 
324
 
 
325
    // FIXME: For now, avoid instructions with multiple defs, unless
 
326
    // it's a dead implicit def.
 
327
    if (Def)
 
328
      RuledOut = true;
 
329
    else
 
330
      Def = Reg;
 
331
 
 
332
    // If we have already seen another instruction that defines the same
 
333
    // register, then this is not safe.
 
334
    if (++PhysRegDefs[Reg] > 1)
 
335
      // MI defined register is seen defined by another instruction in
 
336
      // the loop, it cannot be a LICM candidate.
 
337
      RuledOut = true;
 
338
    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
 
339
      if (++PhysRegDefs[*AS] > 1)
 
340
        RuledOut = true;
 
341
  }
 
342
 
 
343
  // Only consider reloads for now and remats which do not have register
 
344
  // operands. FIXME: Consider unfold load folding instructions.
 
345
  if (Def && !RuledOut) {
 
346
    int FI = INT_MIN;
 
347
    if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) ||
 
348
        (TII->isLoadFromStackSlot(MI, FI) && MFI->isSpillSlotObjectIndex(FI)))
 
349
      Candidates.push_back(CandidateInfo(MI, Def, FI));
 
350
  }
 
351
}
 
352
 
 
353
/// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop
 
354
/// invariants out to the preheader.
 
355
void MachineLICM::HoistRegionPostRA() {
 
356
  unsigned NumRegs = TRI->getNumRegs();
 
357
  unsigned *PhysRegDefs = new unsigned[NumRegs];
 
358
  std::fill(PhysRegDefs, PhysRegDefs + NumRegs, 0);
 
359
 
 
360
  SmallVector<CandidateInfo, 32> Candidates;
 
361
  SmallSet<int, 32> StoredFIs;
 
362
 
 
363
  // Walk the entire region, count number of defs for each register, and
 
364
  // collect potential LICM candidates.
 
365
  const std::vector<MachineBasicBlock*> Blocks = CurLoop->getBlocks();
 
366
  for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
 
367
    MachineBasicBlock *BB = Blocks[i];
 
368
    // Conservatively treat live-in's as an external def.
 
369
    // FIXME: That means a reload that're reused in successor block(s) will not
 
370
    // be LICM'ed.
 
371
    for (MachineBasicBlock::livein_iterator I = BB->livein_begin(),
 
372
           E = BB->livein_end(); I != E; ++I) {
 
373
      unsigned Reg = *I;
 
374
      ++PhysRegDefs[Reg];
 
375
      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
 
376
        ++PhysRegDefs[*AS];
 
377
    }
 
378
 
 
379
    for (MachineBasicBlock::iterator
 
380
           MII = BB->begin(), E = BB->end(); MII != E; ++MII) {
 
381
      MachineInstr *MI = &*MII;
 
382
      ProcessMI(MI, PhysRegDefs, StoredFIs, Candidates);
 
383
    }
 
384
  }
 
385
 
 
386
  // Now evaluate whether the potential candidates qualify.
 
387
  // 1. Check if the candidate defined register is defined by another
 
388
  //    instruction in the loop.
 
389
  // 2. If the candidate is a load from stack slot (always true for now),
 
390
  //    check if the slot is stored anywhere in the loop.
 
391
  for (unsigned i = 0, e = Candidates.size(); i != e; ++i) {
 
392
    if (Candidates[i].FI != INT_MIN &&
 
393
        StoredFIs.count(Candidates[i].FI))
 
394
      continue;
 
395
 
 
396
    if (PhysRegDefs[Candidates[i].Def] == 1) {
 
397
      bool Safe = true;
 
398
      MachineInstr *MI = Candidates[i].MI;
 
399
      for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
 
400
        const MachineOperand &MO = MI->getOperand(j);
 
401
        if (!MO.isReg() || MO.isDef() || !MO.getReg())
 
402
          continue;
 
403
        if (PhysRegDefs[MO.getReg()]) {
 
404
          // If it's using a non-loop-invariant register, then it's obviously
 
405
          // not safe to hoist.
 
406
          Safe = false;
 
407
          break;
 
408
        }
 
409
      }
 
410
      if (Safe)
 
411
        HoistPostRA(MI, Candidates[i].Def);
 
412
    }
 
413
  }
 
414
 
 
415
  delete[] PhysRegDefs;
 
416
}
 
417
 
 
418
/// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the current
 
419
/// loop, and make sure it is not killed by any instructions in the loop.
 
420
void MachineLICM::AddToLiveIns(unsigned Reg) {
 
421
  const std::vector<MachineBasicBlock*> Blocks = CurLoop->getBlocks();
 
422
  for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
 
423
    MachineBasicBlock *BB = Blocks[i];
 
424
    if (!BB->isLiveIn(Reg))
 
425
      BB->addLiveIn(Reg);
 
426
    for (MachineBasicBlock::iterator
 
427
           MII = BB->begin(), E = BB->end(); MII != E; ++MII) {
 
428
      MachineInstr *MI = &*MII;
 
429
      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
430
        MachineOperand &MO = MI->getOperand(i);
 
431
        if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue;
 
432
        if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg()))
 
433
          MO.setIsKill(false);
 
434
      }
 
435
    }
 
436
  }
 
437
}
 
438
 
 
439
/// HoistPostRA - When an instruction is found to only use loop invariant
 
440
/// operands that is safe to hoist, this instruction is called to do the
 
441
/// dirty work.
 
442
void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) {
 
443
  MachineBasicBlock *Preheader = getCurPreheader();
 
444
  if (!Preheader) return;
 
445
 
 
446
  // Now move the instructions to the predecessor, inserting it before any
 
447
  // terminator instructions.
 
448
  DEBUG({
 
449
      dbgs() << "Hoisting " << *MI;
 
450
      if (Preheader->getBasicBlock())
 
451
        dbgs() << " to MachineBasicBlock "
 
452
               << Preheader->getName();
 
453
      if (MI->getParent()->getBasicBlock())
 
454
        dbgs() << " from MachineBasicBlock "
 
455
               << MI->getParent()->getName();
 
456
      dbgs() << "\n";
 
457
    });
 
458
 
 
459
  // Splice the instruction to the preheader.
 
460
  MachineBasicBlock *MBB = MI->getParent();
 
461
  Preheader->splice(Preheader->getFirstTerminator(), MBB, MI);
 
462
 
 
463
  // Add register to livein list to all the BBs in the current loop since a 
 
464
  // loop invariant must be kept live throughout the whole loop. This is
 
465
  // important to ensure later passes do not scavenge the def register.
 
466
  AddToLiveIns(Def);
 
467
 
 
468
  ++NumPostRAHoisted;
 
469
  Changed = true;
 
470
}
 
471
 
 
472
/// HoistRegion - Walk the specified region of the CFG (defined by all blocks
 
473
/// dominated by the specified block, and that are in the current loop) in depth
 
474
/// first order w.r.t the DominatorTree. This allows us to visit definitions
 
475
/// before uses, allowing us to hoist a loop body in one pass without iteration.
 
476
///
 
477
void MachineLICM::HoistRegion(MachineDomTreeNode *N) {
 
478
  assert(N != 0 && "Null dominator tree node?");
 
479
  MachineBasicBlock *BB = N->getBlock();
 
480
 
 
481
  // If this subregion is not in the top level loop at all, exit.
 
482
  if (!CurLoop->contains(BB)) return;
 
483
 
 
484
  for (MachineBasicBlock::iterator
 
485
         MII = BB->begin(), E = BB->end(); MII != E; ) {
 
486
    MachineBasicBlock::iterator NextMII = MII; ++NextMII;
 
487
    Hoist(&*MII);
 
488
    MII = NextMII;
 
489
  }
 
490
 
 
491
  // Don't hoist things out of a large switch statement.  This often causes
 
492
  // code to be hoisted that wasn't going to be executed, and increases
 
493
  // register pressure in a situation where it's likely to matter.
 
494
  if (BB->succ_size() < 25) {
 
495
    const std::vector<MachineDomTreeNode*> &Children = N->getChildren();
 
496
    for (unsigned I = 0, E = Children.size(); I != E; ++I)
 
497
      HoistRegion(Children[I]);
 
498
  }
 
499
}
 
500
 
 
501
/// IsLICMCandidate - Returns true if the instruction may be a suitable
 
502
/// candidate for LICM. e.g. If the instruction is a call, then it's obviously
 
503
/// not safe to hoist it.
 
504
bool MachineLICM::IsLICMCandidate(MachineInstr &I) {
 
505
  // Check if it's safe to move the instruction.
 
506
  bool DontMoveAcrossStore = true;
 
507
  if (!I.isSafeToMove(TII, AA, DontMoveAcrossStore))
 
508
    return false;
 
509
  
 
510
  return true;
 
511
}
 
512
 
 
513
/// IsLoopInvariantInst - Returns true if the instruction is loop
 
514
/// invariant. I.e., all virtual register operands are defined outside of the
 
515
/// loop, physical registers aren't accessed explicitly, and there are no side
 
516
/// effects that aren't captured by the operands or other flags.
 
517
/// 
 
518
bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) {
 
519
  if (!IsLICMCandidate(I))
 
520
    return false;
 
521
 
 
522
  // The instruction is loop invariant if all of its operands are.
 
523
  for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 
524
    const MachineOperand &MO = I.getOperand(i);
 
525
 
 
526
    if (!MO.isReg())
 
527
      continue;
 
528
 
 
529
    unsigned Reg = MO.getReg();
 
530
    if (Reg == 0) continue;
 
531
 
 
532
    // Don't hoist an instruction that uses or defines a physical register.
 
533
    if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 
534
      if (MO.isUse()) {
 
535
        // If the physreg has no defs anywhere, it's just an ambient register
 
536
        // and we can freely move its uses. Alternatively, if it's allocatable,
 
537
        // it could get allocated to something with a def during allocation.
 
538
        if (!RegInfo->def_empty(Reg))
 
539
          return false;
 
540
        if (AllocatableSet.test(Reg))
 
541
          return false;
 
542
        // Check for a def among the register's aliases too.
 
543
        for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
 
544
          unsigned AliasReg = *Alias;
 
545
          if (!RegInfo->def_empty(AliasReg))
 
546
            return false;
 
547
          if (AllocatableSet.test(AliasReg))
 
548
            return false;
 
549
        }
 
550
        // Otherwise it's safe to move.
 
551
        continue;
 
552
      } else if (!MO.isDead()) {
 
553
        // A def that isn't dead. We can't move it.
 
554
        return false;
 
555
      } else if (CurLoop->getHeader()->isLiveIn(Reg)) {
 
556
        // If the reg is live into the loop, we can't hoist an instruction
 
557
        // which would clobber it.
 
558
        return false;
 
559
      }
 
560
    }
 
561
 
 
562
    if (!MO.isUse())
 
563
      continue;
 
564
 
 
565
    assert(RegInfo->getVRegDef(Reg) &&
 
566
           "Machine instr not mapped for this vreg?!");
 
567
 
 
568
    // If the loop contains the definition of an operand, then the instruction
 
569
    // isn't loop invariant.
 
570
    if (CurLoop->contains(RegInfo->getVRegDef(Reg)))
 
571
      return false;
 
572
  }
 
573
 
 
574
  // If we got this far, the instruction is loop invariant!
 
575
  return true;
 
576
}
 
577
 
 
578
 
 
579
/// HasPHIUses - Return true if the specified register has any PHI use.
 
580
static bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) {
 
581
  for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg),
 
582
         UE = RegInfo->use_end(); UI != UE; ++UI) {
 
583
    MachineInstr *UseMI = &*UI;
 
584
    if (UseMI->isPHI())
 
585
      return true;
 
586
  }
 
587
  return false;
 
588
}
 
589
 
 
590
/// isLoadFromConstantMemory - Return true if the given instruction is a
 
591
/// load from constant memory. Machine LICM will hoist these even if they are
 
592
/// not re-materializable.
 
593
bool MachineLICM::isLoadFromConstantMemory(MachineInstr *MI) {
 
594
  if (!MI->getDesc().mayLoad()) return false;
 
595
  if (!MI->hasOneMemOperand()) return false;
 
596
  MachineMemOperand *MMO = *MI->memoperands_begin();
 
597
  if (MMO->isVolatile()) return false;
 
598
  if (!MMO->getValue()) return false;
 
599
  const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(MMO->getValue());
 
600
  if (PSV) {
 
601
    MachineFunction &MF = *MI->getParent()->getParent();
 
602
    return PSV->isConstant(MF.getFrameInfo());
 
603
  } else {
 
604
    return AA->pointsToConstantMemory(MMO->getValue());
 
605
  }
 
606
}
 
607
 
 
608
/// IsProfitableToHoist - Return true if it is potentially profitable to hoist
 
609
/// the given loop invariant.
 
610
bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) {
 
611
  // FIXME: For now, only hoist re-materilizable instructions. LICM will
 
612
  // increase register pressure. We want to make sure it doesn't increase
 
613
  // spilling.
 
614
  // Also hoist loads from constant memory, e.g. load from stubs, GOT. Hoisting
 
615
  // these tend to help performance in low register pressure situation. The
 
616
  // trade off is it may cause spill in high pressure situation. It will end up
 
617
  // adding a store in the loop preheader. But the reload is no more expensive.
 
618
  // The side benefit is these loads are frequently CSE'ed.
 
619
  if (!TII->isTriviallyReMaterializable(&MI, AA)) {
 
620
    if (!isLoadFromConstantMemory(&MI))
 
621
      return false;
 
622
  }
 
623
 
 
624
  // If result(s) of this instruction is used by PHIs, then don't hoist it.
 
625
  // The presence of joins makes it difficult for current register allocator
 
626
  // implementation to perform remat.
 
627
  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 
628
    const MachineOperand &MO = MI.getOperand(i);
 
629
    if (!MO.isReg() || !MO.isDef())
 
630
      continue;
 
631
    if (HasPHIUses(MO.getReg(), RegInfo))
 
632
      return false;
 
633
  }
 
634
 
 
635
  return true;
 
636
}
 
637
 
 
638
MachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) {
 
639
  // If not, we may be able to unfold a load and hoist that.
 
640
  // First test whether the instruction is loading from an amenable
 
641
  // memory location.
 
642
  if (!isLoadFromConstantMemory(MI))
 
643
    return 0;
 
644
 
 
645
  // Next determine the register class for a temporary register.
 
646
  unsigned LoadRegIndex;
 
647
  unsigned NewOpc =
 
648
    TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(),
 
649
                                    /*UnfoldLoad=*/true,
 
650
                                    /*UnfoldStore=*/false,
 
651
                                    &LoadRegIndex);
 
652
  if (NewOpc == 0) return 0;
 
653
  const TargetInstrDesc &TID = TII->get(NewOpc);
 
654
  if (TID.getNumDefs() != 1) return 0;
 
655
  const TargetRegisterClass *RC = TID.OpInfo[LoadRegIndex].getRegClass(TRI);
 
656
  // Ok, we're unfolding. Create a temporary register and do the unfold.
 
657
  unsigned Reg = RegInfo->createVirtualRegister(RC);
 
658
 
 
659
  MachineFunction &MF = *MI->getParent()->getParent();
 
660
  SmallVector<MachineInstr *, 2> NewMIs;
 
661
  bool Success =
 
662
    TII->unfoldMemoryOperand(MF, MI, Reg,
 
663
                             /*UnfoldLoad=*/true, /*UnfoldStore=*/false,
 
664
                             NewMIs);
 
665
  (void)Success;
 
666
  assert(Success &&
 
667
         "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
 
668
         "succeeded!");
 
669
  assert(NewMIs.size() == 2 &&
 
670
         "Unfolded a load into multiple instructions!");
 
671
  MachineBasicBlock *MBB = MI->getParent();
 
672
  MBB->insert(MI, NewMIs[0]);
 
673
  MBB->insert(MI, NewMIs[1]);
 
674
  // If unfolding produced a load that wasn't loop-invariant or profitable to
 
675
  // hoist, discard the new instructions and bail.
 
676
  if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) {
 
677
    NewMIs[0]->eraseFromParent();
 
678
    NewMIs[1]->eraseFromParent();
 
679
    return 0;
 
680
  }
 
681
  // Otherwise we successfully unfolded a load that we can hoist.
 
682
  MI->eraseFromParent();
 
683
  return NewMIs[0];
 
684
}
 
685
 
 
686
void MachineLICM::InitCSEMap(MachineBasicBlock *BB) {
 
687
  for (MachineBasicBlock::iterator I = BB->begin(),E = BB->end(); I != E; ++I) {
 
688
    const MachineInstr *MI = &*I;
 
689
    // FIXME: For now, only hoist re-materilizable instructions. LICM will
 
690
    // increase register pressure. We want to make sure it doesn't increase
 
691
    // spilling.
 
692
    if (TII->isTriviallyReMaterializable(MI, AA)) {
 
693
      unsigned Opcode = MI->getOpcode();
 
694
      DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator
 
695
        CI = CSEMap.find(Opcode);
 
696
      if (CI != CSEMap.end())
 
697
        CI->second.push_back(MI);
 
698
      else {
 
699
        std::vector<const MachineInstr*> CSEMIs;
 
700
        CSEMIs.push_back(MI);
 
701
        CSEMap.insert(std::make_pair(Opcode, CSEMIs));
 
702
      }
 
703
    }
 
704
  }
 
705
}
 
706
 
 
707
const MachineInstr*
 
708
MachineLICM::LookForDuplicate(const MachineInstr *MI,
 
709
                              std::vector<const MachineInstr*> &PrevMIs) {
 
710
  for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) {
 
711
    const MachineInstr *PrevMI = PrevMIs[i];
 
712
    if (TII->produceSameValue(MI, PrevMI))
 
713
      return PrevMI;
 
714
  }
 
715
  return 0;
 
716
}
 
717
 
 
718
bool MachineLICM::EliminateCSE(MachineInstr *MI,
 
719
          DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI) {
 
720
  // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
 
721
  // the undef property onto uses.
 
722
  if (CI == CSEMap.end() || MI->isImplicitDef())
 
723
    return false;
 
724
 
 
725
  if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
 
726
    DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
 
727
 
 
728
    // Replace virtual registers defined by MI by their counterparts defined
 
729
    // by Dup.
 
730
    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
731
      const MachineOperand &MO = MI->getOperand(i);
 
732
 
 
733
      // Physical registers may not differ here.
 
734
      assert((!MO.isReg() || MO.getReg() == 0 ||
 
735
              !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) ||
 
736
              MO.getReg() == Dup->getOperand(i).getReg()) &&
 
737
             "Instructions with different phys regs are not identical!");
 
738
 
 
739
      if (MO.isReg() && MO.isDef() &&
 
740
          !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) {
 
741
        RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg());
 
742
        RegInfo->clearKillFlags(Dup->getOperand(i).getReg());
 
743
      }
 
744
    }
 
745
    MI->eraseFromParent();
 
746
    ++NumCSEed;
 
747
    return true;
 
748
  }
 
749
  return false;
 
750
}
 
751
 
 
752
/// Hoist - When an instruction is found to use only loop invariant operands
 
753
/// that are safe to hoist, this instruction is called to do the dirty work.
 
754
///
 
755
void MachineLICM::Hoist(MachineInstr *MI) {
 
756
  MachineBasicBlock *Preheader = getCurPreheader();
 
757
  if (!Preheader) return;
 
758
 
 
759
  // First check whether we should hoist this instruction.
 
760
  if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
 
761
    // If not, try unfolding a hoistable load.
 
762
    MI = ExtractHoistableLoad(MI);
 
763
    if (!MI) return;
 
764
  }
 
765
 
 
766
  // Now move the instructions to the predecessor, inserting it before any
 
767
  // terminator instructions.
 
768
  DEBUG({
 
769
      dbgs() << "Hoisting " << *MI;
 
770
      if (Preheader->getBasicBlock())
 
771
        dbgs() << " to MachineBasicBlock "
 
772
               << Preheader->getName();
 
773
      if (MI->getParent()->getBasicBlock())
 
774
        dbgs() << " from MachineBasicBlock "
 
775
               << MI->getParent()->getName();
 
776
      dbgs() << "\n";
 
777
    });
 
778
 
 
779
  // If this is the first instruction being hoisted to the preheader,
 
780
  // initialize the CSE map with potential common expressions.
 
781
  if (FirstInLoop) {
 
782
    InitCSEMap(Preheader);
 
783
    FirstInLoop = false;
 
784
  }
 
785
 
 
786
  // Look for opportunity to CSE the hoisted instruction.
 
787
  unsigned Opcode = MI->getOpcode();
 
788
  DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator
 
789
    CI = CSEMap.find(Opcode);
 
790
  if (!EliminateCSE(MI, CI)) {
 
791
    // Otherwise, splice the instruction to the preheader.
 
792
    Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
 
793
 
 
794
    // Clear the kill flags of any register this instruction defines,
 
795
    // since they may need to be live throughout the entire loop
 
796
    // rather than just live for part of it.
 
797
    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
798
      MachineOperand &MO = MI->getOperand(i);
 
799
      if (MO.isReg() && MO.isDef() && !MO.isDead())
 
800
        RegInfo->clearKillFlags(MO.getReg());
 
801
    }
 
802
 
 
803
    // Add to the CSE map.
 
804
    if (CI != CSEMap.end())
 
805
      CI->second.push_back(MI);
 
806
    else {
 
807
      std::vector<const MachineInstr*> CSEMIs;
 
808
      CSEMIs.push_back(MI);
 
809
      CSEMap.insert(std::make_pair(Opcode, CSEMIs));
 
810
    }
 
811
  }
 
812
 
 
813
  ++NumHoisted;
 
814
  Changed = true;
 
815
}
 
816
 
 
817
MachineBasicBlock *MachineLICM::getCurPreheader() {
 
818
  // Determine the block to which to hoist instructions. If we can't find a
 
819
  // suitable loop predecessor, we can't do any hoisting.
 
820
 
 
821
  // If we've tried to get a preheader and failed, don't try again.
 
822
  if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1))
 
823
    return 0;
 
824
 
 
825
  if (!CurPreheader) {
 
826
    CurPreheader = CurLoop->getLoopPreheader();
 
827
    if (!CurPreheader) {
 
828
      MachineBasicBlock *Pred = CurLoop->getLoopPredecessor();
 
829
      if (!Pred) {
 
830
        CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
 
831
        return 0;
 
832
      }
 
833
 
 
834
      CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), this);
 
835
      if (!CurPreheader) {
 
836
        CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
 
837
        return 0;
 
838
      }
 
839
    }
 
840
  }
 
841
  return CurPreheader;
 
842
}