[InstCombine] Fold bitcasts into loads across PHINodes

[philip.pfaffe]

Summary

Due to a combination of canonicalization of induction vars and subsequent inlining/simplification, we are sometimes left with a PHINode which only uses a load and bitcasts, and whose only user is also a bitcast. If the bitcasts are noop and tautological when concatenated, we can instead fold the desired type through the PHI into the load and get rid of some cast clutter.

[chandlerc]

The idea here makes total sense to me, but I don't think this is the right way to do it.

I think you should be combining the PHI or cast, not the load. The combine should be to hoist a cast of a PHI around the PHI if all of the PHI inputs are casts and loads. You might also need to enqueue the loads in the combiner afterward so we revisit them and recognize that we can fold the cast into the load.

[philip.pfaffe]

I adopted Chandler's suggestion of combining the PHI instead of the Load and updated the patch accordingly. I also added a missing RUN line to the test case.

The idea here is to detect a PHI whose only user is a Noop CastInst and then fold the cast back through the phi if the phi only depends on loads and matching casts. This produces a new cast for an incoming load (which should be folded into the loop later on), and skips incoming casts.

lib/Transforms/InstCombine/InstCombinePHI.cpp

Instruction *InstCombiner::SliceUpIllegalIntegerPHI(PHINode &FirstPhi) {
   // Replace all the remaining uses of the PHI nodes (self uses and the lshrs)
   // with undefs.
   Value *Undef = UndefValue::get(FirstPhi.getType());
   for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
     ReplaceInstUsesWith(*PHIsToSlice[i], Undef);
   return ReplaceInstUsesWith(FirstPhi, Undef);
 }
 
+// Fold a CastInst user back through a Phi. This only makes sense when all the
+// inputs to the Phi are either casts as well (between the same types as the
+// CastInst in question), or loads. For the latter case, this op creates new
+// casts, which can later be folded into the load.
+static
+PHINode *foldCastIntoPHI(InstCombiner &IC, PHINode &PN, CastInst *CI) {
+  const DataLayout &DL = IC.getDataLayout();
+
+  if (!CI || !CI->isNoopCast(DL))
+    return nullptr;
+  Type* CastTy = CI->getDestTy();
+
+  // Check whether the only incoming values are loads and bitcasts
+  // There will be at least one of either, as the all-operands-equal case is
+  // handled earlier.
+  for (Use &In: PN.incoming_values()) {
+    // A load may have only one use, otherwise we might loop infinitely
+    if (isa<LoadInst>(In.get()) && In->hasOneUse())
+      continue;
+    // We can handle an incoming cast if it's a noop and has a matching type
+    if (auto *ArgCI = dyn_cast<CastInst>(In.get()))
+      if (ArgCI->isNoopCast(DL) && ArgCI->getSrcTy() == CastTy)
+        continue;
+    return nullptr;
+  }
+
+  PHINode *NewPN = PHINode::Create(CastTy, PN.getNumIncomingValues(),
+                                   PN.getName());
+  IC.InsertNewInstBefore(NewPN, PN);
+  // Populate the new phi
+  for (Use &In: PN.incoming_values()) {
+    if (auto *LI = dyn_cast<LoadInst>(In)) {
+      // Old incoming load needs to be cast to the requested type
+      auto *NewCI = CastInst::CreateBitOrPointerCast(LI, CastTy);
+      NewPN->addIncoming(NewCI, PN.getIncomingBlock(In));
+      NewCI->insertAfter(LI);
+      // Take another look at the load, later, to fold the new cast into it
+      IC.Worklist.Add(LI);
+    } else if (auto *ArgCI = dyn_cast<CastInst>(In)) {
+      // Old incoming cast can be skipped
+      NewPN->addIncoming(ArgCI->getOperand(0), PN.getIncomingBlock(In));
+    } else
+      llvm_unreachable("Not a CastInst or LoadInst");
+  }
+
+  // plug in the new PHI
+  IC.ReplaceInstUsesWith(*CI, NewPN);
+  IC.EraseInstFromFunction(*CI);
+
+  return &PN;
+}
+
+
 // PHINode simplification
 //
 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
   if (Value *V = SimplifyInstruction(&PN, DL, TLI, DT, AC))
     return ReplaceInstUsesWith(PN, V);
 
   // If all PHI operands are the same operation, pull them through the PHI,
   // reducing code size.
if (PN.hasOneUse()) {
     // common case here is good because the only other things that catch this
     // are induction variable analysis (sometimes) and ADCE, which is only run
     // late.
     if (PHIUser->hasOneUse() &&
         (isa<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(PHIUser)) &&
         PHIUser->user_back() == &PN) {
       return ReplaceInstUsesWith(PN, UndefValue::get(PN.getType()));
     }
+
+    // If the only user of a phi is a CastInst, we may be able to fold this cast
+    // back through the phi and simplify the code, given that the phi's only
+    // incoming values are loads or matching casts.
+    if (auto *CI = dyn_cast<CastInst>(PHIUser))
+      if (PHINode *R = foldCastIntoPHI(*this, PN, CI))
+        return R;
   }
 
   // We sometimes end up with phi cycles that non-obviously end up being the
   // same value, for example:
   //   z = some value; x = phi (y, z); y = phi (x, z)
   // where the phi nodes don't necessarily need to be in the same block.  Do a
   // quick check to see if the PHI node only contains a single non-phi value, if
   // so, scan to see if the phi cycle is actually equal to that value.

test/Transforms/InstCombine/fold-phi-cast-load.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+; ModuleID = 'phi_cast.ll'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.Point = type { i32, i32 }
+declare void @something(%struct.Point*)
+
+define void @test1(%struct.Point** %point_array, %struct.Point* %end) {
+entry:
+  %arrayidx = getelementptr inbounds %struct.Point*, %struct.Point** %point_array, i64 0
+  %canon = bitcast %struct.Point** %arrayidx to i64*
+  %0 = load i64, i64* %canon
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %e_canon = phi i64 [ %0, %entry ], [ %incdec_canon, %for.body ]
+  %e.0 = inttoptr i64 %e_canon to %struct.Point*
+  %cmp = icmp ne %struct.Point* %e.0, %end
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  call void @something(%struct.Point* %e.0)
+  %incdec.ptr = getelementptr inbounds %struct.Point, %struct.Point* %e.0, i32 1
+  %incdec_canon = ptrtoint %struct.Point* %incdec.ptr to i64
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+; LABEL: test1
+; CHECK: load %struct.Point*
+; CHECK: phi %struct.Point*
+
+; Check if we handle pointer size correctly
+define void @test2(%struct.Point** %point_array, %struct.Point* %end) {
+entry:
+  %arrayidx = getelementptr inbounds %struct.Point*, %struct.Point** %point_array, i64 0
+  %canon = bitcast %struct.Point** %arrayidx to i32*
+  %0 = load i32, i32* %canon
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %e_canon = phi i32 [ %0, %entry ], [ %incdec_canon, %for.body ]
+  %e.0 = inttoptr i32 %e_canon to %struct.Point*
+  %cmp = icmp ne %struct.Point* %e.0, %end
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  call void @something(%struct.Point* %e.0)
+  %incdec.ptr = getelementptr inbounds %struct.Point, %struct.Point* %e.0, i32 1
+  %incdec_canon = ptrtoint %struct.Point* %incdec.ptr to i32
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+; LABEL: test2
+; CHECK: load i32
+; CHECK: phi i32