1*0b57cec5SDimitry Andric //===- MarkLive.cpp -------------------------------------------------------===// 2*0b57cec5SDimitry Andric // 3*0b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*0b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5*0b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*0b57cec5SDimitry Andric // 7*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 8*0b57cec5SDimitry Andric 9*0b57cec5SDimitry Andric #include "Chunks.h" 10*0b57cec5SDimitry Andric #include "Symbols.h" 11*0b57cec5SDimitry Andric #include "lld/Common/Timer.h" 12*0b57cec5SDimitry Andric #include "llvm/ADT/STLExtras.h" 13*0b57cec5SDimitry Andric #include <vector> 14*0b57cec5SDimitry Andric 15*0b57cec5SDimitry Andric namespace lld { 16*0b57cec5SDimitry Andric namespace coff { 17*0b57cec5SDimitry Andric 18*0b57cec5SDimitry Andric static Timer gctimer("GC", Timer::root()); 19*0b57cec5SDimitry Andric 20*0b57cec5SDimitry Andric // Set live bit on for each reachable chunk. Unmarked (unreachable) 21*0b57cec5SDimitry Andric // COMDAT chunks will be ignored by Writer, so they will be excluded 22*0b57cec5SDimitry Andric // from the final output. 23*0b57cec5SDimitry Andric void markLive(ArrayRef<Chunk *> chunks) { 24*0b57cec5SDimitry Andric ScopedTimer t(gctimer); 25*0b57cec5SDimitry Andric 26*0b57cec5SDimitry Andric // We build up a worklist of sections which have been marked as live. We only 27*0b57cec5SDimitry Andric // push into the worklist when we discover an unmarked section, and we mark 28*0b57cec5SDimitry Andric // as we push, so sections never appear twice in the list. 29*0b57cec5SDimitry Andric SmallVector<SectionChunk *, 256> worklist; 30*0b57cec5SDimitry Andric 31*0b57cec5SDimitry Andric // COMDAT section chunks are dead by default. Add non-COMDAT chunks. 32*0b57cec5SDimitry Andric for (Chunk *c : chunks) 33*0b57cec5SDimitry Andric if (auto *sc = dyn_cast<SectionChunk>(c)) 34*0b57cec5SDimitry Andric if (sc->live) 35*0b57cec5SDimitry Andric worklist.push_back(sc); 36*0b57cec5SDimitry Andric 37*0b57cec5SDimitry Andric auto enqueue = [&](SectionChunk *c) { 38*0b57cec5SDimitry Andric if (c->live) 39*0b57cec5SDimitry Andric return; 40*0b57cec5SDimitry Andric c->live = true; 41*0b57cec5SDimitry Andric worklist.push_back(c); 42*0b57cec5SDimitry Andric }; 43*0b57cec5SDimitry Andric 44*0b57cec5SDimitry Andric auto addSym = [&](Symbol *b) { 45*0b57cec5SDimitry Andric if (auto *sym = dyn_cast<DefinedRegular>(b)) 46*0b57cec5SDimitry Andric enqueue(sym->getChunk()); 47*0b57cec5SDimitry Andric else if (auto *sym = dyn_cast<DefinedImportData>(b)) 48*0b57cec5SDimitry Andric sym->file->live = true; 49*0b57cec5SDimitry Andric else if (auto *sym = dyn_cast<DefinedImportThunk>(b)) 50*0b57cec5SDimitry Andric sym->wrappedSym->file->live = sym->wrappedSym->file->thunkLive = true; 51*0b57cec5SDimitry Andric }; 52*0b57cec5SDimitry Andric 53*0b57cec5SDimitry Andric // Add GC root chunks. 54*0b57cec5SDimitry Andric for (Symbol *b : config->gcroot) 55*0b57cec5SDimitry Andric addSym(b); 56*0b57cec5SDimitry Andric 57*0b57cec5SDimitry Andric while (!worklist.empty()) { 58*0b57cec5SDimitry Andric SectionChunk *sc = worklist.pop_back_val(); 59*0b57cec5SDimitry Andric assert(sc->live && "We mark as live when pushing onto the worklist!"); 60*0b57cec5SDimitry Andric 61*0b57cec5SDimitry Andric // Mark all symbols listed in the relocation table for this section. 62*0b57cec5SDimitry Andric for (Symbol *b : sc->symbols()) 63*0b57cec5SDimitry Andric if (b) 64*0b57cec5SDimitry Andric addSym(b); 65*0b57cec5SDimitry Andric 66*0b57cec5SDimitry Andric // Mark associative sections if any. 67*0b57cec5SDimitry Andric for (SectionChunk &c : sc->children()) 68*0b57cec5SDimitry Andric enqueue(&c); 69*0b57cec5SDimitry Andric } 70*0b57cec5SDimitry Andric } 71*0b57cec5SDimitry Andric 72*0b57cec5SDimitry Andric } 73*0b57cec5SDimitry Andric } 74