Introduce the ScopExpander as a SCEVExpander replacement

[jdoerfert]

Summary

The SCEVExpander cannot deal with all SCEVs Polly allows in all kinds
of expressions. To this end we introduce a ScopExpander that handles
the additional expressions separatly and falls back to the
SCEVExpander for everything else.

[jdoerfert]

Some comments.

lib/CodeGen/BlockGenerators.cpp

387 ↗

(On Diff #32253)

This is needed as we otherwise think the new instructions are escape users, however I think we have to create enforce a new and initially empty entering block now.

lib/Support/ScopHelper.cpp

286 ↗

(On Diff #32253)

Not is missing.

349 ↗

(On Diff #32253)

left over

[hfinkel]

The SCEVExpander cannot deal with all SCEVs Polly allows in all kinds
of expressions. To this end we introduce a ScopExpander that handles
the additional expressions separatly and falls back to the
SCEVExpander for everything else.

Shouldn't you just enhance SCEVExpander?

[grosser]

The SCEVExpander cannot deal with all SCEVs Polly allows in all kinds

of expressions. To this end we introduce a ScopExpander that handles

the additional expressions separatly and falls back to the

SCEVExpander for everything else.

Shouldn't you just enhance SCEVExpander?

Hi Hal,

thanks for jumping in. The point is that Polly starts to support thinks that go beyond what we
expression in SCEV generally. The current expressions we are facing, sDiv and sRem, could probably be added
to SCEV and consequently the SCEVExpander as well, but the next step will be piecewise expressions
such as a < b ? c : d. I am less convinced this really needs to be added to SCEV. Or at least,
I feel that we better keep this in Polly for a while, gain some experience, and move it if the
added value of this becomes really visible. In general I am trying to push as much of the stuff we
are doing directly into LLVM, but at the same time I feel we need to make sure we don't create too
much code that is only useful for Polly ATM.

I would be interested if you agree/disagree with this reasoning.

Best,
Tobias

[hfinkel]

In D12066#225379, @grosser wrote:

The SCEVExpander cannot deal with all SCEVs Polly allows in all kinds

of expressions. To this end we introduce a ScopExpander that handles

the additional expressions separatly and falls back to the

SCEVExpander for everything else.

Shouldn't you just enhance SCEVExpander?

Hi Hal,

thanks for jumping in.

No problem ;)

The point is that Polly starts to support thinks that go beyond what we
expression in SCEV generally. The current expressions we are facing, sDiv and sRem, could probably be added
to SCEV and consequently the SCEVExpander as well, but the next step will be piecewise expressions
such as a < b ? c : d. I am less convinced this really needs to be added to SCEV. Or at least,
I feel that we better keep this in Polly for a while, gain some experience, and move it if the
added value of this becomes really visible. In general I am trying to push as much of the stuff we
are doing directly into LLVM, but at the same time I feel we need to make sure we don't create too
much code that is only useful for Polly ATM.

I would be interested if you agree/disagree with this reasoning.

How are you representing these new SCEV-like nodes? This code seems to look though SCEV unknowns that happen to be sdiv/srem instructions and re-expand the operands. I don't understand why the operands would not otherwise be available (unless these are uninserted instructions -- in which case, I'd think that adding more SCEV subclasses would be a better design -- but maybe I'm overlooking some downside to that).

Best,
Tobias

[sanjoy]

lib/Support/ScopHelper.cpp

292 ↗

(On Diff #32253)

I don't grok how Polly uses SCEVs, but won't LHS be identical to Inst->getOperand(0) here? Likewise for RHS and Inst->getOperand(1)? Why can't this function just return E->getValue() (after which ScopExpander::expandCodeFor should become equivalent to SCEVExpander::expandCodeFor)?

[jdoerfert]

Let me try to comment on both questions (by Hal as well as Sanjoy) at once.

@hfinkel regarding how we model these additions to SCEV:

We use SCEVs as an intermediate step from IR to isl expressions (more precicly isl piecewise affince functions [isl_pw_aff]). However, these piecewise affine functions can express things SCEVs cannot and vice versa. With SDiv and SRem (where the right hand side is a constant) we allowed Polly to represent more than SCEVs as piecewise affine functions. To this end we have to check the SCEVUnknowns each time and decide if they are parameters of the region we analyze (then we treat them as unknown values) or if we can model them. The latter is only supported for the SDiv and SRem at the moment but will be extended at some point to more (e.g. there is a patch that allows bitwise operations etc.).

@sanjoy & @hfinkel regarding this patch and its purpose:

So far the modeling as described above was sufficent to represent SDiv and SRem operations in the mathematical model and to generate a new, optimized code from it. However, recently we noticed a bug in our code generation if the SDiv or SRem operation are part of a parameter that we assume to be copyable. That means we think we can just copy the (side effect free!) computation of the parameter in front of our optimized code version without worrying where the orginal computation was. But if there was a SDiv or SRem in the computation and these did not dominate the analyzed region but where part of it, we generated invalid code when we expanded the parameter SCEV in front of the optimized code region. It was invalid because it referenced the SDiv or SRem in the original region that did not dominate the optimized region. [Note that during our analysis we looked through the SDiv and SRem instruction but SCEVExpander stopped with them]. To this end we introduced the ScopExpander which will expand SCEVs as the SCEVExpander but in case of SDiv or SRem instructions move the expansions in front of the SCoP and expand the SDiv or SRem there instead of just using the original instruction.

[jdoerfert]

Fixed smaller mistakes, added missing comment and two new fast paths.

[Meinersbur]

AFAIU you always insert the new instructions into the entering block. What if the argument of SDiv/SRem depends of an inner loop induction variable (An point raised by Tobias in a mailing list discussion)?

lib/Support/ScopHelper.cpp

261 ↗

(On Diff #32271)

ScopExpander doesn't need the Scop, only the Region.

294 ↗

(On Diff #32271)

Introduce getStartIP() which sets StartIP if nullptr ?

[grosser]

Hi Johannes,

this patch goes in the right direction. I have a couple of comments, but most of them are minor. Can you submit another version, such that I can have a final look. (mostly interested in the handleOutsideUsers test case).

Thank you,
Tobias

include/polly/CodeGen/IslExprBuilder.h

96 ↗

(On Diff #32271)

Expander is not a parameter any more.

include/polly/Support/ScopHelper.h

82 ↗

(On Diff #32271)

"all SCEV additions"?

you mean extended "to handle Polly specific operations not handled by SCEVExpander"?

84 ↗

(On Diff #32271)

internally

89 ↗

(On Diff #32271)

It might still make sense to document the parameters briefly. At least I do not know them by heart.

lib/CodeGen/BlockGenerators.cpp

127 ↗

(On Diff #32271)

Do we happen to have a test case covering this use? Meaning a loop-variant srem node with data-dependences accross basic-blocks that would crash without this addition?

387 ↗

(On Diff #32271)

If I drop this change, all test cases pass. Could you possibly add a test case that illustrates why this change is needed. (It is not 100% clear to me).

lib/Support/ScopHelper.cpp

258 ↗

(On Diff #32271)

Maybe add a comment that explains why we have to extend the SCEVExpander (we can probably resue the replies to Hal and Sanjay).

268 ↗

(On Diff #32271)

Why do we not use the ScopExpander inside the region. Even in the region we may generate code at a location which is not dominated by all SCEVUnknown expressions in the SCEV.

270 ↗

(On Diff #32271)

Why don't we use the ScopExpander in the region? Even inside the region we
may work at places where I does not dominate all SCEVUnknowns, no?

[jdoerfert]

Comments and the new version will follow shortly.

include/polly/Support/ScopHelper.h

82 ↗

(On Diff #32271)

Yes, I rephrased.

lib/CodeGen/BlockGenerators.cpp

127 ↗

(On Diff #32271)

No and I do not think we would crash here anyway. I think only the SDiv/SRem is a parameter of the SCoP case can crash. However, I changed all Expander locations for two reasons:

1. We have a clear interface now that hides how we actually expand code.
2. We have one location where we need to handle new features later on.

If you think it is better to only use the new interface where it is necessary I am almost certain this change and the ones in the IslExprBuilder can be avoided.

387 ↗

(On Diff #32271)

I am unsure because I cannot reproduce it atm. I will remove it run lnt and if it passes I will just keep this in mind.

lib/Support/ScopHelper.cpp

270 ↗

(On Diff #32271)

Like I said above. I don't think so. Even if that might be the case, the current handling might not work then. For now I see 3 cases we expands SCEVs:

1. IslExprBuilder: Here we create (mainly) loop bounds etc. (inside the region) and the problem should not occure since we generate the full expression (except the parameters) from scratch.
2. BlockGenerator: Here we synthezise values during code generation (inside the region) but again, everything except the parameters are generated from scratch (afaik).
3. IslNodeBuilder: Here we generate code for the parameters (in front of the region) and we can crash. However, only if the parameters contains instructions in the region.

If the above observation is correct the code should be too. If not or we extend/change Polly at some point the new structure should allows us to modify the behavior of the SCEV expansion pretty easily.

294 ↗

(On Diff #32271)

Done in the constructor.

[jdoerfert]

Added test cases and modified according to the review.

[grosser]

jdoerfert wrote:

grosser wrote:

Do we happen to have a test case covering this use? Meaning a loop-variant srem node with data-dependences accross basic-blocks that would crash without this addition?

No and I do not think we would crash here anyway. I think only the SDiv/SRem is a parameter of the SCoP case can crash. However, I changed all Expander locations for two reasons:

1. We have a clear interface now that hides how we actually expand code.
2. We have one location where we need to handle new features later on.

OK, that's fine.

Comment at: lib/Support/ScopHelper.cpp:270
@@ +269,3 @@
+ if (!S.getRegion().contains(I))
+ E = visit(E);

+ return Expander.expandCodeFor(E, Ty, I);

grosser wrote:

Why don't we use the ScopExpander in the region? Even inside the region we
may work at places where I does not dominate all SCEVUnknowns, no?

Like I said above. I don't think so. Even if that might be the case, the current handling might not work then. For now I see 3 cases we expands SCEVs:

1. IslExprBuilder: Here we create (mainly) loop bounds etc. (inside the region) and the problem should not occure since we generate the full expression (except the parameters) from scratch.
2. BlockGenerator: Here we synthezise values during code generation (inside the region) but again, everything except the parameters are generated from scratch (afaik).
3. IslNodeBuilder: Here we generate code for the parameters (in front of the region) and we can crash. However, only if the parameters contains instructions in the region.

If the above observation is correct the code should be too. If not or we extend/change Polly at some point the new structure should allows us to modify the behavior of the SCEV expansion pretty easily.

A test case for this is test/Isl/CodeGen/srem-in-other-bb.ll.

It works today as we IndependentBlocks just moves the full operand tree into the
right location. If we disable independent blocks entirely, scalar dependences
are introduced and the values are propagated via memory. So it seems the
way we are currently handling such cases is save, but could be improved in the future
by possibly dropping independent blocks entirely, not model the memory dependences and
then fully expand these extended SCEV expressions during code generation.

However, I believe this is out of scope for this patch.

Feel free to commit if this patch passes LNT for you.

Best,
Tobias

[grosser]

jdoerfert updated this revision to Diff 32394.
jdoerfert marked 4 inline comments as done.
jdoerfert added a comment.

Added test cases and modified according to the review.

http://reviews.llvm.org/D12066

Files:

include/polly/CodeGen/IslExprBuilder.h
include/polly/CodeGen/IslNodeBuilder.h
include/polly/Support/ScopHelper.h
lib/CodeGen/BlockGenerators.cpp
lib/CodeGen/IslExprBuilder.cpp
lib/CodeGen/IslNodeBuilder.cpp
lib/Support/ScopHelper.cpp
test/Isl/CodeGen/inner_scev.ll
test/Isl/CodeGen/inner_scev_2.ll
test/Isl/CodeGen/inner_scev_sdiv_1.ll
test/Isl/CodeGen/inner_scev_sdiv_2.ll
test/Isl/CodeGen/inner_scev_sdiv_3.ll
test/Isl/CodeGen/inner_scev_sdiv_in_lb.ll
test/Isl/CodeGen/inner_scev_sdiv_in_lb_invariant.ll
test/Isl/CodeGen/inner_scev_sdiv_in_rtc.ll

+/ The SCEVExpander will not generate any code for an existing SDiv/SRem
+/ instruction but just use it, if it is references as a SCEVUnknown. We want

referenced

+/ however to generate new code if the instruction is in the analyzed region
+/ and we generate code outside/infront of that region. Hence, we generate the
+/ code for the SDiv/SRem operands in front of the analyzed region and then
+/ create a new SDiv/SRem operation there too.
+struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
+ friend struct SCEVVisitor<ScopExpander, const SCEV *>;
+
+ explicit ScopExpander(const Region &R, ScalarEvolution &SE,
+ const DataLayout &DL, const char *Name)
+ : Expander(SCEVExpander(SE, DL, Name)), SE(SE), Name(Name), R(R) {}
+
+ Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
+ If we generate code in the region we will immediately fall back to the
+ SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
+ needed replace them by copies computed in the entering block.
+ if (!R.contains(I))
+ E = visit(E);
+ return Expander.expandCodeFor(E, Ty, I);
+ }
+
+private:
+ SCEVExpander Expander;
+ ScalarEvolution &SE;
+ const char *Name;
+ const Region &R;
+
+ const SCEV *visitUnknown(const SCEVUnknown *E) {
+ Instruction *Inst = dyn_cast<Instruction>(E->getValue());
+ if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
+ Inst->getOpcode() != Instruction::SDiv))
+ return E;
+
+ if (!R.contains(Inst))
+ return E;
+
+ Instruction *StartIP = R.getEnteringBlock()->getTerminator();
+
+ const SCEV *LHSScev = visit(SE.getSCEV(Inst->getOperand(0)));
+ const SCEV *RHSScev = visit(SE.getSCEV(Inst->getOperand(1)));
+
+ Value *LHS = Expander.expandCodeFor(LHSScev, E->getType(), StartIP);
+ Value *RHS = Expander.expandCodeFor(RHSScev, E->getType(), StartIP);
+
+ Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),
+ LHS, RHS, Inst->getName() + Name, StartIP);
+ return SE.getSCEV(Inst);
+ }
+
+ / The following functions will just traverse the SCEV and rebuild it with
+ / the new operands returned by the traversal.
+ /
+ /{
+ const SCEV *visitConstant(const SCEVConstant *E) { return E; }
+ const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
+ return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
+ }
+ const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
+ return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
+ }
+ const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
+ return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
+ }
+ const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
+ return SE.getUDivExpr(visit(E->getLHS()), visit(E->getRHS()));
+ }
+ const SCEV *visitAddExpr(const SCEVAddExpr *E) {
+ SmallVector<const SCEV *, 4> NewOps;
+ for (const SCEV *Op : E->operands())
+ NewOps.push_back(visit(Op));
+ return SE.getAddExpr(NewOps);
+ }
+ const SCEV *visitMulExpr(const SCEVMulExpr *E) {
+ SmallVector<const SCEV *, 4> NewOps;
+ for (const SCEV *Op : E->operands())
+ NewOps.push_back(visit(Op));
+ return SE.getMulExpr(NewOps);
+ }
+ const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
+ SmallVector<const SCEV *, 4> NewOps;
+ for (const SCEV *Op : E->operands())
+ NewOps.push_back(visit(Op));
+ return SE.getUMaxExpr(NewOps);
+ }
+ const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
+ SmallVector<const SCEV *, 4> NewOps;
+ for (const SCEV *Op : E->operands())
+ NewOps.push_back(visit(Op));
+ return SE.getSMaxExpr(NewOps);
+ }
+ const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
+ SmallVector<const SCEV *, 4> NewOps;
+ for (const SCEV *Op : E->operands())
+ NewOps.push_back(visit(Op));
+ return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
+ }
+ /}
+};

+/// This wrapper will internally call the SCEVExpander but also make sure that

makes sure

Tobias

polly/trunk/include/polly/CodeGen/IslExprBuilder.h

 #ifndef POLLY_ISL_EXPR_BUILDER_H
 #define POLLY_ISL_EXPR_BUILDER_H
 
 #include "polly/CodeGen/IRBuilder.h"
 #include "llvm/ADT/MapVector.h"
 #include "isl/ast.h"
 
 namespace llvm {
-class SCEVExpander;
+class DataLayout;
+class ScalarEvolution;
 }
 
 namespace polly {
 
 /// @brief LLVM-IR generator for isl_ast_expr[essions]
 ///
 /// This generator generates LLVM-IR that performs the computation described by
 /// an isl_ast_expr[ession].
public:
   /// @param Builder The IRBuilder used to construct the isl_ast_expr[ession].
   ///                The insert location of this IRBuilder defines WHERE the
   ///                corresponding LLVM-IR is generated.
   ///
   /// @param IDToValue The isl_ast_expr[ession] may reference parameters or
   ///                  variables (identified by an isl_id). The IDTOValue map
   ///                  specifies the LLVM-IR Values that correspond to these
   ///                  parameters and variables.
-  /// @param Expander  A SCEVExpander to create the indices for multi
-  ///                  dimensional accesses.
-  IslExprBuilder(PollyIRBuilder &Builder, IDToValueTy &IDToValue,
-                 llvm::SCEVExpander &Expander, llvm::DominatorTree &DT,
-                 llvm::LoopInfo &LI)
-      : Builder(Builder), IDToValue(IDToValue), Expander(Expander), DT(DT),
+  IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue,
+                 const llvm::DataLayout &DL, llvm::ScalarEvolution &SE,
+                 llvm::DominatorTree &DT, llvm::LoopInfo &LI)
+      : S(S), Builder(Builder), IDToValue(IDToValue), DL(DL), SE(SE), DT(DT),
         LI(LI) {}
 
   /// @brief Create LLVM-IR for an isl_ast_expr[ession].
   ///
   /// @param Expr The ast expression for which we generate LLVM-IR.
   ///
   /// @return The llvm::Value* containing the result of the computation.
   llvm::Value *create(__isl_take isl_ast_expr *Expr);
public:
   /// The type needs to be large enough to hold all possible input and all
   /// possible output values.
   ///
   /// @param Expr The expression for which to find the type.
   /// @return The type with which the expression should be computed.
   llvm::IntegerType *getType(__isl_keep isl_ast_expr *Expr);
 
 private:
+  Scop &S;
+
   PollyIRBuilder &Builder;
   IDToValueTy &IDToValue;
 
-  /// @brief A SCEVExpander to translate dimension sizes to llvm values.
-  llvm::SCEVExpander &Expander;
-
+  const llvm::DataLayout &DL;
+  llvm::ScalarEvolution &SE;
   llvm::DominatorTree &DT;
   llvm::LoopInfo &LI;
 
   llvm::Value *createOp(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpUnary(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr);

polly/trunk/include/polly/CodeGen/IslNodeBuilder.h

 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_ISL_NODE_BUILDER_H
 #define POLLY_ISL_NODE_BUILDER_H
 
 #include "polly/CodeGen/BlockGenerators.h"
 #include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/CodeGen/LoopGenerators.h"
-#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "isl/ctx.h"
 #include "isl/union_map.h"
 
 using namespace polly;
 using namespace llvm;
 
 struct isl_ast_node;
 
 class IslNodeBuilder {
 public:
   IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
                  const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE,
                  DominatorTree &DT, Scop &S)
-      : S(S), Builder(Builder), Annotator(Annotator), Rewriter(SE, DL, "polly"),
-        ExprBuilder(Builder, IDToValue, Rewriter, DT, LI),
+      : S(S), Builder(Builder), Annotator(Annotator),
+        ExprBuilder(S, Builder, IDToValue, DL, SE, DT, LI),
         BlockGen(Builder, LI, SE, DT, ScalarMap, PHIOpMap, EscapeMap,
                  &ExprBuilder),
         RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT) {}
 
   ~IslNodeBuilder() {}
 
   void addParameters(__isl_take isl_set *Context);
   void create(__isl_take isl_ast_node *Node);
 
   /// @brief Finalize code generation for the SCoP @p S.
   ///
   /// @see BlockGenerator::finalizeSCoP(Scop &S)
   void finalizeSCoP(Scop &S) { BlockGen.finalizeSCoP(S, ValueMap); }
 
   IslExprBuilder &getExprBuilder() { return ExprBuilder; }
 
 private:
   Scop &S;
   PollyIRBuilder &Builder;
   ScopAnnotator &Annotator;
 
-  /// @brief A SCEVExpander to create llvm values from SCEVs.
-  SCEVExpander Rewriter;
-
   IslExprBuilder ExprBuilder;
 
   /// @brief Maps used by the block and region generator to demote scalars.
   ///
   ///@{
 
   /// @brief See BlockGenerator::ScalarMap.
   BlockGenerator::ScalarAllocaMapTy ScalarMap;

polly/trunk/include/polly/Support/ScopHelper.h

 class ScalarEvolution;
 class SCEV;
 class Value;
 class PHINode;
 class Region;
 class Pass;
 class BasicBlock;
 class StringRef;
+class DataLayout;
 class DominatorTree;
 class RegionInfo;
 class ScalarEvolution;
 }
 
 namespace polly {
 class Scop;
 /// Temporary Hack for extended regiontree.

 
 /// @brief Split the entry block of a function to store the newly inserted
 ///        allocations outside of all Scops.
 ///
 /// @param EntryBlock The entry block of the current function.
 /// @param P          The pass that currently running.
 ///
 void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P);
+
+/// @brief Wrapper for SCEVExpander extended to all Polly features.
+///
+/// This wrapper will internally call the SCEVExpander but also makes sure that
+/// all additional features not represented in SCEV (e.g., SDiv/SRem are not
+/// black boxes but can be part of the function) will be expanded correctly.
+///
+/// The parameters are the same as for the creation of a SCEVExpander as well
+/// as the call to SCEVExpander::expandCodeFor:
+///
+/// @param S    The current Scop.
+/// @param SE   The Scalar Evolution pass.
+/// @param DL   The module data layout.
+/// @param Name The suffix added to the new instruction names.
+/// @param E    The expression for which code is actually generated.
+/// @param Ty   The type of the resulting code.
+/// @param IP   The insertion point for the new code.
+llvm::Value *expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
+                           const llvm::DataLayout &DL, const char *Name,
+                           const llvm::SCEV *E, llvm::Type *Ty,
+                           llvm::Instruction *IP);
 }
 #endif

polly/trunk/lib/CodeGen/BlockGenerators.cpp

 #include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/Options.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "isl/aff.h"
 #include "isl/ast.h"
 #include "isl/ast_build.h"
 #include "isl/set.h"
 #include <deque>
Value *BlockGenerator::getNewValue(ScopStmt &Stmt, const Value *Old,
   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);
         ValueToValueMap VTV;
         VTV.insert(BBMap.begin(), BBMap.end());
         VTV.insert(GlobalMap.begin(), GlobalMap.end());
         NewScev = SCEVParameterRewriter::rewrite(NewScev, SE, VTV);
-        SCEVExpander Expander(SE, Stmt.getParent()
-                                      ->getRegion()
-                                      .getEntry()
-                                      ->getParent()
-                                      ->getParent()
-                                      ->getDataLayout(),
-                              "polly");
-        assert(Builder.GetInsertPoint() != Builder.GetInsertBlock()->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 = Expander.expandCodeFor(NewScev, Old->getType(),
-                                                 Builder.GetInsertPoint());
+        Value *Expanded =
+            expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), IP);
 
         BBMap[Old] = Expanded;
         return Expanded;
       }
     }
 
   // A scop-constant value defined by a global or a function parameter.
   if (isa<GlobalValue>(Old) || isa<Argument>(Old))
if (!Addr) {
     Addr->insertBefore(EntryBB->getFirstInsertionPt());
   }
 
   return Addr;
 }
 
 void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst,
                                         Value *InstCopy) {
+
   EscapeUserVectorTy EscapeUsers;
   for (User *U : Inst->users()) {
 
     // Non-instruction user will never escape.
     Instruction *UI = dyn_cast<Instruction>(U);
     if (!UI)
       continue;
 

polly/trunk/lib/CodeGen/IslExprBuilder.cpp

 //===------ IslExprBuilder.cpp ----- Code generate isl AST expressions ----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
-#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "polly/Support/ScopHelper.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 using namespace polly;
 
 Type *IslExprBuilder::getWidestType(Type *T1, Type *T2) {
   assert(isa<IntegerType>(T1) && isa<IntegerType>(T2));
for (unsigned u = 1, e = isl_ast_expr_get_op_n_arg(Expr); u < e; u++) {
     }
 
     // For every but the last dimension multiply the size, for the last
     // dimension we can exit the loop.
     if (u + 1 >= e)
       break;
 
     const SCEV *DimSCEV = SAI->getDimensionSize(u - 1);
-    Value *DimSize = Expander.expandCodeFor(DimSCEV, DimSCEV->getType(),
-                                            Builder.GetInsertPoint());
+    Value *DimSize =
+        expandCodeFor(S, SE, DL, "polly", DimSCEV, DimSCEV->getType(),
 
     Type *Ty = getWidestType(DimSize->getType(), IndexOp->getType());
 
     if (Ty != IndexOp->getType())
       IndexOp = Builder.CreateSExtOrTrunc(IndexOp, Ty,
                                           "polly.access.sext." + BaseName);
     if (Ty != DimSize->getType())
       DimSize = Builder.CreateSExtOrTrunc(DimSize, Ty,

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

 #include "polly/Support/GICHelper.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/TempScopInfo.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/PostDominators.h"
-#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "isl/aff.h"
 #include "isl/ast.h"
while (L != nullptr) {
     L = L->getParentLoop();
   }
 
   isl_set_free(Context);
 }
 
 Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
   Instruction *InsertLocation = --(Builder.GetInsertBlock()->end());
-  return Rewriter.expandCodeFor(Expr, Expr->getType(), InsertLocation);
+  return expandCodeFor(S, SE, DL, "polly", Expr, Expr->getType(),
+                       InsertLocation);
 }

polly/trunk/lib/Support/ScopHelper.cpp

 //===----------------------------------------------------------------------===//
 
 #include "polly/Support/ScopHelper.h"
 #include "polly/ScopInfo.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
+using namespace polly;
 
 #define DEBUG_TYPE "polly-scop-helper"
 
 // Helper function for Scop
 // TODO: Add assertion to not allow parameter to be null
 //===----------------------------------------------------------------------===//
 // Temporary Hack for extended region tree.
 // Cast the region to loop if there is a loop have the same header and exit.
void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
   RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
   RegionInfo *RI = RIP ? &RIP->getRegionInfo() : nullptr;
 
   // splitBlock updates DT, LI and RI.
   splitBlock(EntryBlock, I, DT, LI, RI);
 }
+
+/// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
+/// instruction but just use it, if it is referenced as a SCEVUnknown. We want
+/// however to generate new code if the instruction is in the analyzed region
+/// and we generate code outside/in front of that region. Hence, we generate the
+/// code for the SDiv/SRem operands in front of the analyzed region and then
+/// create a new SDiv/SRem operation there too.
+struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
+  friend struct SCEVVisitor<ScopExpander, const SCEV *>;
+
+  explicit ScopExpander(const Region &R, ScalarEvolution &SE,
+                        const DataLayout &DL, const char *Name)
+      : Expander(SCEVExpander(SE, DL, Name)), SE(SE), Name(Name), R(R) {}
+
+  Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
+    // If we generate code in the region we will immediately fall back to the
+    // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
+    // needed replace them by copies computed in the entering block.
+    if (!R.contains(I))
+      E = visit(E);
+    return Expander.expandCodeFor(E, Ty, I);
+  }
+
+private:
+  SCEVExpander Expander;
+  ScalarEvolution &SE;
+  const char *Name;
+  const Region &R;
+
+  const SCEV *visitUnknown(const SCEVUnknown *E) {
+    Instruction *Inst = dyn_cast<Instruction>(E->getValue());
+    if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
+                  Inst->getOpcode() != Instruction::SDiv))
+      return E;
+
+    if (!R.contains(Inst))
+      return E;
+
+    Instruction *StartIP = R.getEnteringBlock()->getTerminator();
+
+    const SCEV *LHSScev = visit(SE.getSCEV(Inst->getOperand(0)));
+    const SCEV *RHSScev = visit(SE.getSCEV(Inst->getOperand(1)));
+
+    Value *LHS = Expander.expandCodeFor(LHSScev, E->getType(), StartIP);
+    Value *RHS = Expander.expandCodeFor(RHSScev, E->getType(), StartIP);
+
+    Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),
+                                  LHS, RHS, Inst->getName() + Name, StartIP);
+    return SE.getSCEV(Inst);
+  }
+
+  /// The following functions will just traverse the SCEV and rebuild it with
+  /// the new operands returned by the traversal.
+  ///
+  ///{
+  const SCEV *visitConstant(const SCEVConstant *E) { return E; }
+  const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
+    return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
+  }
+  const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
+    return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
+  }
+  const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
+    return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
+  }
+  const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
+    return SE.getUDivExpr(visit(E->getLHS()), visit(E->getRHS()));
+  }
+  const SCEV *visitAddExpr(const SCEVAddExpr *E) {
+    SmallVector<const SCEV *, 4> NewOps;
+    for (const SCEV *Op : E->operands())
+      NewOps.push_back(visit(Op));
+    return SE.getAddExpr(NewOps);
+  }
+  const SCEV *visitMulExpr(const SCEVMulExpr *E) {
+    SmallVector<const SCEV *, 4> NewOps;
+    for (const SCEV *Op : E->operands())
+      NewOps.push_back(visit(Op));
+    return SE.getMulExpr(NewOps);
+  }
+  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
+    SmallVector<const SCEV *, 4> NewOps;
+    for (const SCEV *Op : E->operands())
+      NewOps.push_back(visit(Op));
+    return SE.getUMaxExpr(NewOps);
+  }
+  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
+    SmallVector<const SCEV *, 4> NewOps;
+    for (const SCEV *Op : E->operands())
+      NewOps.push_back(visit(Op));
+    return SE.getSMaxExpr(NewOps);
+  }
+  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
+    SmallVector<const SCEV *, 4> NewOps;
+    for (const SCEV *Op : E->operands())
+      NewOps.push_back(visit(Op));
+    return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
+  }
+  ///}
+};
+
+Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
+                            const char *Name, const SCEV *E, Type *Ty,
+                            Instruction *IP) {
+  ScopExpander Expander(S.getRegion(), SE, DL, Name);
+  return Expander.expandCodeFor(E, Ty, IP);
+}

polly/trunk/test/Isl/CodeGen/inner_scev.ll

-; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s
-;
-; Excerpt from the test-suite's oggenc reduced using bugpoint.
-;
-; It features a SCEV value using %div44 for the inner loop (for.body.51 =>
-; for.cond.60.preheader) that is computed within the body of the outer loop
-; (for.cond.30.preheader => for.cond.60.preheader). CodeGenerator would add a
-; computation of the SCEV to before the scop that references %div44, which is
-; not available then.
-;
-; XFAIL: *
-;
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @_vorbis_apply_window(float* %d) {
-entry:
-  %0 = load float*, float** undef, align 8
-  %div23.neg = sdiv i64 0, -4
-  %sub24 = add i64 0, %div23.neg
-  br label %for.cond.30.preheader
-
-for.cond.30.preheader:                            ; preds = %for.body, %entry
-  %sext = shl i64 %sub24, 32
-  %conv48.74 = ashr exact i64 %sext, 32
-  %cmp49.75 = icmp slt i64 %conv48.74, 0
-  br i1 %cmp49.75, label %for.body.51.lr.ph, label %for.cond.60.preheader
-
-for.body.51.lr.ph:                                ; preds = %for.cond.30.preheader
-  %div44 = sdiv i64 0, 2
-  %sub45 = add nsw i64 %div44, 4294967295
-  %1 = trunc i64 %sub45 to i32
-  %2 = sext i32 %1 to i64
-  br label %for.body.51
-
-for.cond.60.preheader:                            ; preds = %for.body.51, %for.cond.30.preheader
-  ret void
-
-for.body.51:                                      ; preds = %for.body.51, %for.body.51.lr.ph
-  %indvars.iv86 = phi i64 [ %2, %for.body.51.lr.ph ], [ undef, %for.body.51 ]
-  %arrayidx53 = getelementptr inbounds float, float* %0, i64 %indvars.iv86
-  %3 = load float, float* %arrayidx53, align 4
-  %arrayidx55 = getelementptr inbounds float, float* %d, i64 0
-  %mul56 = fmul float %3, undef
-  store float %mul56, float* %arrayidx55, align 4
-  br i1 false, label %for.body.51, label %for.cond.60.preheader
-}

polly/trunk/test/Isl/CodeGen/inner_scev_2.ll

-; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s | FileCheck %s
-; XFAIL: *
-;
-; The SCEV expression in this test case refers to a sequence of sdiv
-; instructions, which are part of different bbs in the SCoP. When code
-; generating the parameter expressions, the code that is generated by the SCEV
-; expander has still references to the in-scop instructions, which is invalid.
-
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @_vorbis_apply_window(float* %d, i64 %param) {
-entry:
-  %0 = load float*, float** undef, align 8
-  %div23.neg = sdiv i64 0, -4
-  %sub24 = add i64 0, %div23.neg
-  br label %for.cond.30.preheader
-
-for.cond.30.preheader:                            ; preds = %for.body, %entry
-  %sext = shl i64 %sub24, 32
-  %conv48.74 = ashr exact i64 %sext, 32
-  %div43 = sdiv i64 %param, 2
-  %cmp49.75 = icmp slt i64 %conv48.74, 0
-  br i1 %cmp49.75, label %for.body.51.lr.ph, label %for.cond.60.preheader
-
-for.body.51.lr.ph:                                ; preds = %for.cond.30.preheader
-  %div44 = sdiv i64 %div43, 2
-  %sub45 = add nsw i64 %div44, 4294967295
-  %1 = trunc i64 %sub45 to i32
-  %2 = sext i32 %1 to i64
-  br label %for.body.51
-
-for.cond.60.preheader:                            ; preds = %for.body.51, %for.cond.30.preheader
-  ret void
-
-for.body.51:                                      ; preds = %for.body.51, %for.body.51.lr.ph
-  %indvars.iv86 = phi i64 [ %2, %for.body.51.lr.ph ], [ undef, %for.body.51 ]
-  %arrayidx53 = getelementptr inbounds float, float* %0, i64 %indvars.iv86
-  %3 = load float, float* %arrayidx53, align 4
-  %arrayidx55 = getelementptr inbounds float, float* %d, i64 0
-  %mul56 = fmul float %3, undef
-  store float %mul56, float* %arrayidx55, align 4
-  br i1 false, label %for.body.51, label %for.cond.60.preheader
-}

polly/trunk/test/Isl/CodeGen/inner_scev_sdiv_1.ll

+; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s
+;
+; Excerpt from the test-suite's oggenc reduced using bugpoint.
+;
+; It features a SCEV value using %div44 for the inner loop (for.body.51 =>
+; for.cond.60.preheader) that is computed within the body of the outer loop
+; (for.cond.30.preheader => for.cond.60.preheader). CodeGenerator would add a
+; computation of the SCEV to before the scop that references %div44, which is
+; not available then.
+;
+; CHECK:      polly.split_new_and_old:
+; CHECK-NEXT:   %div23.neg.polly.copy = sdiv i64 0, -4
+;
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @_vorbis_apply_window(float* %d) {
+entry:
+  %0 = load float*, float** undef, align 8
+  %div23.neg = sdiv i64 0, -4
+  %sub24 = add i64 0, %div23.neg
+  br label %for.cond.30.preheader
+
+for.cond.30.preheader:                            ; preds = %for.body, %entry
+  %sext = shl i64 %sub24, 32
+  %conv48.74 = ashr exact i64 %sext, 32
+  %cmp49.75 = icmp slt i64 %conv48.74, 0
+  br i1 %cmp49.75, label %for.body.51.lr.ph, label %for.cond.60.preheader
+
+for.body.51.lr.ph:                                ; preds = %for.cond.30.preheader
+  %div44 = sdiv i64 0, 2
+  %sub45 = add nsw i64 %div44, 4294967295
+  %1 = trunc i64 %sub45 to i32
+  %2 = sext i32 %1 to i64
+  br label %for.body.51
+
+for.cond.60.preheader:                            ; preds = %for.body.51, %for.cond.30.preheader
+  ret void
+
+for.body.51:                                      ; preds = %for.body.51, %for.body.51.lr.ph
+  %indvars.iv86 = phi i64 [ %2, %for.body.51.lr.ph ], [ undef, %for.body.51 ]
+  %arrayidx53 = getelementptr inbounds float, float* %0, i64 %indvars.iv86
+  %3 = load float, float* %arrayidx53, align 4
+  %arrayidx55 = getelementptr inbounds float, float* %d, i64 0
+  %mul56 = fmul float %3, undef
+  store float %mul56, float* %arrayidx55, align 4
+  br i1 false, label %for.body.51, label %for.cond.60.preheader
+}

polly/trunk/test/Isl/CodeGen/inner_scev_sdiv_2.ll

+; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s | FileCheck %s
+;
+; The SCEV expression in this test case refers to a sequence of sdiv
+; instructions, which are part of different bbs in the SCoP. When code
+; generating the parameter expressions, the code that is generated by the SCEV
+; expander has still references to the in-scop instructions, which is invalid.
+;
+; CHECK:    polly.split_new_and_old:
+; CHECK-NOT:  = sdiv i64 0, -4
+; CHECK:      %div43polly = sdiv i64 %param, 2
+; CHECK:      %div44polly = sdiv i64 %div43polly, 2
+;
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @_vorbis_apply_window(float* %d, i64 %param) {
+entry:
+  %0 = load float*, float** undef, align 8
+  %div23.neg = sdiv i64 0, -4
+  %sub24 = add i64 0, %div23.neg
+  br label %for.cond.30.preheader
+
+for.cond.30.preheader:                            ; preds = %for.body, %entry
+  %sext = shl i64 %sub24, 32
+  %conv48.74 = ashr exact i64 %sext, 32
+  %div43 = sdiv i64 %param, 2
+  %cmp49.75 = icmp slt i64 %conv48.74, 0
+  br i1 %cmp49.75, label %for.body.51.lr.ph, label %for.cond.60.preheader
+
+for.body.51.lr.ph:                                ; preds = %for.cond.30.preheader
+  %div44 = sdiv i64 %div43, 2
+  %sub45 = add nsw i64 %div44, 4294967295
+  %1 = trunc i64 %sub45 to i32
+  %2 = sext i32 %1 to i64
+  br label %for.body.51
+
+for.cond.60.preheader:                            ; preds = %for.body.51, %for.cond.30.preheader
+  ret void
+
+for.body.51:                                      ; preds = %for.body.51, %for.body.51.lr.ph
+  %indvars.iv86 = phi i64 [ %2, %for.body.51.lr.ph ], [ undef, %for.body.51 ]
+  %arrayidx53 = getelementptr inbounds float, float* %0, i64 %indvars.iv86
+  %3 = load float, float* %arrayidx53, align 4
+  %arrayidx55 = getelementptr inbounds float, float* %d, i64 0
+  %mul56 = fmul float %3, undef
+  store float %mul56, float* %arrayidx55, align 4
+  br i1 false, label %for.body.51, label %for.cond.60.preheader
+}

polly/trunk/test/Isl/CodeGen/inner_scev_sdiv_3.ll

+; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s | FileCheck %s
+;
+; This test case has a inner SCEV sdiv that will escape the SCoP. Just check we
+; do not crash and generate valid code.
+;
+; CHECK:    polly.split_new_and_old:
+;
+target triple = "x86_64-unknown-linux-gnu"
+
+define i64 @_vorbis_apply_window(float* %d, i64 %param) {
+entry:
+  %0 = load float*, float** undef, align 8
+  %div23.neg = sdiv i64 0, -4
+  %sub24 = add i64 0, %div23.neg
+  br label %for.cond.30.preheader
+
+for.cond.30.preheader:                            ; preds = %for.body, %entry
+  %sext = shl i64 %sub24, 32
+  %conv48.74 = ashr exact i64 %sext, 32
+  %div43 = sdiv i64 %param, 2
+  %cmp49.75 = icmp slt i64 %conv48.74, 0
+  br i1 %cmp49.75, label %for.body.51.lr.ph, label %for.cond.60.preheader
+
+for.body.51.lr.ph:                                ; preds = %for.cond.30.preheader
+  %div44 = sdiv i64 %div43, 2
+  %sub45 = add nsw i64 %div44, 4294967295
+  %1 = trunc i64 %sub45 to i32
+  %2 = sext i32 %1 to i64
+  br label %for.body.51
+
+for.cond.60.preheader:                            ; preds = %for.body.51, %for.cond.30.preheader
+  %div44.m = phi i64 [%div44, %for.body.51], [ 0, %for.cond.30.preheader]
+  br i1 true, label %end, label %for.cond.30.preheader
+
+end:
+  ret i64 %div44.m
+
+for.body.51:                                      ; preds = %for.body.51, %for.body.51.lr.ph
+  %indvars.iv86 = phi i64 [ %2, %for.body.51.lr.ph ], [ undef, %for.body.51 ]
+  %arrayidx53 = getelementptr inbounds float, float* %0, i64 %indvars.iv86
+  %3 = load float, float* %arrayidx53, align 4
+  %arrayidx55 = getelementptr inbounds float, float* %d, i64 0
+  %mul56 = fmul float %3, undef
+  store float %mul56, float* %arrayidx55, align 4
+  br i1 false, label %for.body.51, label %for.cond.60.preheader
+}

polly/trunk/test/Isl/CodeGen/inner_scev_sdiv_in_lb.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -S -polly-codegen < %s | FileCheck %s --check-prefix=CODEGEN
+;
+; TODO: This is a negative test.
+;
+;       Once we use isl to come up with loop bounds this should work
+;       and hopefully not break 
+;
+; CHECK-NOT: Valid Region
+; CODEGEN-NOT: polly
+;
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N; i++)
+;        for (int j = 0; j < i / 3; j++)
+;          A[i] += A[j];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+bb:
+  %tmp = sext i32 %N to i64
+  br label %bb3
+
+bb3:                                              ; preds = %bb19, %bb
+  %indvars.iv1 = phi i64 [ %indvars.iv.next2, %bb19 ], [ 0, %bb ]
+  %tmp4 = icmp slt i64 %indvars.iv1, %tmp
+  br i1 %tmp4, label %bb5, label %bb20
+
+bb5:                                              ; preds = %bb3
+  br label %bb6
+
+bb6:                                              ; preds = %bb17, %bb5
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb17 ], [ 0, %bb5 ]
+  %tmp7 = trunc i64 %indvars.iv1 to i32
+  %tmp8 = sdiv i32 %tmp7, 3
+  %tmp9 = sext i32 %tmp8 to i64
+  %tmp10 = icmp slt i64 %indvars.iv, %tmp9
+  br i1 %tmp10, label %bb11, label %bb18
+
+bb11:                                             ; preds = %bb6
+  %tmp12 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp13 = load i32, i32* %tmp12, align 4
+  %tmp14 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv1
+  %tmp15 = load i32, i32* %tmp14, align 4
+  %tmp16 = add nsw i32 %tmp15, %tmp13
+  store i32 %tmp16, i32* %tmp14, align 4
+  br label %bb17
+
+bb17:                                             ; preds = %bb11
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb6
+
+bb18:                                             ; preds = %bb6
+  br label %bb19
+
+bb19:                                             ; preds = %bb18
+  %indvars.iv.next2 = add nuw nsw i64 %indvars.iv1, 1
+  br label %bb3
+
+bb20:                                             ; preds = %bb3
+  ret void
+}

polly/trunk/test/Isl/CodeGen/inner_scev_sdiv_in_lb_invariant.ll

+; RUN: opt %loadPolly -S -polly-codegen -polly-no-early-exit < %s | FileCheck %s
+;
+; Check that this will not crash our code generation.
+;
+; CHECK: polly.start:
+;
+;    void f(int *A, int N) {
+;      for (int i = 0; i < N / 4; i++)
+;        A[i] += A[i - 1];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N) {
+bb:
+  %tmp = sdiv i32 %N, 4
+  %tmp2 = sext i32 %tmp to i64
+  br label %bb1
+
+bb1:                                              ; preds = %bb11, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb11 ], [ 0, %bb ]
+  %tmp3 = icmp slt i64 %indvars.iv, %tmp2
+  br i1 %tmp3, label %bb4, label %bb12
+
+bb4:                                              ; preds = %bb1
+  %tmp5 = add nsw i64 %indvars.iv, -1
+  %tmp6 = getelementptr inbounds i32, i32* %A, i64 %tmp5
+  %tmp7 = load i32, i32* %tmp6, align 4
+  %tmp8 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp9 = load i32, i32* %tmp8, align 4
+  %tmp10 = add nsw i32 %tmp9, %tmp7
+  store i32 %tmp10, i32* %tmp8, align 4
+  br label %bb11
+
+bb11:                                             ; preds = %bb4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb12:                                             ; preds = %bb1
+  ret void
+}

polly/trunk/test/Isl/CodeGen/inner_scev_sdiv_in_rtc.ll

+; RUN: opt %loadPolly -polly-codegen -polly-no-early-exit -S < %s | FileCheck %s
+;
+; This will just check that we generate valid code here.
+;
+; CHECK: polly.start:
+;
+;    void f(int *A, int *B) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i % 3] = B[i / 42];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %B, i32 %N) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb9, %bb
+  %i.0 = phi i32 [ 0, %bb ], [ %tmp10, %bb9 ]
+  %exitcond = icmp ne i32 %i.0, %N
+  br i1 %exitcond, label %bb2, label %bb11
+
+bb2:                                              ; preds = %bb1
+  %tmp = sdiv i32 %i.0, 42
+  %tmp3 = sext i32 %tmp to i64
+  %tmp4 = getelementptr inbounds i32, i32* %B, i64 %tmp3
+  %tmp5 = load i32, i32* %tmp4, align 4
+  %tmp6 = srem i32 %i.0, 3
+  %tmp7 = sext i32 %tmp6 to i64
+  %tmp8 = getelementptr inbounds i32, i32* %A, i64 %tmp7
+  store i32 %tmp5, i32* %tmp8, align 4
+  br label %bb9
+
+bb9:                                              ; preds = %bb2
+  %tmp10 = add nuw nsw i32 %i.0, 1
+  br label %bb1
+
+bb11:                                             ; preds = %bb1
+  ret void
+}