Trouble with rewriting MaximumSpanningTree as template.

Hi,

since the MaximumSpanningTree-Algorithm is useful in may ways it would
be great to have this available as generic algorithm.
(See
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20090824/085454.html)

Problem is: I can't get it to work. The attached patch (which depends on
lib/Transforms/Instrumentation/MaximumSpanningTree.* being removed
before application) does not compile with

$> .../lib/Transforms/Instrumentation/MaximumSpanningTree.cpp:38: error:
'stable_sort' is not a member of 'std'

which I find kind of curious since std::stable_sort didn't make a
problem in the specific implementation.

This problem aside I get the error

$> llvm[2]: Linking Debug executable opt
$>
.../llvm-svn-debug-obj/Debug/lib/libLLVMInstrumentation.a(OptimalEdgeProfiling.o):
In function `(anonymous
namespace)::OptimalEdgeProfiler::runOnModule(llvm::Module&)':
$>
.../llvm/llvm-svn/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp:135:
undefined reference to `llvm::MaximumSpanningTree<llvm::BasicBlock
const*>::MaximumSpanningTree(std::vector<std::pair<std::pair<llvm::BasicBlock
const*, llvm::BasicBlock const*>, double>,
std::allocator<std::pair<std::pair<llvm::BasicBlock const*,
llvm::BasicBlock const*>, double> > >&)'
$> collect2: ld returned 1 exit status

when linking this stuff together.

Any hints?

Andi

llvm-r80913.maxspanntree.as.template.patch (5.13 KB)

Andreas Neustifter wrote:

$> .../lib/Transforms/Instrumentation/MaximumSpanningTree.cpp:38: error:
'stable_sort' is not a member of 'std'

which I find kind of curious since std::stable_sort didn't make a
problem in the specific implementation.
  

I don't see anything that definitely pulls <algorithm> in, so it may be
a case of one implementation happening to do it, and the other not.

This problem aside I get the error

$> llvm[2]: Linking Debug executable opt
$>
.../llvm-svn-debug-obj/Debug/lib/libLLVMInstrumentation.a(OptimalEdgeProfiling.o):
In function `(anonymous
namespace)::OptimalEdgeProfiler::runOnModule(llvm::Module&)':
$>
.../llvm/llvm-svn/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp:135:
undefined reference to `llvm::MaximumSpanningTree<llvm::BasicBlock
const*>::MaximumSpanningTree(std::vector<std::pair<std::pair<llvm::BasicBlock
const*, llvm::BasicBlock const*>, double>,
std::allocator<std::pair<std::pair<llvm::BasicBlock const*,
llvm::BasicBlock const*>, double> > >&)'
$> collect2: ld returned 1 exit status

when linking this stuff together.
  

You can't define templates in .cpp files; they must be available for
instantiation in each source file.

Sebastian

Thanks a lot, that did the trick!

Andi

Sebastian Redl wrote: