Home | History | Annotate | Download | only in CodeGen 
      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
    150