[LLVMbugs] [Bug 6773] New: Add Instruction Fold for Masked Merge

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=6773

           Summary: Add Instruction Fold for Masked Merge
           Product: new-bugs
           Version: unspecified
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: me22.ca at gmail.com
                CC: llvmbugs at cs.uiuc.edu


When experimenting with SHA, I was pleased to notice that LLVM will fold the
"Maj" function (x & y) ^ (x & z) ^ (y & z) down to ((z ^ y) & x) ^ (y & z).

The "Ch" function, though, doesn't fold.  (x & y) | (~x & z) should become ((y
^ z) & x) ^ z, as mentioned on
http://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge (as should (x &
y) ^ (~x & z), the version used in the SHA standard).

(If you're wondering at the similarity, Maj(x,y,z) is equivalent to Ch(x, y|z,
y&z).  Using that implementation with the optimized Ch again gives optimal code
from LLVM as it knows to fold (y|z)^(y&z) down to y^z.)


LLVM IR from Bitter Melon:

define i32 @Ch(i32 %x, i32 %y, i32 %z) nounwind readnone {
entry:
  %0 = and i32 %y, %x                             ; <i32> [#uses=1]
  %not = xor i32 %x, -1                           ; <i32> [#uses=1]
  %1 = and i32 %z, %not                           ; <i32> [#uses=1]
  %2 = xor i32 %1, %0                             ; <i32> [#uses=1]
  ret i32 %2
}

define i32 @Maj(i32 %x, i32 %y, i32 %z) nounwind readnone {
entry:
  %0 = xor i32 %z, %y                             ; <i32> [#uses=1]
  %1 = and i32 %0, %x                             ; <i32> [#uses=1]
  %2 = and i32 %z, %y                             ; <i32> [#uses=1]
  %3 = xor i32 %1, %2                             ; <i32> [#uses=1]
  ret i32 %3
}

define i32 @Ch2(i32 %x, i32 %y, i32 %z) nounwind readnone {
entry:
  %0 = xor i32 %z, %y                             ; <i32> [#uses=1]
  %1 = and i32 %0, %x                             ; <i32> [#uses=1]
  %2 = xor i32 %1, %z                             ; <i32> [#uses=1]
  ret i32 %2
}

define i32 @Maj2(i32 %x, i32 %y, i32 %z) nounwind readnone {
entry:
  %0 = and i32 %z, %y                             ; <i32> [#uses=1]
  %1 = xor i32 %z, %y                             ; <i32> [#uses=1]
  %2 = and i32 %1, %x                             ; <i32> [#uses=1]
  %3 = xor i32 %2, %0                             ; <i32> [#uses=1]
  ret i32 %3
}


>From the following C source:

int Ch(int x, int y, int z) {
   return (x&y) ^ (~x&z);
}
int Maj(int x, int y, int z) {
   return (x&y) ^ (x&z) ^ (y&z);
}

int Ch2(int x, int y, int z) {
   return z ^ ((y ^ z) & x);
}
int Maj2(int x, int y, int z) {
   return Ch2(x, y|z, y&z);
}

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.