Reviewers: danno, Toon Verwaest,
Description:
Implement simplistic local alias analysis, which will be used in both check
elimination and load elimination.
BUG=
Please review this at https://codereview.chromium.org/23516010/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files (+43, -26 lines):
A + src/hydrogen-alias-analysis.h
M tools/gyp/v8.gyp
Index: src/hydrogen-alias-analysis.h
diff --git a/src/hydrogen-bce.h b/src/hydrogen-alias-analysis.h
similarity index 51%
copy from src/hydrogen-bce.h
copy to src/hydrogen-alias-analysis.h
index
d91997bda011775d92a66eb9c2c9acbf581d4491..f04f9a2f9ec7a209a596fa3d2d41df6839b57ea0
100644
--- a/src/hydrogen-bce.h
+++ b/src/hydrogen-alias-analysis.h
@@ -25,48 +25,64 @@
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#ifndef V8_HYDROGEN_BCE_H_
-#define V8_HYDROGEN_BCE_H_
+#ifndef V8_HYDROGEN_ALIAS_ANALYSIS_H_
+#define V8_HYDROGEN_ALIAS_ANALYSIS_H_
#include "hydrogen.h"
namespace v8 {
namespace internal {
-
-class BoundsCheckBbData;
-class BoundsCheckKey;
-class BoundsCheckTable : private ZoneHashMap {
- public:
- explicit BoundsCheckTable(Zone* zone);
-
- INLINE(BoundsCheckBbData** LookupOrInsert(BoundsCheckKey* key, Zone*
zone));
- INLINE(void Insert(BoundsCheckKey* key, BoundsCheckBbData* data, Zone*
zone));
- INLINE(void Delete(BoundsCheckKey* key));
-
- private:
- DISALLOW_COPY_AND_ASSIGN(BoundsCheckTable);
+enum HAliasing {
+ kMustAlias,
+ kMayAlias,
+ kNoAlias
};
-class HBoundsCheckEliminationPhase : public HPhase {
+// Defines the interface to alias analysis for the rest of the compiler.
+// A simple implementation can use only local reasoning, but a more
powerful
+// analysis might employ points-to analysis.
+class HAliasAnalyzer : public ZoneObject {
public:
- explicit HBoundsCheckEliminationPhase(HGraph* graph)
- : HPhase("H_Bounds checks elimination", graph), table_(zone()) { }
-
- void Run() {
- EliminateRedundantBoundsChecks(graph()->entry_block());
+ // Simple alias analysis distinguishes allocations, parameters,
+ // and constants using only local reasoning.
+ HAliasing Query(HValue* a, HValue* b) {
+ // The same SSA value always references the same object.
+ if (a == b) return kMustAlias;
+
+ if (a->IsAllocate() || a->IsInnerAllocatedObject()) {
+ // Two non-identical allocations can never be aliases.
+ if (b->IsAllocate()) return kNoAlias;
+ if (b->IsInnerAllocatedObject()) return kNoAlias;
+ // An allocation can never alias a parameter or a constant.
+ if (b->IsParameter()) return kNoAlias;
+ if (b->IsConstant()) return kNoAlias;
+ }
+ if (b->IsAllocate() || b->IsInnerAllocatedObject()) {
+ // An allocation can never alias a parameter or a constant.
+ if (a->IsParameter()) return kNoAlias;
+ if (a->IsConstant()) return kNoAlias;
+ }
+
+ // TODO(titzer): return MustAlias for two equivalent constants.
+ return kMayAlias;
}
- private:
- void EliminateRedundantBoundsChecks(HBasicBlock* bb);
+ inline bool MayAlias(HValue* a, HValue* b) {
+ return Query(a, b) == kMayAlias;
+ }
- BoundsCheckTable table_;
+ inline bool MustAlias(HValue* a, HValue* b) {
+ return Query(a, b) == kMustAlias;
+ }
- DISALLOW_COPY_AND_ASSIGN(HBoundsCheckEliminationPhase);
+ inline bool NoAlias(HValue* a, HValue* b) {
+ return Query(a, b) == kNoAlias;
+ }
};
} } // namespace v8::internal
-#endif // V8_HYDROGEN_BCE_H_
+#endif // V8_HYDROGEN_ALIAS_ANALYSIS_H_
Index: tools/gyp/v8.gyp
diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp
index
5d4933a9f0a39accdba9c5bb36db939a47542b9c..4f629ff20e9535b9044b8e7dbf2d52e1d20dcba4
100644
--- a/tools/gyp/v8.gyp
+++ b/tools/gyp/v8.gyp
@@ -336,6 +336,7 @@
'../../src/heap-snapshot-generator.h',
'../../src/heap.cc',
'../../src/heap.h',
+ '../../src/hydrogen-alias-analysis.h',
'../../src/hydrogen-bce.cc',
'../../src/hydrogen-bce.h',
'../../src/hydrogen-bch.cc',
--
--
v8-dev mailing list
v8-dev@googlegroups.com
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to v8-dev+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.