LCOV - code coverage report
Current view: top level - lib/CodeGen - SafeStackLayout.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 45 59 76.3 %
Date: 2018-07-13 00:08:38 Functions: 5 6 83.3 %
Legend: Lines: hit not hit

          Line data    Source code
       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       99743 : static cl::opt<bool> ClLayout("safe-stack-layout",
      27       99743 :                               cl::desc("enable safe stack layout"), cl::Hidden,
      28      299229 :                               cl::init(true));
      29             : 
      30           0 : LLVM_DUMP_METHOD void StackLayout::print(raw_ostream &OS) {
      31           0 :   OS << "Stack regions:\n";
      32           0 :   for (unsigned i = 0; i < Regions.size(); ++i) {
      33           0 :     OS << "  " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
      34           0 :        << "), range " << Regions[i].Range << "\n";
      35             :   }
      36           0 :   OS << "Stack objects:\n";
      37           0 :   for (auto &IT : ObjectOffsets) {
      38           0 :     OS << "  at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
      39             :   }
      40           0 : }
      41             : 
      42         248 : void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
      43             :                             const StackColoring::LiveRange &Range) {
      44         744 :   StackObjects.push_back({V, Size, Alignment, Range});
      45         496 :   ObjectAlignments[V] = Alignment;
      46         496 :   MaxAlignment = std::max(MaxAlignment, Alignment);
      47         248 : }
      48             : 
      49             : static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
      50             :                                   unsigned Alignment) {
      51         912 :   return alignTo(Offset + Size, Alignment) - Size;
      52             : }
      53             : 
      54         248 : void StackLayout::layoutObject(StackObject &Obj) {
      55         248 :   if (!ClLayout) {
      56             :     // If layout is disabled, just grab the next aligned address.
      57             :     // This effectively disables stack coloring as well.
      58           0 :     unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
      59           0 :     unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment);
      60           0 :     unsigned End = Start + Obj.Size;
      61           0 :     Regions.emplace_back(Start, End, Obj.Range);
      62           0 :     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         496 :   unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment);
      70         248 :   unsigned End = Start + Obj.Size;
      71             :   LLVM_DEBUG(dbgs() << "  First candidate: " << Start << " .. " << End << "\n");
      72         936 :   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         385 :     if (Start >= R.End) {
      77             :       LLVM_DEBUG(dbgs() << "  Does not intersect, skip.\n");
      78         134 :       continue;
      79             :     }
      80         459 :     if (Obj.Range.Overlaps(R.Range)) {
      81             :       // Find the next appropriate location.
      82         208 :       Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment);
      83         208 :       End = Start + Obj.Size;
      84             :       LLVM_DEBUG(dbgs() << "  Overlaps. Next candidate: " << Start << " .. "
      85             :                         << End << "\n");
      86         208 :       continue;
      87             :     }
      88          43 :     if (End <= R.End) {
      89             :       LLVM_DEBUG(dbgs() << "  Reusing region(s).\n");
      90             :       break;
      91             :     }
      92             :   }
      93             : 
      94         248 :   unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
      95         248 :   if (End > LastRegionEnd) {
      96             :     // Insert a new region at the end. Maybe two.
      97         207 :     if (Start > LastRegionEnd) {
      98             :       LLVM_DEBUG(dbgs() << "  Creating gap region: " << LastRegionEnd << " .. "
      99             :                         << Start << "\n");
     100         114 :       Regions.emplace_back(LastRegionEnd, Start, StackColoring::LiveRange());
     101          38 :       LastRegionEnd = Start;
     102             :     }
     103             :     LLVM_DEBUG(dbgs() << "  Creating new region: " << LastRegionEnd << " .. "
     104             :                       << End << ", range " << Obj.Range << "\n");
     105         207 :     Regions.emplace_back(LastRegionEnd, End, Obj.Range);
     106         207 :     LastRegionEnd = End;
     107             :   }
     108             : 
     109             :   // Split starting and ending regions if necessary.
     110        2398 :   for (unsigned i = 0; i < Regions.size(); ++i) {
     111             :     StackRegion &R = Regions[i];
     112         645 :     if (Start > R.Start && Start < R.End) {
     113             :       StackRegion R0 = R;
     114           9 :       R.Start = R0.End = Start;
     115           9 :       Regions.insert(&R, R0);
     116             :       continue;
     117             :     }
     118         636 :     if (End > R.Start && End < R.End) {
     119             :       StackRegion R0 = R;
     120          11 :       R0.End = R.Start = End;
     121          11 :       Regions.insert(&R, R0);
     122             :       break;
     123             :     }
     124             :   }
     125             : 
     126             :   // Update live ranges for all affected regions.
     127        1030 :   for (StackRegion &R : Regions) {
     128         639 :     if (Start < R.End && End > R.Start)
     129             :       R.Range.Join(Obj.Range);
     130         639 :     if (End <= R.End)
     131             :       break;
     132             :   }
     133             : 
     134         496 :   ObjectOffsets[Obj.Handle] = End;
     135             : }
     136             : 
     137         148 : 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         148 :   if (StackObjects.size() > 2)
     145          15 :     std::stable_sort(StackObjects.begin() + 1, StackObjects.end(),
     146             :                      [](const StackObject &a, const StackObject &b) {
     147             :                        return a.Size > b.Size;
     148             :                      });
     149             : 
     150         644 :   for (auto &Obj : StackObjects)
     151         248 :     layoutObject(Obj);
     152             : 
     153             :   LLVM_DEBUG(print(dbgs()));
     154      299377 : }

Generated by: LCOV version 1.13