← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/OptimizePHIs.cpp
1
 
//===-- OptimizePHIs.cpp - Optimize machine instruction PHIs --------------===//
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 optimizes machine instruction PHIs to take advantage of
11
 
// opportunities created during DAG legalization.
12
 
//
13
 
//===----------------------------------------------------------------------===//
14
 
 
15
 
#define DEBUG_TYPE "phi-opt"
16
 
#include "llvm/CodeGen/Passes.h"
17
 
#include "llvm/CodeGen/MachineFunctionPass.h"
18
 
#include "llvm/CodeGen/MachineInstr.h"
19
 
#include "llvm/CodeGen/MachineRegisterInfo.h"
20
 
#include "llvm/Target/TargetInstrInfo.h"
21
 
#include "llvm/Function.h"
22
 
#include "llvm/ADT/SmallPtrSet.h"
23
 
#include "llvm/ADT/Statistic.h"
24
 
using namespace llvm;
25
 
 
26
 
STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
27
 
STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
28
 
 
29
 
namespace {
30
 
  class OptimizePHIs : public MachineFunctionPass {
31
 
    MachineRegisterInfo *MRI;
32
 
    const TargetInstrInfo *TII;
33
 
 
34
 
  public:
35
 
    static char ID; // Pass identification
36
 
    OptimizePHIs() : MachineFunctionPass(ID) {}
37
 
 
38
 
    virtual bool runOnMachineFunction(MachineFunction &MF);
39
 
 
40
 
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
41
 
      AU.setPreservesCFG();
42
 
      MachineFunctionPass::getAnalysisUsage(AU);
43
 
    }
44
 
 
45
 
  private:
46
 
    typedef SmallPtrSet<MachineInstr*, 16> InstrSet;
47
 
    typedef SmallPtrSetIterator<MachineInstr*> InstrSetIterator;
48
 
 
49
 
    bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
50
 
                               InstrSet &PHIsInCycle);
51
 
    bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
52
 
    bool OptimizeBB(MachineBasicBlock &MBB);
53
 
  };
54
 
}
55
 
 
56
 
char OptimizePHIs::ID = 0;
57
 
INITIALIZE_PASS(OptimizePHIs, "opt-phis",
58
 
                "Optimize machine instruction PHIs", false, false);
59
 
 
60
 
FunctionPass *llvm::createOptimizePHIsPass() { return new OptimizePHIs(); }
61
 
 
62
 
bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
63
 
  MRI = &Fn.getRegInfo();
64
 
  TII = Fn.getTarget().getInstrInfo();
65
 
 
66
 
  // Find dead PHI cycles and PHI cycles that can be replaced by a single
67
 
  // value.  InstCombine does these optimizations, but DAG legalization may
68
 
  // introduce new opportunities, e.g., when i64 values are split up for
69
 
  // 32-bit targets.
70
 
  bool Changed = false;
71
 
  for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
72
 
    Changed |= OptimizeBB(*I);
73
 
 
74
 
  return Changed;
75
 
}
76
 
 
77
 
/// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
78
 
/// are copies of SingleValReg, possibly via copies through other PHIs.  If
79
 
/// SingleValReg is zero on entry, it is set to the register with the single
80
 
/// non-copy value.  PHIsInCycle is a set used to keep track of the PHIs that
81
 
/// have been scanned.
82
 
bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
83
 
                                         unsigned &SingleValReg,
84
 
                                         InstrSet &PHIsInCycle) {
85
 
  assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
86
 
  unsigned DstReg = MI->getOperand(0).getReg();
87
 
 
88
 
  // See if we already saw this register.
89
 
  if (!PHIsInCycle.insert(MI))
90
 
    return true;
91
 
 
92
 
  // Don't scan crazily complex things.
93
 
  if (PHIsInCycle.size() == 16)
94
 
    return false;
95
 
 
96
 
  // Scan the PHI operands.
97
 
  for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {
98
 
    unsigned SrcReg = MI->getOperand(i).getReg();
99
 
    if (SrcReg == DstReg)
100
 
      continue;
101
 
    MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
102
 
 
103
 
    // Skip over register-to-register moves.
104
 
    if (SrcMI && SrcMI->isCopy() &&
105
 
        !SrcMI->getOperand(0).getSubReg() &&
106
 
        !SrcMI->getOperand(1).getSubReg() &&
107
 
        TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg()))
108
 
      SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg());
109
 
    if (!SrcMI)
110
 
      return false;
111
 
 
112
 
    if (SrcMI->isPHI()) {
113
 
      if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
114
 
        return false;
115
 
    } else {
116
 
      // Fail if there is more than one non-phi/non-move register.
117
 
      if (SingleValReg != 0)
118
 
        return false;
119
 
      SingleValReg = SrcReg;
120
 
    }
121
 
  }
122
 
  return true;
123
 
}
124
 
 
125
 
/// IsDeadPHICycle - Check if the register defined by a PHI is only used by
126
 
/// other PHIs in a cycle.
127
 
bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
128
 
  assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
129
 
  unsigned DstReg = MI->getOperand(0).getReg();
130
 
  assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
131
 
         "PHI destination is not a virtual register");
132
 
 
133
 
  // See if we already saw this register.
134
 
  if (!PHIsInCycle.insert(MI))
135
 
    return true;
136
 
 
137
 
  // Don't scan crazily complex things.
138
 
  if (PHIsInCycle.size() == 16)
139
 
    return false;
140
 
 
141
 
  for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg),
142
 
         E = MRI->use_end(); I != E; ++I) {
143
 
    MachineInstr *UseMI = &*I;
144
 
    if (!UseMI->isPHI() || !IsDeadPHICycle(UseMI, PHIsInCycle))
145
 
      return false;
146
 
  }
147
 
 
148
 
  return true;
149
 
}
150
 
 
151
 
/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
152
 
/// a single value.
153
 
bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
154
 
  bool Changed = false;
155
 
  for (MachineBasicBlock::iterator
156
 
         MII = MBB.begin(), E = MBB.end(); MII != E; ) {
157
 
    MachineInstr *MI = &*MII++;
158
 
    if (!MI->isPHI())
159
 
      break;
160
 
 
161
 
    // Check for single-value PHI cycles.
162
 
    unsigned SingleValReg = 0;
163
 
    InstrSet PHIsInCycle;
164
 
    if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
165
 
        SingleValReg != 0) {
166
 
      MRI->replaceRegWith(MI->getOperand(0).getReg(), SingleValReg);
167
 
      MI->eraseFromParent();
168
 
      ++NumPHICycles;
169
 
      Changed = true;
170
 
      continue;
171
 
    }
172
 
 
173
 
    // Check for dead PHI cycles.
174
 
    PHIsInCycle.clear();
175
 
    if (IsDeadPHICycle(MI, PHIsInCycle)) {
176
 
      for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
177
 
           PI != PE; ++PI) {
178
 
        MachineInstr *PhiMI = *PI;
179
 
        if (&*MII == PhiMI)
180
 
          ++MII;
181
 
        PhiMI->eraseFromParent();
182
 
      }
183
 
      ++NumDeadPHICycles;
184
 
      Changed = true;
185
 
    }
186
 
  }
187
 
  return Changed;
188
 
}