1303231Sdim//===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- C++ -*-===// 2303231Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6303231Sdim// 7303231Sdim//===----------------------------------------------------------------------===// 8303231Sdim// 9303231Sdim// This file defines parts of the whole-program devirtualization pass 10303231Sdim// implementation that may be usefully unit tested. 11303231Sdim// 12303231Sdim//===----------------------------------------------------------------------===// 13303231Sdim 14303231Sdim#ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H 15303231Sdim#define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H 16303231Sdim 17303231Sdim#include "llvm/IR/Module.h" 18303231Sdim#include "llvm/IR/PassManager.h" 19360784Sdim#include "llvm/Transforms/IPO/FunctionImport.h" 20303231Sdim#include <cassert> 21303231Sdim#include <cstdint> 22360784Sdim#include <set> 23303231Sdim#include <utility> 24303231Sdim#include <vector> 25303231Sdim 26303231Sdimnamespace llvm { 27303231Sdim 28303231Sdimtemplate <typename T> class ArrayRef; 29303231Sdimtemplate <typename T> class MutableArrayRef; 30303231Sdimclass Function; 31303231Sdimclass GlobalVariable; 32341825Sdimclass ModuleSummaryIndex; 33360784Sdimstruct ValueInfo; 34303231Sdim 35303231Sdimnamespace wholeprogramdevirt { 36303231Sdim 37303231Sdim// A bit vector that keeps track of which bits are used. We use this to 38303231Sdim// pack constant values compactly before and after each virtual table. 39303231Sdimstruct AccumBitVector { 40303231Sdim std::vector<uint8_t> Bytes; 41303231Sdim 42303231Sdim // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not. 43303231Sdim std::vector<uint8_t> BytesUsed; 44303231Sdim 45303231Sdim std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) { 46303231Sdim if (Bytes.size() < Pos + Size) { 47303231Sdim Bytes.resize(Pos + Size); 48303231Sdim BytesUsed.resize(Pos + Size); 49303231Sdim } 50303231Sdim return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos); 51303231Sdim } 52303231Sdim 53303231Sdim // Set little-endian value Val with size Size at bit position Pos, 54303231Sdim // and mark bytes as used. 55303231Sdim void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) { 56303231Sdim assert(Pos % 8 == 0); 57303231Sdim auto DataUsed = getPtrToData(Pos / 8, Size); 58303231Sdim for (unsigned I = 0; I != Size; ++I) { 59303231Sdim DataUsed.first[I] = Val >> (I * 8); 60303231Sdim assert(!DataUsed.second[I]); 61303231Sdim DataUsed.second[I] = 0xff; 62303231Sdim } 63303231Sdim } 64303231Sdim 65303231Sdim // Set big-endian value Val with size Size at bit position Pos, 66303231Sdim // and mark bytes as used. 67303231Sdim void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) { 68303231Sdim assert(Pos % 8 == 0); 69303231Sdim auto DataUsed = getPtrToData(Pos / 8, Size); 70303231Sdim for (unsigned I = 0; I != Size; ++I) { 71303231Sdim DataUsed.first[Size - I - 1] = Val >> (I * 8); 72303231Sdim assert(!DataUsed.second[Size - I - 1]); 73303231Sdim DataUsed.second[Size - I - 1] = 0xff; 74303231Sdim } 75303231Sdim } 76303231Sdim 77303231Sdim // Set bit at bit position Pos to b and mark bit as used. 78303231Sdim void setBit(uint64_t Pos, bool b) { 79303231Sdim auto DataUsed = getPtrToData(Pos / 8, 1); 80303231Sdim if (b) 81303231Sdim *DataUsed.first |= 1 << (Pos % 8); 82303231Sdim assert(!(*DataUsed.second & (1 << Pos % 8))); 83303231Sdim *DataUsed.second |= 1 << (Pos % 8); 84303231Sdim } 85303231Sdim}; 86303231Sdim 87303231Sdim// The bits that will be stored before and after a particular vtable. 88303231Sdimstruct VTableBits { 89303231Sdim // The vtable global. 90303231Sdim GlobalVariable *GV; 91303231Sdim 92303231Sdim // Cache of the vtable's size in bytes. 93303231Sdim uint64_t ObjectSize = 0; 94303231Sdim 95303231Sdim // The bit vector that will be laid out before the vtable. Note that these 96303231Sdim // bytes are stored in reverse order until the globals are rebuilt. This means 97303231Sdim // that any values in the array must be stored using the opposite endianness 98303231Sdim // from the target. 99303231Sdim AccumBitVector Before; 100303231Sdim 101303231Sdim // The bit vector that will be laid out after the vtable. 102303231Sdim AccumBitVector After; 103303231Sdim}; 104303231Sdim 105303231Sdim// Information about a member of a particular type identifier. 106303231Sdimstruct TypeMemberInfo { 107303231Sdim // The VTableBits for the vtable. 108303231Sdim VTableBits *Bits; 109303231Sdim 110303231Sdim // The offset in bytes from the start of the vtable (i.e. the address point). 111303231Sdim uint64_t Offset; 112303231Sdim 113303231Sdim bool operator<(const TypeMemberInfo &other) const { 114303231Sdim return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset); 115303231Sdim } 116303231Sdim}; 117303231Sdim 118303231Sdim// A virtual call target, i.e. an entry in a particular vtable. 119303231Sdimstruct VirtualCallTarget { 120303231Sdim VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM); 121303231Sdim 122303231Sdim // For testing only. 123303231Sdim VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian) 124314564Sdim : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian), WasDevirt(false) {} 125303231Sdim 126303231Sdim // The function stored in the vtable. 127303231Sdim Function *Fn; 128303231Sdim 129303231Sdim // A pointer to the type identifier member through which the pointer to Fn is 130303231Sdim // accessed. 131303231Sdim const TypeMemberInfo *TM; 132303231Sdim 133303231Sdim // When doing virtual constant propagation, this stores the return value for 134303231Sdim // the function when passed the currently considered argument list. 135303231Sdim uint64_t RetVal; 136303231Sdim 137303231Sdim // Whether the target is big endian. 138303231Sdim bool IsBigEndian; 139303231Sdim 140314564Sdim // Whether at least one call site to the target was devirtualized. 141314564Sdim bool WasDevirt; 142314564Sdim 143303231Sdim // The minimum byte offset before the address point. This covers the bytes in 144303231Sdim // the vtable object before the address point (e.g. RTTI, access-to-top, 145303231Sdim // vtables for other base classes) and is equal to the offset from the start 146303231Sdim // of the vtable object to the address point. 147303231Sdim uint64_t minBeforeBytes() const { return TM->Offset; } 148303231Sdim 149303231Sdim // The minimum byte offset after the address point. This covers the bytes in 150303231Sdim // the vtable object after the address point (e.g. the vtable for the current 151303231Sdim // class and any later base classes) and is equal to the size of the vtable 152303231Sdim // object minus the offset from the start of the vtable object to the address 153303231Sdim // point. 154303231Sdim uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; } 155303231Sdim 156303231Sdim // The number of bytes allocated (for the vtable plus the byte array) before 157303231Sdim // the address point. 158303231Sdim uint64_t allocatedBeforeBytes() const { 159303231Sdim return minBeforeBytes() + TM->Bits->Before.Bytes.size(); 160303231Sdim } 161303231Sdim 162303231Sdim // The number of bytes allocated (for the vtable plus the byte array) after 163303231Sdim // the address point. 164303231Sdim uint64_t allocatedAfterBytes() const { 165303231Sdim return minAfterBytes() + TM->Bits->After.Bytes.size(); 166303231Sdim } 167303231Sdim 168303231Sdim // Set the bit at position Pos before the address point to RetVal. 169303231Sdim void setBeforeBit(uint64_t Pos) { 170303231Sdim assert(Pos >= 8 * minBeforeBytes()); 171303231Sdim TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal); 172303231Sdim } 173303231Sdim 174303231Sdim // Set the bit at position Pos after the address point to RetVal. 175303231Sdim void setAfterBit(uint64_t Pos) { 176303231Sdim assert(Pos >= 8 * minAfterBytes()); 177303231Sdim TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal); 178303231Sdim } 179303231Sdim 180303231Sdim // Set the bytes at position Pos before the address point to RetVal. 181303231Sdim // Because the bytes in Before are stored in reverse order, we use the 182303231Sdim // opposite endianness to the target. 183303231Sdim void setBeforeBytes(uint64_t Pos, uint8_t Size) { 184303231Sdim assert(Pos >= 8 * minBeforeBytes()); 185303231Sdim if (IsBigEndian) 186303231Sdim TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size); 187303231Sdim else 188303231Sdim TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size); 189303231Sdim } 190303231Sdim 191303231Sdim // Set the bytes at position Pos after the address point to RetVal. 192303231Sdim void setAfterBytes(uint64_t Pos, uint8_t Size) { 193303231Sdim assert(Pos >= 8 * minAfterBytes()); 194303231Sdim if (IsBigEndian) 195303231Sdim TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size); 196303231Sdim else 197303231Sdim TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size); 198303231Sdim } 199303231Sdim}; 200303231Sdim 201303231Sdim// Find the minimum offset that we may store a value of size Size bits at. If 202303231Sdim// IsAfter is set, look for an offset before the object, otherwise look for an 203303231Sdim// offset after the object. 204303231Sdimuint64_t findLowestOffset(ArrayRef<VirtualCallTarget> Targets, bool IsAfter, 205303231Sdim uint64_t Size); 206303231Sdim 207303231Sdim// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the 208303231Sdim// given allocation offset before the vtable address. Stores the computed 209303231Sdim// byte/bit offset to OffsetByte/OffsetBit. 210303231Sdimvoid setBeforeReturnValues(MutableArrayRef<VirtualCallTarget> Targets, 211303231Sdim uint64_t AllocBefore, unsigned BitWidth, 212303231Sdim int64_t &OffsetByte, uint64_t &OffsetBit); 213303231Sdim 214303231Sdim// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the 215303231Sdim// given allocation offset after the vtable address. Stores the computed 216303231Sdim// byte/bit offset to OffsetByte/OffsetBit. 217303231Sdimvoid setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets, 218303231Sdim uint64_t AllocAfter, unsigned BitWidth, 219303231Sdim int64_t &OffsetByte, uint64_t &OffsetBit); 220303231Sdim 221303231Sdim} // end namespace wholeprogramdevirt 222303231Sdim 223303231Sdimstruct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> { 224341825Sdim ModuleSummaryIndex *ExportSummary; 225341825Sdim const ModuleSummaryIndex *ImportSummary; 226341825Sdim WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, 227341825Sdim const ModuleSummaryIndex *ImportSummary) 228341825Sdim : ExportSummary(ExportSummary), ImportSummary(ImportSummary) { 229341825Sdim assert(!(ExportSummary && ImportSummary)); 230341825Sdim } 231303231Sdim PreservedAnalyses run(Module &M, ModuleAnalysisManager &); 232303231Sdim}; 233303231Sdim 234360784Sdimstruct VTableSlotSummary { 235360784Sdim StringRef TypeID; 236360784Sdim uint64_t ByteOffset; 237360784Sdim}; 238360784Sdim 239360784Sdim/// Perform index-based whole program devirtualization on the \p Summary 240360784Sdim/// index. Any devirtualized targets used by a type test in another module 241360784Sdim/// are added to the \p ExportedGUIDs set. For any local devirtualized targets 242360784Sdim/// only used within the defining module, the information necessary for 243360784Sdim/// locating the corresponding WPD resolution is recorded for the ValueInfo 244360784Sdim/// in case it is exported by cross module importing (in which case the 245360784Sdim/// devirtualized target name will need adjustment). 246360784Sdimvoid runWholeProgramDevirtOnIndex( 247360784Sdim ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs, 248360784Sdim std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap); 249360784Sdim 250360784Sdim/// Call after cross-module importing to update the recorded single impl 251360784Sdim/// devirt target names for any locals that were exported. 252360784Sdimvoid updateIndexWPDForExports( 253360784Sdim ModuleSummaryIndex &Summary, 254360784Sdim function_ref<bool(StringRef, ValueInfo)> isExported, 255360784Sdim std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap); 256360784Sdim 257303231Sdim} // end namespace llvm 258303231Sdim 259303231Sdim#endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H 260