Changeset 1254


Ignore:
Timestamp:
Aug 1, 2011, 3:09:47 AM (8 years ago)
Author:
shermer
Message:

Work towards revitalising the optimizations:

Added DefUseProperty?, which computes and stores local def-use chains.
Reworked ReuseAvailableExpressions?, mainly to account for non-SSA blocks. RAE is putatively working, but needs refactoring, cleanup, and more testing.
Small adjustments made to other classes to support these changes, and associated refactoring.

Location:
proto/pebble/trunk
Files:
2 added
8 edited

Legend:

Unmodified
Added
Removed
  • proto/pebble/trunk/src/incode/BasicBlock.java

    r1253 r1254  
    106106                return store.size();
    107107        }
     108        public void replaceInstruction(int index, Instruction copy) {
     109                store.remove(index);
     110                store.add(index, copy);
     111        }
    108112        public void removeLast() {
    109113                store.remove(store.size()-1);
    110114        }
     115
     116///////////////////////////////////////////////////////////////////////////
     117// doDeletions                  : removes instructions that are marked for deletion.
     118///////////////////////////////////////////////////////////////////////////
     119        public void doDeletions() {
     120                List<Instruction> result = new ArrayList<Instruction>();
     121               
     122                for(Instruction i: store) {
     123                        if(!i.isToBeDeleted()) {
     124                                result.add(i);
     125                        }
     126                }
     127                store = result;
     128        }
     129       
    111130       
    112131///////////////////////////////////////////////////////////////////////////
  • proto/pebble/trunk/src/incode/Instruction.java

    r1252 r1254  
    22
    33public class Instruction {
     4        public static final int MAX_NUMBER_OPERANDS = 3;
    45        private Op operation;
    56        private String variable;
     
    1819                this.variable  = translateArrayIndices(variable);
    1920               
    20                 operand = new String[3];
     21                operand = new String[MAX_NUMBER_OPERANDS];
    2122                this.operand[0]  = translateArrayIndices(operand1);
    2223                this.operand[1]  = translateArrayIndices(operand2);
     
    103104                operand[i] = string;
    104105        }
    105 
     106        public boolean containsOperand(String symbol) {
     107                for(int i=0; i<numOperands(); i++) {
     108                        if(getOperand(i).equals(symbol))
     109                                return true;
     110                }
     111                return false;
     112        }
    106113
    107114        ///////////////////////////////////////////////////////////////////////////
     
    114121                return operation.isTestType();
    115122        }
     123        public boolean isAssignment() {
     124                return operation.isAssignment();
     125        }       
    116126        public boolean isCommutable() {
    117127                return operation.isCommutable();
     
    254264                }
    255265        }
     266
     267
     268
     269
     270
     271
    256272}
  • proto/pebble/trunk/src/incode/Op.java

    r1252 r1254  
    5959        public boolean isCommutable() {
    6060                return this==AND || this==OR || this==XOR;
     61        }
     62        public boolean isAssignment() {
     63                return this==AND || this==OR || this==XOR || this==NOT ||
     64                           this==COPY || this==SEL || this==ANDNOT || this==SHIFT ||
     65                           this==SCAN || this==SPAN;
    6166        }
    6267        // for Jump types, the name in operand0 is the block to jump to.
  • proto/pebble/trunk/src/incode/localOptimization/BackwardCopyPropagation.java

    r1242 r1254  
    2525         *
    2626         */
    27         private BasicBlock simplify() {
     27        private void simplify() {
    2828//              System.err.print("backwards copy prop: " + block.numInstructions());
    2929                makeDefinitions();
     
    4747                }
    4848
    49                 BasicBlock result = ReuseAvailableExpressions.doDeletions(block);
     49                block.doDeletions();
    5050//              System.err.println(" " + result.numInstructions());
    51 
    52                 return result;
    5351        }
    5452        /**
     
    8179                }
    8280        }
    83         static public BasicBlock apply(BasicBlock block) {
     81        static public void apply(BasicBlock block) {
    8482                BackwardCopyPropagation propagator = new BackwardCopyPropagation(block);
    85                 return propagator.simplify();
     83                propagator.simplify();
    8684        }
    8785}
  • proto/pebble/trunk/src/incode/localOptimization/EliminateDeadCode.java

    r1242 r1254  
    77import java.util.HashSet;
    88import java.util.Set;
    9 
    10 
    11 
    129
    1310
     
    2623         *
    2724         */
    28         private BasicBlock simplify() {
     25        private void simplify() {
    2926//              System.err.print("eliminate dead code: " + block.numInstructions());
    3027
     
    4744                }
    4845               
    49                 BasicBlock result = ReuseAvailableExpressions.doDeletions(block);
     46                block.doDeletions();
    5047//              System.err.println(" " + result.numInstructions());
    51                
    52                 return result;
    5348        }
    5449
     
    6560                used.add(current.getVariable());
    6661        }
    67         static public BasicBlock apply(BasicBlock block) {
     62        static public void apply(BasicBlock block) {
    6863                EliminateDeadCode eliminator = new EliminateDeadCode(block);
    69                 return eliminator.simplify();
     64                eliminator.simplify();
    7065        }
    7166}
  • proto/pebble/trunk/src/incode/localOptimization/ReuseAvailableExpressions.java

    r1242 r1254  
    55import incode.Op;
    66
     7import java.util.ArrayList;
    78import java.util.HashMap;
     9import java.util.List;
    810import java.util.Map;
     11import java.util.Map.Entry;
    912
    1013
     
    2124        }
    2225       
     26        // lightweight instruction wrapper used to change equals() and hashcode().
    2327        static private class InstructionContainer {
    2428                private Instruction instr;
     
    2731                        this.instr = instr;
    2832                }
    29                
    3033                public boolean equals(Object o) {
    3134                        if(o==null)
     
    3841                                return false;
    3942                       
    40                         if(instr.getOperation() == Op.COMMENT)          // never want comments equal.
     43                        if(!instr.isAssignment())               // don't match non-assignments.
    4144                                return false;
    4245                       
     
    5558                        return instr;
    5659                }
     60                public boolean containsOperand(String symbol) {
     61                        return instr.containsOperand(symbol);
     62                }
    5763        }
    5864
     
    6268         *
    6369         */
    64         public BasicBlock simplify() {
     70        public void simplify() {
    6571//              System.err.print("reuse available expressions: " + block.numInstructions());
    6672               
    6773                for(int index=0; index<block.numInstructions(); index++) {
    68                         Instruction blockCurrent = block.instruction(index);
    69                         replaceArguments(blockCurrent);
    70                        
    71                         InstructionContainer current = new InstructionContainer(blockCurrent);
    72                        
    73                         if(!available(current)) {
    74                                 makeAvailable(current, index);
    75                         }
    76                         else {
    77                                 if(current.instruction().isLiveOut()) {
    78                                         //TODO: fix live-out variables
    79                                 }
    80                                 else {
    81                                         current.instruction().markForDeletion();
    82                                         replaceUses(current.instruction().getVariable(), availableName(current));
    83                                 }
    84                         }
    85                 }
    86 
    87                 BasicBlock result = doDeletions(block);
     74                        simplifyOneInstruction(index);
     75                        killWhatNeedsKilling(index);
     76                }
     77
     78                block.doDeletions();
    8879//              System.err.println(" " + result.numInstructions());
    89                
    90                 return result;
    91         }
     80        }
     81
     82        private void killWhatNeedsKilling(int index) {
     83                Instruction instr = block.instruction(index);
     84                if(!instr.isAssignment())
     85                        return;
     86               
     87                String symbol = instr.getVariable();
     88                removeFromReplacementValues(symbol);
     89                removeAvailabilityWithArgument(symbol);
     90        }
     91
     92        private void removeAvailabilityWithArgument(String symbol) {
     93                List<InstructionContainer> removals = new ArrayList<InstructionContainer>();
     94                for(Entry<InstructionContainer, Integer> entry: availability.entrySet()) {
     95                        InstructionContainer instructionContainer = entry.getKey();
     96                        if(instructionContainer.containsOperand(symbol)) {
     97                                removals.add(instructionContainer);     // avoid mutating map underneath entrySet()
     98                        }
     99                }
     100
     101                for(InstructionContainer key: removals) {
     102                        availability.remove(key);
     103                }
     104        }
     105
     106        private void removeFromReplacementValues(String symbol) {
     107                List<String> removals = new ArrayList<String>();
     108                for(Entry<String, String> entry: replacements.entrySet()) {
     109                        if( symbol.equals(entry.getValue())) {
     110                                removals.add(entry.getKey());   // avoid mutating map underneath entrySet()
     111                        }
     112                }
     113                for(String key: removals) {
     114                        replacements.remove(key);
     115                }
     116        }
     117
     118        private void killReplacementForVariable(Instruction currentI) {
     119                if(currentI.isAssignment()) {
     120                        String variable = currentI.getVariable();
     121                        replacements.remove(variable);
     122                }
     123        }
     124
     125        private void simplifyOneInstruction(int index) {
     126                Instruction currentI = block.instruction(index);
     127                replaceArguments(currentI);
     128                killReplacementForVariable(currentI);
     129               
     130                InstructionContainer currentIC = new InstructionContainer(currentI);
     131               
     132                if(!isAvailable(currentIC)) {
     133                        makeAvailable(currentIC, index);
     134                        if(currentI.getOperation()==Op.COPY) {
     135                                replaceUses(currentI.getVariable(), currentI.getOperand(0));
     136                        }
     137                }
     138                else {
     139                        String priorName = availableName(currentIC);
     140                        String currentName = currentI.getVariable();
     141                       
     142                        Instruction copy = Instruction.makeCopy(currentName, priorName);
     143                        block.replaceInstruction(index, copy);
     144                        replaceUses(currentName, priorName);
     145                }
     146        }
     147
    92148
    93149       
     
    135191//              System.err.println("making avaiable: " + " hash " + (container.hashCode() & 0xffff)
    136192//                              + " " + container.instruction() );
    137                 availability.put(container, index);
     193               
     194                Instruction instruction = container.instruction();
     195                if( instruction.isAssignment() &&
     196                        instruction.getOperation() != Op.COPY) {
     197               
     198                        availability.put(container, index);
     199                }
    138200        }
    139201
     
    146208         * @return
    147209         */
    148         private boolean available(InstructionContainer container) {
     210        private boolean isAvailable(InstructionContainer container) {
    149211                if(availability.containsKey(container))
    150212                        return true;
     
    157219        }
    158220       
    159         static public BasicBlock doDeletions(BasicBlock old) {
    160                 BasicBlock result = new BasicBlock();
    161                
    162                 for(Instruction i: old.instructions()) {
    163                         if(!i.isToBeDeleted()) {
    164                                 result.add(i);
    165                         }
    166                 }
    167                 return result;
    168         }
    169        
    170         static public BasicBlock apply(BasicBlock block) {
     221       
     222        static public void apply(BasicBlock block) {
    171223                ReuseAvailableExpressions reuser = new ReuseAvailableExpressions(block);
    172                 return reuser.simplify();
     224                reuser.simplify();
    173225        }
    174226}
  • proto/pebble/trunk/src/incode/localOptimization/UseAndNot.java

    r1242 r1254  
    2626         *
    2727         */
    28         public BasicBlock simplify() {
     28        public void simplify() {
    2929//              int numInstructionsBefore = block.numInstructions();
    3030               
     
    5555               
    5656               
    57                 BasicBlock result = EliminateDeadCode.apply(block);
    58 //              BasicBlock result = block;
    59 //              int numInstructionsAfter = result.numInstructions();
    60 
    61 //              System.err.println("use and-not: " + numInstructionsBefore + " " + numInstructionsAfter);               
    62                 return result;
     57                EliminateDeadCode.apply(block);
    6358        }
    6459
     
    7065        }
    7166
    72         static public BasicBlock apply(BasicBlock block) {
     67        static public void apply(BasicBlock block) {
    7368                UseAndNot user = new UseAndNot(block);
    74                 return user.simplify();
     69                user.simplify();
    7570        }
    7671}
  • proto/pebble/trunk/src/main/Main.java

    r1253 r1254  
    44import incode.Pythonater;
    55import incode.global.MergeBlocks;
     6import incode.localOptimization.ReuseAvailableExpressions;
    67
    78import java.io.IOException;
     
    5556            MergeBlocks.apply(Fragment.make(headBlock), false);
    5657
     58//            DefUseProperty du = new DefUseProperty(headBlock);
     59//            du.make();
     60//            du.printDiagnostic();
     61           
     62            ReuseAvailableExpressions.apply(headBlock);
     63           
    5764            Pythonater.apply(symbolTable, headCollector, headBlock);
    5865           
Note: See TracChangeset for help on using the changeset viewer.