LoopUnswitch - Simplify based on known not to a be constant.

[trentxintong]

Summary

In case we do not know what the condition is in an unswitched loop, but we know its definitely NOT a known constant. We can perform simplifcations based on this information. More specifically we can simplify comparison instructions with the cond...

[trentxintong]

Ping.

[trentxintong]

2nd PING.

[trentxintong]

Update comments and rename function.

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

1429

Missing check that Val is a ConstantInt.

1431

Maybe use isTrueWhenEqual here, so you can drop the isEquality check?

1431

Err, nevermind, that doesn't work, please ignore.

[trentxintong]

lib/Transforms/Scalar/LoopUnswitch.cpp

1429

Val is going to be a ConstantInt, as its used by ICmpInst, I will add an assert though =).

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

1429

It will be a Constant of integer type... but that's not the same thing as a ConstantInt. (For example ptrtoint i32* @g to i64. is a Constant of integer type.)

[trentxintong]

lib/Transforms/Scalar/LoopUnswitch.cpp

1429

I see. Thanks for pointing this out to me. But does Val have to be a constantInt here. What we know here is that the Cond != Val and we are trying to simplify a icmpinst, we are not getting the actual integer value of this constant.

Even though I think the Val is always going to be the constant int in the current state of pass.

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

1429

Err, no, you're right... this particular transform works out even if Val isn't a ConstantInt, because you're checking for equality.

Sorry, I feel like I'm completely screwing up this review; I'll take another look tomorrow, and hopefully it's clearer then.

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

262

The name "Cond" is kind of confusing... it's the condition of some switch somewhere, but that isn't particularly relevant here. Maybe "Invariant" is a better name, since that's the important property?

Also, the name of the function isn't great... maybe rename it SimplifyInstructionWithNotEqual?

1424

This comment is a bit difficult to parse. Maybe just "icmp eq cond, val -> false"?

1441

Redundant comment.

[trentxintong]

Address efriedma's comments.

[trentxintong]

Address efriedma's comments.

[efriedma]

LGTM.

[trentxintong]

Thanks for the review @efriedma !

[trentxintong]

There was an iterator invalidation bug here. I committed 296069 (https://reviews.llvm.org/rL296069) to fix the problem. Post-commit reviews welcome.

lib/Transforms/Scalar/LoopUnswitch.cpp

 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
private:
 
     void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
                                         BasicBlock *TrueDest,
                                         BasicBlock *FalseDest,
                                         Instruction *InsertPt,
                                         TerminatorInst *TI);
 
     void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
+
+    /// Given that the condition is not equal to \p Val. Simplify instructions
+    /// in the loop.
+    Value *SimplifyInstructionWithInverse(Instruction *Inst, Value *Cond,
+                                          Constant *Val);
   };
 }
 
 // Analyze loop. Check its size, calculate is it possible to unswitch
 // it. Returns true if we can unswitch this loop.
 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI,
                                 AssumptionCache *AC) {
 
if (IsEqual || (isa<ConstantInt>(Val) &&
 
     for (Instruction *UI : Worklist)
       UI->replaceUsesOfWith(LIC, Replacement);
 
     SimplifyCode(Worklist, L);
     return;
   }
 
+
   // Otherwise, we don't know the precise value of LIC, but we do know that it
   // is certainly NOT "Val".  As such, simplify any uses in the loop that we
   // can.  This case occurs when we unswitch switch statements.
   for (User *U : LIC->users()) {
     Instruction *UI = dyn_cast<Instruction>(U);
     if (!UI || !L->contains(UI))
       continue;
 
     Worklist.push_back(UI);
 
-    // TODO: We could do other simplifications, for example, turning
-    // 'icmp eq LIC, Val' -> false.
+    // At this point, we know LIC is definitely not Val. Try to use some simple
+    // logic to simplify the user.
+    //
+    // We should have checked that the UI is part of the loop at this point.
+    assert(L->contains(UI) && "Illegal to simplify instructions outside the loop"); 
+    if (Value *Replacement = SimplifyInstructionWithInverse(UI, LIC, Val)) {
+      // This in-loop instruction has been simplified w.r.t. its context,
+      // i.e. LIC != Val, make sure we propagate its replacement value to
+      // all its users.
+      ReplaceUsesOfWith(UI, Replacement, Worklist, L, LPM);
+      continue;
+    }
 
     // If we know that LIC is not Val, use this info to simplify code.
     SwitchInst *SI = dyn_cast<SwitchInst>(UI);
     if (!SI || !isa<ConstantInt>(Val)) continue;
 
     SwitchInst::CaseIt DeadCase = SI->findCaseValue(cast<ConstantInt>(Val));
     // Default case is live for multiple values.
     if (DeadCase == SI->case_default()) continue;
if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
         ++NumSimplify;
         continue;
       }
 
       continue;
     }
   }
 }
+
+/// A list of simple simplifications we can do given the information that
+/// \p Cond is definitely not equal to \p IV.
+Value *LoopUnswitch::SimplifyInstructionWithInverse(Instruction *Inst,
+                                                    Value *Cond,
+                                                    Constant *Val) {
+  // This is an integer comparison instruction and its operands are Cond
+  // and Val. And we know Cond is definitely not equal to Val, try to
+  // simplify it.
+  ICmpInst *CI = dyn_cast<ICmpInst>(Inst);
+  if (CI && CI->isEquality()) {
+    Value *Op0 = CI->getOperand(0);
+    Value *Op1 = CI->getOperand(1);
+    if ((Op0 == Cond && Op1 == Val) || (Op0 == Val && Op1 == Cond)) {
+      LLVMContext &Ctx = Inst->getContext();
+      if (CI->getPredicate() == CmpInst::ICMP_EQ)
+        return ConstantInt::getFalse(Ctx);
+      else 
+        return ConstantInt::getTrue(Ctx);
+     }
+  }
+
+  // FIXME: there are other simplification opprotunities. e.g. comparison
+  // with floating points, or try to propagate its non-valness through other
+  // instructions such as subtraction.
+  //
+  // Do not know how to simplify instruction.
+  return nullptr;
+}

test/Transforms/LoopUnswitch/simplify-with-inverse.ll

+; RUN: opt < %s -loop-unswitch -verify-loop-info -S < %s 2>&1 | FileCheck %s
+
+; There are 1 case and 1 default case in the switch. after we unswitch, we know the
+; %a is definitely not 0 in one of the unswitched loop, make sure we take advantage
+; of that and simplify the branches in the loop.
+;
+; CHECK: define void @simplify_with_inverse(
+
+; This is the loop in which we know %a is definitely 0.
+; CHECK: sw.bb.us:
+; CHECK: br i1 true, label %if.then.us, label %if.end.us
+
+; This is the loop in which we do not know what %a is but we know %a is definitely NOT 0.
+; Make sure we use that information to simplify.
+; CHECK: sw.bb.split:
+; CHECK: br i1 false, label %if.then, label %if.end
+
+define void @simplify_with_inverse(i32 %a) #0 {
+entry:
+  br label %for.cond
+
+for.cond:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  switch i32 %a, label %sw.default [
+    i32 0, label %sw.bb
+  ]
+
+sw.bb:
+  %cmp1 = icmp eq i32 %a, 0
+  br i1 %cmp1, label %if.then, label %if.end
+
+if.then:
+  call void (...) @bar()
+  br label %if.end
+
+if.end:
+  br label %sw.epilog
+
+sw.default:
+  br label %sw.epilog
+
+sw.epilog:
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}
+
+declare void @bar(...)