Subzero: Initial implementation of BB Local CSE

Subzero: Initial implementation of BB Local CSE

Adds Cfg::localCse for basic-block local common-subexpression elimination
If we have
    t1 = op b c
    t2 = op b c
This pass will replace future uses of t2 in a basic block by t1.

To enable, use -enable-experimental in O2

BUG=none

[manasijm, 2016-05-18 21:35:54]

Description was changed from

==========
Subzero: Initial implementation of BB Local CSE

Adds Cfg::localCse
To enable, use -experimental-opts in O2

BUG=none
==========

to

==========
Subzero: Initial implementation of BB Local CSE

Adds Cfg::localCse
To enable, use -experimental-opts in O2

BUG=none
==========

[manasijm, 2016-05-18 21:35:55]

manasijm@google.com changed reviewers:
+ eholk@chromium.org, jpp@chromium.org, kschimpf@google.com,
stichnot@chromium.org

[Jim Stichnoth, 2016-05-19 01:35:50]

I haven't looked deeply at the core of the algorithm yet.  Let's get these
structural issues out of the way first.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (left):

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#oldcode30
src/IceCfg.cpp:30: 
don't remove this separator blank line

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode509
src/IceCfg.cpp:509: void Cfg::localCSE() {
(putting this comment here for lack of a better place)

This CL definitely needs tests.  I think you should construct a new .ll test
file and demonstrate expected behavior for x86-32 and x86-64.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode517
src/IceCfg.cpp:517: for (unsigned int i = 0; i < Instr->getSrcSize(); ++i) {
SizeT instead of unsigned int

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode518
src/IceCfg.cpp:518: Operand *Opr = Instr->getSrc(i);
I would name it not "Opr", but "Op" or "Opnd" to follow other existing
conventions.  (Unfortunately the most popular name for an Operand* variable is
"Operand", which isn't good...)

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode519
src/IceCfg.cpp:519: if (Variable *Var = llvm::dyn_cast<Variable>(Opr)) {
auto *Var
because the type is already clear from the dyn_cast<>

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode520
src/IceCfg.cpp:520: Result ^= std::hash<uint32_t>()(Var->getIndex());
Can you use SizeT instead of uint32_t, to match the getIndex() declaration?

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode521
src/IceCfg.cpp:521: } else if (Constant *Cst = llvm::dyn_cast<Constant>(Opr)) {
Name it "Const" instead of "Cst" for consistency.

And use "auto *Const = ..."

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode523
src/IceCfg.cpp:523: Cst); // TODO : get Value ConstantPrimitive
TODO(manasijm): get ...

Also, probably put the TODO comment on a separate line so that clang-format
doesn't do this horrible thing.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode527
src/IceCfg.cpp:527: return Result;
Use early returns more aggressively, per
http://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-sim...
.

E.g.:
  if (auto *Var = llvm::dyn_cast<Variable>) {
    return ...;
  }
  if (auto *Const = ...) {
    return ...;
  }
etc.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode531
src/IceCfg.cpp:531: bool operator()(Inst *const InstrA, Inst *const InstrB)
const {
Shouldn't this be "const Inst *InstrA"?  Those are two different meanings.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode533
src/IceCfg.cpp:533: (InstrA->getSrcSize() == InstrB->getSrcSize());
I think this can be made clearer and more efficient through early returns.

The way this is structured, if Result every becomes false, it will always remain
false.  So why not early-return false when any of the intermediate conditions
are false, and then return true at the end after everything is checked.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode535
src/IceCfg.cpp:535: if (llvm::isa<InstArithmetic>(InstrA)) {
if (auto *A = llvm::dyn_cast<InstArithmetic>(InstrA)) {

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode536
src/IceCfg.cpp:536: auto A = llvm::dyn_cast<InstArithmetic>(InstrA);
auto *A
auto *B

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode537
src/IceCfg.cpp:537: auto B = llvm::dyn_cast<InstArithmetic>(InstrB);
use llvm::cast<> instead of llvm::dyn_cast<> here.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode541
src/IceCfg.cpp:541: for (unsigned int i = 0; i < InstrA->getSrcSize() && Result;
++i) {
SizeT i

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode542
src/IceCfg.cpp:542: Result = Result && (InstrA->getSrc(i) == InstrB->getSrc(i));
Be aware that Operand* pointer equality is fine with Constant* and Variable*,
but not necessarily for a target-specific operand type, e.g. X86OperandMem. 
It's not a problem now since this pass is very early, before any target-specific
operands are created, but it would be nice to make it more future-proof.

For example, create a virtual method in the Operand base class, where the
default implementation does a llvm::report_fatal_error(), and then Variable and
Constant override it with a simple pointer comparison.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode548
src/IceCfg.cpp:548: size_t operator()(Variable *Var) const {
const Variable *
?

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode549
src/IceCfg.cpp:549: return std::hash<uint32_t>()(Var->getIndex());
Can this be SizeT instead of uint32_t?

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode553
src/IceCfg.cpp:553: std::unordered_map<Inst *, Variable *, InstHash, InstEq,
You should be able to do:

CfgUnorderedMap<Inst *, Variable *, InstHash, InstEq> Seen;

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode556
src/IceCfg.cpp:556: // This could be converted to an unordered_set without much
effort.
If that's true, and reasonable, then just do it?
You also have CfgUnorderedSet<> available.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode560
src/IceCfg.cpp:560: // Combining the above two into a single data structure
Reflow comment to 80-col

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode568
src/IceCfg.cpp:568: // Not necessary for SSA, still keeping it in case this pass
is
reflow comment

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode587
src/IceCfg.cpp:587: // replace - doing this before checking for repitions
repetitions
and reflow to 80-col

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode589
src/IceCfg.cpp:589: for (unsigned int i = 0; i < Instr.getSrcSize(); ++i) {
SizeT

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode591
src/IceCfg.cpp:591: if (Variable *const Var = llvm::dyn_cast<Variable>(Opr)) {
auto *

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode598
src/IceCfg.cpp:598: // check for repititions
repetitions

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode602
src/IceCfg.cpp:602: // Instr.setDeleted();
remove commented-out line

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode606
src/IceCfg.cpp:606: for (unsigned int i = 0; i < Instr.getSrcSize(); ++i) {
SizeT

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode608
src/IceCfg.cpp:608: if (Variable *Var = llvm::dyn_cast<Variable>(Opr)) {
auto *Var

https://codereview.chromium.org/1997443002/diff/1/src/IceClFlags.def
File src/IceClFlags.def (right):

https://codereview.chromium.org/1997443002/diff/1/src/IceClFlags.def#newcode143
src/IceClFlags.def:143: X(SubzeroExperimentalOptsEnabled, bool, dev_opt_flag,
"experimental-opts",   \
I think you can remove the "Subzero" prefix, because that is pretty much assumed
here.

And to keep a consistent naming style, I would suggest something like
"-enable-experimental" and name the variable something like EnableExperimental.

https://codereview.chromium.org/1997443002/diff/1/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1997443002/diff/1/src/IceInst.h#newcode112
src/IceInst.h:112: assert(Index < NumSrcs);
For safety, add a couple more asserts:
  assert(!isDeleted());
  assert(LiveRangesEnded == 0);

The latter one mostly ensures you don't call the method at a point where it
might be "dangerous" because you're relying on previously computed liveness info
that might now become out of sync.

[manasijm, 2016-05-19 02:01:53]

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode509
src/IceCfg.cpp:509: void Cfg::localCSE() {
On 2016/05/19 01:35:49, stichnot wrote:
> (putting this comment here for lack of a better place)
> 
> This CL definitely needs tests.  I think you should construct a new .ll test
> file and demonstrate expected behavior for x86-32 and x86-64.

I have not managed to isolate a small example yet unfortunately.
None of the convoluted field access constructs I produced on my own generated
anything similar to what 188.ammp had.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode521
src/IceCfg.cpp:521: } else if (Constant *Cst = llvm::dyn_cast<Constant>(Opr)) {
On 2016/05/19 01:35:49, stichnot wrote:
> Name it "Const" instead of "Cst" for consistency.
> 
> And use "auto *Const = ..."

Ok, didn't do that in the first place because const being a keyword, Const might
look confusing.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode531
src/IceCfg.cpp:531: bool operator()(Inst *const InstrA, Inst *const InstrB)
const {
On 2016/05/19 01:35:48, stichnot wrote:
> Shouldn't this be "const Inst *InstrA"?  Those are two different meanings.

I had some const correctness trouble with that. Will recheck.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode542
src/IceCfg.cpp:542: Result = Result && (InstrA->getSrc(i) == InstrB->getSrc(i));
On 2016/05/19 01:35:48, stichnot wrote:
> Be aware that Operand* pointer equality is fine with Constant* and Variable*,
> but not necessarily for a target-specific operand type, e.g. X86OperandMem. 
> It's not a problem now since this pass is very early, before any
target-specific
> operands are created, but it would be nice to make it more future-proof.
> 
> For example, create a virtual method in the Operand base class, where the
> default implementation does a llvm::report_fatal_error(), and then Variable
and
> Constant override it with a simple pointer comparison.

Or just returning false if they are not Constant* or Variable* should work.
Why should it be a fatal error ?

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode598
src/IceCfg.cpp:598: // check for repititions
typo, will update on next patchset.

[manasijm, 2016-05-19 17:50:17]

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (left):

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#oldcode30
src/IceCfg.cpp:30: 
On 2016/05/19 01:35:50, stichnot wrote:
> don't remove this separator blank line

Done.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode519
src/IceCfg.cpp:519: if (Variable *Var = llvm::dyn_cast<Variable>(Opr)) {
On 2016/05/19 01:35:49, stichnot wrote:
> auto *Var
> because the type is already clear from the dyn_cast<>

Done.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode520
src/IceCfg.cpp:520: Result ^= std::hash<uint32_t>()(Var->getIndex());
On 2016/05/19 01:35:49, stichnot wrote:
> Can you use SizeT instead of uint32_t, to match the getIndex() declaration?

Done.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode527
src/IceCfg.cpp:527: return Result;
On 2016/05/19 01:35:49, stichnot wrote:
> Use early returns more aggressively, per
>
http://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-sim...
> .
> 
> E.g.:
>   if (auto *Var = llvm::dyn_cast<Variable>) {
>     return ...;
>   }
>   if (auto *Const = ...) {
>     return ...;
>   }
> etc.
Not applicable here, all the sources has to be incorporated in the hash.
Will do this for InstEq.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode531
src/IceCfg.cpp:531: bool operator()(Inst *const InstrA, Inst *const InstrB)
const {
On 2016/05/19 02:01:53, manasijm wrote:
> On 2016/05/19 01:35:48, stichnot wrote:
> > Shouldn't this be "const Inst *InstrA"?  Those are two different meanings.
> 
> I had some const correctness trouble with that. Will recheck.

Done.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode598
src/IceCfg.cpp:598: // check for repititions
On 2016/05/19 02:01:53, manasijm wrote:
> typo, will update on next patchset.

Done.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode602
src/IceCfg.cpp:602: // Instr.setDeleted();
On 2016/05/19 01:35:49, stichnot wrote:
> remove commented-out line

Done.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode606
src/IceCfg.cpp:606: for (unsigned int i = 0; i < Instr.getSrcSize(); ++i) {
On 2016/05/19 01:35:49, stichnot wrote:
> SizeT

Done.

https://codereview.chromium.org/1997443002/diff/1/src/IceCfg.cpp#newcode608
src/IceCfg.cpp:608: if (Variable *Var = llvm::dyn_cast<Variable>(Opr)) {
On 2016/05/19 01:35:49, stichnot wrote:
> auto *Var

Done.

https://codereview.chromium.org/1997443002/diff/1/src/IceClFlags.def
File src/IceClFlags.def (right):

https://codereview.chromium.org/1997443002/diff/1/src/IceClFlags.def#newcode143
src/IceClFlags.def:143: X(SubzeroExperimentalOptsEnabled, bool, dev_opt_flag,
"experimental-opts",   \
On 2016/05/19 01:35:50, stichnot wrote:
> I think you can remove the "Subzero" prefix, because that is pretty much
assumed
> here.
> 
> And to keep a consistent naming style, I would suggest something like
> "-enable-experimental" and name the variable something like
EnableExperimental.

Done.

[Jim Stichnoth, 2016-05-23 16:52:57]

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode510
src/IceCfg.cpp:510: void Cfg::localCSE() {
I'd like to have a comment here briefly describing the assumptions and scope of
the analysis/transformation.  E.g., block-local; target common subexpressions
left by GEP simplification pass; allow for this to be done on non-SSA form such
as after simple Phi lowering.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode521
src/IceCfg.cpp:521: Result ^= std::hash<SizeT>()(Var->getIndex());
This is a repetition of the VariableHash implementation below, hopefully the
duplication can be avoided.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode524
src/IceCfg.cpp:524: // TODO : get Value of ConstantPrimitive
If I understand this correctly, your hash function is based on the pointer
value.  Please hash on contents instead, otherwise you risk non-deterministic
execution.  Perhaps it wouldn't affect the output directly, but it might affect
bucketing performance?  And it's just not a good path to start down.

Suggestion: add a virtual hash method to Operand.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode533
src/IceCfg.cpp:533: if (!(llvm::isa<Variable>(A) || (llvm::isa<Constant>(A))) ||
This is really hard to read/understand.  How about something more like:

  if (llvm::isa<Variable>(A))
    return (A == B);
  if (llvm::isa<Constant>(A))
    return (A == B);
  return false;

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode536
src/IceCfg.cpp:536: // No reason this has to an error. Returning false just
disables the cse
"has to an error" ==> "has to be an error" ?

And no reason for *what* to be an error?  I don't see any errors being signaled.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode546
src/IceCfg.cpp:546: auto B = llvm::cast<InstArithmetic>(InstrB);
auto *

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode547
src/IceCfg.cpp:547: // A, B are guranteed to be of the same 'kind' at this point
guaranteed

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode548
src/IceCfg.cpp:548: // So, dyn_Cast is not needed
dyn_cast

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode589
src/IceCfg.cpp:589: for (auto Dep : DepIter->second) {
I think this use of "auto" is getting too deep for easy comprehension.  Can you
do something like one of these?

  for (auto *DepInst : DepIter->second) { ... }

  for (Inst *Dep : DepIter->second) { ... }

(assuming I managed to work out the types correctly)

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode599
src/IceCfg.cpp:599: if (Variable *const Var = llvm::dyn_cast<Variable>(Opnd)) {
"Variable *const Var" just means that the value of the Var pointer won't change.
 It doesn't prevent Var->SomeField from being changed.  What if any const do you
really want here?

https://codereview.chromium.org/1997443002/diff/80001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/local-cse.ll (right):

https://codereview.chromium.org/1997443002/diff/80001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/local-cse.ll:2: ; RUN: %p2i -i %s --filetype=asm
--target x8632 --args -threads=0 \
1. Instead of "--filetype=asm", use "--filetype=obj --disassemble".  Otherwise
the test will fail in a MINIMAL build (or more generally, a NODUMP build)
because only filetype=obj is supported there.

2. No need to specify -threads=0 here.  In fact, using the default (threads=2)
is encouraged in order to draw out non-determinism that might have snuck in.

3. Once you add "--disassemble", you will need to modify the CHECK lines to
follow Intel asm syntax, rather than AT&T syntax.  (i.e., s/addl/add/ )

https://codereview.chromium.org/1997443002/diff/80001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/local-cse.ll:22: ; X8632: addl
There is a lot of repetition of fixed patterns in the test output.  This can be
mitigated by using multiple --check-prefix arguments in the RUN command.  Below,
I've made this modification to the test.  "X8632" represents the output that is
always there for target=x8632, regardless of -enable-experimental.  "X8632EXP"
output should be there when using -enable-experimental, and "X8632NOEXP" when
not using it.

Also, you might consider further simplifying the test patterns since x8632 and
x8664 output are identical with respect to what's being tested.  I.e., just use
"X86" instead of "X8632" and "X8664".

; Tests local-cse on x8632 and x8664

; RUN: %p2i -i %s --filetype=obj --disassemble --target x8632 --args \
; RUN: -O2 -enable-experimental | FileCheck --check-prefix=X8632 --check-prefix
X8632EXP %s

; RUN: %p2i -i %s --filetype=obj --disassemble --target x8632 --args \
; RUN: -O2 | FileCheck --check-prefix=X8632 --check-prefix X8632NOEXP %s

; RUN: %p2i -i %s --filetype=obj --disassemble --target x8664 --args \
; RUN: -O2 -enable-experimental | FileCheck --check-prefix=X8664 --check-prefix
X8664EXP %s

; RUN: %p2i -i %s --filetype=obj --disassemble --target x8664 --args \
; RUN: -O2 | FileCheck --check-prefix=X8664 --check-prefix X8664NOEXP %s


define internal i32 @local_cse_test(i32 %a, i32 %b) {
entry:
  %add1 = add i32 %b, %a
  %add2 = add i32 %b, %a
  %add3 = add i32 %add1, %add2
  ret i32 %add3
}
; X8632: add
; X8632: add
; X8632NOEXP: add
; X8632EXP-NOT: add
; X8632: ret

; X8664: add
; X8664: add
; X8664NOEXP: add
; X8664EXP-NOT: add
; X8664: ret

https://codereview.chromium.org/1997443002/diff/80001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/local-cse.ll:41: 
Remove trailing whitespace (i.e. blank line at the end of file) to keep git
happy.

[manasijm, 2016-05-23 23:13:30]

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode510
src/IceCfg.cpp:510: void Cfg::localCSE() {
On 2016/05/23 16:52:56, stichnot wrote:
> I'd like to have a comment here briefly describing the assumptions and scope
of
> the analysis/transformation.  E.g., block-local; target common subexpressions
> left by GEP simplification pass; allow for this to be done on non-SSA form
such
> as after simple Phi lowering.

Done.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode521
src/IceCfg.cpp:521: Result ^= std::hash<SizeT>()(Var->getIndex());
On 2016/05/23 16:52:57, stichnot wrote:
> This is a repetition of the VariableHash implementation below, hopefully the
> duplication can be avoided.

Done.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode524
src/IceCfg.cpp:524: // TODO : get Value of ConstantPrimitive
On 2016/05/23 16:52:57, stichnot wrote:
> If I understand this correctly, your hash function is based on the pointer
> value.  Please hash on contents instead, otherwise you risk non-deterministic
> execution.  Perhaps it wouldn't affect the output directly, but it might
affect
> bucketing performance?  And it's just not a good path to start down.
> 
> Suggestion: add a virtual hash method to Operand.

Done.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode533
src/IceCfg.cpp:533: if (!(llvm::isa<Variable>(A) || (llvm::isa<Constant>(A))) ||
On 2016/05/23 16:52:56, stichnot wrote:
> This is really hard to read/understand.  How about something more like:
> 
>   if (llvm::isa<Variable>(A))
>     return (A == B);
>   if (llvm::isa<Constant>(A))
>     return (A == B);
>   return false;

Done.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode546
src/IceCfg.cpp:546: auto B = llvm::cast<InstArithmetic>(InstrB);
On 2016/05/23 16:52:56, stichnot wrote:
> auto *

Done.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode547
src/IceCfg.cpp:547: // A, B are guranteed to be of the same 'kind' at this point
On 2016/05/23 16:52:57, stichnot wrote:
> guaranteed

Done.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode548
src/IceCfg.cpp:548: // So, dyn_Cast is not needed
On 2016/05/23 16:52:57, stichnot wrote:
> dyn_cast

Done.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode589
src/IceCfg.cpp:589: for (auto Dep : DepIter->second) {
On 2016/05/23 16:52:57, stichnot wrote:
> I think this use of "auto" is getting too deep for easy comprehension.  Can
you
> do something like one of these?
> 
>   for (auto *DepInst : DepIter->second) { ... }
> 
>   for (Inst *Dep : DepIter->second) { ... }
> 
> (assuming I managed to work out the types correctly)

Done.

https://codereview.chromium.org/1997443002/diff/80001/src/IceCfg.cpp#newcode599
src/IceCfg.cpp:599: if (Variable *const Var = llvm::dyn_cast<Variable>(Opnd)) {
On 2016/05/23 16:52:57, stichnot wrote:
> "Variable *const Var" just means that the value of the Var pointer won't
change.
>  It doesn't prevent Var->SomeField from being changed.  What if any const do
you
> really want here?

Artifact from first patch set.

https://codereview.chromium.org/1997443002/diff/80001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/local-cse.ll (right):

https://codereview.chromium.org/1997443002/diff/80001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/local-cse.ll:2: ; RUN: %p2i -i %s --filetype=asm
--target x8632 --args -threads=0 \
On 2016/05/23 16:52:57, stichnot wrote:
> 1. Instead of "--filetype=asm", use "--filetype=obj --disassemble".  Otherwise
> the test will fail in a MINIMAL build (or more generally, a NODUMP build)
> because only filetype=obj is supported there.
> 
> 2. No need to specify -threads=0 here.  In fact, using the default (threads=2)
> is encouraged in order to draw out non-determinism that might have snuck in.
> 
> 3. Once you add "--disassemble", you will need to modify the CHECK lines to
> follow Intel asm syntax, rather than AT&T syntax.  (i.e., s/addl/add/ )

Done.

https://codereview.chromium.org/1997443002/diff/80001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/local-cse.ll:22: ; X8632: addl
On 2016/05/23 16:52:57, stichnot wrote:
> There is a lot of repetition of fixed patterns in the test output.  This can
be
> mitigated by using multiple --check-prefix arguments in the RUN command. 
Below,
> I've made this modification to the test.  "X8632" represents the output that
is
> always there for target=x8632, regardless of -enable-experimental.  "X8632EXP"
> output should be there when using -enable-experimental, and "X8632NOEXP" when
> not using it.
> 
> Also, you might consider further simplifying the test patterns since x8632 and
> x8664 output are identical with respect to what's being tested.  I.e., just
use
> "X86" instead of "X8632" and "X8664".
> 
> ; Tests local-cse on x8632 and x8664
> 
> ; RUN: %p2i -i %s --filetype=obj --disassemble --target x8632 --args \
> ; RUN: -O2 -enable-experimental | FileCheck --check-prefix=X8632
--check-prefix
> X8632EXP %s
> 
> ; RUN: %p2i -i %s --filetype=obj --disassemble --target x8632 --args \
> ; RUN: -O2 | FileCheck --check-prefix=X8632 --check-prefix X8632NOEXP %s
> 
> ; RUN: %p2i -i %s --filetype=obj --disassemble --target x8664 --args \
> ; RUN: -O2 -enable-experimental | FileCheck --check-prefix=X8664
--check-prefix
> X8664EXP %s
> 
> ; RUN: %p2i -i %s --filetype=obj --disassemble --target x8664 --args \
> ; RUN: -O2 | FileCheck --check-prefix=X8664 --check-prefix X8664NOEXP %s
> 
> 
> define internal i32 @local_cse_test(i32 %a, i32 %b) {
> entry:
>   %add1 = add i32 %b, %a
>   %add2 = add i32 %b, %a
>   %add3 = add i32 %add1, %add2
>   ret i32 %add3
> }
> ; X8632: add
> ; X8632: add
> ; X8632NOEXP: add
> ; X8632EXP-NOT: add
> ; X8632: ret
> 
> ; X8664: add
> ; X8664: add
> ; X8664NOEXP: add
> ; X8664EXP-NOT: add
> ; X8664: ret

Done.

https://codereview.chromium.org/1997443002/diff/80001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/local-cse.ll:41: 
On 2016/05/23 16:52:57, stichnot wrote:
> Remove trailing whitespace (i.e. blank line at the end of file) to keep git
> happy.

Done.

[Jim Stichnoth, 2016-05-24 04:58:11]

otherwise lgtm

https://codereview.chromium.org/1997443002/diff/100001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1997443002/diff/100001/src/IceCfg.cpp#newcode527
src/IceCfg.cpp:527: SizeT operator()(const Variable *Var) const { return
Var->hashValue(); }
For these hash functions, I think it's more standard to return a size_t value.

https://codereview.chromium.org/1997443002/diff/100001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1997443002/diff/100001/src/IceInst.h#newcode114
src/IceInst.h:114: assert(LiveRangesEnded == 0);
Add a brief comment why this assert is needed (the other asserts are clear).

Something like: Try to ensure this is not called after liveness analysis runs,
because last-use info will surely become incorrect.

https://codereview.chromium.org/1997443002/diff/100001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1997443002/diff/100001/src/IceOperand.h#newco...
src/IceOperand.h:162: virtual SizeT hashValue() const override { return 0; }
You shouldn't need "virtual" if you're using "override".

[manasijm, 2016-05-24 16:48:47]

Description was changed from

==========
Subzero: Initial implementation of BB Local CSE

Adds Cfg::localCse
To enable, use -experimental-opts in O2

BUG=none
==========

to

==========
Subzero: Initial implementation of BB Local CSE

Adds Cfg::localCse for basic-block local common-subexpression elimination
If we have
    t1 = op b c
    t2 = op b c
This pass will replace future uses of t2 in a basic block by t1.

To enable, use -enable-experimental in O2

BUG=none
==========

[manasijm, 2016-05-24 16:54:22]

https://codereview.chromium.org/1997443002/diff/100001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1997443002/diff/100001/src/IceCfg.cpp#newcode527
src/IceCfg.cpp:527: SizeT operator()(const Variable *Var) const { return
Var->hashValue(); }
On 2016/05/24 04:58:11, stichnot wrote:
> For these hash functions, I think it's more standard to return a size_t value.

Done.

https://codereview.chromium.org/1997443002/diff/100001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1997443002/diff/100001/src/IceInst.h#newcode114
src/IceInst.h:114: assert(LiveRangesEnded == 0);
On 2016/05/24 04:58:11, stichnot wrote:
> Add a brief comment why this assert is needed (the other asserts are clear).
> 
> Something like: Try to ensure this is not called after liveness analysis runs,
> because last-use info will surely become incorrect.

Done.

https://codereview.chromium.org/1997443002/diff/100001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1997443002/diff/100001/src/IceOperand.h#newco...
src/IceOperand.h:162: virtual SizeT hashValue() const override { return 0; }
On 2016/05/24 04:58:11, stichnot wrote:
> You shouldn't need "virtual" if you're using "override".

Done.

[Jim Stichnoth, 2016-05-24 22:02:53]

Committed in 032c315836b8c1ed9ff6bb2be1981b6d4a1a3594.
Not automatically mailed/closed due to authentication fail.