[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

970

that needs to be recomputed

lib/Analysis/ScopInfo.cpp

1409–1410

use is / uses are

2794

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

2919

grammar

2924

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

1420

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

2782

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

1420

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.

2782

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?

546

Flag to indicate that the instruction ...

include/polly/LinkAllPasses.h

36 ↗

(On Diff #37007)

Separate patch to remove IndependentBlocks?

include/polly/ScopInfo.h

516

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

Rename to "copyTo"?

541

Unrelated?

932

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.

940

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

974

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

1275

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

1291

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.

1295

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

1330

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

lib/Analysis/ScopInfo.cpp

667

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

673

Doesn't this update InstructionToAccesses?

1420

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>

2778

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

2783

What is there to see?

2788

Why exit node PHIs processed, but not standard phis?

2800

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

2815

auto -> Use ?

2817

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.

2824

and continue ?

2876

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

2880

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?

2885

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?

2890

What does this condition mean?

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

2894

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?

2932

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

2935

auto -> MemoryAccess ?

2940

Is this break meant to leave both for-loops?

2947

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

2963

collectNonTrivialOperands actually skips PHIs which are also implicit accesses.

2972

hence -> i.e.

lib/CodeGen/BlockGenerators.cpp

67

When does a dependent scalar become a global?

86

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

130

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

147

This essentially becomes

assert(TryOnly)
return nullptr;

169

What is the rationale for this condition?

171

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?

226

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

228

This idiom appears multiple times. Introduce a helper function?

334

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

480

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.

546

I will check that.

include/polly/ScopInfo.h

940

We could do that.

1275

We could do that.

1291

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

1295

We could do that.

lib/Analysis/ScopInfo.cpp

2815

We could do that.

2824

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

2935

We could do that.

lib/CodeGen/BlockGenerators.cpp

226

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

228

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

334

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

516

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

541

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

932

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).

1330

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

667

Sure we can add an assertion.

673

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

1420

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.

2778

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.

2783

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.

2788

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.

2800

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?

2817

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

2876

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

2880

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

2885

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).

2890

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

2894

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.

2932

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

2940

It could be but doesn't need to.

2947

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.

2963

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

lib/CodeGen/BlockGenerators.cpp

67

If it is hoisted.

86

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.

130

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

147

Seems fine to me.

169

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.

171

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

1291

What is a "transitive operand"?

lib/Analysis/ScopInfo.cpp

2800

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

946

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

1190

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.

1275

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

+1

1277

why we need they in SCoP Users?

1291

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?

1295

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

2509

SE is a member of Scop

2790

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

2805–2830

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);
}

2884

This user is actually inside the Scop, right?

2885

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

2890

I read:

if (Stmt.containValueReadOf(OutsideOperand))

lib/CodeGen/BlockGenerators.cpp

172

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

946

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

1277

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.

1291

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.

1295

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

2790

Added a comment.

2805–2830

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?

2884

Renamed.

2885

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

2890

Yes. Is that a problem?

lib/CodeGen/BlockGenerators.cpp

172

We could do that later, true.

[etherzhhb]

include/polly/ScopInfo.h

1291

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

lib/Analysis/ScopInfo.cpp

2805–2830

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)

2890

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

lib/CodeGen/BlockGenerators.cpp

143–147

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.

334

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.

1071–1072

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

1291

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

2805–2830

I can do that.

lib/CodeGen/BlockGenerators.cpp

334

I can add a comment. sure.

1071–1072

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

1291

ok

lib/CodeGen/BlockGenerators.cpp

1071–1072

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 all 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 ensure 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 an instruction.
-  ///
-  /// @param Inst The instruction for which we get the loop.
-  /// @return The innermost loop that surrounds the instruction.
-  Loop *getLoopForInst(const Instruction *Inst);
+  /// @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, const Instruction *Inst,
                                   Value *Pointer, ValueMapT &BBMap,
                                   LoopToScevMapT &LTS,
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 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 get the newest version of @p ScalarValue.
   ///
   /// @param ScalarValue The original value needed.
   /// @param R           The current SCoP region.
   /// @param Stmt        The ScopStmt in which we look up this value.
   /// @param LTS         A mapping from loops virtual canonical induction
   ///                    variable to their new values

include/polly/ScopInfo.h

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 Stmt    The statement the copied access should reside in.
+  MemoryAccess *copy(AccFuncSetType &AccList, ScopStmt *Stmt) const;
+
 public:
   /// @brief Create a new MemoryAccess.
   ///
   /// @param Stmt       The parent statement.
   /// @param AccessInst The instruction doing the access.
   /// @param Id         Identifier that is guranteed to be unique within the
   ///                   same ScopStmt.
   /// @param BaseAddr   The accessed array's address.
   /// @param ElemBytes  Number of accessed bytes.
   /// @param AccType    Whether read or write access.
   /// @param IsAffine   Whether the subscripts are affine expressions.
   /// @param Origin     What is the purpose of this access?
   /// @param Subscripts Subscipt expressions
   /// @param Sizes      Dimension lengths of the accessed array.
   /// @param BaseName   Name of the acessed array.
   MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, __isl_take isl_id *Id,
                AccessType Type, Value *BaseAddress, unsigned ElemBytes,
                bool Affine, ArrayRef<const SCEV *> Subscripts,
                ArrayRef<const SCEV *> Sizes, Value *AccessValue,
                AccessOrigin Origin, StringRef BaseName);
   ~MemoryAccess();
 
   /// @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 @p MA from this statement.
+  ///
+  /// @param MA     The access to remove.
+  /// @param OnlyMA Flag to indicate if all accesses caused by the access
+  ///               instruction of @p MA should be removed or only @MA.
+  ///
+  void removeMemoryAccess(MemoryAccess *MA, bool OnlyMA);
 
   /// @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);
 
   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 need 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:
   InvariantEquivClassesTy InvariantEquivClasses;
 
   /// @brief Scop constructor; invoked from ScopInfo::buildScop.
   Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD,
        ScalarEvolution &SE, DominatorTree &DT, LoopInfo &LI, isl_ctx *ctx,
        unsigned MaxLoopDepth);
 
   /// @brief Initialize this ScopInfo .
   void init(AliasAnalysis &AA);
 
   /// @brief Add loop carried constraints to the header block of the loop @p L.
   ///
   /// @param L  The loop to process.
   void addLoopBoundsToHeaderDomain(Loop *L);
 
   /// @brief Compute the branching constraints for each basic block in @p R.
   ///
private:
   ///
   /// Common inv. loads: V, A[0][0], LB[0], LB[1]
   /// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB)
   void hoistInvariantLoads();
 
   /// @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.
+  void collectNonTrivialOperands();
+
+  /// @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();
+
+  /// @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();
+
+  /// @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.
+  void simplifyScalarAccesses();
+
   /// @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.
   void addUserContext();
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 IsPHI       Is this ScopArrayInfo object modeling special
   ///                    PHI node storage.
   const ScopArrayInfo *getOrCreateScopArrayInfo(Value *BasePtr,
                                                 Type *ElementType,
                                                 ArrayRef<const SCEV *> Sizes,

lib/Analysis/ScopInfo.cpp

MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
                            AccessOrigin Origin, StringRef BaseName)
     : Id(Id), Origin(Origin), AccType(Type), RedType(RT_NONE), Statement(Stmt),
       BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes),
       Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
       AccessValue(AccessValue), IsAffine(Affine),
       Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
       NewAccessRelation(nullptr) {}
 
+MemoryAccess *MemoryAccess::copy(AccFuncSetType &AccList,
+                                 ScopStmt *Stmt) const {
+  AccList.emplace_back(Stmt, getAccessInstruction(), getId(), getType(),
+                       getBaseAddr(), getElemSizeInBytes(), isAffine(),
+                       Subscripts, Sizes, getAccessValue(), Origin,
+                       getBaseName());
+  MemoryAccess *CopyMA = &AccList.back();
+
+  unsigned Dims = getStatement()->getNumIterators();
+  unsigned StmtDims = Stmt->getNumIterators();
+  isl_map *AR = getAccessRelation();
+  if (StmtDims > Dims)
+    AR = isl_map_add_dims(AR, isl_dim_in, StmtDims - Dims);
+
+  CopyMA->AccessRelation =
+      isl_map_set_tuple_id(AR, isl_dim_in, Stmt->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());
 }
for (MemoryAccess *Access : MemAccs) {
 
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
         Access->getBaseAddr(), ElementType, Access->Sizes, Access->isPHI());
 
     Access->buildAccessRelation(SAI);
   }
 }
 
-void ScopStmt::addAccess(MemoryAccess *Access) {
+void ScopStmt::addAccess(MemoryAccess *Access, bool Front) {
   Instruction *AccessInst = Access->getAccessInstruction();
 
   MemoryAccessList *&MAL = InstructionToAccess[AccessInst];
   if (!MAL)
     MAL = new MemoryAccessList();
   MAL->emplace_front(Access);
+  if (Front)
+    MemAccs.insert(MemAccs.begin(), MAL->front());
+  else
     MemAccs.push_back(MAL->front());
 }
 
 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) {
-
-  // Remove all memory accesses in @p InvMAs from this statement together
-  // with all scalar accesses that were caused by them. The tricky iteration
-  // order uses is needed because the MemAccs is a vector and the order in
-  // which the accesses of each memory access list (MAL) are stored in this
-  // vector is reversed.
-  for (MemoryAccess *MA : InvMAs) {
-    auto &MAL = *lookupAccessesFor(MA->getAccessInstruction());
-    MAL.reverse();
+void ScopStmt::removeMemoryAccess(MemoryAccess *MA, bool OnlyMA) {
 
-    auto MALIt = MAL.begin();
-    auto MALEnd = MAL.end();
-    auto MemAccsIt = MemAccs.begin();
-    while (MALIt != MALEnd) {
-      while (*MemAccsIt != *MALIt)
-        MemAccsIt++;
+  // The tricky iteration order used is needed because MemAccs is a vector
+  // and the order in which the accesses of each memory access list (MAL) are
+  // stored in this vector is reversed.
+  auto MALLastIt = MAL.before_begin();
+  while (true) {
+
+    while (OnlyMA && MALIt != MALEnd && (MA != *MALIt)) {
+      MALLastIt++;
+      MALIt++;
+    }
+
+    if (MALIt == MALEnd)
+      break;
+
 
-      MALIt++;
-      MemAccs.erase(MemAccsIt);
-    }
+    MALIt = MAL.erase_after(MALLastIt);
 
-    InstructionToAccess.erase(MA->getAccessInstruction());
-    delete &MAL;
-  }
-}
+  if (!MAL.empty())
+    return;
+
 
 //===----------------------------------------------------------------------===//
 /// Scop class implement
 
 void Scop::setContext(__isl_take isl_set *NewContext) {
   NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context));
   isl_set_free(Context);
   Context = NewContext;
void Scop::init(AliasAnalysis &AA) {
   updateAccessDimensionality();
   realignParams();
   addParameterBounds();
   addUserContext();
   buildBoundaryContext();
   simplifyContexts();
   buildAliasChecks(AA);
 
   hoistInvariantLoads();
+  simplifyScalarAccesses();
   simplifySCoP(false);
 }
 
 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
   isl_set_free(BoundaryContext);
   isl_schedule_free(Schedule);
for (ScopStmt &Stmt : *this) {
     // We inserted invariant accesses always in the front but need them to be
     // sorted in a "natural order". The statements are already sorted in reverse
     // post order and that suffices for the accesses too. The reason we require
     // an order in the first place is the dependences between invariant loads
     // that can be caused by indirect loads.
     InvMAs.reverse();
 
     // Transfer the memory access from the statement to the SCoP.
-    Stmt.removeMemoryAccesses(InvMAs);
+    for (MemoryAccess *MA : InvMAs)
+      Stmt.removeMemoryAccess(MA, false);
     addInvariantLoads(Stmt, InvMAs);
 
     isl_set_free(Domain);
   }
   isl_union_map_free(Writes);
 
   if (!InvariantEquivClasses.empty())
     IsOptimized = true;
if (Stmt && Stmt->lookupAccessesFor(LI) != nullptr) {
                       "such. SCoP for "
                    << getRegion() << " will be dropped\n\n");
       addAssumption(isl_set_empty(getParamSpace()));
       return;
     }
   }
 }
 
+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() {
+  // See: Scop::simplifyScalarAccesses()
+
+  SmallPtrSet<Instruction *, 32> Visited;
+  for (ScopStmt &Stmt : *this) {
+    for (MemoryAccess *MA : Stmt) {
+      if (MA->isExplicit() || MA->isRead() || MA->isPHI())
+        continue;
+
+      Instruction *AccessInst = MA->getAccessInstruction();
+      if (isa<TerminatorInst>(AccessInst))
+        AccessInst = cast<Instruction>(MA->getBaseAddr());
+
+      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() {
+  // See: Scop::simplifyScalarAccesses()
+
+  for (ScopStmt &Stmt : *this) {
+    BasicBlock *StmtBB = Stmt.isBlockStmt() ? Stmt.getBasicBlock()
+                                            : Stmt.getRegion()->getEntry();
+    AccFuncSetType &AccList = AccFuncMap[StmtBB];
+
+    SmallVector<MemoryAccess *, 8> AdditionalAccesses;
+    SmallVector<MemoryAccess *, 8> ResolvedAccesses;
+
+    for (MemoryAccess *MA : Stmt) {
+      if (MA->isExplicit() || MA->isWrite() || MA->isPHI())
+        continue;
+
+      Instruction *DefInst = dyn_cast<Instruction>(MA->getAccessValue());
+      if (!DefInst)
+        continue;
+
+      ScopStmt *DefStmt = getStmtForBasicBlock(DefInst->getParent());
+      if (!DefStmt)
+        continue;
+
+      auto &NonTrivialOperands = NonTrivialOperandsMap[DefInst];
+      auto &SideEffectOperands = NonTrivialOperands.first;
+      if (!canRecomputeInStmt(Stmt, SideEffectOperands))
+        continue;
+
+      auto &OutsideOperands = NonTrivialOperands.second;
+      for (auto &OutsideOperandPair : OutsideOperands) {
+        Instruction *OutsideOperand = OutsideOperandPair.first;
+        Instruction *OutsideUser = OutsideOperandPair.second;
+        ScopStmt *UserStmt = getStmtForBasicBlock(OutsideUser->getParent());
+        assert(UserStmt);
+        auto *UseMAs = UserStmt->lookupAccessesFor(OutsideUser);
+        if (!UseMAs)
+          continue;
+
+        for (const MemoryAccess *UseMA : *UseMAs)
+          if (UseMA->getBaseAddr() == OutsideOperand)
+            AdditionalAccesses.push_back(UseMA->copy(AccList, &Stmt));
+      }
+
+      Stmt.addDependentScalar(DefInst);
+      ResolvedAccesses.push_back(MA);
+    }
+
+    for (MemoryAccess *MA : ResolvedAccesses)
+      Stmt.removeMemoryAccess(MA, true);
+    for (MemoryAccess *MA : AdditionalAccesses)
+      Stmt.addAccess(MA, true);
+  }
+}
+
+void Scop::removeUnreadScalarWrites() {
+  // See: Scop::simplifyScalarAccesses()
+
+  for (ScopStmt &Stmt : *this) {
+    SmallVector<MemoryAccess *, 8> ResolvedAccesses;
+    for (MemoryAccess *MA : Stmt) {
+      if (MA->isExplicit() || MA->isRead() || MA->isPHI())
+        continue;
+
+      Instruction *AccessInst = MA->getAccessInstruction();
+      if (isa<TerminatorInst>(AccessInst))
+        AccessInst = cast<Instruction>(MA->getBaseAddr());
+
+      if (!R.contains(AccessInst))
+        continue;
+
+      bool AllUsersRemoved = true;
+      for (auto *User : AccessInst->users()) {
+        auto *UserInst = cast<Instruction>(User);
+
+        auto *UserStmt = getStmtForBasicBlock(UserInst->getParent());
+        if (!UserStmt) {
+          AllUsersRemoved = false;
+          break;
+        }
+
+        auto *UserMAs = UserStmt->lookupAccessesFor(UserInst);
+        if (!UserMAs)
+          continue;
+
+        for (auto *UserMA : *UserMAs) {
+          if (UserMA->isExplicit() || UserMA->isWrite())
+            continue;
+
+          AllUsersRemoved = false;
+          break;
+        }
+      }
+
+      if (!AllUsersRemoved)
+        continue;
+
+      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.
+      const ScopArrayInfo *SAI = MA->getScopArrayInfo();
+      removeScopArrayInfo(SAI);
+
+      Stmt.removeMemoryAccess(MA, true);
+    }
+  }
+}
+
+void Scop::simplifyScalarAccesses() {
+  // 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();
+
+  // 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.
+  removeRecomputableScalarReads();
+
+  // 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.
+  removeUnreadScalarWrites();
+}
+
+void Scop::removeScopArrayInfo(const ScopArrayInfo *SAI) {
+  ScopArrayInfoMap.erase(std::make_pair(SAI->getBasePtr(), SAI->isPHI()));
+}
+
 const ScopArrayInfo *
 Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType,
                                ArrayRef<const SCEV *> Sizes, bool IsPHI) {
   auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, IsPHI)];
   if (!SAI) {
     SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes, IsPHI,
                                 this));
   } else {

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()))
     if (const SCEV *Scev = SE.getSCEVAtScope(const_cast<Value *>(Old), L)) {
       if (!isa<SCEVCouldNotCompute>(Scev)) {
         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;
       }
     }
 
   return nullptr;
 }
 
 Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
-                                   LoopToScevMapT &LTS, Loop *L) const {
+                                   LoopToScevMapT &LTS, Loop *L, bool TryOnly) {
   // We assume constants never change.
   // This avoids map lookups for many calls to this function.
   if (isa<Constant>(Old))
     return const_cast<Value *>(Old);
 
   if (Value *New = GlobalMap.lookup(Old)) {
     if (Value *NewRemapped = GlobalMap.lookup(New))
       New = NewRemapped;
     if (Old->getType()->getScalarSizeInBits() <
         New->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 const_cast<Value *>(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 const_cast<Value *>(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, getLoopForInst(Inst));
+    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) {
       assert(OldPtrTy->getPointerElementType()->getPrimitiveSizeInBits() ==
                  NewPtrTy->getPointerElementType()->getPrimitiveSizeInBits() &&
              "Pointer types to elements with different size found");
       Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
     }
     return Address;
   }
 
-  return getNewValue(Stmt, Pointer, BBMap, LTS, getLoopForInst(Inst));
+  return getNewValue(Stmt, Pointer, BBMap, LTS, getLoopForStmt(Stmt));
 }
 
-Loop *BlockGenerator::getLoopForInst(const llvm::Instruction *Inst) {
-  return LI.getLoopFor(Inst->getParent());
+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;
 

 
 void BlockGenerator::generateScalarStore(ScopStmt &Stmt, StoreInst *Store,
                                          ValueMapT &BBMap, LoopToScevMapT &LTS,
                                          isl_id_to_ast_expr *NewAccesses) {
   auto *Pointer = Store->getPointerOperand();
   Value *NewPointer =
       generateLocationAccessed(Stmt, Store, Pointer, BBMap, LTS, NewAccesses);
   Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap, LTS,
-                                    getLoopForInst(Store));
+                                    getLoopForStmt(Stmt));
 
   if (DebugPrinting)
     RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to  ", NewPointer,
                                           ": ", ValueOperand, "\n");
 
   Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlignment());
 }
 
 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;
 
-  Loop *L = getLoopForInst(Inst);
+  Loop *L = getLoopForStmt(Stmt);
   if ((Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
       canSynthesize(Inst, &LI, &SE, &Stmt.getParent()->getRegion())) {
     // Synthesizable statements will be generated on-demand.
     return;
   }
 
   if (auto *Load = dyn_cast<LoadInst>(Inst)) {
     Value *NewLoad = generateScalarLoad(Stmt, Load, BBMap, LTS, NewAccesses);
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->begin());
+
+  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;
Value *BlockGenerator::getNewScalarValue(Value *ScalarValue, const Region &R,
   }
 
   if (Value *ScalarValueCopy = BBMap.lookup(ScalarValueInst))
     return /* Case (3a) */ ScalarValueCopy;
 
   if ((Stmt.isBlockStmt() &&
        Stmt.getBasicBlock() == ScalarValueInst->getParent()) ||
       (Stmt.isRegionStmt() && Stmt.getRegion()->contains(ScalarValueInst))) {
-    auto SynthesizedValue = trySynthesizeNewValue(
-        Stmt, ScalarValueInst, BBMap, LTS, getLoopForInst(ScalarValueInst));
+    auto SynthesizedValue = trySynthesizeNewValue(Stmt, ScalarValueInst, BBMap,
+                                                  LTS, getLoopForStmt(Stmt));
 
     if (SynthesizedValue)
       return SynthesizedValue;
   }
 
   // Case (3b)
   Value *Address = getOrCreateScalarAlloca(ScalarValueInst);
   ScalarValue = Builder.CreateLoad(Address, Address->getName() + ".reload");
void VectorBlockGenerator::generateLoad(
   VectorMap[Load] = NewLoad;
 }
 
 void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst,
                                          ValueMapT &VectorMap,
                                          VectorValueMapT &ScalarMaps) {
   int VectorWidth = getVectorWidth();
   Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap,
-                                     ScalarMaps, getLoopForInst(Inst));
+                                     ScalarMaps, getLoopForStmt(Stmt));
 
   assert(isa<CastInst>(Inst) && "Can not generate vector code for instruction");
 
   const CastInst *Cast = dyn_cast<CastInst>(Inst);
   VectorType *DestType = VectorType::get(Inst->getType(), VectorWidth);
   VectorMap[Inst] = Builder.CreateCast(Cast->getOpcode(), NewOperand, DestType);
 }
 
 void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst,
                                           ValueMapT &VectorMap,
                                           VectorValueMapT &ScalarMaps) {
-  Loop *L = getLoopForInst(Inst);
+  Loop *L = getLoopForStmt(Stmt);
   Value *OpZero = Inst->getOperand(0);
   Value *OpOne = Inst->getOperand(1);
 
   Value *NewOpZero, *NewOpOne;
   NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L);
   NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L);
 
   Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne,
                                        Inst->getName() + "p_vec");
   VectorMap[Inst] = NewInst;
 }
 
 void VectorBlockGenerator::copyStore(
     ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap,
     VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
   const MemoryAccess &Access = Stmt.getAccessFor(Store);
 
   auto *Pointer = Store->getPointerOperand();
   Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap,
-                                 ScalarMaps, getLoopForInst(Store));
+                                 ScalarMaps, getLoopForStmt(Stmt));
 
   // Make sure we have scalar values available to access the pointer to
   // the data location.
   extractScalarValues(Store, VectorMap, ScalarMaps);
 
   if (Access.isStrideOne(isl_map_copy(Schedule))) {
     Type *VectorPtrType = getVectorPtrTy(Pointer, getVectorWidth());
     Value *NewPointer = generateLocationAccessed(
void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   // Create a dedicated entry for the region where we can reload all demoted
   // inputs.
   BasicBlock *EntryBB = R->getEntry();
   BasicBlock *EntryBBCopy =
       SplitBlock(Builder.GetInsertBlock(), Builder.GetInsertPoint(), &DT, &LI);
   EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
   Builder.SetInsertPoint(EntryBBCopy->begin());
 
   generateScalarLoads(Stmt, RegionMaps[EntryBBCopy]);
 
   for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
     if (!R->contains(*PI))
       BlockMap[*PI] = EntryBBCopy;
 
   // Iterate over all blocks in the region in a breadth-first search.
   std::deque<BasicBlock *> Blocks;
   SmallPtrSet<BasicBlock *, 8> SeenBlocks;
   Blocks.push_back(EntryBB);
if (StmtR->contains(IncomingBB)) {
     assert(RegionMaps.count(BBCopy) &&
            "Incoming PHI block did not have a BBMap");
     ValueMapT &BBCopyMap = RegionMaps[BBCopy];
 
     Value *Op = PHI->getIncomingValueForBlock(IncomingBB);
 
     auto OldIP = Builder.GetInsertPoint();
     Builder.SetInsertPoint(BBCopy->getTerminator());
-    OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForInst(PHI));
+    OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));
     Builder.SetInsertPoint(OldIP);
   } else {
 
     if (PHICopy->getBasicBlockIndex(BBCopy) >= 0)
       return;
 
     Value *PHIOpAddr = getOrCreatePHIAlloca(const_cast<PHINode *>(PHI));
     OpCopy = new LoadInst(PHIOpAddr, PHIOpAddr->getName() + ".reload",

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-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_2 = load i64, i64* %init_ptr
   %init_sum = add i64 %init, %init_2
 ; CHECK:      Stmt_for_j
-; CHECK:           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-NOT:       [Scalar: 1]
+; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:          [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] };
+; CHECK-NOT:       [Scalar: 1]
   %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
   store i64 %init_sum, 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/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-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/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;

 entry.next:
 ; CHECK-NOT:      Stmt_entry_next
   %init = load i64, i64* %init_ptr
   br label %for.j
 
 for.j:
   %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
 ; CHECK:      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]
   %init_plus_two = add i64 %init, 2
   %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:
; CHECK-NOT:      Stmt_entry_next
   %init = load i64, i64* %init_ptr
   br label %for.j
 
 for.j:
 ; CHECK:      Stmt_for_j
   %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ]
   %scevgep = getelementptr i64, i64* %A, i64 %indvar.j
   store i64 %init, i64* %scevgep
-; 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]
   %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:
   %exitcond.i = icmp eq i64 %indvar.i.next, %N
   br i1 %exitcond.i, label %return, label %for.i
 
 return:
   ret void
 }

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
+}