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

Generated by: LCOV version 1.13