lib/CodeGen/SafeStackLayout.cpp

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