This is an archive of the discontinued LLVM Phabricator instance.

[Polly] Remove dependency of `Scop::getStmtFor(Inst)` on `getStmtFor(BB)`. [NFC].
ClosedPublic

Authored by nandini12396 on Jul 20 2017, 12:55 AM.

Details

Summary

We are working towards removing uses of Scop::getStmtFor(BB). In this patch, we remove dependency of Scop::getStmtFor(Inst) on getStmtFor(BB). To do so, we introduce a map of instructions to their corresponding scop statements and use it to get the instructions' statement.

Diff Detail

Repository
rL LLVM

Event Timeline

nandini12396 created this revision.Jul 20 2017, 12:55 AM
Meinersbur edited edge metadata.Jul 20 2017, 5:51 AM

This is good, just the additional assertion would be nice.

lib/Analysis/ScopInfo.cpp
4759 ↗(On Diff #107456)

[Suggestion] Could you add an assertion here that checks that the instruction is not yet mapped to something else?

4769 ↗(On Diff #107456)

Here too.

Addressed comments.

Meinersbur added inline comments.Jul 20 2017, 1:14 PM
lib/Analysis/ScopInfo.cpp
4829–4830 ↗(On Diff #107525)

[Serious] InstStmtMap[&Inst] modifies the map inside an assert statement. Such side-effects may cause Polly to behave differently in debug than in release builds. While currently the element is added anyway, some future change may add the element only under some condition and forget this assert that still adds it. It is good practice to avoid side-effects in asserts in the first place.

Please use InstStmtMap.count(&Inst) instead.

Meinersbur added inline comments.Jul 21 2017, 6:01 AM
lib/Analysis/ScopInfo.cpp
5003–5006 ↗(On Diff #107525)

I think

return InstStmtMap.lookup(Inst);

does exactly the same.

Meinersbur added inline comments.Jul 21 2017, 6:20 AM
lib/Analysis/ScopInfo.cpp
4828 ↗(On Diff #107525)

To fix the fx_basic_util_crash.ll case, only map the instructions that are actually in the statement (The Instructions vector).

However, this causes 31 other tests to break, particularly on assert(Parent.getStmtFor(AccessVal) == this). That assertion can be removed, it is suficient if the value is syntesizable in the statement.

Then there are still 3 other failing tests remaining.

nandini12396 marked 2 inline comments as done.Jul 25 2017, 5:32 AM
nandini12396 added inline comments.
lib/Analysis/ScopInfo.cpp
4829–4830 ↗(On Diff #107525)

Sure.

5003–5006 ↗(On Diff #107525)

Done. Thank you.

nandini12396 marked 2 inline comments as done.Jul 25 2017, 6:01 AM
nandini12396 added inline comments.
lib/Analysis/ScopInfo.cpp
4828 ↗(On Diff #107525)

yes, I had earlier inserted only the instructions of the Instructions vector into the Map. But I reverted because I didnt understand how can this be a non-functional change?
Apart from that assertion for me, only 2 other tests fail on !Inst->mayReadOrWriteMemory(). Im thinking why so..
And Im also thinking why this should fix the fx_basic_util_crash.ll case.

nandini12396 added inline comments.Jul 25 2017, 6:11 AM
lib/Analysis/ScopInfo.cpp
4828 ↗(On Diff #107525)

Oh, I see. Sorry, I missed your comment about the test case where you said "We should probably not try to verify the arguments of synthesizable instructions."

Meinersbur added inline comments.Jul 25 2017, 9:16 AM
lib/Analysis/ScopInfo.cpp
4828 ↗(On Diff #107525)

But I reverted because I didnt understand how can this be a non-functional change?

It is "No Functional Change Intended". We want Polly to behave exactly the same, but prepare for necessary later changes. Even if it means we break internal interfaces.

In this case, once we split a BB into two statement, we have don't know to which statement associate a synthesiable instruction. It might be used in both, yet getInstruction() of neither contains it.

The straightforward thing is to not associate with any of them. getStmtFor(Instruction*) must not return a statement. The alternatives would be adding it to both/all statement's instruction list or one of them arbitrarily. Maybe you have an argument why one of them is better?

Preparing for instructions that belong to no statement must therefore be done anyway.

nandini12396 updated this revision to Diff 108322.
Meinersbur added inline comments.Jul 27 2017, 9:54 AM
lib/Analysis/ScopInfo.cpp
3804 ↗(On Diff #108322)

[Serious] Only remove those in the statement's instruction list. Otherwise this also removes the links of all other statements representing this BasicBlock.

nandini12396 marked an inline comment as done.

@Meinersbur : This change leads to failure of ForwardOpTree/noforward_synthesizable_unknownit.ll because getStmtFor synthesizable instruction returns nullptr, which makes DefStmt null in line 227.

This is an interesting case because %i.trunc is synthesizable within the loop, but not outside of it.

What getStmtFor(BB) is trying to get here is some statement where it transfer the llvm::Value from (using a MemoryKind::Value WRITE/READ pair).

A "sophisticated" solution would be to select one statement in the loop (the last would be good) and insert a MemoryKind::Value WRITE there.

A simple solution, which is also the status quo before this patch, is to bail out (return FD_CannotForward)

Rebase & fix test-case failure as suggested.

Meinersbur added inline comments.Aug 8 2017, 5:10 AM
lib/Analysis/ScopInfo.cpp
4095 ↗(On Diff #109948)

[Suggestion] Could you add a comment what is happening here?

lib/Transform/ForwardOpTree.cpp
164 ↗(On Diff #109948)

[Serious] The statement where UseInst is defined should be the preferred one. The last statement of a BasicBlock is only a backup. Using any BB else than the preferred one would require to add another scalar write (currently not implemented in ForwardOpTree), which is what -polly-optree is trying to avoid.

The case is probably rare enough that we could also just return FD_CannotForward.

if (!DefStmt)
  return FD_CannotForward;

Note that in a recent commit this line has been moved to forwardTree.

Address comments

Meinersbur added inline comments.Aug 9 2017, 2:16 AM
lib/Transform/ForwardOpTree.cpp
669 ↗(On Diff #110279)

Please don't use assignments in conditionals (unless its an initializer of an inline variable declaration). It's hard to see whether its a typo of (==) or meant to have side-effects.

split if condition.

Meinersbur accepted this revision.Aug 9 2017, 9:43 AM

LGTM.

Thanks a lot!

This revision is now accepted and ready to land.Aug 9 2017, 9:43 AM
This revision was automatically updated to reflect the committed changes.