Sparse propagation framework

Project Infrastructure LLVM Dev List Archives
1

Hi All,

I’m relatively new to LLVM (but not optimizing compilers), and have been reading docs and browsing code.

I noticed in the 2.4 release notes that a sparse propagation framework had been added based on the SCCP algorithm. I might have a need for exactly this kind of framework in order to prototype an analysis I have in mind.

I also noticed, however, that this doesn’t appear to be in use at this time.

Are there plans to reimplement SCCP and/or other analyses/optimizations using this framework? Is the framework known to generally work? I searched the bug database but didn’t find anything that looked related.

Thanks,

Mark

2

Hi All,

Hi Mark,

I'm relatively new to LLVM (but not optimizing compilers), and have been
reading docs and browsing code.

Bienvenue!

I noticed in the 2.4 release notes that a sparse propagation framework had
been added based on the SCCP algorithm. I might have a need for exactly this
kind of framework in order to prototype an analysis I have in mind.

I also noticed, however, that this doesn't appear to be in use at this time.

It is being used:

opt.cpp:

void AddStandardCompilePasses(PassManager &PM) {
...
  addPass(PM, createSCCPPass()); // Constant prop with
SCCP

and in gcc/llvm-backend.cpp:

static void createPerModuleOptimizationPasses() {
...
      PM->add(createSCCPPass()); // Constant prop
with SCCP

-bw

3

He's not asking about the SCCP pass, but rather
llvm/Analysis/SparsePropagation.h, which is in fact unused at the
moment.

-Eli

4

The sparse solver is indeed being actively used and maintained.

John.

5

I guess I wasn’t clear. I was referring to the code in
include/llvm/Analysis/SparsePropagation.h
and
lib/Analysis/SparsePropagation.cpp
which use the same optimistic worklist based algorithm that SCCP uses, but allow for pluggable lattices/transfer-functions via subclassing the AbstractLatticeFunction class.

It looks like this was written to be a more general framework that worklist based algorithms (esp. ones that have a notion of executable edges) could be built on, but was never used within LLVM.

Mark

6

Hi Mark,

It is actively being used by out of tree code. I don't know of any plans to change SCCP, or any reason to do so, but it could be done in principle.

-Chris