14238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng/* 24238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Copyright (C) 2009 The Android Open Source Project 34238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 44238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Licensed under the Apache License, Version 2.0 (the "License"); 54238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * you may not use this file except in compliance with the License. 64238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * You may obtain a copy of the License at 74238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 84238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * http://www.apache.org/licenses/LICENSE-2.0 94238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Unless required by applicable law or agreed to in writing, software 114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * distributed under the License is distributed on an "AS IS" BASIS, 124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 134238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * See the License for the specific language governing permissions and 144238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * limitations under the License. 154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 17375fb116bcb817b37509ab579dbd55cdbb765cbfCarl Shapiro#ifndef DALVIK_VM_DATAFLOW_H_ 18375fb116bcb817b37509ab579dbd55cdbb765cbfCarl Shapiro#define DALVIK_VM_DATAFLOW_H_ 194238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 204238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#include "Dalvik.h" 214238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#include "CompilerInternals.h" 224238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 234238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengtypedef enum DataFlowAttributePos { 244238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kUA = 0, 254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kUB, 264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kUC, 274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kUAWide, 284238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kUBWide, 294238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kUCWide, 304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kDA, 314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kDAWide, 324238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kIsMove, 334238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kIsLinear, 344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kSetsConst, 354238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kFormat35c, 364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kFormat3rc, 374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kPhi, 384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kNullNRangeCheck0, 394238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kNullNRangeCheck1, 404238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng kNullNRangeCheck2, 411465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee kFPA, 421465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee kFPB, 431465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee kFPC, 447a2697d327936e20ef5484f7819e2e4bf91c891fBen Cheng kGetter, 457a2697d327936e20ef5484f7819e2e4bf91c891fBen Cheng kSetter, 464238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} DataFlowAttributes; 474238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 484238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_NOP 0 494238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_UA (1 << kUA) 504238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_UB (1 << kUB) 514238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_UC (1 << kUC) 524238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_UA_WIDE (1 << kUAWide) 534238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_UB_WIDE (1 << kUBWide) 544238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_UC_WIDE (1 << kUCWide) 554238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_DA (1 << kDA) 564238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_DA_WIDE (1 << kDAWide) 574238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_IS_MOVE (1 << kIsMove) 584238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_IS_LINEAR (1 << kIsLinear) 594238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_SETS_CONST (1 << kSetsConst) 604238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_FORMAT_35C (1 << kFormat35c) 614238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_FORMAT_3RC (1 << kFormat3rc) 624238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_PHI (1 << kPhi) 634238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_NULL_N_RANGE_CHECK_0 (1 << kNullNRangeCheck0) 644238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_NULL_N_RANGE_CHECK_1 (1 << kNullNRangeCheck1) 654238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_NULL_N_RANGE_CHECK_2 (1 << kNullNRangeCheck2) 661465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee#define DF_FP_A (1 << kFPA) 671465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee#define DF_FP_B (1 << kFPB) 681465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee#define DF_FP_C (1 << kFPC) 697a2697d327936e20ef5484f7819e2e4bf91c891fBen Cheng#define DF_IS_GETTER (1 << kGetter) 707a2697d327936e20ef5484f7819e2e4bf91c891fBen Cheng#define DF_IS_SETTER (1 << kSetter) 714238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 724238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_HAS_USES (DF_UA | DF_UB | DF_UC | DF_UA_WIDE | \ 734238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DF_UB_WIDE | DF_UC_WIDE) 744238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 754238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_HAS_DEFS (DF_DA | DF_DA_WIDE) 764238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 774238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DF_HAS_NR_CHECKS (DF_NULL_N_RANGE_CHECK_0 | \ 784238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DF_NULL_N_RANGE_CHECK_1 | \ 794238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DF_NULL_N_RANGE_CHECK_2) 804238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 81ccd6c0102d1f898aaea1c94761167fdd083b5275Ben Cheng#define DF_A_IS_REG (DF_UA | DF_UA_WIDE | DF_DA | DF_DA_WIDE) 82ccd6c0102d1f898aaea1c94761167fdd083b5275Ben Cheng#define DF_B_IS_REG (DF_UB | DF_UB_WIDE) 83ccd6c0102d1f898aaea1c94761167fdd083b5275Ben Cheng#define DF_C_IS_REG (DF_UC | DF_UC_WIDE) 847a2697d327936e20ef5484f7819e2e4bf91c891fBen Cheng#define DF_IS_GETTER_OR_SETTER (DF_IS_GETTER | DF_IS_SETTER) 85ccd6c0102d1f898aaea1c94761167fdd083b5275Ben Cheng 861465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbeeextern int dvmCompilerDataFlowAttributes[kMirOpLast]; 874238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 884238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengtypedef struct BasicBlockDataFlow { 894238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng BitVector *useV; 904238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng BitVector *defV; 914238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng BitVector *liveInV; 924238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng BitVector *phiV; 934238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int *dalvikToSSAMap; 944238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} BasicBlockDataFlow; 954238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 964238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengtypedef struct SSARepresentation { 974238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int numUses; 984238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int *uses; 991465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee bool *fpUse; 1004238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int numDefs; 1014238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int *defs; 1021465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee bool *fpDef; 1034238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} SSARepresentation; 1044238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 105535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng/* 106535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * An induction variable is represented by "m*i + c", where i is a basic 107535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * induction variable. 108535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng */ 1094238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengtypedef struct InductionVariableInfo { 1104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int ssaReg; 1114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int basicSSAReg; 112535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng int m; // multiplier 113535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng int c; // constant 114535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng int inc; // loop incriment 1154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} InductionVariableInfo; 1164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 1174238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengtypedef struct ArrayAccessInfo { 1184238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int arrayReg; 1194238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int ivReg; 1204238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int maxC; // For DIV - will affect upper bound checking 1214238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int minC; // For DIV - will affect lower bound checking 1224238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} ArrayAccessInfo; 1234238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 1244238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define ENCODE_REG_SUB(r,s) ((s<<16) | r) 1254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DECODE_REG(v) (v & 0xffff) 1264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DECODE_SUB(v) (((unsigned int) v) >> 16) 1274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 128375fb116bcb817b37509ab579dbd55cdbb765cbfCarl Shapiro#endif // DALVIK_VM_DATAFLOW_H_ 129