LCOV - code coverage report
Current view: top level - lib/CodeGen - SafeStackColoring.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 118 119 99.2 %
Date: 2018-02-19 03:08:00 Functions: 10 10 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- SafeStackColoring.cpp - SafeStack frame coloring -------------------===//
       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 "SafeStackColoring.h"
      11             : #include "llvm/ADT/BitVector.h"
      12             : #include "llvm/ADT/DenseMap.h"
      13             : #include "llvm/ADT/DepthFirstIterator.h"
      14             : #include "llvm/ADT/SmallVector.h"
      15             : #include "llvm/IR/BasicBlock.h"
      16             : #include "llvm/IR/CFG.h"
      17             : #include "llvm/IR/Instruction.h"
      18             : #include "llvm/IR/Instructions.h"
      19             : #include "llvm/IR/IntrinsicInst.h"
      20             : #include "llvm/IR/Intrinsics.h"
      21             : #include "llvm/IR/User.h"
      22             : #include "llvm/Support/Casting.h"
      23             : #include "llvm/Support/CommandLine.h"
      24             : #include "llvm/Support/Compiler.h"
      25             : #include "llvm/Support/Debug.h"
      26             : #include "llvm/Support/raw_ostream.h"
      27             : #include <cassert>
      28             : #include <tuple>
      29             : #include <utility>
      30             : 
      31             : using namespace llvm;
      32             : using namespace llvm::safestack;
      33             : 
      34             : #define DEBUG_TYPE "safestackcoloring"
      35             : 
      36             : // Disabled by default due to PR32143.
      37       97324 : static cl::opt<bool> ClColoring("safe-stack-coloring",
      38       97324 :                                 cl::desc("enable safe stack coloring"),
      39      291972 :                                 cl::Hidden, cl::init(false));
      40             : 
      41         228 : const StackColoring::LiveRange &StackColoring::getLiveRange(AllocaInst *AI) {
      42         228 :   const auto IT = AllocaNumbering.find(AI);
      43             :   assert(IT != AllocaNumbering.end());
      44         456 :   return LiveRanges[IT->second];
      45             : }
      46             : 
      47         444 : bool StackColoring::readMarker(Instruction *I, bool *IsStart) {
      48             :   auto *II = dyn_cast<IntrinsicInst>(I);
      49         180 :   if (!II || (II->getIntrinsicID() != Intrinsic::lifetime_start &&
      50             :               II->getIntrinsicID() != Intrinsic::lifetime_end))
      51             :     return false;
      52             : 
      53         180 :   *IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start;
      54         180 :   return true;
      55             : }
      56             : 
      57         148 : void StackColoring::removeAllMarkers() {
      58         508 :   for (auto *I : Markers) {
      59         180 :     auto *Op = dyn_cast<Instruction>(I->getOperand(1));
      60         180 :     I->eraseFromParent();
      61             :     // Remove the operand bitcast, too, if it has no more uses left.
      62         180 :     if (Op && Op->use_empty())
      63          78 :       Op->eraseFromParent();
      64             :   }
      65         148 : }
      66             : 
      67         148 : void StackColoring::collectMarkers() {
      68         148 :   InterestingAllocas.resize(NumAllocas);
      69             :   DenseMap<BasicBlock *, SmallDenseMap<Instruction *, Marker>> BBMarkerSet;
      70             : 
      71             :   // Compute the set of start/end markers per basic block.
      72         604 :   for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
      73         456 :     AllocaInst *AI = Allocas[AllocaNo];
      74             :     SmallVector<Instruction *, 8> WorkList;
      75         228 :     WorkList.push_back(AI);
      76         552 :     while (!WorkList.empty()) {
      77             :       Instruction *I = WorkList.pop_back_val();
      78         864 :       for (User *U : I->users()) {
      79          96 :         if (auto *BI = dyn_cast<BitCastInst>(U)) {
      80          96 :           WorkList.push_back(BI);
      81         456 :           continue;
      82             :         }
      83         444 :         auto *UI = dyn_cast<Instruction>(U);
      84         444 :         if (!UI)
      85           0 :           continue;
      86             :         bool IsStart;
      87         444 :         if (!readMarker(UI, &IsStart))
      88         264 :           continue;
      89         180 :         if (IsStart)
      90             :           InterestingAllocas.set(AllocaNo);
      91         360 :         BBMarkerSet[UI->getParent()][UI] = {AllocaNo, IsStart};
      92         180 :         Markers.push_back(UI);
      93             :       }
      94             :     }
      95             :   }
      96             : 
      97             :   // Compute instruction numbering. Only the following instructions are
      98             :   // considered:
      99             :   // * Basic block entries
     100             :   // * Lifetime markers
     101             :   // For each basic block, compute
     102             :   // * the list of markers in the instruction order
     103             :   // * the sets of allocas whose lifetime starts or ends in this BB
     104             :   DEBUG(dbgs() << "Instructions:\n");
     105         148 :   unsigned InstNo = 0;
     106         948 :   for (BasicBlock *BB : depth_first(&F)) {
     107             :     DEBUG(dbgs() << "  " << InstNo << ": BB " << BB->getName() << "\n");
     108         252 :     unsigned BBStart = InstNo++;
     109             : 
     110         252 :     BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
     111         252 :     BlockInfo.Begin.resize(NumAllocas);
     112         252 :     BlockInfo.End.resize(NumAllocas);
     113         252 :     BlockInfo.LiveIn.resize(NumAllocas);
     114         252 :     BlockInfo.LiveOut.resize(NumAllocas);
     115             : 
     116             :     auto &BlockMarkerSet = BBMarkerSet[BB];
     117         252 :     if (BlockMarkerSet.empty()) {
     118         182 :       unsigned BBEnd = InstNo;
     119         364 :       BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
     120         182 :       continue;
     121             :     }
     122             : 
     123         180 :     auto ProcessMarker = [&](Instruction *I, const Marker &M) {
     124             :       DEBUG(dbgs() << "  " << InstNo << ":  "
     125             :                    << (M.IsStart ? "start " : "end   ") << M.AllocaNo << ", "
     126             :                    << *I << "\n");
     127             : 
     128         720 :       BBMarkers[BB].push_back({InstNo, M});
     129             : 
     130         540 :       InstructionNumbering[I] = InstNo++;
     131             : 
     132         180 :       if (M.IsStart) {
     133         275 :         if (BlockInfo.End.test(M.AllocaNo))
     134             :           BlockInfo.End.reset(M.AllocaNo);
     135             :         BlockInfo.Begin.set(M.AllocaNo);
     136             :       } else {
     137         170 :         if (BlockInfo.Begin.test(M.AllocaNo))
     138             :           BlockInfo.Begin.reset(M.AllocaNo);
     139             :         BlockInfo.End.set(M.AllocaNo);
     140             :       }
     141         250 :     };
     142             : 
     143          70 :     if (BlockMarkerSet.size() == 1) {
     144          26 :       ProcessMarker(BlockMarkerSet.begin()->getFirst(),
     145          52 :                     BlockMarkerSet.begin()->getSecond());
     146             :     } else {
     147             :       // Scan the BB to determine the marker order.
     148         547 :       for (Instruction &I : *BB) {
     149         459 :         auto It = BlockMarkerSet.find(&I);
     150         459 :         if (It == BlockMarkerSet.end())
     151         305 :           continue;
     152         154 :         ProcessMarker(&I, It->getSecond());
     153             :       }
     154             :     }
     155             : 
     156          70 :     unsigned BBEnd = InstNo;
     157         140 :     BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
     158             :   }
     159         148 :   NumInst = InstNo;
     160         148 : }
     161             : 
     162          36 : void StackColoring::calculateLocalLiveness() {
     163             :   bool changed = true;
     164         140 :   while (changed) {
     165             :     changed = false;
     166             : 
     167         428 :     for (BasicBlock *BB : depth_first(&F)) {
     168         136 :       BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
     169             : 
     170             :       // Compute LiveIn by unioning together the LiveOut sets of all preds.
     171             :       BitVector LocalLiveIn;
     172         512 :       for (auto *PredBB : predecessors(BB)) {
     173         208 :         LivenessMap::const_iterator I = BlockLiveness.find(PredBB);
     174             :         assert(I != BlockLiveness.end() && "Predecessor not found");
     175         104 :         LocalLiveIn |= I->second.LiveOut;
     176             :       }
     177             : 
     178             :       // Compute LiveOut by subtracting out lifetimes that end in this
     179             :       // block, then adding in lifetimes that begin in this block.  If
     180             :       // we have both BEGIN and END markers in the same basic block
     181             :       // then we know that the BEGIN marker comes after the END,
     182             :       // because we already handle the case where the BEGIN comes
     183             :       // before the END when collecting the markers (and building the
     184             :       // BEGIN/END vectors).
     185         136 :       BitVector LocalLiveOut = LocalLiveIn;
     186         136 :       LocalLiveOut.reset(BlockInfo.End);
     187         136 :       LocalLiveOut |= BlockInfo.Begin;
     188             : 
     189             :       // Update block LiveIn set, noting whether it has changed.
     190         136 :       if (LocalLiveIn.test(BlockInfo.LiveIn)) {
     191             :         changed = true;
     192          30 :         BlockInfo.LiveIn |= LocalLiveIn;
     193             :       }
     194             : 
     195             :       // Update block LiveOut set, noting whether it has changed.
     196         136 :       if (LocalLiveOut.test(BlockInfo.LiveOut)) {
     197             :         changed = true;
     198          38 :         BlockInfo.LiveOut |= LocalLiveOut;
     199             :       }
     200             :     }
     201             :   } // while changed.
     202          36 : }
     203             : 
     204          36 : void StackColoring::calculateLiveIntervals() {
     205         154 :   for (auto IT : BlockLiveness) {
     206          82 :     BasicBlock *BB = IT.getFirst();
     207             :     BlockLifetimeInfo &BlockInfo = IT.getSecond();
     208             :     unsigned BBStart, BBEnd;
     209         164 :     std::tie(BBStart, BBEnd) = BlockInstRange[BB];
     210             : 
     211             :     BitVector Started, Ended;
     212          82 :     Started.resize(NumAllocas);
     213          82 :     Ended.resize(NumAllocas);
     214             :     SmallVector<unsigned, 8> Start;
     215          82 :     Start.resize(NumAllocas);
     216             : 
     217             :     // LiveIn ranges start at the first instruction.
     218         668 :     for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
     219         293 :       if (BlockInfo.LiveIn.test(AllocaNo)) {
     220             :         Started.set(AllocaNo);
     221         120 :         Start[AllocaNo] = BBStart;
     222             :       }
     223             :     }
     224             : 
     225         524 :     for (auto &It : BBMarkers[BB]) {
     226         180 :       unsigned InstNo = It.first;
     227         180 :       bool IsStart = It.second.IsStart;
     228         180 :       unsigned AllocaNo = It.second.AllocaNo;
     229             : 
     230         180 :       if (IsStart) {
     231             :         assert(!Started.test(AllocaNo) || Start[AllocaNo] == BBStart);
     232          95 :         if (!Started.test(AllocaNo)) {
     233             :           Started.set(AllocaNo);
     234             :           Ended.reset(AllocaNo);
     235         186 :           Start[AllocaNo] = InstNo;
     236             :         }
     237             :       } else {
     238             :         assert(!Ended.test(AllocaNo));
     239          85 :         if (Started.test(AllocaNo)) {
     240         166 :           LiveRanges[AllocaNo].AddRange(Start[AllocaNo], InstNo);
     241             :           Started.reset(AllocaNo);
     242             :         }
     243             :         Ended.set(AllocaNo);
     244             :       }
     245             :     }
     246             : 
     247         668 :     for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
     248         293 :       if (Started.test(AllocaNo))
     249         140 :         LiveRanges[AllocaNo].AddRange(Start[AllocaNo], BBEnd);
     250             :   }
     251          36 : }
     252             : 
     253             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     254             : LLVM_DUMP_METHOD void StackColoring::dumpAllocas() {
     255             :   dbgs() << "Allocas:\n";
     256             :   for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
     257             :     dbgs() << "  " << AllocaNo << ": " << *Allocas[AllocaNo] << "\n";
     258             : }
     259             : 
     260             : LLVM_DUMP_METHOD void StackColoring::dumpBlockLiveness() {
     261             :   dbgs() << "Block liveness:\n";
     262             :   for (auto IT : BlockLiveness) {
     263             :     BasicBlock *BB = IT.getFirst();
     264             :     BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
     265             :     auto BlockRange = BlockInstRange[BB];
     266             :     dbgs() << "  BB [" << BlockRange.first << ", " << BlockRange.second
     267             :            << "): begin " << BlockInfo.Begin << ", end " << BlockInfo.End
     268             :            << ", livein " << BlockInfo.LiveIn << ", liveout "
     269             :            << BlockInfo.LiveOut << "\n";
     270             :   }
     271             : }
     272             : 
     273             : LLVM_DUMP_METHOD void StackColoring::dumpLiveRanges() {
     274             :   dbgs() << "Alloca liveness:\n";
     275             :   for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
     276             :     LiveRange &Range = LiveRanges[AllocaNo];
     277             :     dbgs() << "  " << AllocaNo << ": " << Range << "\n";
     278             :   }
     279             : }
     280             : #endif
     281             : 
     282         148 : void StackColoring::run() {
     283             :   DEBUG(dumpAllocas());
     284             : 
     285         604 :   for (unsigned I = 0; I < NumAllocas; ++I)
     286         684 :     AllocaNumbering[Allocas[I]] = I;
     287         148 :   LiveRanges.resize(NumAllocas);
     288             : 
     289         148 :   collectMarkers();
     290             : 
     291         148 :   if (!ClColoring) {
     292         378 :     for (auto &R : LiveRanges) {
     293             :       R.SetMaximum(1);
     294             :       R.AddRange(0, 1);
     295             :     }
     296             :     return;
     297             :   }
     298             : 
     299         226 :   for (auto &R : LiveRanges)
     300          95 :     R.SetMaximum(NumInst);
     301         226 :   for (unsigned I = 0; I < NumAllocas; ++I)
     302          95 :     if (!InterestingAllocas.test(I))
     303           8 :       LiveRanges[I] = getFullLiveRange();
     304             : 
     305          36 :   calculateLocalLiveness();
     306             :   DEBUG(dumpBlockLiveness());
     307          36 :   calculateLiveIntervals();
     308             :   DEBUG(dumpLiveRanges());
     309      291972 : }

Generated by: LCOV version 1.13