← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to lib/CodeGen/SpillPlacement.h

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/CodeGen/SpillPlacement.h
 
1
//===-- SpillPlacement.h - Optimal Spill Code Placement --------*- C++ -*--===//
 
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 analysis computes the optimal spill code placement between basic blocks.
 
11
//
 
12
// The runOnMachineFunction() method only precomputes some profiling information
 
13
// about the CFG. The real work is done by prepare(), addConstraints(), and
 
14
// finish() which are called by the register allocator.
 
15
//
 
16
// Given a variable that is live across multiple basic blocks, and given
 
17
// constraints on the basic blocks where the variable is live, determine which
 
18
// edge bundles should have the variable in a register and which edge bundles
 
19
// should have the variable in a stack slot.
 
20
//
 
21
// The returned bit vector can be used to place optimal spill code at basic
 
22
// block entries and exits. Spill code placement inside a basic block is not
 
23
// considered.
 
24
//
 
25
//===----------------------------------------------------------------------===//
 
26
 
 
27
#ifndef LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
 
28
#define LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
 
29
 
 
30
#include "llvm/ADT/ArrayRef.h"
 
31
#include "llvm/ADT/SmallVector.h"
 
32
#include "llvm/CodeGen/MachineFunctionPass.h"
 
33
#include "llvm/Support/BlockFrequency.h"
 
34
 
 
35
namespace llvm {
 
36
 
 
37
class BitVector;
 
38
class EdgeBundles;
 
39
class MachineBasicBlock;
 
40
class MachineLoopInfo;
 
41
class MachineBlockFrequencyInfo;
 
42
 
 
43
class SpillPlacement : public MachineFunctionPass {
 
44
  struct Node;
 
45
  const MachineFunction *MF;
 
46
  const EdgeBundles *bundles;
 
47
  const MachineLoopInfo *loops;
 
48
  const MachineBlockFrequencyInfo *MBFI;
 
49
  Node *nodes;
 
50
 
 
51
  // Nodes that are active in the current computation. Owned by the prepare()
 
52
  // caller.
 
53
  BitVector *ActiveNodes;
 
54
 
 
55
  // Nodes with active links. Populated by scanActiveBundles.
 
56
  SmallVector<unsigned, 8> Linked;
 
57
 
 
58
  // Nodes that went positive during the last call to scanActiveBundles or
 
59
  // iterate.
 
60
  SmallVector<unsigned, 8> RecentPositive;
 
61
 
 
62
  // Block frequencies are computed once. Indexed by block number.
 
63
  SmallVector<BlockFrequency, 8> BlockFrequencies;
 
64
 
 
65
  /// Decision threshold. A node gets the output value 0 if the weighted sum of
 
66
  /// its inputs falls in the open interval (-Threshold;Threshold).
 
67
  BlockFrequency Threshold;
 
68
 
 
69
public:
 
70
  static char ID; // Pass identification, replacement for typeid.
 
71
 
 
72
  SpillPlacement() : MachineFunctionPass(ID), nodes(nullptr) {}
 
73
  ~SpillPlacement() override { releaseMemory(); }
 
74
 
 
75
  /// BorderConstraint - A basic block has separate constraints for entry and
 
76
  /// exit.
 
77
  enum BorderConstraint {
 
78
    DontCare,  ///< Block doesn't care / variable not live.
 
79
    PrefReg,   ///< Block entry/exit prefers a register.
 
80
    PrefSpill, ///< Block entry/exit prefers a stack slot.
 
81
    PrefBoth,  ///< Block entry prefers both register and stack.
 
82
    MustSpill  ///< A register is impossible, variable must be spilled.
 
83
  };
 
84
 
 
85
  /// BlockConstraint - Entry and exit constraints for a basic block.
 
86
  struct BlockConstraint {
 
87
    unsigned Number;            ///< Basic block number (from MBB::getNumber()).
 
88
    BorderConstraint Entry : 8; ///< Constraint on block entry.
 
89
    BorderConstraint Exit : 8;  ///< Constraint on block exit.
 
90
 
 
91
    /// True when this block changes the value of the live range. This means
 
92
    /// the block has a non-PHI def.  When this is false, a live-in value on
 
93
    /// the stack can be live-out on the stack without inserting a spill.
 
94
    bool ChangesValue;
 
95
  };
 
96
 
 
97
  /// prepare - Reset state and prepare for a new spill placement computation.
 
98
  /// @param RegBundles Bit vector to receive the edge bundles where the
 
99
  ///                   variable should be kept in a register. Each bit
 
100
  ///                   corresponds to an edge bundle, a set bit means the
 
101
  ///                   variable should be kept in a register through the
 
102
  ///                   bundle. A clear bit means the variable should be
 
103
  ///                   spilled. This vector is retained.
 
104
  void prepare(BitVector &RegBundles);
 
105
 
 
106
  /// addConstraints - Add constraints and biases. This method may be called
 
107
  /// more than once to accumulate constraints.
 
108
  /// @param LiveBlocks Constraints for blocks that have the variable live in or
 
109
  ///                   live out.
 
110
  void addConstraints(ArrayRef<BlockConstraint> LiveBlocks);
 
111
 
 
112
  /// addPrefSpill - Add PrefSpill constraints to all blocks listed.  This is
 
113
  /// equivalent to calling addConstraint with identical BlockConstraints with
 
114
  /// Entry = Exit = PrefSpill, and ChangesValue = false.
 
115
  ///
 
116
  /// @param Blocks Array of block numbers that prefer to spill in and out.
 
117
  /// @param Strong When true, double the negative bias for these blocks.
 
118
  void addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong);
 
119
 
 
120
  /// addLinks - Add transparent blocks with the given numbers.
 
121
  void addLinks(ArrayRef<unsigned> Links);
 
122
 
 
123
  /// scanActiveBundles - Perform an initial scan of all bundles activated by
 
124
  /// addConstraints and addLinks, updating their state. Add all the bundles
 
125
  /// that now prefer a register to RecentPositive.
 
126
  /// Prepare internal data structures for iterate.
 
127
  /// Return true is there are any positive nodes.
 
128
  bool scanActiveBundles();
 
129
 
 
130
  /// iterate - Update the network iteratively until convergence, or new bundles
 
131
  /// are found.
 
132
  void iterate();
 
133
 
 
134
  /// getRecentPositive - Return an array of bundles that became positive during
 
135
  /// the previous call to scanActiveBundles or iterate.
 
136
  ArrayRef<unsigned> getRecentPositive() { return RecentPositive; }
 
137
 
 
138
  /// finish - Compute the optimal spill code placement given the
 
139
  /// constraints. No MustSpill constraints will be violated, and the smallest
 
140
  /// possible number of PrefX constraints will be violated, weighted by
 
141
  /// expected execution frequencies.
 
142
  /// The selected bundles are returned in the bitvector passed to prepare().
 
143
  /// @return True if a perfect solution was found, allowing the variable to be
 
144
  ///         in a register through all relevant bundles.
 
145
  bool finish();
 
146
 
 
147
  /// getBlockFrequency - Return the estimated block execution frequency per
 
148
  /// function invocation.
 
149
  BlockFrequency getBlockFrequency(unsigned Number) const {
 
150
    return BlockFrequencies[Number];
 
151
  }
 
152
 
 
153
private:
 
154
  bool runOnMachineFunction(MachineFunction&) override;
 
155
  void getAnalysisUsage(AnalysisUsage&) const override;
 
156
  void releaseMemory() override;
 
157
 
 
158
  void activate(unsigned);
 
159
  void setThreshold(const BlockFrequency &Entry);
 
160
};
 
161
 
 
162
} // end namespace llvm
 
163
 
 
164
#endif