LCOV - code coverage report
Current view: top level - lib/CodeGen - SafeStackColoring.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 142 143 99.3 %
Date: 2017-09-14 15:23:50 Functions: 10 10 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13