Add InstCombine/InstructionSimplify support for Freeze Instruction

[aqjune]

Summary

• Add llvm::SimplifyFreezeInst
• Add InstCombiner::visitFreeze
• Add llvm tests

[aqjune]

• Move isGuaranteedNotToBeUndefOrPoison from https://reviews.llvm.org/D29011

[aqjune]

Rebased to svn commit 308173

[filcab]

LGTM

include/llvm/Analysis/InstructionSimplify.h

294 ↗

(On Diff #86251)

No need for the name in the comment.

[aqjune]

Rebased to svn commit 331586

[lebedev.ri]

test/Transforms/InstCombine/freeze.ll

1 ↗

(On Diff #145378)

Please consider using utils/update_test_checks.py

[aqjune]

Rebase to trunk@369887 (August 26th, 2019)

[reames]

LGTM.

p.s. Do you have a list of items for this work somewhere? We clearly need support in a number of passes, is there a master list so that we can split work once the IR def pass lands?

[lebedev.ri]

This needs both an instsimplify test and an instcombine test.
Other than that this seems conservatively correct.

[aqjune]

In D29013#1723781, @reames wrote:

LGTM.

p.s. Do you have a list of items for this work somewhere? We clearly need support in a number of passes, is there a master list so that we can split work once the IR def pass lands?

Hi, sorry for the delay. I don't have master list, but possible places where freeze can be considered is as follows:

• The loopunswitch bug can be fixed with freeze. https://reviews.llvm.org/D29015 , https://reviews.llvm.org/D29016 , I'll update the patch today or tomorrow.
• select(c, bop(x,y), bop(x,z)) -> bop(x,(select(c,y,z)) is buggy if c is poison and bop is division because it generates division by poison. This can be resolved by freezing c. It is at InstCombiner::foldSelectOpOp of InstCombineSelect.cpp
• Check whether freeze was regarded as a zero-cost instruction when inlining
• Division hoisting

divisor = y | 1 // divisor is either non-zero or poison
while (cond) {
  x = 100 / divisor // Hoisting this x may introduce UB, so y should be freezed in advance.
  use(x)
}

Similar case is having if (divisor != 0) check surrounding the while loop. When divisor is undef (and if branching on undef is nondeterministic jump), hoisting the division is not explained. You can freeze the divisor.

• SelectionDAGBuilder::visitBr() tries to lower br i1 (and (icmp ...), (icmp ...)) into two separated branches, but it is blocked if one of the icmps is freezed. Adding transformations like freeze (icmp a, const) -> icmp (freeze a), const is helpful for this.

llvm/include/llvm/Analysis/InstructionSimplify.h

 /// Given operands for a BinaryOperator, fold the result or return null.
 /// Try to use FastMathFlags when folding the result.
 Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
                      FastMathFlags FMF, const SimplifyQuery &Q);
 
 /// Given a callsite, fold the result or return null.
 Value *SimplifyCall(CallBase *Call, const SimplifyQuery &Q);
 
+/// Given an operand for a Freeze, see if we can fold the result.
+/// If not, this returns null.
+Value *SimplifyFreezeInst(Value *Op, const SimplifyQuery &Q);
+
 /// See if we can compute a simplified version of this instruction. If not,
 /// return null.
 Value *SimplifyInstruction(Instruction *I, const SimplifyQuery &Q,
                            OptimizationRemarkEmitter *ORE = nullptr);
 
 /// Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
 ///
 /// This first performs a normal RAUW of I with SimpleV. It then recursively

llvm/include/llvm/Analysis/ValueTracking.h

class Value;
   /// Return true if this function can prove that if PoisonI is executed
   /// and yields a full-poison value (all bits poison), then that will
   /// trigger undefined behavior.
   ///
   /// Note that this currently only considers the basic block that is
   /// the parent of I.
   bool programUndefinedIfFullPoison(const Instruction *PoisonI);
 
+  /// Return true if this function can prove that V is never undef value
+  /// or poison value.
+  bool isGuaranteedNotToBeUndefOrPoison(const Value *V);
+
   /// Specific patterns of select instructions we can match.
   enum SelectPatternFlavor {
     SPF_UNKNOWN = 0,
     SPF_SMIN,                   /// Signed minimum
     SPF_UMIN,                   /// Unsigned minimum
     SPF_SMAX,                   /// Signed maximum
     SPF_UMAX,                   /// Unsigned maximum
     SPF_FMINNUM,                /// Floating point minnum

llvm/lib/Analysis/InstructionSimplify.cpp

for (auto &Arg : Call->args()) {
     if (!C)
       return nullptr;
     ConstantArgs.push_back(C);
   }
 
   return ConstantFoldCall(Call, F, ConstantArgs, Q.TLI);
 }
 
+/// Given operands for a Freeze, see if we can fold the result.
+static Value *SimplifyFreezeInst(Value *Op0) {
+  // Use a utility function defined in ValueTracking.
+  if (llvm::isGuaranteedNotToBeUndefOrPoison(Op0))
+    return Op0;
+  // We have room for improvement.
+  return nullptr;
+}
+
+Value *llvm::SimplifyFreezeInst(Value *Op0, const SimplifyQuery &Q) {
+  return ::SimplifyFreezeInst(Op0);
+}
+
 /// See if we can compute a simplified version of this instruction.
 /// If not, this returns null.
 
 Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &SQ,
                                  OptimizationRemarkEmitter *ORE) {
   const SimplifyQuery Q = SQ.CxtI ? SQ : SQ.getWithInstruction(I);
   Value *Result;
 
Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &SQ,
   }
   case Instruction::PHI:
     Result = SimplifyPHINode(cast<PHINode>(I), Q);
     break;
   case Instruction::Call: {
     Result = SimplifyCall(cast<CallInst>(I), Q);
     break;
   }
+  case Instruction::Freeze:
+    Result = SimplifyFreezeInst(I->getOperand(0), Q);
+    break;
 #define HANDLE_CAST_INST(num, opc, clas) case Instruction::opc:
 #include "llvm/IR/Instruction.def"
 #undef HANDLE_CAST_INST
     Result =
         SimplifyCastInst(I->getOpcode(), I->getOperand(0), I->getType(), Q);
     break;
   case Instruction::Alloca:
     // No simplifications for Alloca and it can't be constant folded.

llvm/lib/Analysis/ValueTracking.cpp

auto AllUsesGuardedByBranch = [&](const BranchInst *BI) {
     }
 
     return true;
   };
 
   return llvm::any_of(GuardingBranches, AllUsesGuardedByBranch);
 }
 
+bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V) {
+  // If the value is a freeze instruction, then it can never
+  // be undef or poison.
+  if (isa<FreezeInst>(V))
+    return true;
+  // TODO: Some instructions are guaranteed to return neither undef
+  // nor poison if their arguments are not poison/undef.
+
+  // TODO: Deal with other Constant subclasses.
+  if (isa<ConstantInt>(V) || isa<GlobalVariable>(V))
+    return true;
+
+  return false;
+}
 
 OverflowResult llvm::computeOverflowForSignedAdd(const AddOperator *Add,
                                                  const DataLayout &DL,
                                                  AssumptionCache *AC,
                                                  const Instruction *CxtI,
                                                  const DominatorTree *DT) {
   return ::computeOverflowForSignedAdd(Add->getOperand(0), Add->getOperand(1),
                                        Add, DL, AC, CxtI, DT);

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   Instruction *visitInsertValueInst(InsertValueInst &IV);
   Instruction *visitInsertElementInst(InsertElementInst &IE);
   Instruction *visitExtractElementInst(ExtractElementInst &EI);
   Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
   Instruction *visitExtractValueInst(ExtractValueInst &EV);
   Instruction *visitLandingPadInst(LandingPadInst &LI);
   Instruction *visitVAStartInst(VAStartInst &I);
   Instruction *visitVACopyInst(VACopyInst &I);
+  Instruction *visitFreeze(FreezeInst &I);
 
   /// Specify what to return for unhandled instructions.
   Instruction *visitInstruction(Instruction &I) { return nullptr; }
 
   /// True when DB dominates all uses of DI except UI.
   /// UI must be in the same block as DI.
   /// The routine checks that the DI parent and DB are different.
   bool dominatesAllUses(const Instruction *DI, const Instruction *UI,

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

if (LI.isCleanup() != CleanupFlag) {
     assert(!CleanupFlag && "Adding a cleanup, not removing one?!");
     LI.setCleanup(CleanupFlag);
     return &LI;
   }
 
   return nullptr;
 }
 
+Instruction *InstCombiner::visitFreeze(FreezeInst &I) {
+  Value *Op0 = I.getOperand(0);
+
+  if (Value *V = SimplifyFreezeInst(Op0, SQ.getWithInstruction(&I)))
+    return replaceInstUsesWith(I, V);
+
+  return nullptr;
+}
+
 /// Try to move the specified instruction from its current block into the
 /// beginning of DestBlock, which can only happen if it's safe to move the
 /// instruction past all of the instructions between it and the end of its
 /// block.
 static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock,
                                  InstCombiner::BuilderTy &Builder) {
   assert(I->hasOneUse() && "Invariants didn't hold!");
   BasicBlock *SrcBlock = I->getParent();

llvm/test/Transforms/InstCombine/freeze.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+define i32 @fold(i32 %x) {
+; CHECK-LABEL: @fold(
+; CHECK-NEXT:    [[Y:%.*]] = freeze i32 [[X:%.*]]
+; CHECK-NEXT:    ret i32 [[Y]]
+;
+  %y = freeze i32 %x
+  %z = freeze i32 %y
+  ret i32 %z
+}
+
+define i32 @make_const() {
+; CHECK-LABEL: @make_const(
+; CHECK-NEXT:    ret i32 10
+;
+  %x = freeze i32 10
+  ret i32 %x
+}

llvm/test/Transforms/InstSimplify/freeze.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instsimplify -S | FileCheck %s
+
+define i32 @fold(i32 %x) {
+; CHECK-LABEL: @fold(
+; CHECK-NEXT:    [[Y:%.*]] = freeze i32 [[X:%.*]]
+; CHECK-NEXT:    ret i32 [[Y]]
+;
+  %y = freeze i32 %x
+  %z = freeze i32 %y
+  ret i32 %z
+}
+
+define i32 @make_const() {
+; CHECK-LABEL: @make_const(
+; CHECK-NEXT:    ret i32 10
+;
+  %x = freeze i32 10
+  ret i32 %x
+}