1 //===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines parts of the whole-program devirtualization pass 10 // implementation that may be usefully unit tested. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H 15 #define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H 16 17 #include "llvm/ADT/DenseSet.h" 18 #include "llvm/IR/GlobalValue.h" 19 #include "llvm/IR/PassManager.h" 20 #include "llvm/Support/Compiler.h" 21 #include <cassert> 22 #include <cstdint> 23 #include <map> 24 #include <set> 25 #include <utility> 26 #include <vector> 27 28 namespace llvm { 29 class Module; 30 31 template <typename T> class ArrayRef; 32 template <typename T> class MutableArrayRef; 33 class GlobalVariable; 34 class ModuleSummaryIndex; 35 struct ValueInfo; 36 37 namespace wholeprogramdevirt { 38 39 // A bit vector that keeps track of which bits are used. We use this to 40 // pack constant values compactly before and after each virtual table. 41 struct AccumBitVector { 42 std::vector<uint8_t> Bytes; 43 44 // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not. 45 std::vector<uint8_t> BytesUsed; 46 getPtrToDataAccumBitVector47 std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) { 48 if (Bytes.size() < Pos + Size) { 49 Bytes.resize(Pos + Size); 50 BytesUsed.resize(Pos + Size); 51 } 52 return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos); 53 } 54 55 // Set little-endian value Val with size Size at bit position Pos, 56 // and mark bytes as used. setLEAccumBitVector57 void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) { 58 assert(Pos % 8 == 0); 59 auto DataUsed = getPtrToData(Pos / 8, Size); 60 for (unsigned I = 0; I != Size; ++I) { 61 DataUsed.first[I] = Val >> (I * 8); 62 assert(!DataUsed.second[I]); 63 DataUsed.second[I] = 0xff; 64 } 65 } 66 67 // Set big-endian value Val with size Size at bit position Pos, 68 // and mark bytes as used. setBEAccumBitVector69 void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) { 70 assert(Pos % 8 == 0); 71 auto DataUsed = getPtrToData(Pos / 8, Size); 72 for (unsigned I = 0; I != Size; ++I) { 73 DataUsed.first[Size - I - 1] = Val >> (I * 8); 74 assert(!DataUsed.second[Size - I - 1]); 75 DataUsed.second[Size - I - 1] = 0xff; 76 } 77 } 78 79 // Set bit at bit position Pos to b and mark bit as used. setBitAccumBitVector80 void setBit(uint64_t Pos, bool b) { 81 auto DataUsed = getPtrToData(Pos / 8, 1); 82 if (b) 83 *DataUsed.first |= 1 << (Pos % 8); 84 assert(!(*DataUsed.second & (1 << Pos % 8))); 85 *DataUsed.second |= 1 << (Pos % 8); 86 } 87 }; 88 89 // The bits that will be stored before and after a particular vtable. 90 struct VTableBits { 91 // The vtable global. 92 GlobalVariable *GV; 93 94 // Cache of the vtable's size in bytes. 95 uint64_t ObjectSize = 0; 96 97 // The bit vector that will be laid out before the vtable. Note that these 98 // bytes are stored in reverse order until the globals are rebuilt. This means 99 // that any values in the array must be stored using the opposite endianness 100 // from the target. 101 AccumBitVector Before; 102 103 // The bit vector that will be laid out after the vtable. 104 AccumBitVector After; 105 }; 106 107 // Information about a member of a particular type identifier. 108 struct TypeMemberInfo { 109 // The VTableBits for the vtable. 110 VTableBits *Bits; 111 112 // The offset in bytes from the start of the vtable (i.e. the address point). 113 uint64_t Offset; 114 115 bool operator<(const TypeMemberInfo &other) const { 116 return std::tie(Bits, Offset) < std::tie(other.Bits, other.Offset); 117 } 118 }; 119 120 // A virtual call target, i.e. an entry in a particular vtable. 121 struct VirtualCallTarget { 122 LLVM_ABI VirtualCallTarget(GlobalValue *Fn, const TypeMemberInfo *TM); 123 124 // For testing only. VirtualCallTargetVirtualCallTarget125 VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian) 126 : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian), WasDevirt(false) {} 127 128 // The function (or an alias to a function) stored in the vtable. 129 GlobalValue *Fn; 130 131 // A pointer to the type identifier member through which the pointer to Fn is 132 // accessed. 133 const TypeMemberInfo *TM; 134 135 // When doing virtual constant propagation, this stores the return value for 136 // the function when passed the currently considered argument list. 137 uint64_t RetVal; 138 139 // Whether the target is big endian. 140 bool IsBigEndian; 141 142 // Whether at least one call site to the target was devirtualized. 143 bool WasDevirt; 144 145 // The minimum byte offset before the address point. This covers the bytes in 146 // the vtable object before the address point (e.g. RTTI, access-to-top, 147 // vtables for other base classes) and is equal to the offset from the start 148 // of the vtable object to the address point. minBeforeBytesVirtualCallTarget149 uint64_t minBeforeBytes() const { return TM->Offset; } 150 151 // The minimum byte offset after the address point. This covers the bytes in 152 // the vtable object after the address point (e.g. the vtable for the current 153 // class and any later base classes) and is equal to the size of the vtable 154 // object minus the offset from the start of the vtable object to the address 155 // point. minAfterBytesVirtualCallTarget156 uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; } 157 158 // The number of bytes allocated (for the vtable plus the byte array) before 159 // the address point. allocatedBeforeBytesVirtualCallTarget160 uint64_t allocatedBeforeBytes() const { 161 return minBeforeBytes() + TM->Bits->Before.Bytes.size(); 162 } 163 164 // The number of bytes allocated (for the vtable plus the byte array) after 165 // the address point. allocatedAfterBytesVirtualCallTarget166 uint64_t allocatedAfterBytes() const { 167 return minAfterBytes() + TM->Bits->After.Bytes.size(); 168 } 169 170 // Set the bit at position Pos before the address point to RetVal. setBeforeBitVirtualCallTarget171 void setBeforeBit(uint64_t Pos) { 172 assert(Pos >= 8 * minBeforeBytes()); 173 TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal); 174 } 175 176 // Set the bit at position Pos after the address point to RetVal. setAfterBitVirtualCallTarget177 void setAfterBit(uint64_t Pos) { 178 assert(Pos >= 8 * minAfterBytes()); 179 TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal); 180 } 181 182 // Set the bytes at position Pos before the address point to RetVal. 183 // Because the bytes in Before are stored in reverse order, we use the 184 // opposite endianness to the target. setBeforeBytesVirtualCallTarget185 void setBeforeBytes(uint64_t Pos, uint8_t Size) { 186 assert(Pos >= 8 * minBeforeBytes()); 187 if (IsBigEndian) 188 TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size); 189 else 190 TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size); 191 } 192 193 // Set the bytes at position Pos after the address point to RetVal. setAfterBytesVirtualCallTarget194 void setAfterBytes(uint64_t Pos, uint8_t Size) { 195 assert(Pos >= 8 * minAfterBytes()); 196 if (IsBigEndian) 197 TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size); 198 else 199 TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size); 200 } 201 }; 202 203 // Find the minimum offset that we may store a value of size Size bits at. If 204 // IsAfter is set, look for an offset before the object, otherwise look for an 205 // offset after the object. 206 LLVM_ABI uint64_t findLowestOffset(ArrayRef<VirtualCallTarget> Targets, 207 bool IsAfter, uint64_t Size); 208 209 // Set the stored value in each of Targets to VirtualCallTarget::RetVal at the 210 // given allocation offset before the vtable address. Stores the computed 211 // byte/bit offset to OffsetByte/OffsetBit. 212 LLVM_ABI void setBeforeReturnValues(MutableArrayRef<VirtualCallTarget> Targets, 213 uint64_t AllocBefore, unsigned BitWidth, 214 int64_t &OffsetByte, uint64_t &OffsetBit); 215 216 // Set the stored value in each of Targets to VirtualCallTarget::RetVal at the 217 // given allocation offset after the vtable address. Stores the computed 218 // byte/bit offset to OffsetByte/OffsetBit. 219 LLVM_ABI void setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets, 220 uint64_t AllocAfter, unsigned BitWidth, 221 int64_t &OffsetByte, uint64_t &OffsetBit); 222 223 } // end namespace wholeprogramdevirt 224 225 struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> { 226 ModuleSummaryIndex *ExportSummary; 227 const ModuleSummaryIndex *ImportSummary; 228 bool UseCommandLine = false; WholeProgramDevirtPassWholeProgramDevirtPass229 WholeProgramDevirtPass() 230 : ExportSummary(nullptr), ImportSummary(nullptr), UseCommandLine(true) {} WholeProgramDevirtPassWholeProgramDevirtPass231 WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, 232 const ModuleSummaryIndex *ImportSummary) 233 : ExportSummary(ExportSummary), ImportSummary(ImportSummary) { 234 assert(!(ExportSummary && ImportSummary)); 235 } 236 LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &); 237 }; 238 239 struct VTableSlotSummary { 240 StringRef TypeID; 241 uint64_t ByteOffset; 242 }; 243 LLVM_ABI bool 244 hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO); 245 LLVM_ABI void 246 updatePublicTypeTestCalls(Module &M, bool WholeProgramVisibilityEnabledInLTO); 247 LLVM_ABI void updateVCallVisibilityInModule( 248 Module &M, bool WholeProgramVisibilityEnabledInLTO, 249 const DenseSet<GlobalValue::GUID> &DynamicExportSymbols, 250 bool ValidateAllVtablesHaveTypeInfos, 251 function_ref<bool(StringRef)> IsVisibleToRegularObj); 252 LLVM_ABI void updateVCallVisibilityInIndex( 253 ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO, 254 const DenseSet<GlobalValue::GUID> &DynamicExportSymbols, 255 const DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols); 256 257 LLVM_ABI void getVisibleToRegularObjVtableGUIDs( 258 ModuleSummaryIndex &Index, 259 DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols, 260 function_ref<bool(StringRef)> IsVisibleToRegularObj); 261 262 /// Perform index-based whole program devirtualization on the \p Summary 263 /// index. Any devirtualized targets used by a type test in another module 264 /// are added to the \p ExportedGUIDs set. For any local devirtualized targets 265 /// only used within the defining module, the information necessary for 266 /// locating the corresponding WPD resolution is recorded for the ValueInfo 267 /// in case it is exported by cross module importing (in which case the 268 /// devirtualized target name will need adjustment). 269 LLVM_ABI void runWholeProgramDevirtOnIndex( 270 ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs, 271 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap); 272 273 /// Call after cross-module importing to update the recorded single impl 274 /// devirt target names for any locals that were exported. 275 LLVM_ABI void updateIndexWPDForExports( 276 ModuleSummaryIndex &Summary, 277 function_ref<bool(StringRef, ValueInfo)> isExported, 278 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap); 279 280 } // end namespace llvm 281 282 #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H 283