Differential D25095
[Polly] Ignore removed memory access. NFC. Authored by Meinersbur on Sep 30 2016, 8:10 AM.
Details
The DeLICM (and Known) pass will remove redundant explicit memory accesses. This patch prepares the code generator to ignore such removed access. The code currently has no effect because there is no pass except Invariant Load Hoisting yet that removes accesses. The hoisted loads are skipped because their value is already found in GlobalMap. Opening for review since Tobias mentioned concerns about generateArrayLoad returning Undef.
Diff Detail Event TimelineComment Actions Hi Michael, I am worried about a situation where we have sth like: %val = load %A If we drop the div, we might trigger undefined behavior. To my understanding this can never happen, as you will only drop direct copy sequences, right? I am probably too careful here, but if you could quickly check (assert) that the only use of %val is in a store instruction, my worries would disappear. Also, if you commit this separately, which certainly would not hurt, a JSON test case would be amazing. Best, Comment Actions Did you mean "drop the load"? This patch does not influence non-access instruction handling.
The correctness of removing a memory access is a concern of the the code that removes them. At codegen-time it is very difficult or even impossible to retroactively check whether a removal was correct. There is no exhaustive list of reasons why it could be removed. The detection mechanism you mentioned is neither sufficient nor mandatory even for just DeLICM. It is invalid if the store, which could also be an implicit store, is not also removed. Uses can also be in other statements that get their llvm::Value from a scalar load, but have no effect on the removal of such a load. Also consider that not generating a store is just as harmful for the generated code as replacing a load by an Undef. The missing store would be even harder to find.
The json importer currently does not support removing MemoryAccesses. Implementing that will require much more code and certainly also its own review. Comment Actions Another patch would introduce ScopInfo::removeSingleMemoryAccess(MemoryAccess*). FWIW I could bundle that patch, this patch, and json importer support for removing accesses. Comment Actions Adding Roman who might have an opinion here as well. Right.
I understand that in the end passes such as DeLICM need to decide what is save to do and what not. Let me just write down some related, but unfinished thoughts I have, that may give some context of what I am thinking about and where I believe there are possibilities to improve the current design of Polly. I have been thinking for a while, if we really want to remove loads and stores from the polyhedral representation and to which extend we want to do this. I generally have the feeling that removing memory accesses by dropping the full polly::MemoryAccess is not what we actually want, as it results in an inconsistency between the IR and the polyhedral model. We already discussed this earlier, when we concluded that the MemoryAccess is currently holding two kinds of information. The information about the original access and the information about how we transform the memory access. If we drop the full memory access structure we loose the information about the original memory access. Obviously, there is precedence with Johannes' load hoisting, which introduced this behavior, but I hope we can improve this design in the future by making the separation between new and original memory access behavior more clear I see different ways to improve this situation. I could e.g. see the load hoisting being expressed by modifying the access functions similar to how we do this today in Roman's and your work. We also have since a long time on the Polly todo list the introduction of ScopStmts that are defined on instruction trees, rather than basic blocks. As part of this, I could imaging that we automatically detect pure 'copy-only' statements and match them to the Copy_Stmt Roman recently introduced. Assuming this direction is where we want to go (and this probably needs more discussion -- maybe next phone call?), I was wondering where DeLICM fits in here. If DeLICM for example only removes copy statements maybe we could in the future avoid the removal of memory accesses in DeLICM and instead remove full copy statements. Now going back to this actual patch. I don't think it is necessary to today go full speed on these design changes, but am OK to continue removing full polly::MemoryAccesses for a while. Still, I think to make future changes easier it would be great if we could limit the generality of such changes to what is needed for DeLICM today. As said earlier, I understand that we cannot validate DeLICM retrospectively. But maybe we can check what kind of load/store memory accesses we allow to be removed. I went back to learn which memory accesses DeLICM removes today and it seems
I suggested this as a way to obtain test coverage for this patch without the need for delicm yet. I would hope that JSON is easy to extend (e.g. just mark a memory access as 'deleted'). Another option would be to commit this change together with the delicm cleanup() routine after DELICM. We can then run delicm to test the codegen change and it also becomes more clear what Best, Comment Actions the cleanup() currently implemented in DeLICM does the base minimum: Remove stores to array that a not necessary, but would impact the freedom of the scheduler. Removing loads as well would require something like a reference counter for loads (or just looking for remaining valid uses), which I might still implement. I think there were also situations were stores that are dead a left over, but I can't recall details at the moment. These are concerns of DeLICM, and I would be uncomfortable with adding these details to an unrelated pass such as CodeGen. If the load is not dropped, it might read an location that has never been written to because all writes to it have been redirected, ie. and Undef value. Without the check added in this patch whether the loads has been dropped, it would probably crash because it required details from an deleted MemoryAccess. If there is a compute instruction in between in the same statement, then nothing should be removed in the first place.
Committing with DeLICM would be fine with me, but doesn't solve the question of returning undef. Do implicitly suggest to commit cleanup() separately from the main part? Michael Comment Actions OK. So it seems today (and in the immediate future) DeLICM will only drop stores, but loads are left untouched. Is this right?
Does this not mean that load memory accesses will never be removed by DeLICM and that consequently the "if (!Stmt.getArrayAccessOrNULLFor(Load))" is never false, due to DeLICM? If I add an assert before the "createUNDEF" none of the current DeLICM test cases fails, except the ones that already fail due to the missing "known" pass. It seems as if this code currently is not needed. If this is the case, maybe we should postpone this discussion until we actually decide to remove loads in DeLICM?
Yes. The cleanup routine is certainly an independent change that would make sense to split off. I personally prefer small changes similar to how Sven is looking for patch sets that are split up in independent changes. Optimally changes of commonly around 30-50 lines, with around 200 lines max. I understand that this takes additional work to split up patches, but in my experience it saves a lot of time in discussions. Obviously, if I am open to discuss different strategies to upstream such large patches. (In general I prefer to avoid to build up such large patches in the first place, as working with them always adds a lot of overhead). Comment Actions Thinking about this change, we could possibly also commit a minimal DeLICM pass which only runs cleanup(). In some way, this is also a trivial change, which could even be tested on an appropriately designed .ll input file. It would allow us to get all the basic infrastructure in place. |