The "scope" of passes

Hongbin_Zheng · April 10, 2010, 7:43am

hi all,

i have some thing not so sure about “scope” of llvm passes:

suppose i have a function pass PassF and a BasicBlock analysis pass PassB. if i want to use the analysis result of PassB for a BasicBlock in PassF, i think i can create PassB in runOnFunction of PassF, and call runOnBasicBlock manually to get the result:

PassB pb; //create a PassB
//we also need consider the analysis usage of PassB
pb.runOnBasicBlock(bb); // run PassB on bb manually
… use the result of pb …

is there any other better way?

thanks very much
–ether

John_Criswell2 · April 12, 2010, 2:03pm

ether zhhb wrote:

hi all,

i have some thing not so sure about "scope" of llvm passes:

suppose i have a function pass PassF and a BasicBlock analysis pass PassB. if i want to use the analysis result of PassB for a BasicBlock in PassF, i think i can create PassB in runOnFunction of PassF, and call runOnBasicBlock manually to get the result:

PassB pb; //create a PassB
//we also need consider the analysis usage of PassB
pb.runOnBasicBlock(bb); // run PassB on bb manually
.... use the result of pb ......

is there any other better way?

I think the correct way to do this is to declare PassB as a prerequisite pass in PassF's getAnalysisUsage() method and then to use getAnalysis<PassB>(BasicBlock * BB) in PassF.

A ModulePass can use a FunctionPass, so I assume a FunctionPass can use a BasicBlockPass in this fashion.

-- John T.

Hongbin_Zheng · April 13, 2010, 1:41am

hi again

hi john,

thanks very much, i will try it out.

–best regards
ether

ether zhhb wrote:

hi all,

i have some thing not so sure about “scope” of llvm passes:

suppose i have a function pass PassF and a BasicBlock analysis pass PassB. if i want to use the analysis result of PassB for a BasicBlock in PassF, i think i can create PassB in runOnFunction of PassF, and call runOnBasicBlock manually to get the result:

PassB pb; //create a PassB
//we also need consider the analysis usage of PassB
pb.runOnBasicBlock(bb); // run PassB on bb manually
… use the result of pb …

is there any other better way?

I think the correct way to do this is to declare PassB as a prerequisite pass in PassF’s getAnalysisUsage() method and then to use getAnalysis(BasicBlock * BB) in PassF.

A ModulePass can use a FunctionPass, so I assume a FunctionPass can use a BasicBlockPass in this fashion.

that’s because FunctionPass implement the “addLowerLevelRequiredPass” function, but others not.

so, is there any special reason that only “addLowerLevelRequiredPass” is allow?

– John T.

–best regards
ether

Devang_Patel · April 13, 2010, 6:16am

There is no reason to not allow it. It is not done because there was
not any use. If you need this then pl. prepare a patch!

Hongbin_Zheng · April 13, 2010, 6:37am

yes i will

John_Criswell2 · April 13, 2010, 2:38pm

Devang Patel wrote:

that's because FunctionPass implement the "addLowerLevelRequiredPass"
function, but others not.

so, is there any special reason that only "addLowerLevelRequiredPass" is
allow?

There is no reason to not allow it. It is not done because there was
not any use. If you need this then pl. prepare a patch!

Alternatively, if you wrote the BasicBlock analysis pass, you could easily modify it to be a FunctionPass.

Currently, I think this is a better alternative because:

1) It doesn't require patching LLVM (meaning that your passes can work with LLVM 2.7)
2) You will get better reusability of the analysis results. When a higher level pass calls a lower level pass (e.g., ModulePass calls FunctionPass), the lower level pass is run again, even if it was run previously and did not have its analysis results invalidated. If the passes are of the same level (e.g., FunctionPass requires FunctionPass), then the PassManager can avoid duplicate runs of the analysis pass if its results are not invalidated.

-- John T.

Hongbin_Zheng · April 17, 2010, 1:57pm

hi John,

sorry for reply so late.

Devang Patel wrote:

that’s because FunctionPass implement the “addLowerLevelRequiredPass”
function, but others not.

so, is there any special reason that only “addLowerLevelRequiredPass” is
allow?

There is no reason to not allow it. It is not done because there was
not any use. If you need this then pl. prepare a patch!

Alternatively, if you wrote the BasicBlock analysis pass, you could easily modify it to be a FunctionPass.

yep, if we just concerning use BB pass in Function pass, we can just change it into a Function pass. (In fact, i had do something like this before )

But the problem is, sometimes, the BB pass PassA use by some Function pass requires others BB pass for analysis result, so we had to rewrite all the passes required by PassA to Function pass, so that PassA can get the analysis

Currently, I think this is a better alternative because:

It doesn’t require patching LLVM (meaning that your passes can work with LLVM 2.7)

You will get better reusability of the analysis results. When a higher level pass calls a lower level pass (e.g., ModulePass calls FunctionPass), the lower level pass is run again, even if it was run previously and did not have its analysis results invalidated. If the passes are of the same level (e.g., FunctionPass requires FunctionPass), then the PassManager can avoid duplicate runs of the analysis pass if its results are not invalidated.

yep, this make sense.

– John T.

Devang

best regards
–ether

John_Criswell2 · April 19, 2010, 2:27pm

ether zhhb wrote:

hi John,

sorry for reply so late.

    Devang Patel wrote:

            that's because FunctionPass implement the
            "addLowerLevelRequiredPass"
            function, but others not.

            so, is there any special reason that only
            "addLowerLevelRequiredPass" is
            allow?

        There is no reason to not allow it. It is not done because
        there was
        not any use. If you need this then pl. prepare a patch!

    Alternatively, if you wrote the BasicBlock analysis pass, you
    could easily modify it to be a FunctionPass.

yep, if we just concerning use BB pass in Function pass, we can just change it into a Function pass. (In fact, i had do something like this before )

But the problem is, sometimes, the BB pass PassA use by some Function pass requires others BB pass for analysis result, so we had to rewrite all the passes required by PassA to Function pass, so that PassA can get the analysis

Yes, it's inconvenient, but you only have two options: either enhance the PassManager to allow a FunctionPass to use a BasicBlockPass, or modify all of your BasicBlockPass'es to be FunctionPass'es.

Personally, I would make everything a FunctionPass. When a lower level pass is requested by a higher level pass (e.g., ModulePass requests a FunctionPass), then the lower-level pass is re-run *even if it was executed previously and not invalidated.* So, in your case, if a FunctionPass requests the results of BasicBlockPass, that BasicBlockPass will be re-run, even if it was run previously and not invalidated.

Plus, you can always write a BasicBlockPass *and* a FunctionPass that reuse the same code. For example, you could structure your code this way:

classname::analyzeBasicBlock (BasicBlock & BB) {
...
}

BBClassName::runOnBasicBlock (BasicBlock & BB) {
analyzeBasicBlock (BB):
}

FuncClassName::runOnFunction (Function & F) {
    for each basic block in F {
       analyzeBasicBlock (BB)
    }
}

The you either use the BasicBlockPass or FunctionPass depending upon what your needs are.

-- John T.

Hongbin_Zheng · April 20, 2010, 2:35am

hi John,

ether zhhb wrote:

hi John,

sorry for reply so late.

Devang Patel wrote:

that’s because FunctionPass implement the
“addLowerLevelRequiredPass”
function, but others not.

so, is there any special reason that only
“addLowerLevelRequiredPass” is
allow?

There is no reason to not allow it. It is not done because
there was
not any use. If you need this then pl. prepare a patch!

Alternatively, if you wrote the BasicBlock analysis pass, you
could easily modify it to be a FunctionPass.

yep, if we just concerning use BB pass in Function pass, we can just change it into a Function pass. (In fact, i had do something like this before )

But the problem is, sometimes, the BB pass PassA use by some Function pass requires others BB pass for analysis result, so we had to rewrite all the passes required by PassA to Function pass, so that PassA can get the analysis

Yes, it’s inconvenient, but you only have two options: either enhance the PassManager to allow a FunctionPass to use a BasicBlockPass, or modify all of your BasicBlockPass’es to be FunctionPass’es.

Personally, I would make everything a FunctionPass. When a lower level pass is requested by a higher level pass (e.g., ModulePass requests a FunctionPass), then the lower-level pass is re-run even if it was executed previously and not invalidated. So, in your case, if a FunctionPass requests the results of BasicBlockPass, that BasicBlockPass will be re-run, even if it was run previously and not invalidated.

Maybe we could add some “results cache” to the llvm pass manager system, but this will make things too complex and will not give significant advantage to llvm, since the we almost do not need to run passes “out of scope”.

Plus, you can always write a BasicBlockPass and a FunctionPass that reuse the same code. For example, you could structure your code this way:

classname::analyzeBasicBlock (BasicBlock & BB) {
…
}

BBClassName::runOnBasicBlock (BasicBlock & BB) {
analyzeBasicBlock (BB):
}

FuncClassName::runOnFunction (Function & F) {
for each basic block in F {
analyzeBasicBlock (BB)
}
}

or

BBClassName::runOnBasicBlock (BasicBlock & BB) {
do something
}

FuncClassName::runOnFunction (Function & F) {
BBClassName bbPass;
for each basic block in F {
bbPass.clear();
bbPass.runOnBasicBlock (BB)
}
}

as i mention in the first mail

well, thanks very much for your suggestion about this.

–best regards
ether

Arjun · April 23, 2010, 6:50am

Personally, I would make everything a FunctionPass.

What if a FunctionPass requires the results of a LoopPass? Is there a way to get
all loops of a function without using LoopPass and LoopInfo?

Devang_Patel · April 23, 2010, 4:41pm

A LoopPass operates on loops. It updates/deletes loops. Its end result
is modified loops.
A FunctionPass operates on entire function.

LoopInfo is a FunctionPass that collect loops from a function. A
FunctionPass can certainly request another FunctionPass such as
LoopInfo.

Arjun · April 24, 2010, 6:09am

But is there a better way of getting the loops in a function than using LoopInfo? For some tasks it is necessary that we don’t process the same loop twice. Doing that with LoopInfo requires the use of a flag.

Hongbin_Zheng · April 25, 2010, 2:34am

hi,

But is there a better way of getting the loops in a function than using LoopInfo?

maybe you could try the scc_iterator.

For some tasks it is necessary that we don’t process the same loop twice.

a looppass will not process a loop twice if you do not reinsert it into the queue of loopmanager.

Devang_Patel · April 26, 2010, 5:03pm

LoopInfo finds loop in a function and provides interface to iterator
loops. LoopInfo does not process loops, it is not a pass. A function
pass can request LoopInfo pass and use loop info iterators to access
loops. See LoopInfo header file.