Fix a problem where the TwoAddressInstructionPass which generate redundant register moves in a loop.

From:
int M, total;
void foo() {
int i;
for (i = 0; i < M; i++) {
total = total + i / 2;
}
}

T

Fix a problem where the TwoAddressInstructionPass which generate redundant register moves in a loop.

From:
int M, total;
void foo() {
int i;
for (i = 0; i < M; i++) {
total = total + i / 2;
}
}

This is the kernel loop:

.LBB0_2: # %for.body

=>This Inner Loop Header: Depth=1
movl %edx, %esi
movl %ecx, %edx
shrl $31, %edx
addl %ecx, %edx
sarl %edx
addl %esi, %edx
incl %ecx
cmpl %eax, %ecx
jl .LBB0_2
--------------------------
The first mov insn "movl %edx, %esi" could be removed if we change "addl %esi, %edx" to "addl %edx, %esi".

The IR before TwoAddressInstructionPass is:
BB#2: derived from LLVM BB %for.body

Predecessors according to CFG: BB#1 BB#2
%vreg3<def> = COPY %vreg12<kill>; GR32:%vreg3,%vreg12
%vreg2<def> = COPY %vreg11<kill>; GR32:%vreg2,%vreg11
%vreg7<def,tied1> = SHR32ri %vreg3<tied0>, 31, %EFLAGS<imp-def,dead>; GR32:%vreg7,%vreg3
%vreg8<def,tied1> = ADD32rr %vreg3<tied0>, %vreg7<kill>, %EFLAGS<imp-def,dead>; GR32:%vreg8,%vreg3,%vreg7
%vreg9<def,tied1> = SAR32r1 %vreg8<kill,tied0>, %EFLAGS<imp-def,dead>; GR32:%vreg9,%vreg8
%vreg4<def,tied1> = ADD32rr %vreg9<kill,tied0>, %vreg2<kill>, %EFLAGS<imp-def,dead>; GR32:%vreg4,%vreg9,%vreg2
%vreg5<def,tied1> = INC64_32r %vreg3<kill,tied0>, %EFLAGS<imp-def,dead>; GR32:%vreg5,%vreg3
CMP32rr %vreg5, %vreg0, %EFLAGS<imp-def>; GR32:%vreg5,%vreg0
%vreg11<def> = COPY %vreg4; GR32:%vreg11,%vreg4
%vreg12<def> = COPY %vreg5<kill>; GR32:%vreg12,%vreg5
JL_4 <BB#2>, %EFLAGS<imp-use,kill>
Now TwoAddressInstructionPass will choose vreg9 to be tied with vreg4. However, it doesn't see that there is copy from vreg4 to vreg11 and another copy from vreg11 to vreg2 inside the loop body. To remove those copies, it is necessary to choose vreg2 to be tied with vreg4 instead of vreg9. This code pattern commonly appears when there is reduction operation in a loop.

So check for a reversed copy chain and if we encounter one then we can commute the add instruction so we can avoid a copy.

Patch by Wei Mi.
http://reviews.llvm.org/D7806

llvm-svn: 231148

show more ...

Replace some uses of getSubtargetImpl with the cached version
off of the MachineFunction or with the version that takes a
Function reference as an argument.

llvm-svn: 227185

Update SetVector to rely on the underlying set's insert to return a pair<iterator, bool>

This is to be consistent with StringSet and ultimately with the standard
library's associative container inse

Update SetVector to rely on the underlying set's insert to return a pair<iterator, bool>

This is to be consistent with StringSet and ultimately with the standard
library's associative container insert function.

This lead to updating SmallSet::insert to return pair<iterator, bool>,
and then to update SmallPtrSet::insert to return pair<iterator, bool>,
and then to update all the existing users of those functions...

llvm-svn: 222334

show more ...

Improve logic that decides if its profitable to commute when some of the virtual registers involved have uses/defs chains connecting them to physical register. Fix up the tests that this change impro

Improve logic that decides if its profitable to commute when some of the virtual registers involved have uses/defs chains connecting them to physical register. Fix up the tests that this change improves.

llvm-svn: 221336

show more ...

Remove the TargetMachine forwards for TargetSubtargetInfo based
information and update all callers. No functional change.

llvm-svn: 214781

[Modules] Remove potential ODR violations by sinking the DEBUG_TYPE
define below all header includes in the lib/CodeGen/... tree. While the
current modules implementation doesn't check for this kind

[Modules] Remove potential ODR violations by sinking the DEBUG_TYPE
define below all header includes in the lib/CodeGen/... tree. While the
current modules implementation doesn't check for this kind of ODR
violation yet, it is likely to grow support for it in the future. It
also removes one layer of macro pollution across all the included
headers.

Other sub-trees will follow.

llvm-svn: 206837

show more ...

[C++11] More 'nullptr' conversion. In some cases just using a boolean check instead of comparing to nullptr.

llvm-svn: 206142

Switch a number of loops in lib/CodeGen over to range-based for-loops, now that
the MachineRegisterInfo iterators are compatible with it.

llvm-svn: 204075

Phase 2 of the great MachineRegisterInfo cleanup. This time, we're changing
operator* on the by-operand iterators to return a MachineOperand& rather than
a MachineInstr&. At this point they almost

Phase 2 of the great MachineRegisterInfo cleanup. This time, we're changing
operator* on the by-operand iterators to return a MachineOperand& rather than
a MachineInstr&. At this point they almost behave like normal iterators!

Again, this requires making some existing loops more verbose, but should pave
the way for the big range-based for-loop cleanups in the future.

llvm-svn: 203865

show more ...

[C++11] Add 'override' keyword to virtual methods that override their base class.

llvm-svn: 203220

[C++11] Replace llvm::next and llvm::prior with std::next and std::prev.

Remove the old functions.

llvm-svn: 202636

Allow MachineCSE to coalesce trivial subregister copies the same way that it coalesces normal copies.

Without this, MachineCSE is powerless to handle redundant operations with truncated source opera

Allow MachineCSE to coalesce trivial subregister copies the same way that it coalesces normal copies.

Without this, MachineCSE is powerless to handle redundant operations with truncated source operands.

This required fixing the 2-addr pass to handle tied subregisters. It isn't clear what combinations of subregisters can legally be tied, but the simple case of truncated source operands is now safely handled:

%vreg11<def> = COPY %vreg1:sub_32bit; GR32:%vreg11 GR64:%vreg1
%vreg12<def> = COPY %vreg2:sub_32bit; GR32:%vreg12 GR64:%vreg2
%vreg13<def,tied1> = ADD32rr %vreg11<tied0>, %vreg12<kill>, %EFLAGS<imp-def>

Test case: cse-add-with-overflow.ll.

This exposed an existing bug in
PPCInstrInfo::commuteInstruction. Thanks to Rafael for the test case:
PowerPC/crash.ll.

llvm-svn: 197465

show more ...

Revert "Allow MachineCSE to coalesce trivial subregister copies the same way that it coalesces normal copies."

This reverts commit r197414.

It broke the ppc64 bootstrap. I will post a testcase in a

Revert "Allow MachineCSE to coalesce trivial subregister copies the same way that it coalesces normal copies."

This reverts commit r197414.

It broke the ppc64 bootstrap. I will post a testcase in a sec.

llvm-svn: 197424

show more ...

Allow MachineCSE to coalesce trivial subregister copies the same way
that it coalesces normal copies.

Without this, MachineCSE is powerless to handle redundant operations
with truncated source opera

Allow MachineCSE to coalesce trivial subregister copies the same way
that it coalesces normal copies.

Without this, MachineCSE is powerless to handle redundant operations
with truncated source operands.

This required fixing the 2-addr pass to handle tied subregisters. It
isn't clear what combinations of subregisters can legally be tied, but
the simple case of truncated source operands is now safely handled:

%vreg11<def> = COPY %vreg1:sub_32bit; GR32:%vreg11 GR64:%vreg1
%vreg12<def> = COPY %vreg2:sub_32bit; GR32:%vreg12 GR64:%vreg2
%vreg13<def,tied1> = ADD32rr %vreg11<tied0>, %vreg12<kill>, %EFLAGS<imp-def>

llvm-svn: 197414

show more ...

Rename LiveRange to LiveInterval::Segment

The Segment struct contains a single interval; multiple instances of this struct
are used to construct a live range, but the struct is not a live range by
i

Rename LiveRange to LiveInterval::Segment

The Segment struct contains a single interval; multiple instances of this struct
are used to construct a live range, but the struct is not a live range by
itself.

llvm-svn: 192392

show more ...

Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector size.

llvm-svn: 186274

TiedTo flag can now be placed on implicit operands. isTwoAddrUse() should look
at all of the operands. Previously it was skipping over implicit operands which
cause infinite looping when the two-addr

TiedTo flag can now be placed on implicit operands. isTwoAddrUse() should look
at all of the operands. Previously it was skipping over implicit operands which
cause infinite looping when the two-address pass try to reschedule a
two-address instruction below the kill of tied operand.

I'm unable to come up with a reasonably sized test case.
rdar://13747577

llvm-svn: 180906

show more ...

Register Coalescing: add a flag to disable rescheduling.

When MachineScheduler is enabled, this functionality can be
removed. Until then, provide a way to disable it for test cases and
designing Mac

Register Coalescing: add a flag to disable rescheduling.

When MachineScheduler is enabled, this functionality can be
removed. Until then, provide a way to disable it for test cases and
designing MachineScheduler heuristics.

llvm-svn: 180192

show more ...

Remove unused #includes.

llvm-svn: 176467

Add a use of an otherwise unused variable to remove a warning in non-Asserts
builds.

llvm-svn: 175981

TwoAddressInstructionPass::tryInstructionTransform() only potentially returns
true when shouldOnlyCommute is false, so we can remove code that checks
otherwise.

llvm-svn: 175980

TwoAddrInstructionPass::tryInstructionTransform() has a case where it calls
itself recursively with a new instruction that has not been finalized, in order
to determine whether to keep the instructio

TwoAddrInstructionPass::tryInstructionTransform() has a case where it calls
itself recursively with a new instruction that has not been finalized, in order
to determine whether to keep the instruction. On 'make check' and test-suite the
only cases where the recursive invocation made any transformations were simple
instruction commutations, so I am restricting the recursive invocation to do
only this.

The other cases wouldn't work correctly when updating LiveIntervals, since the
new instructions don't have slot indices and LiveIntervals hasn't yet been
updated. If the other transformations were actually triggering in any test case
it would be possible to support it with a lot of effort, but since they don't
it's not worth it.

llvm-svn: 175979

show more ...

TargetInstrInfo::commuteInstruction() doesn't actually return a new instruction
unless it was requested to with an optional parameter that defaults to false, so
we don't need to handle that case in T

TargetInstrInfo::commuteInstruction() doesn't actually return a new instruction
unless it was requested to with an optional parameter that defaults to false, so
we don't need to handle that case in TwoAddressInstructionPass.

llvm-svn: 175974

show more ...

Fix a bug with the LiveIntervals updating in the two-address pass found by
running ASCI_Purple/SMG2000 in the test-suite.

llvm-svn: 175957

Make TwoAddressInstructionPass::sink3AddrInstruction() LiveIntervals-aware.

llvm-svn: 175956