Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

propagateMoves is much slower than expected #100

Open
nomaddo opened this issue May 31, 2018 · 0 comments
Open

propagateMoves is much slower than expected #100

nomaddo opened this issue May 31, 2018 · 0 comments
Labels
enhancement optimization related to an optimization step

Comments

@nomaddo
Copy link
Collaborator

nomaddo commented May 31, 2018 

$ build/test/TestVC4C --fast-regressions
....
[W] Thu May 31 19:34:22 2018: 
[W] Thu May 31 19:34:22 2018: Profiling results for 57 functions:
[W] Thu May 31 19:34:22 2018:                                Optimizer  95702 ms    95702501 us       159 calls      601902 us/call                       /home/nomaddo/idein/VC4C/src/Compiler.cpp#147
[W] Thu May 31 19:34:22 2018:                              createGraph  85733 ms    85733231 us       431 calls      198917 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#773
[W] Thu May 31 19:34:22 2018:                               colorGraph  83953 ms    83953922 us       388 calls      216376 us/call              /home/nomaddo/idein/VC4C/src/asm/CodeGenerator.cpp#79
[W] Thu May 31 19:34:22 2018:                           PropagateMoves  75268 ms    75268340 us       805 calls       93501 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                                 addEdges  49637 ms    49637054 us       431 calls      115167 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#679
[W] Thu May 31 19:34:22 2018:                         MergeBasicBlocks  33401 ms    33401054 us       389 calls       85863 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                               Precompile  29807 ms    29807678 us       161 calls      185140 us/call     /home/nomaddo/idein/VC4C/src/precompilation/Precompiler.cpp#45
[W] Thu May 31 19:34:22 2018:                        createUsageRanges  20647 ms    20647497 us       431 calls       47906 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#655
[W] Thu May 31 19:34:22 2018:                           walkUsageRange  19794 ms    19794931 us    333040 calls          59 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#666
[W] Thu May 31 19:34:22 2018:                                createCFG  19517 ms    19517876 us       778 calls       25087 us/call      /home/nomaddo/idein/VC4C/src/analysis/ControlFlowGraph.cpp#247
[W] Thu May 31 19:34:22 2018:                              SingleSteps  15162 ms    15162521 us       805 calls       18835 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                               Normalizer  10008 ms    10008454 us       159 calls       62946 us/call                       /home/nomaddo/idein/VC4C/src/Compiler.cpp#143
[W] Thu May 31 19:34:22 2018:                     initializeLocalsUses   7180 ms     7180857 us       389 calls       18459 us/call              /home/nomaddo/idein/VC4C/src/asm/CodeGenerator.cpp#76
[W] Thu May 31 19:34:22 2018:                                   Inline   6763 ms     6763773 us       390 calls       17343 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#124
[W] Thu May 31 19:34:22 2018:                           EliminateMoves   6064 ms     6064691 us       805 calls        7533 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                      NormalizationPasses   5680 ms     5680478 us       389 calls       14602 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#159
[W] Thu May 31 19:34:22 2018:                                   Parser   4693 ms     4693706 us       160 calls       29335 us/call                       /home/nomaddo/idein/VC4C/src/Compiler.cpp#135
[W] Thu May 31 19:34:22 2018:                      ReorderInstructions   4626 ms     4626148 us       389 calls       11892 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                              replaceNOPs   4557 ms     4557092 us      9557 calls         476 us/call        /home/nomaddo/idein/VC4C/src/optimization/Reordering.cpp#365
[W] Thu May 31 19:34:22 2018:                 findReplacementCandidate   4284 ms     4284597 us     24437 calls         175 us/call        /home/nomaddo/idein/VC4C/src/optimization/Reordering.cpp#144
[W] Thu May 31 19:34:22 2018:              findInstructionNotAccessing   3895 ms     3895851 us     23659 calls         164 us/call        /home/nomaddo/idein/VC4C/src/optimization/Reordering.cpp#182
[W] Thu May 31 19:34:22 2018:                      SimplifyArithmetics   3867 ms     3867917 us    517797 calls           7 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#71
[W] Thu May 31 19:34:22 2018:                                fixLocals   3747 ms     3747665 us    259118 calls          14 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#454
[W] Thu May 31 19:34:22 2018:                         AdjustmentPasses   3101 ms     3101605 us       389 calls        7973 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#217
[W] Thu May 31 19:34:22 2018:                   EliminateBitOperations   3073 ms     3073571 us       805 calls        3818 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                            FoldConstants   2856 ms     2856815 us    517797 calls           5 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#71
[W] Thu May 31 19:34:22 2018:                 CombineSelectionWithZero   2806 ms     2806321 us    517797 calls           5 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#71
[W] Thu May 31 19:34:22 2018:                  CombineSettingSameFlags   2350 ms     2350210 us    517797 calls           4 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#71
[W] Thu May 31 19:34:22 2018:                         HandleImmediates   2280 ms     2280504 us       778 calls        2931 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#223
[W] Thu May 31 19:34:22 2018:                       createColoredNodes   2234 ms     2234208 us       431 calls        5183 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#609
[W] Thu May 31 19:34:22 2018:                         processClosedSet   2020 ms     2020040 us     63871 calls          31 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#718
[W] Thu May 31 19:34:22 2018:                               Intrinsics   2001 ms     2001402 us       389 calls        5144 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#176
[W] Thu May 31 19:34:22 2018:                   HandleUseWithImmediate   1800 ms     1800214 us       389 calls        4627 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#223
[W] Thu May 31 19:34:22 2018:                         SecondNormalizer   1770 ms     1770819 us       159 calls       11137 us/call                       /home/nomaddo/idein/VC4C/src/Compiler.cpp#151
[W] Thu May 31 19:34:22 2018:                        updateFixedLocals   1748 ms     1748345 us    291929 calls           5 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#424
[W] Thu May 31 19:34:22 2018:                  CombineALUIinstructions   1690 ms     1690090 us       389 calls        4344 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                      checkExcludedValues   1537 ms     1537532 us    411203 calls           3 us/call        /home/nomaddo/idein/VC4C/src/optimization/Reordering.cpp#52
[W] Thu May 31 19:34:22 2018:                          MapMemoryAccess   1474 ms     1474854 us       390 calls        3781 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#165
[W] Thu May 31 19:34:22 2018:                      CombineLiteralLoads   1320 ms     1320153 us       389 calls        3393 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                     SplitReadAfterWrites    673 ms      673700 us       389 calls        1731 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                         SimplifyBranches    475 ms      475506 us       389 calls        1222 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                  ResolveStackAllocations    287 ms      287135 us       390 calls         736 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#176
[W] Thu May 31 19:34:22 2018:                        mapImmediateValue    282 ms      282055 us    110727 calls           2 us/call    /home/nomaddo/idein/VC4C/src/normalization/LiteralValues.cpp#592
[W] Thu May 31 19:34:22 2018:                           ExtendBranches    250 ms      250860 us       389 calls         644 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#232
[W] Thu May 31 19:34:22 2018:                               resetGraph    237 ms      237446 us        42 calls        5653 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#771
[W] Thu May 31 19:34:22 2018:                            toRegisterMap    236 ms      236086 us       385 calls         613 us/call              /home/nomaddo/idein/VC4C/src/asm/CodeGenerator.cpp#101
[W] Thu May 31 19:34:22 2018:                       toRegisterMapGraph    233 ms      233410 us       385 calls         606 us/call              /home/nomaddo/idein/VC4C/src/asm/CodeGenerator.cpp#102
[W] Thu May 31 19:34:22 2018:                        fixRegisterErrors    188 ms      188657 us        45 calls        4192 us/call              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#1159
[W] Thu May 31 19:34:22 2018:                      HandleLiteralVector    178 ms      178247 us       389 calls         458 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#176
[W] Thu May 31 19:34:22 2018:                   MapGlobalDataToAddress    140 ms      140491 us       389 calls         361 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#176
[W] Thu May 31 19:34:22 2018:                         CombineRotations    101 ms      101102 us       805 calls         125 us/call         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#128
[W] Thu May 31 19:34:22 2018:                MoveRotationSourcesToAccs     95 ms       95982 us       389 calls         246 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#223
[W] Thu May 31 19:34:22 2018:                         EliminateReturns     86 ms       86848 us       389 calls         223 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#176
[W] Thu May 31 19:34:22 2018:                          CheckNormalized     78 ms       78510 us       389 calls         201 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#176
[W] Thu May 31 19:34:22 2018:                      AddStartStopSegment     78 ms       78001 us       389 calls         200 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#184
[W] Thu May 31 19:34:22 2018:                  findPreviousInstruction     71 ms       71952 us     23093 calls           3 us/call        /home/nomaddo/idein/VC4C/src/optimization/Reordering.cpp#22
[W] Thu May 31 19:34:22 2018:                         UnrollWorkGroups     18 ms       18401 us       389 calls          47 us/call       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#194
[W] Thu May 31 19:34:22 2018: 
[W] Thu May 31 19:34:22 2018: Profiling results for 43 counters:
[W] Thu May 31 19:34:22 2018:                    Clean locals (before) 263167 counts  389 calls   676 avg./call             +0 (   +0%)                         /home/nomaddo/idein/VC4C/src/Method.cpp#270
[W] Thu May 31 19:34:22 2018:                     Clean locals (after) 174775 counts  389 calls   449 avg./call    diff -88392 (  -33%)                         /home/nomaddo/idein/VC4C/src/Method.cpp#304
[W] Thu May 31 19:34:22 2018:            Scratch memory size (in rows)    487 counts  390 calls     1 avg./call             +0 (   +0%)     /home/nomaddo/idein/VC4C/src/normalization/MemoryAccess.cpp#485
[W] Thu May 31 19:34:22 2018:                           VPM cache size   6336 counts   16 calls   396 avg./call             +0 (   +0%)                  /home/nomaddo/idein/VC4C/src/periphery/VPM.cpp#807
[W] Thu May 31 19:34:22 2018:             Eliminate Phi-nodes (before)  49053 counts 1099 calls    44 avg./call             +0 (   +0%)       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#113
[W] Thu May 31 19:34:22 2018:              Eliminate Phi-nodes (after)  51287 counts 1099 calls    46 avg./call    diff  +2234 (   +4%)       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#116
[W] Thu May 31 19:34:22 2018:                          Inline (before)  34271 counts  390 calls    87 avg./call             +0 (   +0%)       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#123
[W] Thu May 31 19:34:22 2018:                           Inline (after) 117012 counts  390 calls   300 avg./call    diff +82741 ( +241%)       /home/nomaddo/idein/VC4C/src/normalization/Normalizer.cpp#128
[W] Thu May 31 19:34:22 2018:                SimplifyBranches (before) 264194 counts  389 calls   679 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:                 SimplifyBranches (after) 261715 counts  389 calls   672 avg./call    diff  -2479 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:                MergeBasicBlocks (before) 261715 counts  389 calls   672 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:                 MergeBasicBlocks (after) 249892 counts  389 calls   642 avg./call    diff -11823 (   -4%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:                     SingleSteps (before) 517754 counts  805 calls   643 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:                      SingleSteps (after) 517295 counts  805 calls   642 avg./call    diff   -459 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:                CombineRotations (before) 517295 counts  805 calls   642 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:                 CombineRotations (after) 517230 counts  805 calls   642 avg./call    diff    -65 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:                  EliminateMoves (before) 517230 counts  805 calls   642 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:                   EliminateMoves (after) 511105 counts  805 calls   634 avg./call    diff  -6125 (   -1%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:          EliminateBitOperations (before) 511105 counts  805 calls   634 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:           EliminateBitOperations (after) 511105 counts  805 calls   634 avg./call    diff     +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:                  PropagateMoves (before) 511105 counts  805 calls   634 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:                   PropagateMoves (after) 511105 counts  805 calls   634 avg./call    diff     +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:            SplitReadAfterWrites (before) 243243 counts  389 calls   625 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:             SplitReadAfterWrites (after) 265607 counts  389 calls   682 avg./call    diff +22364 (   +9%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:             CombineLiteralLoads (before) 265607 counts  389 calls   682 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:              CombineLiteralLoads (after) 258955 counts  389 calls   665 avg./call    diff  -6652 (   -2%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:             ReorderInstructions (before) 258955 counts  389 calls   665 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:              ReorderInstructions (after) 236406 counts  389 calls   607 avg./call    diff -22549 (   -8%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:         CombineALUIinstructions (before) 236406 counts  389 calls   607 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#127
[W] Thu May 31 19:34:22 2018:          CombineALUIinstructions (after) 203595 counts  389 calls   523 avg./call    diff -32811 (  -13%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#132
[W] Thu May 31 19:34:22 2018:                   OptimizationIterations    805 counts  389 calls     2 avg./call             +0 (   +0%)         /home/nomaddo/idein/VC4C/src/optimization/Optimizer.cpp#200
[W] Thu May 31 19:34:22 2018:                  CodeGeneration (before) 282559 counts  389 calls   726 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/CodeGenerator.cpp#66
[W] Thu May 31 19:34:22 2018:                          SpillCandidates      4 counts208167 calls     0 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#676
[W] Thu May 31 19:34:22 2018:                    Register error case 1      1 counts    1 calls     1 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#1003
[W] Thu May 31 19:34:22 2018:                           NOP insertions      1 counts    1 calls     1 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#1029
[W] Thu May 31 19:34:22 2018:                    Register error case 2     75 counts   75 calls     1 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#1055
[W] Thu May 31 19:34:22 2018:                                A blocked      0 counts   75 calls     0 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#1062
[W] Thu May 31 19:34:22 2018:                                B blocked      1 counts   75 calls     0 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#1063
[W] Thu May 31 19:34:22 2018:                    Register error case 3      1 counts    1 calls     1 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#1110
[W] Thu May 31 19:34:22 2018:                                move to A      0 counts    1 calls     0 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#1115
[W] Thu May 31 19:34:22 2018:                                move to B      0 counts    1 calls     0 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#1116
[W] Thu May 31 19:34:22 2018:                   reassignNodeToRegister      0 counts   88 calls     0 avg./call             +0 (   +0%)              /home/nomaddo/idein/VC4C/src/asm/GraphColoring.cpp#874
[W] Thu May 31 19:34:22 2018:                   CodeGeneration (after) 267832 counts  385 calls   695 avg./call    diff -14727 (   -5%)              /home/nomaddo/idein/VC4C/src/asm/CodeGenerator.cpp#168
Suite 'RegressionTest' finished, 157/162 successful (96.91%) in 207844813 microseconds (207845 ms).
@nomaddo nomaddo added enhancement optimization related to an optimization step labels May 31, 2018
doe300 added a commit that referenced this issue Jul 1, 2018
@doe300
Several fixes and improvements
0010998 
* Fixes an error allocating registers for work-group info
* Optimizes multiplication of known unsigned values
* Adds exit-criteria to propagateMoves, improving speed, see #100
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement optimization related to an optimization step
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@nomaddo