Check for all known bits on ret in InstCombine

[hfinkel]

Summary

From a combination of invariants (and perhaps through other means), it is possible that all bits of a return value might be known. Currently, InstCombine does not check for this (which is understandable given assumptions of constant propagation), but means that we'd miss simple cases where invariants are involved.

[chandlerc]

This patch seems trivially fine once we sort out invariants. However, I wonder about doing something more comprehensive. No need to wait for that to make basic improvements here, but something to think about.

lib/Transforms/InstCombine/InstructionCombining.cpp

1938–1939

I wonder if it makes sense to do something somewhat more pervasive by replacing all uses of a value? Essentially, an invariant constant propagation pass.

[hfinkel]

Renamed to llvm.assume.

[reames]

The code change LGTM.

The changes inspires two thoughts:

1. As we've discussed off list and Chandler mentioned, we need to

investigate profitability of various invariant condition propagation
schemes.

2. When do we remove a llvm.assume? In your test case, you had an

assume which (after the transform) retained a condition about an
otherwise used value (%a). This seems like an obvious case to remove
since we've gotten all the benefit we can from it. Are there other
cases like this we should implement?

p.s. Do you have a wiki or notes page somewhere where we can track
potential enhancements? I worry large parts are getting lost in all the
various review threads.

Philip

[hfinkel]

Rebased (perhaps no change in the limited-context diff).

[hfinkel]

r217346.

lib/Transforms/InstCombine/InstCombine.h

public:
   Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
   Instruction *visitAllocaInst(AllocaInst &AI);
   Instruction *visitAllocSite(Instruction &FI);
   Instruction *visitFree(CallInst &FI);
   Instruction *visitLoadInst(LoadInst &LI);
   Instruction *visitStoreInst(StoreInst &SI);
   Instruction *visitBranchInst(BranchInst &BI);
   Instruction *visitSwitchInst(SwitchInst &SI);
+  Instruction *visitReturnInst(ReturnInst &RI);
   Instruction *visitInsertValueInst(InsertValueInst &IV);
   Instruction *visitInsertElementInst(InsertElementInst &IE);
   Instruction *visitExtractElementInst(ExtractElementInst &EI);
   Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
   Instruction *visitExtractValueInst(ExtractValueInst &EV);
   Instruction *visitLandingPadInst(LandingPadInst &LI);
 
   // visitInstruction - Specify what to return for unhandled instructions...

lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombiner::visitFree(CallInst &FI) {
   // free(foo);
   if (MinimizeSize)
     if (Instruction *I = tryToMoveFreeBeforeNullTest(FI))
       return I;
 
   return nullptr;
 }
 
+Instruction *InstCombiner::visitReturnInst(ReturnInst &RI) {
+  if (RI.getNumOperands() == 0) // ret void
+    return nullptr;
+
+  Value *ResultOp = RI.getOperand(0);
+  Type *VTy = ResultOp->getType();
+  if (!VTy->isIntegerTy())
+    return nullptr;
+
+  // There might be assume intrinsics dominating this return that completely
+  // determine the value. If so, constant fold it.
+  unsigned BitWidth = VTy->getPrimitiveSizeInBits();
+  APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
+  computeKnownBits(ResultOp, KnownZero, KnownOne, 0, &RI);
+  if ((KnownZero|KnownOne).isAllOnesValue())
+    RI.setOperand(0, Constant::getIntegerValue(VTy, KnownOne));
 
+  return nullptr;
+}
 
 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
   // Change br (not X), label True, label False to: br X, label False, True
   Value *X = nullptr;
   BasicBlock *TrueDest;
   BasicBlock *FalseDest;
   if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) &&
       !isa<Constant>(X)) {

test/Transforms/InstCombine/assume.ll

; CHECK: ret i32
 
   %0 = load i32* %a, align 4
   ret i32 %0
 }
 
 ; Function Attrs: nounwind
 declare void @llvm.assume(i1) #1
 
+define i32 @simple(i32 %a) #1 {
+entry:
+
+; CHECK-LABEL: @simple
+; CHECK: call void @llvm.assume
+; CHECK: ret i32 4
+
+  %cmp = icmp eq i32 %a, 4
+  tail call void @llvm.assume(i1 %cmp)
+  ret i32 %a
+}
+
 ; Function Attrs: nounwind uwtable
 define i32 @can1(i1 %a, i1 %b, i1 %c) {
 entry:
   %and1 = and i1 %a, %b
   %and  = and i1 %and1, %c
   tail call void @llvm.assume(i1 %and)
 
 ; CHECK-LABEL: @can1