[ELF] - Introduce helper for iterating over linker commands.

[grimar]

Summary

We often need to iterate over linker script commands.
And very often we need only a single command type in a loop.
I suggest adding the helper for convenience.
The patch shows the change I am suggesting.

[arichardson]

ELF/LinkerScript.h

317

Since this only seems to be used in foreach loops maybe using llvm::make_filter_range instead of creating a new vector would make sense?

[ruiu]

I'm personally not too excited about this kind of higher-order function, and my first impression is that the original code is better. I might be convinced either way, but I think I'm mildly against doing this.

[• espindola]

I like this, but I agree that we should avoid allocating a temporary std::vector.

[grimar]

• Reimplemented with use of make_filter_range.

(honestly, this looking a bit scary for me, though I still like the caller side simplifications).

[grimar]

In D45166#1054578, @ruiu wrote:

I'm personally not too excited about this kind of higher-order function, and my first impression is that the original code is better. I might be convinced either way, but I think I'm mildly against doing this.

The original code is sometimes hard to read IMO.
For example constructions like below are simplified greatly.

for (BaseCommand *Base : SectionCommands) {
auto *Sec = dyn_cast<OutputSection>(Base);
if (!Sec)
 continue;

You do not need to think about what is Base2 anymore:

for (BaseCommand *Base2 : Sec->SectionCommands)
if (auto *Cmd = dyn_cast<SymbolAssignment>(Base2))
  declareSymbol(Cmd);

[grimar]

• Cleanup.

[• espindola]

ELF/LinkerScript.h

317

s/static/inline, no?

Using auto as a return type is c++14 according to clang.

This could probably use a map + filter:

template <class CmdType>
using Foo = llvm::filter_iterator<ArrayRef<BaseCommand *>::iterator,
                                decltype(&dynCastToCmdType<CmdType>)>;

template <class CmdType>
using Bar =
  llvm::mapped_iterator<Foo<CmdType>, decltype(dynCastToCmdType<CmdType>) *>;

template <class CmdType>
llvm::iterator_range<Bar<CmdType>> filter(ArrayRef<BaseCommand *> V) {

But it feels like some of this code should be in LLVM. In particular, LLVM should probably have

• a make_mapped_range function
• type alias for filter_iterator_range

[• espindola]

The code I have is:

template <class CmdType> CmdType *castToCmdType(BaseCommand *Cmd) {
  return cast<CmdType>(Cmd);
}
template <class CmdType> bool isaCmdType(const BaseCommand *Cmd) {
  return isa<CmdType>(Cmd);
}
template <class CmdType>
using Foo = llvm::filter_iterator<ArrayRef<BaseCommand *>::iterator,
                                  decltype(&isaCmdType<CmdType>)>;
template <class CmdType>
using Bar =
    llvm::mapped_iterator<Foo<CmdType>, decltype(castToCmdType<CmdType>) *>;
template <class CmdType>
llvm::iterator_range<Bar<CmdType>> filter(ArrayRef<BaseCommand *> V) {
  auto R = llvm::make_filter_range(V, isaCmdType<CmdType>);
  // FIXME: llvm should have a make_mapped_range
  auto B = map_iterator(R.begin(), castToCmdType<CmdType>);
  auto E = map_iterator(R.end(), castToCmdType<CmdType>);
  return llvm::make_range(B, E);
}

[grimar]

• Used the approach suggested.

[grimar]

ELF/LinkerScript.h

317

Using auto as a return type is c++14 according to clang.

I thought we can use c++14 features as long as minimal versions of clang/gcc version accept it.
Not 100% sure that is the case for auto though honestly.

[• espindola]

LGTM

ELF/LinkerScript.h

317

Good question. It might be a good idea to ask on llvm-dev. At least the clang build is still using -std=c++11.

[grimar]

• Used filter<> in a few more places.

Rui, are you OK to land this version? It reduces nesting and simplifies loops..

[arichardson]

ELF/LinkerScript.h

318

This wrapper function could also be replaced with

template<typename CmdType>
using CastCmdType = CmdType *(*)(BaseCommand*);

And then using static_cast<CastCmdType<CmdType>>(&llvm::cast<CmdType, BaseCommand>) instead of castToCmdType<CmdType>.

However, I'm not sure that's any easier to understand.

ELF/AArch64ErrataFix.cpp

 bool AArch64Err843419Patcher::createFixes() {
   if (Initialized == false)
     init();
 
   bool AddressesChanged = false;
   for (OutputSection *OS : OutputSections) {
     if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
       continue;
-    for (BaseCommand *BC : OS->SectionCommands)
-      if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
-        std::vector<Patch843419Section *> Patches =
-            patchInputSectionDescription(*ISD);
-        if (!Patches.empty()) {
-          insertPatches(*ISD, Patches);
-          AddressesChanged = true;
-        }
-      }
+    for (auto *ISD : filter<InputSectionDescription>(OS->SectionCommands)) {
   }
   return AddressesChanged;
 }

ELF/LinkerScript.h

public:
   // Used to implement INSERT [AFTER|BEFORE]. Contains commands that need
   // to be inserted into SECTIONS commands list.
   llvm::DenseMap<StringRef, std::vector<BaseCommand *>> InsertAfterCommands;
   llvm::DenseMap<StringRef, std::vector<BaseCommand *>> InsertBeforeCommands;
 };
 
 extern LinkerScript *Script;
 
+template <class CmdType> static auto filter(ArrayRef<BaseCommand *> V) {
+  struct Iter
+      : llvm::iterator_adaptor_base<Iter, BaseCommand *const *,
+                                    std::random_access_iterator_tag, CmdType *,
+                                    ptrdiff_t, CmdType **, CmdType *> {
+    Iter(BaseCommand *const *I) : iterator_adaptor_base(I) {}
+    reference operator*() const { return dyn_cast<CmdType>(*I); }
+  };
+  return make_filter_range(llvm::iterator_range<Iter>(V),
+                           [](BaseCommand *Cmd) { return Cmd; });
+}
+
 } // end namespace elf
 } // end namespace lld
 
 #endif // LLD_ELF_LINKER_SCRIPT_H

ELF/LinkerScript.cpp

for (BaseCommand *Base : SectionCommands) {
     if (!Sec)
       continue;
     // If the output section directive has constraints,
     // we can't say for sure if it is going to be included or not.
     // Skip such sections for now. Improve the checks if we ever
     // need symbols from that sections to be declared early.
     if (Sec->Constraint != ConstraintKind::NoConstraint)
       continue;
-    for (BaseCommand *Base2 : Sec->SectionCommands)
-      if (auto *Cmd = dyn_cast<SymbolAssignment>(Base2))
-        declareSymbol(Cmd);
+
+    for (auto *Cmd : filter<SymbolAssignment>(Sec->SectionCommands))
   }
 }
 
 // This function is called from assignAddresses, while we are
 // fixing the output section addresses. This function is supposed
 // to set the final value for a given symbol assignment.
 void LinkerScript::assignSymbol(SymbolAssignment *Cmd, bool InSec) {
   if (Cmd->Name == ".") {
for (InputSection *S : V) {
     S->Live = false;
     discard(S->DependentSections);
   }
 }
 
 std::vector<InputSection *>
 LinkerScript::createInputSectionList(OutputSection &OutCmd) {
   std::vector<InputSection *> Ret;
-
-  for (BaseCommand *Base : OutCmd.SectionCommands) {
-    if (auto *Cmd = dyn_cast<InputSectionDescription>(Base)) {
-      Cmd->Sections = computeInputSections(Cmd);
-      Ret.insert(Ret.end(), Cmd->Sections.begin(), Cmd->Sections.end());
-    }
-  }
+  for (auto *Cmd : filter<InputSectionDescription>(OutCmd.SectionCommands)) {
   return Ret;
 }
 
 void LinkerScript::processSectionCommands() {
   // A symbol can be assigned before any section is mentioned in the linker
   // script. In an DSO, the symbol values are addresses, so the only important
   // section values are:
   // * SHN_UNDEF
if (auto *Sec = dyn_cast<OutputSection>(Base)) {
         for (InputSectionBase *S : V)
           S->Assigned = false;
         Sec->SectionCommands.clear();
         continue;
       }
 
       // A directive may contain symbol definitions like this:
       // ".foo : { ...; bar = .; }". Handle them.
-      for (BaseCommand *Base : Sec->SectionCommands)
-        if (auto *OutCmd = dyn_cast<SymbolAssignment>(Base))
-          addSymbol(OutCmd);
+      for (auto *OutCmd : filter<SymbolAssignment>(Sec->SectionCommands))
 
       // Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign
       // is given, input sections are aligned to that value, whether the
       // given value is larger or smaller than the original section alignment.
       if (Sec->SubalignExpr) {
         uint32_t Subalign = Sec->SubalignExpr().getValue();
         for (InputSectionBase *S : V)
           S->Alignment = Subalign;
void LinkerScript::adjustSectionsBeforeSorting() {
   // clutter the output.
   // We instead remove trivially empty sections. The bfd linker seems even
   // more aggressive at removing them.
   llvm::erase_if(SectionCommands, [&](BaseCommand *Base) { return !Base; });
 }
 
 void LinkerScript::adjustSectionsAfterSorting() {
   // Try and find an appropriate memory region to assign offsets in.
-  for (BaseCommand *Base : SectionCommands) {
-    if (auto *Sec = dyn_cast<OutputSection>(Base)) {
-      if (!Sec->LMARegionName.empty()) {
-        if (MemoryRegion *M = MemoryRegions.lookup(Sec->LMARegionName))
-          Sec->LMARegion = M;
-        else
-          error("memory region '" + Sec->LMARegionName + "' not declared");
-      }
-      Sec->MemRegion = findMemoryRegion(Sec);
-      // Handle align (e.g. ".foo : ALIGN(16) { ... }").
-      if (Sec->AlignExpr)
-        Sec->Alignment =
-            std::max<uint32_t>(Sec->Alignment, Sec->AlignExpr().getValue());
-    }
-  }
+  for (OutputSection *Sec : filter<OutputSection>(SectionCommands)) {
 
   // If output section command doesn't specify any segments,
   // and we haven't previously assigned any section to segment,
   // then we simply assign section to the very first load segment.
   // Below is an example of such linker script:
   // PHDRS { seg PT_LOAD; }
   // SECTIONS { .aaa : { *(.aaa) } }
   std::vector<StringRef> DefPhdrs;
   auto FirstPtLoad = llvm::find_if(PhdrsCommands, [](const PhdrsCommand &Cmd) {
     return Cmd.Type == PT_LOAD;
   });
   if (FirstPtLoad != PhdrsCommands.end())
     DefPhdrs.push_back(FirstPtLoad->Name);
 
   // Walk the commands and propagate the program headers to commands that don't
   // explicitly specify them.
-  for (BaseCommand *Base : SectionCommands) {
-    auto *Sec = dyn_cast<OutputSection>(Base);
-    if (!Sec)
-      continue;
-
+  for (OutputSection *Sec : filter<OutputSection>(SectionCommands)) {
     if (Sec->Phdrs.empty()) {
       // To match the bfd linker script behaviour, only propagate program
       // headers to sections that are allocated.
       if (Sec->Flags & SHF_ALLOC)
         Sec->Phdrs = DefPhdrs;
     } else {
       DefPhdrs = Sec->Phdrs;
     }

ELF/OutputSections.cpp

 }
 
 bool OutputSection::classof(const BaseCommand *C) {
   return C->Kind == OutputSectionKind;
 }
 
 void OutputSection::sort(std::function<int(InputSectionBase *S)> Order) {
   assert(Live);
-  for (BaseCommand *B : SectionCommands)
-    if (auto *ISD = dyn_cast<InputSectionDescription>(B))
-      sortByOrder(ISD->Sections, Order);
+  for (auto *ISD : filter<InputSectionDescription>(SectionCommands))
 }
 
 // Fill [Buf, Buf + Size) with Filler.
 // This is used for linker script "=fillexp" command.
 static void fill(uint8_t *Buf, size_t Size, uint32_t Filler) {
   size_t I = 0;
   for (; I + 4 < Size; I += 4)
     memcpy(Buf + I, &Filler, 4);
if (Filler) {
       else
         End = Buf + Sections[I + 1]->OutSecOff;
       fill(Start, End - Start, Filler);
     }
   });
 
   // Linker scripts may have BYTE()-family commands with which you
   // can write arbitrary bytes to the output. Process them if any.
-  for (BaseCommand *Base : SectionCommands)
-    if (auto *Data = dyn_cast<ByteCommand>(Base))
-      writeInt(Buf + Data->Offset, Data->Expression().getValue(), Data->Size);
+  for (auto *Data : filter<ByteCommand>(SectionCommands))
 }
 
 template <class ELFT>
 static void finalizeShtGroup(OutputSection *OS,
                              InputSection *Section) {
   assert(Config->Relocatable);
 
   // sh_link field for SHT_GROUP sections should contain the section index of
int elf::getPriority(StringRef S) {
   int V;
   if (!to_integer(S.substr(Pos + 1), V, 10))
     return 65536;
   return V;
 }
 
 std::vector<InputSection *> elf::getInputSections(OutputSection *OS) {
   std::vector<InputSection *> Ret;
-  for (BaseCommand *Base : OS->SectionCommands)
-    if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
-      Ret.insert(Ret.end(), ISD->Sections.begin(), ISD->Sections.end());
+  for (auto *ISD : filter<InputSectionDescription>(OS->SectionCommands))
   return Ret;
 }
 
 // Sorts input sections by section name suffixes, so that .foo.N comes
 // before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
 // We want to keep the original order if the priorities are the same
 // because the compiler keeps the original initialization order in a
 // translation unit and we need to respect that.

ELF/Relocations.cpp

 ThunkSection *ThunkCreator::getISThunkSec(InputSection *IS) {
   ThunkSection *TS = ThunkedSections.lookup(IS);
   if (TS)
     return TS;
 
   // Find InputSectionRange within Target Output Section (TOS) that the
   // InputSection (IS) that we need to precede is in.
   OutputSection *TOS = IS->getParent();
-  for (BaseCommand *BC : TOS->SectionCommands)
-    if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
-      if (ISD->Sections.empty())
-        continue;
-      InputSection *first = ISD->Sections.front();
-      InputSection *last = ISD->Sections.back();
-      if (IS->OutSecOff >= first->OutSecOff &&
-          IS->OutSecOff <= last->OutSecOff) {
-        TS = addThunkSection(TOS, ISD, IS->OutSecOff);
-        ThunkedSections[IS] = TS;
-        break;
-      }
-    }
+  for (auto *ISD : filter<InputSectionDescription>(TOS->SectionCommands)) {
+    if (IS->OutSecOff >= first->OutSecOff && IS->OutSecOff <= last->OutSecOff) {
   return TS;
 }
 
 // Create one or more ThunkSections per OS that can be used to place Thunks.
 // We attempt to place the ThunkSections using the following desirable
 // properties:
 // - Within range of the maximum number of callers
 // - Minimise the number of ThunkSections

 // Call Fn on every executable InputSection accessed via the linker script
 // InputSectionDescription::Sections.
 void ThunkCreator::forEachInputSectionDescription(
     ArrayRef<OutputSection *> OutputSections,
     std::function<void(OutputSection *, InputSectionDescription *)> Fn) {
   for (OutputSection *OS : OutputSections) {
     if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
       continue;
-    for (BaseCommand *BC : OS->SectionCommands)
-      if (auto *ISD = dyn_cast<InputSectionDescription>(BC))
-        Fn(OS, ISD);
+    for (auto *ISD : filter<InputSectionDescription>(OS->SectionCommands))
   }
 }
 
 // Return true if the relocation target is an in range Thunk.
 // Return false if the relocation is not to a Thunk. If the relocation target
 // was originally to a Thunk, but is no longer in range we revert the
 // relocation back to its original non-Thunk target.
 bool ThunkCreator::normalizeExistingThunk(Relocation &Rel, uint64_t Src) {

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
   }
 }
 
 template <class ELFT> void Writer<ELFT>::addSectionSymbols() {
   // Create a section symbol for each output section so that we can represent
   // relocations that point to the section. If we know that no relocation is
   // referring to a section (that happens if the section is a synthetic one), we
   // don't create a section symbol for that section.
-  for (BaseCommand *Base : Script->SectionCommands) {
-    auto *Sec = dyn_cast<OutputSection>(Base);
-    if (!Sec)
-      continue;
+  for (auto *Sec : filter<OutputSection>(Script->SectionCommands)) {
     auto I = llvm::find_if(Sec->SectionCommands, [](BaseCommand *Base) {
       if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
         return !ISD->Sections.empty();
       return false;
     });
     if (I == Sec->SectionCommands.end())
       continue;
     InputSection *IS = cast<InputSectionDescription>(*I)->Sections[0];
static void sortSection(OutputSection *Sec,
 
   // Never sort these.
   if (Name == ".init" || Name == ".fini")
     return;
 
   // Sort input sections by priority using the list provided
   // by --symbol-ordering-file.
   if (!Order.empty())
-    for (BaseCommand *B : Sec->SectionCommands)
-      if (auto *ISD = dyn_cast<InputSectionDescription>(B))
-        sortISDBySectionOrder(ISD, Order);
+    for (auto *ISD : filter<InputSectionDescription>(Sec->SectionCommands))
 }
 
 // If no layout was provided by linker script, we want to apply default
 // sorting for special input sections. This also handles --symbol-ordering-file.
 template <class ELFT> void Writer<ELFT>::sortInputSections() {
   // Build the order once since it is expensive.
   DenseMap<const InputSectionBase *, int> Order = buildSectionOrder();
-  for (BaseCommand *Base : Script->SectionCommands)
-    if (auto *Sec = dyn_cast<OutputSection>(Base))
-      sortSection(Sec, Order);
+  for (auto *Sec : filter<OutputSection>(Script->SectionCommands))
 }
 
 template <class ELFT> void Writer<ELFT>::sortSections() {
   Script->adjustSectionsBeforeSorting();
 
   // Don't sort if using -r. It is not necessary and we want to preserve the
   // relative order for SHF_LINK_ORDER sections.
   if (Config->Relocatable)
     return;
 
-  for (BaseCommand *Base : Script->SectionCommands)
-    if (auto *Sec = dyn_cast<OutputSection>(Base))
-      Sec->SortRank = getSectionRank(Sec);
+  for (auto *Sec : filter<OutputSection>(Script->SectionCommands))
 
   sortInputSections();
 
   if (!Script->HasSectionsCommand) {
     // We know that all the OutputSections are contiguous in this case.
     auto E = Script->SectionCommands.end();
     auto I = Script->SectionCommands.begin();
     auto IsSection = [](BaseCommand *Base) { return isa<OutputSection>(Base); };
if (!Config->Relocatable && Config->EMachine == EM_ARM &&
         }
       }
     }
 
     for (int I = 0, N = Sections.size(); I < N; ++I)
       *ScriptSections[I] = Sections[I];
 
     // Remove the Sections we marked as duplicate earlier.
-    for (BaseCommand *Base : Sec->SectionCommands)
-      if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
-        llvm::erase_if(ISD->Sections, [](InputSection *IS) { return !IS; });
+    for (auto *ISD : filter<InputSectionDescription>(Sec->SectionCommands))
   }
 }
 
 static void applySynthetic(const std::vector<SyntheticSection *> &Sections,
                            std::function<void(SyntheticSection *)> Fn) {
   for (SyntheticSection *SS : Sections)
     if (SS && SS->getParent() && !SS->empty())
       Fn(SS);
for (InputSectionBase *S : llvm::reverse(InputSections)) {
     if (!SS)
       return;
     OutputSection *OS = SS->getParent();
     if (!OS || !SS->empty())
       continue;
 
     // If we reach here, then SS is an unused synthetic section and we want to
     // remove it from corresponding input section description of output section.
-    for (BaseCommand *B : OS->SectionCommands)
-      if (auto *ISD = dyn_cast<InputSectionDescription>(B))
-        llvm::erase_if(ISD->Sections,
-                       [=](InputSection *IS) { return IS == SS; });
+    for (auto *ISD : filter<InputSectionDescription>(OS->SectionCommands))
+      llvm::erase_if(ISD->Sections, [=](InputSection *IS) { return IS == SS; });
   }
 }
 
 // Returns true if a symbol can be replaced at load-time by a symbol
 // with the same name defined in other ELF executable or DSO.
 static bool computeIsPreemptible(const Symbol &B) {
   assert(!B.isLocal());
   // Only symbols that appear in dynsym can be preempted.
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   Out::InitArray = findSection(".init_array");
   Out::FiniArray = findSection(".fini_array");
 
   // The linker needs to define SECNAME_start, SECNAME_end and SECNAME_stop
   // symbols for sections, so that the runtime can get the start and end
   // addresses of each section by section name. Add such symbols.
   if (!Config->Relocatable) {
     addStartEndSymbols();
-    for (BaseCommand *Base : Script->SectionCommands)
-      if (auto *Sec = dyn_cast<OutputSection>(Base))
-        addStartStopSymbols(Sec);
+    for (OutputSection *Sec : filter<OutputSection>(Script->SectionCommands))
   }
 
   // Add _DYNAMIC symbol. Unlike GNU gold, our _DYNAMIC symbol has no type.
   // It should be okay as no one seems to care about the type.
   // Even the author of gold doesn't remember why gold behaves that way.
   // https://sourceware.org/ml/binutils/2002-03/msg00360.html
   if (InX::DynSymTab)
     Symtab->addRegular("_DYNAMIC", STV_HIDDEN, STT_NOTYPE, 0 /*Value*/,
if (errorCount())
     return;
 
   removeUnusedSyntheticSections();
 
   sortSections();
 
   // Now that we have the final list, create a list of all the
   // OutputSections for convenience.
-  for (BaseCommand *Base : Script->SectionCommands)
-    if (auto *Sec = dyn_cast<OutputSection>(Base))
-      OutputSections.push_back(Sec);
+  for (OutputSection *Sec : filter<OutputSection>(Script->SectionCommands))
 
   // Prefer command line supplied address over other constraints.
   for (OutputSection *Sec : OutputSections) {
     auto I = Config->SectionStartMap.find(Sec->Name);
     if (I != Config->SectionStartMap.end())
       Sec->AddrExpr = [=] { return I->second; };
   }