001package org.clafer.ir.analysis;
002
003import java.util.HashSet;
004import java.util.Set;
005import org.clafer.ir.IrArrayToSet;
006import org.clafer.ir.IrElement;
007import org.clafer.ir.IrExpr;
008import org.clafer.ir.IrIntExpr;
009import org.clafer.ir.IrJoinFunction;
010import org.clafer.ir.IrJoinRelation;
011import org.clafer.ir.IrModule;
012import org.clafer.ir.IrRewriter;
013import org.clafer.ir.IrSetExpr;
014
015/**
016 *
017 * @author jimmy
018 */
019public class CommonSubexpression {
020
021    private CommonSubexpression() {
022    }
023
024    public static Set<IrExpr> findCommonSubexpressions(IrModule module) {
025        CommonSubexpressionFinder finder = new CommonSubexpressionFinder();
026        finder.rewrite(module, null);
027        return finder.duplicates;
028    }
029
030    private static class CommonSubexpressionFinder extends IrRewriter<Void> {
031
032        private final Set<IrExpr> seen = new HashSet<>();
033        private final Set<IrExpr> duplicates = new HashSet<>();
034
035        @Override
036        public IrIntExpr visit(IrElement ir, Void a) {
037            rewrite(ir.getArray(), a);
038            rewrite(ir.getIndex(), a);
039            if (!seen.add(ir)) {
040                duplicates.add(ir);
041            }
042            return ir;
043        }
044
045        @Override
046        public IrSetExpr visit(IrArrayToSet ir, Void a) {
047            rewrite(ir.getArray(), a);
048            if (!seen.add(ir)) {
049                duplicates.add(ir);
050            }
051            return ir;
052        }
053
054        @Override
055        public IrSetExpr visit(IrJoinRelation ir, Void a) {
056            rewrite(ir.getTake(), a);
057            rewrite(ir.getChildren(), a);
058            if (!seen.add(ir)) {
059                duplicates.add(ir);
060            }
061            return ir;
062        }
063
064        @Override
065        public IrSetExpr visit(IrJoinFunction ir, Void a) {
066            rewrite(ir.getTake(), a);
067            rewrite(ir.getRefs(), a);
068            if (!seen.add(ir)) {
069                duplicates.add(ir);
070            }
071            return ir;
072        }
073    }
074}