Handle resolvable branches in complete loop unroll heuristic.

[mzolotukhin]

Summary

Resolving a branch allows us to ignore blocks that won't be executed, and thus make our estimate more accurate.
This patch is intended to be applied after D10205 (though it could be applied independently).

[mzolotukhin]

• In two-operand instructions use simplified values only if both operands have the same base pointer (or don't have it at all).

[chandlerc]

Totally the right direction, just some quick comments here. This patch will likely change some based on my comments in D10205 but these are independent issues.

lib/Transforms/Scalar/LoopUnrollPass.cpp

581–582

I don't think the 'Cond' variable is buying you much.

I would also write the condition differently as the only null case is where we have no simplified value. The type must always be an int. So:

if (Constant *SimpleCond = SimplifiedValues.lookup(BI->getCondition())) {
  BBWorklist.insert(BI->getSuccessor(cast<ConstantInt>(SimpleCond)->isZero() ? 1 : 0));

588–591

Same comment as above.

[mzolotukhin]

• Rebase.
• Rename SCEVSimplify to simplifyInstWithSCEV in visitCmpInst.
• Fallback to Base visitor if failed to constant fold (and only then call simplifyInstWithSCEV).
• Rewrite conditional expression for adding successors.

[mzolotukhin]

• Rebase on master.

[mzolotukhin]

Ping!

[mzolotukhin]

Ping!

[mzolotukhin]

Ping!

[chandlerc]

Looks really close, just need to sort out the offset simplification.

lib/Transforms/Scalar/LoopUnrollPass.cpp

386–388

This doesn't really seem correct to me...

For example, multiplication such as "(B + X) * (B + Y)" does not simplify to "X * Y". Even addition doesn't simplify that way.

I think it would be more clear (and correct) to explicitly handle the math that simplifies here rather than trying to share a routine. Test for subtraction and that LHS and RHS are in the simplified addresses mapping. If they are, you can write a comment about how the base addresses cancel and the result is the CaonstantExpr difference of the offsets.

I don't think you really need to even think about falling through to the fancy InstSimplify logic here because you only can do anything when you have boring constant offsets.

455

If you take my advice above, I would also inline the logic here. I'm not sure there is really going to be that much shared between the two when you're done. You can really *only* handle subtraction above, but here you can handle any comparison and really want to just fall back on the same logic.

596

I would leave a hint in this comment that this is the fallback if we can't directly fold the successor above.

[mzolotukhin]

Address review remarks:

• Add tests.
• Remove simplifyUsingOffsets routine.
• .. and rebase on the trunk.

[mzolotukhin]

Hi Chandler,

I updated the patch - does it look good now?

I decided not to handle operands in (Base+Offset) form in visitBinaryOperator for now, because I think we could get into troubles even if we only look at SUB (I'm concerned about possible overflow errors here). I think it's possible to do, but we can do it later if we ever need it.

Tests are also added to the patch now (mostly they are from D10208).

Thanks,
Michael

[chandlerc]

This looks fantastic. Nit-picky indenting and layout below. Feel free to commit with that addressed.

lib/Transforms/Scalar/LoopUnrollPass.cpp

457–465

I actually think its better to nest these. Because we're using fall-through to "continue trying", the early-exit is hard to spot here. It also will save some map lookups:

auto SimplifiedLHS = SimplifiedAddresses.find(LHS)
if (SimplifiedLHS != SimplifiedAddresses.end()) {
  auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
  if (SimplifiedRHS != SimplifiedAddresses.end()) {
    SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
    SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
    if (LHSAddr.Base == RHSAddr.Base) {
      LHS = LHSAddr.Offset;
      ...

468–470

If you're going to skip the middle {}s (which I'm fine with) skip the outer ones as well.

[mzolotukhin]

Thanks, Chandler! It's committed.

Michael

lib/Transforms/Scalar/LoopUnrollPass.cpp

bool visitBinaryOperator(BinaryOperator &I) {
     Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
     if (!isa<Constant>(LHS))
       if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
         LHS = SimpleLHS;
     if (!isa<Constant>(RHS))
       if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
         RHS = SimpleRHS;
 
     if (!isa<Constant>(LHS) && !isa<Constant>(RHS))
       if (!simplifyUsingOffsets(LHS, RHS))
         return Base::visitBinaryOperator(I);
 
     Value *SimpleV = nullptr;
     const DataLayout &DL = I.getModule()->getDataLayout();
     if (auto FI = dyn_cast<FPMathOperator>(&I))
       SimpleV =
           SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
     else
       SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
bool visitLoad(LoadInst &I) {
     }
 
     Constant *CV = CDS->getElementAsConstant(Index);
     assert(CV && "Constant expected.");
     SimplifiedValues[&I] = CV;
 
     return true;
   }
+
+  bool visitCmpInst(CmpInst &I) {
+    Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+
+    // First try to handle simplified comparisons.
+    if (!isa<Constant>(LHS))
+      if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
+        LHS = SimpleLHS;
+    if (!isa<Constant>(RHS))
+      if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
+        RHS = SimpleRHS;
+
+    if (!isa<Constant>(LHS) && !isa<Constant>(RHS))
+      if (!simplifyUsingOffsets(LHS, RHS))
+        return Base::visitCmpInst(I);
+
+    if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
+      if (Constant *CRHS = dyn_cast<Constant>(RHS))
+        if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
+          SimplifiedValues[&I] = C;
+          return true;
+        }
+    }
+
+    return Base::visitCmpInst(I);
+  }
+
+  /// \brief Check if \p LHS and \p RHS correspond to address expressions with
+  /// the same base and their offsets could be folded to constants.
+  ///
+  /// \returns true and updates \p LHS and \p RHS if they both are present in
+  /// SimplifiedOffsets and have the same base address.
+  bool simplifyUsingOffsets(Value *&LHS, Value *&RHS) {
+    if (!SimplifiedOffsets.count(LHS) || !SimplifiedOffsets.count(RHS))
+      return false;
+    SimplifiedAddress LHSAddr = SimplifiedOffsets.lookup(LHS);
+    SimplifiedAddress RHSAddr = SimplifiedOffsets.lookup(RHS);
+    if (LHSAddr.Base != RHSAddr.Base)
+      return false;
+    LHS = LHSAddr.Offset;
+    RHS = RHSAddr.Offset;
+    return true;
+  }
 };
 } // namespace
 
 
 namespace {
 struct EstimatedUnrollCost {
   /// \brief The estimated cost after unrolling.
   unsigned UnrolledCost;
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
         // loop form.
         RolledDynamicCost += InstCost;
 
         // If unrolled body turns out to be too big, bail out.
         if (UnrolledCost > MaxUnrolledLoopSize)
           return None;
       }
 
+      TerminatorInst *TI = BB->getTerminator();
+
+      // Add in the live successors by first checking whether we have terminator
+      // that may be simplified based on the values simplified by this call.
+      if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+        if (BI->isConditional()) {
+          if (Constant *SimpleCond =
+                  SimplifiedValues.lookup(BI->getCondition())) {
+            BBWorklist.insert(BI->getSuccessor(
+                cast<ConstantInt>(SimpleCond)->isZero() ? 1 : 0));
+            continue;
+          }
+        }
+      } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+        if (Constant *SimpleCond =
+                SimplifiedValues.lookup(SI->getCondition())) {
+          BBWorklist.insert(
+              SI->getSuccessor(cast<ConstantInt>(SimpleCond)->getSExtValue()));
+          continue;
+        }
+      }
+
       // Add BB's successors to the worklist.
       for (BasicBlock *Succ : successors(BB))
         if (L->contains(Succ))
           BBWorklist.insert(Succ);
     }
 
     // If we found no optimization opportunities on the first iteration, we
     // won't find them on later ones too.
     if (UnrolledCost == RolledDynamicCost)