contrib/llvm/lib/CodeGen/SafeStackLayout.cpp

   1 //===-- SafeStackLayout.cpp - SafeStack frame layout -----------*- 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 #include "SafeStackLayout.h"
  11
  12 #include "llvm/IR/Instructions.h"
  13 #include "llvm/Support/Debug.h"
  14
  15 using namespace llvm;
  16 using namespace llvm::safestack;
  17
  18 #define DEBUG_TYPE "safestacklayout"
  19
  20 static cl::opt<bool> ClLayout("safe-stack-layout",
  21                               cl::desc("enable safe stack layout"), cl::Hidden,
  22                               cl::init(true));
  23
  24 LLVM_DUMP_METHOD void StackLayout::print(raw_ostream &OS) {
  25   OS << "Stack regions:\n";
  26   for (unsigned i = 0; i < Regions.size(); ++i) {
  27     OS << "  " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
  28        << "), range " << Regions[i].Range << "\n";
  29   }
  30   OS << "Stack objects:\n";
  31   for (auto &IT : ObjectOffsets) {
  32     OS << "  at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
  33   }
  34 }
  35
  36 void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
  37                             const StackColoring::LiveRange &Range) {
  38   StackObjects.push_back({V, Size, Alignment, Range});
  39   MaxAlignment = std::max(MaxAlignment, Alignment);
  40 }
  41
  42 static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
  43                                   unsigned Alignment) {
  44   return alignTo(Offset + Size, Alignment) - Size;
  45 }
  46
  47 void StackLayout::layoutObject(StackObject &Obj) {
  48   if (!ClLayout) {
  49     // If layout is disabled, just grab the next aligned address.
  50     // This effectively disables stack coloring as well.
  51     unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
  52     unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment);
  53     unsigned End = Start + Obj.Size;
  54     Regions.emplace_back(Start, End, Obj.Range);
  55     ObjectOffsets[Obj.Handle] = End;
  56     return;
  57   }
  58
  59   DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align " << Obj.Alignment
  60                << ", range " << Obj.Range << "\n");
  61   assert(Obj.Alignment <= MaxAlignment);
  62   unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment);
  63   unsigned End = Start + Obj.Size;
  64   DEBUG(dbgs() << "  First candidate: " << Start << " .. " << End << "\n");
  65   for (const StackRegion &R : Regions) {
  66     DEBUG(dbgs() << "  Examining region: " << R.Start << " .. " << R.End
  67                  << ", range " << R.Range << "\n");
  68     assert(End >= R.Start);
  69     if (Start >= R.End) {
  70       DEBUG(dbgs() << "  Does not intersect, skip.\n");
  71       continue;
  72     }
  73     if (Obj.Range.Overlaps(R.Range)) {
  74       // Find the next appropriate location.
  75       Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment);
  76       End = Start + Obj.Size;
  77       DEBUG(dbgs() << "  Overlaps. Next candidate: " << Start << " .. " << End
  78                    << "\n");
  79       continue;
  80     }
  81     if (End <= R.End) {
  82       DEBUG(dbgs() << "  Reusing region(s).\n");
  83       break;
  84     }
  85   }
  86
  87   unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
  88   if (End > LastRegionEnd) {
  89     // Insert a new region at the end. Maybe two.
  90     if (Start > LastRegionEnd) {
  91       DEBUG(dbgs() << "  Creating gap region: " << LastRegionEnd << " .. "
  92                    << Start << "\n");
  93       Regions.emplace_back(LastRegionEnd, Start, StackColoring::LiveRange());
  94       LastRegionEnd = Start;
  95     }
  96     DEBUG(dbgs() << "  Creating new region: " << LastRegionEnd << " .. " << End
  97                  << ", range " << Obj.Range << "\n");
  98     Regions.emplace_back(LastRegionEnd, End, Obj.Range);
  99     LastRegionEnd = End;
 100   }
 101
 102   // Split starting and ending regions if necessary.
 103   for (unsigned i = 0; i < Regions.size(); ++i) {
 104     StackRegion &R = Regions[i];
 105     if (Start > R.Start && Start < R.End) {
 106       StackRegion R0 = R;
 107       R.Start = R0.End = Start;
 108       Regions.insert(&R, R0);
 109       continue;
 110     }
 111     if (End > R.Start && End < R.End) {
 112       StackRegion R0 = R;
 113       R0.End = R.Start = End;
 114       Regions.insert(&R, R0);
 115       break;
 116     }
 117   }
 118
 119   // Update live ranges for all affected regions.
 120   for (StackRegion &R : Regions) {
 121     if (Start < R.End && End > R.Start)
 122       R.Range.Join(Obj.Range);
 123     if (End <= R.End)
 124       break;
 125   }
 126
 127   ObjectOffsets[Obj.Handle] = End;
 128 }
 129
 130 void StackLayout::computeLayout() {
 131   // Simple greedy algorithm.
 132   // If this is replaced with something smarter, it must preserve the property
 133   // that the first object is always at the offset 0 in the stack frame (for
 134   // StackProtectorSlot), or handle stack protector in some other way.
 135
 136   // Sort objects by size (largest first) to reduce fragmentation.
 137   if (StackObjects.size() > 2)
 138     std::stable_sort(StackObjects.begin() + 1, StackObjects.end(),
 139                      [](const StackObject &a, const StackObject &b) {
 140                        return a.Size > b.Size;
 141                      });
 142
 143   for (auto &Obj : StackObjects)
 144     layoutObject(Obj);
 145
 146   DEBUG(print(dbgs()));
 147 }