Changeset 1279 for proto


Ignore:
Timestamp:
Aug 4, 2011, 10:44:13 PM (8 years ago)
Author:
shermer
Message:

Work on cleaning and reducing output code:

Added various small utility methods to objects in 'incode' package.
Minor changes to the broken UseAndNot?, in prep for fixing it.
Added recomputeUses to DefUseProperty?, to incrementally update def-use chains.
Added global optimizations DeadCodeEliminator? and CopyRemover?.
Added utility AllVariables? in incode.global
Added policy to LivenessProperty? that all struct.field variables are live-out.
Discovered bug with MergeBlocks? when if-error was allowed to be in the middle of a block. Removed that option for now.

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

Legend:

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

    r1256 r1279  
    271271                List<BasicBlock> result = new ArrayList<BasicBlock>(2);
    272272                Instruction i = lastInstruction();
    273                
    274                 if(i.isJumpType()) {
    275                         result.add(lookup(i.getOperand(0)));
    276                 }
    277                 else if(i.isTestType()) {
    278                         result.add(lookup(i.getOperand(0)));
    279                         result.add(lookup(i.getOperand(1)));
    280                 }
    281                
     273                for(int eOpNum: i.blockNameEIndices()) {
     274                        result.add(lookup(i.extendedOperand(eOpNum)));
     275                }
    282276                return result;
    283277        }
  • proto/pebble/trunk/src/incode/Fragment.java

    r1255 r1279  
    2323        //              tests and whiles have both successors specified.
    2424        //              any jump-type statement has its successor specified.
     25       
     26
     27        ///////////////////////////////////////////////////////////////////////////
     28        // constructor and two factories
     29        ///////////////////////////////////////////////////////////////////////////
    2530        private Fragment(BasicBlock head) {
    2631                assert head != null;
    2732                this.head = head;
    2833        }
    29 
     34        public static Fragment make(BasicBlock head) {
     35                return new Fragment(head);
     36        }
     37        public static Fragment make(String headName) {
     38                return new Fragment(BasicBlock.lookup(headName));
     39        }
     40       
     41        ///////////////////////////////////////////////////////////////////////////
     42        // head and tail
     43        ///////////////////////////////////////////////////////////////////////////
    3044       
    3145        public BasicBlock getHead() {
     
    4155        }
    4256
     57        ///////////////////////////////////////////////////////////////////////////
     58        // numInstructions
     59        ///////////////////////////////////////////////////////////////////////////
     60        public int numInstructions() {
     61                int sum = 0;
     62                for(BasicBlock block: this) {
     63                        sum += block.numInstructions();
     64                }
     65                return sum;
     66        }
    4367       
    4468        ///////////////////////////////////////////////////////////////////
     
    178202
    179203
    180         public static Fragment make(BasicBlock head) {
    181                 return new Fragment(head);
    182         }
    183         public static Fragment make(String headName) {
    184                 return new Fragment(BasicBlock.lookup(headName));
    185         }
    186 
    187204}
  • proto/pebble/trunk/src/incode/Instruction.java

    r1260 r1279  
    114114                return false;
    115115        }
    116 
     116        public String extendedOperand(int eOpNumber) {
     117                if(eOpNumber==0) {
     118                        return getVariable();
     119                }
     120                return  getOperand(eOpNumber-1);
     121        }
     122        public void setExtendedOperand(int eOpNumber, String replacement) {
     123                if(eOpNumber==0) {
     124                        setVariable(replacement);
     125                }
     126                else {
     127                        setOperand(eOpNumber-1, replacement);
     128                }
     129               
     130        }
     131       
    117132        ///////////////////////////////////////////////////////////////////////////
    118133        // delegate property accessors
     
    132147        public int numOperands() {
    133148                return operation.numberOfOperands();
     149        }
     150        public int[] variableDefEIndices() {
     151                return operation.defEIndices();
     152        }
     153        public int[] blockNameEIndices() {
     154                return operation.blockNameEIndices();
    134155        }
    135156        public List<Integer> variableUseEIndices() {
     
    210231       
    211232       
    212         public String extendedOperand(int eOpNumber) {
    213                 if(eOpNumber==0) {
    214                         return getVariable();
    215                 }
    216                 return  getOperand(eOpNumber-1);
    217         }
     233
    218234        ///////////////////////////////////////////////////////////////////////////
    219235        // static factories for each op-type
     
    310326
    311327
     328
    312329}
  • proto/pebble/trunk/src/incode/Op.java

    r1260 r1279  
    115115                return empty;
    116116        }
     117        public final int[] blockNameEIndices() {
     118                if(this==ERROR)                         return one;
     119                if(isTestType())                        return two;
     120                if(isJumpType())                        return one;
     121                return empty;
     122        }
    117123        ///////////////////////////////////////////////////////////////////////////////
    118124        // Note: I chose to implement the following routines as switches rather than as a
  • proto/pebble/trunk/src/incode/Pythonater.java

    r1261 r1279  
    1515                printPythonStructs(symbolTable, System.out);
    1616                printMainPythonRoutine(head, System.out);
     17                System.err.println("numInstructions: " + Fragment.make(head).numInstructions());
    1718        }
    1819
  • proto/pebble/trunk/src/incode/WorkList.java

    r1242 r1279  
    1616                BasicBlock block;
    1717                Object data;
     18                public String toString() {
     19                        if(block==null)
     20                                return "<null>";
     21                        return "<" + block.getName() + ">";
     22                }
    1823        }
    1924        Deque<Item> todo;
  • proto/pebble/trunk/src/incode/global/LivenessProperty.java

    r1260 r1279  
    198198                        live.initializeLiveInAndOut();
    199199                }
     200               
     201                BasicBlock tail = fragment.getTail();
     202                LivenessProperty tailLive = getFrom(tail);
     203                tailLive.addVariablesToLiveOut(AllVariables.allFieldVariables(fragment));
    200204        }
    201205        private static void processWorkQueueUntilEmpty() {
     
    213217                        workQueue.add(block);
    214218        }
     219        public Set<String> getLiveOut() {
     220                return liveOut;
     221        }
     222        public Set<String> getLiveIn() {
     223                return liveIn;
     224        }
    215225       
    216226
  • proto/pebble/trunk/src/incode/global/MergeBlocks.java

    r1253 r1279  
    1717
    1818public class MergeBlocks {
    19         public static void apply(Fragment fragment, boolean errorEndsBlock) {
     19// TODO:
     20// errorEndsBlock set to true until issues with the error instruction
     21// get resolved.  If an error statement is last in a block, and the following
     22// block is empty, it results in a problem for this algorithm.  Error statements
     23// being non-block-ending should be handled from the Op level out.  Empty block
     24// detection should be more robust.  We should have a fragment variant that
     25// comes with a formal start block and formal end block.
     26       
     27//      public static void apply(Fragment fragment, boolean errorEndsBlock) {
     28        public static void apply(Fragment fragment) {
     29       
    2030                Predecessors.make(fragment);
    2131                clearPredecessors(fragment.getHead());  // keeps head from being merged away.
    22                 MergeBlocks merger = new MergeBlocks(fragment, errorEndsBlock);
     32                MergeBlocks merger = new MergeBlocks(fragment, true); // errorEndsBlock);
    2333                merger.run();
    2434                Predecessors.remove(fragment);          // predecessors are not left in a good state.
     
    8191                }
    8292                else {
     93//                      BasicBlock succSuccessor = successor.primarySuccessor();
    8394                        last.setOperand(0, "--next instruction--");
    8495                }
  • proto/pebble/trunk/src/incode/localOptimization/DefUseProperty.java

    r1256 r1279  
    1717        @SuppressWarnings("unused")
    1818        private static final int IS_DEAD = -4;
     19       
     20        private static final int DOES_NOT_USE = -5;     
     21        public static boolean notThisBlock(int index) {
     22                return index < 0;
     23        }
    1924       
    2025        public static final String PROPERTY_NAME = "defs and uses";
     
    124129                }
    125130        }
     131        public void recomputeUses(int defIndex) {
     132                InstructionDefUseIndices previousIndices = defsAndUses.get(defIndex);
     133                int previousEOpNum = 0;
     134                String symbol = block.instruction(defIndex).getVariable();
     135               
     136                for(int index = defIndex; index < block.numInstructions(); index++) {
     137                        int useIndex = usesSymbol(block.instruction(index), symbol);
     138                        if(useIndex != DOES_NOT_USE) {
     139                                previousIndices.setNextUse(previousEOpNum, index);
     140                                previousIndices = defsAndUses.get(index);
     141                                previousEOpNum = useIndex;
     142                        }
     143                }
     144                previousIndices.setNextUse(previousEOpNum, END_OF_BLOCK);
     145        }
     146       
     147        private int usesSymbol(Instruction instruction, String symbol) {
     148                for(int eOpNum: instruction.variableUseEIndices()) {
     149                        if(instruction.extendedOperand(eOpNum).equals(symbol)) {
     150                                return eOpNum;
     151                        }
     152                }
     153                return DOES_NOT_USE;
     154        }
    126155        private int getWithDefault(Map<String, Integer> map, String operand, int defaultValue) {
    127156                Integer defIndex = map.get(operand);
  • proto/pebble/trunk/src/incode/localOptimization/UseAndNot.java

    r1254 r1279  
    22
    33import incode.BasicBlock;
     4import incode.Fragment;
    45import incode.Instruction;
    56import incode.Op;
     
    2324        /*
    2425         * Preconditions: no instructions are marked for deletion.
    25          * all live-out variables are marked as such.
     26         * all live-out variables are marked as such. [Broken]
    2627         *
    2728         */
     
    5354                        }
    5455                }
    55                
    56                
    57                 EliminateDeadCode.apply(block);
    5856        }
    5957
     
    6967                user.simplify();
    7068        }
     69        static public void apply(Fragment fragment) {
     70                for(BasicBlock block: fragment) {
     71                        apply(block);
     72                }
     73        }
    7174}
  • proto/pebble/trunk/src/main/Main.java

    r1261 r1279  
    33import incode.Fragment;
    44import incode.Pythonater;
     5import incode.global.CopyRemover;
     6import incode.global.DeadCodeEliminator;
     7import incode.global.LivenessProperty;
    58import incode.global.MergeBlocks;
    69import incode.localOptimization.ReuseAvailableExpressions;
     10import incode.localOptimization.UseAndNot;
    711
    812import java.io.IOException;
     
    5761           
    5862            BasicBlock headBlock = ASTtoIncode.apply(tree);
    59             MergeBlocks.apply(Fragment.make(headBlock), false);
    60 
    61 //            DefUseProperty du = new DefUseProperty(headBlock);
    62 //            du.make();
    63 //            du.printDiagnostic();
     63            Fragment fragment = Fragment.make(headBlock);
     64            MergeBlocks.apply(fragment);
    6465           
    6566            ReuseAvailableExpressions.apply(headBlock);
    66 //            LocalDeadCodeEliminator.apply(headBlock);
    67 //            LivenessProperty.build(Fragment.make(headBlock));
     67
     68            LivenessProperty.build(fragment);
     69            DeadCodeEliminator.apply(fragment);
     70           
     71            CopyRemover.apply(fragment);
     72//            UseAndNot.apply(fragment);
    6873           
    6974            Pythonater.apply(tree.getSymbolTable(), headBlock);
Note: See TracChangeset for help on using the changeset viewer.