Page MenuHomePhabricator

[Polly] Split statements on encountering store instructions.
ClosedPublic

Authored by nandini12396 on Aug 31 2017, 8:02 AM.

Diff Detail

Repository
rL LLVM

Event Timeline

nandini12396 created this revision.Aug 31 2017, 8:02 AM

@Meinersbur : Should I change the checks in all the failing tests? But I think they may change again after the way of split is modified.

grosser edited edge metadata.Sep 2 2017, 12:09 AM

Hi Nandini,

no need to change tests. I would just run this once over polybench to see if anything fails.

Now, the actual heuristic we want to implement should likely be something ala:

I would rather aim for making a scop statement a specific subset of the
instructions in the basic block. As a first step, we could then aim for the
minimal DAGs that do not yet require the introduction of new scalar
dependences. E.g. a DAG like this:

 Load    Load
    \  /  |
     op   op
       \ /
      Store

Using these DAGs we keep the changes small, we enable more fine-grained
transformations and we do avoid any risks due to scalar expension.

as discussed here: https://bugs.llvm.org/show_bug.cgi?id=12402

Hence, starting from the last store, add all (non-synthesizable) instructions belonging to this store's operand tree (and collect the set of memory locations read from). Then proceed to the next store. If the store's memory location conflicts with any of the memory locations read add the next store's operand tree to the very same statement. If the read set of the earlier store and the subsequent writes do not interfere,

Best,
Tobias

Hello Sir,

no need to change tests. I would just run this once over polybench to see if anything fails.

I ran LNT on the llvm test-suite with cflags -O3 -mllvm -polly -mllvm -polly-process-unprofitable and there are no failures.
However, there are some assertion fails in polly/tests/ itself. One such example is test/Isl/CodeGen/non-affine-dominance-generated-entering.ll.
I will try to understand this and let you know.

Thank you,
Nandini

Meinersbur edited edge metadata.Sep 18 2017, 4:06 AM

Sorry for my absence for a while, a paper submission deadline came in the way.

I think we should not use "one and only one" strategy. We may want to run experiments to compare different strategies with each other. I suggest adding an option to switch between strategies, such as:

enum class GranularityChoice {
	BasicBlocks,
	Stores
};

static cl::opt<GranularityChoice> StmtGranularity("polly-stmt-granularity", 
	cl::desc("Select the statement granularity algorithm"),
	cl::values(
		clEnumValN(GranularityChoice::BasicBlocks, "bb", "Entire basic blocks granularity"),
		clEnumValN(GranularityChoice::Stores, "store", "Store-level granularity")
	),
	 cl::init(GranularityChoice::BasicBlocks), 
	cl::cat(PollyCategory));

This allows us to implement multiple strategies. Existing regression tests do not need to be changed.

One day we determined a "best" strategy, we only need to change the default. Regression tests can continue using -polly-stmt-granularity=bb.

The store-level granularity you implemented looks ok. I suggest to keep the polly_split_after metadata splitting which allows us to force splitting whatever the -polly-stmt-granularity setting is. The only tests I observe crashing (and therefore should fix) are ScopInfo/invariant_load_zext_parameter-2.ll and Isl\CodeGen\non-affine-dominance-generated-entering.ll.

Ideas for follow-up patches:

  • A instruction-level granularity where each statement has at most one instruction. I don't expect it to be useful in production, but for stress-testing Polly with lots of statements.
  • We could improve store-level granularity by only adding instructions required by that store to the same statement (if not yet added to another statement yet). Instructions not required by any store can be put in its own statement. -polly-optree would move it anyway, but it would be nice it had less work to do and have fewer dependencies if -polly-optree is not used.
nandini12396 retitled this revision from [Polly] [WIP] Split statements on encountering store instructions. to [Polly] Split statements on encountering store instructions..

Hello Sir,

Somehow, there are no assertion failures after your changes :).

but, those test-case fail when we add -polly-stmt-granularity=store still. Do we need to fix them?

Please add at least one test case for the new feature (splitting at stores).

Yes please fix the crashes. You can make a copy of the test cases and add -polly-stmt-granularity=store. There should never be any input that makes the compiler crash.

nandini12396 retitled this revision from [Polly] Split statements on encountering store instructions. to [Polly][WIP] Split statements on encountering store instructions..
Meinersbur added inline comments.Sep 28 2017, 4:28 AM
lib/Analysis/ScopBuilder.cpp
740–744 ↗(On Diff #116827)

I looked at non-affine-dominance-generated-entering-1.ll and these lines causes the region-stmt for subregionStmt to split, but we cannot split region statements yet. We must not break the loop here, there are no additional statements for a region-stmt.

Tobias recently added instruction lists for a region-stmts entry node. Support for splitting it shouldn't that hard anymore (If you want to implement that, please try in a different patch)

@Meinersbur: Oh I see that. Thank you, I will try that now.

@Meinersbur : After your commit rL314665, these tests no longer fail.

@Meinersbur : After your commit rL314665, these tests no longer fail.

Could you rebase this patch?

nandini12396 retitled this revision from [Polly][WIP] Split statements on encountering store instructions. to [Polly] Split statements on encountering store instructions..

rebase

Please add at least one test case where a basic block is successfully split up and check that there are two statements now.

lib/Analysis/ScopBuilder.cpp
697 ↗(On Diff #117690)

Not specificfor this patch:
StoreInsts are not the only instructions that write to memory, some CallInsts do as well: memset, etc.
There is Instruction::mayWriteToMemory(). Should we split at those as well?

test/Isl/CodeGen/non-affine-dominance-generated-entering-1.ll
3–7 ↗(On Diff #117690)

Please update the description of what this test is for.

9–16 ↗(On Diff #117690)

If this test is for testing the capability to split statement, we should test the result of the split (ScopInfo -analyze output)

test/ScopInfo/invariant_load_zext_parameter-3.ll
4 ↗(On Diff #117690)

Please update the description of what this test is for.

25–29 ↗(On Diff #117690)

If this test is for testing the capability to split statement, we should test the result of the split (ScopInfo -analyze output)

nandini12396 edited the summary of this revision. (Show Details)
Meinersbur accepted this revision.Dec 11 2017, 4:51 AM

LGTM, going to committ...

Thanks a lot!

test/ScopInfo/stmt_split_on_store.ll
1 ↗(On Diff #126274)

Very nice test case.

This revision is now accepted and ready to land.Dec 11 2017, 4:51 AM
This revision was automatically updated to reflect the committed changes.

I filed a bug for this option: http://llvm.org/PR35623 .

This is likely not specific to the -polly-stmt-granularity=store option, but for splitting in general.