contrib/llvm/lib/CodeGen/SafeStackColoring.h

   1 //===-- SafeStackColoring.h - SafeStack frame coloring ---------*- 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 #ifndef LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
  11 #define LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
  12
  13 #include "llvm/ADT/BitVector.h"
  14 #include "llvm/ADT/DenseMap.h"
  15 #include "llvm/ADT/SmallVector.h"
  16 #include "llvm/IR/Function.h"
  17 #include "llvm/Support/raw_os_ostream.h"
  18
  19 namespace llvm {
  20 class AllocaInst;
  21
  22 namespace safestack {
  23 /// Compute live ranges of allocas.
  24 /// Live ranges are represented as sets of "interesting" instructions, which are
  25 /// defined as instructions that may start or end an alloca's lifetime. These
  26 /// are:
  27 /// * lifetime.start and lifetime.end intrinsics
  28 /// * first instruction of any basic block
  29 /// Interesting instructions are numbered in the depth-first walk of the CFG,
  30 /// and in the program order inside each basic block.
  31 class StackColoring {
  32   /// A class representing liveness information for a single basic block.
  33   /// Each bit in the BitVector represents the liveness property
  34   /// for a different stack slot.
  35   struct BlockLifetimeInfo {
  36     /// Which slots BEGINs in each basic block.
  37     BitVector Begin;
  38     /// Which slots ENDs in each basic block.
  39     BitVector End;
  40     /// Which slots are marked as LIVE_IN, coming into each basic block.
  41     BitVector LiveIn;
  42     /// Which slots are marked as LIVE_OUT, coming out of each basic block.
  43     BitVector LiveOut;
  44   };
  45
  46 public:
  47   /// This class represents a set of interesting instructions where an alloca is
  48   /// live.
  49   struct LiveRange {
  50     BitVector bv;
  51     void SetMaximum(int size) { bv.resize(size); }
  52     void AddRange(unsigned start, unsigned end) { bv.set(start, end); }
  53     bool Overlaps(const LiveRange &Other) const {
  54       return bv.anyCommon(Other.bv);
  55     }
  56     void Join(const LiveRange &Other) { bv |= Other.bv; }
  57   };
  58
  59 private:
  60   Function &F;
  61
  62   /// Maps active slots (per bit) for each basic block.
  63   typedef DenseMap<BasicBlock *, BlockLifetimeInfo> LivenessMap;
  64   LivenessMap BlockLiveness;
  65
  66   /// Number of interesting instructions.
  67   int NumInst;
  68   /// Numeric ids for interesting instructions.
  69   DenseMap<Instruction *, unsigned> InstructionNumbering;
  70   /// A range [Start, End) of instruction ids for each basic block.
  71   /// Instructions inside each BB have monotonic and consecutive ids.
  72   DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
  73
  74   ArrayRef<AllocaInst *> Allocas;
  75   unsigned NumAllocas;
  76   DenseMap<AllocaInst *, unsigned> AllocaNumbering;
  77   /// LiveRange for allocas.
  78   SmallVector<LiveRange, 8> LiveRanges;
  79
  80   /// The set of allocas that have at least one lifetime.start. All other
  81   /// allocas get LiveRange that corresponds to the entire function.
  82   BitVector InterestingAllocas;
  83   SmallVector<Instruction *, 8> Markers;
  84
  85   struct Marker {
  86     unsigned AllocaNo;
  87     bool IsStart;
  88   };
  89
  90   /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
  91   DenseMap<BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>> BBMarkers;
  92
  93   void dumpAllocas();
  94   void dumpBlockLiveness();
  95   void dumpLiveRanges();
  96
  97   bool readMarker(Instruction *I, bool *IsStart);
  98   void collectMarkers();
  99   void calculateLocalLiveness();
 100   void calculateLiveIntervals();
 101
 102 public:
 103   StackColoring(Function &F, ArrayRef<AllocaInst *> Allocas)
 104       : F(F), NumInst(-1), Allocas(Allocas), NumAllocas(Allocas.size()) {}
 105
 106   void run();
 107   void removeAllMarkers();
 108
 109   /// Returns a set of "interesting" instructions where the given alloca is
 110   /// live. Not all instructions in a function are interesting: we pick a set
 111   /// that is large enough for LiveRange::Overlaps to be correct.
 112   const LiveRange &getLiveRange(AllocaInst *AI);
 113
 114   /// Returns a live range that represents an alloca that is live throughout the
 115   /// entire function.
 116   LiveRange getFullLiveRange() {
 117     assert(NumInst >= 0);
 118     LiveRange R;
 119     R.SetMaximum(NumInst);
 120     R.AddRange(0, NumInst);
 121     return R;
 122   }
 123 };
 124
 125 static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
 126   OS << "{";
 127   int idx = V.find_first();
 128   bool first = true;
 129   while (idx >= 0) {
 130     if (!first) {
 131       OS << ", ";
 132     }
 133     first = false;
 134     OS << idx;
 135     idx = V.find_next(idx);
 136   }
 137   OS << "}";
 138   return OS;
 139 }
 140
 141 static inline raw_ostream &operator<<(raw_ostream &OS,
 142                                       const StackColoring::LiveRange &R) {
 143   return OS << R.bv;
 144 }
 145
 146 } // namespace safestack
 147 } // namespace llvm
 148
 149 #endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H