[InstCombine] Bitreverse/Bswap: Allow ORs of base values

[jmolloy]

Summary

Previously, we'd only recognize bitreversals or byteswaps where the generated value starts off as zero:

int2_t b = 0;
if (a & 1) b |= 2;
if (a & 2) b |= 1;
return b;

But with not much work we can also support starting the generated value as the reversal value:

int2_t b = a;
if (a & 1) b |= 2;
if (a & 2) b |= 1;
return b;

[jmolloy]

Optimistic Christmas Season Ping!

[jmolloy]

Updated diff to reflect the changes that have gone into trunk.

[sanjoy]

Resigning from old patch to get it off my queue. Feel free to add me back if this is revived at some point.

[hfinkel]

lib/Transforms/Utils/Local.cpp

1673

Why is there no else if A->Provider && IsIdentityTransform(A->Provenance)) here?

lib/Transforms/Utils/Local.cpp

if (const Function *F = CS.getCalledFunction())
     return F->hasFnAttribute("gc-leaf-function");
 
   return false;
 }
 
 /// A potential constituent of a bitreverse or bswap expression. See
 /// collectBitParts for a fuller explanation.
 struct BitPart {
-  BitPart(Value *P, unsigned BW) : Provider(P) {
+  BitPart(Value *P, unsigned BW) : Provider(P), ExtraOr(nullptr) {
     Provenance.resize(BW);
   }
 
   /// The Value that this is a bitreverse/bswap of.
   Value *Provider;
+  /// An extra optional value to be ORred into the result.
+  Value *ExtraOr;
   /// The "provenance" of each bit. Provenance[A] = B means that bit A
   /// in Provider becomes bit B in the result of this expression.
   SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
 
   enum { Unset = -1 };
 };
 
 /// Analyze the specified subexpression and see if it is capable of providing
if (Instruction *I = dyn_cast<Instruction>(V)) {
     if (I->getOpcode() == Instruction::Or) {
       auto &A = collectBitParts(I->getOperand(0), MatchBSwaps,
                                 MatchBitReversals, BPS);
       auto &B = collectBitParts(I->getOperand(1), MatchBSwaps,
                                 MatchBitReversals, BPS);
       if (!A || !B)
         return Result;
 
+      auto IsIdentityTransform = [](ArrayRef<int8_t> A) {
+        for (size_t I = 0; I < A.size(); ++I)
+          if (A[I] != (int8_t)I)
+            return false;
+        return true;
+      };
+ 
+      // If one of the values is a simple provider...
+      if (B->Provider && IsIdentityTransform(B->Provenance)) {
+        Result = BitPart(*A);
+        Result->ExtraOr = B->Provider;
+        return Result;
+      }
+      
       // Try and merge the two together.
-      if (!A->Provider || A->Provider != B->Provider)
+      if (!A->Provider || A->Provider != B->Provider ||
+          (A->ExtraOr && B->ExtraOr && A->ExtraOr != B->ExtraOr))
         return Result;
 
       Result = BitPart(A->Provider, BitWidth);
+      Result->ExtraOr = A->ExtraOr ? A->ExtraOr : B->ExtraOr;
       for (unsigned i = 0; i < A->Provenance.size(); ++i) {
         if (A->Provenance[i] != BitPart::Unset &&
             B->Provenance[i] != BitPart::Unset &&
             A->Provenance[i] != B->Provenance[i])
           return Result = None;
 
         if (A->Provenance[i] == BitPart::Unset)
           Result->Provenance[i] = B->Provenance[i];
if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) {
       unsigned BitShift =
           cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U);
       // Ensure the shift amount is defined.
       if (BitShift > BitWidth)
         return Result;
 
       auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
                                   MatchBitReversals, BPS);
-      if (!Res)
+      if (!Res || Res->ExtraOr)
         return Result;
       Result = Res;
 
       // Perform the "shift" on BitProvenance.
       auto &P = Result->Provenance;
       if (I->getOpcode() == Instruction::Shl) {
         P.erase(std::prev(P.end(), BitShift), P.end());
         P.insert(P.begin(), BitShift, BitPart::Unset);
bool llvm::recognizeBitReverseOrBSwapIdiom(
   Intrinsic::ID Intrin;
   if (OKForBSwap && MatchBSwaps)
     Intrin = Intrinsic::bswap;
   else if (OKForBitReverse && MatchBitReversals)
     Intrin = Intrinsic::bitreverse;
   else
     return false;
 
+  IRBuilder<> B(I);
   Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy);
-  InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I));
+  InsertedInsts.push_back(B.CreateCall(F, Res->Provider));
+
+  if (Res->ExtraOr)
+    InsertedInsts.push_back(
+        cast<Instruction>(B.CreateOr(InsertedInsts.back(), Res->ExtraOr)));
   return true;
 }

test/Transforms/CodeGenPrepare/ARM/bitreverse-recognize.ll

for.body:                                         ; preds = %for.body, %entry
   %sub = sub nuw nsw i32 31, %i.08
   %shl = shl i32 %and, %sub
   %or = or i32 %shl, %b.07
   %inc = add nuw nsw i32 %i.08, 1
   %exitcond = icmp eq i32 %inc, 32
   br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !3
 }
 
+; CHECK-LABEL: @g
+define i32 @g(i32 %a, i32 %b) #0 {
+; CHECK: %0 = call i32 @llvm.bitreverse.i32(i32 %a)
+; CHECK: %1 = or i32 %0, %b
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret i32 %or
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.08 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %b.07 = phi i32 [ %b, %entry ], [ %or, %for.body ]
+  %shr = lshr i32 %a, %i.08
+  %and = and i32 %shr, 1
+  %sub = sub nuw nsw i32 31, %i.08
+  %shl = shl i32 %and, %sub
+  %or = or i32 %shl, %b.07
+  %inc = add nuw nsw i32 %i.08, 1
+  %exitcond = icmp eq i32 %inc, 32
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !3
+}
+
 attributes #0 = { norecurse nounwind readnone "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="cortex-a8" "target-features"="+dsp,+neon,+vfp3" "unsafe-fp-math"="false" "use-soft-float"="false" }
 
 !llvm.module.flags = !{!0, !1}
 !llvm.ident = !{!2}
 
 !0 = !{i32 1, !"wchar_size", i32 4}
 !1 = !{i32 1, !"min_enum_size", i32 4}
 !2 = !{!"clang version 3.8.0 (http://llvm.org/git/clang.git b7441a0f42c43a8eea9e3e706be187252db747fa)"}
 !3 = distinct !{!3, !4}
 !4 = !{!"llvm.loop.unroll.full"}