SCCP.java revision 579d7739c53a2707ad711a2d2cae46d7d782f061 
1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.ssa;
18
19import com.android.dx.rop.code.CstInsn;
20import com.android.dx.rop.code.Insn;
21import com.android.dx.rop.code.PlainInsn;
22import com.android.dx.rop.code.RegOps;
23import com.android.dx.rop.code.RegisterSpecList;
24import com.android.dx.rop.code.Rop;
25import com.android.dx.rop.code.RegisterSpec;
26import com.android.dx.rop.code.Rops;
27import com.android.dx.rop.cst.Constant;
28import com.android.dx.rop.cst.CstInteger;
29import com.android.dx.rop.cst.TypedConstant;
30import com.android.dx.rop.type.TypeBearer;
31import com.android.dx.rop.type.Type;
32
33import java.util.ArrayList;
34import java.util.BitSet;
35
36/**
37 * A small variant of Wegman and Zadeck's Sparse Conditional Constant
38 * Propagation algorithm.
39 */
40public class SCCP {
41    /** Lattice values  */
42    private static final int TOP = 0;
43    private static final int CONSTANT = 1;
44    private static final int VARYING = 2;
45    /** method we're processing */
46    private SsaMethod ssaMeth;
47    /** ssaMeth.getRegCount() */
48    private int regCount;
49    /** Lattice values for each SSA register */
50    private int[] latticeValues;
51    /** For those registers that are constant, this is the constant value */
52    private Constant[] latticeConstants;
53    /** Worklist of basic blocks to be processed */
54    private ArrayList<SsaBasicBlock> cfgWorklist;
55    /** Worklist of executed basic blocks with phis to be processed */
56    private ArrayList<SsaBasicBlock> cfgPhiWorklist;
57    /** Bitset containing bits for each block that has been found executable */
58    private BitSet executableBlocks;
59    /** Worklist for SSA edges.  This is a list of registers to process */
60    private ArrayList<SsaInsn> ssaWorklist;
61    /**
62     * Worklist for SSA edges that represent varying values.  It makes the
63     * algorithm much faster if you move all values to VARYING as fast as
64     * possible.
65     */
66    private ArrayList<SsaInsn> varyingWorklist;
67    /** Worklist of potential branches to convert to gotos */
68    private ArrayList<SsaInsn> branchWorklist;
69
70    private SCCP(SsaMethod ssaMeth) {
71        this.ssaMeth = ssaMeth;
72        this.regCount = ssaMeth.getRegCount();
73        this.latticeValues = new int[this.regCount];
74        this.latticeConstants = new Constant[this.regCount];
75        this.cfgWorklist = new ArrayList<SsaBasicBlock>();
76        this.cfgPhiWorklist = new ArrayList<SsaBasicBlock>();
77        this.executableBlocks = new BitSet(ssaMeth.getBlocks().size());
78        this.ssaWorklist = new ArrayList<SsaInsn>();
79        this.varyingWorklist = new ArrayList<SsaInsn>();
80        this.branchWorklist = new ArrayList<SsaInsn>();
81        for (int i = 0; i < this.regCount; i++) {
82            latticeValues[i] = TOP;
83            latticeConstants[i] = null;
84        }
85    }
86
87    /**
88     * Performs sparse conditional constant propagation on a method.
89     * @param ssaMethod Method to process
90     */
91    public static void process (SsaMethod ssaMethod) {
92        new SCCP(ssaMethod).run();
93    }
94
95    /**
96     * Adds a SSA basic block to the CFG worklist if it's unexecuted, or
97     * to the CFG phi worklist if it's already executed.
98     * @param ssaBlock Block to add
99     */
100    private void addBlockToWorklist(SsaBasicBlock ssaBlock) {
101        if (!executableBlocks.get(ssaBlock.getIndex())) {
102            cfgWorklist.add(ssaBlock);
103            executableBlocks.set(ssaBlock.getIndex());
104        } else {
105            cfgPhiWorklist.add(ssaBlock);
106        }
107    }
108
109    /**
110     * Adds an SSA register's uses to the SSA worklist.
111     * @param reg SSA register
112     * @param latticeValue new lattice value for @param reg.
113     */
114    private void addUsersToWorklist(int reg, int latticeValue) {
115        if (latticeValue == VARYING) {
116            for (SsaInsn insn : ssaMeth.getUseListForRegister(reg)) {
117                varyingWorklist.add(insn);
118            }
119        } else {
120            for (SsaInsn insn : ssaMeth.getUseListForRegister(reg)) {
121                ssaWorklist.add(insn);
122            }
123        }
124    }
125
126    /**
127     * Sets a lattice value for a register to value.
128     * @param reg SSA register
129     * @param value Lattice value
130     * @param cst Constant value (may be null)
131     * @return true if the lattice value changed.
132     */
133    private boolean setLatticeValueTo(int reg, int value, Constant cst) {
134        if (value != CONSTANT) {
135            if (latticeValues[reg] != value) {
136                latticeValues[reg] = value;
137                return true;
138            }
139            return false;
140        } else {
141            if (latticeValues[reg] != value
142                    || !latticeConstants[reg].equals(cst)) {
143                latticeValues[reg] = value;
144                latticeConstants[reg] = cst;
145                return true;
146            }
147            return false;
148        }
149    }
150
151    /**
152     * Simulates a PHI node and set the lattice for the result
153     * to the appropriate value.
154     * Meet values:
155     * TOP x anything = TOP
156     * VARYING x anything = VARYING
157     * CONSTANT x CONSTANT = CONSTANT if equal constants, VARYING otherwise
158     * @param insn PHI to simulate.
159     */
160    private void simulatePhi(PhiInsn insn) {
161        int phiResultReg = insn.getResult().getReg();
162
163        if (latticeValues[phiResultReg] == VARYING) {
164            return;
165        }
166
167        RegisterSpecList sources = insn.getSources();
168        int phiResultValue = TOP;
169        Constant phiConstant = null;
170        int sourceSize = sources.size();
171
172        for (int i = 0; i < sourceSize; i++) {
173            int predBlockIndex = insn.predBlockIndexForSourcesIndex(i);
174            int sourceReg = sources.get(i).getReg();
175            int sourceRegValue = latticeValues[sourceReg];
176
177            if (!executableBlocks.get(predBlockIndex)) {
178                continue;
179            }
180
181            if (sourceRegValue == CONSTANT) {
182                if (phiConstant == null) {
183                    phiConstant = latticeConstants[sourceReg];
184                    phiResultValue = CONSTANT;
185                 } else if (!latticeConstants[sourceReg].equals(phiConstant)){
186                    phiResultValue = VARYING;
187                    break;
188                }
189            } else {
190                phiResultValue = sourceRegValue;
191                break;
192            }
193        }
194        if (setLatticeValueTo(phiResultReg, phiResultValue, phiConstant)) {
195            addUsersToWorklist(phiResultReg, phiResultValue);
196        }
197    }
198
199    /**
200     * Simulate a block and note the results in the lattice.
201     * @param block Block to visit
202     */
203    private void simulateBlock(SsaBasicBlock block) {
204        for (SsaInsn insn : block.getInsns()) {
205            if (insn instanceof PhiInsn) {
206                simulatePhi((PhiInsn) insn);
207            } else {
208                simulateStmt(insn);
209            }
210        }
211    }
212
213    /**
214     * Simulate the phis in a block and note the results in the lattice.
215     * @param block Block to visit
216     */
217    private void simulatePhiBlock(SsaBasicBlock block) {
218        for (SsaInsn insn : block.getInsns()) {
219            if (insn instanceof PhiInsn) {
220                simulatePhi((PhiInsn) insn);
221            } else {
222                return;
223            }
224        }
225    }
226
227    private static String latticeValName(int latticeVal) {
228        switch (latticeVal) {
229            case TOP: return "TOP";
230            case CONSTANT: return "CONSTANT";
231            case VARYING: return "VARYING";
232            default: return "UNKNOWN";
233        }
234    }
235
236    /**
237     * Simulates branch insns, if possible. Adds reachable successor blocks
238     * to the CFG worklists.
239     * @param insn branch to simulate
240     */
241    private void simulateBranch(SsaInsn insn) {
242        Rop opcode = insn.getOpcode();
243        RegisterSpecList sources = insn.getSources();
244
245        boolean constantBranch = false;
246        boolean constantSuccessor = false;
247
248        // Check if the insn is a branch with a constant condition
249        if (opcode.getBranchingness() == Rop.BRANCH_IF) {
250            Constant cA = null;
251            Constant cB = null;
252
253            RegisterSpec specA = sources.get(0);
254            int regA = specA.getReg();
255            if (!ssaMeth.isRegALocal(specA) &&
256                    latticeValues[regA] == CONSTANT) {
257                cA = latticeConstants[regA];
258            }
259
260            if (sources.size() == 2) {
261                RegisterSpec specB = sources.get(1);
262                int regB = specB.getReg();
263                if (!ssaMeth.isRegALocal(specB) &&
264                        latticeValues[regB] == CONSTANT) {
265                    cB = latticeConstants[regB];
266                }
267            }
268
269            // Calculate the result of the condition
270            if (cA != null && sources.size() == 1) {
271                switch (((TypedConstant) cA).getBasicType()) {
272                    case Type.BT_INT:
273                        constantBranch = true;
274                        int vA = ((CstInteger) cA).getValue();
275                        switch (opcode.getOpcode()) {
276                            case RegOps.IF_EQ:
277                                constantSuccessor = (vA == 0);
278                                break;
279                            case RegOps.IF_NE:
280                                constantSuccessor = (vA != 0);
281                                break;
282                            case RegOps.IF_LT:
283                                constantSuccessor = (vA < 0);
284                                break;
285                            case RegOps.IF_GE:
286                                constantSuccessor = (vA >= 0);
287                                break;
288                            case RegOps.IF_LE:
289                                constantSuccessor = (vA <= 0);
290                                break;
291                            case RegOps.IF_GT:
292                                constantSuccessor = (vA > 0);
293                                break;
294                            default:
295                                throw new RuntimeException("Unexpected op");
296                        }
297                        break;
298                    default:
299                        // not yet supported
300                }
301            } else if (cA != null && cB != null) {
302                switch (((TypedConstant) cA).getBasicType()) {
303                    case Type.BT_INT:
304                        constantBranch = true;
305                        int vA = ((CstInteger) cA).getValue();
306                        int vB = ((CstInteger) cB).getValue();
307                        switch (opcode.getOpcode()) {
308                            case RegOps.IF_EQ:
309                                constantSuccessor = (vA == vB);
310                                break;
311                            case RegOps.IF_NE:
312                                constantSuccessor = (vA != vB);
313                                break;
314                            case RegOps.IF_LT:
315                                constantSuccessor = (vA < vB);
316                                break;
317                            case RegOps.IF_GE:
318                                constantSuccessor = (vA >= vB);
319                                break;
320                            case RegOps.IF_LE:
321                                constantSuccessor = (vA <= vB);
322                                break;
323                            case RegOps.IF_GT:
324                                constantSuccessor = (vA > vB);
325                                break;
326                            default:
327                                throw new RuntimeException("Unexpected op");
328                        }
329                        break;
330                    default:
331                        // not yet supported
332                }
333            }
334        }
335
336        /*
337         * If condition is constant, add only the target block to the
338         * worklist. Otherwise, add all successors to the worklist.
339         */
340        SsaBasicBlock block = insn.getBlock();
341
342        if (constantBranch) {
343            int successorBlock;
344            if (constantSuccessor) {
345                successorBlock = block.getSuccessorList().get(1);
346            } else {
347                successorBlock = block.getSuccessorList().get(0);
348            }
349            addBlockToWorklist(ssaMeth.getBlocks().get(successorBlock));
350            branchWorklist.add(insn);
351        } else {
352            for (int i = 0; i < block.getSuccessorList().size(); i++) {
353                int successorBlock = block.getSuccessorList().get(i);
354                addBlockToWorklist(ssaMeth.getBlocks().get(successorBlock));
355            }
356        }
357    }
358
359    /**
360     * Simulates math insns, if possible.
361     *
362     * @param insn non-null insn to simulate
363     * @param resultType basic type of the result
364     * @return constant result or null if not simulatable.
365     */
366    private Constant simulateMath(SsaInsn insn, int resultType) {
367        Insn ropInsn = insn.getOriginalRopInsn();
368        int opcode = insn.getOpcode().getOpcode();
369        RegisterSpecList sources = insn.getSources();
370        int regA = sources.get(0).getReg();
371        Constant cA;
372        Constant cB;
373
374        if (latticeValues[regA] != CONSTANT) {
375            cA = null;
376        } else {
377            cA = latticeConstants[regA];
378        }
379
380        if (sources.size() == 1) {
381            CstInsn cstInsn = (CstInsn) ropInsn;
382            cB = cstInsn.getConstant();
383        } else { /* sources.size() == 2 */
384            int regB = sources.get(1).getReg();
385            if (latticeValues[regB] != CONSTANT) {
386                cB = null;
387            } else {
388                cB = latticeConstants[regB];
389            }
390        }
391
392        if (cA == null || cB == null) {
393            //TODO handle a constant of 0 with MUL or AND
394            return null;
395        }
396
397        switch (resultType) {
398            case Type.BT_INT:
399                int vR;
400                boolean skip=false;
401
402                int vA = ((CstInteger) cA).getValue();
403                int vB = ((CstInteger) cB).getValue();
404
405                switch (opcode) {
406                    case RegOps.ADD:
407                        vR = vA + vB;
408                        break;
409                    case RegOps.SUB:
410                        // 1 source for reverse sub, 2 sources for regular sub
411                        if (sources.size() == 1) {
412                            vR = vB - vA;
413                        } else {
414                            vR = vA - vB;
415                        }
416                        break;
417                    case RegOps.MUL:
418                        vR = vA * vB;
419                        break;
420                    case RegOps.DIV:
421                        if (vB == 0) {
422                            skip = true;
423                            vR = 0; // just to hide a warning
424                        } else {
425                            vR = vA / vB;
426                        }
427                        break;
428                    case RegOps.AND:
429                        vR = vA & vB;
430                        break;
431                    case RegOps.OR:
432                        vR = vA | vB;
433                        break;
434                    case RegOps.XOR:
435                        vR = vA ^ vB;
436                        break;
437                    case RegOps.SHL:
438                        vR = vA << vB;
439                        break;
440                    case RegOps.SHR:
441                        vR = vA >> vB;
442                        break;
443                    case RegOps.USHR:
444                        vR = vA >>> vB;
445                        break;
446                    case RegOps.REM:
447                        if (vB == 0) {
448                            skip = true;
449                            vR = 0; // just to hide a warning
450                        } else {
451                            vR = vA % vB;
452                        }
453                        break;
454                    default:
455                        throw new RuntimeException("Unexpected op");
456                }
457
458                return skip ? null : CstInteger.make(vR);
459
460            default:
461                // not yet supported
462                return null;
463        }
464    }
465
466    /**
467     * Simulates a statement and set the result lattice value.
468     * @param insn instruction to simulate
469     */
470    private void simulateStmt(SsaInsn insn) {
471        Insn ropInsn = insn.getOriginalRopInsn();
472        if (ropInsn.getOpcode().getBranchingness() != Rop.BRANCH_NONE
473                || ropInsn.getOpcode().isCallLike()) {
474            simulateBranch(insn);
475        }
476
477        int opcode = insn.getOpcode().getOpcode();
478        RegisterSpec result = insn.getResult();
479
480        if (result == null) {
481            // Find move-result-pseudo result for int div and int rem
482            if (opcode == RegOps.DIV || opcode == RegOps.REM) {
483                SsaBasicBlock succ = insn.getBlock().getPrimarySuccessor();
484                result = succ.getInsns().get(0).getResult();
485            } else {
486                return;
487            }
488        }
489
490        int resultReg = result.getReg();
491        int resultValue = VARYING;
492        Constant resultConstant = null;
493
494        switch (opcode) {
495            case RegOps.CONST: {
496                CstInsn cstInsn = (CstInsn)ropInsn;
497                resultValue = CONSTANT;
498                resultConstant = cstInsn.getConstant();
499                break;
500            }
501            case RegOps.MOVE: {
502                if (insn.getSources().size() == 1) {
503                    int sourceReg = insn.getSources().get(0).getReg();
504                    resultValue = latticeValues[sourceReg];
505                    resultConstant = latticeConstants[sourceReg];
506                }
507                break;
508            }
509            case RegOps.ADD:
510            case RegOps.SUB:
511            case RegOps.MUL:
512            case RegOps.DIV:
513            case RegOps.AND:
514            case RegOps.OR:
515            case RegOps.XOR:
516            case RegOps.SHL:
517            case RegOps.SHR:
518            case RegOps.USHR:
519            case RegOps.REM: {
520                resultConstant = simulateMath(insn, result.getBasicType());
521                if (resultConstant != null) {
522                    resultValue = CONSTANT;
523                }
524                break;
525            }
526            case RegOps.MOVE_RESULT_PSEUDO: {
527                if (latticeValues[resultReg] == CONSTANT) {
528                    resultValue = latticeValues[resultReg];
529                    resultConstant = latticeConstants[resultReg];
530                }
531                break;
532            }
533            // TODO: Handle non-int arithmetic.
534            // TODO: Eliminate check casts that we can prove the type of.
535            default: {}
536        }
537        if (setLatticeValueTo(resultReg, resultValue, resultConstant)) {
538            addUsersToWorklist(resultReg, resultValue);
539        }
540    }
541
542    private void run() {
543        SsaBasicBlock firstBlock = ssaMeth.getEntryBlock();
544        addBlockToWorklist(firstBlock);
545
546        /* Empty all the worklists by propagating our values */
547        while (!cfgWorklist.isEmpty()
548                || !cfgPhiWorklist.isEmpty()
549                || !ssaWorklist.isEmpty()
550                || !varyingWorklist.isEmpty()) {
551            while (!cfgWorklist.isEmpty()) {
552                int listSize = cfgWorklist.size() - 1;
553                SsaBasicBlock block = cfgWorklist.remove(listSize);
554                simulateBlock(block);
555            }
556
557            while (!cfgPhiWorklist.isEmpty()) {
558                int listSize = cfgPhiWorklist.size() - 1;
559                SsaBasicBlock block = cfgPhiWorklist.remove(listSize);
560                simulatePhiBlock(block);
561            }
562
563            while (!varyingWorklist.isEmpty()) {
564                int listSize = varyingWorklist.size() - 1;
565                SsaInsn insn = varyingWorklist.remove(listSize);
566
567                if (!executableBlocks.get(insn.getBlock().getIndex())) {
568                    continue;
569                }
570
571                if (insn instanceof PhiInsn) {
572                    simulatePhi((PhiInsn)insn);
573                } else {
574                    simulateStmt(insn);
575                }
576            }
577            while (!ssaWorklist.isEmpty()) {
578                int listSize = ssaWorklist.size() - 1;
579                SsaInsn insn = ssaWorklist.remove(listSize);
580
581                if (!executableBlocks.get(insn.getBlock().getIndex())) {
582                    continue;
583                }
584
585                if (insn instanceof PhiInsn) {
586                    simulatePhi((PhiInsn)insn);
587                } else {
588                    simulateStmt(insn);
589                }
590            }
591        }
592
593        replaceConstants();
594        replaceBranches();
595    }
596
597    /**
598     * Replaces TypeBearers in source register specs with constant type
599     * bearers if possible. These are then referenced in later optimization
600     * steps.
601     */
602    private void replaceConstants() {
603        for (int reg = 0; reg < regCount; reg++) {
604            if (latticeValues[reg] != CONSTANT) {
605                continue;
606            }
607            if (!(latticeConstants[reg] instanceof TypedConstant)) {
608                // We can't do much with these
609                continue;
610            }
611
612            SsaInsn defn = ssaMeth.getDefinitionForRegister(reg);
613            TypeBearer typeBearer = defn.getResult().getTypeBearer();
614
615            if (typeBearer.isConstant()) {
616                /*
617                 * The definition was a constant already.
618                 * The uses should be as well.
619                 */
620                continue;
621            }
622
623            // Update the destination RegisterSpec with the constant value
624            RegisterSpec dest = defn.getResult();
625            RegisterSpec newDest
626                    = dest.withType((TypedConstant)latticeConstants[reg]);
627            defn.setResult(newDest);
628
629            /*
630             * Update the sources RegisterSpec's of all non-move uses.
631             * These will be used in later steps.
632             */
633            for (SsaInsn insn : ssaMeth.getUseListForRegister(reg)) {
634                if (insn.isPhiOrMove()) {
635                    continue;
636                }
637
638                NormalSsaInsn nInsn = (NormalSsaInsn) insn;
639                RegisterSpecList sources = insn.getSources();
640
641                int index = sources.indexOfRegister(reg);
642
643                RegisterSpec spec = sources.get(index);
644                RegisterSpec newSpec
645                        = spec.withType((TypedConstant)latticeConstants[reg]);
646
647                nInsn.changeOneSource(index, newSpec);
648            }
649        }
650    }
651
652    /**
653     * Replaces branches that have constant conditions with gotos
654     */
655    private void replaceBranches() {
656        for (SsaInsn insn : branchWorklist) {
657            // Find if a successor block is never executed
658            int oldSuccessor = -1;
659            SsaBasicBlock block = insn.getBlock();
660            int successorSize = block.getSuccessorList().size();
661            for (int i = 0; i < successorSize; i++) {
662                int successorBlock = block.getSuccessorList().get(i);
663                if (!executableBlocks.get(successorBlock)) {
664                    oldSuccessor = successorBlock;
665                }
666            }
667
668            /*
669             * Prune branches that have already been handled and ones that no
670             * longer have constant conditions (no nonexecutable successors)
671             */
672            if (successorSize != 2 || oldSuccessor == -1) continue;
673
674            // Replace branch with goto
675            Insn originalRopInsn = insn.getOriginalRopInsn();
676            block.replaceLastInsn(new PlainInsn(Rops.GOTO,
677                originalRopInsn.getPosition(), null, RegisterSpecList.EMPTY));
678            block.removeSuccessor(oldSuccessor);
679        }
680    }
681}
682