Circular dependencies

Reid added some nice inter-library dependency data to utils/llvm-config/LibDeps.txt.

There are three sets of circular dependencies between LLVM libraries. If you use any library from one of these sets, you may need to pull in the rest:

   LLVMCodeGen.o LLVMSelectionDAG.o libLLVMAnalysis.a libLLVMTarget.a
   libLLVMTransformUtils.a libLLVMipa.a

   LLVMSparcV9.o LLVMSparcV9InstrSched.o LLVMSparcV9ModuloSched.o
   LLVMSparcV9RegAlloc.o

   LLVMExecutionEngine.o LLVMInterpreter.o LLVMJIT.o

The first set is the most problematic: It includes four *.a files, which means that certain linkers will tend to get confused unless you repeat '-l' flags.

The odd entry here is libLLVMipa.a, which gets pulled in by something in libLLVMTransformUtils.a, but which doesn't often seem to be needed in practice.

The third set is also a bit surprising: You always need to link in an interpreter, even when you have a perfectly good JIT.

I hope this information amuses or informs someone. :slight_smile:

Cheers,
Eric

Hi Eric,

Its definitely amusing :slight_smile:

About the only thing I can suggest are:

1. Combine LLVMSparc*.o into one LLVMSparc.a. That work is already
happening with the new Sparc backend that is being developed. Should be
out in 1.7 (Chris?)

2. Combine the JIT/Interpreter/ExecutionEngine into one .a

I don't know enough about the codegen/target/analysis/ipa stuff to be
able to make any suggestions. Perhaps Chris can shed some light.

Reid.

About the only thing I can suggest are:

1. Combine LLVMSparc*.o into one LLVMSparc.a. That work is already
happening with the new Sparc backend that is being developed. Should be
out in 1.7 (Chris?)

I wouldn't worry about the SparcV9 backend for your project.

2. Combine the JIT/Interpreter/ExecutionEngine into one .a

I'd much rather change the code so that interpreter depends on EE and JIT depends on EE, but EE depends on neither of them.

This would allow people to link just the JIT or just the interpreter into their apps, instead of always having both or none.

I don't know enough about the codegen/target/analysis/ipa stuff to be
able to make any suggestions. Perhaps Chris can shed some light.

   LLVMCodeGen.o LLVMSelectionDAG.o libLLVMAnalysis.a libLLVMTarget.a
   libLLVMTransformUtils.a libLLVMipa.a

Codegen and SelectionDAG can be merged, either physically in the source base or treated as one thing in your code.

CodeGen should depend on Target, but not the other way around.
LLVMIPA should depend on LLVMAnalysis, but certainly nothing in the list should depend on LLVMIPA. If you knew what was pulling in IPA that would probably be an easy tie to sever.

Ideally, none of the above should depend on libLLVMTransformUtils.

-Chris

Reid.

Reid added some nice inter-library dependency data to utils/llvm-
config/LibDeps.txt.

There are three sets of circular dependencies between LLVM libraries.
If you use any library from one of these sets, you may need to pull
in the rest:

   LLVMCodeGen.o LLVMSelectionDAG.o libLLVMAnalysis.a libLLVMTarget.a
   libLLVMTransformUtils.a libLLVMipa.a

   LLVMSparcV9.o LLVMSparcV9InstrSched.o LLVMSparcV9ModuloSched.o
   LLVMSparcV9RegAlloc.o

   LLVMExecutionEngine.o LLVMInterpreter.o LLVMJIT.o

The first set is the most problematic: It includes four *.a files,
which means that certain linkers will tend to get confused unless you
repeat '-l' flags.

The odd entry here is libLLVMipa.a, which gets pulled in by something
in libLLVMTransformUtils.a, but which doesn't often seem to be needed
in practice.

The third set is also a bit surprising: You always need to link in an
interpreter, even when you have a perfectly good JIT.

I hope this information amuses or informs someone. :slight_smile:

Cheers,
Eric

_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-Chris

Here's the raw data on who's pulling what into that cycle:

LLVMCodeGen.o: libLLVMAnalysis.a libLLVMSupport.a libLLVMTarget.a LLVMCore.o

LLVMSelectionDAG.o: libLLVMSupport.a libLLVMSystem.a libLLVMTarget.a libLLVMTransformUtils.a LLVMCodeGen.o LLVMCore.o

libLLVMAnalysis.a: libLLVMSupport.a libLLVMTarget.a LLVMCore.o

libLLVMTarget.a: libLLVMSupport.a LLVMCodeGen.o LLVMCore.o LLVMSelectionDAG.o

libLLVMTransformUtils.a: libLLVMAnalysis.a libLLVMipa.a libLLVMSupport.a LLVMCore.o

libLLVMipa.a: libLLVMAnalysis.a libLLVMSupport.a LLVMCore.o

It looks as if libLLVMipa.a is pulled in by libLLVMTransformUtils.a, which is in turn pulled in by LLVMSelectionDAG.o. Do either of those links seem remotely plausible?

Somebody who can run GenLibDeps.txt (I can't) could narrow it down further.

Cheers,
Eric

2. Combine the JIT/Interpreter/ExecutionEngine into one .a

I'd much rather change the code so that interpreter depends on EE and JIT depends on EE, but EE depends on neither of them.

This would allow people to link just the JIT or just the interpreter into their apps, instead of always having both or none.

FWIW, this is now in CVS.

I don't know enough about the codegen/target/analysis/ipa stuff to be
able to make any suggestions. Perhaps Chris can shed some light.

   LLVMCodeGen.o LLVMSelectionDAG.o libLLVMAnalysis.a libLLVMTarget.a
   libLLVMTransformUtils.a libLLVMipa.a

LLVMIPA should depend on LLVMAnalysis, but certainly nothing in the list should depend on LLVMIPA. If you knew what was pulling in IPA that would probably be an easy tie to sever.

To diagnose and fix this, I need to know the specific symbol in libipa that is getting referenced. Reid, since you have the magical ability to run the script, can you look into it?

-Chris

Yeah, I'm definitely having headaches with LLVMTransformUtils, which needs to appear before LLVMAnalysis and lLLVMTarget.

   -lLLVMTransformUtils -lLLVMAnalysis -lLLVMTarget

If I don't do this, I get link errors on:

   __ZN4llvm11BasicAAStubEv

I think, for now, the only portable workaround is for me to link all the *.a libraries in that loop twice, and hope we can clean up the dependencies later.

There's several places where llvm-config could be simplified quite a bit if we broke the unnecessary dependencies and merged the remaining loops into single *.a files. In some sense, parts of llvm-config are re-inventing the system linker. Depending on your point of view, this might be a bad thing. :slight_smile:

Many thanks to everyone who's helped sort this out!

Cheers,
Eric

Yes. I'll get to it sometime today.

Okay, the problem with this cycle is LoopSimplify. It is using
AliasAnalysis which is where that _ZN4llvm11BasicAAStubEv symbol is
coming from. It seems to me that LoopSimplify.cpp is in the wrong
place. This file defines the LoopSimplify FunctionPass which doesn't
seem to me to be a "transform util". I thought the purpose of
"Transforms/Util" was to provide utilities that are common amongst
transforms. But, LoopSimplyf *is* a transform. So, I think the solution
is to move LoopSimplify.cpp out of Transforms/Utils to somewhere else,
say just "Transforms. By doing this, we probably eliminate the cycle.
I'm going to validate that shortly.

Reid.

Okay, its not that simple.

Several files in Transforms/Utils depend on things in lib/Analysis. A
quick grep shows:

BreakCriticalEdges.cpp:#include "llvm/Analysis/Dominators.h"
BreakCriticalEdges.cpp:#include "llvm/Analysis/LoopInfo.h"
CloneTrace.cpp:#include "llvm/Analysis/Trace.h"
CodeExtractor.cpp:#include "llvm/Analysis/Dominators.h"
CodeExtractor.cpp:#include "llvm/Analysis/LoopInfo.h"
CodeExtractor.cpp:#include "llvm/Analysis/Verifier.h"
InlineFunction.cpp:#include "llvm/Analysis/CallGraph.h"
Local.cpp:#include "llvm/Analysis/ConstantFolding.h"
PromoteMemoryToRegister.cpp:#include "llvm/Analysis/Dominators.h"
PromoteMemoryToRegister.cpp:#include "llvm/Analysis/AliasSetTracker.h"

Am I right in assuming that the goal here is to get libTransformUtils to
depend on nothing in libTransforms or libAnalysis? If so, its going to
take some significant code rearrangement.

Perhaps a lib/Analysis/Utils is in order?

Please advise.

Reid.

Am I right in assuming that the goal here is to get libTransformUtils to
depend on nothing in libTransforms or libAnalysis? If so, its going to
take some significant code rearrangement.

Perhaps a lib/Analysis/Utils is in order?

I think it's ok for TransformUtils to depend on Analysis. Having xformations depend on analyses is ok, we just don't want the opposite.

-Chris