[GISel][KnownBits] Update a comment regarding the effect of cache on PHIs
authorQuentin Colombet <qcolombet@apple.com>
Tue, 25 Feb 2020 22:03:21 +0000 (14:03 -0800)
committerQuentin Colombet <qcolombet@apple.com>
Tue, 25 Feb 2020 23:56:15 +0000 (15:56 -0800)
commit5bf0023b0d706bb8817f1e58145996cccc2f2c58
tree42c8a73598ccfa0dd1b6c8e2bf85fb537c39380d
parent3cefebc3fe1e962983fc2c8a06dc7fca074678ce
[GISel][KnownBits] Update a comment regarding the effect of cache on PHIs

Unlike what I claimed in my previous commit. The caching is
actually not NFC on PHIs.

When we put a big enough max depth, we end up simulating loops.
The cache is effectively cutting the simulation short and we
get less information as a result.
E.g.,
```
v0 = G_CONSTANT i8 0xC0
jump
v1 = G_PHI i8 v0, v2
v2 = G_LSHR i8 v1, 1
```

Let say we want the known bits of v1.
- With cache:
Set v1 cache to we know nothing
v1 is v0 & v2
v0 gives us 0xC0
v2 gives us known bits of v1 >> 1
v1 is in the cache
=> v1 is 0, thus v2 is 0x80
Finally v1 is v0 & v2 => 0x80

- Without cache and enough depth to do two iteration of the loop:
v1 is v0 & v2
v0 gives us 0xC0
v2 gives us known bits of v1 >> 1
v1 is v0 & v2
v0 is 0xC0
v2 is v1 >> 1
Reach the max depth for v1...
unwinding
v1 is know nothing
v2 is 0x80
v0 is 0xC0
v1 is 0x80
v2 is 0xC0
v0 is 0xC0
v1 is 0xC0

Thus now v1 is 0xC0 instead of 0x80.

I've added a unittest demonstrating that.

NFC
llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp
llvm/unittests/CodeGen/GlobalISel/KnownBitsTest.cpp