[Polly] Allow eager evaluated binary && and || conditions

[jdoerfert]

Summary

The domain generation can handle lazy && and || by default but eager
evaluated expressions were dismissed as non-affine. With this patch we
will allow arbitrary combinations of and/or bit-operations in the
conditions of branches.

[grosser]

Thanks Johannes!

polly/trunk/lib/Analysis/ScopDetection.cpp

bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI,
 
   return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB,
                                      ConditionSCEV, ConditionSCEV, SI);
 }
 
 bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
                                   Value *Condition, bool IsLoopBranch,
                                   DetectionContext &Context) const {
+
+  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
+    auto Opcode = BinOp->getOpcode();
+    if (Opcode == Instruction::And || Opcode == Instruction::Or) {
+      Value *Op0 = BinOp->getOperand(0);
+      Value *Op1 = BinOp->getOperand(1);
+      return isValidBranch(BB, BI, Op0, IsLoopBranch, Context) &&
+             isValidBranch(BB, BI, Op1, IsLoopBranch, Context);
+    }
+  }
+
   // Non constant conditions of branches need to be ICmpInst.
   if (!isa<ICmpInst>(Condition)) {
     if (!IsLoopBranch && AllowNonAffineSubRegions &&
         addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
       return true;
     return invalid<ReportInvalidCond>(Context, /*Assert=*/true, BI, &BB);
   }
 

polly/trunk/lib/Analysis/ScopInfo.cpp

ConditionSetUnion =
         isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
   ConditionSets[0] = setDimensionIds(
       Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion));
 
   S.markAsOptimized();
   isl_pw_aff_free(LHS);
 }
 
-/// @brief Build the conditions sets for the terminator @p TI in the @p Domain.
+/// @brief Build the conditions sets for the branch condition @p Condition in
+///        the @p Domain.
 ///
 /// This will fill @p ConditionSets with the conditions under which control
 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
 /// have as many elements as @p TI has successors.
 static void
-buildConditionSets(Scop &S, TerminatorInst *TI, Loop *L,
+buildConditionSets(Scop &S, Value *Condition, TerminatorInst *TI, Loop *L,
                    __isl_keep isl_set *Domain,
                    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
 
-  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
-    return buildConditionSets(S, SI, L, Domain, ConditionSets);
-
-  assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
-
-  if (TI->getNumSuccessors() == 1) {
-    ConditionSets.push_back(isl_set_copy(Domain));
-    return;
-  }
-
-  Value *Condition = getConditionFromTerminator(TI);
-  assert(Condition && "No condition for Terminator");
-
   isl_set *ConsequenceCondSet = nullptr;
   if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
     if (CCond->isZero())
       ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
     else
       ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
+  } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
+    auto Opcode = BinOp->getOpcode();
+    assert(Opcode == Instruction::And || Opcode == Instruction::Or);
+
+    buildConditionSets(S, BinOp->getOperand(0), TI, L, Domain, ConditionSets);
+    buildConditionSets(S, BinOp->getOperand(1), TI, L, Domain, ConditionSets);
+
+    isl_set_free(ConditionSets.pop_back_val());
+    isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
+    isl_set_free(ConditionSets.pop_back_val());
+    isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
+
+    if (Opcode == Instruction::And)
+      ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);
+    else
+      ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);
   } else {
     auto *ICond = dyn_cast<ICmpInst>(Condition);
     assert(ICond &&
            "Condition of exiting branch was neither constant nor ICmp!");
 
     ScalarEvolution &SE = *S.getSE();
     BasicBlock *BB = TI->getParent();
     isl_pw_aff *LHS, *RHS;
     LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), BB);
     RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), BB);
     ConsequenceCondSet =
         buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
   }
 
   assert(ConsequenceCondSet);
   isl_set *AlternativeCondSet =
       isl_set_complement(isl_set_copy(ConsequenceCondSet));
 
   ConditionSets.push_back(isl_set_coalesce(
       isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain))));
   ConditionSets.push_back(isl_set_coalesce(
       isl_set_intersect(AlternativeCondSet, isl_set_copy(Domain))));
 }
 
+/// @brief Build the conditions sets for the terminator @p TI in the @p Domain.
+///
+/// This will fill @p ConditionSets with the conditions under which control
+/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
+/// have as many elements as @p TI has successors.
+static void
+buildConditionSets(Scop &S, TerminatorInst *TI, Loop *L,
+                   __isl_keep isl_set *Domain,
+                   SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+
+  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
+    return buildConditionSets(S, SI, L, Domain, ConditionSets);
+
+  assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
+
+  if (TI->getNumSuccessors() == 1) {
+    ConditionSets.push_back(isl_set_copy(Domain));
+    return;
+  }
+
+  Value *Condition = getConditionFromTerminator(TI);
+  assert(Condition && "No condition for Terminator");
+
+  return buildConditionSets(S, Condition, TI, L, Domain, ConditionSets);
+}
+
 void ScopStmt::buildDomain() {
   isl_id *Id;
 
   Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
 
   Domain = getParent()->getDomainConditions(this);
   Domain = isl_set_set_tuple_id(Domain, Id);
 }

polly/trunk/test/ScopInfo/eager-binary-and-or-conditions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+; void or(float *A, long n, long m) {
+;   for (long i = 0; i < 100; i++) {
+;     if (i < n || i < m)
+;       A[i] += i;
+;   }
+; }
+;
+; void and(float *A, long n, long m) {
+;   for (long i = 0; i < 100; i++) {
+;     if (i < n && i < m)
+;       A[i] += i;
+;   }
+; }
+;
+; CHECK: Function: or
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:       [n, m] -> { Stmt_if_then[i0] : (i0 <= 99 and i0 >= 0 and i0 <= -1 + m) or (i0 <= 99 and i0 >= 0 and i0 <= -1 + n) };
+;
+; CHECK: Function: and
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:       [n, m] -> { Stmt_if_then[i0] : i0 <= 99 and i0 >= 0 and i0 <= -1 + m and i0 <= -1 + n }
+;
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define void @or(float* nocapture %A, i64 %n, i64 %m) #0 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.inc, %entry
+  %i.03 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp1 = icmp slt i64 %i.03, %n
+  %cmp2 = icmp slt i64 %i.03, %m
+  %or.cond = or i1 %cmp1, %cmp2
+  br i1 %or.cond, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %conv = sitofp i64 %i.03 to float
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %i.03
+  %0 = load float, float* %arrayidx, align 4
+  %add = fadd float %conv, %0
+  store float %add, float* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.then, %for.body
+  %inc = add nuw nsw i64 %i.03, 1
+  %exitcond = icmp eq i64 %inc, 100
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc
+  ret void
+}
+
+; Function Attrs: nounwind uwtable
+define void @and(float* nocapture %A, i64 %n, i64 %m) #0 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.inc, %entry
+  %i.03 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp1 = icmp slt i64 %i.03, %n
+  %cmp2 = icmp slt i64 %i.03, %m
+  %or.cond = and i1 %cmp1, %cmp2
+  br i1 %or.cond, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %conv = sitofp i64 %i.03 to float
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %i.03
+  %0 = load float, float* %arrayidx, align 4
+  %add = fadd float %conv, %0
+  store float %add, float* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %inc = add nuw nsw i64 %i.03, 1
+  %exitcond = icmp eq i64 %inc, 100
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc
+  ret void
+}

polly/trunk/test/ScopInfo/multiple-binary-or-conditions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+; void or(float *A, long n, long m) {
+;   for (long i = 0; i < 100; i++) {
+;     if (i < n || i < m || i > p)
+;       A[i] += i;
+;   }
+; }
+;
+; CHECK: Function: or
+; CHECK:   Stmt_if_then
+; CHECK:     Domain :=
+; CHECK:       [n, m, p] -> { Stmt_if_then[i0] : (i0 >= 1 + p and i0 <= 99 and i0 >= 0) or (i0 <= 99 and i0 >= 0 and i0 <= -1 + m) or (i0 <= 99 and i0 >= 0 and i0 <= -1 + n) };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define void @or(float* nocapture %A, i64 %n, i64 %m, i64 %p) #0 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.inc, %entry
+  %i.03 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp1 = icmp slt i64 %i.03, %n
+  %cmp2 = icmp slt i64 %i.03, %m
+  %cmp3 = icmp sgt i64 %i.03, %p
+  %or.tmp = or i1 %cmp1, %cmp2
+  %or.cond = or i1 %or.tmp, %cmp3
+  br i1 %or.cond, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %conv = sitofp i64 %i.03 to float
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %i.03
+  %0 = load float, float* %arrayidx, align 4
+  %add = fadd float %conv, %0
+  store float %add, float* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.then, %for.body
+  %inc = add nuw nsw i64 %i.03, 1
+  %exitcond = icmp eq i64 %inc, 100
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc
+  ret void
+}