[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/InstCombineLoadStoreAlloca.cpp

case LLVMContext::MD_range:
       // These don't apply for stores.
       break;
     }
   }
 
   return NewStore;
 }
 
+
+/// \brief Combine a Load used only by a PHI to a new type if all instructions
+/// connected to the PHI agree on the new type
+///
+/// If successful, creates a new LoadInst and a new PHINode and inserts them into
+/// the IR.
+/// Returns the new PHINode.
+static
+PHINode* combineLoadPHIToType(InstCombiner &IC, LoadInst &LI,
+                              PHINode *PN, Type *Ty) {
+  const DataLayout &DL = IC.getDataLayout();
+
+  // Test whether all instructions connected to the PHI agree on the same
+  // desired type Ty.
+  for (int i = 0, e = PN->getNumIncomingValues(); i < e; i++) {
+    if (auto *CI = dyn_cast<CastInst>(PN->getIncomingValue(i))) {
+      if (!CI->isNoopCast(DL) ||!CI->hasOneUse() ||
+          CI->getSrcTy() != Ty) {
+        return nullptr;
+      }
+    } else if (PN->getIncomingValue(i) != &LI) {
+      // We currently do this only for a single load instruction.
+      return nullptr;
+    }
+  }
+
+
+  // Create a new PHI and Load with the proper type and attach the PHI to the
+  // uncasted incoming values.
+  PHINode *NewPN = PHINode::Create(Ty, PN->getNumIncomingValues(),
+                                   PN->getName() + ".cast");
+  LoadInst *NewLoad = combineLoadToNewType(IC, LI, Ty);
+  for (int i = 0, e = PN->getNumIncomingValues(); i < e; i++) {
+    Value *InV;
+    if (auto *CI = dyn_cast<CastInst>(PN->getIncomingValue(i))) {
+      InV = CI->getOperand(0);
+    } else {
+      InV = NewLoad;
+    }
+    NewPN->addIncoming(InV, PN->getIncomingBlock(i));
+  }
+
+  // Insert the new PHI into the IR
+  IC.InsertNewInstBefore(NewPN, *PN);
+
+  return NewPN;
+}
+
 /// \brief Combine loads to match the type of value their uses after looking
 /// through intervening bitcasts.
 ///
 /// The core idea here is that if the result of a load is used in an operation,
 /// we should load the type most conducive to that operation. For example, when
 /// loading an integer and converting that immediately to a pointer, we should
 /// instead directly load a pointer.
 ///
if (std::all_of(LI.user_begin(), LI.user_end(), [&LI](User *U) {
       }
       assert(LI.use_empty() && "Failed to remove all users of the load!");
       // Return the old load so the combiner can delete it safely.
       return &LI;
     }
   }
 
   // Fold away bit casts of the loaded value by loading the desired type.
-  if (LI.hasOneUse())
+  if (LI.hasOneUse()) {
     if (auto *BC = dyn_cast<BitCastInst>(LI.user_back())) {
       LoadInst *NewLoad = combineLoadToNewType(IC, LI, BC->getDestTy());
       BC->replaceAllUsesWith(NewLoad);
       IC.EraseInstFromFunction(*BC);
       return &LI;
     }
 
+    // If the loaded value is bitcasted with a PHINode between the BitCastInst and
+    // the Load, we can perform the fold as well, given that we can prove that all
+    // users and inputs of the phi agree on the desired type.
+    if (auto *PN = dyn_cast<PHINode>(LI.user_back())) {
+      if (PN->hasOneUse()) {
+        if (auto *CI = dyn_cast<CastInst>(PN->user_back())) {
+          if (CI->isNoopCast(DL)) {
+            Type *Ty = CI->getDestTy();
+            // Test wether all involved instructions agree on the desired type,
+            // then generate a new phi and load using this type.
+            if (PHINode *NewPN = combineLoadPHIToType(IC, LI, PN, Ty)) {
+              // We have created a new phi and load, now plug it in and vacuum
+              // the old instructions.
+              CI->replaceAllUsesWith(NewPN);
+              IC.EraseInstFromFunction(*CI);
+              // Remove all incoming values of the phi and erase the instructions
+              // removeIncomingValue decreases the length of the incoming arrray,
+              // so do this from back to front.
+              for (int e = 0, i = PN->getNumIncomingValues(); i > e; i--) {
+                auto *V = cast<Instruction>(PN->removeIncomingValue(i-1, false));
+                // We shouldn't erase the LI because IC would like to do that.
+                // Currently, the only Non-BitCast Instruction that the PHI can
+                // have as incoming Value at this point is LI.
+                if (V != &LI) { IC.EraseInstFromFunction(*V); }
+              }
+              IC.EraseInstFromFunction(*PN);
+              return &LI;
+            }
+          }
+        }
+      }
+    }
+  }
+
   // FIXME: We should also canonicalize loads of vectors when their elements are
   // cast to other types.
   return nullptr;
 }
 
 // If we can determine that all possible objects pointed to by the provided
 // pointer value are, not only dereferenceable, but also definitively less than
 // or equal to the provided maximum size, then return true. Otherwise, return

test/Transforms/InstCombine/bitcast_load_phi.ll

+; 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 }
+
+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*
+
+
+; Test if instcombine looks whether pointer width matches integer width
+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
+
+declare void @something(%struct.Point*)