Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1310833003:
Refactor LinearScan::scan from one huge function into smaller functions. (Closed)
|
Created:
5 years, 4 months ago by ascull Modified:
5 years, 4 months ago CC:
native-client-reviews_googlegroups.com Base URL:
https://chromium.googlesource.com/native_client/pnacl-subzero.git@master Target Ref:
refs/heads/master Visibility:
Public. |
DescriptionRefactor LinearScan::scan from one huge function into smaller functions.
BUG=
R=jvoung@chromium.org, stichnot@chromium.org
Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=d24cfda1f63f04f22118addb793b197fd3141b15
Patch Set 1 #Patch Set 2 : Fix randomization guards. #
Total comments: 35
Patch Set 3 : #
Total comments: 7
Patch Set 4 : Final edits and rebase #Messages
Total messages: 10 (1 generated)
ascull@google.com changed reviewers: + jvoung@chromium.org, stichnot@chromium.org
All the tests still pass, is that good enough to say this hasn't broken something?
On 2015/08/21 23:45:36, ascull wrote:
> All the tests still pass, is that good enough to say this hasn't broken
> something?
The way I check a pure refactoring change like this is to check the spec2k
output for total equality.
mkdir /tmp/spec.{old,new}
# build current master
szbuild_spec2k.py -O2 --filetype=asm -v --force --sz=--threads=0
cd .../tests/spec2k
cp ???.*/*.sz.s /tmp/spec.old/
# build new CL branch
szbuild_spec2k.py -O2 --filetype=asm -v --force --sz=--threads=0
cd .../tests/spec2k
cp ???.*/*.sz.s /tmp/spec.new/
diff -r /tmp/spec.{old,new}
If you really want to be thorough, you can add --sz=--verbose=most to the
szbuild commands, redirect stdout to two different files, and "diff -q" them for
equality.
I tried all this and I'm happy to say all output is the same. :)
https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp File src/IceRegAlloc.cpp (right): https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:11: /// This file implements the LinearScan class, which performs the linear-scan While you're at it, could you reformat all the other comment blocks in this file to use the full 80 columns? (Looks like that's already done for the .h file.) https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:338: void LinearScan::handleActiveRangeExpiredOrInactive(Variable *Cur) { const Variable *Cur https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:346: if (Verbose) { Could you change every instance of "if (Verbose)" to "if (isVerbose())"? Then create an isVerbose method in the .h file: bool isVerbose() const { return BuildDefs::dump() && Verbose; } The idea being that all the stream code should disappear from the MINIMAL build. Going a bit further, it looks like almost every instance of "if (Verbose)" guards the same 4 lines of code except for the string constant, so there's another opportunity to refactor. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:375: void LinearScan::handleInctiveRangeExpiredOrReactived(Variable *Cur) { const Variable *Cur https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:416: void LinearScan::findRegisterPreference(Variable *Cur, const Variable *Cur https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:466: void LinearScan::filterFreeWithInactiveRanges(Variable *Cur) { const Variable *Cur https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:491: void LinearScan::filterFreeWithPrecoloredRanges(Variable *Cur) { const Variable *Cur https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:786: Weights.resize(RegMask.size()); It seems to me that Weights and PrecoloredUnhandledMask could be resized once outside the loop. Maybe to NumRegisters? https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:825: // Second choice: any free register. TODO: After explicit affinity is I think this TODO should be removed. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h File src/IceRegAlloc.h (right): https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:58: void addSpillFill(Variable *Cur, llvm::SmallBitVector RegMask); I think all these SmallBitVectors should be passed by ref, and by const ref where possible. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:62: void handleInctiveRangeExpiredOrReactived(Variable *Cur); Reactivated https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:67: void allocatePreferedRegister(Variable *Cur); Preferred https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:77: static constexpr size_t REGS_SIZE = 32; Make this public, so that the Machine could potentially static_assert against this. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:95: /// AllowOverlap inference below. Probably just remove the word "below". https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:96: llvm::SmallVector<int, REGS_SIZE> RegUses; Can you change int to int32_t ? https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:98: /// \name Iteration state I wonder if you could move the iteration-specific stuff into a separate class. This class would be defined only within IceRegAlloc.cpp so it would be otherwise completely hidden. You could hold a pointer to that object within this class. The object could be created at the beginning of scan() and delete before scan() returns. As such, it would be better to make it a unique_ptr, but I think you need to complete class definition available, not just forward-declared. The rationale is that the rest of the fields of this class have some meaning and consistency between calls to the public methods, whereas these fields have meaning only within scan(), and are essentially undefined otherwise.
https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp File src/IceRegAlloc.cpp (right): https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:666: // Finish up by assigning RegNumTmp->RegNum (or a random permutation thereof) nit: I think this was from the original comment, but maybe make "RegNumTmp->RegNum" look less like a class member field load? (more space ?) https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h File src/IceRegAlloc.h (right): https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:62: void handleInctiveRangeExpiredOrReactived(Variable *Cur); Inctive -> Inactive https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:81: const bool Verbose; nit: Cluster some of the bools together for better use of alignment-padding? I suppose the "AllowOverlap" can stay with the Iteration state block since it's logically related.
https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp File src/IceRegAlloc.cpp (right): https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:11: /// This file implements the LinearScan class, which performs the linear-scan On 2015/08/24 15:08:30, stichnot wrote: > While you're at it, could you reformat all the other comment blocks in this file > to use the full 80 columns? (Looks like that's already done for the .h file.) Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:338: void LinearScan::handleActiveRangeExpiredOrInactive(Variable *Cur) { On 2015/08/24 15:08:30, stichnot wrote: > const Variable *Cur Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:346: if (Verbose) { On 2015/08/24 15:08:31, stichnot wrote: > Could you change every instance of "if (Verbose)" to "if (isVerbose())"? Then > create an isVerbose method in the .h file: > > bool isVerbose() const { > return BuildDefs::dump() && Verbose; > } > > The idea being that all the stream code should disappear from the MINIMAL build. > > Going a bit further, it looks like almost every instance of "if (Verbose)" > guards the same 4 lines of code except for the string constant, so there's > another opportunity to refactor. The initializer for Verbose includes `BuildDefs::dump()` already and given this is a compile time constant there doesn't seem to be a need for a function call. I have refactored the 4 lines into `dumpLiveRangeTrace`. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:375: void LinearScan::handleInctiveRangeExpiredOrReactived(Variable *Cur) { On 2015/08/24 15:08:31, stichnot wrote: > const Variable *Cur Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:666: // Finish up by assigning RegNumTmp->RegNum (or a random permutation thereof) On 2015/08/24 15:33:01, jvoung wrote: > nit: I think this was from the original comment, but maybe make > "RegNumTmp->RegNum" look less like a class member field load? (more space ?) Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:786: Weights.resize(RegMask.size()); On 2015/08/24 15:08:30, stichnot wrote: > It seems to me that Weights and PrecoloredUnhandledMask could be resized once > outside the loop. Maybe to NumRegisters? The resize must be in the loops .size() is used by a for loop. I have put a reserve outside of the loop so memory allocation will not happen inside the loop. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:825: // Second choice: any free register. TODO: After explicit affinity is On 2015/08/24 15:08:30, stichnot wrote: > I think this TODO should be removed. Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h File src/IceRegAlloc.h (right): https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:58: void addSpillFill(Variable *Cur, llvm::SmallBitVector RegMask); On 2015/08/24 15:08:31, stichnot wrote: > I think all these SmallBitVectors should be passed by ref, and by const ref > where possible. This gets taken care of by passing IterationState by reference. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:62: void handleInctiveRangeExpiredOrReactived(Variable *Cur); On 2015/08/24 15:33:01, jvoung wrote: > Inctive -> Inactive Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:62: void handleInctiveRangeExpiredOrReactived(Variable *Cur); On 2015/08/24 15:08:31, stichnot wrote: > Reactivated Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:67: void allocatePreferedRegister(Variable *Cur); On 2015/08/24 15:08:31, stichnot wrote: > Preferred Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:77: static constexpr size_t REGS_SIZE = 32; On 2015/08/24 15:08:31, stichnot wrote: > Make this public, so that the Machine could potentially static_assert against > this. Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:81: const bool Verbose; On 2015/08/24 15:33:01, jvoung wrote: > nit: Cluster some of the bools together for better use of alignment-padding? I > suppose the "AllowOverlap" can stay with the Iteration state block since it's > logically related. Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:95: /// AllowOverlap inference below. On 2015/08/24 15:08:31, stichnot wrote: > Probably just remove the word "below". Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:96: llvm::SmallVector<int, REGS_SIZE> RegUses; On 2015/08/24 15:08:31, stichnot wrote: > Can you change int to int32_t ? Done. https://codereview.chromium.org/1310833003/diff/20001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:98: /// \name Iteration state On 2015/08/24 15:08:31, stichnot wrote: > I wonder if you could move the iteration-specific stuff into a separate class. > This class would be defined only within IceRegAlloc.cpp so it would be otherwise > completely hidden. You could hold a pointer to that object within this class. > The object could be created at the beginning of scan() and delete before scan() > returns. As such, it would be better to make it a unique_ptr, but I think you > need to complete class definition available, not just forward-declared. > > The rationale is that the rest of the fields of this class have some meaning and > consistency between calls to the public methods, whereas these fields have > meaning only within scan(), and are essentially undefined otherwise. No need to go to the heap or pollute the class. Putting this on the stack in scan() does the trick. This brings it back to the original C-style implementation I proposed.
otherwise lgtm. Thanks! https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.cpp File src/IceRegAlloc.cpp (right): https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:403: // TODO(stichnot): te through the actual Variables of the instruction, s/te/Iterate/ https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:682: // Resize once not per iteration maybe "Resize once outside the loop" or something https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.cpp#new... src/IceRegAlloc.cpp:806: if (Verbose) { Similar to most all of Subzero's dump routines, I would put this at the beginning: if (!BuildDefs::dump()) return; Since BuildDefs::dump() is a constexpr function, a MINIMAL build is all but guaranteed to dead-code eliminate the entire function body. Furthermore, the compiler will probably inline all calls to this now-trivial function, essentially removing those call instructions. The result is faster code and smaller code. With only the "if (Verbose)" guard, I'm concerned that it may not be as easy for the compiler to reason that const bool Verbose is always false and to get the same improvement. Maybe it is that clever, but what about g++ or some other compiler? https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.h File src/IceRegAlloc.h (right): https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:45: struct IterationState { I think it would be safer to call this a class instead of a struct and explicitly initialize its fields: class IterationState { // delete default copy ctor / assignment operator public: IterationState() = default; Variable *Cur = nullptr; Variable *Prefer = nullptr; int32_t PreferReg = Variable::NoRegister; bool AllowOverlap = false; ... }; https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:47: llvm::SmallBitVector RegMask; Maybe move the llvm:: fields to the end.
lgtm too https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.h File src/IceRegAlloc.h (right): https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:85: void assignFinalRegisters(llvm::SmallBitVector RegMaskFull, re: passing llvm::SmallBitVector arguments which Jim brought up earlier -- these are also passed by value. It looks like it's only one field (either used as a pointer, or the bits themselves for the small variant of the vector), but how complicated the pass-by-value is depends on whether the class is "non-trivial" or not. If POD, it would be pretty nice and simple and cheaper than pass by ref, but if not, then...
https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.h File src/IceRegAlloc.h (right): https://codereview.chromium.org/1310833003/diff/40001/src/IceRegAlloc.h#newco... src/IceRegAlloc.h:85: void assignFinalRegisters(llvm::SmallBitVector RegMaskFull, On 2015/08/25 12:50:48, jvoung wrote: > re: passing llvm::SmallBitVector arguments which Jim brought up earlier -- these > are also passed by value. > > It looks like it's only one field (either used as a pointer, or the bits > themselves for the small variant of the vector), but how complicated the > pass-by-value is depends on whether the class is "non-trivial" or not. If POD, > it would be pretty nice and simple and cheaper than pass by ref, but if not, > then... Oh yeah, I missed this. Please pass these by ref, ideally const ref.
Message was sent while issue was closed.
Committed patchset #4 (id:60001) manually as d24cfda1f63f04f22118addb793b197fd3141b15 (presubmit successful). |
