Add --check-library-dependency to maintain compatibility with other linkers

[ruiu]

Summary

I'm proposing a new command line flag, --check-library-dependency, in
this patch. The flag and the feature proposed below doesn't exist in
GNU linkers nor the current lld.

--check-library-dependency is an option to detect reverse or cyclic
dependencies between static archives, and it can be used to keep
your program compatible with GNU linkers after you switch to lld.
I'll explain the feature and why you may find it useful below.

lld's symbol resolution semantics is more relaxed than traditional
Unix linkers. Therefore,

ld.lld foo.a bar.o

succeeds even if bar.o contains an undefined symbol that have to be
resolved by some object file in foo.a. Traditional Unix linkers
don't allow this kind of backward reference, as they visit each
file only once from left to right in the command line while
resolving all undefined symbol at the moment of visiting.

In the above case, since there's no undefined symbol when a linker
visits foo.a, no files are pulled out from foo.a, and because the
linker forgets about foo.a after visiting, it can't resolve
undefined symbols that could have been resolved otherwise.

That lld accepts more relaxed form means (besides it makes more
sense) that you can accidentally write a command line or a build
file that works only with lld, even if you have a plan to
distribute it to wider users who may be using GNU linkers. With
--check-library-dependency, you can detect a library order that
doesn't work with other Unix linkers.

The option is also useful to detect cyclic dependencies between
static archives. Again, lld accepts

ld.lld foo.a bar.a

even if foo.a and bar.a depend on each other. With
--check-library-dependency, it is handled as an error.

Here is how the option works. We assign a group ID to each file. A
file with a smaller group ID can pull out object files from an
archive file with an equal or greater group ID. Otherwise, it is a
reverse dependency and an error.

A file outside --{start,end}-group gets a fresh ID when
instantiated. All files within the same --{start,end}-group get the
same group ID. E.g.

ld.lld A B --start-group C D --end-group E

A and B form group 0, C, D and their member object files form group
1, and E forms group 2. I think that you can see how this group
assignment rule simulates the traditional linker's semantics.

[ruiu]

• rebase

[ruiu]

• revert unrelated change

[grimar]

lld/ELF/Driver.cpp

929

I think GroupDepth should not be a member of InputFile.
It could be a local variable it seems:

  int32_t GroupDepth = 0;
  for (auto *Arg : Args) {
    switch (Arg->getOption().getUnaliasedOption().getID()) {
...
    case OPT_start_group:
      ++GroupDepth;
      break;
    case OPT_end_group:
      if (GroupDepth > 0)
        --GroupDepth;
      else
        error("stray --end-group");
      break;
...
    }

    // All files within the same --start-group and --end-group get the
    // same group ID. Otherwise, a new file will get a new group ID.
    if (!GroupDepth)
      ++InputFile::CurrentGroupId;
  }

lld/ELF/SymbolTable.cpp

295

I think our comments are usually impersonal.

339

I would end the sentence after "group 0."
Otherwise "0, C, D" looks like a single list.

341

"I think that you can see how this group assignment rule simulates the traditional linker's semantics."

Is also personal and does not make sense in the comment. It brings no new information about the feature.
I would remove this sentence completely.

344

Why is it "bad"? In the policy of LLD it is valid and hence neutral. It just that old linkers
does not support such references, though that do not make them "bad". I would drop this word.

344

Also, should it be a warning? It is a bit more flexible probably.

621

checkDependency duplicates in few places, I would suggest
to land D45083 first and I think you should be able to use SymbolTable::fetchIfLazy here and
move checkDependency there to avoid duplications.

[ruiu]

I'd like to not reply on each comment as I want reviewers focus on design and feature themselves first.

Guys, do you think the new command line option name make sense? Do you think it's actually useful?

[dblaikie]

Makes sense to me - I haven't applied/tested the patch against some recent
commits to LLVM I've made that broke gold/binutils ld based builders but
didn't break for me locally (using lld), but assuming it catches those -
yeah, it'd be useful to me & I'd totally turn it on locally & suggest
anyone else using lld with LLVM to do so as well.

[ruiu]

• rebased
• recognize GROUP linker script command

[• espindola]

The option and general algorithm makes sense to me.

I am just not sure about the name since cyclic dependencies are still supported with --start-group/--end-group for example.

BTW, I think this is a conservative heuristic since it would warn on "foo.a --start-group bar.a foo.a --end-group" if bar.a fetches a member of foo.a. That is probably fine.

Taking a look at the implementation now.

[• espindola]

lld/ELF/Options.td

354

To fetch archive members. Otherwise it sounds like bar.o cannot refer to foo.o in "foo.o bar.o".

lld/ELF/SymbolTable.cpp

292

This seems to be over selling it. It will not detect cyclic reference if the members that cause it are not used.

I think it is clear to just say that the option prevents an undefined reference from fetching a member written earlier in the command line.

342

I agree that "bad" is out of place. The user asked to find backwards references and we found one.

From the error it is also not clear that Name is a symbol name. How about something like

Undefined reference Name in Old refers to New.

378

I think this is the only call to checkDependency that you need. We never find a backward reference when adding a lazy symbol.

[ruiu]

• address review comments

[ruiu]

lld/ELF/Driver.cpp

929

We can't do that because we have to handle linker scripts as well.

lld/ELF/Options.td

354

Done

lld/ELF/SymbolTable.cpp

292

Done

295

I think "I" in this comment (in particular in this sentence) is fine.

342

Changed the wording.

378

Done

[ruiu]

Overall I'm satisfied with this patch. It's small and I _believe_ it works for the purpose to keep your build file compatible with GNU. That said, I want to be careful when I add a new command line flag (in particular something important like this), so I'll start a discussion on llvm-dev to get feedback from those who are using lld and interested in this feature.

[peter.smith]

Perhaps --check-library-dependency is too strong a name for the cases that this can catch. I think it is really a --find-library-backreferences that can be helpful as part of resolving differences in behaviour between lld and other unix linkers, but there are limitations.

Looking at this from a perspective of someone trying to migrate from GNU to LLD. Consider these cases for which --check-library-dependency will detect a back reference, but the outcomes are different in each case:
Library f1.a containing f1.o that defines f()
Library f2.a containing f2.o that defines f()
Library g.a containing g.o that defines g(), g.o references f()
Object m.o containing main() that references g()

The link lines below all result in the same backward reference warning:
m.o f1.a g.a : result in an undefined symbol error on a GNU linker, succeed with LLD with f1.o from f1.a.
m.o f1.a g.a f1.a : result in GNU Linker and LLD extracting the same library, f1.o from f1.a
m.o f1.a g.a f2.a f1.a : result in different outputs as the GNU Linker will select f2.o from f2.a to define f and LLD will detect f1.a

The next example does not give a backward reference warning but does give different results on GNU and LLD
m.o --start-group f1.a g.a f2.a f1.a --end-group : result in different outputs as the GNU Linker will select f2.o from f2.a to define f and LLD will detect f1.a

The last example could be problematic for users wanting to start a new project and guarantee that it will work with LLD and GNU assuming --check-library-dependency. I think that we may need a two level index, file level and group level, so that we can check for back-references with the group.

[• espindola]

I am OK with this patch. My only concern is the name. I like the --find-library-backreferences suggestion.

[ruiu]

--find-library-backreferences might be indeed better than --check-library-dependency, but both options are perhaps too long as a Unix linker option? How about --detect-backrefs? Maybe just --backref?

[• espindola]

In D45195#1058915, @ruiu wrote:

--find-library-backreferences might be indeed better than --check-library-dependency, but both options are perhaps too long as a Unix linker option? How about --detect-backrefs? Maybe just --backref?

+1 for --detect-backrefs.

[peter.smith]

In D45195#1058915, @ruiu wrote:

--find-library-backreferences might be indeed better than --check-library-dependency, but both options are perhaps too long as a Unix linker option? How about --detect-backrefs? Maybe just --backref?

I think --backref is a bit too abstract, from looking at the option in a command line I would have no idea what it actually did without looking at the help. I think --detect-backrefs is better as it at least hints that it is of a diagnostic nature. I've got a mild preference for adding library or lib so we know what backrefs are referring to, but if everyone else is happy with --detect-backrefs then go with that. As an aside, Looking at the length of options in ld.bfd --help I think it has long given up on short option names, particularly for infrequently used ones.

[grimar]

FWIW, --detect-backrefs sounds better for me than --backrefs.

Also can suggest -no-backrefs.

lld/ELF/Driver.cpp

629

Does it make sense to enable it by default?

[grimar]

Or maybe warn-backrefs (similarly to warn-common, warn-symbol-ordering and warn-unresolved-symbols).

[• espindola]

In D45195#1059454, @grimar wrote:

Or maybe warn-backrefs (similarly to warn-common, warn-symbol-ordering and warn-unresolved-symbols).

True, that is a nice precedent.

I would leave the warning off at least initially.

[MaskRay]

lld/ELF/Driver.cpp

929

It seems gold does not support nested --start-group --end-group

% ld.gold -\( -\( a.o -\) -\)     
ld.gold: fatal error: May not nest groups

lld/ELF/SymbolTable.cpp

336

Does A forms group 0 while B forms group 1?

[ruiu]

lld/ELF/Driver.cpp

929

Oh, I didn't know that. That means we can replace GroupDepth with a boolean variable.

lld/ELF/SymbolTable.cpp

336

You are right. I'll update this comment.

[ruiu]

• renamed the option --warn-backrefs
• address other comments

[ruiu]

• update comments

[• espindola]

Fine by me.

[emaste]

lld/trunk/ELF/Options.td

333 ↗

(On Diff #141763)

I'm not sure what fetch archive members means in this context. What about "warn about undefined symbol references satisifed by earlier archive members" or something like that?

lld/trunk/ELF/SymbolTable.cpp

292 ↗

(On Diff #141763)

Does the option prevent this case or (in the absence of -fatal-warnings) only warn about it?

lld/ELF/Config.h

struct Configuration {
   bool AllowMultipleDefinition;
   bool AndroidPackDynRelocs = false;
   bool ARMHasBlx = false;
   bool ARMHasMovtMovw = false;
   bool ARMJ1J2BranchEncoding = false;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;
+  bool CheckLibraryDependency;
   bool CheckSections;
   bool CompressDebugSections;
   bool Cref;
   bool DefineCommon;
   bool Demangle = true;
   bool DisableVerify;
   bool EhFrameHdr;
   bool EmitRelocs;

lld/ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
 
   Config->AllowMultipleDefinition =
       Args.hasFlag(OPT_allow_multiple_definition,
                    OPT_no_allow_multiple_definition, false) ||
       hasZOption(Args, "muldefs");
   Config->AuxiliaryList = args::getStrings(Args, OPT_auxiliary);
   Config->Bsymbolic = Args.hasArg(OPT_Bsymbolic);
   Config->BsymbolicFunctions = Args.hasArg(OPT_Bsymbolic_functions);
+  Config->CheckLibraryDependency = Args.hasFlag(
+      OPT_check_library_dependency, OPT_no_check_library_dependency, false);
   Config->CheckSections =
       Args.hasFlag(OPT_check_sections, OPT_no_check_sections, true);
   Config->Chroot = Args.getLastArgValue(OPT_chroot);
   Config->CompressDebugSections = getCompressDebugSections(Args);
   Config->Cref = Args.hasFlag(OPT_cref, OPT_no_cref, false);
   Config->DefineCommon = Args.hasFlag(OPT_define_common, OPT_no_define_common,
                                       !Args.hasArg(OPT_relocatable));
   Config->Demangle = Args.hasFlag(OPT_demangle, OPT_no_demangle, true);
case OPT_no_whole_archive:
       InWholeArchive = (ID == OPT_whole_archive);
       break;
     case OPT_just_symbols:
       if (Optional<MemoryBufferRef> MB = readFile(Arg->getValue())) {
         Files.push_back(createObjectFile(*MB));
         Files.back()->JustSymbols = true;
       }
       break;
+    case OPT_start_group:
+      ++InputFile::GroupDepth;
+      break;
+    case OPT_end_group:
+      if (InputFile::GroupDepth > 0)
+        --InputFile::GroupDepth;
+      else
+        error("stray --end-group");
+      break;
     case OPT_start_lib:
     case OPT_end_lib:
       InLib = (ID == OPT_start_lib);
       break;
     }
   }
 
   if (Files.empty() && errorCount() == 0)

lld/ELF/InputFiles.h

public:
   mutable std::string ToStringCache;
 
   std::string getSrcMsg(const Symbol &Sym, InputSectionBase &Sec,
                         uint64_t Offset);
 
   // True if this is an argument for --just-symbols. Usually false.
   bool JustSymbols = false;
 
+  // GroupId is used for --check-library-dependency which is an
+  // optional error checking feature. All files within the same
+  // --{start,end}-group get the same group ID. Otherwise, each file
+  // gets a new group ID. For more info, see checkDependency() in
+  // SymbolTable.cpp.
+  uint32_t GroupId;
+  static uint32_t GroupDepth;
+
 protected:
   InputFile(Kind K, MemoryBufferRef M);
   std::vector<InputSectionBase *> Sections;
   std::vector<Symbol *> Symbols;
 
 private:
   const Kind FileKind;
+
+  static uint32_t NextGroupId;
 };
 
 template <typename ELFT> class ELFFileBase : public InputFile {
 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Word Elf_Word;
   typedef typename ELFT::SymRange Elf_Sym_Range;

lld/ELF/InputFiles.cpp

 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::sys;
 using namespace llvm::sys::fs;
 
 using namespace lld;
 using namespace lld::elf;
 
+uint32_t InputFile::GroupDepth;
+uint32_t InputFile::NextGroupId;
 std::vector<BinaryFile *> elf::BinaryFiles;
 std::vector<BitcodeFile *> elf::BitcodeFiles;
 std::vector<InputFile *> elf::ObjectFiles;
 std::vector<InputFile *> elf::SharedFiles;
 
 TarWriter *elf::Tar;
 
-InputFile::InputFile(Kind K, MemoryBufferRef M) : MB(M), FileKind(K) {}
+InputFile::InputFile(Kind K, MemoryBufferRef M)
+    : MB(M), GroupId(NextGroupId), FileKind(K) {
+  // All files within the same --{start,end}-group get the same group ID.
+  // Otherwise, a new file will get a new group ID.
+  if (GroupDepth == 0)
+    ++NextGroupId;
+}
 
 Optional<MemoryBufferRef> elf::readFile(StringRef Path) {
   // The --chroot option changes our virtual root directory.
   // This is useful when you are dealing with files created by --reproduce.
   if (!Config->Chroot.empty() && Path.startswith("/"))
     Path = Saver.save(Config->Chroot + Path);
 
   log(Path);
MemoryBufferRef MB =
       CHECK(C.getMemoryBufferRef(),
             toString(this) +
                 ": could not get the buffer for the member defining symbol " +
                 Sym.getName());
 
   if (Tar && C.getParent()->isThin())
     Tar->append(relativeToRoot(CHECK(C.getFullName(), this)), MB.getBuffer());
 
-  return createObjectFile(MB, getName(),
-                          C.getParent()->isThin() ? 0 : C.getChildOffset());
+  InputFile *File = createObjectFile(
+      MB, getName(), C.getParent()->isThin() ? 0 : C.getChildOffset());
+  File->GroupId = GroupId;
+  return File;
 }
 
 template <class ELFT>
 SharedFile<ELFT>::SharedFile(MemoryBufferRef M, StringRef DefaultSoName)
     : ELFFileBase<ELFT>(Base::SharedKind, M), SoName(DefaultSoName),
       IsNeeded(!Config->AsNeeded) {}
 
 // Partially parse the shared object file so that we can call
MemoryBufferRef LazyObjFile::getBuffer() {
   Seen = true;
   return MB;
 }
 
 InputFile *LazyObjFile::fetch() {
   MemoryBufferRef MBRef = getBuffer();
   if (MBRef.getBuffer().empty())
     return nullptr;
-  return createObjectFile(MBRef, ArchiveName, OffsetInArchive);
+
+  InputFile *File = createObjectFile(MBRef, ArchiveName, OffsetInArchive);
+  File->GroupId = GroupId;
+  return File;
 }
 
 template <class ELFT> void LazyObjFile::parse() {
   // A lazy object file wraps either a bitcode file or an ELF file.
   if (isBitcode(this->MB)) {
     std::unique_ptr<lto::InputFile> Obj =
         CHECK(lto::InputFile::create(this->MB), this);
     for (const lto::InputFile::Symbol &Sym : Obj->symbols())

lld/ELF/Options.td

defm eh_frame_hdr: B<"eh-frame-hdr",
     "Request creation of .eh_frame_hdr section and PT_GNU_EH_FRAME segment header",
     "Do not create .eh_frame_hdr section">;
 
 def emit_relocs: F<"emit-relocs">, HelpText<"Generate relocations in output">;
 
 def enable_new_dtags: F<"enable-new-dtags">,
   HelpText<"Enable new dynamic tags">;
 
+def end_group: F<"end-group">,
+  HelpText<"Ignored for compatibility with GNU unless you pass --check-library-dependency">;
+
 def end_lib: F<"end-lib">,
   HelpText<"End a grouping of objects that should be treated as if they were together in an archive">;
 
 defm entry: Eq<"entry">, HelpText<"Name of entry point symbol">,
   MetaVarName<"<entry>">;
 
 defm error_limit: Eq<"error-limit">,
   HelpText<"Maximum number of errors to emit before stopping (0 = no limit)">;

 
 def shared: F<"shared">, HelpText<"Build a shared object">;
 
 defm soname: Eq<"soname">, HelpText<"Set DT_SONAME">;
 
 defm sort_section: Eq<"sort-section">,
   HelpText<"Specifies sections sorting rule when linkerscript is used">;
 
+def start_group: F<"start-group">,
+  HelpText<"Ignored for compatibility with GNU unless you pass --check-library-dependency">;
+
 def start_lib: F<"start-lib">,
   HelpText<"Start a grouping of objects that should be treated as if they were together in an archive">;
 
 def strip_all: F<"strip-all">, HelpText<"Strip all symbols">;
 
 def strip_debug: F<"strip-debug">, HelpText<"Strip debugging information">;
 
 defm symbol_ordering_file: Eq<"symbol-ordering-file">,
defm whole_archive: B<"whole-archive",
     "Do not force load of all members in a static library">;
 
 defm wrap: Eq<"wrap">, HelpText<"Use wrapper functions for symbol">,
   MetaVarName<"<symbol>">;
 
 def z: JoinedOrSeparate<["-"], "z">, MetaVarName<"<option>">,
   HelpText<"Linker option extensions">;
 
+defm check_library_dependency: B<"check-library-dependency",
+    "Do not allow backward symbol references",
+    "Allow backward symbol references">;
+
 // Aliases
 def alias_auxiliary: Separate<["-"], "f">, Alias<auxiliary>;
 def alias_Bdynamic_call_shared: F<"call_shared">, Alias<Bdynamic>;
 def alias_Bdynamic_dy: F<"dy">, Alias<Bdynamic>;
 def alias_Bstatic_dn: F<"dn">, Alias<Bstatic>;
 def alias_Bstatic_non_shared: F<"non_shared">, Alias<Bstatic>;
 def alias_Bstatic_static: F<"static">, Alias<Bstatic>;
 def alias_define_common_d: Flag<["-"], "d">, Alias<define_common>;
 def alias_define_common_dc: F<"dc">, Alias<define_common>;
 def alias_define_common_dp: F<"dp">, Alias<define_common>;
 def alias_discard_all_x: Flag<["-"], "x">, Alias<discard_all>;
 def alias_discard_locals_X: Flag<["-"], "X">, Alias<discard_locals>;
 def alias_emit_relocs: Flag<["-"], "q">, Alias<emit_relocs>;
+def alias_end_group_paren: Flag<["-"], ")">, Alias<end_group>;
 def alias_entry_e: JoinedOrSeparate<["-"], "e">, Alias<entry>;
 def alias_export_dynamic_E: Flag<["-"], "E">, Alias<export_dynamic>;
 def alias_filter: Separate<["-"], "F">, Alias<filter>;
 def alias_format_b: Separate<["-"], "b">, Alias<format>;
 def alias_library: JoinedOrSeparate<["-"], "l">, Alias<library>;
 def alias_library_path: JoinedOrSeparate<["-"], "L">, Alias<library_path>;
 def alias_no_pie_pic_executable: F<"no-pic-executable">, Alias<no_pie>;
 def alias_omagic: Flag<["-"], "N">, Alias<omagic>;
 def alias_o_output: Joined<["--"], "output=">, Alias<o>;
 def alias_o_output2 : Separate<["--"], "output">, Alias<o>;
 def alias_pie_pic_executable: F<"pic-executable">, Alias<pie>;
 def alias_print_map_M: Flag<["-"], "M">, Alias<print_map>;
 def alias_relocatable_r: Flag<["-"], "r">, Alias<relocatable>;
 def alias_rpath_R: JoinedOrSeparate<["-"], "R">, Alias<rpath>;
 def alias_script_T: JoinedOrSeparate<["-"], "T">, Alias<script>;
 def alias_shared_Bshareable: F<"Bshareable">, Alias<shared>;
 def alias_soname_h: JoinedOrSeparate<["-"], "h">, Alias<soname>;
+def alias_start_group_paren: Flag<["-"], "(">, Alias<start_group>;
 def alias_strip_all: Flag<["-"], "s">, Alias<strip_all>;
 def alias_strip_debug_S: Flag<["-"], "S">, Alias<strip_debug>;
 def alias_trace: Flag<["-"], "t">, Alias<trace>;
 def alias_trace_symbol_y : JoinedOrSeparate<["-"], "y">, Alias<trace_symbol>;
 def alias_Ttext_segment: Separate<["-", "--"], "Ttext-segment">, Alias<Ttext>;
 def alias_Ttext_segment_eq: Joined<["-", "--"], "Ttext-segment=">, Alias<Ttext>;
 def alias_undefined_u: JoinedOrSeparate<["-"], "u">, Alias<undefined>;
 def alias_version_V: Flag<["-"], "V">, Alias<version>;
 
-// Our symbol resolution algorithm handles symbols in archive files differently
-// than traditional linkers, so we don't need --start-group and --end-group.
-// These options are recongized for compatibility but ignored.
-def end_group: F<"end-group">;
-def end_group_paren: Flag<["-"], ")">;
-def start_group: F<"start-group">;
-def start_group_paren: Flag<["-"], "(">;
-
 // LTO-related options.
 def lto_aa_pipeline: J<"lto-aa-pipeline=">,
   HelpText<"AA pipeline to run during LTO. Used in conjunction with -lto-newpm-passes">;
 def lto_newpm_passes: J<"lto-newpm-passes=">,
   HelpText<"Passes to run during LTO">;
 def lto_partitions: J<"lto-partitions=">,
   HelpText<"Number of LTO codegen partitions">;
 def disable_verify: F<"disable-verify">;

lld/ELF/ScriptParser.cpp

 private:
   void addFile(StringRef Path);
 
   void readAsNeeded();
   void readEntry();
   void readExtern();
   void readGroup();
   void readInclude();
+  void readInput();
   void readMemory();
   void readOutput();
   void readOutputArch();
   void readOutputFormat();
   void readPhdrs();
   void readRegionAlias();
   void readSearchDir();
   void readSections();
if (Tok == ";")
       continue;
 
     if (Tok == "ASSERT") {
       Script->SectionCommands.push_back(readAssert());
     } else if (Tok == "ENTRY") {
       readEntry();
     } else if (Tok == "EXTERN") {
       readExtern();
-    } else if (Tok == "GROUP" || Tok == "INPUT") {
+    } else if (Tok == "GROUP") {
       readGroup();
     } else if (Tok == "INCLUDE") {
       readInclude();
+    } else if (Tok == "INPUT") {
+      readInput();
     } else if (Tok == "MEMORY") {
       readMemory();
     } else if (Tok == "OUTPUT") {
       readOutput();
     } else if (Tok == "OUTPUT_ARCH") {
       readOutputArch();
     } else if (Tok == "OUTPUT_FORMAT") {
       readOutputFormat();

 
 void ScriptParser::readExtern() {
   expect("(");
   while (!errorCount() && !consume(")"))
     Config->Undefined.push_back(next());
 }
 
 void ScriptParser::readGroup() {
-  expect("(");
-  while (!errorCount() && !consume(")")) {
-    if (consume("AS_NEEDED"))
-      readAsNeeded();
-    else
-      addFile(unquote(next()));
-  }
+  ++InputFile::GroupDepth;
+  readInput();
+  --InputFile::GroupDepth;
 }
 
 void ScriptParser::readInclude() {
   StringRef Tok = unquote(next());
 
   if (!Seen.insert(Tok).second) {
     setError("there is a cycle in linker script INCLUDEs");
     return;
   }
 
   if (Optional<std::string> Path = searchLinkerScript(Tok)) {
     if (Optional<MemoryBufferRef> MB = readFile(*Path))
       tokenize(*MB);
     return;
   }
   setError("cannot find linker script " + Tok);
 }
 
+void ScriptParser::readInput() {
+  expect("(");
+  while (!errorCount() && !consume(")")) {
+    if (consume("AS_NEEDED"))
+      readAsNeeded();
+    else
+      addFile(unquote(next()));
+  }
+}
+
 void ScriptParser::readOutput() {
   // -o <file> takes predecence over OUTPUT(<file>).
   expect("(");
   StringRef Tok = next();
   if (Config->OutputFile.empty())
     Config->OutputFile = unquote(Tok);
   expect(")");
 }

lld/ELF/SymbolTable.cpp

 template <class ELFT> Symbol *SymbolTable::addUndefined(StringRef Name) {
   return addUndefined<ELFT>(Name, STB_GLOBAL, STV_DEFAULT,
                             /*Type*/ 0,
                             /*CanOmitFromDynSym*/ false, /*File*/ nullptr);
 }
 
 static uint8_t getVisibility(uint8_t StOther) { return StOther & 3; }
 
+// Do extra check for --check-library-dependency.
+//
+// --check-library-dependency is an option to detect reverse or cyclic
+// dependencies between static archives, and it can be used to keep your
+// program compatible with GNU linkers after you switch to lld. I'll
+// explain the feature and why you may find it useful in this comment.
+//
+// lld's symbol resolution semantics is more relaxed than traditional Unix
+// linkers. For example,
+//
+//   ld.lld foo.a bar.o
+//
+// succeeds even if bar.o contains an undefined symbol that have to be
+// resolved by some object file in foo.a. Traditional Unix linkers don't
+// allow this kind of backward reference, as they visit each file only once
+// from left to right in the command line while resolving all undefined
+// symbols at the moment of visiting.
+//
+// In the above case, since there's no undefined symbol when a linker visits
+// foo.a, no files are pulled out from foo.a, and because the linker forgets
+// about foo.a after visiting, it can't resolve undefined symbols in bar.o
+// that could have been resolved otherwise.
+//
+// That lld accepts more relaxed form means that (besides it'd makes more
+// sense) you can accidentally write a command line or a build file that
+// works only with lld, even if you have a plan to distribute it to wider
+// users who may be using GNU linkers. With --check-library-dependency, you
+// can detect a library order that doesn't work with other Unix linkers.
+//
+// The option is also useful to detect cyclic dependencies between static
+// archives. Again, lld accepts
+//
+//   ld.lld foo.a bar.a
+//
+// even if foo.a and bar.a depend on each other. With
+// --check-library-dependency, it is handled as an error.
+//
+// Here is how the option works. We assign a group ID to each file. A file
+// with a smaller group ID can pull out object files from an archive file
+// with an equal or greater group ID. Otherwise, it is a reverse dependency
+// and an error.
+//
+// A file outside --{start,end}-group gets a fresh ID when instantiated. All
+// files within the same --{start,end}-group get the same group ID. E.g.
+//
+//   ld.lld A B --start-group C D --end-group E
+//
+// A and B form group 0. C, D and their member object files form group 1. E
+// forms group 2. I think that you can see how this group assignment rule
+// simulates the traditional linker's semantics.
+static void checkDependency(StringRef Name, InputFile *Old, InputFile *New) {
+  if (Config->CheckLibraryDependency && Old && New->GroupId < Old->GroupId)
+    warn("bad backward reference detected: " + Name + " in " + toString(Old) +
+         " depends on " + toString(New));
+}
+
 template <class ELFT>
 Symbol *SymbolTable::addUndefined(StringRef Name, uint8_t Binding,
                                   uint8_t StOther, uint8_t Type,
                                   bool CanOmitFromDynSym, InputFile *File) {
   Symbol *S;
   bool WasInserted;
   uint8_t Visibility = getVisibility(StOther);
   std::tie(S, WasInserted) =
Symbol *SymbolTable::addUndefined(StringRef Name, uint8_t Binding,
 
   if (!Config->GcSections && Binding != STB_WEAK)
     if (auto *SS = dyn_cast<SharedSymbol>(S))
       SS->getFile<ELFT>().IsNeeded = true;
 
   if (S->isLazy()) {
     // An undefined weak will not fetch archive members. See comment on Lazy in
     // Symbols.h for the details.
-    if (Binding == STB_WEAK)
+    if (Binding == STB_WEAK) {
       S->Type = Type;
-    else
-      fetchLazy<ELFT>(S);
+      return S;
+    }
+
+    checkDependency(Name, File, S->File);
   }
   return S;
 }
 
 // Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
 // foo@@VER. We want to effectively ignore foo, so give precedence to
 // foo@@VER.
 // FIXME: If users can transition to using
void SymbolTable::addLazyArchive(StringRef Name, ArchiveFile &F,
 
   // An undefined weak will not fetch archive members. See comment on Lazy in
   // Symbols.h for the details.
   if (S->isWeak()) {
     replaceSymbol<LazyArchive>(S, F, Sym, S->Type);
     S->Binding = STB_WEAK;
     return;
   }
+
+  checkDependency(Name, S->File, &F);
   if (InputFile *File = F.fetch(Sym))
     addFile<ELFT>(File);
 }
 
 template <class ELFT>
 void SymbolTable::addLazyObject(StringRef Name, LazyObjFile &Obj) {
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) = insert(Name);
   if (WasInserted) {
     replaceSymbol<LazyObject>(S, Obj, Name, Symbol::UnknownType);
     return;
   }
   if (!S->isUndefined())
     return;
 
   // See comment for addLazyArchive above.
   if (S->isWeak()) {
     replaceSymbol<LazyObject>(S, Obj, Name, S->Type);
     S->Binding = STB_WEAK;
     return;
   }
-  if (InputFile *F = Obj.fetch())
-    addFile<ELFT>(F);
+
+  checkDependency(Name, S->File, &Obj);
+  if (InputFile *File = Obj.fetch())
+    addFile<ELFT>(File);
 }
 
 template <class ELFT> void SymbolTable::fetchLazy(Symbol *Sym) {
   if (auto *S = dyn_cast<LazyArchive>(Sym)) {
     if (InputFile *File = S->fetch())
       addFile<ELFT>(File);
     return;
   }

lld/test/ELF/check-library-dependency.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+# RUN: echo ".globl foo; foo:" | llvm-mc -filetype=obj -triple=x86_64-unknown-linux - -o %t2.o
+# RUN: rm -f %t2.a
+# RUN: llvm-ar rcs %t2.a %t2.o
+
+# RUN: ld.lld --fatal-warnings -o %t.exe %t1.o %t2.a
+# RUN: ld.lld --fatal-warnings -o %t.exe %t2.a %t1.o
+# RUN: ld.lld --fatal-warnings --check-library-dependency -o %t.exe %t1.o %t2.a
+# RUN: ld.lld --fatal-warnings --check-library-dependency -o %t.exe %t1.o --start-lib %t2.o --end-lib
+
+# RUN: ld.lld --fatal-warnings --check-library-dependency -o %t.exe --start-group %t2.a %t1.o --end-group
+# RUN: ld.lld --fatal-warnings --check-library-dependency -o %t.exe "-(" %t2.a %t1.o "-)"
+# RUN: ld.lld --fatal-warnings --check-library-dependency -o %t.exe "-(" "-(" %t2.a "-)" %t1.o "-)"
+
+# RUN: echo "INPUT(\"%t1.o\" \"%t2.a\")" > %t1.script
+# RUN: ld.lld --fatal-warnings --check-library-dependency -o %t.exe %t1.script
+
+# RUN: echo "GROUP(\"%t2.a\" \"%t1.o\")" > %t2.script
+# RUN: ld.lld --fatal-warnings --check-library-dependency -o %t.exe %t2.script
+
+# RUN: not ld.lld --fatal-warnings --check-library-dependency -o %t.exe %t2.a %t1.o 2>&1 | FileCheck %s
+# RUN: not ld.lld --fatal-warnings --check-library-dependency -o %t.exe %t2.a "-(" %t1.o "-)" 2>&1 | FileCheck %s
+
+# CHECK: bad backward reference detected: foo in {{.*}}1.o depends on {{.*}}2.a
+
+# RUN: not ld.lld --fatal-warnings --end-group 2>&1 | FileCheck -check-prefix=ENDGROUP %s
+# ENDGROUP: stray --end-group
+
+.globl _start, foo
+_start:
+  call foo