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