← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/StackSlotColoring.cpp
 
1
//===-- StackSlotColoring.cpp - Stack slot coloring 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 file implements the stack slot coloring pass.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
#define DEBUG_TYPE "stackcoloring"
 
15
#include "VirtRegMap.h"
 
16
#include "llvm/CodeGen/Passes.h"
 
17
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 
18
#include "llvm/CodeGen/LiveStackAnalysis.h"
 
19
#include "llvm/CodeGen/MachineFrameInfo.h"
 
20
#include "llvm/CodeGen/MachineLoopInfo.h"
 
21
#include "llvm/CodeGen/MachineMemOperand.h"
 
22
#include "llvm/CodeGen/MachineRegisterInfo.h"
 
23
#include "llvm/CodeGen/PseudoSourceValue.h"
 
24
#include "llvm/Support/CommandLine.h"
 
25
#include "llvm/Support/Debug.h"
 
26
#include "llvm/Target/TargetInstrInfo.h"
 
27
#include "llvm/Target/TargetMachine.h"
 
28
#include "llvm/ADT/BitVector.h"
 
29
#include "llvm/ADT/SmallSet.h"
 
30
#include "llvm/ADT/SmallVector.h"
 
31
#include "llvm/ADT/Statistic.h"
 
32
#include <vector>
 
33
using namespace llvm;
 
34
 
 
35
static cl::opt<bool>
 
36
DisableSharing("no-stack-slot-sharing",
 
37
             cl::init(false), cl::Hidden,
 
38
             cl::desc("Suppress slot sharing during stack coloring"));
 
39
 
 
40
static cl::opt<bool>
 
41
ColorWithRegsOpt("color-ss-with-regs",
 
42
                 cl::init(false), cl::Hidden,
 
43
                 cl::desc("Color stack slots with free registers"));
 
44
 
 
45
 
 
46
static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden);
 
47
 
 
48
STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring");
 
49
STATISTIC(NumRegRepl,    "Number of stack slot refs replaced with reg refs");
 
50
STATISTIC(NumLoadElim,   "Number of loads eliminated");
 
51
STATISTIC(NumStoreElim,  "Number of stores eliminated");
 
52
STATISTIC(NumDead,       "Number of trivially dead stack accesses eliminated");
 
53
 
 
54
namespace {
 
55
  class StackSlotColoring : public MachineFunctionPass {
 
56
    bool ColorWithRegs;
 
57
    LiveStacks* LS;
 
58
    VirtRegMap* VRM;
 
59
    MachineFrameInfo *MFI;
 
60
    MachineRegisterInfo *MRI;
 
61
    const TargetInstrInfo  *TII;
 
62
    const TargetRegisterInfo *TRI;
 
63
    const MachineLoopInfo *loopInfo;
 
64
 
 
65
    // SSIntervals - Spill slot intervals.
 
66
    std::vector<LiveInterval*> SSIntervals;
 
67
 
 
68
    // SSRefs - Keep a list of frame index references for each spill slot.
 
69
    SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs;
 
70
 
 
71
    // OrigAlignments - Alignments of stack objects before coloring.
 
72
    SmallVector<unsigned, 16> OrigAlignments;
 
73
 
 
74
    // OrigSizes - Sizess of stack objects before coloring.
 
75
    SmallVector<unsigned, 16> OrigSizes;
 
76
 
 
77
    // AllColors - If index is set, it's a spill slot, i.e. color.
 
78
    // FIXME: This assumes PEI locate spill slot with smaller indices
 
79
    // closest to stack pointer / frame pointer. Therefore, smaller
 
80
    // index == better color.
 
81
    BitVector AllColors;
 
82
 
 
83
    // NextColor - Next "color" that's not yet used.
 
84
    int NextColor;
 
85
 
 
86
    // UsedColors - "Colors" that have been assigned.
 
87
    BitVector UsedColors;
 
88
 
 
89
    // Assignments - Color to intervals mapping.
 
90
    SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments;
 
91
 
 
92
  public:
 
93
    static char ID; // Pass identification
 
94
    StackSlotColoring() :
 
95
      MachineFunctionPass(&ID), ColorWithRegs(false), NextColor(-1) {}
 
96
    StackSlotColoring(bool RegColor) :
 
97
      MachineFunctionPass(&ID), ColorWithRegs(RegColor), NextColor(-1) {}
 
98
    
 
99
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
100
      AU.setPreservesCFG();
 
101
      AU.addRequired<SlotIndexes>();
 
102
      AU.addPreserved<SlotIndexes>();
 
103
      AU.addRequired<LiveStacks>();
 
104
      AU.addRequired<VirtRegMap>();
 
105
      AU.addPreserved<VirtRegMap>();      
 
106
      AU.addRequired<MachineLoopInfo>();
 
107
      AU.addPreserved<MachineLoopInfo>();
 
108
      AU.addPreservedID(MachineDominatorsID);
 
109
      MachineFunctionPass::getAnalysisUsage(AU);
 
110
    }
 
111
 
 
112
    virtual bool runOnMachineFunction(MachineFunction &MF);
 
113
    virtual const char* getPassName() const {
 
114
      return "Stack Slot Coloring";
 
115
    }
 
116
 
 
117
  private:
 
118
    void InitializeSlots();
 
119
    void ScanForSpillSlotRefs(MachineFunction &MF);
 
120
    bool OverlapWithAssignments(LiveInterval *li, int Color) const;
 
121
    int ColorSlot(LiveInterval *li);
 
122
    bool ColorSlots(MachineFunction &MF);
 
123
    bool ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
 
124
                                SmallVector<SmallVector<int, 4>, 16> &RevMap,
 
125
                                BitVector &SlotIsReg);
 
126
    void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI,
 
127
                            MachineFunction &MF);
 
128
    bool PropagateBackward(MachineBasicBlock::iterator MII,
 
129
                           MachineBasicBlock *MBB,
 
130
                           unsigned OldReg, unsigned NewReg);
 
131
    bool PropagateForward(MachineBasicBlock::iterator MII,
 
132
                          MachineBasicBlock *MBB,
 
133
                          unsigned OldReg, unsigned NewReg);
 
134
    void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI,
 
135
                                    unsigned Reg, const TargetRegisterClass *RC,
 
136
                                    SmallSet<unsigned, 4> &Defs,
 
137
                                    MachineFunction &MF);
 
138
    bool AllMemRefsCanBeUnfolded(int SS);
 
139
    bool RemoveDeadStores(MachineBasicBlock* MBB);
 
140
  };
 
141
} // end anonymous namespace
 
142
 
 
143
char StackSlotColoring::ID = 0;
 
144
 
 
145
static RegisterPass<StackSlotColoring>
 
146
X("stack-slot-coloring", "Stack Slot Coloring");
 
147
 
 
148
FunctionPass *llvm::createStackSlotColoringPass(bool RegColor) {
 
149
  return new StackSlotColoring(RegColor);
 
150
}
 
151
 
 
152
namespace {
 
153
  // IntervalSorter - Comparison predicate that sort live intervals by
 
154
  // their weight.
 
155
  struct IntervalSorter {
 
156
    bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {
 
157
      return LHS->weight > RHS->weight;
 
158
    }
 
159
  };
 
160
}
 
161
 
 
162
/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot
 
163
/// references and update spill slot weights.
 
164
void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {
 
165
  SSRefs.resize(MFI->getObjectIndexEnd());
 
166
 
 
167
  // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.
 
168
  for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
 
169
       MBBI != E; ++MBBI) {
 
170
    MachineBasicBlock *MBB = &*MBBI;
 
171
    unsigned loopDepth = loopInfo->getLoopDepth(MBB);
 
172
    for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end();
 
173
         MII != EE; ++MII) {
 
174
      MachineInstr *MI = &*MII;
 
175
      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
176
        MachineOperand &MO = MI->getOperand(i);
 
177
        if (!MO.isFI())
 
178
          continue;
 
179
        int FI = MO.getIndex();
 
180
        if (FI < 0)
 
181
          continue;
 
182
        if (!LS->hasInterval(FI))
 
183
          continue;
 
184
        LiveInterval &li = LS->getInterval(FI);
 
185
        li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth);
 
186
        SSRefs[FI].push_back(MI);
 
187
      }
 
188
    }
 
189
  }
 
190
}
 
191
 
 
192
/// InitializeSlots - Process all spill stack slot liveintervals and add them
 
193
/// to a sorted (by weight) list.
 
194
void StackSlotColoring::InitializeSlots() {
 
195
  int LastFI = MFI->getObjectIndexEnd();
 
196
  OrigAlignments.resize(LastFI);
 
197
  OrigSizes.resize(LastFI);
 
198
  AllColors.resize(LastFI);
 
199
  UsedColors.resize(LastFI);
 
200
  Assignments.resize(LastFI);
 
201
 
 
202
  // Gather all spill slots into a list.
 
203
  DEBUG(dbgs() << "Spill slot intervals:\n");
 
204
  for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) {
 
205
    LiveInterval &li = i->second;
 
206
    DEBUG(li.dump());
 
207
    int FI = li.getStackSlotIndex();
 
208
    if (MFI->isDeadObjectIndex(FI))
 
209
      continue;
 
210
    SSIntervals.push_back(&li);
 
211
    OrigAlignments[FI] = MFI->getObjectAlignment(FI);
 
212
    OrigSizes[FI]      = MFI->getObjectSize(FI);
 
213
    AllColors.set(FI);
 
214
  }
 
215
  DEBUG(dbgs() << '\n');
 
216
 
 
217
  // Sort them by weight.
 
218
  std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
 
219
 
 
220
  // Get first "color".
 
221
  NextColor = AllColors.find_first();
 
222
}
 
223
 
 
224
/// OverlapWithAssignments - Return true if LiveInterval overlaps with any
 
225
/// LiveIntervals that have already been assigned to the specified color.
 
226
bool
 
227
StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const {
 
228
  const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color];
 
229
  for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) {
 
230
    LiveInterval *OtherLI = OtherLIs[i];
 
231
    if (OtherLI->overlaps(*li))
 
232
      return true;
 
233
  }
 
234
  return false;
 
235
}
 
236
 
 
237
/// ColorSlotsWithFreeRegs - If there are any free registers available, try
 
238
/// replacing spill slots references with registers instead.
 
239
bool
 
240
StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
 
241
                                   SmallVector<SmallVector<int, 4>, 16> &RevMap,
 
242
                                   BitVector &SlotIsReg) {
 
243
  if (!(ColorWithRegs || ColorWithRegsOpt) || !VRM->HasUnusedRegisters())
 
244
    return false;
 
245
 
 
246
  bool Changed = false;
 
247
  DEBUG(dbgs() << "Assigning unused registers to spill slots:\n");
 
248
  for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
 
249
    LiveInterval *li = SSIntervals[i];
 
250
    int SS = li->getStackSlotIndex();
 
251
    if (!UsedColors[SS] || li->weight < 20)
 
252
      // If the weight is < 20, i.e. two references in a loop with depth 1,
 
253
      // don't bother with it.
 
254
      continue;
 
255
 
 
256
    // These slots allow to share the same registers.
 
257
    bool AllColored = true;
 
258
    SmallVector<unsigned, 4> ColoredRegs;
 
259
    for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) {
 
260
      int RSS = RevMap[SS][j];
 
261
      const TargetRegisterClass *RC = LS->getIntervalRegClass(RSS);
 
262
      // If it's not colored to another stack slot, try coloring it
 
263
      // to a "free" register.
 
264
      if (!RC) {
 
265
        AllColored = false;
 
266
        continue;
 
267
      }
 
268
      unsigned Reg = VRM->getFirstUnusedRegister(RC);
 
269
      if (!Reg) {
 
270
        AllColored = false;
 
271
        continue;
 
272
      }
 
273
      if (!AllMemRefsCanBeUnfolded(RSS)) {
 
274
        AllColored = false;
 
275
        continue;
 
276
      } else {
 
277
        DEBUG(dbgs() << "Assigning fi#" << RSS << " to "
 
278
                     << TRI->getName(Reg) << '\n');
 
279
        ColoredRegs.push_back(Reg);
 
280
        SlotMapping[RSS] = Reg;
 
281
        SlotIsReg.set(RSS);
 
282
        Changed = true;
 
283
      }
 
284
    }
 
285
 
 
286
    // Register and its sub-registers are no longer free.
 
287
    while (!ColoredRegs.empty()) {
 
288
      unsigned Reg = ColoredRegs.back();
 
289
      ColoredRegs.pop_back();
 
290
      VRM->setRegisterUsed(Reg);
 
291
      // If reg is a callee-saved register, it will have to be spilled in
 
292
      // the prologue.
 
293
      MRI->setPhysRegUsed(Reg);
 
294
      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
 
295
        VRM->setRegisterUsed(*AS);
 
296
        MRI->setPhysRegUsed(*AS);
 
297
      }
 
298
    }
 
299
    // This spill slot is dead after the rewrites
 
300
    if (AllColored) {
 
301
      MFI->RemoveStackObject(SS);
 
302
      ++NumEliminated;
 
303
    }
 
304
  }
 
305
  DEBUG(dbgs() << '\n');
 
306
 
 
307
  return Changed;
 
308
}
 
309
 
 
310
/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.
 
311
///
 
312
int StackSlotColoring::ColorSlot(LiveInterval *li) {
 
313
  int Color = -1;
 
314
  bool Share = false;
 
315
  if (!DisableSharing) {
 
316
    // Check if it's possible to reuse any of the used colors.
 
317
    Color = UsedColors.find_first();
 
318
    while (Color != -1) {
 
319
      if (!OverlapWithAssignments(li, Color)) {
 
320
        Share = true;
 
321
        ++NumEliminated;
 
322
        break;
 
323
      }
 
324
      Color = UsedColors.find_next(Color);
 
325
    }
 
326
  }
 
327
 
 
328
  // Assign it to the first available color (assumed to be the best) if it's
 
329
  // not possible to share a used color with other objects.
 
330
  if (!Share) {
 
331
    assert(NextColor != -1 && "No more spill slots?");
 
332
    Color = NextColor;
 
333
    UsedColors.set(Color);
 
334
    NextColor = AllColors.find_next(NextColor);
 
335
  }
 
336
 
 
337
  // Record the assignment.
 
338
  Assignments[Color].push_back(li);
 
339
  int FI = li->getStackSlotIndex();
 
340
  DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");
 
341
 
 
342
  // Change size and alignment of the allocated slot. If there are multiple
 
343
  // objects sharing the same slot, then make sure the size and alignment
 
344
  // are large enough for all.
 
345
  unsigned Align = OrigAlignments[FI];
 
346
  if (!Share || Align > MFI->getObjectAlignment(Color))
 
347
    MFI->setObjectAlignment(Color, Align);
 
348
  int64_t Size = OrigSizes[FI];
 
349
  if (!Share || Size > MFI->getObjectSize(Color))
 
350
    MFI->setObjectSize(Color, Size);
 
351
  return Color;
 
352
}
 
353
 
 
354
/// Colorslots - Color all spill stack slots and rewrite all frameindex machine
 
355
/// operands in the function.
 
356
bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
 
357
  unsigned NumObjs = MFI->getObjectIndexEnd();
 
358
  SmallVector<int, 16> SlotMapping(NumObjs, -1);
 
359
  SmallVector<float, 16> SlotWeights(NumObjs, 0.0);
 
360
  SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs);
 
361
  BitVector SlotIsReg(NumObjs);
 
362
  BitVector UsedColors(NumObjs);
 
363
 
 
364
  DEBUG(dbgs() << "Color spill slot intervals:\n");
 
365
  bool Changed = false;
 
366
  for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
 
367
    LiveInterval *li = SSIntervals[i];
 
368
    int SS = li->getStackSlotIndex();
 
369
    int NewSS = ColorSlot(li);
 
370
    assert(NewSS >= 0 && "Stack coloring failed?");
 
371
    SlotMapping[SS] = NewSS;
 
372
    RevMap[NewSS].push_back(SS);
 
373
    SlotWeights[NewSS] += li->weight;
 
374
    UsedColors.set(NewSS);
 
375
    Changed |= (SS != NewSS);
 
376
  }
 
377
 
 
378
  DEBUG(dbgs() << "\nSpill slots after coloring:\n");
 
379
  for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) {
 
380
    LiveInterval *li = SSIntervals[i];
 
381
    int SS = li->getStackSlotIndex();
 
382
    li->weight = SlotWeights[SS];
 
383
  }
 
384
  // Sort them by new weight.
 
385
  std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter());
 
386
 
 
387
#ifndef NDEBUG
 
388
  for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i)
 
389
    DEBUG(SSIntervals[i]->dump());
 
390
  DEBUG(dbgs() << '\n');
 
391
#endif
 
392
 
 
393
  // Can we "color" a stack slot with a unused register?
 
394
  Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg);
 
395
 
 
396
  if (!Changed)
 
397
    return false;
 
398
 
 
399
  // Rewrite all MO_FrameIndex operands.
 
400
  SmallVector<SmallSet<unsigned, 4>, 4> NewDefs(MF.getNumBlockIDs());
 
401
  for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {
 
402
    bool isReg = SlotIsReg[SS];
 
403
    int NewFI = SlotMapping[SS];
 
404
    if (NewFI == -1 || (NewFI == (int)SS && !isReg))
 
405
      continue;
 
406
 
 
407
    const TargetRegisterClass *RC = LS->getIntervalRegClass(SS);
 
408
    SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
 
409
    for (unsigned i = 0, e = RefMIs.size(); i != e; ++i)
 
410
      if (!isReg)
 
411
        RewriteInstruction(RefMIs[i], SS, NewFI, MF);
 
412
      else {
 
413
        // Rewrite to use a register instead.
 
414
        unsigned MBBId = RefMIs[i]->getParent()->getNumber();
 
415
        SmallSet<unsigned, 4> &Defs = NewDefs[MBBId];
 
416
        UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, RC, Defs, MF);
 
417
      }
 
418
  }
 
419
 
 
420
  // Delete unused stack slots.
 
421
  while (NextColor != -1) {
 
422
    DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n");
 
423
    MFI->RemoveStackObject(NextColor);
 
424
    NextColor = AllColors.find_next(NextColor);
 
425
  }
 
426
 
 
427
  return true;
 
428
}
 
429
 
 
430
/// AllMemRefsCanBeUnfolded - Return true if all references of the specified
 
431
/// spill slot index can be unfolded.
 
432
bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) {
 
433
  SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS];
 
434
  for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) {
 
435
    MachineInstr *MI = RefMIs[i];
 
436
    if (TII->isLoadFromStackSlot(MI, SS) ||
 
437
        TII->isStoreToStackSlot(MI, SS))
 
438
      // Restore and spill will become copies.
 
439
      return true;
 
440
    if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false))
 
441
      return false;
 
442
    for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
 
443
      MachineOperand &MO = MI->getOperand(j);
 
444
      if (MO.isFI() && MO.getIndex() != SS)
 
445
        // If it uses another frameindex, we can, currently* unfold it.
 
446
        return false;
 
447
    }
 
448
  }
 
449
  return true;
 
450
}
 
451
 
 
452
/// RewriteInstruction - Rewrite specified instruction by replacing references
 
453
/// to old frame index with new one.
 
454
void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI,
 
455
                                           int NewFI, MachineFunction &MF) {
 
456
  // Update the operands.
 
457
  for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) {
 
458
    MachineOperand &MO = MI->getOperand(i);
 
459
    if (!MO.isFI())
 
460
      continue;
 
461
    int FI = MO.getIndex();
 
462
    if (FI != OldFI)
 
463
      continue;
 
464
    MO.setIndex(NewFI);
 
465
  }
 
466
 
 
467
  // Update the memory references. This changes the MachineMemOperands
 
468
  // directly. They may be in use by multiple instructions, however all
 
469
  // instructions using OldFI are being rewritten to use NewFI.
 
470
  const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI);
 
471
  const Value *NewSV = PseudoSourceValue::getFixedStack(NewFI);
 
472
  for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
 
473
       E = MI->memoperands_end(); I != E; ++I)
 
474
    if ((*I)->getValue() == OldSV)
 
475
      (*I)->setValue(NewSV);
 
476
}
 
477
 
 
478
/// PropagateBackward - Traverse backward and look for the definition of
 
479
/// OldReg. If it can successfully update all of the references with NewReg,
 
480
/// do so and return true.
 
481
bool StackSlotColoring::PropagateBackward(MachineBasicBlock::iterator MII,
 
482
                                          MachineBasicBlock *MBB,
 
483
                                          unsigned OldReg, unsigned NewReg) {
 
484
  if (MII == MBB->begin())
 
485
    return false;
 
486
 
 
487
  SmallVector<MachineOperand*, 4> Uses;
 
488
  SmallVector<MachineOperand*, 4> Refs;
 
489
  while (--MII != MBB->begin()) {
 
490
    bool FoundDef = false;  // Not counting 2address def.
 
491
 
 
492
    Uses.clear();
 
493
    const TargetInstrDesc &TID = MII->getDesc();
 
494
    for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
 
495
      MachineOperand &MO = MII->getOperand(i);
 
496
      if (!MO.isReg())
 
497
        continue;
 
498
      unsigned Reg = MO.getReg();
 
499
      if (Reg == 0)
 
500
        continue;
 
501
      if (Reg == OldReg) {
 
502
        if (MO.isImplicit())
 
503
          return false;
 
504
 
 
505
        // Abort the use is actually a sub-register def. We don't have enough
 
506
        // information to figure out if it is really legal.
 
507
        if (MO.getSubReg() || MII->isExtractSubreg() ||
 
508
            MII->isInsertSubreg() || MII->isSubregToReg())
 
509
          return false;
 
510
 
 
511
        const TargetRegisterClass *RC = TID.OpInfo[i].getRegClass(TRI);
 
512
        if (RC && !RC->contains(NewReg))
 
513
          return false;
 
514
 
 
515
        if (MO.isUse()) {
 
516
          Uses.push_back(&MO);
 
517
        } else {
 
518
          Refs.push_back(&MO);
 
519
          if (!MII->isRegTiedToUseOperand(i))
 
520
            FoundDef = true;
 
521
        }
 
522
      } else if (TRI->regsOverlap(Reg, NewReg)) {
 
523
        return false;
 
524
      } else if (TRI->regsOverlap(Reg, OldReg)) {
 
525
        if (!MO.isUse() || !MO.isKill())
 
526
          return false;
 
527
      }
 
528
    }
 
529
 
 
530
    if (FoundDef) {
 
531
      // Found non-two-address def. Stop here.
 
532
      for (unsigned i = 0, e = Refs.size(); i != e; ++i)
 
533
        Refs[i]->setReg(NewReg);
 
534
      return true;
 
535
    }
 
536
 
 
537
    // Two-address uses must be updated as well.
 
538
    for (unsigned i = 0, e = Uses.size(); i != e; ++i)
 
539
      Refs.push_back(Uses[i]);
 
540
  }
 
541
  return false;
 
542
}
 
543
 
 
544
/// PropagateForward - Traverse forward and look for the kill of OldReg. If
 
545
/// it can successfully update all of the uses with NewReg, do so and
 
546
/// return true.
 
547
bool StackSlotColoring::PropagateForward(MachineBasicBlock::iterator MII,
 
548
                                         MachineBasicBlock *MBB,
 
549
                                         unsigned OldReg, unsigned NewReg) {
 
550
  if (MII == MBB->end())
 
551
    return false;
 
552
 
 
553
  SmallVector<MachineOperand*, 4> Uses;
 
554
  while (++MII != MBB->end()) {
 
555
    bool FoundKill = false;
 
556
    const TargetInstrDesc &TID = MII->getDesc();
 
557
    for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
 
558
      MachineOperand &MO = MII->getOperand(i);
 
559
      if (!MO.isReg())
 
560
        continue;
 
561
      unsigned Reg = MO.getReg();
 
562
      if (Reg == 0)
 
563
        continue;
 
564
      if (Reg == OldReg) {
 
565
        if (MO.isDef() || MO.isImplicit())
 
566
          return false;
 
567
 
 
568
        // Abort the use is actually a sub-register use. We don't have enough
 
569
        // information to figure out if it is really legal.
 
570
        if (MO.getSubReg() || MII->isExtractSubreg())
 
571
          return false;
 
572
 
 
573
        const TargetRegisterClass *RC = TID.OpInfo[i].getRegClass(TRI);
 
574
        if (RC && !RC->contains(NewReg))
 
575
          return false;
 
576
        if (MO.isKill())
 
577
          FoundKill = true;
 
578
 
 
579
        Uses.push_back(&MO);
 
580
      } else if (TRI->regsOverlap(Reg, NewReg) ||
 
581
                 TRI->regsOverlap(Reg, OldReg))
 
582
        return false;
 
583
    }
 
584
    if (FoundKill) {
 
585
      for (unsigned i = 0, e = Uses.size(); i != e; ++i)
 
586
        Uses[i]->setReg(NewReg);
 
587
      return true;
 
588
    }
 
589
  }
 
590
  return false;
 
591
}
 
592
 
 
593
/// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding
 
594
/// folded memory references and replacing those references with register
 
595
/// references instead.
 
596
void
 
597
StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI,
 
598
                                               unsigned Reg,
 
599
                                               const TargetRegisterClass *RC,
 
600
                                               SmallSet<unsigned, 4> &Defs,
 
601
                                               MachineFunction &MF) {
 
602
  MachineBasicBlock *MBB = MI->getParent();
 
603
  if (unsigned DstReg = TII->isLoadFromStackSlot(MI, OldFI)) {
 
604
    if (PropagateForward(MI, MBB, DstReg, Reg)) {
 
605
      DEBUG(dbgs() << "Eliminated load: ");
 
606
      DEBUG(MI->dump());
 
607
      ++NumLoadElim;
 
608
    } else {
 
609
      TII->copyRegToReg(*MBB, MI, DstReg, Reg, RC, RC);
 
610
      ++NumRegRepl;
 
611
    }
 
612
 
 
613
    if (!Defs.count(Reg)) {
 
614
      // If this is the first use of Reg in this MBB and it wasn't previously
 
615
      // defined in MBB, add it to livein.
 
616
      MBB->addLiveIn(Reg);
 
617
      Defs.insert(Reg);
 
618
    }
 
619
  } else if (unsigned SrcReg = TII->isStoreToStackSlot(MI, OldFI)) {
 
620
    if (MI->killsRegister(SrcReg) && PropagateBackward(MI, MBB, SrcReg, Reg)) {
 
621
      DEBUG(dbgs() << "Eliminated store: ");
 
622
      DEBUG(MI->dump());
 
623
      ++NumStoreElim;
 
624
    } else {
 
625
      TII->copyRegToReg(*MBB, MI, Reg, SrcReg, RC, RC);
 
626
      ++NumRegRepl;
 
627
    }
 
628
 
 
629
    // Remember reg has been defined in MBB.
 
630
    Defs.insert(Reg);
 
631
  } else {
 
632
    SmallVector<MachineInstr*, 4> NewMIs;
 
633
    bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs);
 
634
    Success = Success; // Silence compiler warning.
 
635
    assert(Success && "Failed to unfold!");
 
636
    MachineInstr *NewMI = NewMIs[0];
 
637
    MBB->insert(MI, NewMI);
 
638
    ++NumRegRepl;
 
639
 
 
640
    if (NewMI->readsRegister(Reg)) {
 
641
      if (!Defs.count(Reg))
 
642
        // If this is the first use of Reg in this MBB and it wasn't previously
 
643
        // defined in MBB, add it to livein.
 
644
        MBB->addLiveIn(Reg);
 
645
      Defs.insert(Reg);
 
646
    }
 
647
  }
 
648
  MBB->erase(MI);
 
649
}
 
650
 
 
651
/// RemoveDeadStores - Scan through a basic block and look for loads followed
 
652
/// by stores.  If they're both using the same stack slot, then the store is
 
653
/// definitely dead.  This could obviously be much more aggressive (consider
 
654
/// pairs with instructions between them), but such extensions might have a
 
655
/// considerable compile time impact.
 
656
bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {
 
657
  // FIXME: This could be much more aggressive, but we need to investigate
 
658
  // the compile time impact of doing so.
 
659
  bool changed = false;
 
660
 
 
661
  SmallVector<MachineInstr*, 4> toErase;
 
662
 
 
663
  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 
664
       I != E; ++I) {
 
665
    if (DCELimit != -1 && (int)NumDead >= DCELimit)
 
666
      break;
 
667
    
 
668
    MachineBasicBlock::iterator NextMI = llvm::next(I);
 
669
    if (NextMI == MBB->end()) continue;
 
670
    
 
671
    int FirstSS, SecondSS;
 
672
    unsigned LoadReg = 0;
 
673
    unsigned StoreReg = 0;
 
674
    if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue;
 
675
    if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue;
 
676
    if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue;
 
677
    
 
678
    ++NumDead;
 
679
    changed = true;
 
680
    
 
681
    if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) {
 
682
      ++NumDead;
 
683
      toErase.push_back(I);
 
684
    }
 
685
    
 
686
    toErase.push_back(NextMI);
 
687
    ++I;
 
688
  }
 
689
  
 
690
  for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(),
 
691
       E = toErase.end(); I != E; ++I)
 
692
    (*I)->eraseFromParent();
 
693
  
 
694
  return changed;
 
695
}
 
696
 
 
697
 
 
698
bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
 
699
  DEBUG(dbgs() << "********** Stack Slot Coloring **********\n");
 
700
 
 
701
  MFI = MF.getFrameInfo();
 
702
  MRI = &MF.getRegInfo(); 
 
703
  TII = MF.getTarget().getInstrInfo();
 
704
  TRI = MF.getTarget().getRegisterInfo();
 
705
  LS = &getAnalysis<LiveStacks>();
 
706
  VRM = &getAnalysis<VirtRegMap>();
 
707
  loopInfo = &getAnalysis<MachineLoopInfo>();
 
708
 
 
709
  bool Changed = false;
 
710
 
 
711
  unsigned NumSlots = LS->getNumIntervals();
 
712
  if (NumSlots < 2) {
 
713
    if (NumSlots == 0 || !VRM->HasUnusedRegisters())
 
714
      // Nothing to do!
 
715
      return false;
 
716
  }
 
717
 
 
718
  // Gather spill slot references
 
719
  ScanForSpillSlotRefs(MF);
 
720
  InitializeSlots();
 
721
  Changed = ColorSlots(MF);
 
722
 
 
723
  NextColor = -1;
 
724
  SSIntervals.clear();
 
725
  for (unsigned i = 0, e = SSRefs.size(); i != e; ++i)
 
726
    SSRefs[i].clear();
 
727
  SSRefs.clear();
 
728
  OrigAlignments.clear();
 
729
  OrigSizes.clear();
 
730
  AllColors.clear();
 
731
  UsedColors.clear();
 
732
  for (unsigned i = 0, e = Assignments.size(); i != e; ++i)
 
733
    Assignments[i].clear();
 
734
  Assignments.clear();
 
735
 
 
736
  if (Changed) {
 
737
    for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
 
738
      Changed |= RemoveDeadStores(I);
 
739
  }
 
740
 
 
741
  return Changed;
 
742
}