[Polly] Create virtual independent blocks

[jdoerfert]

Summary

Even with the scalar/PHI modeling and code generation we still
utilized the independent blocks pass to move scalars around in order to
decrease the dependences caused by them. However, this has two major
drawbacks:
  o Polly could not be used as analysis only pass by default and
    without the independent blocks pass the result suffered.
  o The independent blocks pass had limited knowledge about domains
    as well as accesses. Both limited the pass to simple
    movement/re-computation of scalars that can be trivially moved.

This patch is a drop-in replacement for the independent blocks pass
that first virtually moves/re-computes scalars in the SCoP description.
Only in the code generation re-computation will actually take place.

The logic is split in three traversals of the scalars in the SCoP:
  1) Collect interesting operands for each scalar definition that
     escapes the block it resides in.
  2) For each scalar use, check if the definition can be recomputed
     in its statement based on the interesting operands of the
     definition. If so, remove the access and remember that the
     definition has to be recomputed later.
  3) For each scalar definition, check if all uses have been
     eliminated through virtual re-computation. If so, remove the
     access as it does not need to be communicated anymore.

Subsequent patches can increase the capabilities easily as the domain
and access information is already available.

  --------------------------  REVIEW NOTES  --------------------------

    - lnt & unit tests are green
    - We had 245 scalar access in the test suite before, now 236. In
      total this logic eliminated 21 trivially recomputable scalars
      and allowed to eliminate 54 instead of 49 statements.
    - The buildbots show the following compile/execution time changes for
      a similar but prior version of this patch:

      Compile time:
        Improvements           : Δ       : Previous : Current : σ
        .../bmm                : -71.43% : 0.6440   : 0.1840  : 0.0054
        .../paq8p              : -12.48% : 5.8644   : 5.1323  : 0.0181
        .../consumer-lame      : -10.13% : 10.3444  : 9.2961  : 0.0376
        .../sieve              : -5.61%  : 0.4280   : 0.4040  : 0.0093
        .../espresso           : -1.35%  : 10.3841  : 10.2441 : 0.0395
        ..//Recurrences-dbl    : -1.24%  : 4.1923   : 4.1403  : 0.0150
        .../471_omnetpp        : -1.08%  : 42.1606  : 41.7046 : 0.1013

      Execution time:
        Regressions            : Δ       : Previous : Current : σ
        .../salsa20            : 4.32%   : 6.6684   : 6.9564  : 0.0059
        .../GlobalDataFlow-dbl : 1.53%   : 4.6963   : 4.7683  : 0.0047

        Improvements           : Δ       : Previous : Current : σ
        ..//viterbi            : -1.61%  : 2.7402   : 2.6962  : 0.0072

[jdoerfert]

Ping

[grosser]

Hi Johannes,

great to see we will finally get rid of the IndependentBlocks pass. I just had a very first skim over this patch, but did not manage to do a full review yet.

The two main items I would still like to look into:

1. This seems to conflict with http://reviews.llvm.org/D12975 (Michael's DE-LICM)

I need to get a better understanding in which ways these patches possibly conflict (as well as the overall design).

2. Post-processing statements vs. instruction-list ScopStmts

Your current approach of first building all ScopStmts and then post-process them to eliminate scalar dependences is interesting. However, it requires a special post-processing phase in ScopInfo and additional special-purpose code in ScopStmt and BlockGenerator. I wonder if it may make sense to build ScopStmts from the beginning just as a list of instructions (instead of a basic block) which could then be uniformly processed in the BlockGenerator.

Best,
Tobias

include/polly/ScopInfo.h

1190

that needs to be recomputed

lib/Analysis/ScopInfo.cpp

1573–1575

use is / uses are

3113

"The latter to add" does not seem to make sense grammatically.

3238

grammar

3243

I am not yet convinced an exit ScopStmt is something we would like to have. Maybe leave this for another patch review.

[Meinersbur]

In D13611#268449, @grosser wrote:

Hi Johannes,

great to see we will finally get rid of the IndependentBlocks pass. I just had a very first skim over this patch, but did not manage to do a full review yet.

The two main items I would still like to look into:

1. This seems to conflict with http://reviews.llvm.org/D12975 (Michael's DE-LICM)

I need to get a better understanding in which ways these patches possibly conflict (as well as the overall design).

To add some details:

D12975 tracks which values flow between ScopStmts which this patch modifies at a very late phase. There should be fewer such implicit flows, but some of those flows might have already be created with origin MAPPED. The array element occupied by this MAPPED flow might be used for some other implicit flow, meaning De-LICM before virtual blocks is ineffective. It is also more difficult to modify MAPPEDs because lifetime issues have to be considered and there is no distinction between SCALAR and PHI origins (not sure how much of a problem this is though).

One of my rationale to do De-LICM before even creating MemoryAccesses is that it is easier to implement (no moving, copying, deleting of MemoryAccesses) and reduced overhead because fewer MemoryAccesses are created in the first place.

So we have the possibilities to either do "simplifyScalarAccesses" before creating MemoryAccesses (e.g. by marking Instructions to where they should be copied) or "De-LICM" after simplifyScalarAccesses.

lib/Analysis/ScopInfo.cpp

1584

I do not understand this code. Why did you even remove any comment about what it is doing?

3101

God function antipattern

[jdoerfert]

In D13611#268449, @grosser wrote:

Hi Johannes,

great to see we will finally get rid of the IndependentBlocks pass. I just had a very first skim over this patch, but did not manage to do a full review yet.

The two main items I would still like to look into:

1. This seems to conflict with http://reviews.llvm.org/D12975 (Michael's DE-LICM)

I need to get a better understanding in which ways these patches possibly conflict (as well as the overall design).

Yeah, at the time this was written it was fine but as far as I understand it the MAPPED accesses (and possibly more) implicitly change the semantics of the SCoP description without it beeing actually changed (except the "MAPPED" flag). One could argue that this should look for MAPPED accesses but I don't, instead I will argue that "MAPPED" should not be an access property that is determined on the CFG and only a flag in the access description that turns on some alternate path in the code generation. An access that is not actually happening (no code is generated for) should not be in the SCoP description and the ones in there should happen where they are and read/write the location they define. If that is the case this patch should work properly.

2. Post-processing statements vs. instruction-list ScopStmts

Your current approach of first building all ScopStmts and then post-process them to eliminate scalar dependences is interesting. However, it requires a special post-processing phase in ScopInfo and additional special-purpose code in ScopStmt and BlockGenerator. I wonder if it may make sense to build ScopStmts from the beginning just as a list of instructions (instead of a basic block) which could then be uniformly processed in the BlockGenerator.

Processing the SCoP allows general solutions which are not (easily) reproduceable on the CFG, e.g., determining if a load is overwritten is easy and precise but hard on the CFG. The instruction list is a different issue and it would remove not that much code/logic anyway. With the pending patches by Michael we will reload scalars at the beginning of a statmeent and as I pointed out on that review, alsmost the same is added here. While I did not get a valuable response on the idea (and implementation sketch) to merge the recomputation and the scalar reload at the beginning of a statement, I think it is what we ultimately want.

[jdoerfert]

In D13611#268497, @Meinersbur wrote:

In D13611#268449, @grosser wrote:

Hi Johannes,

great to see we will finally get rid of the IndependentBlocks pass. I just had a very first skim over this patch, but did not manage to do a full review yet.

The two main items I would still like to look into:

1. This seems to conflict with http://reviews.llvm.org/D12975 (Michael's DE-LICM)

I need to get a better understanding in which ways these patches possibly conflict (as well as the overall design).

To add some details:

D12975 tracks which values flow between ScopStmts which this patch modifies at a very late phase. There should be fewer such implicit flows, but some of those flows might have already be created with origin MAPPED. The array element occupied by this MAPPED flow might be used for some other implicit flow, meaning De-LICM before virtual blocks is ineffective. It is also more difficult to modify MAPPEDs because lifetime issues have to be considered and there is no distinction between SCALAR and PHI origins (not sure how much of a problem this is though).

See the comment on

One of my rationale to do De-LICM before even creating MemoryAccesses is that it is easier to implement (no moving, copying, deleting of MemoryAccesses) and reduced overhead because fewer MemoryAccesses are created in the first place.

While moving, copying and deleting MemoryAccesses sound like a lot, one has to remember the number of times this can happen and the cost of each operation.
I think the fact that we get generally better results with this patch than without (see commit message) shows that the "overhead" is low enough.

The implementation difficulty is another issue. While this patch currently only forwards/copies scalars its general structure allows more, e.g., reload values instead of communicate them (see subsequent patch) or remove conditional PHI nodes and replace them by selects. While e.g., reloading is generally hard and costly on the CFG level (one has to determine if the value has been overwritten somewhere in between) the SCoP abstraction allows to reason about it in a simple and consise way.

So we have the possibilities to either do "simplifyScalarAccesses" before creating MemoryAccesses (e.g. by marking Instructions to where they should be copied) or "De-LICM" after simplifyScalarAccesses.

I already proposed the latter in a review last week but I don't recall a positive answer to that.

lib/Analysis/ScopInfo.cpp

1584

This code was basically moved and the original comment was left behind, hence the answer to your question is simple:

The comment has to be moved too.

3101

I take this comment should read as:

Please split the function in three parts.

Sure, can do.

[Meinersbur]

In D13611#268545, @jdoerfert wrote:

In D13611#268449, @grosser wrote:

Hi Johannes,

great to see we will finally get rid of the IndependentBlocks pass. I just had a very first skim over this patch, but did not manage to do a full review yet.

The two main items I would still like to look into:

1. This seems to conflict with http://reviews.llvm.org/D12975 (Michael's DE-LICM)

I need to get a better understanding in which ways these patches possibly conflict (as well as the overall design).

Yeah, at the time this was written it was fine but as far as I understand it the MAPPED accesses (and possibly more) implicitly change the semantics of the SCoP description without it beeing actually changed (except the "MAPPED" flag). One could argue that this should look for MAPPED accesses but I don't, instead I will argue that "MAPPED" should not be an access property that is determined on the CFG and only a flag in the access description that turns on some alternate path in the code generation. An access that is not actually happening (no code is generated for) should not be in the SCoP description and the ones in there should happen where they are and read/write the location they define. If that is the case this patch should work properly.

The semantics of a Scop does not change. What does change is where implicits are stored. Like AccessInstruction and AccessValue and non-affine subregions, it is no information required by the polyhedral model itself, but required to associate polyhedral statments to the IR behind it.

To avoid modifying IR directly, we "virtualize" the relevant metainformation such that the Scop description and IR code do not map directly. Having to redirect loads/stores becomes unavoidable.

2. Post-processing statements vs. instruction-list ScopStmts

Your current approach of first building all ScopStmts and then post-process them to eliminate scalar dependences is interesting. However, it requires a special post-processing phase in ScopInfo and additional special-purpose code in ScopStmt and BlockGenerator. I wonder if it may make sense to build ScopStmts from the beginning just as a list of instructions (instead of a basic block) which could then be uniformly processed in the BlockGenerator.

Processing the SCoP allows general solutions which are not (easily) reproduceable on the CFG, e.g., determining if a load is overwritten is easy and precise but hard on the CFG. The instruction list is a different issue and it would remove not that much code/logic anyway. With the pending patches by Michael we will reload scalars at the beginning of a statmeent and as I pointed out on that review, alsmost the same is added here.

I can't find such code in this patch. Where is it?

While I did not get a valuable response on the idea (and implementation sketch) to merge the recomputation and the scalar reload at the beginning of a statement, I think it is what we ultimately want.

What proposal are you refereing to? What scalar reload?

In D13611#268560, @jdoerfert wrote:

In D13611#268497, @Meinersbur wrote:

In D13611#268449, @grosser wrote:

Hi Johannes,

great to see we will finally get rid of the IndependentBlocks pass. I just had a very first skim over this patch, but did not manage to do a full review yet.

The two main items I would still like to look into:

1. This seems to conflict with http://reviews.llvm.org/D12975 (Michael's DE-LICM)

I need to get a better understanding in which ways these patches possibly conflict (as well as the overall design).

To add some details:

D12975 tracks which values flow between ScopStmts which this patch modifies at a very late phase. There should be fewer such implicit flows, but some of those flows might have already be created with origin MAPPED. The array element occupied by this MAPPED flow might be used for some other implicit flow, meaning De-LICM before virtual blocks is ineffective. It is also more difficult to modify MAPPEDs because lifetime issues have to be considered and there is no distinction between SCALAR and PHI origins (not sure how much of a problem this is though).

See the comment on

Which coomment?

One of my rationale to do De-LICM before even creating MemoryAccesses is that it is easier to implement (no moving, copying, deleting of MemoryAccesses) and reduced overhead because fewer MemoryAccesses are created in the first place.

While moving, copying and deleting MemoryAccesses sound like a lot, one has to remember the number of times this can happen and the cost of each operation.
I think the fact that we get generally better results with this patch than without (see commit message) shows that the "overhead" is low enough.

I have no general objection to it. However, you occasionally raise such concerns yourself (e.g. D13341) so I try to take them into account.

The implementation difficulty is another issue. While this patch currently only forwards/copies scalars its general structure allows more, e.g., reload values instead of communicate them (see subsequent patch) or remove conditional PHI nodes and replace them by selects. While e.g., reloading is generally hard and costly on the CFG level (one has to determine if the value has been overwritten somewhere in between) the SCoP abstraction allows to reason about it in a simple and consise way.

Such analysis on the polyhedral model requires expensive ISL operations to compute the dependences. One of our intents of simplifying the scop description is to make its analysis run faster. We'd do still to the complicated analysis on the large scop description to get a simpler on and redo the same analysis. I am not saying this that this cannot make sense, but the simplifications we want to perform (IndependentBlocks, DeLICM) are both on the IR level on which reasoning is much cheaper.

So we have the possibilities to either do "simplifyScalarAccesses" before creating MemoryAccesses (e.g. by marking Instructions to where they should be copied) or "De-LICM" after simplifyScalarAccesses.

I already proposed the latter in a review last week but I don't recall a positive answer to that.

AFAIU we about to discuss this.

[jdoerfert]

Rebased + Changed according to first comments

[jdoerfert]

Fix minor errors

[Meinersbur]

I have the impression that this very much relies on that accesses (mostly SCALAR READ, but also PHI writes in non-affine subregions) are computed per instruction, whereas in D13762 I tried to make them per-ScopStmt. The difference is that e.g. if there are two reads in the same BB, two loads would be generated. In D13762 I tried to ensure that there is only one load.

This patch seems to skip PHI accesses completely. In San Joe you mentioned that only loop-carried phis would be skipped. Where is that part? Where would DeLICM tell what memory can be reused?

I got the impression we could generalize this with in SCEV expander. A SCEV-like object (we already support SDiv/SRem) could store an entire operand tree of movable instructions and CodeGen would synthesize/materialize it on request. This looks like more streamlined with current mechanisms instead of introducing a new one. What do you think?

include/polly/CodeGen/BlockGenerators.h

422

"all" does not match the description below

426

... where they are used.

428

... thus ensures that all ...

483

llvm_unreachable is not defined to trigger a trap.

488

Missing documentation?

545

Flag to indicate that the instruction ...

include/polly/LinkAllPasses.h

36 ↗

(On Diff #37007)

Separate patch to remove IndependentBlocks?

include/polly/ScopInfo.h

646

We can get the AccList from getStatement()->getParent()->AccFuncMap. Not necessary to pass it as parameter.

Rename to "copyTo"?

690

Unrelated?

1156

I think we should not depend on the order of accesses. ISL does not understand such an order and depending on it will likely cause some bugs (Think of a load after storing to the same location; do we even handle that case yet?).

AFAIK ISL assumes that all loads happen before the stores.

1164

OnlyMA=false removes multiple accesses, so move to a "removeAccessesCausedBy" function?

1194

It would be better if the class would not expose its implementation as an API. It could return iterators or an ArrayRef.

1555

It would be more idomatic if each call would check only a single Instruction instead of passing a set implementation.

1571

I think you should clarify that you actually mean a flattened operand _tree_. I think LLVM uses the term operands as the direct arguments/parameters of an instruction.

1575

AFAICS it is only used during the execution of simplifyScalarAccesses. You could make it local and pass it to the functions that need it.

1610

The name "simplifyScalarAccesses" is very general. How about "recomputableDependentScalars"?

lib/Analysis/ScopInfo.cpp

797

What if it has fewer dimensions? If it is impossible, could you add an assertion to make it clear?

803

Doesn't this update InstructionToAccesses?

1592

I'd still ask you to refactor this code. It is hard to understand and looks fragile as it depends on order. Maybe you could use some functions from <algorithm>

3097

What are you plans here? When can instructions with side effects be recomputed?

3102

What is there to see?

3107

Why exit node PHIs processed, but not standard phis?

3119

Why for each access separately? Shouldn't this be per-ScopStmt because it only matters for cross-stmt operands?

3134

auto -> Use ?

3136

This probably will have issues with PHIs in the scop's entry just is in PR25394, ie. if InstOpInst is a PHI with an incoming block from outside the scop.

3143

and continue ?

3195

Wouldn't it be possible to recompute some of the dependent values, even if some operands have side effects?

3199

Why only instructions that have operands from outside? For movable instructions (DependentScalar) without such operands, but implicit accesses, don't we need to remove its memory accesses as well?

3204

This is using the list of accesses this function modifies on the fly ("InstructionToAccess"). As such, it seems to me to depend on the order we iterate over all statements. E.g. the previous iteration already removed the read access of "OutsideUser", hence will not be added to AdditionalAccesses anymore, hence we miss some read accesses.

Or am I wrong? Why is it this cannot happen?

3209

What does this condition mean?

I think we generally are misusing "BaseAddr" for scalar access, because it actually not an address.

3213

I'd expect this to be computed in collectNonTrivialOperands(), like a partition of instructions in the operand tree into

• Movable
• Outside/Sideeffect (operand tree leaves)

I understand your algorithm works differently, but to understand, what is the rationale to only have direct operands in DependentScalars, while we want to copy/move an entire operand tree?

3251

If a user has no more accesses, is it because it is intended to be removed?

3254

auto -> MemoryAccess ?

3259

Is this break meant to leave both for-loops?

3266

This seems to be a different kind of "resolved" than in removeRecomputableScalarReads.

3282

collectNonTrivialOperands actually skips PHIs which are also implicit accesses.

3291

hence -> i.e.

lib/CodeGen/BlockGenerators.cpp

67

When does a dependent scalar become a global?

82

Shouldn't these be in the BBMap after recomputeDependentScalars() executed?

141–143

Why does this become necessary? Shouldn't "trySynthesizeNewValue" determine itself whether it is synthesizable?

158–159

This essentially becomes

assert(TryOnly)
return nullptr;

180

What is the rationale for this condition?

182

Shouldn't this been handled by recomputeDependentScalars() already? How do we know that the operand is even a DependentScalar?

If this is because DependendScalars is unordered, wouldn't it be cleaner to ensure they are in their order of dependence?

235–238

I like this change, but could be committed independently. Maybe also as a member function of ScopStmt?

237

This idiom appears multiple times. Introduce a helper function?

344

Any reason to do this before generateScalarLoads()? Naively, I'd think it belongs after it because some if the dependent instructions might still use scalars (e.g. read-only ones).

test/Isl/CodeGen/srem-in-other-bb.ll

1

Nice, but unrelated

[jdoerfert]

In D13611#284391, @Meinersbur wrote:

I have the impression that this very much relies on that accesses (mostly SCALAR READ, but also PHI writes in non-affine subregions) are computed per instruction, whereas in D13762 I tried to make them per-ScopStmt. The difference is that e.g. if there are two reads in the same BB, two loads would be generated. In D13762 I tried to ensure that there is only one load.

One vs. multiple loads/stores of scalars is only of little difference to us as it will only affect code generation. Everything before, especially dependence analysis, will be the same. Hence, consolidating scalar accesses only to save duplicate loads/stores in the genereted IR (that will be taken care of anyway) is no good reason to make any kind of scalar elimination harder.

This patch seems to skip PHI accesses completely. In San Joe you mentioned that only loop-carried phis would be skipped. Where is that part? Where would DeLICM tell what memory can be reused?

There are 5 patches. This is the first and it only deals with trivially recomputable scalars, thus the onces without any "interesting/complicated operands".
The following patches as well as DeLICM comes into play in the canRecomputeInStmt function which is (almost) the only place that needs to be updated to allow more functionality.

I got the impression we could generalize this with in SCEV expander. A SCEV-like object (we already support SDiv/SRem) could store an entire operand tree of movable instructions and CodeGen would synthesize/materialize it on request. This looks like more streamlined with current mechanisms instead of introducing a new one. What do you think?

If SCEV would allow floating point values maybe, till then, we would implement everything we have here somehow in our SCoPExpander which is not really helpful. Additionally, during the SCoP generation (e.g., when we check if we can synthezise scalars instead of communicating them) we cannot check for overwritten loads and free memory locations we can reuse.

include/polly/CodeGen/BlockGenerators.h

476–477

When we virtually move instructions we are not really interested in the loop surroinding them but their new parent block/statement, thus the change.

[jdoerfert]

I tried to address (in words) all your comments. Once we agrred on how to proceed I will do code changes.

include/polly/CodeGen/BlockGenerators.h

426

I will check that.

428

I will check that.

545

I will check that.

include/polly/ScopInfo.h

1164

We could do that.

1555

We could do that.

1571

Where do you expect a tree here? It actually contains transitive operands and I could add that word.

1575

We could do that.

lib/Analysis/ScopInfo.cpp

3134

We could do that.

3143

This looks weird without the follow up commits that introduce some code here.

3254

We could do that.

lib/CodeGen/BlockGenerators.cpp

235–238

I can commit it a priori but I don't see the need for a ScopStmt member function at the moment.

237

That's something not conflicting or required for this commit we can do.

344

First, by construction we can place it here as all recomputable scalars do not depend on anything we cannot recompute. Second, we can probably move it after the scalar loads generation but it should be all the same.

test/Isl/CodeGen/srem-in-other-bb.ll

1

I probably forogot that while I prepared this commit and all the test cases. I'm sorry.

[jdoerfert]

include/polly/CodeGen/BlockGenerators.h

422

All that are not communicated via memory but need to be recomputed.

483

I can use the original message instead. If you have a better way to describe llvm_unreachable I can put it here alternatively.

488

Yeah, somebody should add documentation to all this undocumented functions at some point.

include/polly/ScopInfo.h

646

I would like to avoid accessing members of a different class.

690

Needed somewhere, but it was quite a while ago. If ppl need to know where I can check.

1156

I'm not sure about your isl assumption but in any case, I'm not assuming anything here. The different input locations are purely for user experience (as the accesses are ordered in a more natural fashion).

1610

We do not recompute here and later we do not always recompute to simplify scalars, thus I think it actually fits pretty well.

lib/Analysis/ScopInfo.cpp

797

Sure we can add an assertion.

803

Mh, there was no need but we can do that too I guess.

1592

This code (already in the current HEAD) is ugly because it tries to be smart. While it heavily depends on the order it might need a lot more iterations if it would not. I don't argue we have to keep it but only that it works in Polly HEAD for now and can be takled afterwards, if we find a nice and comparable way to do it.

3097

That was what I was telling you in SJ about. I even pushed the first patch that implements this TODO to reviews and it depends on this one.

3102

I'm not sure how to answer to that as I expected the link to the function that containts the comment for this one to be self-explanatory.

3107

I'm not sure why you ask this but as you can probably see in the code no "PHI access" is processed. Though, if something that is a PHI does not introduce a "PHI access" it might be processed here.

3119

I'm not sure what you mean. Why do we look at each access separatly or why do we look at the non-trivial-operands of each access separalty?

3136

Mh, if we have a test case I'll check that.

3195

Might be, but it won't help with removing the scalar dependences. Actually, it might make them worse.

3199

Outside operands are the read only scalars we track to easy OpenMP code generation. The scalar access we recompute is removed later.

3204

No read access is/should be removed if it is still connected to anything else. Hence, your senario should never happen. Additionally, we actually iterate over accesses here, thus the actual removal happens only at the end (after we traversed all accesses).

3209

It depends on how you see it. I think the (virtual) register is a unique address for a scalar, thus it fits well here.

3213

We copy/move the entire operand tree but for that I do not need to traverse it and put all instructions into a list. I simply store the root of the tree and traverse it during the actual copy/move.

3251

Actually, it has already been removed, hence the statement but no read access.

3259

It could be but doesn't need to.

3266

No it is the same but for the write accesses instead of the reads. Or to be more precise, it is the passive version as writes are (passively) resolved if all their reads have been (actively) resolved.

3282

It does not skip them but stops as they are non-trivial operands.

lib/CodeGen/BlockGenerators.cpp

67

If it is hoisted.

82

After recomputeDependentScalars is executed they are in BBMap. Though our synthesize code sometimes thinks it can sythesize something while it actually referes to old values we have to recompute first while we are in recomputeDependentScalars.

141–143

Good question. I don't remember anymore. I'll check once the general patch is agreed on.

158–159

Seems fine to me.

180

If we could not generate a new operand but we need to because the old one is an instruction in the region we have to do something.

182

Shouldn't this been handled by recomputeDependentScalars() already? How do we know that the operand is even a DependentScalar?

This code is only triggered while we execute recomputeDependentScalars.

If this is because DependendScalars is unordered, wouldn't it be cleaner to ensure they are in their order of dependence?

Which order of dependence? We got a DAG here and have to code generate it. One way is to find some topological order on the whole dag and then generate code, the other (which is implemented) is a recursive demand driven code generation. As we do the second everywhere else I figured it makes sense to do it here too.

[Meinersbur]

include/polly/ScopInfo.h

1571

What is a "transitive operand"?

lib/Analysis/ScopInfo.cpp

3119

This is nested inside a "for (MemoryAccess *MA : Stmt)" loop and NonTrivialOperandsMap is indexed by its AccessInst.

• If an instruction has multiple write access (AFAIK not possible at the moment), the code below would run multiple times over the same AccessInst.

• Multiple instructions in the same Stmt might use the same value, thus its operand tree appears multiple times in this statement. At code generation, each of them would get its own copy of the operand tree, although only one per stmt is necessary (the same tree can be reused for both users)

[jdoerfert]

Rebase and adjustment according to comments

[etherzhhb]

include/polly/ScopInfo.h

1160

Does "Caused by the instruction of MA" mean the user of instruction of MA?

1416

SE is a member of Scop, no need to pass it as a parameter.

I think it is reasonable to carry it around because we store SCEVs with Scop, e.g. Parameters.

1555

It would be more idomatic if each call would check only a single Instruction instead of passing a set implementation.

+1

1557

why we need they in SCoP Users?

1571

a = b + c
d = a + e

I guess b, c and hopefully a are the transitive operands of d.

They are also the leaves of the operand DAG rooted on d.

When we recompute d, the recomputation stop at b, c, e, right? That is, all instructions inside the DAG is recomputed.

So NoTrivialInstructionSet and OutsideOperandsSet together are the boundaries/leaves of the recompuation DAG, and NoTrivialInstructionSet are the instructions inside the Scop while OutsideOperandsSet are the instructions outside the Scop, right?

1575

I read:

<NoTrivialInstructions (first of NonTrivialOperandsPairTy )>   <OutsideOperandsSetTy (second of NonTrivialOperandsPairTy)>
                                   \                                       /
                                                 Recomputable DAG
                                                        | (root)
                                                 Instruction (the key of NonTrivialOperandsMap)

Actually can we check if an operand is outside Scop on the fly, such that only 1 operand set is need?

lib/Analysis/ScopInfo.cpp

2812

SE is a member of Scop

3109

// Now AccessInst is a write scalar access (and not a PHI).

3124–3149

How about using the following approach, which is all over LLVM codebase, and we can create a function for it.

// Depth-first traverse the operand DAG of AccessInst, until we reach:
//  * An instruction that is defined outside the current Scop (OutsideOperands )
//  * An instruction with side-effect (SideEffectOperands)
std::set Visited;
SmallVector<std::pair<Instruction*, Instruction::op_iterator> > VisitStack;
VisitStack.push_back(std::make_pair(AccessInst, AccessInst->begin()));

while (VisitStack.empty()) {
  auto CurNode = VisitStack.back().first;
  auto &CurChildIt = VisitStack.back().second;

  if (CurChildIt == CurNode->end()) {
    VisitStack.pop_back();
    continue;
  }

  Instruction *ChildInst = dyn_cast<Instruction>(*CurChildIt);
  ++CurChildIt;

  // Stop at invariances
  if (ChildInst == nullptr)
    continue;
  
  if (!Visited.insert(Inst).second)
    continue;

  // Invariance again.
  if (!R.contains(ChildInst)) {
    OutsideOperands.push_back(std::make_pair(InstOpInst, Inst));
    continue;
  }

  if (Inst->mayHaveSideEffects() || Inst->mayReadFromMemory()) {
    SideEffectOperands.insert(Inst);
    continue;
  }

  if (!isa<PHINode>(Inst))
    continue;

  if (R.contains(Inst) && canSynthesize(Inst, &LI, &SE, &R))
    continue;

  SideEffectOperands.insert(Inst);
}

3203

This user is actually inside the Scop, right?

3204

So what we need is only the parent block of the user that is inside the Scop?

3209

I read:

if (Stmt.containValueReadOf(OutsideOperand))

lib/CodeGen/BlockGenerators.cpp

183

If copyInstruction returns the newly copied instruction, the code

copyInstruction(Stmt, OldOperandInst, BBMap, LTS, nullptr, Recompute);
NewOperand = BBMap[OldOperand];

Become:

NewOperand = copyInstruction(Stmt, OldOperandInst, BBMap, LTS, nullptr, Recompute);

Which looks better and easier to understand.

But this can be done in another patch.

[etherzhhb]

See inline comments, otherwise I do not see any problem

[jdoerfert]

Updated according to Hongbin's comments. Unified all non-trivial operands.

[jdoerfert]

I addressed all of the comments except one (the new algorithm to collect non-trivial operands).

@etherzhhb, @Meinersbur, @grosser, @sebpop
Since this patch caused so much discussion I guess it would be nice to get two ppl to tell me it's fine to commit.

include/polly/ScopInfo.h

1160

I created two functions now. One to remove all accesses caused by an instruction and one to remove exactly the accesses passed as arguments.

1557

To find the access in the SCoP (if there is one). Only knowing the outside operand doesn't suffice to identify the MemoryAccess objects that we already created because of this outside operand.

1571

I guess b, c and hopefully a are the transitive operands of d.

In the code above operands would mean {b,c,e} for the instruction d.

They are also the leaves of the operand DAG rooted on d.

True, but whit PHI nodes we might not have a DAG and the PHIs are not necessarily leaves.

When we recompute d, the recomputation stop at b, c, e, right? That is, all instructions inside the DAG is recomputed.

Yes. And since we do not recompute loop carried PHIs here we always have this nice DAG.

So NoTrivialInstructionSet and OutsideOperandsSet together are the boundaries/leaves of the recompuation DAG, and NoTrivialInstructionSet are the instructions inside the Scop while OutsideOperandsSet are the instructions outside the Scop, right?

Yes, except the PHI case where we do not have a DAG and even though PHI are not leaves we put them in the NoTrivialInstructionSet.

1575

Good point, I adjusted the code to use only one set of non-trivial operands and then compute the outside operands + inside users on the fly. Thanks!

lib/Analysis/ScopInfo.cpp

3109

Added a comment.

3124–3149

I don't get the problem you try to solve here. Why do we need a different algorithm and what is it that it does better?

3203

Renamed.

3204

True. I changed this code to use only one set of operands and compute everything else on the fly.

3209

Yes. Is that a problem?

lib/CodeGen/BlockGenerators.cpp

183

We could do that later, true.

[etherzhhb]

include/polly/ScopInfo.h

1571

Just to confirm, we do not recompute loop-carried PHIs, right?

lib/Analysis/ScopInfo.cpp

3124–3149

It is almost the same algorithm, but in different 'style'. I think I should not push too hard about the "style". So I think we are done with this.

But we should put some comments to describe what the algorithm is doing like:

// Traverse the operand DAG of AccessInst, until we reach:
//  * An instruction that is defined outside the current Scop (OutsideOperands )
//  * An instruction with side-effect (SideEffectOperands)

3209

It is a little bit not straight forward, but with the comment above, I think it is ok.

lib/CodeGen/BlockGenerators.cpp

154–158

TryOnly is only used here. And this block is equivalent to:

assert(TryOnly && "Unexpected scalar dependence in region!");
return nullptr;

Instead of passing TryOnly as function parameter, can we move the assertion out of this function, like:

auto *V = getNewValue(....);
assert((V || TryOnly) && "Unexpected scalar dependence in region!");

Now we can remove this confusing TryOnly.

344

First, by construction we can place it here as all recomputable scalars do not depend on anything we cannot recompute. Second, we can probably move it after the scalar loads generation but it should be all the same.

It would be good to put your above explanations as comments to the code.

1086–1087

Interesting duplication :)
We should also add some comments to explain why we recomputeDependentScalar before generateScalarLoads here as well.

[jdoerfert]

etherzhhb requested changes to this revision
This revision now requires changes to proceed.

Do you want other changes than the missing comments and the TryOnly thing? Both seem to be minor but the status change seems to indicate a bigger problem with this patch.

include/polly/ScopInfo.h

1571

Not in this patch (or the following three that are more or less rdy), however we are working on loop-carried PHIs too.

lib/Analysis/ScopInfo.cpp

3124–3149

I can do that.

lib/CodeGen/BlockGenerators.cpp

344

I can add a comment. sure.

1086–1087

I am confused. Are you hinting on the fact that we call "recomputeDependentScalars" here too or that we call it again before "generateScalarLoads"? I talked about the order already in the comment above. And the duplication of the "recomputeDependentScalars" call has the reason as the duplication of the "generateScalarLoads" call, this is the starting point of a "copyStmt" function. While above it is for block statements, here it is for region statements. If you want I can extract both calls into a "initializeScalars" method that is called before a statement is copied.

[etherzhhb]

I change the status to make this patch not block on me. There is no major issue.

[etherzhhb]

include/polly/ScopInfo.h

1571

ok

lib/CodeGen/BlockGenerators.cpp

1086–1087

I just think the duplicate here is interesting/funny ...

My intention is to suggest that we put the same comments as 344 here to explain the order, otherwise people may confused when they see this before they see the comments in line 344.

If you want I can extract both calls into a "initializeScalars" method that is called before a statement is copied.

This is great but can be done in another patch.

[etherzhhb]

I change the status to make this patch not block on me. There is no major issue.

I think this patch is good to go once the comments are fixed.

[grosser]

I still want to have a look at this, but did not make it. I am a little
delayed on the larger patches, but first will need to have a look at
Johannes SSA patch.

Best,
Tobias

[jdoerfert]

Ping?

include/polly/CodeGen/BlockGenerators.h

protected:
 
   /// @brief Promote the values of demoted scalars after the SCoP.
   ///
   /// If a scalar value was used outside the SCoP we need to promote the value
   /// stored in the memory cell allocated for that scalar and combine it with
   /// the original value in the non-optimized SCoP.
   void createScalarFinalization(Region &R);
 
+  /// @brief Recompute scalars needed in this statement.
+  ///
+  /// During SCoP creation scalars can be virtually moved to simplify the SCoP
+  /// description as well as the dependences. However, they are only moved if
+  /// we can recompute them in the statements they are used in. This method will
+  /// perform the recomputation before we clone the original statement into the
+  /// new, optimized region. Thus it ensures that all scalars are available.
+  void recomputeDependentScalars(ScopStmt &Stmt, ValueMapT &BBMap,
+                                 LoopToScevMapT &LTS,
+                                 isl_id_to_ast_expr *NewAccesses);
+
   /// @brief Try to synthesize a new value
   ///
   /// Given an old value, we try to synthesize it in a new context from its
   /// original SCEV expression. We start from the original SCEV expression,
   /// then replace outdated parameter and loop references, and finally
   /// expand it to code that computes this updated expression.
   ///
   /// @param Stmt      The statement to code generate
   /// @param Old       The old Value
   /// @param BBMap     A mapping from old values to their new values
   ///                  (for values recalculated within this basic block)
   /// @param LTS       A mapping from loops virtual canonical induction
   ///                  variable to their new values
   ///                  (for values recalculated in the new ScoP, but not
   ///                   within this basic block)
   /// @param L         The loop that surrounded the instruction that referenced
   ///                  this value in the original code. This loop is used to
   ///                  evaluate the scalar evolution at the right scope.
   ///
   /// @returns  o A newly synthesized value.
   ///           o NULL, if synthesizing the value failed.
   Value *trySynthesizeNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
-                               LoopToScevMapT &LTS, Loop *L) const;
+                               LoopToScevMapT &LTS, Loop *L);
 
   /// @brief Get the new version of a value.
   ///
   /// Given an old value, we first check if a new version of this value is
   /// available in the BBMap or GlobalMap. In case it is not and the value can
   /// be recomputed using SCEV, we do so. If we can not recompute a value
   /// using SCEV, but we understand that the value is constant within the scop,
   /// we return the old value.  If the value can still not be derived, this
   /// function will assert.
   ///
   /// @param Stmt      The statement to code generate.
   /// @param Old       The old Value.
   /// @param BBMap     A mapping from old values to their new values
   ///                  (for values recalculated within this basic block).
   /// @param LTS       A mapping from loops virtual canonical induction
   ///                  variable to their new values
   ///                  (for values recalculated in the new ScoP, but not
   ///                   within this basic block).
   /// @param L         The loop that surrounded the instruction that referenced
   ///                  this value in the original code. This loop is used to
   ///                  evaluate the scalar evolution at the right scope.
+  /// @param TryOnly   Flag to indicate that nullptr is a valid return value
+  ///                  if no new value was found.
   ///
   /// @returns  o The old value, if it is still valid.
   ///           o The new value, if available.
-  ///           o NULL, if no value is found.
+  ///           o NULL, if no value is found and TryOnly is set.
+  ///           o Otherwise a trap is triggered.
   Value *getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
-                     LoopToScevMapT &LTS, Loop *L) const;
+                     LoopToScevMapT &LTS, Loop *L, bool TryOnly = false);
 
   void copyInstScalar(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap,
-                      LoopToScevMapT &LTS);
+                      LoopToScevMapT &LTS, bool Recompute = false);
 
   /// @brief Get the innermost loop that surrounds the statement @p Stmt.
   Loop *getLoopForStmt(const ScopStmt &Stmt) const;
 
   /// @brief Generate the operand address
   /// @param NewAccesses A map from memory access ids to new ast expressions,
   ///                    which may contain new access expressions for certain
   ///                    memory accesses.
   Value *generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
                                   ValueMapT &BBMap, LoopToScevMapT &LTS,
                                   isl_id_to_ast_expr *NewAccesses);
protected:
   ///                    within this basic block).
   /// @param LTS         A mapping from loops virtual canonical induction
   ///                    variable to their new values
   ///                    (for values recalculated in the new ScoP, but not
   ///                     within this basic block).
   /// @param NewAccesses A map from memory access ids to new ast expressions,
   ///                    which may contain new access expressions for certain
   ///                    memory accesses.
+  /// @param Recompute   Flag to indicate that the instruction is a scalar that
+  ///                    needs to be recomputed in this statement. It basically
+  ///                    forces us to copy not only the instruction but also all
+  ///                    operands if we cannot find a local or global mapping.
   void copyInstruction(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap,
-                       LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses);
+                       LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses,
+                       bool Recompute = false);
 
   /// @brief Helper to determine if @p Inst can be synthezised in @p Stmt.
   ///
   /// @returns false, iff @p Inst can be synthesized in @p Stmt.
   bool canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst);
 };
 
 /// @brief Generate a new vector basic block for a polyhedral statement.

include/polly/ScopInfo.h

public:
   /// where the result of the PHI node is stored and later loaded from as well
   /// as a second one where the incoming values of the PHI nodes are stored
   /// into and reloaded when the PHI is executed. As both memories use the
   /// original PHI node as virtual base pointer, we have this additional
   /// attribute to distinguish the PHI node specific array modeling from the
   /// normal scalar array modeling.
   bool isPHIKind() const { return Kind == MK_PHI; };
 
+  /// @rbeif Return the memory kind of this array.
+  MemoryKind getKind() const { return Kind; };
+
   /// @brief Dump a readable representation to stderr.
   void dump() const;
 
   /// @brief Print a readable representation to @p OS.
   ///
   /// @param SizeAsPwAff Print the size as isl_pw_aff
   void print(raw_ostream &OS, bool SizeAsPwAff = false) const;
 
private:
   /// @brief Assemble the access relation from all availbale information.
   ///
   /// In particular, used the information passes in the constructor and the
   /// parent ScopStmt set by setStatment().
   ///
   /// @param SAI Info object for the accessed array.
   void buildAccessRelation(const ScopArrayInfo *SAI);
 
+  /// @brief Copy this memory access into the given statement @p Stmt.
+  ///
+  /// @param AccList The list that contains all accesses for @p Stmt.
+  /// @param NewStmt The statement the copied access should reside in.
+  MemoryAccess *copyTo(AccFuncSetType &AccList, ScopStmt *NewStmt) const;
+
 public:
   /// @brief Create a new MemoryAccess.
   ///
   /// @param Stmt       The parent statement.
   /// @param AccessInst The instruction doing the access.
   /// @param BaseAddr   The accessed array's address.
   /// @param ElemBytes  Number of accessed bytes.
   /// @param AccType    Whether read or write access.
public:
   /// anymore. For this reason we remember these explicitely for all PHI-kind
   /// accesses.
   ArrayRef<std::pair<BasicBlock *, Value *>> getIncoming() const {
     assert(isAnyPHIKind());
     return Incoming;
   }
 
   /// @brief Get the type of a memory access.
-  enum AccessType getType() { return AccType; }
+  enum AccessType getType() const { return AccType; }
 
   /// @brief Is this a reduction like access?
   bool isReductionLike() const { return RedType != RT_NONE; }
 
   /// @brief Is this a read memory access?
   bool isRead() const { return AccType == MemoryAccess::READ; }
 
   /// @brief Is this a must-write memory access?
private:
 
   /// @brief The isl AST build for the new generated AST.
   isl_ast_build *Build;
 
   SmallVector<Loop *, 4> NestLoops;
 
   std::string BaseName;
 
+  /// @brief Set of scalar values that need to be recomputed in this statement.
+  SetVector<Instruction *> DependentScalars;
+
   /// Build the statement.
   //@{
   void buildDomain();
 
   /// @brief Fill NestLoops with loops surrounding this statement.
   void collectSurroundingLoops();
 
   /// @brief Build the access relation of all memory accesses.
public:
   void setBasicBlock(BasicBlock *Block) {
     // TODO: Handle the case where the statement is a region statement, thus
     //       the entry block was split and needs to be changed in the region R.
     assert(BB && "Cannot set a block for a region statement");
     BB = Block;
   }
 
   /// @brief Add @p Access to this statement's list of accesses.
-  void addAccess(MemoryAccess *Access);
+  ///
+  /// @param Access The access to add.
+  /// @param Front  Flag to indicate where the access should be added.
+  void addAccess(MemoryAccess *Access, bool Front = false);
 
   /// @brief Remove the memory access in @p InvMAs.
   ///
-  /// Note that scalar accesses that are caused by any access in @p InvMAs will
-  /// be eliminated too.
-  void removeMemoryAccesses(MemoryAccessList &InvMAs);
+  /// @param OnlyMA Flag to indicate if all accesses caused by the access
+  ///               instruction of @p MA should be removed or only @MA.
+  ///
+  /// Note that if @p OnlyMA is not set, scalar accesses that are caused by any
+  /// access in @p InvMAs will be eliminated too.
+  void removeMemoryAccesses(const MemoryAccessList &InvMAs,
+                            bool OnlyMA = false);
 
   typedef MemoryAccessVec::iterator iterator;
   typedef MemoryAccessVec::const_iterator const_iterator;
 
   iterator begin() { return MemAccs.begin(); }
   iterator end() { return MemAccs.end(); }
   const_iterator begin() const { return MemAccs.begin(); }
   const_iterator end() const { return MemAccs.end(); }
 
   unsigned getNumParams() const;
   unsigned getNumIterators() const;
 
   Scop *getParent() { return &Parent; }
   const Scop *getParent() const { return &Parent; }
 
   const char *getBaseName() const;
 
   /// @brief Set the isl AST build.
   void setAstBuild(__isl_keep isl_ast_build *B) { Build = B; }
 
   /// @brief Get the isl AST build.
   __isl_keep isl_ast_build *getAstBuild() const { return Build; }
 
+  /// @brief Add a scalar that needs to be recomputed in this statement.
+  void addDependentScalar(Instruction *Inst) { DependentScalars.insert(Inst); }
+
+  /// @brief Return the scalars that need to be recomputed in this statement.
+  const SetVector<Instruction *> &getDependentScalars() const {
+    return DependentScalars;
+  }
+
   /// @brief Restrict the domain of the statement.
   ///
   /// @param NewDomain The new statement domain.
   void restrictDomain(__isl_take isl_set *NewDomain);
 
   /// @brief Compute the isl representation for the SCEV @p E in this stmt.
   __isl_give isl_pw_aff *getPwAff(const SCEV *E);
 
private:
   /// @brief Get or create the access function set in a BasicBlock
   AccFuncSetType &getOrCreateAccessFunctions(const BasicBlock *BB) {
     return AccFuncMap[BB];
   }
   //@}
 
   /// @brief Initialize this ScopInfo .
   void init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD,
-            DominatorTree &DT, LoopInfo &LI);
+            DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE);
 
   /// @brief Add loop carried constraints to the header block of the loop @p L.
   ///
   /// @param L  The loop to process.
   /// @param LI The LoopInfo for the current function.
   void addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI);
 
   /// @brief Compute the branching constraints for each basic block in @p R.
private:
   /// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB)
   ///
   /// @param SD The ScopDetection analysis for the current function.
   void hoistInvariantLoads(ScopDetection &SD);
 
   /// @brief Add invariant loads listed in @p InvMAs with the domain of @p Stmt.
   void addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs);
 
+  /// @brief Check if we can recompute all instructions in @p Stmt.
+  ///
+  /// @param Stmt  The statement we want to recompute @p Insts in.
+  /// @param Insts The instructions we need to recompute.
+  ///
+  /// @returns True, if all instructions can be recomputed in @p Stmt.
+  bool canRecomputeInStmt(ScopStmt &Stmt, SmallPtrSet<Instruction *, 4> &Insts);
+
+  /// @brief Type for outside operands and their in SCoP users.
+  using OutsideOperandsSetTy =
+      SmallVector<std::pair<Instruction *, Instruction *>, 4>;
+
+  /// @brief Type for a set of instructions.
+  using InstructionSetTy = SmallPtrSet<Instruction *, 4>;
+
+  /// @brief Type for non-trivially copy/recompute-able operands.
+  ///
+  /// The first element of the pair contains instructions that are actually not
+  /// trivially copy/recompute-able, e.g., PHI nodes and loads. The second part
+  /// contains all in SCoP operands that use outside instructions. They are
+  /// non-trivial as we need to model the scalar read accesses of the outside
+  /// operands properly.
+  using NonTrivialOperandsPairTy =
+      std::pair<InstructionSetTy, OutsideOperandsSetTy>;
+
+  /// @brief Map from in SCoP instructions to their non-trivial operands.
+  DenseMap<Instruction *, NonTrivialOperandsPairTy> NonTrivialOperandsMap;
+
+  /// @brief Collect non-trivial operands for all scalar write accesses.
+  ///
+  /// @param LI The LoopInfo for the current function.
+  /// @param SE The ScalarEvolution for the current function.
+  ///
+  void collectNonTrivialOperands(LoopInfo &LI, ScalarEvolution &SE);
+
+  /// @brief Remove scalar reads that can be recomputed.
+  ///
+  /// This function will check if a scalar read can be recomputed instead of
+  /// reloaded/communicated. If so it will remove that access and add the
+  /// definition to the ScopStmt::DependentScalars of that statement instead.
+  /// During code generation these scalars will be recomputed before the
+  /// instructions in the statement are copied, thus can be used in the
+  /// statement without the need communicate them through memory. Additionally,
+  /// this function might introduce new read accesses for operands that are
+  /// defined outside the SCoP in order to allow e.g., OpenMP code generation
+  /// easy access to the values needed in a statement.
+  void removeRecomputableScalarReads(ScopStmt &Stmt);
+
+  /// @brief Remove scalar writes that are not read in the SCoP or at its exit.
+  ///
+  /// When Scop::recomputeScalarReads() removes read accesses the corresponding
+  /// write accesses might not be needed anymore. To this end, this function
+  /// removes scalar writes without scalar reads inside the SCoP or an escaping
+  /// use that would cause a reload and merge at the SCoP exit.
+  void removeUnreadScalarWrites(ScopStmt &Stmt);
+
+  /// @brief Simplify the scalar accesses in this SCoP.
+  ///
+  /// Scalar accesses are often not needed and only caused by the placement in
+  /// the code. Additionally it is sometimes possible to recompute scalars to
+  /// avoid communication. As scalars basically sequentialize all loops they are
+  /// in, we try to avoid scalar accesses as much as possible. To this end we
+  /// will virtually move and later recompute them in the code generation. This
+  /// allows more freedom for the scheduler while we do not need to change the
+  /// original code region at all.
+  ///
+  /// @param LI The LoopInfo for the current function.
+  /// @param SE The ScalarEvolution for the current function.
+  ///
+  void simplifyScalarAccesses(LoopInfo &LI, ScalarEvolution &SE);
+
   /// @brief Build the Context of the Scop.
   void buildContext();
 
   /// @brief Build the BoundaryContext based on the wrapping of expressions.
   void buildBoundaryContext();
 
   /// @brief Add user provided parameter constraints to context (source code).
   void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI);
public:
   typedef StmtSet::const_reverse_iterator const_reverse_iterator;
 
   reverse_iterator rbegin() { return Stmts.rbegin(); }
   reverse_iterator rend() { return Stmts.rend(); }
   const_reverse_iterator rbegin() const { return Stmts.rbegin(); }
   const_reverse_iterator rend() const { return Stmts.rend(); }
   //@}
 
+  /// @brief Remove the ScopArrayInfo object @p SAI.
+  void removeScopArrayInfo(const ScopArrayInfo *SAI);
+
   /// @brief Return the (possibly new) ScopArrayInfo object for @p Access.
   ///
   /// @param ElementType The type of the elements stored in this array.
   /// @param Kind        The kind of the array info object.
   const ScopArrayInfo *getOrCreateScopArrayInfo(Value *BasePtr,
                                                 Type *ElementType,
                                                 ArrayRef<const SCEV *> Sizes,
                                                 ScopArrayInfo::MemoryKind Kind);

lib/Analysis/ScopInfo.cpp

: Kind(Kind), AccType(Type), RedType(RT_NONE), Statement(Stmt),
       AccessValue(AccessValue), IsAffine(Affine),
       Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
       NewAccessRelation(nullptr) {
 
   std::string IdName = "__polly_array_ref";
   Id = isl_id_alloc(Stmt->getParent()->getIslCtx(), IdName.c_str(), this);
 }
 
+MemoryAccess *MemoryAccess::copyTo(AccFuncSetType &AccList,
+                                   ScopStmt *NewStmt) const {
+  AccList.emplace_back(NewStmt, getAccessInstruction(), getType(),
+                       getBaseAddr(), getElemSizeInBytes(), isAffine(),
+                       Subscripts, Sizes, getAccessValue(), Kind,
+                       getBaseName());
+  MemoryAccess *CopyMA = &AccList.back();
+
+  unsigned CurStmtDims = getStatement()->getNumIterators();
+  unsigned NewStmtDims = NewStmt->getNumIterators();
+  assert(NewStmtDims >= CurStmtDims);
+
+  isl_map *AR = getAccessRelation();
+  if (NewStmtDims > CurStmtDims)
+    AR = isl_map_add_dims(AR, isl_dim_in, NewStmtDims - CurStmtDims);
+
+  CopyMA->AccessRelation =
+      isl_map_set_tuple_id(AR, isl_dim_in, NewStmt->getDomainId());
+  return CopyMA;
+}
+
 void MemoryAccess::realignParams() {
   isl_space *ParamSpace = Statement->getParent()->getParamSpace();
   AccessRelation = isl_map_align_params(AccessRelation, ParamSpace);
 }
 
 const std::string MemoryAccess::getReductionOperatorStr() const {
   return MemoryAccess::getReductionOperatorStr(getReductionType());
 }
else
       Ty = ScopArrayInfo::MK_Array;
 
     auto *SAI = S.getOrCreateScopArrayInfo(Access->getBaseAddr(), ElementType,
                                            Access->Sizes, Ty);
     Access->buildAccessRelation(SAI);
   }
 }
 
-void ScopStmt::addAccess(MemoryAccess *Access) {
+void ScopStmt::addAccess(MemoryAccess *Access, bool Front) {
   Instruction *AccessInst = Access->getAccessInstruction();
 
   if (Access->isArrayKind()) {
     MemoryAccessList &MAL = InstructionToAccess[AccessInst];
     MAL.emplace_front(Access);
   } else if (Access->isValueKind() && Access->isWrite()) {
     Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());
     assert(Parent.getStmtForBasicBlock(AccessVal->getParent()) == this);
     assert(!ValueWrites.lookup(AccessVal));
 
     ValueWrites[AccessVal] = Access;
   } else if (Access->isValueKind() && Access->isRead()) {
     Value *AccessVal = Access->getAccessValue();
     assert(!ValueReads.lookup(AccessVal));
 
     ValueReads[AccessVal] = Access;
   } else if (Access->isAnyPHIKind() && Access->isWrite()) {
     PHINode *PHI = cast<PHINode>(Access->getBaseAddr());
     assert(!PHIWrites.lookup(PHI));
 
     PHIWrites[PHI] = Access;
   }
 
+  if (Front)
+    MemAccs.insert(MemAccs.begin(), Access);
+  else
     MemAccs.push_back(Access);
 }
 
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 
   Domain = isl_set_align_params(Domain, Parent.getParamSpace());
 }
void ScopStmt::print(raw_ostream &OS) const {
   } else
     OS.indent(16) << "n/a\n";
 
   for (MemoryAccess *Access : MemAccs)
     Access->print(OS);
 }
 
 void ScopStmt::dump() const { print(dbgs()); }
 
-void ScopStmt::removeMemoryAccesses(MemoryAccessList &InvMAs) {
+void ScopStmt::removeMemoryAccesses(const MemoryAccessList &InvMAs,
+                                    bool OnlyMA) {
   // Remove all memory accesses in @p InvMAs from this statement
   // together with all scalar accesses that were caused by them.
   // MK_Value READs have no access instruction, hence would not be removed by
   // this function. However, it is only used for invariant LoadInst accesses,
   // its arguments are always affine, hence synthesizable, and therefore there
   // are no MK_Value READ accesses to be removed.
   for (MemoryAccess *MA : InvMAs) {
     auto Predicate = [&](MemoryAccess *Acc) {
-      return Acc->getAccessInstruction() == MA->getAccessInstruction();
+      return Acc == MA ||
+             (!OnlyMA &&
+              Acc->getAccessInstruction() == MA->getAccessInstruction());
     };
     MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate),
                   MemAccs.end());
     InstructionToAccess.erase(MA->getAccessInstruction());
+    if (MA->isValueKind() && MA->isWrite())
+      ValueWrites.erase(MA->getAccessInstruction());
+    else if (MA->isValueKind() && MA->isRead())
+      ValueReads.erase(MA->getAccessValue());
+    else if (MA->isAnyPHIKind() && MA->isWrite())
+      PHIWrites.erase(cast<PHINode>(MA->getBaseAddr()));
   }
 }
 
 //===----------------------------------------------------------------------===//
 /// Scop class implement
 
 void Scop::setContext(__isl_take isl_set *NewContext) {
   NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context));
: SE(&ScalarEvolution), R(R), IsOptimized(false),
       HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false),
       MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Context(nullptr),
       Affinator(this), AssumedContext(nullptr), BoundaryContext(nullptr),
       Schedule(nullptr) {
   buildContext();
 }
 
 void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD,
-                DominatorTree &DT, LoopInfo &LI) {
+                DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE) {
   addUserAssumptions(AC, DT, LI);
   buildInvariantEquivalenceClasses(SD);
 
   buildDomains(&R, SD, DT, LI);
 
   // Remove empty and ignored statements.
   // Exit early in case there are no executable statements left in this scop.
   simplifySCoP(true, DT, LI);
void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD,
   realignParams();
   addParameterBounds();
   addUserContext();
   buildBoundaryContext();
   simplifyContexts();
   buildAliasChecks(AA);
 
   hoistInvariantLoads(SD);
+  simplifyScalarAccesses(LI, SE);
   simplifySCoP(false, DT, LI);
 }
 
 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
   isl_set_free(BoundaryContext);
   isl_schedule_free(Schedule);
for (ScopStmt &Stmt : *this) {
     Stmt.removeMemoryAccesses(InvariantAccesses);
     addInvariantLoads(Stmt, InvariantAccesses);
   }
   isl_union_map_free(Writes);
 
   verifyInvariantLoads(SD);
 }
 
+bool Scop::canRecomputeInStmt(ScopStmt &Stmt,
+                              SmallPtrSet<Instruction *, 4> &Insts) {
+  if (Insts.empty())
+    return true;
+
+  // TODO: Check if we can actually move the instructions.
+  return false;
+}
+
+void Scop::collectNonTrivialOperands(LoopInfo &LI, ScalarEvolution &SE) {
+  // See: Scop::simplifyScalarAccesses()
+
+  SmallPtrSet<Instruction *, 32> Visited;
+  for (ScopStmt &Stmt : *this) {
+    for (MemoryAccess *MA : Stmt) {
+      if (MA->isArrayKind() || MA->isRead() || MA->isPHIKind())
+        continue;
+
+      Instruction *AccessInst = cast<Instruction>(MA->getAccessValue());
+      if (NonTrivialOperandsMap.count(AccessInst))
+        continue;
+
+      DEBUG(dbgs() << "\nCheck operand tree of '" << *AccessInst << "'\n");
+
+      auto &NonTrivialOperands = NonTrivialOperandsMap[AccessInst];
+      auto &SideEffectOperands = NonTrivialOperands.first;
+      auto &OutsideOperands = NonTrivialOperands.second;
+
+      SmallPtrSet<Instruction *, 8> Worklist;
+      Worklist.insert(AccessInst);
+      Visited.clear();
+
+      while (!Worklist.empty()) {
+        Instruction *Inst = *Worklist.begin();
+        Worklist.erase(Inst);
+
+        if (!Visited.insert(Inst).second)
+          continue;
+
+        for (auto &InstOp : Inst->operands())
+          if (Instruction *InstOpInst = dyn_cast<Instruction>(InstOp)) {
+            if (R.contains(InstOpInst))
+              Worklist.insert(InstOpInst);
+            else
+              OutsideOperands.push_back(std::make_pair(InstOpInst, Inst));
+          }
+
+        if (Inst->mayHaveSideEffects() || Inst->mayReadFromMemory())
+          SideEffectOperands.insert(Inst);
+
+        if (!isa<PHINode>(Inst))
+          continue;
+
+        if (R.contains(Inst) && canSynthesize(Inst, &LI, &SE, &R))
+          continue;
+
+        SideEffectOperands.insert(Inst);
+      }
+
+      DEBUG({
+        dbgs() << "\tSideEffectOperands: {\n";
+        for (auto *Op : SideEffectOperands)
+          dbgs() << "\t\t" << *Op << "\n";
+        dbgs() << "\t}\n";
+        dbgs() << "\tOutsideOperands: {\n";
+        for (const auto &OpPair : OutsideOperands) {
+          dbgs() << "\t\t" << *OpPair.first << "\n";
+          dbgs() << "\t\tused by " << *OpPair.second << "\n";
+        }
+        dbgs() << "\t}\n\n";
+      });
+    }
+  }
+}
+
+void Scop::removeRecomputableScalarReads(ScopStmt &Stmt) {
+  // See: Scop::simplifyScalarAccesses()
+
+  BasicBlock *StmtBB =
+      Stmt.isBlockStmt() ? Stmt.getBasicBlock() : Stmt.getRegion()->getEntry();
+  AccFuncSetType &AccList = AccFuncMap[StmtBB];
+
+  SmallVector<MemoryAccess *, 8> AdditionalAccesses;
+  MemoryAccessList ResolvedAccesses;
+
+  for (MemoryAccess *MA : Stmt) {
+    if (!(MA->isValueKind() && MA->isRead()))
+      continue;
+
+    auto *DefInst = dyn_cast<Instruction>(MA->getAccessValue());
+
+    // Skip read-only scalars.
+    if (!DefInst)
+      continue;
+
+    // Skip read-only scalars and scalars defined in non-affine regions.
+    auto *DefStmt = getStmtForBasicBlock(DefInst->getParent());
+    if (!DefStmt || DefStmt->isRegionStmt())
+      continue;
+
+    // Check if the scalar can be recomputed in this statement.
+    auto &NonTrivialOperands = NonTrivialOperandsMap[DefInst];
+    auto &SideEffectOperands = NonTrivialOperands.first;
+    if (!canRecomputeInStmt(Stmt, SideEffectOperands))
+      continue;
+
+    // If the scalar can be recomputed, we copy all accesses of read-only
+    // scalars that are part of the operand tree of the recomputed value.
+    auto &OutsideOperands = NonTrivialOperands.second;
+    for (auto &OutsideOperandPair : OutsideOperands) {
+      Instruction *OutsideOperand = OutsideOperandPair.first;
+      Instruction *OutsideUser = OutsideOperandPair.second;
+      ScopStmt *UserStmt = getStmtForBasicBlock(OutsideUser->getParent());
+      if (!UserStmt)
+        continue;
+
+      // If an access to the read-only scalar is already present, continue.
+      if (Stmt.lookupValueReadOf(OutsideOperand))
+        continue;
+
+      // If an access to the read-only scalar was generated copy it.
+      auto *UseMA = UserStmt->lookupValueReadOf(OutsideOperand);
+      if (UseMA)
+        AdditionalAccesses.push_back(UseMA->copyTo(AccList, &Stmt));
+    }
+
+    Stmt.addDependentScalar(DefInst);
+    ResolvedAccesses.push_front(MA);
+  }
+
+  Stmt.removeMemoryAccesses(ResolvedAccesses, true);
+  for (MemoryAccess *MA : AdditionalAccesses)
+    Stmt.addAccess(MA, true);
+}
+
+void Scop::removeUnreadScalarWrites(ScopStmt &Stmt) {
+  // See: Scop::simplifyScalarAccesses()
+
+  // Predicate that will evaluate to true if we have to assume that
+  // @p AccessValue will be read in @p BB and additionally escape @p BB.
+  auto ContainsRead = [&](BasicBlock *BB, Value *AccessValue) {
+    auto *UStmt = getStmtForBasicBlock(BB);
+    if (!UStmt)
+      return false;
+
+    // TODO: This is too conservative.
+    if (UStmt->isRegionStmt())
+      return true;
+
+    // If there is no write in @p BB it will not escape @p BB, thus the
+    // read is a no-op.
+    bool ContainsWrite = false;
+    for (auto *UStmtMA : *UStmt)
+      ContainsWrite |= UStmtMA->isWrite();
+    if (!ContainsWrite)
+      return false;
+
+    return UStmt->lookupValueReadOf(AccessValue) != nullptr;
+  };
+
+  // Predicate that will evaluate to true if @p UserInst is a user of
+  // @p AccessValue in the current polyhedral description of the SCoP.
+  auto IsRemainingUser = [&](Instruction *UserInst, Value *AccessValue) {
+    auto *UserBB = UserInst->getParent();
+
+    // If the user is outside the SCoP the @p AccessValue is escaping and
+    // we implicitly model the escaping use.
+    if (!R.contains(UserBB))
+      return true;
+
+    auto *UserPHI = dyn_cast<PHINode>(UserInst);
+    if (!UserPHI)
+      return ContainsRead(UserBB, AccessValue);
+
+    //
+    if (UserBB == R.getEntry() && !R.getEnteringBlock())
+      return true;
+
+    // TODO: This is too conservative.
+    if (auto *UserPHIStmt = getStmtForBasicBlock(UserBB))
+      if (UserPHIStmt->isRegionStmt())
+        return true;
+
+    // If the user is a PHI node we have to check the incoming blocks of that
+    // PHI that are associated with the access instruction for possible uses.
+    for (unsigned u = 0, e = UserPHI->getNumIncomingValues(); u < e; u++)
+      if (UserPHI->getIncomingValue(u) == AccessValue)
+        if (ContainsRead(UserPHI->getIncomingBlock(u), AccessValue))
+          return true;
+
+    return false;
+  };
+
+  // Iterate over all accesses in @p Stmt and check if for all value writes
+  // if we still have a (possible) user. If not we will remove the access
+  // as well as the corresponding ScopArrayInfo object.
+  SmallVector<MemoryAccess *, 8> ResolvedAccesses;
+  for (MemoryAccess *MA : Stmt) {
+    if (!(MA->isValueKind() && MA->isWrite()))
+      continue;
+
+    bool AllUsersRemoved = true;
+    auto *AccessInst = cast<Instruction>(MA->getAccessValue());
+    for (auto *User : AccessInst->users())
+      AllUsersRemoved &= !IsRemainingUser(cast<Instruction>(User), AccessInst);
+
+    if (AllUsersRemoved)
+      ResolvedAccesses.push_back(MA);
+  }
+
+  for (MemoryAccess *MA : ResolvedAccesses) {
+    // Remove the ScopArrayInfo object for this scalar as we do neither
+    // define nor read it in the SCoP description but only copy the original
+    // version in the unoptimized region.
+    removeScopArrayInfo(MA->getScopArrayInfo());
+
+    Stmt.removeMemoryAccesses({MA}, true);
+  }
+}
+
+void Scop::simplifyScalarAccesses(LoopInfo &LI, ScalarEvolution &SE) {
+  // First iterate over all implicit write accesses, hence scalar definitions
+  // and collect all operands that might have side effects or read memory as
+  // well as all operands that are outside the SCoP. The former is needed to
+  // decide if we can recompute the scalar definition to another statement.
+  // The latter to add read-only scalar accesses to the statement in which the
+  // scalar is recomputed. That allows us to identify values needed e.g., for
+  // parallel code generation.
+  collectNonTrivialOperands(LI, SE);
+
+  // In the second step traverse all implicit read accesses, hence scalar uses
+  // in statements that do not define the scalar. However, at the moment we
+  // exclude PHIs to simplify the logic. For each use we will check if we can
+  // recompute the definition to this block (see canRecomputeInStmt()).
+  // If so we will:
+  //   o Add the definition to the dependent scalars set of the use statement.
+  //   o Add read accesses for all prior to the SCoP defined values if they
+  //     were present in the definition statement.
+  //   o Remove the use access from the use statement as it will be recomputed
+  //     and does not need to be communicated anymore.
+  for (ScopStmt &Stmt : *this)
+    removeRecomputableScalarReads(Stmt);
+
+  // In the third and final step we iterate over the scalar definitions in
+  // the SCoP again. We will check if we removed the accesses for all users
+  // of the scalar in the SCoP. If so, we can safely remove the scalar write
+  // access as all users will recompute the value. As we currently cannot simply
+  // use this logic to recompute values at the exit of the SCoP we will not
+  // remove scalars that escape the SCoP.
+  for (ScopStmt &Stmt : *this)
+    removeUnreadScalarWrites(Stmt);
+}
+
+void Scop::removeScopArrayInfo(const ScopArrayInfo *SAI) {
+  ScopArrayInfoMap.erase(std::make_pair(SAI->getBasePtr(), SAI->getKind()));
+}
+
 const ScopArrayInfo *
 Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
                                ArrayRef<const SCEV *> Sizes,
                                ScopArrayInfo::MemoryKind Kind) {
   auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)];
   if (!SAI) {
     auto &DL = getRegion().getEntry()->getModule()->getDataLayout();
     SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {
   // nodes that are at this point not part of the region will be.
   // To handle these PHI nodes later we will now model their operands as scalar
   // accesses. Note that we do not model anything in the exit block if we have
   // an exiting block in the region, as there will not be any splitting later.
   if (!R.getExitingBlock())
     buildAccessFunctions(R, *R.getExit(), *SD->getInsnToMemAccMap(&R), nullptr,
                          /* IsExitBlock */ true);
 
-  scop->init(*AA, AC, *SD, *DT, *LI);
+  scop->init(*AA, AC, *SD, *DT, *LI, *SE);
 }
 
 void ScopInfo::print(raw_ostream &OS, const Module *) const {
   if (!scop) {
     OS << "Invalid Scop!\n";
     return;
   }
 

lib/CodeGen/BlockGenerators.cpp

BlockGenerator::BlockGenerator(PollyIRBuilder &B, LoopInfo &LI,
                                ScalarAllocaMapTy &PHIOpMap,
                                EscapeUsersAllocaMapTy &EscapeMap,
                                ValueMapT &GlobalMap,
                                IslExprBuilder *ExprBuilder)
     : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
       EntryBB(nullptr), PHIOpMap(PHIOpMap), ScalarMap(ScalarMap),
       EscapeMap(EscapeMap), GlobalMap(GlobalMap) {}
 
+void BlockGenerator::recomputeDependentScalars(
+    ScopStmt &Stmt, ValueMapT &BBMap, LoopToScevMapT &LTS,
+    isl_id_to_ast_expr *NewAccesses) {
+
+  for (auto *Inst : Stmt.getDependentScalars())
+    if (!GlobalMap.count(Inst))
+      copyInstruction(Stmt, Inst, BBMap, LTS, NewAccesses, true);
+}
+
 Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
                                              ValueMapT &BBMap,
-                                             LoopToScevMapT &LTS,
-                                             Loop *L) const {
+                                             LoopToScevMapT &LTS, Loop *L) {
   if (!SE.isSCEVable(Old->getType()))
     return nullptr;
 
   const SCEV *Scev = SE.getSCEVAtScope(Old, L);
   if (!Scev)
     return nullptr;
 
   if (isa<SCEVCouldNotCompute>(Scev))
     return nullptr;
 
   const SCEV *NewScev = apply(Scev, LTS, SE);
+
+  // Recompute scalars needed for this SCEV
+  const Region &R = Stmt.getParent()->getRegion();
+  SetVector<Value *> Values;
+  findValues(NewScev, Values);
+  for (Value *Val : Values) {
+    if (Instruction *Inst = dyn_cast<Instruction>(Val))
+      if (R.contains(Inst))
+        copyInstruction(Stmt, Inst, BBMap, LTS, nullptr, true);
+  }
+
   ValueMapT VTV;
   VTV.insert(BBMap.begin(), BBMap.end());
   VTV.insert(GlobalMap.begin(), GlobalMap.end());
 
   Scop &S = *Stmt.getParent();
   const DataLayout &DL =
       S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
   auto IP = Builder.GetInsertPoint();
 
   assert(IP != Builder.GetInsertBlock()->end() &&
          "Only instructions can be insert points for SCEVExpander");
   Value *Expanded =
       expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV);
 
   BBMap[Old] = Expanded;
   return Expanded;
 }
 
 Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
-                                   LoopToScevMapT &LTS, Loop *L) const {
+                                   LoopToScevMapT &LTS, Loop *L, bool TryOnly) {
   // Constants that do not reference any named value can always remain
   // unchanged. Handle them early to avoid expensive map lookups. We do not take
   // the fast-path for external constants which are referenced through globals
   // as these may need to be rewritten when distributing code accross different
   // LLVM modules.
   if (isa<Constant>(Old) && !isa<GlobalValue>(Old))
     return Old;
 
if (Old->getType()->getScalarSizeInBits() <
       New = Builder.CreateTruncOrBitCast(New, Old->getType());
 
     return New;
   }
 
   if (Value *New = BBMap.lookup(Old))
     return New;
 
+  if (canSynthesize(Old, &LI, &SE, &Stmt.getParent()->getRegion()))
     if (Value *New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L))
       return New;
 
   // A scop-constant value defined by a global or a function parameter.
   if (isa<GlobalValue>(Old) || isa<Argument>(Old))
     return Old;
 
   // A scop-constant value defined by an instruction executed outside the scop.
   if (const Instruction *Inst = dyn_cast<Instruction>(Old))
     if (!Stmt.getParent()->getRegion().contains(Inst->getParent()))
       return Old;
 
+  if (TryOnly)
+    return nullptr;
+
   // The scalar dependence is neither available nor SCEVCodegenable.
   llvm_unreachable("Unexpected scalar dependence in region!");
-  return nullptr;
 }
 
 void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
-                                    ValueMapT &BBMap, LoopToScevMapT &LTS) {
+                                    ValueMapT &BBMap, LoopToScevMapT &LTS,
+                                    bool Recompute) {
   // We do not generate debug intrinsics as we did not investigate how to
   // copy them correctly. At the current state, they just crash the code
   // generation as the meta-data operands are not correctly copied.
   if (isa<DbgInfoIntrinsic>(Inst))
     return;
 
+  const Region &R = Stmt.getParent()->getRegion();
   Instruction *NewInst = Inst->clone();
 
   // Replace old operands with the new ones.
   for (Value *OldOperand : Inst->operands()) {
-    Value *NewOperand =
-        getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt));
+    Value *NewOperand = getNewValue(Stmt, OldOperand, BBMap, LTS,
+                                    getLoopForStmt(Stmt), Recompute);
+
+    if (Recompute) {
+      Instruction *NewOperandInst = dyn_cast_or_null<Instruction>(NewOperand);
+      if (!NewOperand || (NewOperandInst && R.contains(NewOperandInst))) {
+        if (Instruction *OldOperandInst = dyn_cast<Instruction>(OldOperand)) {
+          copyInstruction(Stmt, OldOperandInst, BBMap, LTS, nullptr, Recompute);
+          NewOperand = BBMap[OldOperand];
+        }
+      }
+    }
 
     if (!NewOperand) {
       assert(!isa<StoreInst>(NewInst) &&
              "Store instructions are always needed!");
+      assert(!Recompute && "Recompute copy should never fail");
       delete NewInst;
       return;
     }
 
     NewInst->replaceUsesOfWith(OldOperand, NewOperand);
   }
 
   Builder.Insert(NewInst);
if (OldPtrTy != NewPtrTy)
       Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
     return Address;
   }
 
   return getNewValue(Stmt, Inst.getPointerOperand(), BBMap, LTS,
                      getLoopForStmt(Stmt));
 }
 
 Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
   auto *StmtBB =
       Stmt.isBlockStmt() ? Stmt.getBasicBlock() : Stmt.getRegion()->getEntry();
   return LI.getLoopFor(StmtBB);
 }
 
 Value *BlockGenerator::generateScalarLoad(ScopStmt &Stmt, LoadInst *Load,
                                           ValueMapT &BBMap, LoopToScevMapT &LTS,
                                           isl_id_to_ast_expr *NewAccesses) {
   if (Value *PreloadLoad = GlobalMap.lookup(Load))
     return PreloadLoad;
 

 bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {
   Loop *L = getLoopForStmt(Stmt);
   return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
          canSynthesize(Inst, &LI, &SE, &Stmt.getParent()->getRegion());
 }
 
 void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
                                      ValueMapT &BBMap, LoopToScevMapT &LTS,
-                                     isl_id_to_ast_expr *NewAccesses) {
+                                     isl_id_to_ast_expr *NewAccesses,
+                                     bool Recompute) {
+
   // Terminator instructions control the control flow. They are explicitly
   // expressed in the clast and do not need to be copied.
   if (Inst->isTerminator())
     return;
 
   // Synthesizable statements will be generated on-demand.
   if (canSyntheziseInStmt(Stmt, Inst))
     return;
if (auto *PHI = dyn_cast<PHINode>(Inst)) {
     return;
   }
 
   // Skip some special intrinsics for which we do not adjust the semantics to
   // the new schedule. All others are handled like every other instruction.
   if (isIgnoredIntrinsic(Inst))
     return;
 
-  copyInstScalar(Stmt, Inst, BBMap, LTS);
+  copyInstScalar(Stmt, Inst, BBMap, LTS, Recompute);
 }
 
 void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
                               isl_id_to_ast_expr *NewAccesses) {
   assert(Stmt.isBlockStmt() &&
          "Only block statements can be copied by the block generator");
 
   ValueMapT BBMap;
BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
   return CopyBB;
 }
 
 BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
                                    ValueMapT &BBMap, LoopToScevMapT &LTS,
                                    isl_id_to_ast_expr *NewAccesses) {
   BasicBlock *CopyBB = splitBB(BB);
   Builder.SetInsertPoint(&CopyBB->front());
+
+  recomputeDependentScalars(Stmt, BBMap, LTS, NewAccesses);
+
   generateScalarLoads(Stmt, BBMap);
 
   copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
 
   // After a basic block was copied store all scalars that escape this block in
   // their alloca.
   generateScalarStores(Stmt, LTS, BBMap);
   return CopyBB;
void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   // inputs.
   BasicBlock *EntryBB = R->getEntry();
   BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
                                        &*Builder.GetInsertPoint(), &DT, &LI);
   EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
   Builder.SetInsertPoint(&EntryBBCopy->front());
 
   ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
+  recomputeDependentScalars(Stmt, EntryBBMap, LTS, IdToAstExp);
   generateScalarLoads(Stmt, EntryBBMap);
 
   for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
     if (!R->contains(*PI))
       BlockMap[*PI] = EntryBBCopy;
 
   // Determine the original exit block of this subregion. If it the exit block
   // is also the scop's exit, it it has been changed to polly.merge_new_and_old.
   // We move one block back to find the original block. This only happens if the

test/Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_different_bb.ll

 ; RUN: opt %loadPolly -polly-codegen -polly-parallel \
 ; RUN: -polly-parallel-force -S < %s | FileCheck %s
 ;
 ; Test to verify that we hand down the preloaded A[0] to the OpenMP subfunction.
 ;
 ;    void f(float *A) {
 ;      for (int i = 1; i < 1000; i++)
 ;        A[i] += /* split bb */ A[0];
 ;    }
-;                                           A[0]  tmp (unused)      A
-; CHECK: %polly.par.userContext = alloca { float,    float*,     float* }
+;                                           A[0]    A
+; CHECK: %polly.par.userContext = alloca { float, float* }
 ;
 ; CHECK:  %polly.subfn.storeaddr.polly.access.A.load = getelementptr inbounds
 ; CHECK:  store float %polly.access.A.load, float* %polly.subfn.storeaddr.polly.access.A.load
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(float* nocapture %A) {
 entry:

test/Isl/CodeGen/eliminate-multiple-scalar-fp-reads.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s --check-prefix=SCOP
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+;
+; SCOP-NOT: Scalar: 1
+; SCOP-NOT: ReadAccess
+;
+; Verify the original region is untouched but all computation is moved to the
+; only place it is needed in the generated region.
+;
+; CHECK:      for.body.f:
+; CHECK-NEXT:   %idxprom = sext i32 %i.0 to i64
+; CHECK-NEXT:   %arrayidx = getelementptr inbounds float, float* %A, i64 %idxprom
+; CHECK-NEXT:   store float %add5, float* %arrayidx
+;
+; CHECK: polly.stmt.for.body.f:
+; CHECK:   %0 = trunc i64 %polly.indvar to i32
+; CHECK:   %1 = shl i32 %0, 1
+; CHECK:   %p_conv = sitofp i32 %1 to float
+; CHECK:   %p_add = fadd float %p_conv, %p_conv
+; CHECK:   %p_add3 = fadd float %p_conv, %p_add
+; CHECK:   %p_add1 = fadd float %p_add, %p_conv
+; CHECK:   %p_add4 = fadd float %p_add3, %p_add1
+; CHECK:   %p_add2 = fadd float %p_conv, %p_conv
+; CHECK:   %p_add5 = fadd float %p_add4, %p_add2
+; CHECK:   %scevgep = getelementptr float, float* %A, i64 %polly.indvar
+; CHECK:   store float %p_add5, float* %scevgep
+;
+;    void f(float *A) {
+;      for (int i = 0; i < 1000; i++) {
+;        float a = i * 2;
+;        /* split BB */
+;        float b = a + a;
+;        /* split BB */
+;        float c = b + a;
+;        /* split BB */
+;        float d = a + a;
+;        /* split BB */
+;        float e = a + b + c + d;
+;        /* split BB */
+;        A[i] = e;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(float* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1000
+  br i1 %cmp, label %for.body.a, label %for.end
+
+for.body.a:
+  %mul = mul nsw i32 %i.0, 2
+  %conv = sitofp i32 %mul to float
+  br label %for.body.b
+
+for.body.b:
+  %add = fadd float %conv, %conv
+  br label %for.body.c
+
+for.body.c:
+  %add1 = fadd float %add, %conv
+  br label %for.body.d
+
+for.body.d:
+  %add2 = fadd float %conv, %conv
+  br label %for.body.e
+
+for.body.e:
+  %add3 = fadd float %conv, %add
+  %add4 = fadd float %add3, %add1
+  %add5 = fadd float %add4, %add2
+  br label %for.body.f
+
+for.body.f:
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %idxprom
+  store float %add5, float* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/Isl/CodeGen/eliminate-multiple-scalar-reads.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s --check-prefix=SCOP
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+;
+; SCOP-NOT: Scalar: 1
+; SCOP-NOT: ReadAccess
+;
+; Verify the original region is untouched but all computation is moved to the
+; only place it is needed in the generated region.
+;
+; CHECK:      for.body.f:
+; CHECK-NEXT:   %idxprom6 = sext i32 %i.0 to i64
+; CHECK-NEXT:   %arrayidx7 = getelementptr inbounds i32, i32* %A, i64 %idxprom6
+; CHECK-NEXT:   store i32 %add5, i32* %arrayidx7, align 4
+;
+; CHECK: polly.stmt.for.body.f:
+; CHECK:   %scevgep = getelementptr i32, i32* %A, i64 %polly.indvar
+; CHECK:   %0 = trunc i64 %polly.indvar to i32
+; CHECK:   %1 = shl i32 %0, 4
+; CHECK:   store i32 %1, i32* %scevgep
+;
+;    void f(int *A) {
+;      for (int i = 0; i < 1000; i++) {
+;        int a = i * 2;
+;        /* split BB */
+;        int b = a + a;
+;        /* split BB */
+;        int c = b + a;
+;        /* split BB */
+;        int d = a + a;
+;        /* split BB */
+;        int e = a + b + c + d;
+;        /* split BB */
+;        A[i] = e;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1000
+  br i1 %cmp, label %for.body.a, label %for.end
+
+for.body.a:                                         ; preds = %for.cond
+  %tmp = mul nsw i32 %i.0, 2
+  br label %for.body.b
+
+for.body.b:
+  %add = add nsw i32 %tmp, %tmp
+  br label %for.body.c
+
+for.body.c:
+  %add1 = add nsw i32 %add, %tmp
+  br label %for.body.d
+
+for.body.d:
+  %add2 = add nsw i32 %tmp, %tmp
+  br label %for.body.e
+
+for.body.e:
+  %add3 = add nsw i32 %tmp, %add
+  %add4 = add nsw i32 %add3, %add1
+  %add5 = add nsw i32 %add4, %add2
+  br label %for.body.f
+
+for.body.f:
+  %idxprom6 = sext i32 %i.0 to i64
+  %arrayidx7 = getelementptr inbounds i32, i32* %A, i64 %idxprom6
+  store i32 %add5, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/Isl/CodeGen/eliminate-scalars-with-outside-load.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s --check-prefix=CODEGEN
+;
+; Verify that we will virtually move %mul but also the read of %tmp to the
+; for.body.split block.
+;
+; CHECK:      Stmt_for_body_split
+; CHECK-NOT:            MemRef_mul
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                { Stmt_for_body_split[i0] -> MemRef_tmp[] };
+; CHECK-NOT:            MemRef_mul
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                { Stmt_for_body_split[i0] -> MemRef_A[i0] };
+; CHECK-NOT:            MemRef_mul
+;
+; CODEGEN:       polly.stmt.for.body.split:
+; CODEGEN-NEXT:    %p_mul = fmul float %tmp, 2.000000e+00
+;                  // Unused:
+; CODEGEN-NEXT:    %tmp.s2a.reload = load float, float* %tmp.s2a
+;
+; CODEGEN-NEXT:    %scevgep = getelementptr float, float* %A, i64 %polly.indvar
+; CODEGEN-NEXT:    store float %p_mul,
+;
+;    void f(float *A) {
+;      float x = A[-1];
+;      for (int i = 0; i < 1000; i++) {
+;        float a = x * 2;
+;        /* split BB */
+;        A[i] = a;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(float* %A) {
+entry:
+  %arrayidx = getelementptr inbounds float, float* %A, i64 -1
+  %tmp = load float, float* %arrayidx, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1000
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %mul = fmul float %tmp, 2.000000e+00
+  br label %for.body.split
+
+for.body.split:                                         ; preds = %for.cond
+  %arrayidx1 = getelementptr inbounds float, float* %A, i64 %indvars.iv
+  store float %mul, float* %arrayidx1, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/Isl/CodeGen/srem-in-other-bb.ll

-; RUN: opt %loadPolly -polly-codegen -S \
-; RUN:     < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 ;
 ;    void pos(float *A, long n) {
 ;      for (long i = 0; i < 100; i++)
 ;        A[n % 42] += 1;
 ;    }
 ;
-; CHECK:      polly.stmt.bb2:
-; CHECK-NEXT:   %p_tmp = srem i64 %n, 42
-; CHECK-NEXT:   store i64 %p_tmp, i64* %tmp.s2a
-;
-; CHECK:      polly.stmt.bb3:
-; CHECK:        %tmp.s2a.reload = load i64, i64* %tmp.s2a
-; CHECK:        %p_tmp3 = getelementptr inbounds float, float* %A, i64 %tmp.s2a.reload
+; CHECK: polly.stmt.bb3:
+; CHECK:   %[[rem:[._a-zA-Z0-9]*]] = srem i64 %n, 42
+; CHECK:   getelementptr inbounds float, float* %A, i64 %[[rem]]
 
 define void @pos(float* %A, i64 %n) {
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb6, %bb
   %i.0 = phi i64 [ 0, %bb ], [ %tmp7, %bb6 ]
   %exitcond = icmp ne i64 %i.0, 100

test/ScopInfo/eliminate-scalar-caused-by-load-reduction-2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s --check-prefix=CODEGEN
+;
+; This is a negative test. We should move the load to the split block
+; and remove all scalar accesses, however at the moment we only move
+; instructions that are trivially safe to move. All three checks should
+; be negated at some point. This also checks that we currently not try to
+; move a part of the scalar operand chain, i.e., the %add instruction.
+;
+; CHECK: Scalar: 1
+; CHECK: Scalar: 1
+; CHECK-NOT: Reduction: +
+;
+; These checks should stay as they verify we did not modify the original region:
+;
+; CODEGEN:      for.body.split:
+; CODEGEN-NEXT:   %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+; CODEGEN-NEXT:   store i32 %add, i32* %arrayidx2, align 4
+;
+;    void f(int *A) {
+;      for (int i = 0; i < 1000; i++) {
+;        int x = A[i] + 3;
+;        /* split BB */
+;        A[i] = x;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1000
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp, 3
+  br label %for.body.split
+
+for.body.split:
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/eliminate-scalar-caused-by-load-reduction.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; This is a negative test. We should move the load to the split block
+; and remove all scalar accesses, however at the moment we only move
+; instructions that are trivially safe to move. All three checks should
+; be negated at some point.
+;
+; CHECK: Scalar: 1
+; CHECK: Scalar: 1
+; CHECK-NOT: Reduction: +
+;
+;    void f(int *A) {
+;      for (int i = 0; i < 1000; i++) {
+;        int x = A[i];
+;        /* split BB */
+;        A[i] = x + 3;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1000
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp = load i32, i32* %arrayidx, align 4
+  br label %for.body.split
+
+for.body.split:
+  %add = add nsw i32 %tmp, 3
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/inter_bb_scalar_dep.ll

 ; RUN: opt %loadPolly -basicaa -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-codegen -analyze < %s
 
 ; void f(long A[], int N, int *init_ptr) {
 ;   long i, j;
 ;
 ;   for (i = 0; i < N; ++i) {
 ;     init = *init_ptr;
 ;     for (i = 0; i < N; ++i) {
 ;       A[i] = init + 2;
entry.next:                                       ; preds = %for.i
   %init = load i64, i64* %init_ptr
 ; CHECK-NOT: Stmt_entry_next
   br label %for.j
 
 for.j:                                            ; preds = %for.j, %entry.next
   %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
   %init_plus_two = add i64 %init, 2
 ; CHECK-LABEL: Stmt_for_j
-; CHECK:           ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
+; CHECK-NOT:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NOT:           [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
 ; CHECK:           MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
+; CHECK-NOT:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
   %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
   store i64 %init_plus_two, i64* %scevgep
   %indvar.j.next = add nsw i64 %indvar.j, 1
   %exitcond.j = icmp eq i64 %indvar.j.next, %N
   br i1 %exitcond.j, label %for.i.end, label %for.j
 
 for.i.end:                                        ; preds = %for.j
   %exitcond.i = icmp eq i64 %indvar.i.next, %N
   br i1 %exitcond.i, label %return, label %for.i
 
 return:                                           ; preds = %for.i.end
   ret void
 }
 
 attributes #0 = { nounwind }

test/ScopInfo/intra_and_inter_bb_scalar_dep.ll

 ; CHECK-NEXT: }
 ;
 ; CHECK:      Statements {
 ; CHECK-NEXT:     Stmt_for_j
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [N] -> { Stmt_for_j[i0, i1] : 0 <= i0 < N and 0 <= i1 < N };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [N] -> { Stmt_for_j[i0, i1] -> [i0, i1] };
-; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
 ; CHECK-NEXT: }
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 
 define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) #0 {
 entry:

test/ScopInfo/invariant-loads-leave-read-only-statements.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-codegen -analyze < %s
 
 ; CHECK:      Statements {
 ; CHECK-NEXT:     Stmt_top_split
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [p_0, p_1, p_2] -> { Stmt_top_split[] };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [p_0, p_1, p_2] -> { Stmt_top_split[] -> [0, 0, 0, 0] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_26[] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_25[] };
 ; CHECK-NEXT:     Stmt_L_4
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] : 0 <= i0 < p_0 and 0 <= i1 < p_0 and 0 <= i2 < p_0 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> [1, i0, i1, i2] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_19[i1, i0] };

test/ScopInfo/multidim_fortran_srem.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 
 ; CHECK:      Statements {
-; CHECK-NEXT:     Stmt_bb188
-; CHECK-NEXT:         Domain :=
-; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb188[i0] : 0 <= i0 <= -3 + tmp183 };
-; CHECK-NEXT:         Schedule :=
-; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb188[i0] -> [i0, 0, 0, 0] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb188[i0] -> MemRef_tmp192[] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb188[i0] -> MemRef_tmp194[] };
 ; CHECK-NEXT:     Stmt_bb203
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb203[i0, i1, i2] : 0 <= i0 <= -3 + tmp183 and 0 <= i1 <= -3 + tmp180 and 0 <= i2 <= -3 + tmp177 };
 ; CHECK-NEXT:         Schedule :=
-; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb203[i0, i1, i2] -> [i0, 1, i1, i2] };
-; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb203[i0, i1, i2] -> MemRef_tmp192[] };
+; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb203[i0, i1, i2] -> [i0, i1, i2] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb203[i0, i1, i2] -> MemRef_tmp173[o0, 1 + i1, 1 + i2] : 3*floor((-i0 + o0)/3) = -i0 + o0 and 0 <= o0 <= 2 };
-; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb203[i0, i1, i2] -> MemRef_tmp194[] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb203[i0, i1, i2] -> MemRef_tmp173[o0, 1 + i1, 1 + i2] : 3*floor((-2 - i0 + o0)/3) = -2 - i0 + o0 and 0 <= o0 <= 2 };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb203[i0, i1, i2] -> MemRef_arg56[1 + i0, 1 + i1, 1 + i2] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [tmp180, tmp177, tmp183, tmp162, tmp157, tmp150, tmp146, tmp140, tmp] -> { Stmt_bb203[i0, i1, i2] -> MemRef_arg55[1 + i0, 1 + i1, 1 + i2] };
 ; CHECK-NEXT: }
 

test/ScopInfo/out-of-scop-use-in-region-entry-phi-node.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 
-; CHECK: MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT: [p_0] -> { Stmt_bb3[] -> MemRef_tmp5[] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:   [p_0] -> { Stmt_bb3[] -> MemRef_tmp5[] };
+; CHECK:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:   [p_0] -> { Stmt_bb3[] -> MemRef_tmp7[] };
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @hoge() {
 bb:
   br label %bb2
 
 bb2:                                              ; preds = %bb

test/ScopInfo/scalar_dependence_cond_br.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ;
 ;    void f(int *A, int c, int d) {
 ;      for (int i = 0; i < 1024; i++)
 ;        if (c < i)
 ;          A[i]++;
 ;    }
 ;
-; FIXME: This test is a negative test until we have an independent blocks alternative.
-;
 ; We should move operands as close to their use as possible, hence in this case
-; there should not be any scalar dependence anymore after %cmp1 is moved to 
-; %for.body (%c and %indvar.iv are synthesis able).
+; there should not be any scalar dependence anymore after %cmp1 is virtually 
+; moved to %for.body (%c and %indvar.iv are synthesis able).
 ;
-; CHECK:      [Scalar: 1]
+; CHECK-NOT:      [Scalar: 1]
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A, i64 %c) {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry

test/ScopInfo/schedule-const-post-dominator-walk.ll

 ; RUN: opt %loadPolly -analyze -polly-scops < %s | FileCheck %s
+; RUN: opt %loadPolly -disable-output -polly-codegen < %s
 
 ; CHECK: { Stmt_bb3[i0] -> [0, 0] };
 ; CHECK: { Stmt_bb2[] -> [1, 0] };
 
 ; Verify that we generate the correct schedule. In older versions of Polly,
 ; we generated an incorrect schedule:
 ;
 ;   { Stmt_bb3[i0] -> [1, 0]; Stmt_bb2[] -> [0, 0] }

test/ScopInfo/tempscop-printing.ll

 ; RUN: opt %loadPolly -basicaa -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-codegen -analyze < %s
 
 ; void f(long A[], int N, int *init_ptr) {
 ;   long i, j;
 ;
 ;   for (i = 0; i < N; ++i) {
 ;     init = *init_ptr;
 ;     for (i = 0; i < N; ++i) {
 ;       A[i] = init + 2;
 ;     }
 ;   }
 ; }
 
 ; CHECK-LABEL: Function: f
 ;
 ; CHECK:       Statements {
 ; CHECK-NEXT:      Stmt_for_j
 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              [N] -> { Stmt_for_j[i0, i1] : 0 <= i0 < N and 0 <= i1 < N };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              [N] -> { Stmt_for_j[i0, i1] -> [i0, i1] };
-; CHECK-NEXT:          ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:              [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
 ; CHECK-NEXT:          MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:              [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
 ; CHECK-NEXT:  }
 ;
 ; CHECK-LABEL: Function: g
 ;
 ; CHECK:       Statements {
 ; CHECK-NEXT:      Stmt_for_j
 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              [N] -> { Stmt_for_j[i0, i1] : 0 <= i0 < N and 0 <= i1 < N };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              [N] -> { Stmt_for_j[i0, i1] -> [i0, i1] };
 ; CHECK-NEXT:          MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:              [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
-; CHECK-NEXT:          ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:              [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] };
 ; CHECK-NEXT:  }
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 
 
 define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) nounwind {
 entry:
   br label %for.i

test/ScopInfo/unneeded_scalar_dependences-1.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+; CHECK-NOT: Scalar: 1
+;
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N; i++) {
+;        int x = i + 1;
+;        for (int j = 0; j < N; j++)
+;          A[i] += A[j];
+;        A[i] += x;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.10, %entry
+  %indvars.iv1 = phi i64 [ %indvars.iv.next2, %for.inc.10 ], [ 0, %entry ]
+  %indvars.iv.next2 = add nuw nsw i64 %indvars.iv1, 1
+  %tmp6 = trunc i64 %indvars.iv.next2 to i32
+  %cmp = icmp slt i64 %indvars.iv1, %tmp
+  br i1 %cmp, label %for.body, label %for.end.12
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond.1
+
+for.cond.1:                                       ; preds = %for.inc, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body ]
+  %lftr.wideiv = trunc i64 %indvars.iv to i32
+  %exitcond = icmp ne i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.body.3, label %for.end
+
+for.body.3:                                       ; preds = %for.cond.1
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp3 = load i32, i32* %arrayidx, align 4
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv1
+  %tmp4 = load i32, i32* %arrayidx5, align 4
+  %add6 = add nsw i32 %tmp4, %tmp3
+  store i32 %add6, i32* %arrayidx5, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.3
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond.1
+
+for.end:                                          ; preds = %for.cond.1
+  %arrayidx8 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv1
+  %tmp5 = load i32, i32* %arrayidx8, align 4
+  %add9 = add nsw i32 %tmp5, %tmp6
+  store i32 %add9, i32* %arrayidx8, align 4
+  br label %for.inc.10
+
+for.inc.10:                                       ; preds = %for.end
+  br label %for.cond
+
+for.end.12:                                       ; preds = %for.cond
+  ret void
+}

test/ScopInfo/unneeded_scalar_dependences-2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+; CHECK-NOT: Scalar: 1
+;
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N; i++) {
+;        int x = i + 3;
+;        for (int j = 0; j < N; j++)
+;          A[i] += A[x + j];
+;        A[x] += x;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.11, %entry
+  %indvars.iv2 = phi i64 [ %indvars.iv.next3, %for.inc.11 ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv2, %tmp
+  br i1 %cmp, label %for.body, label %for.end.13
+
+for.body:                                         ; preds = %for.cond
+  %tmp5 = add nuw nsw i64 %indvars.iv2, 3
+  br label %for.cond.1
+
+for.cond.1:                                       ; preds = %for.inc, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body ]
+  %lftr.wideiv = trunc i64 %indvars.iv to i32
+  %exitcond = icmp ne i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.body.3, label %for.end
+
+for.body.3:                                       ; preds = %for.cond.1
+  %tmp6 = add nuw nsw i64 %tmp5, %indvars.iv
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %tmp6
+  %tmp7 = load i32, i32* %arrayidx, align 4
+  %arrayidx6 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv2
+  %tmp8 = load i32, i32* %arrayidx6, align 4
+  %add7 = add nsw i32 %tmp8, %tmp7
+  store i32 %add7, i32* %arrayidx6, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.3
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond.1
+
+for.end:                                          ; preds = %for.cond.1
+  %arrayidx9 = getelementptr inbounds i32, i32* %A, i64 %tmp5
+  %tmp9 = load i32, i32* %arrayidx9, align 4
+  %tmp10 = trunc i64 %tmp5 to i32
+  %add10 = add nsw i32 %tmp9, %tmp10
+  store i32 %add10, i32* %arrayidx9, align 4
+  br label %for.inc.11
+
+for.inc.11:                                       ; preds = %for.end
+  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv2, 1
+  br label %for.cond
+
+for.end.13:                                       ; preds = %for.cond
+  ret void
+}

test/ScopInfo/unneeded_scalar_dependences-3.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+; CHECK-NOT: Scalar: 1
+;
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N; i++) {
+;        int x = i + 3;
+;        for (int j = 0; j < N; j++)
+;          A[i] += x + j * x;
+;        A[x] += x * x;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.10, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc.10 ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end.12
+
+for.body:                                         ; preds = %for.cond
+  %tmp2 = add nuw nsw i64 %indvars.iv, 3
+  br label %for.cond.1
+
+for.cond.1:                                       ; preds = %for.inc, %for.body
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %j.0, %N
+  br i1 %exitcond, label %for.body.3, label %for.end
+
+for.body.3:                                       ; preds = %for.cond.1
+  %tmp3 = trunc i64 %tmp2 to i32
+  %mul = mul nsw i32 %j.0, %tmp3
+  %tmp4 = trunc i64 %tmp2 to i32
+  %add4 = add nsw i32 %tmp4, %mul
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp5 = load i32, i32* %arrayidx, align 4
+  %add5 = add nsw i32 %tmp5, %add4
+  store i32 %add5, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.3
+  %inc = add nuw nsw i32 %j.0, 1
+  br label %for.cond.1
+
+for.end:                                          ; preds = %for.cond.1
+  %tmp6 = trunc i64 %tmp2 to i32
+  %mul6 = mul nsw i32 %tmp6, %tmp6
+  %arrayidx8 = getelementptr inbounds i32, i32* %A, i64 %tmp2
+  %tmp7 = load i32, i32* %arrayidx8, align 4
+  %add9 = add nsw i32 %tmp7, %mul6
+  store i32 %add9, i32* %arrayidx8, align 4
+  br label %for.inc.10
+
+for.inc.10:                                       ; preds = %for.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end.12:                                       ; preds = %for.cond
+  ret void
+}

test/ScopInfo/unneeded_scalar_dependences-4.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+; CHECK-NOT: MemRef_cond
+; CHECK-NOT: Scalar: 1
+;
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N; i++) {
+;        int x = i > 42 ? i - 3 : i;
+;        for (int j = 0; j < N; j++)
+;          A[i] += x + j * x;
+;        A[i] += x * x;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.10, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc.10 ], [ 0, %entry ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc11, %for.inc.10 ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end.12
+
+for.body:                                         ; preds = %for.cond
+  %cmp1 = icmp sgt i64 %indvars.iv, 42
+  %tmp2 = trunc i64 %indvars.iv to i32
+  %sub = add nsw i32 %i.0, -3
+  %cond = select i1 %cmp1, i32 %sub, i32 %tmp2
+  br label %for.cond.2
+
+for.cond.2:                                       ; preds = %for.inc, %cond.end
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %cmp3 = icmp slt i32 %j.0, %N
+  br i1 %cmp3, label %for.body.4, label %for.end
+
+for.body.4:                                       ; preds = %for.cond.2
+  %mul = mul nsw i32 %j.0, %cond
+  %add = add nsw i32 %cond, %mul
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp4 = load i32, i32* %arrayidx, align 4
+  %add5 = add nsw i32 %tmp4, %add
+  store i32 %add5, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.4
+  %inc = add nuw nsw i32 %j.0, 1
+  br label %for.cond.2
+
+for.end:                                          ; preds = %for.cond.2
+  %mul6 = mul nsw i32 %cond, %cond
+  %arrayidx8 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp5 = load i32, i32* %arrayidx8, align 4
+  %add9 = add nsw i32 %tmp5, %mul6
+  store i32 %add9, i32* %arrayidx8, align 4
+  br label %for.inc.10
+
+for.inc.10:                                       ; preds = %for.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %inc11 = add nuw nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end.12:                                       ; preds = %for.cond
+  ret void
+}

test/ScopInfo/unneeded_scalar_dependences-5.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+; CHECK-NOT: MemRef_conv
+; CHECK-NOT: Scalar: 1
+;
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N; i++) {
+;        float x = i + 3.3;
+;        for (int j = 0; j < N; j++)
+;          A[i] += x + j * x;
+;        A[i] += x * x;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.17, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc.17 ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end.19
+
+for.body:                                         ; preds = %for.cond
+  %tmp1 = trunc i64 %indvars.iv to i32
+  %conv = sitofp i32 %tmp1 to double
+  %add = fadd double %conv, 3.300000e+00
+  %conv1 = fptrunc double %add to float
+  br label %for.cond.2
+
+for.cond.2:                                       ; preds = %for.inc, %for.body
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %j.0, %N
+  br i1 %exitcond, label %for.body.5, label %for.end
+
+for.body.5:                                       ; preds = %for.cond.2
+  %conv6 = sitofp i32 %j.0 to float
+  %mul = fmul float %conv6, %conv1
+  %add7 = fadd float %conv1, %mul
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp2 = load i32, i32* %arrayidx, align 4
+  %conv8 = sitofp i32 %tmp2 to float
+  %add9 = fadd float %conv8, %add7
+  %conv10 = fptosi float %add9 to i32
+  store i32 %conv10, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.5
+  %inc = add nuw nsw i32 %j.0, 1
+  br label %for.cond.2
+
+for.end:                                          ; preds = %for.cond.2
+  %mul11 = fmul float %conv1, %conv1
+  %arrayidx13 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp3 = load i32, i32* %arrayidx13, align 4
+  %conv14 = sitofp i32 %tmp3 to float
+  %add15 = fadd float %conv14, %mul11
+  %conv16 = fptosi float %add15 to i32
+  store i32 %conv16, i32* %arrayidx13, align 4
+  br label %for.inc.17
+
+for.inc.17:                                       ; preds = %for.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end.19:                                       ; preds = %for.cond
+  ret void
+}

test/ScopInfo/unneeded_scalar_dependences-6.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+;    void f(int *A, int N) {
+;      for (int i = 1; i < N; i++) {
+;        int preloaded = A[0];
+;        /* split BB */
+;        A[i] += preloaded;
+;      }
+;    }
+;
+; CHECK:    Invariant Accesses: {
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                [N] -> { Stmt_for_body[i0] -> MemRef_A[0] };
+; CHECK:            Execution Context: [N] -> {  : N >= 2 }
+; CHECK:    }
+;
+; CHECK-NOT: Scalar: 1
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 1, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp1 = load i32, i32* %A, align 4
+  br label %for.body.split
+
+for.body.split:
+  %arrayidx1 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp2 = load i32, i32* %arrayidx1, align 4
+  %add = add nsw i32 %tmp2, %tmp1
+  store i32 %add, i32* %arrayidx1, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/unneeded_scalar_dependences-7.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N; i++) {
+;        int scevable_addr = 2 * i + N;
+;        /* split BB */
+;        A[scevable_addr] += i;
+;      }
+;    }
+;
+; CHECK-NOT: Scalar: 1
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp1 = trunc i64 %indvars.iv to i32
+  %mul = shl nsw i32 %tmp1, 1
+  %add = add nsw i32 %mul, %N
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
+  br label %for.body.split
+
+for.body.split:
+  %tmp2 = load i32, i32* %arrayidx, align 4
+  %tmp3 = trunc i64 %indvars.iv to i32
+  %add1 = add nsw i32 %tmp2, %tmp3
+  store i32 %add1, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/unneeded_scalar_dependences-8.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+;    void f(int *A, int N) {
+;      int pre_scevable_addr = 2 * N + (N - 1);
+;      for (int i = 0; i < N; i++) {
+;        int scevable_addr = 2 * i + pre_scevable_addr;
+;        /* split BB */
+;        A[scevable_addr] += i;
+;      }
+;    }
+;
+; CHECK-NOT: Scalar: 1
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  %m = mul nsw i32 %N, 2
+  %s = sub nsw i32 %N, 1
+  %pre_scevable_addr = add nsw i32 %m, %s
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp1 = trunc i64 %indvars.iv to i32
+  %mul = shl nsw i32 %tmp1, 1
+  %add = add nsw i32 %mul, %pre_scevable_addr
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
+  br label %for.body.split
+
+for.body.split:
+  %tmp2 = load i32, i32* %arrayidx, align 4
+  %tmp3 = trunc i64 %indvars.iv to i32
+  %add1 = add nsw i32 %tmp2, %tmp3
+  store i32 %add1, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/unneeded_scalar_dependences-9.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+;    void f(int *A, int N) {
+;      if (N > 42) {
+;        int pre_scevable_addr = 2 * N + (N - 1);
+;        for (int i = 0; i < N; i++) {
+;          int scevable_addr = 2 * i + pre_scevable_addr;
+;          /* split BB */
+;          A[scevable_addr] += i;
+;        }
+;      }
+;    }
+;
+; CHECK-NOT: Scalar: 1
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+entry:
+  %tmp = sext i32 %N to i64
+  %m = mul nsw i32 %N, 2
+  br label %if.cond
+
+if.cond:
+  %s = sub nsw i32 %N, 1
+  %c = icmp sgt i32 %N, 42
+  br i1 %c, label %if.then, label %for.end
+
+if.then:
+  %pre_scevable_addr = add nsw i32 %m, %s
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %if.then ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp1 = trunc i64 %indvars.iv to i32
+  %mul = shl nsw i32 %tmp1, 1
+  %add = add nsw i32 %mul, %pre_scevable_addr
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
+  br label %for.body.split
+
+for.body.split:
+  %tmp2 = load i32, i32* %arrayidx, align 4
+  %tmp3 = trunc i64 %indvars.iv to i32
+  %add1 = add nsw i32 %tmp2, %tmp3
+  store i32 %add1, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}