Changeset 1256 for proto


Ignore:
Timestamp:
Aug 2, 2011, 1:10:28 AM (8 years ago)
Author:
shermer
Message:

Work towards optimization.

Added LocalDeadCodeEliminator? (LDCE), separate from the old EliminateDeadCode?. Worked on clarifying code in DefUseProperty?. LDCE does not improve almost-SSA code much, so I've left it out of the standard transformation pipeline in main.Main.

Added a global liveness analysis class, LivenessProperty?. This is prep for a global dead code eliminator.

Added possibleUseEIndices() and defEIndices() to Op, and similar things to instruction; this localizes decisions about which instruction operands mean what. Finding all the places in the code base that make these decisions, and changing them to use this mechanism, may take a while.

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

Legend:

Unmodified
Added
Removed
  • proto/pebble/trunk/inputs/input-11.pbl

    r1254 r1256  
    1010        m = b & c
    1111#       d = >>>j
    12 #       g = b +> d
     12        g = b +> d
    1313        f = d ^ a
    1414        d = m <> b
     
    1616        if v & d | x not allone then {
    1717                x = 0
     18                g = a +> d
     19                h = x1
    1820        }
    1921        else {
    2022                m = 1
     23                f = r <> m
     24                g = x2
    2125        }
    2226
     27        g = b +> d
     28        f = d ^ a
     29        m = x3
    2330
    2431}
  • proto/pebble/trunk/src/incode/BasicBlock.java

    r1254 r1256  
    66
    77import java.util.ArrayList;
     8import java.util.Collections;
    89import java.util.HashMap;
    910import java.util.List;
     
    102103        public List<Instruction> instructions() {
    103104                return new ArrayList<Instruction>(store);
     105        }
     106        public List<Instruction> reverseInstructions() {
     107                List<Instruction> list = instructions();
     108                Collections.reverse(list);
     109                return list;
    104110        }
    105111        public int numInstructions() {
  • proto/pebble/trunk/src/incode/Instruction.java

    r1254 r1256  
    11package incode;
     2
     3import java.util.ArrayList;
     4import java.util.List;
    25
    36public class Instruction {
     
    129132        public int numOperands() {
    130133                return operation.numberOfOperands();
     134        }
     135        public List<Integer> variableUseEIndices() {
     136                List<Integer> result = new ArrayList<Integer>(4);
     137                int[] indices = operation.possibleUseEIndices();
     138                for(int index: indices) {
     139                        if(denotesAVariable(extendedOperand(index))) {
     140                                result.add(index);
     141                        }
     142                }
     143                return result;
     144        }
     145       
     146        // String is not T, F, starting with [-0..9], or "smallConstant("
     147        private boolean denotesAVariable(String s) {
     148                if(s==null || s.length()==0)
     149                        return false;
     150               
     151                char firstChar = s.charAt(0);
     152                if(s.length()==1 && (firstChar== 'T' || firstChar=='F')) {
     153                        return false;
     154                }
     155               
     156                if(firstChar=='-' || Character.isDigit(firstChar))
     157                        return false;
     158               
     159                if(s.startsWith("smallConstant"))
     160                        return false;
     161                return true;
    131162        }
    132163       
     
    179210       
    180211       
     212        public String extendedOperand(int eOpNumber) {
     213                if(eOpNumber==0) {
     214                        return getVariable();
     215                }
     216                return  getOperand(eOpNumber-1);
     217        }
    181218        ///////////////////////////////////////////////////////////////////////////
    182219        // static factories for each op-type
  • proto/pebble/trunk/src/incode/Op.java

    r1254 r1256  
    33 */
    44package incode;
     5
    56
    67public enum Op {
     
    7374                return this==TEST || this==WHILE;
    7475        }
     76
     77        ///////////////////////////////////////////////////////////////////////////////
     78        // possibleUseEIndices: return an array of which extendedIndices possibly
     79        //                              denote variable uses.  Whether these operands actually are uses
     80        //                              of variables depends on whether the string for that operand
     81        //                              denotes a variable; the other possibility are that it denotes
     82        //                              a constant (T, F, or an integer/smallConstant).
     83        //
     84        // defEIndices: returns an array of which extendedIndices are (definitely)
     85        //                              variable definitions.
     86        //
     87        ///////////////////////////////////////////////////////////////////////////////
    7588       
    76         //Note: I chose to implement the following as a switch rather than as a constructor arg
    77         // so that the constructor calls do not get too large and uneven.  The default case
    78         // should perhaps be more forceful, such as an error message or assertion.
    79         // By examining format(), one should be able to see which operands do what in any
    80         // particular instruction.
    81        
     89        static final int[] empty = {};
     90        static final int[] one = {1};
     91        static final int[] two = {1, 2};
     92        static final int[] three = {1, 2, 3};
     93        static final int[] variable = {0};
     94
     95        public final int[] possibleUseEIndices() {
     96                if(this==COMMENT)                       return empty;
     97                if(this==ERROR)                         return variable;
     98                if(isTestType())                        return variable;
     99                if(isJumpType())                        return empty;
     100               
     101                if(numberOfOperands==0)         return empty;
     102                if(numberOfOperands==1)         return one;
     103                if(numberOfOperands==2)         return two;
     104                if(numberOfOperands==3)         return three;
     105                return empty;
     106        }
     107        public final int[] defEIndices() {
     108                if(isAssignment())                      return variable;
     109                return empty;
     110        }
     111        ///////////////////////////////////////////////////////////////////////////////
     112        // Note: I chose to implement the following routines as switches rather than as a
     113        // constructor args so that the constructor calls do not get too large and uneven.
     114        // The default case should perhaps be more forceful, such as an error message or
     115        // assertion.  By examining format(), one should be able to see which operands do
     116        // what in any particular instruction.
     117        //
    82118        //
    83119        // Format strings for use in a call with arguments as follows:
    84120        //                                                        1$        2$          3$          4$          5$
    85121        // String.format(Op.format(), variable, operand[0], operand[1], operand[2], comparisonString());
     122        //
     123        ///////////////////////////////////////////////////////////////////////////////
    86124        public String format() {
    87125                switch(this) {
  • proto/pebble/trunk/src/incode/localOptimization/DefUseProperty.java

    r1254 r1256  
    1313
    1414public class DefUseProperty implements Property {
    15         private static final int BEGINNING_OF_BLOCK = -1;
    16         private static final int END_OF_BLOCK = -3;
     15        public static final int BEGINNING_OF_BLOCK = -1;
     16        public static final int END_OF_BLOCK = -3;
     17        @SuppressWarnings("unused")
     18        private static final int IS_DEAD = -4;
     19       
    1720        public static final String PROPERTY_NAME = "defs and uses";
    1821        private BasicBlock block;
     
    6063                this.block = block;
    6164                makeDefsAndUsesStorage();
     65                make();
     66        }
     67        public DefUseProperty attach() {
     68                this.block.addProperty(this);
     69                return this;
    6270        }
    6371        private void makeDefsAndUsesStorage() {
     
    7280       
    7381        //
    74         // a def index of -1 means "defined before this block"
    7582        // the def index for the variable of an instruction is its
    7683        // previous definition.
     
    9198                       
    9299                        for(int eOpNumber=0; eOpNumber<nOperands+1; eOpNumber++) {
    93                                 String operand = eOpNumber==0 ? instr.getVariable()
    94                                                                       : instr.getOperand(eOpNumber-1);
    95                                 Integer defIndex = lastDef.get(operand);
    96                                 int def = defIndex==null ? BEGINNING_OF_BLOCK : defIndex;
    97                                 indices.setDef(eOpNumber, def);
     100                                String operand = instr.extendedOperand(eOpNumber);
     101                                int definingInstrIndex = getWithDefault(lastDef, operand, BEGINNING_OF_BLOCK);
     102                                indices.setDef(eOpNumber, definingInstrIndex);
    98103                                indices.setNextUse(eOpNumber, END_OF_BLOCK);
    99104                               
     
    101106                                if(eOpNumber>0) {       // uses only
    102107                                        if(lastUse.get(operand)==null) {
    103                                                 if(def!=BEGINNING_OF_BLOCK) {
    104                                                         setNextUse(def, 0, index);
     108                                                if(definingInstrIndex!=BEGINNING_OF_BLOCK) {
     109                                                        setNextUse(definingInstrIndex, 0, index);
    105110                                                }
    106111                                        }
    107112                                        else {
     113                                                // in instruction lastUseIndex, "operand" may be used more
     114                                                // than once.  This sets the first of those uses' nextUse value.
    108115                                                int lastUseIndex = lastUse.get(operand);
    109                                                 setNextUse(lastUseIndex, operand, index);
     116                                                setNextUse(lastUseIndex, operand, index);       
    110117                                        }
    111118                                        lastUse.put(operand, index);
     
    117124                }
    118125        }
     126        private int getWithDefault(Map<String, Integer> map, String operand, int defaultValue) {
     127                Integer defIndex = map.get(operand);
     128                return defIndex==null ? defaultValue : defIndex;
     129        }
     130       
    119131        public void printDiagnostic() {
    120132                PStringBuilder builder = new PStringBuilder(0);
     
    147159                return indices.getNextUse(eOpIndex);
    148160        }
     161        // although instruction[index] may have more than one use of the symbol
     162        // as an operand, the first of those uses has the real nextUse info.
     163        // thus we may use getEOpIndex and get the correct information.
     164        public int getNextUse(int index, String symbol) {
     165                Instruction instr = block.instruction(index);
     166                int eOpIndex = getFirstEOpIndex(instr, symbol);
     167                int nextUse = getNextUse(index, eOpIndex);
     168                return nextUse;
     169        }
    149170        private void setNextUse(int instrIndex, int eOpIndex, int value ) {
    150171                InstructionDefUseIndices indices = defsAndUses.get(instrIndex);
     
    154175        private void setNextUse(int index, String operand, int value) {
    155176                Instruction instr = block.instruction(index);
    156                 int eOpIndex = getEOpIndex(instr, operand);
     177                int eOpIndex = getFirstEOpIndex(instr, operand);
    157178                setNextUse(index, eOpIndex, value);
    158179        }
    159         private int getEOpIndex(Instruction instr, String operand) {
     180        // returns eOpIndex of the FIRST use of symbol as an operand.
     181        private int getFirstEOpIndex(Instruction instr, String symbol) {
    160182                int eOpIndex;
    161183                for(eOpIndex=1; eOpIndex<instr.numOperands()+1; eOpIndex++) {
    162                         if(instr.getOperand(eOpIndex-1).equals(operand))
     184                        if(instr.getOperand(eOpIndex-1).equals(symbol))
    163185                                break;
    164186                }
  • proto/pebble/trunk/src/main/Main.java

    r1254 r1256  
    33import incode.Fragment;
    44import incode.Pythonater;
     5import incode.global.LivenessProperty;
    56import incode.global.MergeBlocks;
    67import incode.localOptimization.ReuseAvailableExpressions;
     
    6162           
    6263            ReuseAvailableExpressions.apply(headBlock);
     64//            LocalDeadCodeEliminator.apply(headBlock);
     65            LivenessProperty.build(Fragment.make(headBlock));
    6366           
    6467            Pythonater.apply(symbolTable, headCollector, headBlock);
Note: See TracChangeset for help on using the changeset viewer.