/*
 * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package org.graalvm.compiler.core.amd64;

import org.graalvm.compiler.asm.amd64.AMD64Address.Scale;
import org.graalvm.compiler.core.common.NumUtil;
import org.graalvm.compiler.core.common.type.IntegerStamp;
import org.graalvm.compiler.debug.DebugContext;
import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.ValueNode;
import org.graalvm.compiler.nodes.calc.AddNode;
import org.graalvm.compiler.nodes.calc.LeftShiftNode;
import org.graalvm.compiler.nodes.calc.NegateNode;
import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
import org.graalvm.compiler.nodes.memory.address.AddressNode;
import org.graalvm.compiler.phases.common.AddressLoweringPhase.AddressLowering;

import jdk.vm.ci.meta.JavaConstant;

public class AMD64AddressLowering extends AddressLowering {
    @Override
    public AddressNode lower(ValueNode address) {
        return lower(address, null);
    }

    @Override
    public AddressNode lower(ValueNode base, ValueNode offset) {
        AMD64AddressNode ret = new AMD64AddressNode(base, offset);
        StructuredGraph graph = base.graph();

        boolean changed;
        do {
            changed = improve(graph, base.getDebug(), ret, false, false);
        } while (changed);

        return graph.unique(ret);
    }

    /**
     * Tries to optimize addresses so that they match the AMD64-specific addressing mode better
     * (base + index * scale + displacement).
     *
     * @param graph the current graph
     * @param debug the current debug context
     * @param ret the address that should be optimized
     * @param isBaseNegated determines if the address base is negated. if so, all values that are
     *            extracted from the base will be negated as well
     * @param isIndexNegated determines if the index is negated. if so, all values that are
     *            extracted from the index will be negated as well
     * @return true if the address was modified
     */
    protected boolean improve(StructuredGraph graph, DebugContext debug, AMD64AddressNode ret, boolean isBaseNegated, boolean isIndexNegated) {
        ValueNode newBase = improveInput(ret, ret.getBase(), 0, isBaseNegated);
        if (newBase != ret.getBase()) {
            ret.setBase(newBase);
            return true;
        }

        ValueNode newIdx = improveInput(ret, ret.getIndex(), ret.getScale().log2, isIndexNegated);
        if (newIdx != ret.getIndex()) {
            ret.setIndex(newIdx);
            return true;
        }

        if (ret.getIndex() instanceof LeftShiftNode) {
            LeftShiftNode shift = (LeftShiftNode) ret.getIndex();
            if (shift.getY().isConstant()) {
                int amount = ret.getScale().log2 + shift.getY().asJavaConstant().asInt();
                Scale scale = Scale.fromShift(amount);
                if (scale != null) {
                    ret.setIndex(shift.getX());
                    ret.setScale(scale);
                    return true;
                }
            }
        }

        if (ret.getScale() == Scale.Times1) {
            if (ret.getIndex() == null && ret.getBase() instanceof AddNode) {
                AddNode add = (AddNode) ret.getBase();
                ret.setBase(add.getX());
                ret.setIndex(considerNegation(graph, add.getY(), isBaseNegated));
                return true;
            } else if (ret.getBase() == null && ret.getIndex() instanceof AddNode) {
                AddNode add = (AddNode) ret.getIndex();
                ret.setBase(considerNegation(graph, add.getX(), isIndexNegated));
                ret.setIndex(add.getY());
                return true;
            }

            if (ret.getBase() instanceof LeftShiftNode && !(ret.getIndex() instanceof LeftShiftNode)) {
                ValueNode tmp = ret.getBase();
                ret.setBase(considerNegation(graph, ret.getIndex(), isIndexNegated != isBaseNegated));
                ret.setIndex(considerNegation(graph, tmp, isIndexNegated != isBaseNegated));
                return true;
            }
        }

        return improveNegation(graph, debug, ret, isBaseNegated, isIndexNegated);
    }

    private boolean improveNegation(StructuredGraph graph, DebugContext debug, AMD64AddressNode ret, boolean originalBaseNegated, boolean originalIndexNegated) {
        boolean baseNegated = originalBaseNegated;
        boolean indexNegated = originalIndexNegated;

        ValueNode originalBase = ret.getBase();
        ValueNode originalIndex = ret.getIndex();

        if (ret.getBase() instanceof NegateNode) {
            NegateNode negate = (NegateNode) ret.getBase();
            ret.setBase(negate.getValue());
            baseNegated = !baseNegated;
        }

        if (ret.getIndex() instanceof NegateNode) {
            NegateNode negate = (NegateNode) ret.getIndex();
            ret.setIndex(negate.getValue());
            indexNegated = !indexNegated;
        }

        if (baseNegated != originalBaseNegated || indexNegated != originalIndexNegated) {
            ValueNode base = ret.getBase();
            ValueNode index = ret.getIndex();

            boolean improved = improve(graph, debug, ret, baseNegated, indexNegated);
            if (baseNegated != originalBaseNegated) {
                if (base == ret.getBase()) {
                    ret.setBase(originalBase);
                } else if (ret.getBase() != null) {
                    ret.setBase(graph.maybeAddOrUnique(NegateNode.create(ret.getBase())));
                }
            }

            if (indexNegated != originalIndexNegated) {
                if (index == ret.getIndex()) {
                    ret.setIndex(originalIndex);
                } else if (ret.getIndex() != null) {
                    ret.setIndex(graph.maybeAddOrUnique(NegateNode.create(ret.getIndex())));
                }
            }
            return improved;
        } else {
            assert ret.getBase() == originalBase && ret.getIndex() == originalIndex;
        }
        return false;
    }

    private static ValueNode considerNegation(StructuredGraph graph, ValueNode value, boolean negate) {
        if (negate && value != null) {
            return graph.maybeAddOrUnique(NegateNode.create(value));
        }
        return value;
    }

    private ValueNode improveInput(AMD64AddressNode address, ValueNode node, int shift, boolean negateExtractedDisplacement) {
        if (node == null) {
            return null;
        }

        JavaConstant c = node.asJavaConstant();
        if (c != null) {
            return improveConstDisp(address, node, c, null, shift, negateExtractedDisplacement);
        } else {
            if (node.stamp() instanceof IntegerStamp) {
                if (node instanceof ZeroExtendNode && (((ZeroExtendNode) node).getInputBits() == 32)) {
                    /*
                     * we can't just swallow all zero-extends as we might encounter something like
                     * the following: ZeroExtend(Add(negativeValue, positiveValue)).
                     *
                     * if we swallow the zero-extend in this case and subsequently optimize the add,
                     * we might end up with a negative value that has less than 64 bits in base or
                     * index. such a value would require sign extension instead of zero-extension
                     * but the backend can only do zero-extension. if we ever want to optimize that
                     * further, we would also need to be careful about over-/underflows.
                     *
                     * furthermore, we also can't swallow zero-extends with less than 32 bits as
                     * most of these values are immediately sign-extended to 32 bit by the backend
                     * (therefore, the subsequent implicit zero-extension to 64 bit won't do what we
                     * expect).
                     */
                    ValueNode value = ((ZeroExtendNode) node).getValue();
                    if (!mightBeOptimized(value)) {
                        // if the value is not optimized further by the address lowering, then we
                        // can safely rely on the backend doing the implicitly zero-extension.
                        return value;
                    }
                }

                if (node instanceof AddNode) {
                    AddNode add = (AddNode) node;
                    if (add.getX().isConstant()) {
                        return improveConstDisp(address, node, add.getX().asJavaConstant(), add.getY(), shift, negateExtractedDisplacement);
                    } else if (add.getY().isConstant()) {
                        return improveConstDisp(address, node, add.getY().asJavaConstant(), add.getX(), shift, negateExtractedDisplacement);
                    }
                }
            }
        }

        return node;
    }

    /**
     * This method returns true for all nodes that might be optimized by the address lowering.
     */
    protected boolean mightBeOptimized(ValueNode value) {
        return value instanceof AddNode || value instanceof LeftShiftNode || value instanceof NegateNode || value instanceof ZeroExtendNode;
    }

    private static ValueNode improveConstDisp(AMD64AddressNode address, ValueNode original, JavaConstant c, ValueNode other, int shift, boolean negateExtractedDisplacement) {
        if (c.getJavaKind().isNumericInteger()) {
            long delta = c.asLong() << shift;
            if (updateDisplacement(address, delta, negateExtractedDisplacement)) {
                return other;
            }
        }
        return original;
    }

    protected static boolean updateDisplacement(AMD64AddressNode address, long displacementDelta, boolean negateDelta) {
        long sign = negateDelta ? -1 : 1;
        long disp = address.getDisplacement() + displacementDelta * sign;
        if (NumUtil.isInt(disp)) {
            address.setDisplacement((int) disp);
            return true;
        }
        return false;
    }
}