(Possibly buggy?) doFinalization method behavior of FunctionPass

Project Infrastructure LLVM Dev List Archives
1

Hello there,

I’m writing some LLVM passes, and just ran into an interesting situation: now, I don’t know if I misunderstood the way doFinalization is supposed to work, but I hope someone could help =)

One of the transformations I wrote needed to replace some instructions within the code, so I needed to clean up the code after the process was completed. The pass basically swapped some function calls (from the standard C library) with my own implementation of those functions. Changing the code in this way, though, creates some dead code (like those dead prototypes that are not being used anymore).

I, then, implemented the “clean up” strategy overriding doFinalization. Unfortunately, any modifications done to the module in this method appears to be ignored by LLVM. I even dumped the module directly from within the method, and could see that the modifications were applied to that reference of the module, but the .bc file opt wrote into does not retain these changes.

Now, bear with me here: I know that other passes like DCE could be used to clean the bytecode, but some of the code I implemented in doFinalization actually needed to run only once, and necessarily after the pass has finished: this is where I check to see if there is some extra situation I need to address, optimize some of the replaced instructions, and verify if any of the functions that I want to remove had their addresses taken by any instruction.

Also, doFinalization has a bool return type, but it doesn’t appear to have any different behavior if I return either value =/ (I assumed the general idea would be “return true if the module was modified in any way”, like runOnFunction, but I couldn’t find anything to support that anywhere).

Thus, am I wrong about how to use doFinalization? If so, is there any way to guarantee running some code only once and only when a pass already finished its job?

Thanks in advance,

Oh, and before I forget, this is the version of the opt I’m running:

LLVM (http://llvm.org/):
LLVM version 3.7.0svn
DEBUG build with assertions.
Built May 4 2015 (00:18:21).
Default target: x86_64-apple-darwin14.3.0
Host CPU: sandybridge

2

Dear Cristianno,

Have you verified that some other pass is not adding the function declarations back in after your pass is executed (e.g., by using the -debug-pass=Executions argument to see what passes run after your pass)?

Also, does your doFinalization() method make other changes that are persistent?

Regards,

John Criswell

3

Hello Cristiano,

I don’t think doFinalization() is really meant to be used this way.

Its purpose is to allow clean-up of internal data-structures used by the pass itself, not to make additional changes to the module.

One option would be to rewrite your pass as a ModulePass instead of a FunctionPass, then iterating over the functions manually, and doing the final clean-up once that’s done.

Michael

4

My understanding is that doInitialization() and doFinalization() are designed specifically for modifying the LLVM IR (otherwise, why would a mutable reference to the Function be provided)? If that is not the case, then there is either a bug in the code or a bug in the documentation. That said, I agree with the suggestion of writing a ModulePass. Since the PassManager does not run FunctionPasses in parallel yet, there’s little benefit to using them. I have often found the limitations on FunctionPasses to not be worth the hassle. Regards, John Criswell

5

I’ve always thought that the only guarantee is that doFinalization(Module &M) runs after runOnFunction() was executed for all functions in M, and there’s no guarantee it runs immediately after.

That is, a PM may run a bunch of function passes over each function, and only then call doFinazliation() for each pass. That means that, even though you get a mutable reference to the module, the module you’ll see is quite different from what you may expect.

People more familiar with the pass managers – please correct me if I’m wrong.

Michael

6

Correct. You’re guaranteed that doFinalization() is run after your pass has been executed over all the functions. There’s no guarantees about what other passes are going to do either before or after doFinalization() is called. Therefore, it’s fine for doFinalization() to modify the Module. You just have to be aware that other passes may change the Module later. That’s why I asked whether there are any other passes executed after Cristianno’s pass: they can (theoretically) add the function declarations back into the Module. Regards, John Criswell

7

Hello again,

First of all, thanks for all the answers =) they really helped a lot =D

Have you verified that some other pass is not adding the function declarations back in after your pass is executed (e.g., by using the -debug-pass=Executions argument to see what passes run after your pass)?

I considered that for a moment, but I realized that wouldn’t be possible for two reasons: I specifically ran my pass with opt level zero; and one of the tasks I was doing was removing unused prototypes from the Module – so, why would any other doFinalization pass reintroduce those prototypes if those functions were not being invoked anywhere? (PS: since this clean-up happened inside my doFinalization, I’m assuming only other doFinalization would be able to change the module after this point)

Also, does your doFinalization() method make other changes that are persistent?

The main reason why I chose to use doFinalization was to check if any of the functions I’m replacing still had any uses: since my pass replaced every function call with my respective function calls, if any uses could still be listed, that meant that some instruction must be taking the address of that function, and I should treat those instructions at this point. At the end, since I was already checking for uses, I ended up removing the extra prototypes at this point, if they were still there.

I don’t think doFinalization() is really meant to be used this way.

Its purpose is to allow clean-up of internal data-structures used by the pass itself, not to make additional changes to the module.

Then, I have a question: why should doFinalization need a Module& as argument? I mean, since I shouldn’t be able to modify it, and all data structures I created to work my pass are known and (mostly) directly accessible from within doFinalization, its argument would never be useful, right?

One option would be to rewrite your pass as a ModulePass instead of a FunctionPass, then iterating over the functions manually, and doing the final clean-up once that’s done.

That said, I agree with the suggestion of writing a ModulePass. Since the PassManager does not run FunctionPasses in parallel yet, there’s little benefit to using them. I have often found the limitations on FunctionPasses to not be worth the hassle.

Well, I actually wouldn’t mind using a ModulePass to begin with, but unfortunately I had to rewrite my pass as a FunctionPass because part of the job it does involve accessing the DominatorTree – and, unfortunately, I couldn’t find a way to access it from inside a ModulePass. Even when I try to force a dependence between my module pass and DominatorTree, I can’t get it to work because (if I’m not mistaken) module passes are hard-coded to run before function passes =/

My understanding is that doInitialization() and doFinalization() are designed specifically for modifying the LLVM IR (otherwise, why would a mutable reference to the Function be provided)?

If that is not the case, then there is either a bug in the code or a bug in the documentation.

Exactly like I thought =)

I’ve always thought that the only guarantee is that doFinalization(Module &M) runs after runOnFunction() was executed for all functions in M, and there’s no guarantee it runs immediately after.

That is, a PM may run a bunch of function passes over each function, and only then call doFinazliation() for each pass. That means that, even though you get a mutable reference to the module, the module you’ll see is quite different from what you may expect.

People more familiar with the pass managers – please correct me if I’m wrong.

I don’t really mind at all if other passes run or even had their doFinalization passes running in any order in relation to mine: the point here is doFinalization is running (I know that because module.dump() is being called from inside that function, and I can see the module containing the modifications I do during the execution of that method), but the final bc file (written by opt) does have the exactly same code that I get if I dumped module at the beginning of my doFinalization (and they have differences between them btw =)).

8

Btw, I forgot to add this piece of information: I ended up dividing the work of my pass into two parts – I created a module pass that had all the transformation instructions that didn’t have anything to do with dominance, and I kept the dominance-dependent code inside a function pass. Then, I just had to force a dependence between them (the function pass requiring the module one), and this way I could apply my transformations.

Anyways, I still think doFinalization is wrongly defined or, at least, implemented, as I tried to discuss on my previous email =)

Thanks a lot,

9

Only one little correction:

10

As the person whose use case motivated added them, we definitely didn’t intend them to be used for modifying IR.

—Owen

11

Dear Owen,

First, to be sure we're on the same page, are we talking about doFinalization() in a FunctionPass or the doFinalization() method of another type of pass? I've been assuming that we're talking about FunctionPasses.

Second, according to the documentation, FunctionPass::doInitialization() is allowed to modify the IR. The documentation on doFinalization() does not say anything either way on the matter.

It sounds like there's a bug in the documentation. Would you like me to file a bug report?

Regards,

John Criswell

12

Ah, actually, I was thinking of ModulePass::doFinalization. I’m not certain of the history of FunctionPass::doFinalization

—Owen

13

I think it’s wrongly documented. :slight_smile:

As a side note, I believe requiring transformation passes (as opposed to requiring analysis passes) is also not-quite-supported.

14

It’s not just a question of other passes changing the module between your runOnFunction()-s and your doFinalization().

In theory, you may also have something like code-generation (or something else with non-IR output) in the same PassManager as your pass. In this case, doFinalization() will run too late for it to matter. So leaving a module in a “half-baked” state until after doFinalization() runs seems ill-advised to me.

Michael

15

Hi again,

I think it’s wrongly documented. :slight_smile:

It could be, and I guess it probably is, but as I’m going to discuss below, it should be interesting to have some function that bears this documented doFinalization behavior =)

As a side note, I believe requiring transformation passes (as opposed to requiring analysis passes) is also not-quite-supported.

I didn’t know about that XD, and I think it makes sense (I don’t even have to call getAnalysis from inside my FunctionPass, since I don’t really mind at all about any data flowing from the ModulePass), but it apparently worked =/ I know I could just invoke both transformations from command line (just by adding a different cmd option to opt), but, idk, it sounded kind of weird having to write something like:

opt -load MyPasses.dylib -myPass -myPass_Extras <…>

since I always HAD TO have both being enabled together anyways.

16

Well, to be fair, the main idea of having FunctionPasses in the first place is that (please, correct me if I'm mistaken) opt could be running different passes on different functions at the same time, so the compilation process could be sped up. I know the parallel part of this is not yet implemented on LLVM, but I think I can assume that my pass is going to work on a function, and other passes will work over the same function after mine, even before my pass can start again its work over the next function. In a way, doesn't it mean that my pass keeps "half-baking" its work one function at a time until it finishes all of them for a given module?

As long as the pass’s modifications for each function don’t depend on modifications made to another function, that function is “fully-baked”. :slight_smile:
And if these modifications do depend on what you do to another function, then I’d suggest the pass should be a ModulePass.

This is actually why I think doFinalization should have a different perspective between Module and "TheRestOfThe"-Passes: given that a module is the basic unit of compilation for opt, doFinalization is going to be called as many times as runOnModule for every module you try to transform/analyze on a ModulePass. This is not true for FunctionPass, for example: if I have to do some work only once, and preferably after finishing with all functions, I would have to insert some if clause into my runOnFunction that checks a counter of functions and would effectively run only if I already ran NumberOfFunctionsWithoutConsideringDefinitions times -- which is hardly a good programming method. Besides, if what I assumed above is really true (that there is no guarantee that your FunctionPass finishes with the module before other FunctionPasses run over some of the functions), even this strategy is worthless: the code could be changed by other passes between the first and last execution of my pass runOnFunction =/

That’s exactly my point – if you have to do some work only once, and that work has module-wide impact (as opposed to function-wide), then I believe you ought to be using a ModulePass. Yes, this imposes a constraint on scheduling that’s probably stronger than you want, but I don’t think there’s a way to express “run my pass over functions in parallel (in theory), then run another part of it over the module, but make sure nothing bad happens in between”.

a. AsmPrinter: a MachineFunctionPass who's doFinalization is defined at line 1004 of lib/CodeGen/AsmPrinter.cpp
b. Inliner: a CallGraphSCCPass, having doFinalization defined at lib/Transforms/IPO/Inliner.cpp:621
c. BBPassManager: a FunctionPass, at lib/IR/LegacyPassManager.cpp:1344
d. FunctionPassManager: a Pass, at lib/IR/LegacyPassManager.cpp:1441

(a) is not an IR-to-IR pass. It only reads the module to generate output, it doesn’t actually write to the module.
(c) and (d) are part of the PassManager infrastructure, and can make assumptions about ordering that a regular pass shouldn’t. And, in any case, the only thing they seem to do with the module/function they get is to pass it on to the doFinalization() methods of their contained passes.
(b) seems to be the only real example of this in-tree, and it’s insanely old code by LLVM standards (written by Chris in 2004). So, perhaps, originally this is the way it was meant to work. But I’m fairly certain this is not a preferred practice today.
Again, I’d really appreciate it if anyone with more in-depth knowledge of the infrastructure could comment.

On the other hand, assuming the documentation is actually wrong, and doFinalization shouldn't be allowed to change the module, I still couldn't see why exactly doFinalization functions have a Module& as argument (at least the FunctionPass one), or a boolean return type for that matter; in other words, I would guess the signature of this function is wrongly defined anyways.

cheers,