LGTM

I'm not too familiar with the history of OptimizePHIs but some things feel odd to me here:

• The comments in the pass make it seem like it is designed to catch dataflow around loops, yet the motivation for your changes appears to be simpler phis without loops involved.
• I keep wondering why we bother with COPYs here at all. If the COPYs are really trivial COPYs between the same register classes then we really should just remove them when we are still in MachineSSA. Do you know how they are created? Maybe you can simply stop their creation instead?
• Skipping COPYs like this is also a bit inconsequential and will miss several cases: You could have more than 1 COPY in a row or switch between register classes. The PeepholeOptimizer pass already handles these more complex cases, so maybe we rather should look for running OptimizePHIs after the Peephole Optimizer so those COPYs are optimized? (Not sure though if there are other negative effects of running OptimizePHIs later or PeepholeOpt earlier).

Seems useful. Please implement consistently for all stop/start args and document it somewhere.

• Address review feedback

I'm currently less active in LLVM and will not have the time to review this in depth. Some comments:

I certainly was always annoyed that bugpoint wouldn't pick up the tools in the same build directory forcing me to manually specify paths to the tools.
However unfortunately this isn't going far enough and will still search the tools in PATH first, which can still be annoying as in my experience you can often have llvm developer tools installed by your distribution/package managers etc. in your PATH.

Some notes on what is left here:

• Change allocation direction to go from end to begin of a basic block.
• Change debug value handling: The tricky thing with the changed direction is that we dealing with dangling DBG_VALUE instructions (they have a vreg use after the last non-debug use of a vreg) gets trickier. They are rare but occur in several unittests so we now track them separately in the code and perform a forward walk each time after the vreg is allocation by the real last use to see whether the register reached the dangling DBG_VALUE.
• This also simplifies DBG_VALUE handling, to always referenvce stack slots in case of spills as we now place spills immediately adjacent to the definition of a value/register.
• Generally rewrote allocateInstruction to be hopefolly somewhat simpler
• Added some heuristic for tricky inline assembly early clobber situations: If we detect a tricky situation now, we will take all def and early-clobber like operands and sort them by the size of the register class so that we can assign tricky cases more consistently and are more likely to be successfull (this was necessary to fix some unittests that were lucky with the old allocation algorithm but unlucky with the new one. With the new heuristic we should be less dependent on luck).

• Simpler patch now that more things have been split up into separate review and NFC patches.

• I split up two more NFC commits: rL346575 and rL346576.
• I split several step by step patches to ease review (note that I did not bother to fix hundreds of testcases for the intermediate steps, so I will not commit them independently): D54364, D54365, D54366, D54367, D54368

This is part of my rewrite regallocfast series. See also D52010

This is part of my rewrite regallocfast series. See also D52010

This is part of my regallocfast rewrite series, see also D52010

Maybe you can give it at least some cursory review?

Take my "meh" as LGTM if nobody objects in the next couple days.

The whole registry system isn't used much. The whole machine seems a little overengineered in retrospect (there only ever is a single listener for example). But making it typesafe seems sensible.

And fix one more variable name typo (sorry for all the updates).

And fix one more variable name typo (sorry for all the updates).

Tweak some more comments.

fix typos

• Added two more tests
• Revamped explanation of the transformation. It's better but I fear still very hard to crasp. Oh well it's as good as I can make it right now...

@mstorsjo could you check if this fixes your original problem?

After pondering about this again, this should be the correct fix.

I extracted a couple of obvious cleanups to reduce the code churn here. They landed in rL346287, rL346288, rL346289, rL346296, rL346297, rL346298
(will update and split the diff here soon)

In D52010#1289784, @atanasyan wrote:

@abeserminji: Aleksandar, could you take a look at the RegAllocFast::reloadAtBegin? It looks like a necessity of using the rafast-ignore-missing-defs option is caused by the rL336328 commit.

@mips target owners: Please take a look at the unittests where I had to use -rafast-ignore-missing-defs to workaround invalid machine code. Those tests use a virtual register before it is defined (the old regalloc fast used to just ignore this in some cases).

• Adapted all the unit tests
• Slight tuning of register hinting code
• Improved allocation heuristic for livethrough and earlyclobber registers, allowing us to allocate more inline assembly constructs consistently (rather than the previous allocator doing it by luck).

It seems to have a bug now where the first time a physical register is used, it immediately sets kill on it even though there are further uses of the same def

hmm this is still buggy...

Putting this up for early review, still need to create a minimal testcase.

Unfortunately, it doesn't seem to fix the problem reported in that PR. But maybe it gets us closer to being able to fix it?

I'm not opposed to this change. But out of curiosity:

In D49671#1282086, @materi wrote:

This patch is causing some problems in my out-of-tree back-end. We add some MachineOperands on the fly for some uses/defs that are conditional or depend on some circumstances, like how registers were allocated, or which depth a loop is at in a loop nest. With this patch, these manually added operands don't work as we intend.

Would you be in a position to mark your extra operands as explicit operands since the machine does appear to be reading/writing them in your case? (Maybe you have to mark the instruction as variadic, or I would be open to invent a new MCInstrDesc flag if that helps...)

In D49671#1283704, @materi wrote:

In D49671#1283621, @jonpa wrote:

I'm wondering if we could maybe keep the old flexible way to look at MachineOperands and put the functionality which sets the latency to zero in the getOperandLatency hook instead?

@materi: I think your ideas make sense. If you have a patch, could you post it, please?

What I meant was to have subtargets override the default latency calculation if they want to ignore operands that are not in the MCInstrDesc. That is, implement SytemZ::getOperandLatency() and have it return 0 in the cases where DefIdx or UseIdx is too large.

I don't have a patch for this and I really don't know which targets want the new behavior.

My first idea for this patch was to loop over the operands / read advances of the instruction in order to propagate read advances to the non-tablegen super-reg operands (see earlier patch proposal under 'History'). This is more arduous than the simply clearing those latencies during DAG construction, per what was committed. I think however this should work for you as well, or?

I wonder if it would be enough to make a rule to clear latencies only on *implicit* extra operands, and not on explicit ones? In other words if added *explicit* operands were left alone, this would not break anything? But I am not sure if this is possible with variadic instructions, or if it's a good idea...

I don't like any implementation that has first-class and second-class MachineOperands. At least I think it's a bad idea to have this in the default implementation, doing it in a target hook makes sense though.

LGTM. Looks sensible to me, nitpicks below.

LGTM, thanks for pushing this! Some of the changes here look like things that were just waiting to become an actual problem.

• Use empty implementation from https://reviews.llvm.org/D53909
• Add a test (I wish writing minimal debug info tests was simpler than this...)

• Add a simple unittest
• Go with the adl_begin() == adl_end() implementation for now. We can always switch to more fine grained overloading when we actually deem it necessary for performance. And after all we will probably just replace it with std::empty() anyway once we use C++17 in llvm.

In D53909#1281525, @dblaikie wrote:

(maybe some unit tests?)

Also, what about having only a single implementation:

template <typename Range>
constexpr bool empty(const Range &r) {
  return adl_begin(r) == adl_end(r);
}

Not sure why the standard library doesn't do it this way, but there are probably good reasons... though maybe they don't apply to us/llvm?

I'm now depending on this for a change I'm working on rather than figuring out how to fix kill flag handling

I'm not sure what exactly you mean by that. But just as a warning: This patch will lead to more kill flags being added than before, but it does not guarantee that every last use has a kill flag (especially vregs live across blocks will still lack kill flags).

Updated version

ping

• I am slowly adatpting all the tests to the changes here; I have a commit fixing ~100 of them but there is still maybe 30-40 to go.
• I believe I have the first two asserts fixed locally here.
• The 3rd assert is picking up invalid MIR (a value is used before it is defined), my local version now has a commandline flag that allows us to disable that assert for the couple tests that show invalid MIR (planning to file PRs for the target owners to fix, so we can remove the commandline flag once the last test is fixed).

The code in PEI::replaceFrameIndices also seems sketchy to me as in case of nested callframes it would set InsideCallSequence to false after the inner ADJCALLSTACKUP (though at a first glance I wasn't sure yet why that variable exists at all, and why we would not track sp adjustments outside of callframe setups...)

What about MachineVerifier::verifyStackFrame()? That currently rejects any function with nested callframe setups. You will probably see your testcases fail when running with -verify-machineinstrs.

Please try whether using DoNotOptimize as suggested works. With that addressed LGTM.

Can you explain what you would use per-thread command line options for?
Intuitively I would not expect actual commandline users wanting to set options per thread. If you need it to tweak compiler behavior then it might be better to find ways to encode the information in TargetOptions.h, function attributes or similar, so we have a streamlined way of setting them independently of programmatically modifying commandline options.

Did you make sure this typically finished in 0.5-1s of time?

LGTM

• drop accidental reformatting of existing code from the patch.

noticed that the test needs to operate on i64 to have any effect (as all i32 values are reported as TCC_Free anyway)

In D53174#1262775, @MatzeB wrote:

In D53174#1262762, @craig.topper wrote:

Or is moving them because its a loop and we don't want to reload it every iteration and don't trust LICM?

I'm not completely sure. I see the code operating with block frequencies so it probably sees a lower block frequency in front of the loop.

The pass itself currently runs relatively close to SelectionDAG so there is no LICM happening anymore. Though IMO it really should be implemented in SelectionDAG after everything is expanded and actually all constants are visible and not play all the games with hoisting constants between blocks.

In D53174#1262762, @craig.topper wrote:

Or is moving them because its a loop and we don't want to reload it every iteration and don't trust LICM?

• This is not inspired by some benchmark, but from me needing stable tests in an upcoming change making DAGCombiner slightly less aggressive with OpaqueConstants. It does however seem like the right thing to do in general.

This is currently not motivated by a benchmark but preparation for an upcoming commit of mine where I don't want ConstantHoisting to screw with dev/rem and mess up testcases.

As far as I understand MachineMemoryOperands:

Sorry for slow response. LGTM, some nitpicks below but feel free to fix testcases and nitpicks at your own discretion.

Landed in rL343874

That explains why I couldn't find those line tables in the executables :)

Is it possible that your test harness is removing .dSYMs? .. ah, no, what's happening is that clang declines to add a dsymutil step when it's being used to link .o's into an executable.

In D52862#1255543, @vsk wrote:

In D52862#1255533, @MatzeB wrote:

In D52862#1255529, @vsk wrote:

The core idea and test updates look good to me. I'm curious about the size changes: are you just measuring the size of executables, or of .o's? If it's the former, on Darwin, any size change resulting from this patch might indicate bugs.

I measured executable sizes.

Ah, ok. Well, we know we have more work to do to eliminate codegen differences with/without debug info. We're planning on discussing this at the debug info BoF. (It's not a blocker for this patch.)

The actual instructions are exactly the same, at least in the couple examples I picked.

In D52862#1255529, @vsk wrote:

The core idea and test updates look good to me. I'm curious about the size changes: are you just measuring the size of executables, or of .o's? If it's the former, on Darwin, any size change resulting from this patch might indicate bugs.

Recommitted as rL343895 now, let's hope it passes the tests this time.

Comparing two test-suite builds gives me:

In D52125#1253119, @vsk wrote:

In D52125#1253075, @eugenis wrote:

In case someone wants to look at debug info issue:

1.ii40 KBDownload

test case
bin/clang++ -fsanitize=hwaddress --target=aarch64-linux-android -gline-tables-only -O0 1.ii -c

I can reproduce the issue. I think the unexpected locations come from DwargDebug::beginInstruction:

if (!DL) {
  // We have an unspecified location, which might want to be line 0.

Apparently there's a toggle which can switch off this behavior: -mllvm -use-unknown-locations=Disable.

... and trying again with that option set, the line table bloat is gone.

By default line 0 locations are enabled if the instruction is the first inst in a block, or is after a label. That seems reasonable, but in light of this issue it might be worth revisiting.

+CC dsanders

Feel free to revert for now, but are you sure it is actually this commit?

In D52125#1235612, @vsk wrote:

As Matthias points out, a spill/reload can't unambiguously be associated with a specific instruction.

Note that passing an empty location means that the instruction is described by the previous .loc directive in the stream (if one is present). I think the pedantic thing to do would be to use the special "line 0" location. However, that might bloat the line table and possibly interfere with the way llvm currently identifies prologues.