Home | History | Annotate | Download | only in CodeGen 
      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   for (auto &Obj : StackObjects)
    136     layoutObject(Obj);
    137 
    138   DEBUG(print(dbgs()));
    139 }
    140