Introduction of improved switch lowering.
This includes the high level analysis of switches, the x86 lowering,
the repointing of targets in jump tables and ASM emission of jump
tables.
The technique uses jump tables, range test and binary search with
worst case O(lg n) which improves the previous worst case of O(n)
from a sequential search.
Use is hidden by the --adv-switch flag as the IAS emission still
needs to be implemented.
BUG=None
R=jvoung@chromium.org, stichnot@chromium.org
Review URL: https://codereview.chromium.org/1234803007.
diff --git a/src/IceInst.h b/src/IceInst.h
index cfa6dd3..48b18f4 100644
--- a/src/IceInst.h
+++ b/src/IceInst.h
@@ -67,6 +67,7 @@
FakeDef, // not part of LLVM/PNaCl bitcode
FakeUse, // not part of LLVM/PNaCl bitcode
FakeKill, // not part of LLVM/PNaCl bitcode
+ JumpTable, // not part of LLVM/PNaCl bitcode
Target // target-specific low-level ICE
// Anything >= Target is an InstTarget subclass.
// Note that the value-spaces are shared across targets.
@@ -108,6 +109,7 @@
/// Returns a list of out-edges corresponding to a terminator
/// instruction, which is the last instruction of the block.
+ /// The list must not contain duplicates.
virtual NodeList getTerminatorEdges() const {
// All valid terminator instructions override this method. For
// the default implementation, we assert in case some CfgNode
@@ -119,9 +121,8 @@
virtual bool isUnconditionalBranch() const { return false; }
/// If the instruction is a branch-type instruction with OldNode as a
/// target, repoint it to NewNode and return true, otherwise return
- /// false. Only repoint one instance, even if the instruction has
- /// multiple instances of OldNode as a target.
- virtual bool repointEdge(CfgNode *OldNode, CfgNode *NewNode) {
+ /// false. Repoint all instances of OldNode as a target.
+ virtual bool repointEdges(CfgNode *OldNode, CfgNode *NewNode) {
(void)OldNode;
(void)NewNode;
return false;
@@ -352,7 +353,7 @@
}
NodeList getTerminatorEdges() const override;
bool isUnconditionalBranch() const override { return isUnconditional(); }
- bool repointEdge(CfgNode *OldNode, CfgNode *NewNode) override;
+ bool repointEdges(CfgNode *OldNode, CfgNode *NewNode) override;
void dump(const Cfg *Func) const override;
static bool classof(const Inst *Inst) { return Inst->getKind() == Br; }
@@ -727,7 +728,7 @@
}
void addBranch(SizeT CaseIndex, uint64_t Value, CfgNode *Label);
NodeList getTerminatorEdges() const override;
- bool repointEdge(CfgNode *OldNode, CfgNode *NewNode) override;
+ bool repointEdges(CfgNode *OldNode, CfgNode *NewNode) override;
void dump(const Cfg *Func) const override;
static bool classof(const Inst *Inst) { return Inst->getKind() == Switch; }
@@ -899,6 +900,43 @@
const Inst *Linked;
};
+/// JumpTable instruction. This represents a jump table that will be
+/// stored in the .rodata section. This is used to track and repoint
+/// the target CfgNodes which may change, for example due to
+/// splitting for phi lowering.
+class InstJumpTable : public InstHighLevel {
+ InstJumpTable() = delete;
+ InstJumpTable(const InstJumpTable &) = delete;
+ InstJumpTable &operator=(const InstJumpTable &) = delete;
+
+public:
+ static InstJumpTable *create(Cfg *Func, SizeT NumTargets, CfgNode *Default) {
+ return new (Func->allocate<InstJumpTable>())
+ InstJumpTable(Func, NumTargets, Default);
+ }
+ void emit(const Cfg *Func) const override;
+ void emitIAS(const Cfg *Func) const override;
+ void addTarget(SizeT TargetIndex, CfgNode *Target) {
+ assert(TargetIndex < NumTargets);
+ Targets[TargetIndex] = Target;
+ }
+ bool repointEdges(CfgNode *OldNode, CfgNode *NewNode) override;
+ IceString getName(const Cfg *Func) const;
+ void dump(const Cfg *Func) const override;
+ static bool classof(const Inst *Inst) { return Inst->getKind() == JumpTable; }
+
+private:
+ InstJumpTable(Cfg *Func, SizeT NumTargets, CfgNode *Default);
+ void destroy(Cfg *Func) override {
+ Func->deallocateArrayOf<CfgNode *>(Targets);
+ Inst::destroy(Func);
+ }
+
+ const SizeT LabelNumber;
+ const SizeT NumTargets;
+ CfgNode **Targets;
+};
+
/// The Target instruction is the base class for all target-specific
/// instructions.
class InstTarget : public Inst {
